Bài giảng Hệ điều hành - Operating System (CNTT)

kết lúc thực thi tiến trình. • Một ñoạn lệnh nhỏ, gọi là stub, dùng ñể ñịnh vị hàm của thư viện ñang ở trong bộ nhớ. • Stub thi hành hàm vừa tìm thấy. • HðH cần phải kiểm tra xem hàm cần tìm có nằm trong bộ nhớ của tiến trình hay không. Memory management 8 Overlays • Chỉ lưu trong bộ nhớ chỉ thị và dữ liệu ñang cần. • Cần thiết khi một tiến trình lớn hơn dung lượng nhớ có thể cấp phát cho nó. Memory management 9 Một số khái niệm • Khi một chương trình thực hiện, nội dung của nó sẽ ñược ñưa vào bộ nhớ máy tính. • Khi ñó, hệ ñiều hành phải ñịnh ra một vùng nhớ trống cho chương trình hoạt ñộng. • Thao tác này gọi là location. Memory management 10 Một số khái niệm • Sau một thời gian hoạt ñộng sẽ có một số chương trình kết thúc bộ nhớ bị phân mảnh. • Một số chương trình khác muốn hoạt ñộng nhưng các khối nhớ trống còn lại không ñủ cấp cho nó. • Khi ñó hệ ñiều hành phải thực hiện thao tác relocation ñịnh vị lại các chương trình hiện có ñể tạo ra khối nhớ trống lớn nhất cho chương trình. Memory management 11 Một số khái niệm • Cơ chế overlay là cơ chế cho phép chia nhỏ 1 chương trình ra thành nhiều phần. • Mỗi phần là 1 trang (page). Tại một thời ñiểm chỉ thực hiện một hoặc một số trang. • Số trang thực hiện mỗi lần là số khung trang k. Các phần còn lại sẽ ñược ñể lại ở bộ nhớ ngoài. Memory management 12 Các kỹ thuật thay thế trang trong cơ chế overlay • Fifo: – Ví dụ: A cần thực hiện nội dung các page theo thứ tự sau: 2 9 6 8 2 4 3 7 5 3 9. Với số khung trang k = 3. ( Mỗi thời ñiểm tối ña thực hiện ñược 3 trang). – ðầu tiên 2 ñược nạp vào bộ nhớ. 2 (trạng thái bộ nhớ) – Tiếp theo 9 ñược nạp vào bộ nhớ. 2 9 – Tiếp theo 6 ñược nạp vào bộ nhớ. 2 9 6 – Sau ñó sẽ thay 2 bởi 8. 8 9 6 – Sau ñó sẽ thay 9 bởi 2. 8 2 6 – ??? 8 2 4 – ??? 3 2 4 – ??? 3 7 4 – ??? 3 7 5 – ??? 3 7 5 – ??? 9 7 5 Memory management 13 Các kỹ thuật thay thế trang trong cơ chế overlay • Ít sử dụng nhất trong tương lai: – Trang ñược thay thế là trang ít sử dụng nhất trong tương lai. Nếu 2 trang trong tương lai có số lần xuất hiện bằng nhau và khác 0 thì ta sẽ chọn trang xa nhất ñể thay thế. Nếu hai trang trong tương lai ñều không xuất hiện thì chọn trang ñầu tiên tính từ trên xuống. – Ví dụ: B cần thực hiện nội dung các page theo thứ tự sau: 2 9 6 8 5 2 4 3 7 5 3 8 9. Với số khung trang k = 3. ( Mỗi thời ñiểm tối ña thực hiện ñược 3 trang). – ðầu tiên 2 ñược nạp vào bộ nhớ. 2 (trạng thái bộ nhớ) – Tiếp theo 9 ñược nạp vào bộ nhớ. 2 9 – Tiếp theo 6 ñược nạp vào bộ nhớ. 2 9 6 – Sau ñó sẽ thay 6 bởi 8. 2 9 8 – Sau ñó sẽ thay 9 bởi 5. 2 5 8 – ??? 2 5 8 – ??? 4 5 8 – ??? 3 5 8 – ??? 3 5 7 – ??? 3 5 7 – ??? 8 5 7 – ??? 9 5 7 Memory management 14 Câu hỏi • A cần thực hiện nội dung các page theo thứ tự sau: 2 9 6 8 2 4 3 7 5 3 9. Với số khung trang k = 3. ( Mỗi thời ñiểm tối ña thực hiện ñược 3 trang). Hãy thực hiện theo kỹ thuật ít sử dụng nhất trong tương lai. • B cần thực hiện nội dung các page theo thứ tự sau: 2 9 6 8 5 2 4 3 7 5 3 8 9. Với số khung trang k = 3. ( Mỗi thời ñiểm tối ña thực hiện ñược 3 trang). Hãy hiện thực theo kỹ thuật thay thế trang fifo trong cơ chế overlay. Memory management 15 Không gian ñịa chỉ lôgic và vật lý • Khái niệm một không gian ñịa chỉ lôgic ñược kết buộc với một không gian ñịa chỉ vật lý ñóng vai trờ trung tâm trong một việc quản lý bộ nhớ tốt. – ðịa chỉ lôgic – ñược phát sinh bởi bộ xử lý; còn ñược gọi là ñịa chỉ ảo. – ðịa chỉ vật lý – ñịa chỉ ñược nhìn thấy bởi ñơn vị quản lý bộ nhớ. – Không gian ñịa chỉ – là tập hợp tất cả các ñịa chỉ ảo phát sinh bởi một chương trình. – Không gian vật lý – là tập hợp tất cả các ñịa chỉ vật lý tương ứng với các ñịa chỉ ảo. • ðịa chỉ lôgic và ñịa chỉ vật lý như nhau trong mô hình kết buộc ñịa chỉ tại thời ñiểm biên dịch và nạp; • ðịa chỉ lôgic và ñịa chỉ vật lý khác nhau trong mô hình kết buộc ñịa chỉ tại thời ñiểm thi hành. Memory management 16 ðơn vị quản lý Bộ nhớ Memory-Management Unit (MMU) • Thiết bị phần cứng ñể ánh xạ ñịa chỉ ảo thành ñịa chỉ vật lý. • Trong mô hình MMU, mỗi ñịa chỉ phát sinh bởi một tiến trình ñược cộng thêm giá trị của thanh ghi tái ñịnh vị (relocation register) tại thời ñiểm nó truy xuất ñến bộ ngớ. • Chương trình người dùng chỉ quan tâm ñến ñịa chỉ lôgic; nó không thấy ñịa chỉ vật lý thật sự. Memory management 17 Memory management 18 Các kiểu cấp phát vùng nhớ • Cấp phát bộ nhớ liên tục với một phân vùng • Cấp phát bộ nhớ liên tục với nhiều phân vùng có kích thước cố ñịnh • Cấp phát bộ nhớ liên tục với nhiều phân vùng có kích thước ñộng • Cấp phát bộ nhớ không liên tục bằng phân trang Memory management 19 Cấp phát liên tục một phân vùng • Bộ nhớ chính thường chia làm hai phân vùng: – Phần chứa HðH, thường nằm ở vùng nhớ thấp cùng với bảng vector ngắt. – Các tiến trình người dùng nằm ở vùng nhớ cao. • Cấp phát chỉ trên một vùng – Thanh ghi tái ñịnh vị ñược dùng ñể bảo vệ các tiến trình người dùng với nhau và bảo vệ dữ liệu và ñoạn mã của HðH. – Thanh ghi tái ñịnh vị lưu giá trị ñịa chỉ vật lý nhỏ nhất; thanh ghi giới hạn (limit register) chứa phạm vi ñịa chỉ lôgic  mọi ñịa chỉ lôgic phải nhỏ hơn thanh ghi giới hạn. – Thường dùng trong các hệ ñơn chương Memory management 20 9.03 Memory management 21 Cấp phát liên tục nhiều phân vùng cố ñịnh • Cấp phát liên tục với nhiều phân vùng cố ñịnh – Bộ nhớ ñược phân thành các phân vùng có kích thước cố ñịnh (có thể khác nhau hoặc bằng nhau) – Khi một tiến trình vào, nó sẽ ñược cấp phát cho một phân vùng có kích thước ñủ ñể chứa nó. • Khuyết ñiểm: – Mỗi phân vùng chỉ ñược lưu một tiến trình  số tiến trình ñồng thời bị giới hạn bởi số phân vùng – Nếu kích thước của tiến trình không vừa ñúng bằng kích thước của phân vùng chứa nó, phần bộ nhớ không ñược sử dụng sẽ lãng phí  hiện tượng phân mảnh nội vi (internal fragmentation). – Sử dụng thanh ghi tái ñịnh vị và thanh ghi giới hạn ñể bảo vệ các tiến trình khỏi bị xâm phạm lẫn nhau. Memory management 22 Cấp phát liên tục nhiều phân vùng cố ñịnh Memory management 23 Cấp phát liên tục nhiều phân vùng cố ñịnh Memory management 24 P3 P1 P5 400 900 1900 2560 Dư 200Kb Dư 400Kb Dư 160Kb Cấp phát liên tục nhiều phân vùng cố ñịnh Giả sử các phân vùng cố ñịnh là 500 Kb, 1000Kb và 656 Kb. Memory management 25 Cấp phát liên tục nhiều phân vùng ñộng • Cấp phát liên tục với nhiều phân vùng ñộng – Khi một tiến trình vào hệ thống, cấp phát cho nó vùng nhớ vừa ñúng với kích thước của tiến trình. – Khi tiến trình kết thúc vùng nhớ ñó sẽ bị thu hồi và cấp phát cho các tiến trình khác – Kích thước của vùng nhớ ñộng – Vị trí của vùng nhớ cũng ñộng • Khuyết ñiểm: – Không còn hiện tượng phân mảnh nội vi nhưng xuất hiện hiện tượng phân mảnh ngoại vi (external fragmentation)  có khả năng tổng vùng nhớ còn trống có thể ñủ ñể cấp phát cho nhu cầu của tiến trình nhưng không thể vì chúng nằm rải rác. – Giải pháp cho phân mảnh ngoại vi dồn vùng nhớ  phức tạp, chi phí cao. – Nếu trong quá trình xử lý tiến trình có nhu cầu sử dụng thêm vùng nhớ  phải dời chỗ tiến trình hoặc cấp phát thêm nếu còn trống phần ngay sau nó  cần phải có một thuật toán lường trước hoặc tối ưu việc cấp phát vùng nhớ tránh phải dời chỗ tiến trình nhiều. Memory management 26 Cấp phát liên tục nhiều phân vùng ñộng Memory management 27 Cấp phát liên tục nhiều phân vùng ñộng Memory management 28 Relocation Memory management 29 Relocation Memory management 30 Cấp phát liên tục nhiều phân vùng ñộng • First-fit: Cấp phát cho vùng trống ñầu tiên có thể chứa ñược tiến trình. • Best-fit: Cấp phát vùng trống nhỏ nhất có thể chứa ñược tiến trình; phải tìm kiếm trên toàn bộ danh sách các vùng trống. • Worst-fit: Cấp phát vùng trống lớn nhất; phải tìm kiếm trên toàn bộ danh sách Chọn vùng nhớ trống nào ñể cấp phát cho một tiến trình khi có nhu cầu First-fit tốt hơn về tốc ñộ và Best-fit tối ưu hóa việc sử dụng bộ nhớ Memory management 31 Câu hỏi bài tập • Vẽ sơ ñồ cấp phát liên tục nhiều phân vùng ñộng theo: – First fit ? – Best fit ? – Worst fit? Trong trường hợp của hình bên Memory management 32 Swapping • Một tiến trình có thể bị chuyển ra ngoài tạm thời ñến một vùng lưu trữ nào ñó khi tiến trình ñó phải chờ ñợi trong khoảng thời gian dài ñể giải phóng vùng nhớ cho tiến trình khác (swap out). • Khi tiến trình kết thúc việc chờ, nó có thể ñược mang vào lại bộ nhớ chính ñể xử lý (swap in). • Thao tác swap cũng có thể xảy ra khi dùng các thuật toán ñiều phối tiến trình có ñộ ưu tiên Memory management 33 Swapping • Nâng cao mức ñộ ña chương • Khi tiến trình ñược mang lại bộ nhớ chính, nó sẽ ñược nạp vào vùng nhớ nào? – Kết buộc lúc nạp  phải ñưa vào vùng nhớ cũ của nó – Kết buộc lúc thi hành  thay ñổi thanh ghi tái ñịnh vị • Cần sử dụng bộ nhớ phụ ñủ lớn ñể lưu các tiến trình bị khóa. • Thời gian swap chủ yếu là thời gian chuyển tiến trình từ vùng nhớ chính ñến bộ nhớ phụ  một tiến trình cần phải có khoảng thời gian xử lý ñủ lớn. Memory management 34 Mô hình thao tác swapping Memory management 35 Khuyết ñiểm của các pp cấp phát liên tục • Xảy ra hiện tượng phân mảnh bộ nhớ: – Phân mảnh nội vi (internal fragmentation) • Kích thước phân vùng cố ñịnh – Phân mảnh ngoại vi (external fragmentation) • Kích thước phân vùng ñộng Memory management 36 Cấp phát bộ nhớ bằng pp phân trang (Paging) • Không gian ñịa chỉ lôgic của một tiến trình có thể không liên tục. • Chia bộ nhớ vật lý thành các khối có kích thước cố ñịnh gọi là khung (frame) (kích thước là số mũ của 2, từ 512 ñến 8192 bytes). • Chia bộ nhớ lôgic thành các khối có cùng kích thước và gọi là trang (pages). • Lưu trạng thái của tất cả các khung (frame). • ðể chạy một chương trình có kích thước n trang, cần phải tìm n khung trống và nạp chương trình vào. • Tạo một bảng trang ñể chuyển ñổi ñịa chỉ lôgic sang ñịa chỉ vật lý. • Có hiện tượng phân mảnh bộ nhớ nội vi. Memory management 37 Mô hình chuyển ñổi ñịa chỉ • ðịa chỉ ñược tạo ra bởi CPU gồm có hai phần: – Số trang (Page number) (p) – ñược dùng như là một chỉ số của một bảng trang chứa ñịa chỉ cơ sở của mỗi trang trong bộ nhớ vật lý. – Page offset (d) – kết hợp với ñịa chỉ cơ sở ñể ñịnh ra không gian ñịa chỉ vật lý ñược gởi ñến bộ nhớ. Memory management 38 Kiến trúc chuyển ñổi ñịa chỉ Memory management 39 Ví dụ trang Memory management 40 Cài ñặt bảng trang • Bảng trang ñược ñặt trong bộ nhớ. • Page-table base register (PTBR) chỉ ñến bảng trang. • Page-table length register (PRLR) cho biết kích thước của bảng trang. • Với mô hình này, mọi sự truy cập chỉ thị/dữ liệu ñều ñòi hỏi hai lần truy cập vùng nhớ: 1) truy cập bảng trang; 2) chỉ thị hoặc dữ liệu  có vẻ chậm. • Khắc phục vấn ñề hai lần truy cập vùng nhớ bằng cách sử dụng một vùng ñệm phần cứng tra cứu nhanh ñặc biệt (special fast-lookup hardware) gọi là associative registers hoặc translation look-aside buffers (TLBs) Memory management 41 Memory management 42 Effective Access Time • Thời gian tìm kiếm trong associate registers = ε ñơn vị thời gian • Giả sử thời gian truy cập bộ nhớ là 1 ms • Gọi α là tỉ lệ số lần số trang ñược tìm thấy trong các associative registers. • Effective Access Time (EAT) EAT = (1 + ε) α + (2 + ε)(1 – α) = 2 + ε – α Memory management 43 Bảo vệ vùng nhớ • Làm sao biết trang nào của tiến trình nào? Cần bảo vệ các tiến trình truy xuất vào trang không phải của mình. • Việc bảo vệ vùng nhớ ñược cài ñặt bằng cách liên kết một khung với một bit, gọi là bit kiểm tra hợp lệ (valid- invalid bit). • Valid-invalid bit ñược ñính kèm vào mỗi ô trang bảng trang: – “valid” chỉ ra rằng trang ñi kèm là nằm trong không gian ñịa chỉ lôgic của tiến trình vì vậy truy xuất trang này là hợp lệ. – “invalid” chỉ ra rằng trang ñi kèm không nằm trong không gian ñịa chỉ lôgic của tiến trình. Memory management 44 Memory management 45 Tổ chức bảng trang • Chỉ một bảng trang (cho mỗi tiến trình) • Tiến trình nhiều trang  quản lý bộ nhớ rất lớn  số trang nhiều  kích thước của bảng trang phải lớn  không tối ưu. • Giải pháp: – Phân trang ña cấp (multilevel paging) – Bảng trang nghịch ñảo Memory management 46 Phân trang ña cấp • Phân chia bảng trang thành các phần nhỏ • Bản thân bảng trang cũng ñược phân trang Memory management 47 Mô hình phân trang hai cấp Memory management 48 Ví dụ phân trang 2 cấp • Một ñịa chỉ lôgic (trên máy 32 bit với kích thước trang là 4K) ñược chia thành: – Page number: 20 bit. – Page offset: 12 bit. • Bởi vì bảng trang ñược phân trang, số trang tiếp tục ñược phân chia thành: – Page number: 10-bit. – Page offset: 10 bit. • ðịa chỉ lôgic sẽ có cấu trúc như sau: page number page offset pi p2 d 10 10 12 Memory management 49 Chuyển ñổi ñịa chỉ • Address-translation scheme for a two-level 32-bit paging architecture Memory management 50 Phân tích • Nếu chỉ dùng một trang – bảng trang sẽ có 220 phần tử. • Nếu dùng phân trang 2 cấp – Bảng trang ngoài cần 210 phần tử – Bảng trang trong vẫn có 220 phần tử nhưng có thể ñược ñặt ở vùng nhớ phụ Memory management 51 Bảng trang nghịch ñảo • Sử dụng một bảng trang duy nhất cho mọi tiến trình • Một entry cho mỗi khung (bộ nhớ vật lý). • Một entry bao gồm ñịa chỉ ảo của khung và tiến trình sở hữu khung ñó. • Giảm kích thước lưu trữ bảng trang , nhưng tăng thời gian tìm kiếm bảng trang. • Dùng bảng băm ñể tăng tốc tìm kiếm. Memory management 52 Kiến trúc bảng trang nghịch ñảo Memory management 53 Chia sẻ và bảo vệ • Chia sẻ và bảo vệ – Ở cấp ñộ trang – ðứng ở khía cạnh người dùng, khá bất tiện • Vd: ðoạn mã nằm trên nhiều trang  phải chia sẻ tất cả các trang ñó với nhau. – ðoạn mã phải nằm ở một vị trí giống nhau trông tất cả các không gian ñịa chỉ của của tiến trình muốn chia sẻ Memory management 54 Ví dụ chia sẻ trang Memory management 55 Phân ñoạn • Hỗ trợ quản lý bộ nhớ theo góc ñộ người dùng. • Một chương trình bao gồm nhiều phân ñoạn (segment): – ðoạn mã – Biến toàn cục, dữ liệu – stack – heap Memory management 56 Góc ñộ người dùng 1 3 2 4 1 4 2 3 user space physical memory space Memory management 57 Kiến trúc phân ñoạn • ðịa chỉ lôgic = • Bảng phân ñoạn (Segment table) – chuyển ñổi ñịa chỉ hai chiều thành ñịa chỉ vật lý một chiều. Mỗi ô trong bảng gồm có: – Thanh ghi nền (base) – chứa ñịa chỉ vật lý bắt ñầu của phân ñoạn trong bộ nhớ chính. – Thanh ghi giới hạn (limit) – chỉ kích thước của phân ñoạn. • Segment-table base register (STBR) lưu trữ ñịa chỉ của bảng phân ñoạn trong vùng nhớ. • Segment-table length register (STLR) chỉ số segment ñược sử dụng bởi 1 chương trình Memory management 58 Chuyển ñổi ñịa chỉ Memory management 59 Kiến trúc phân ñoạn (tt) • Tái ñịnh vị. – ðộng (dynamic partition) – Thông qua bảng phân ñoạn • Chia sẻ. – Có thể chia sẻ các phân ñoạn giữa các chương trình – Sử dụng chung chỉ số sement • Cấp phát. – first fit/best fit – Có hiện tượng phân mảnh ngoại vi Memory management 60 Chuyển ñổi ñịa chỉ Memory management 61 Kiến trúc phân ñoạn (tt) • Bảo vệ – Mỗi entry thêm một bit “valid bit”. Nếu valid bit = 0 ⇒ truy cập phân ñoạn không hợp lệ – Hỗ trợ phân quyền theo từng thao tác read/write/execute Memory management 62 Memory management 63 Kết hợp phân trang và phân ñoạn • Ý tưởng: – Phân trang trong mỗi phân ñoạn – Bộ nhớ = nhiều phân ñoạn – Phân ñoạn = nhiều trang • Giải quyết tình trạng phân mảnh ngoại vi • Mỗi phần tử của bảng phân ñoạn gồm hai thành phần: – Thanh ghi giới hạn (limit): kích thước của phân ñoạn (giống với phân ñoạn thuần) – Thanh ghi cơ sở (base): chứa ñịa chỉ của bảng trang của phân ñoạn ñó (khác với phân ñoạn thuần) Memory management 64 Các tiêu chuẩn so sánh các pp quản lý vùng nhớ • Hỗ trợ phần cứng • Hiệu năng • Sự phân mảnh • Khả năng tái ñịnh vị • Hỗ trợ swap • Chia sẻ • Bảo vệ 11/07/08 1 Bộ nhớ ảo Trần Sơn Hải Khoa Toán – Tin học ðại học Sư phạm TPHCM Heavily reference to Operating System Slide of Hoang Than Anh Tuan, University of Pedagogy, HCMC 11/07/08 2 Bộ nhớ ảo: Ý tưởng • Hai ñặc trưng quan trọng của kiến trúc phân ñoạn và phân trang: – Mọi sự truy xuất vùng nhớ của một tiến trình ñều ñược chuyển ñổi ñịa chỉ lúc thi hành (run-time)  có thể swap-in, swap- out. – Một tiến trình ñược phân ra thành một số phần (trang hoặc ñoạn) và không nhất thiết phải nằm liên tục nhau 11/07/08 3 Bộ nhớ ảo: Ý tưởng (tt) • Nếu hai tính chất trên ñược bảo ñảm thì không nhất thiết tất cả các trang hoặc phân ñoạn phải nằm trong bộ nhớ chính lúc thi hành. • Ưu ñiểm: – Có nhiều tiến trình trong bộ nhớ hơn  giải thuật lập lịch sẽ tối ưu hơn  nâng cao mức ñộ ña chương – Một tiến trình có thể lớn hơn kích thước của bộ nhớ chính 11/07/08 4 Nguyên lý cục bộ Các thao tác truy cập vùng nhớ có khuynh hướng cụm lại (cluster). Sau một khoảng thời gian ñủ dài, cụm này có thể sẽ thay ñổi, nhưng trong một khoảng thời gian ngắn, bộ xử lý chủ yếu chỉ làm việc trên một số cụm nhất ñịnh. Sau một khoảng thời gian ñủ dài, cụm này có thể sẽ thay ñổi, nhưng trong một khoảng thời gian ngắn, bộ xử lý chủ yếu chỉ làm việc trên một số cụm nhất ñịnh. 11/07/08 5 Giải thích Các câu lệnh cơ bản chủ yếu là tuần tự (thi hành từ trên xuống dưới). Câu lệnh không tuần tự là câu lệnh rẽ nhánh (câu lệnh ñiều kiện) thường chiếm tỉ lệ khá ít. Trong một khoảng thời gian ngắn, các chỉ thị thông thường nằm trong một số hàm, thủ tục nhất ñịnh. Hầu hết các câu lệnh lặp chứa một số ít các chỉ thị và lặp lại nhiều lần. Do ñó trong suốt thời gian lặp, việc tính toán hầu như chỉ diễn ra trong một vùng nhỏ liên tục. Khi truy cập vào một cấu trúc dữ liệu trước ñó, thông thường các câu lệnh ñặt liền nhau sẽ truy cập ñến các thành phần khác nhau của cùng một cấu trúc dữ liệu. 11/07/08 6 Các vấn ñề liên quan ñến bộ nhớ ảo • Cần có sự hỗ trợ phần cứng về kiến trúc phân trang và phân ñoạn – ðã khảo sát • Cần có thuật toán hiệu quả ñể quản lý việc chuyển ñổi các trang, phân ñoạn từ bộ nhớ chính vào bộ nhớ phụ và ngược lại – Nguyên lý cục bộ – ðĩa cứng hoạt ñộng theo khối – Dự ñoán ñược các trang và phân ñoạn dựa vào lịch sử truy xuất vùng nhớ trước ñó. 11/07/08 7 Quản lý việc chuyển ñổi giữa vùng nhớ chính và vùng nhớ phụ • Các chính sách cần xét: – Chính sách nạp (fetch policy): khi nào thì một trang ñược nạp vào bộ nhớ? – Chính sách ñặt (placement policy): trang hoặc phân ñoạn sẽ ñược ñặt ở ñâu trong bộ nhớ chính? – Chính sách thay thế (replacement policy): chọn trang nào ñưa ra khỏi bộ nhớ phụ khi cần nạp một trang mới vào bộ nhớ chính? 11/07/08 8 Cài ñặt bộ nhớ ảo • Kỹ thuật phân trang theo yêu cầu (demand paging) • Kỹ thuật phân ñoạn theo yêu cầu (demand segmentation) – Khó vì kích thước không ñồng nhất 11/07/08 9 Kỹ thuật phân trang theo yêu cầu • Phân trang theo yêu cầu = Phân trang + swapping • Tiến trình là một tập các trang thường trú trên bộ nhớ phụ. • Một trang chỉ ñược nạp vào bộ nhớ chính khi có yêu cầu. • Khi có yêu cầu về một trang nào ñó, cần có cơ chế cho biết trang ñó ñang ở trên ñó hoặc ở trong bộ nhớ – Sử dụng bit valid/invalid – Valid: có trong bộ nhớ chính – Invalid: trang không hợp lệ hoặc trang ñang nằm trong bộ nhớ phụ 11/07/08 10 Cơ chế phần cứng • Bảng trang – Phải phản ánh ñược một trang ñang nằm trong bộ nhớ chính hay bộ nhớ phụ và tương ứng ñang nằm ở vị trí nào (trong bộ nhớ chính hoặc bộ nhớ phụ) • Bộ nhớ phụ – Dùng một không gian trên ñĩa cứng thường gọi là không gian swapping. 11/07/08 11 11/07/08 12 11/07/08 13 Quá trình xử lý một trang không có trong bộ nhớ chính (lỗi trang) 1. Kiểm tra trang ñược truy xuất có hợp lệ hay không? 2. Nếu truy xuất không hợp lệ  kết thúc Ngược lại  bước 3 3. Tìm vị trí chứa trang muốn truy xuất trên ñĩa cứng. 4. Tìm một khung trang trống trên bộ nhớ chính 1. Nếu tìm thấy  bước 5 2. Nếu không tìm thấy khung trang trống, tìm một khung trang “nạn nhân” và chuyển nó ra bộ nhớ phụ, cập nhật bảng trang 5. Chuyển trang muốn truy xuất từ bộ nhớ phụ vào bộ nhớ chính, cập nhật bảng trang, bảng khung trang. 6. Tái kích hoạt tiến trình tại chỉ thị truy xuất ñến trang 11/07/08 14 11/07/08 15 Thay thế trang • Là cơ chế thay thế một trang ñang nằm trong bộ nhớ nhưng chưa cần sử dụng bằng một trang ñang nằm trong ñĩa (không gian swapping) ñang ñược yêu cầu. • Hai thao tác: – Chuyển trang từ bộ nhớ chính ra bộ nhớ phụ – Mang trang từ bộ nhớ phụ vào vào nhớ chính • Giảm số lần thao tác bằng bit cập nhập (dirty bit) – Bit cập nhật = 1: nội dung trang ñã bị thay ñổi  cần lưu lại trên ñĩa – Bit cập nhật = 0: nội dung trang không bị thay ñổi  không cần lưu lại trên ñĩa 11/07/08 16 Một phần tử trong bảng trang Page number Valid bit Dirty bit 11/07/08 17 Hiệu quả của phân trang theo yêu cầu • Gọi p là xác suất xảy ra lỗi trang: – P = 0: không có lỗi trang – P = 1: mỗi truy xuất ñến bộ nhớ ñều có lỗi trang • MA: thời gian truy xuất ñến bộ nhớ chính • TDP: thời gian xử lý lỗi trang = [+ swapout] + swapin + tái kích họat • TEA: thời gian thật sự ñể thực hiện một truy xuất bộ nhớ TEA = (1-p)MA + p*TDP • Mấu chốt là p: p càng thấp thì hiệu quả của phân trang theo yêu cầu càng cao 11/07/08 18 Thuật toán thay thế trang • Ý tưởng chính: – Chọn trang nạn nhân là trang mà sau khi thay thế sẽ gây ra ít lỗi trang nhất. • Các thuật toán: – FIFO – Tối ưu (ít sử dụng nhất trong tương lai) – LRU – Xấp xỉ LRU 11/07/08 19 Thuật tóan FIFO • Ý tưởng: – Ghi nhận thời ñiểm một trang ñược ñưa vào bộ nhớ – Thay thế trang ở trong bộ nhớ lâu nhất • Có thể không cần ghi nhận thời ñiểm ñưa mộ trang vào bộ nhớ. Sử dụng danh sách trang theo kiểu FIFO  trang thay thế luôn là trang ñầu • Dễ hiểu, dễ cài ñặt, nhưng không lôgic trong trường hợp những trang ñầu tiên ñược nạp vào thường những trang quan trọng, chứa dữ liệu truy xuất thường xuyên  chuyển nó ra sẽ gây lỗi trang cho những lần truy xuất sau • Nghịch lý Belady: số lượng lỗi trang sẽ tăng lên nếu số lượng khung trang tăng lên. 11/07/08 20 Thuật toán tối ưu • Ý tưởng: – Thay thế trang sẽ ñược lâu sử dụng nhất trong tương lai. • Hoàn hảo về mặt ý tưởng nhưng không khả thi về mặt thực tế – Làm sao dự ñoán ñược chuỗi các trang truy xuất trong tương lai. 11/07/08 21 Thuật toán “Lâu nhất chưa sử dụng” (Least-recently-used LRU) • Ý tưởng: – Ghi nhận thời ñiểm cuối cùng trang ñược truy cập – Thay thế trang chưa ñược truy cập lâu nhất • Dùng quá khứ gần ñể dự ñoán tương lai – FIFO: thời ñiểm nạp vào – Tối ưu: thời ñiểm sẽ truy cập 11/07/08 22 Least-recently-used LRU • Các cách cài ñặt: – Sử dụng bộ ñếm • Mỗi phần tử trong bảng trang có một thành phần ghi nhận thời ñiểm truy xuất mới nhất. • CPU có một bộ ñếm, tăng khi có một truy xuất ñến bộ nhớ • Cập nhật thời ñiểm theo bộ ñếm • Trang có thời ñiểm truy xuất nhỏ nhất sẽ bị thay thế – Sử dụng stack • Lưu các số hiệu trang • Khi một trang ñược truy xuất  chuyển số hiệu trang lên ñầu stack • Thay thế trang có số hiệu ở ñáy stack 11/07/08 23 • LRU ñòi hỏi phần cứng hỗ trợ khá nhiều – Biến bộ ñếm – Stack • Tìm các thuật toán xấp xỉ LRU 11/07/08 24 Thuật toán xấp xỉ LRU • Có 3 thuật toán – Sử dụng nhiều bit tham khảo (reference bit) – Cơ hội thứ hai – Cơ hội thứ hai cải tiến • Ý tưởng chính: bit tham khảo ñược thêm vào mỗi phần tử trong bảng trang – Ban ñầu = 0 – Có truy xuất  1 – Sau mỗi chu kỳ qui ñịnh trước, kiểm tra bit này và gán nó trở lại là 0. – Biết ñược trang nào ñã ñược truy xuất gần ñây nhưng không biết ñược thứ tự truy xuất. 11/07/08 25 Thuật toán nhiều bit tham khảo • Ý tưởng: – 1 bit tham khảo chỉ biết ñược thông tin của 1 chu kỳ – Nhiều bit tham khảo sẽ biết ñược thông tin của nhiều chu kỳ. • Sử dụng thêm 8 bit tham khảo cho mỗi phần tử trong bảng trang • Sau một chu kỳ, một ngắt ñược phát sinh, HðH sẽ ñặt bit tham khảo của trang ñó (0 hoặc 1) vào bit cao nhất trong 8 bit, loại bỏ bit cuối cùng (thấp nhất) • 8 bit sẽ lưu trữ tình hình truy xuất ñến trang trong 8 chu kỳ gần nhất • 10001000 sẽ tốt hơn 01111111 • Nếu xem là số nguyên không dấu thì trang ñược thay thế là trang có số tương ứng nhỏ nhất. 11/07/08 26 Thuật toán cơ hội thứ hai • Ý tưởng: – Sử dụng một một bit tham khảo duy nhất – Ý tưởng như FIFO có cải tiến • Nếu bit tham khảo = 0  thay thế trang • Ngược lại, cho trang này cơ hội thứ hai ñặt bit tham khảo về 0, chọn trang FIFO kế tiếp. Trang ñược cho cơ hội thứ hai ñặt vào cuối hàng ñợi. • Một trang ñã ñược cho cơ hội thứ hai sẽ không bị thay thế trước khi các trang còn lại bị thay thế • Có thể cài ñặt bằng một xâu vòng (danh sách liên kết vòng). 11/07/08 27 Thuật toán cơ hội thứ hai nâng cao • Ý tưởng: – Xét cặp bit: reference bit và dirty bit – (0,0): không truy xuất, không sửa ñổi  trang tốt nhất ñể thay thế. – (0,1): không truy xuất, có sửa ñổi  cần lưu lại trang thay thế. – (1,0): có truy xuất, chưa sửa ñổi  có khả năng sẽ ñược sử dụng tiếp. – (1,1): có truy xuất, có sửa ñổi  có khả năng ñược sử dụng tiếp và nếu thay thế cần lưu lại. – Lớp ñầu tiên có ñộ ưu tiên thấp nhất và lớp cuối cùng có ñộ ưu tiên cao nhất. 11/07/08 28 Cấp phát khung trang • Trả lời câu hỏi: – Mỗi tiến trình sẽ ñược cấp phát bao nhiêu khung trang? • Các hướng tiếp cận: – Cấp phát cố ñịnh: • Cấp phát công bằng • Cấp phát theo tỉ lệ – Cấp phát theo ñộ ưu tiên 11/07/08 29 Cấp phát cố ñịnh • Mỗi tiến trình sẽ ñược cấp phát một số lượng khung trang cố ñịnh ngay từ ñầu cho ñến khi kết thúc thi hành. • Có 2 hướng – Cấp phát công bằng • M khung trang, n tiến trình  mỗi tiến trình m/n – Cấp phát theo tỉ lệ • Si: kích thước bộ nhớ ảo của tiến trình I • S = sum(Si) • M khung trang • Tiến trình I sẽ có: (Si/S)*M khung trang 11/07/08 30 Cấp phát theo ñộ ưu tiên • Số khung trang dành cho mỗi tiến trình phụ thuộc vào ñộ ưu tiên của tiến trình tại thời ñiểm xác ñịnh. • Nếu tiến trình pi phát sinh lỗi trang, chọn một trong các khung trang của nó ñể thay thế hoặc một khung trang của các tiến trình có ñộ ưu tiên thấp hơn. 11/07/08 31 Thay thế toàn cục và Thay thế cục bộ • Thay thế toàn cục – Trang “nạn nhân” có thể là bất cứ khung trang nào của hệ thống, không nhất thiết phải là khung trang của tiến trình ñó. • Thay thế cục bộ – Trang nạn nhân là một trong số khung trang của tiến trình ñó. • Có vẻ thay thế toàn cục sẽ linh hoạt hơn nhưng có thể gây ra hiệu ứng trì trệ hệ thống (thrashing) • Thrashing: tự ñọc tài liệu 1Hệ thống quản lý tập tin 2 Tổng quan • Khái niệm cơ bản • Mô hình quản lý tập tin • Cài ñặt hệ thống quản lý tập tin • Truy xuất hệ thống quản lý tập tin 3Các khái niệm cơ bản • Bộ nhớ ngoài (secondary storage) – Có khả năng lưu trữ dữ liệu trong thời gian dài – Công dụng: • Dữ liệu có kích thước rất lớn  bộ nhớ trong không ñủ ñể chứa • Phải ñược lưu lại trong thời gian dài, ngay cả khi chương trình không chạy • Tập tin – Là ñơn vị lưu trữ thông tin cơ bản của bộ nhớ ngoài – Là sự trừu tượng hóa của bộ nhớ ngoài – ðược quản lý bởi hệ ñiều hành – Có một tên – Tập hợp các sector 4 Các khái niệm cơ bản • Thư mục – Là một tập tin ñặc biệt, có thể lưu trữ nhiều tập tin khác. • Hệ thống quản lý tập tin – Là một phần của hệ ñiều hành cung cấp các chức năng quản lý tập tin (thư mục) như: • Cách hiển thị tập tin • Cách ñặt tên tập tin • Tổ chức thông tin của tập tin • Thao tác trên tập tin • Sử dụng và bảo vệ tập tin 5Mô hình quản lý tập tin • Cách ñặt tên: – Phụ thuộc vào hệ ñiều hành – Thường là các chữ cái và số – Phân biệt chữ hoa, chữ thường??? – Chia làm 2 phần ñược phân cách bởi dấu “.”: • Phần tên: tên của tập tin • Phần mở rộng: ñể xác ñịnh loại tập tin 6 Cấu trúc của tập tin • Có thể chia làm 3 loại – Dãy tuần tự các byte không cấu trúc – Dãy các record có kích thước cố ñịnh – Cấu trúc cây: gồm nhiều record, không nhất thiết phải có kích thước bằng nhau. Mỗi record có thể có khóa ñể tìm kiếm nhanh hơn. 7Phân loại các kiểu tập tin • Tập tin bình thường: – Tập tin văn bản: có phân biệt ký tự xuống dòng  thích hợp với các chương trình soạn thảo – Tập tin nhị phân: có qui ñịnh cấu trúc riêng. • Thư mục: là tập tin dùng ñể lưu trữ các tập tin khác • Tập tin dành riêng cho hệ ñiều hành: thường ñược gắn với một thiết bị phần cứng. 8 Truy xuất tập tin • Truy xuất tuần tự – ðể ñến ñược byte (record) thứ i phải ñi qua i byte (record) trước ñó. • Truy xuất ngẫu nhiên 9Các thuộc tính của tập tin • Mô tả các thông tin của tập tin • Ví dụ: – Bảo vệ: ai ñược quyền truy xuất. – Ngày giờ tạo tập tin – 10 Hệ thống thư mục • Thư mục chứa nhiều entry, mỗi entry tương ứng với một tập tin. • Entry chứa: – Tên tập tin, thuộc tính, ñịa chỉ trên bộ nhớ ngoài lưu tập tin. – Hoặc tên tập tin và một con trỏ trỏ ñến cấu trúc chứa thuộc tính, ñịa chỉ trên bộ nhớ ngoài. • Một tập tin luôn nằm trong một thư mục  khi có yêu cầu mở một tập tin, HðH tìm trên thư mục ñã chỉ ra cho ñến kho tìm ñược tập tin cần tìm, ñưa vào bộ nhớ chính. Thao tác sau ñó hầu hết sẽ làm việc trên bộ nhớ chính. 11 Hệ thống thư mục • Theo dạng thư mục ñơn: – Chỉ có một thư mục và mọi tập tin ñều ñặt trong thư mục ñó  khó ñặt tên tập tin vì có thể trùng nhau. • Theo dạng hai cấp: – Có một thư mục gốc, trong thư mục gốc có nhiều thư mục con và các tập tin sẽ ñược lưu vào trong các thư mục con. • Theo dạng ña cấp – Có một thư mục gốc, một thư mục có thể chứa các thư mục con và các tập tin. 12 Hệ thống thư mục 1 cấp 13 Hệ thống thư mục 2 cấp 14 Hệ thống thư mục ña cấp (cấu trúc cây) 15 Hệ thống thư mục ña cấp (không có chu trình) 16 Hệ thống thư mục tổng quát 17 ðường dẫn • ðường dẫn: cho phép xác ñịnh vị trí của tập tin trong hệ thống thư mục. • Trong hệ thống thư mục theo kiểu ña cấp (cây thư mục) có hai cách ñể xác ñịnh một tập tin. • ðường dẫn tuyệt ñối: mỗi tập tin ñược gán một ñường dẫn từ thư mục gốc ñến tập tin. • ðường dẫn tương ñối: người dùng có thể qui ñịnh một thư mục hiện hành, mọi ñường dẫn không cần chỉ ra từ thư mục gốc mà chỉ cần chỉ ra từ thư mục hiện hành • Lưu ý: “.” thư mục hiện hành, “..” thư mục cha 18 Các chức năng • Tập tin: – Tạo – Xóa – Mở – ðóng – ðọc – Ghi – Thêm – Tìm – Lấy thuộc tính và thay ñổi thuộc tính – ðổi tên 19 • Thư mục: – Tạo – Xóa – Mở (thư mục) – ðóng – ðọc thư mục – ðổi tên – Liên kết – Bỏ liên kết Các chức năng 20 Hệ Thống Quản Lý Tập Tin • ðóng vai trò trung gian nhờ vào ñó người dùng chỉ cần cung cấp tên có thể xác ñịnh ñược tập tin nằm ở những sector nào. • Hai ñối tượng chủ yếu trên HTQLTT là tập tin và thư mục. 21 Hệ Thống Quản Lý Tập Tin • Multi System là cơ chế cho phép trên 1 ñĩa cứng có nhiều hệ ñiều hành. • Mỗi vùng trên ñĩa cứng thuộc về một hệ ñiều hành gọi là 1 partition. • Một hệ ñiều hành có thể có nhiều partition khi ñó nó sẽ có 1 partition chính: primary partition, còn lại là extended partition. 22 Hệ Thống Quản Lý Tập Tin • Khi ñĩa cứng có nhiều hệ ñiều hành phải tồn tại 1 hệ ñiều hành ñược khởi ñộng ñầu tiên thì partition chính của hệ ñiều hành ñó ñược gọi là active. • ðể quản lý các partition, ta sử dụng sector ñầu tiên trên ñĩa gọi là Master Boot Record. Mỗi partition sẽ chiếm 16 bytes thông tin trên Master Boot Record 23 Hệ Thống Quản Lý Tập Tin • Mỗi partition sẽ chiếm 16 bytes thông tin trên Master Boot Record Khoảng cách từ Master Boot ñến partition 48 Dung lượng partition412 Sector kết thúc17 Track kết thúc16 Head kết thúc15 F9 – DOS, FA - Win Byte mô tả loại hệ ñiều hành14 Sector bắt ñầu13 Track bắt ñầu12 Head bắt ñầu11 80h hoặc 0Active partition10 Ví dụÝ Nghĩaðộ lớnOffset 24 Hệ Thống Quản Lý Tập Tin • Mutil Volume: là cơ chế cho phép trên 1 partition có thể chia nhỏ ra nhiều phần. Mỗi phần ñược gọi là 1 volume. • Mỗi volume sẽ tương ứng với 1 ổ ñĩa logic. • Một volume sẽ có cấu trúc như sau: • Với DOS, Win, 1 partition thường tương ứng với 1 volume, 1 ổ ñĩa logic • ðiã mềm ñược xem là 1 volume. DataQuản lýBoot Sector 25 Cài ñặt hệ thống quản lý tập tin • Mỗi tập tin ñược lưu trên nhiều block (khối) khác nhau của 1 volume.Mỗi block có kích thước 2k sector và ñánh số từ 0. • ðĩa mềm 1 block = 1 sector. Một block có các trạng thái sau: – Free: chưa thuộc về tập tin nào – Used: thuộc vào duy nhất một tập tin • Vấn ñề là hệ thống cần phải biết tất cả các khối của một tập tin nào ñó  bảng phân phối vùng nhớ • Các phương pháp chính – ðịnh vị liên tiếp (mô hình tuần tự) – ðịnh vị bằng chỉ số (mô hình Index) – ðịnh vị bằng danh sách liên kết (Mô hình liên kết) – ðịnh vị bằng danh sách liên kết sử dụng chỉ số (Mô hình liên kết chỉ số) – I-node 26 ðịnh vị liên tiếp • Các khối của tập tin ñược cấp phát liên tiếp nhau  chỉ cần lưu khối ñầu tiên và kích thước của tập tin. • Cấu trúc một ô của vùng quản lý: Struct oquanly { char filename[11]; int blockbatdau; long size; } • Ưu ñiểm: – Dễ cài ñặt – ðọc nhanh • Khuyết ñiểm: – Không thể lưu trữ khi bị phân mảnh – Phải biết kích thước tối ña của tập tin 27 ðịnh vị liên tiếp 28 ðịnh vị chỉ số • Cấu trúc một ô của vùng quản lý: Struct oquanly { char filename[11]; int blockIndex[max];//mảng chỉ số các block long size; } • Ưu ñiểm: – Có thể lưu trữ khi phân mảnh – ðọc nhanh • Khuyết ñiểm: – Giới hạn kích thước tập tin 29 ðịnh vị bằng danh sách liên kết • Các khối của một tập tin sẽ trỏ ñến khối kế tiếp. Khối cuối cùng trỏ ñến NULL  chỉ cần lưu khối ñầu tiên. • Ưu ñiểm: – Không bị phân mảnh • Khuyết ñiểm – Truy xuất tuần tự 30 ðịnh vị bằng danh sách liên kết 31 ðịnh vị bằng DSLK sử dụng chỉ số • Thay vì dùng con trỏ, sử dụng chỉ số ñể liên kết các khối. • Ưu ñiểm: – Có thể truy xuất ngẫu nhiên • Khuyết ñiểm: – Giới hạn kích thước bảng chứa các chỉ số liên kết 32 33 Câu Hỏi • Master Boot Record là gì? Một ổ cứng có thể chia tối ña bao nhiêu partion? Một Partion có phải luôn tương ứng với một ổ ñĩa Logic (ví dụ C D) hay không? • Theo phương pháp ñịnh vị bằng chỉ số, nếu một ô quản lý có kích thước 59 bytes thì giới hạn kích thước một tập tin là bao nhiêu trong trường hợp 1 block = 1KB. • Bạn ñang ở thư mục “C:\Documents and Settings\All Users” hãy viết ñường dẫn tương ñối ñến “C:\Windows”? 34 ðịnh vị bằng I-node • I-node gồm 2 phần: phần lưu thuộc tính và phần ñịa chỉ. • Phần ñịa chỉ có thể chia làm 2 phần – Phần ñầu: 10 phần tử chứa ñịa chỉ trực tiếp của 10 khối ñầu tiên – Phần tử thứ 11 chứa ñịa chỉ của một khối mà khối ñó chứa 210 phần tử, mỗi phần tử chứa ñịa chỉ của một khối thật sự của tập tin – Phần tử thứ 12 chứa ñịa chỉ của một khối mà mỗi phần tử trong khối như là phần tử thứ 11. – Phần tử thứ 13 chứa ñịa chỉ của một khối mà mỗi phần tử trong khối như là phần tử thứ 12. 35 36 0 1 10 11 12 37 Mô hình tổ chức Volume của UNIX • Theo dạng inode DataDanh sách inode Khối khởi ñộng Boot Sector Khối khởi ñộng chứa chương trình khởi ñộng. Danh sách các inode ñược phân thành các ô. Mỗi ô gọi là một inode (64 bytes) Mỗi inode quản lý cho một tập tin hoặc một thư mục con. 38 Mô hình tổ chức Volume của UNIX 13 1211109 8765 4321(3bytes) 25 bytes thông tin về tập tin và thư mục con (tên, thuộc tính, quyền sở hữu....) 39 bytes phân thành 13 ô. Mỗi ô chứ chỉ số của 1 block. 10 ô ñầu tiên chứa chỉ số block dữ liệu của tập tin. Ô 11 chứa chỉ số block mà block ñó ñược phân thành nhiều ô (3 bytes) chứa chỉ số block dữ liệu. Ô 12 chứa chỉ số block mà block này ñược chia thành các ô. Mỗi ô chứa chỉ số của 1 block có vai trò như của ô 11. Ô 12 chứa chỉ số block mà block này ñược chia thành các ô. Mỗi ô chứa chỉ số của 1 block có vai trò như của ô 12. 39 Quản lý ñĩa • Tập tin ñược lưu trên ñĩa  lưu như thế nào? – Lưu trên n byte liên tiếp  tập tin lớn thì quản lý khó – Lưu trên các khối  thường dùng • Kích thước khối hầu như ñược ñặt là 512byte (1 sector chuẩn) – Có thể là 1K, 2K 40 Lưu danh sách khối trống • Công dụng: – Nhanh chóng xác ñịnh khối ñể cấp phát khi có nhu cầu lưu tập tin hoặc tạo mới tập tin. • Các phương pháp: – Bảng bit: • N khối  n bit. • Bit = 0  khối còn trống • Bit = 1  khối ñã sử dụng • Kích thước bảng bit: disk size / (8 * block size) • Ví dụ: ñĩa 16Gb, block 512 byte  bảng bit chiếm 4MB 41 • Các phương pháp lưu khối trống – Danh sách các vùng trống • Mỗi phần tử bao gồm vị trí bắt ñầu và kích thước của vùng trống – Danh sách khối trống • Mỗi khối ñược gán một con số • Danh sách các khối trống ñược lưu trong một vùng dành riêng 42 Giới thiệu về hệ thống quản lý quyền sở hữu file của UNIX • Tiến trình và file ñều ñược sở hữu bởi một người dùng nào ñó. • Một tập tin sẽ có user owner và group owner – Chủ sở hữu có quyền kiểm soát chính và có thể bị tước ñọat bởi root (user cao nhất). – Mỗi file có một chủ sở hữu chính và thuộc vào một hay nhiều nhóm chủ sở hữu. – Chủ sở hữu có thể xác ñịnh quyền truy cập cho mọi thành viên còn lại (trừ root) bằng chmod. – Người sở hữu không nhất thiết phải thuộc về một nhóm sở hữu tập tin. 43 Hệ thống FAT 12, 16, 32 • Mô hình này ñược áp dụng cho hệ ñiều hành DOS và Windows. • FAT1 và FAT2 là hai bảng giống nhau. FAT2 là bảng dự phòng của FAT1. • FAT (File Allocation Table) ñược phân thành các ô, mỗi ô quản lý trong 1 block. – Ô thứ i quản lý Block thứ i-2 – Kích thước mỗi ô có thể là 12, 16 hay 32 Bit. BS FAT1 FAT2 DIRECTORY Data Vùng quản lý Vùng dữ liệu 44 Hệ thống FAT 12, 16, 32 • FAT (File Allocation Table) ñược phân thành các ô, mỗi ô quản lý trong 1 block. – Ô thứ I quản lý Block thứ i-2 – Kích thước mỗi ô có thể là 12, 16 hay 32 Bit. – Giá trị của các ô có thể là: • 0 là free • FF7 là bad • FF8 – FFF là cuối file • Khác là ô tiếp theo BS FAT1 FAT2 DIRECTORY Block 0 1 2 3 Vùng quản lý Vùng dữ liệu 45 Hệ thống FAT 12, 16, 32 • Root Directory ñược phân thành các ô, mỗi ô quản lý cho 1 tập tin hay thư mục. – Mỗi ô của Root Directory có kich thước 32 bytes – Cấu trúc 32 bytes này như sau: BS FAT1 FAT2 DIRECTORY Block 0 1 2 3 Vùng quản lý Vùng dữ liệu 46 Hệ thống FAT 12, 16, 32 BS FAT1 FAT2 DIRECTORY Block 0 1 2 3 Vùng quản lý Vùng dữ liệu Kích thước file428 chỉ số ô ñàu tiên trên bảng FAT 226 Giờ tạo224 Ngày tạo222 Chưa dùng ñến1012 Thư mục con (16) hay tập tin (>=32) 111 Extension38 Filename80 Ý nghĩaðộ lớnOffset Cấu trúc một ô của Root Directory 47 Thông tin về mô hình FAT trên ñĩa mềm 1,4 MB • Có 2880 sector • Vùng quản lý gồm 32 sector: – FAT1: 9 sector – FAT2: 9 sector – Root Directory: 14 sector. Chia thành (14*512)/32=224 ô.  có tối ña 224 tập tin trên thư mục gốc. • Vùng dữ liệu 2847 sector. • Thư mục con cũng chiếm một số block trên volume. Nội dung của các block này sẽ có cấu trúc như Root Directory. Nghĩa là cũng phân thành các ô, mỗi ô quản lý cho 1 tập tin. 48 Ví dụ • Trên thư mục gốc có tập tin emoi.c (5,2,7): dự liệu của tập tin emoi trên các block 5, 2, 7 hay nói cách khác chỉ số cá ô quản lý là ô (7,4,9), tập tin m.txt (9,4,3) và thư mục L (6). Hãy vẽ bảng FAT, Root Dir? • Nhắc lại: ô thứ I của FAT quản lý block thứ i-2. • Root Dir ñược chia thành các ô (32 bytes), ta tập trung vào thể hiện 4 thông tin tên file, phần mở rộng, giá trị byte 11 biểu diễn tập tin hay thư mục và giá trị bytes26-27 biểu chỉ số ô ñầu tiên trong bảng FAT. 49 Ví dụ 60 (free) FFFFFF 45 FFF9 0 (free)0 (free) 816L 1132txt m 732c emoi 32 là thư mục; 16 là tập tin 7, 11, 8 là chỉ số ô ñầu tiên trong bảng FAT của tập tin emoi.c, m.txt và thư mục L. Ô thứ 0 50 Ví dụ • Giả sử thư mục L (6) trong ví dụ chứa tập tin A(1) và B.doc(8) thì nội dung của block 6 như sau: 1032doc B 332 A 016.. 816. Chỉ số ô FAT ñầu tiêncủa thư mục hiện hành Chỉ số ô FAT ñầu tiên của thư mục cha nếu cha là thư mục gốc thì bằng 0 Block 51 Ví dụ • Giả sử thư mục L (6) trong ví dụ chứa tập tin A(1) và B.doc(8) thì nội dung của block 6 và bảng FAT như sau: 1032doc B 332 A 016.. 816. 6FFF FFFFFF 45 FFF9 FFF0 (free) 52 Bài tập FAT và RD • Dung lượng ñĩa sẽ quyết ñịnh kích thước 1 ô trên bảng FAT. • FAT12  212 ô = 4096 ô  tối ña là 4094 block. (vì mỗi ô quản lý 1 block) Tính toán khoảng gần ñúng. • Ví dụ: cho ñĩa có dung lượng 20MB. Mỗi block là 2 sector. Hỏi ñĩa sử dụng bảng FAT nào là hợp lý? – Số ô = số block + 2 = (20*10242)/(2*512) = 5*212+2 Nên dùng FAT 16. • Nếu dùng FAT 32 thì sao? – Mỗi block có kích thước nhỏ ñi  1 block có thể chỉ là 1 sector. 53 Bài tập FAT và RD • Cho một volume có 20 block như sau • Thư mục gốc \: – E (0) • M.TXT (1,19,18) • C (2) – U.TXT (4,5) – V (6) » N.TXT (7,8) » I.TXT (9,10) – M.TXT (3,17,16) • Hãy vẽ FAT, RD và các block liên quan (block nội dung của thư mục có cấu trúc tượng tự RD thêm vào . và ..) . • Quy ước có phần mở rộng là tập tin, có chứa con thì sẽ phải là thư mục. Cho một ñĩa có dung lượng 40GB. Mỗi block gồm 16 sector. Hỏi ta sử dụng bảng FAT nào là thích hợp nhất? 54 Câu Hỏi Ôn tập 1. So sánh thời gian các lệnh copy, move, delete trong tất cả các trường hợp có thể có. 2. Tại sao trong UNIX không có system call detete() ñể xoá file mà chỉ có system call unlink() ñể xoá một link ñến file? 3. Trình bày các thao tác của DOS/Win khi tiến hành khi delete một file? 1Hệ thống quản lý nhập/xuất 2 Tổng quan • Giới thiệu về thiết bị nhập xuất • Các kỹ thuật quản lý thao tác nhập xuất • Các vấn ñề về thiết kế hệ thống quản lý nhập xuất trong HðH • Kỹ thuật vùng ñệm nhập xuất • Quản lý hệ thống nhập xuất ñĩa 3Phân loại các thiết bị nhập/xuất • Human readable – Dùng ñể giao tiếp với người dùng – Máy in – Thiết bị ñầu cuối liên quan ñến hiển thị • Màn hình hiển thị • Bàn phím • Chuột 4 Phân loại các thiết bị nhập/xuất (2) • Machine readable – Dùng ñể giao tiếp với thiết bị ñiện tử – ðĩa 5Phân loại các thiết bị nhập/xuất (2) • Giao tiếp – Dùng ñể giao tiếp với các thiết bị ở xa (remote device) – Modem 6 Sự khác nhau giữa các thiết bị I/O • Tốc ñộ • Ứng dụng • Mức ñộ phức tạp ñể kiểm soát • ðơn vị truyền • Biểu diễn dữ liệu • Phát sinh lỗi 8Sự khác nhau giữa các thiết bị I/O (2) • Ứng dụng – ðĩa dùng ñể lưu trữ ñòi hỏi phải có hệ thống quản lý tập tin ñi kèm – ðĩa dùng ñể làm bộ nhớ ảo ñòi hỏi phải có sự hỗ trợ phần cứng và phần mềm. – Các thiết bị ñầu cuối ñược sử dụng bởi quản trị sẽ có ñộ ưu tiên cao hơn. 9Sự khác nhau giữa các thiết bị I/O (3) • ðộ phức tạp ñể kiểm soát: – Máy in so với ñĩa • ðơn vị truyền – Có thể ñược truyền theo byte hoặc khối (có thể là bit) • Biểu diễn dữ liệu – Cơ chế mã hóa • Phát sinh lỗi – Thiết bị khác nhau xử lý lỗi phát sinh khác nhau 10 Kỹ thuật xử lý I/O • Programmed I/O – Tiến trình phải busy-waiting cho thao tác nhập xuất hoàn thành • Interrupt-driven I/O – Phát sinh lệnh I/O – Bộ xử lý tiếp tục thực thi các chỉ thị khác – Module I/O gởi một ngắt ñến bộ xử lý khi hoàn thành thao tác I/O 11 Kỹ thuật quản lý I/O (2) • Direct Memory Access (DMA) – Module DMA ñiều khiển việc chuyển ñổi dữ liệu giữa bộ nhớ chính và thiết bị I/O – Bộ xử lý chỉ bị ngắt khi toàn bộ khối ñã ñược chuyển 12 Lịch sử phát triển của quản lý I/O • Bộ xử lý trực tiếp ñiều khiển thiết bị ngoại vi • Bộ ñiều khiển (Controller) hay module I/O module ñược thêm vào – Bộ xử lý dùng programmed I/O không có hỗ trợ ngắt – Bộ xử lý không cần phải quản lý chi tiết các thiết bị ngoại vi 13 Lịch sử phát triển của quản lý I/O • Bộ ñiều khiển hoặc module I/O module có hỗ trợ ngắt – Bộ xử lý không cần phải bỏ thời gian chờ thao tác I/O thi hành • Direct Memory Access – Khối dữ liệu ñược chuyển vào bộ nhớ mà không cần xử lý của bộ xử lý – Bộ xử lý chỉ liên quan vào lúc bắt ñầu và lúc kết thúc chuyển khối. 14 Lịch sử phát triển của quản lý I/O • Module I/O là một bộ xử lý riêng biệt – Có tập lệnh chuyên biệt • Bộ xử lý I/O – Module I/O có bộ nhớ riêng 15 Các vấn ñề thiết kế liên quan ñến HðH • Tính hiệu quả – Hầu hết các thiết bị I/O ñều rất chậm so với bộ nhớ chính • Sử dụng cơ chế ña chương cho phép một vài tiến trình chờ I/O trong khi tiến trình khác thi hành – Cơ chế swapping • Bản chất cũng là thao tác nhập/xuất 16 Các vấn ñề thiết kế liên quan ñến HðH • Tính tổng quát – Mong muốn xử lý tất cả các thiết bị I/O giống nhau – Che giấu hầu hết chi tiết của thiết bị nhận xuất ñể tiến trình (mức cao) xem các thiết bị ở một vài chức năng thông dụng như read, write, open, close, lock, unlock 17 Mô hình lôgic các chức năng nhập xuất • Giao tiếp ñơn giản (thiết bị ngoại vi cục bộ) – Logical I/O – Device I/O – Scheduling and Control • Giao tiếp thông quan cổng kết nối – Communication architecture – Device I/O – Scheduling and Control 18 Mô hình lôgic các chức năng nhập xuất • Hệ thống tập tin – Directory management – File system – Physical organization – Device I/O – Scheduling and Control 20 Kỹ thuật vùng ñệm nhật/xuất • Lý do – Các tiến trình phải chờ hoàn thành I/O trước khi xử lý tiếp – Thao tác I/O vẫn phải tốn bộ nhớ 21 Kỹ thuật vùng ñệm nhật/xuất (2) • Các thiết bị I/O có hai dạng hỗ trợ nhập/xuất cơ bản: – Hướng khối (block – oriented) – Hướng dòng (stream – oriented) • Block-oriented – Thông tin ñược lưu trong những khối có kích thước cho trước – ðơn vị chuyển là một khối / một lần – Dùng cho ñĩa • Stream-oriented – Truyền thông tin như là một dòng các byte – Dùng cho các thiết bị ñầu cuối, máy in, chuột, cổng giao tiếp, 22 Single Buffer • HðH dành riêng một vùng ñệm trong bộ nhớ chính cho thao tác I/O • Block-oriented – Dữ liệu vào ñược chuyển vào vùng ñệm theo ñơn vị khối – Khối ñó sẽ chuyển ñến cho tiến trình người dùng khi cần – Khối khác ñược chuyển vào vùng ñệm, trong khi tiến trình ñang xử lý khối trước ñó. • Stream-oriented – Như khối nhưng với ñơn vị là dòng. Một dòng ñược kết thúc bởi dấu CF. 23 I/O Buffering 24 Double Buffer • Dùng hai vùng ñệm thay vì một • Một tiến trình có thể chuyển dữ liệu vào và ra một vùng ñệm trong khi hệ ñiều hành truyền thông tin hoặc thao tác trên vùng ñệm còn lại 25 Circular Buffer • Nhiều hơn hai vùng ñệm • Trong trường hợp thao tác nhập xuất gắn liền với tiến trình. 26 I/O Buffering 27 Nhắc lại cấu trúc ñĩa • Các thành phần của ñĩa – platters – surfaces – tracks – sectors – cylinders – arm – heads platter surface track sector cylinder arm head 28 Các tham số liên quan ñến hiệu năng truy xuất ñĩa • ðể ñọc hay ghi, ñầu ñĩa phải di chuyển ñến track và sector tương ứng • Seek time – Thời gian dùng ñể ñịnh vị ñầu ñĩa ñến track mong muốn • Rotational delay hoặc rotational latency – Thời gian dùng ñể di chuyển ñầu ñĩa ñến sector tương ứng (vị trí ñầu tiên của sector) • Transfer time – Thời gian chuyển dữ liệu (từ hoặc vào bộ nhớ chính) 29 Thời gian thi hành tác vụ I/O 30 Tham số hiệu năng ñĩa • Access time = seek time + rotational delay – Thời gian ñể ñặt ñầu ñĩa và ñúng vị trí ñể ñọc và ghi • Dữ liệu sẽ ñược chuyển khi ñầu ñĩa nằm ñúng vị trí sector. 31 Chính sách lập lịch trên ñĩa • Mấu chốt là Seek time. – Vì sao? • Với một ñĩa có thể một số các yêu cầu I/O • Cần có cơ chế xử lý các yêu cầu này thích hợp  tăng hiệu năng xử lý I/O 32 Chính sách lập lịch trên ñĩa (2) • First-in, first-out (FIFO) – Xử lý yêu cầu một cách tuần tự – Công bằng cho tất cả tiến trình – Nếu nhiều tiến trình thì xác suất xem như là ngẫu nhiên 33 Chính sách lập lịch trên ñĩa (3) • Có ưu tiên – Mục tiêu không phải là tối ưu ñĩa mà ñể phục vụ cho các mục tiêu khác – Các công việc có thời gian thi hành ngắn có thể có ñộ ưu tiên cao hơn – Khả năng tương tác cao 34 Chính sách lập lịch trên ñĩa (4) • Last-in, first-out – Tốt cho các hệ thống xử lý giao dịch (transaction processing system) • Thiết bị ñược giao cho người dùng gần ñây nhất  ñầu ñọc di chuyển ít nhất – Có thể xảy ra tình trạng ñói (starvation) 35 Chính sách lập lịch trên ñĩa (5) • First Come, First Service – Phương pháp này dễ lập trình nhưng không cung cấp dịch vụ tốt. – Ví dụ: cần phải ñọc các khối theo thứ tự sau 98 183 37 122 14 75 và ñầu ñọc ñang ở vị trí 59. – ðầu ñọc sẽ lần lượt ñi qua các khối 59 98 183 37 122 12 75. 36 Chính sách lập lịch trên ñĩa (6) • Shortest Service Time First (SSTF) – Chọn yêu cầu I/O mà ñòi hỏi ít di chuyển nhất ñầu ñĩa từ vị trí hiện tại – Luôn luôn cho ra seek time nhỏ nhất. – Ví dụ: cần ñọc các khối 98 183 37 122 14 124 65 và 67. Giả sử ñầu ñọc ñang ở vị trí 53. – ðầu ñọc sẽ lần lượt qua các khối 53 65 67 37 4 98 122 124 183 37 Chính sách lập lịch trên ñĩa (7) • SCAN – ðầu ñọc di chuyển theo một hướng nhất ñịnh. Ví dụ cần ñọc các khối 98 183 37 122 14 124 65 67. Giả sử ñầu ñọc ở vị trí 53. – ðầu ñọc sẽ lần lượt qua các khối 53 37 14 0 65 67 98 122 124 183 (theo SCAN ñịnh hướng về 0) 38 Chính sách lập lịch trên ñĩa (7) • C-SCAN – Như SCAN, giới hạn chỉ di chuyển theo 1 chiều – Quay về vị trí bắt ñầu ngay khi ñụng track ở xa nhất, không cần phải tiếp tục. – Ví dụ cần ñọc các khối 98 183 37 122 14 124 65 67. Giả sử ñầu ñọc ở vị trí 53. – ðầu ñọc sẽ lần lượt qua các khối 53 65 67 98 122 124 183 199 0 14 37 39 Disk Scheduling Algorithms 40 Câu hỏi ôn tập – Ví dụ: cần ñọc các khối 98 183 124 65 12 và 67. Giả sử ñầu ñọc ñang ở vị trí 53. – ðầu ñọc sẽ lần lượt qua các khối nào và vẽ sơ ñồ theo các thuật toán ñọc ñĩa FCFS, SSTF, SCAN và C-SCAN. – Từ ñó kết luận xem cách ñọc nào tối ưu nhất. 41 ðịa chỉ tương ñối = (head, cylinder, sector) Head : 0  Số mặt trên ñĩa – 1 Cylinder: 0  Số cylinder trên ñĩa – 1 Sector : 1  Số sector trên track ðịa chỉ tuyệt ñối = head * Số sector/track + track * số sector/cylinder + sector - 1