Bài giảng Nguyên lý hệ điều hành - Chương 3: Quản lý lưu trữ

2008-05-01 Nguyên lý Hệ điều hành 2 Nội dung chương 3 1. Quản lý bộ nhớ 2. Bộ nhớ ảo 3. Giao diện hệ thống file 4. Cài đặt hệ thống file 2008-05-01 Nguyên lý Hệ điều hành 3 1. Quản lý bộ nhớ 1. Cơ sở 2. Swapping 3. Phân phối bộ nhớ liên tục 4. Phân trang (paging) 5. Phân đoạn (segmentation) 6. Phân đoạn kết hợp với phân trang (Segmentation với Paging) 2008-05-01 Nguyên lý Hệ điều hành 4 1.1. Cơ sở „ Chương trình muốn thực thi cần phải được tải vào bộ nhớ và đặt trong một tiến trình „ Hàng đợi vào (Input Queue) ‰ Tập các tiến trình trên đĩa, đang đợi tải vào bộ nhớ để thực hiện „ Các chương trình người dùng muốn được thực thi cần phải qua một số bước trong đó có bước gán địa chỉ cho các câu lệnh/dữ liệu. 2008-05-01 Nguyên lý Hệ điều hành 5 Gán bộ nhớ cho các câu lệnh và dữ liệu „ Việc gán địa chỉ cho các câu lệnh và dữ liệu được thực thi tại các thời điểm ‰ Biên dịch – nếu vị trí trong bộ nhớ đã được biết trước – sinh ra mã tuyệt đối (absolute code); cần phải được biên dịch lại nếu vị trí bắt đầu bị thay đổi ‰ Lúc tải (loading time) – phải sinh ra mã có thể định vị lại (relocatable code) – nếu vị trí trong bộ nhớ không được biết trước „ Mã có thể định vị lại “14 bytes kể từ đầu module” ‰ Lúc thực thi – Gán địa chỉ được trì hoãn cho đến khi thực thi nếu tiến trình có thể thay đổi, từ đoạn bộ nhớ này đến đoạn bộ nhớ khác trong khi thực thi. „ Yêu cầu phần cứng hỗ trợ cho các ánh xạ địa chỉ (thanh ghi cơ sở, thanh ghi giới hạn) 2008-05-01 Nguyên lý Hệ điều hành 6 Các bước xử lý của tiến trình người dùng 2008-05-01 Nguyên lý Hệ điều hành 7 Không gian địa chỉ vật lý và không gian địa chỉ logic „ Khái niệm không gian địa chỉ logic gắn với không gian địa chỉ vật lý là trung tâm của các kĩ thuật quản lý bộ nhớ ‰ Các địa chỉ logic – được sinh ra bởi CPU; còn được gọi là địa chỉ ảo ‰ Địa chỉ vật lý – địa chỉ thật trong bộ nhớ, thấy được bởi đơn vị quản lý bộ nhớ „ Như nhau trong lược đồ gán địa chỉ lúc biên dịch, tải „ Khác nhau trong lược đồ gán địa chỉ lúc thực thi 2008-05-01 Nguyên lý Hệ điều hành 8 Đơn vị quản lý bộ nhớ (MMU) „ Thiết bị phần cứng thực hiện việc ánh xạ địa chỉ ảo đến địa chỉ vật lý „ Ví dụ về 1 lược đồ MMU đơn giản ‰ Giá trị thanh ghi relocation được cộng vào cho mỗi địa chỉ được sinh ra bởi tiến trình người dùng tại thời điểm nó tải vào bộ nhớ. „ Chương trình người dùng làm việc với các địa chỉ logic; nó không bao giờ thấy địa chỉ vật lý 2008-05-01 Nguyên lý Hệ điều hành 9 Gán địa chỉ động với thanh ghi relocation 2008-05-01 Nguyên lý Hệ điều hành 10 Tải động vào bộ nhớ „ Các phương thức không được tải vào bộ nhớ khi nó được gọi „ Tận dụng không gian bộ nhớ tốt hơn ‰ Phương thức không được sử dụng sẽ không bao giờ được tải „ Hữu ích khi cần lượng mã lớn để xử lý các trường hợp không thường xuyên „ Không cần phải có sự hỗ trợ đặc biệt của hệ điều hành trong thiết kế chương trình 2008-05-01 Nguyên lý Hệ điều hành 11 Liên kết động „ Việc liên kết sẽ bị trì hoãn đến thời gian thực thi „ Các đoạn mã nhỏ, gọi là stub, được sử dụng để xác định thủ tục thư viện trong vùng bộ nhớ thích hợp. „ Stub được thay thế bởi địa chỉ vật lý của routine và thực thi routine „ Hệ điều hành cần phải kiểm tra xem liệu phương thức có nằm trong địa chỉ bộ nhớ của tiến trình „ Liên kết động rất hữu hiệu cho các thư viện 2008-05-01 Nguyên lý Hệ điều hành 12 Overlays „ Chỉ giữ trong bộ nhớ những câu lệnh và dữ liệu cần trong bất cứ thời điểm nào „ Cần khi tiến trình lớn hơn kích cỡ bộ nhớ được gán cho nó „ Được thực thi bởi người dùng, không cần sự hỗ trợ đặc biệt từ hệ điều hành, thiết kế lập trình của cấu trúc overlay tương đối phức tạp 2008-05-01 Nguyên lý Hệ điều hành 13 Overlays 2008-05-01 Nguyên lý Hệ điều hành 14 1.2. Swapping „ Một tiến trình có thể bị swapped tạm ra bộ lưu trữ nền , sau đó được mang trở lại bộ nhớ để thực thi tiếp „ Bộ lưu trữ nền – đĩa tốc độ nhanh, đủ lớn để lưu trữ phiên bản của tất cả ảnh bộ nhớ cho tất cả người dùng; phải cung cấp khả năng truy cập trực tiệp đến các ảnh bộ nhớ này. „ Roll out, roll in – biến thể swapping được sử dụng trong thuật toán lấp lịp có ưu tiến; tiến trình có độ ưu tiên thấp nhất bị swap ra cho phép tiến trình có độ ưu tiên cao nhất được tải vào và thực thi. „ Một trong những giai đoạn quan trọng trong thời gian swap là thời gian chuyển đổi ngữ cảnh ‰ Tổng thời gian chuyển giao tỉ lệ với tổng dung lượng bộ nhớ bị swap. „ Ta có thể thấy nhiều phiên bản biến thể của trên rất nhiều hệ thống, i.e., UNIX, Linux, and Windows. 2008-05-01 Nguyên lý Hệ điều hành 15 Lược đồ Swapping 2008-05-01 Nguyên lý Hệ điều hành 16 1.3. Phân phối bộ nhớ liên tục „ Bộ nhớ chính thường được chia thành hai phần ‰ Phần lưu trú hệ điều hành, thường được tổ chức trong vùng bộ nhớ thấp (địa chỉ thấp) với vector ngắt. ‰ Các tiến trình người dùng, thường được tổ chức trong vùng bộ nhớ cao. „ Bảo vệ ‰ Lược đồ thanh ghi relocation cho việc bảo vệ các tiến trình người dùng. ‰ Thay ghi relocation chứa giá trị của địa chỉa vật lý nhỏ nhất; thanh ghi giới hạn chứa các giá trị từ miền địa chỉ logic – các địa chỉ logic phải có giá trị nhỏ hơn giá trị của thanh ghi giới hạn. 2008-05-01 Nguyên lý Hệ điều hành 17 Hỗ trợ phần cứng cho các thanh ghi relocation và thanh ghi limit 2008-05-01 Nguyên lý Hệ điều hành 18 Phân phối liên tục (Cont.) „ Phân phối đa phân đoạn ‰ Lỗ hổng– khối bộ nhớ rỗi; các lỗ hổng với những kích cỡ khác nhau nằm rải rác trong bộ nhớ. ‰ Khi một tiến trình cần tải vào bộ nhớ, nó được phân phối vùng bộ nhớ từ lỗ hổng đủ lớn chứa nó. ‰ Hệ điều hành quản lý thông tin về: a) các phân đoạn đã được phân phối b) Các phân đoạn rỗi (lỗ hổng) OS process 5 process 8 process 2 OS process 5 process 2 OS process 5 process 2 OS process 5 process 9 process 2 process 9 process 10 2008-05-01 Nguyên lý Hệ điều hành 19 Bài toán phân phối bộ nhớ động „ Làm thế nào để phân phối tiến trình có kích cỡ n vào một danh sách các lỗ hổng còn rỗi ‰ First-fit: tìm lỗ hổng đầu tiên đủ lớn ‰ Best-fit: tìm lỗ hổng bé nhất, đủ lớn „ Tìm kiếm trên toàn bộ danh sách các lỗ hổng (trừ phi các lỗ hổng được sắp xếp theo kích cỡ) „ Sinh ra phần thừa nhỏ nhất ‰ Worst-fit: tìm lỗ hổng lớn nhất „ Cũng phải tìm kiếm „ Sinh ra phần thừa lớn nhất „ First-fit và best-fit tốt hơn chiến lược worst-fit trên quan điểm tốc độ và sự tận dụng bộ nhớ 2008-05-01 Nguyên lý Hệ điều hành 20 Sự phân mảnh „ Phân mảnh ngoài – tổng không gian bộ nhớ có thể đáp ứng yêu cầu, nhưng không liên tục „ Phân mảnh trong – bộ nhớ được phân phối có thể lớn hơn một chút so với yêu cầu; sự khác biệt về kích cỡ này là nội trong một phân đoạn, và ko được sử dụng „ Làm giảm phân mảnh ngoài bằng kết khối ‰ Xáo các nội dung bộ nhớ để đặt tất cả vùng bộ nhớ rỗi cạnh nhau tạo thành một khối lớn ‰ Kết khối chỉ thích hợp khi việc phân đoạn lại là động và được thực hiện tại lúc thực thi 2008-05-01 Nguyên lý Hệ điều hành 21 1.4. Phân trang (paging) „ Không gian địa chỉ logic 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 cỡ cố định gọi là frames (kích cỡ là lũy thừa của 2, khoảng từ 512 bytes đến 8192 bytes). „ Chia bộ nhớ logic thành các khối cũng kích cỡ, gọi là trang (pages). „ Lưu lại tất cả các frames rỗi. „ Để thực thi một chương trình có n pages, cần tìm n frames rỗi và tải chương trình vào. „ Thiết lập một bảng page để chuyển đổi địa chỉ logic thành địa chỉ vật lý. „ Có sự phân mảnh trong. 2008-05-01 Nguyên lý Hệ điều hành 22 Lược đồ dịch địa chỉ „ Địa chỉ sinh bởi CPU được chia thành hai phần ‰ Page number (p) – được sử dụng như là một chỉ số trong bảng page, chứa địa chỉ cơ sở của mỗi page trong bộ nhớ vật lý ‰ Page offset (d) – được kết hợp với địa chỉ cơ sở để xác định địa chỉ vật lý được gửi cho đơn vị bộ nhớ. 2008-05-01 Nguyên lý Hệ điều hành 23 Kiến trúc dịch địa chỉ 2008-05-01 Nguyên lý Hệ điều hành 24 Ví dụ về phân trang 2008-05-01 Nguyên lý Hệ điều hành 25 Ví dụ phân trang 2008-05-01 Nguyên lý Hệ điều hành 26 Các frame rỗi Trước khi phân phối Sau khi phân phối 2008-05-01 Nguyên lý Hệ điều hành 27 Thực thi bảng page „ Bảng page được lưu trữ trong bộ nhớ trong. „ Thanh ghi cơ sở bảng-trang (PTBR) trỏ đến bảng trang. „ Thanh ghi độ dài bảng trang (PRLR) chỉ kích cỡ của bảng trang. „ Trong lược đồ này, mọi truy cập đến dữ liệu và câu lệnh đòi hỏi hai lần truy cập bộ nhớ. ‰ Một lần cho bảng trang và một lần cho dữ liệu/ câu lệnh. „ Hai vấn đề truy cập bộ nhớ này có thể được giải quyết bằng cách sử dụng một cache phần cứng tra cứu nhanh gọi là bộ nhớ kết hợp hay bộ đệm dịch (TLBs) 2008-05-01 Nguyên lý Hệ điều hành 28 Bộ nhớ kết hợp „ Bộ nhớ kết hợp – tìm kiếm song song Dịch địa chỉ (A’, A’’) ‰ Nếu A’ là thanh ghi kết hợp, lấy frame# ra ‰ Nếu không, lấy frame# từ bảng trang trong bộ nhớ Page # Frame # 2008-05-01 Nguyên lý Hệ điều hành 29 Phần cứng cho phân trang, TLB 2008-05-01 Nguyên lý Hệ điều hành 30 Thời gian truy cập hiệu quả „ Tra cứu kết hợp = ε thời gian đơn vị „ Giả sử thời gian chu kỳ bộ nhớ là 1 micro giây „ Tỉ lệ hit – phần trăm thời gian mà một page number được tìm thấy trong các thanh ghi kết hợp; khẩu phần liên quan đến số các thanh ghi kết hợp. „ Hit ratio = α „ Thời gian truy cập hiệu quả(EAT) EAT = (1 + ε) α + (2 + ε)(1 – α) = 2 + ε – α 2008-05-01 Nguyên lý Hệ điều hành 31 Bảo vệ bộ nhớ „ Bảo vệ bộ nhớ bằng cách kết hợp các bit bảo vệ mới mỗi frame. „ Bit valid-invalid gắn với mỗi phần tử của bảng trang: ‰ “valid” chỉ rằng trang liên kết trong một không gian địa chỉ logic, và là một trang hợp lệ. ‰ “invalid” chỉ rằng trang không ở trong một không gian địa chỉ logic. 2008-05-01 Nguyên lý Hệ điều hành 32 Bit valid và invalid trong bảng trang 2008-05-01 Nguyên lý Hệ điều hành 33 Các trang chia sẻ „ Mã chia sẻ ‰ Một phiên bản mã chỉ đọc được chia sẻ giữa nhiều tiến trình(i.e., text editors, compilers, window systems). ‰ Mã chia sẻ phải xuất hiện tại cùng một vị trí trong không gian địa chỉ logic của tất cả các tiến trình. „ Mã và dữ liệu riêng ‰ Mỗi tiến trình lưu trữ một phiên bản riêng của mã và dữ liệu. ‰ Các trang cho mã riêng và dữ liệu riêng có thể xuất hiện mọi nơi trong không gian địa chỉ logc. 2008-05-01 Nguyên lý Hệ điều hành 34 Ví dụ về các trang chia sẻ 2008-05-01 Nguyên lý Hệ điều hành 35 1.5. Cấu trúc bảng trang „ Phân trang phân cấp „ Các bảng trang băm „ Các bảng trang đánh chỉ số ngược 2008-05-01 Nguyên lý Hệ điều hành 36 Các bảng trang phân cấp „ Chia không gian địa chỉ vật lý thành nhiều bảng trang. „ Một kĩ thuật đơn giản là sử dụng bảng trang hai mức. 2008-05-01 Nguyên lý Hệ điều hành 37 Ví dụ về bảng trang hai mức „ Một địa chỉ logic (trên máy 32 bit với kích cỡ trang 4K) được chia thành: ‰ Page number gồm 20 bits ‰ Page offset gồm 12 bits „ Khi bảng trang được phân trang, page number được chia tiếp thành: ‰ Một page number 10 bits. ‰ Một page offset 10 bit. „ Như vậy, không gian địa chỉ logic sẽ như sau: ở đây pi là một chỉ số của bảng page ngoài và p2 là độ dịch chuyển trong trang của bảng trang ngoài. page number page offset pi p2 d 10 10 12 2008-05-01 Nguyên lý Hệ điều hành 38 Lược đồ bảng trang hai mức 2008-05-01 Nguyên lý Hệ điều hành 39 Lược đồ dịch địa chỉ „ Lược đồ dịch địa chỉ cho kiến trúc phân trang 32-bit hai tầng. 2008-05-01 Nguyên lý Hệ điều hành 40 Các bảng trang băm „ Thông thường các không gian địa chỉ > 32 bits. „ Chỉ số trang ảo được băm vào một bảng trang. Bảng trang này chứa một chuỗi các phần tử được băm vào cùng một vị trí. „ Các chỉ số trang ảo được tìm kiếm trong chuỗi này. Nếu tìm thấy, frame vật lý tương ứng được lấy ra. 2008-05-01 Nguyên lý Hệ điều hành 41 Bảng trang băm 2008-05-01 Nguyên lý Hệ điều hành 42 Bảng trang ngược „ Mỗi phần từ tương ứng với một trang thật trong bộ nhớ. „ Mỗi phần thử gồm địa chỉ ảo của trang được lưu trong phần bộ nhớ thật, với thông tin về tiến trình chứa trang đó. „ Giảm bộ nhớ cần thiết để lưu trữ mỗi bảng trang, nhưng tăng thời gian cần thiết để tìm kiếm bảng khi một yêu cầu truy cập trang xuất hiện. „ Sử dụng trang băm để giới hạn tìm kiếm đến một, hoặc một vài phần tử của bảng trang. 2008-05-01 Nguyên lý Hệ điều hành 43 Kiến trúc bảng trang ngược 2008-05-01 Nguyên lý Hệ điều hành 44 1.6. Phân đoạn „ Lược đồ quản lý bộ nhỡ hỗ trợ quan điểm của người dùng về bộ nhớ. „ Một chương trình là một tập các đoạn. Một đoạn là một đơn vị logic gồm có: main program, procedure, function, method, object, local variables, global variables, common block, stack, symbol table, arrays 2008-05-01 Nguyên lý Hệ điều hành 45 Quan điểm người dùng của một chương trình 2008-05-01 Nguyên lý Hệ điều hành 46 Quan điểm logic của segmentation 1 3 2 4 1 4 2 3 user space physical memory space 2008-05-01 Nguyên lý Hệ điều hành 47 Kiến trúc phân đoạn „ Địa chỉ logic gồm hai phần: , „ Bảng Segment– ánh xạ các địa chỉ vật lý hai chiều; mỗi phần tử của bảng có: ‰ Base – chứa địa chỉ vật lý bắt đầu nơi mà các segment lưu trú trong bộ nhớ. ‰ Limit – xác định kích cỡ của segment. „ Segment-table base register (STBR) trỏ đến bảng segment trong bộ nhớ. „ Segment-table length register (STLR) thế hiện số các segments được sử dụng bởi một chương trình; segment number s là hợp lệ nếu s < STLR. 2008-05-01 Nguyên lý Hệ điều hành 48 Kiến trúc segmentation (cont.) „ Xác định vị trí lại. ‰ Động ‰ Dùng bảng segment „ Chia sẻ. ‰ Các đoạn được chia sẻ. ‰ Cùng segment number „ Phân phối. ‰ first fit/best fit ‰ Phân mảnh ngoài 2008-05-01 Nguyên lý Hệ điều hành 49 Kiến trúc phân đoạn „ Bảo vệ. Một phần từ trong bảng segment liên kết với: ‰ Bit hợp lệ = 0 ⇒ segment không hợp lệ ‰ Ưu tiên read/write/execute „ Các bits bảo vệ kết hợp với các segments; chia sẻ mã ở mức segment. „ Khi các segment thay đổi kích cỡ, phân phối bộ nhớ là phân phối động. „ Một ví dụ segmentation được cho trong hình vẽ sau 2008-05-01 Nguyên lý Hệ điều hành 50 Phần cứng phân đoạn 2008-05-01 Nguyên lý Hệ điều hành 51 Ví dụ về phân đoạn 2008-05-01 Nguyên lý Hệ điều hành 52 Chia sẻ các đoạn 2008-05-01 Nguyên lý Hệ điều hành 53 Phân đoạn kết hợp với phân trang „ Hệ thống MULTICS giải quyết bài toán phân mảnh ngoài bằng cách phân trang các segments. „ Giải pháp khác với segmentation thuần túy là phần từ bảng segment không chứa địa chỉ cơ sở của segment mà địa chỉ cơ sở của bảng trang cho segment này. 2008-05-01 Nguyên lý Hệ điều hành 54 Lược đồ dịch địa chỉ MULTICS 2008-05-01 Nguyên lý Hệ điều hành 55 Phân đoạn kết hợp với phân trang – Intel 386 „ Như trong hình vẽ sau, Intel 386 sử dụng segmentation với paging cho việc quản lý bộ nhớ với lược đồ hai tầng phân trang. 2008-05-01 Nguyên lý Hệ điều hành 56 Dịch địa chỉ Intel 30386 2008-05-01 Nguyên lý Hệ điều hành 57 2. Bộ nhớ ảo 1. Cơ sở 2. Phân trang theo yêu cầu 3. Hiệu năng của phân trang theo yêu cầu 4. Thay thế trang 5. Các thuật toán thay thế trang 6. Cấp phát frames 7. Thrashing 8. Các vấn đề khác 2008-05-01 Nguyên lý Hệ điều hành 58 2.1. Cơ sở „ Câu lệnh/ dữ liệu cần trong BNTđể thực hiện „ Không cần thường xuyên lưu toàn bộ chương trình người dùng vào trong BNT „ Bộ nhớ ảo – tách biệt bộ nhớ logic mức người dùng và bộ nhớ vật lý ‰ Chỉ một phần chương trình cần trong bộ nhớ để thực thi ‰ Không gian địa chỉ logic có thể lớn hơn nhiều không gian địa chỉ vật lý ‰ Cho phép chia sẻ các không gian địa chỉ bởi một số tiến trình. ‰ Cho phép tạo nhiều tiến trình một cách hiệu quả. „ Bộ nhớ ảo có thể được thực thi thông qua: ‰ Phân trang theo yêu cầu ‰ Phân đoạn theo yêu cầu 2008-05-01 Nguyên lý Hệ điều hành 59 Bộ nhớ ảo lớn hơn bộ nhớ vật lý 2008-05-01 Nguyên lý Hệ điều hành 60 Không gian địa chỉ ảo 2008-05-01 Nguyên lý Hệ điều hành 61 Thư viện chia sẻ dùng bộ nhớ ảo 2008-05-01 Nguyên lý Hệ điều hành 62 2.2. Phân trang theo yêu cầu „ Chỉ tải một trang vào bộ nhớ khi cần thiết ‰ Cần vào/ra ít ‰ Cần bộ nhớ ít ‰ Phản ứng nhanh hơn ‰ Cho phép nhiều người dùng hơn „ Cần một trang⇒ tham chiếu đến nó ‰ Tham chiếu không hợp lệ⇒ bỏ qua ‰ Không trong bộ nhớ⇒ tải vào bộ nhớ 2008-05-01 Nguyên lý Hệ điều hành 63 Chuyển bộ nhớ được phân trang vào không gian đĩa liên tục 2008-05-01 Nguyên lý Hệ điều hành 64 Bit valid/invalid „ Liên kết mỗi phần tử của bảng trang với một bit valid/invalid (1 ⇒ in-memory, 0 ⇒ not-in-memory) „ Bit valid–invalid được khởi tạo bằng 0 với mọi phần tử của bảng trang. „ Ví dụ về một bảng trang. „ Trong quá trình dịch địa chỉ, nếu bit valid-invalid trong phần tử bảng trang là 0 ⇒ lỗi trang. 1 1 1 1 0 0 0 M Frame # valid-invalid bit page table 2008-05-01 Nguyên lý Hệ điều hành 65 Bảng trang khi một vài trang không trong bộ nhớ chính 2008-05-01 Nguyên lý Hệ điều hành 66 Lỗi trang „ Tham chiếu đến một trang không có trong bộ nhớ, trước tiên tham chiếu sinh ra một trap cho hệ điều hành⇒ lỗi trang „ Hệ điều hành kiểm tra bảng khác để xác định ‰ Tham chiếu không hợp lệ⇒ bỏ qua. ‰ Trang không có trong bộ nhớ. „ Lấy ra một frame rỗng „ Tráo đổi trang vào frame „ Thiết lập lại các bảng, bit valid = 1 „ Khởi tạo lại lệnh: ‰ Chuyển khối 2008-05-01 Nguyên lý Hệ điều hành 67 Các bước xử lý lỗi trang 2008-05-01 Nguyên lý Hệ điều hành 68 Trường hợp không còn frame rỗi „ Thay thế trang ‰ Tìm một trang nào đó hiện trong bộ nhớ, nhưng đang không được sử dụng, swap nó ra. ‰ Thuật toán thay trang ‰ Hiệu năng – cần một thuận toán trả lại với ít lỗi trang nhất có thể. „ Trang có thể được tải vào bộ nhớ một vài lần. 2008-05-01 Nguyên lý Hệ điều hành 69 2.3. Hiệu năng của phân trang theo yêu cầu „ Tỉ lệ lỗi trang 0 ≤ p ≤ 1.0 ‰ Nếu p = 0, không có lỗi trang ‰ Nếu p = 1, mọi tham chiếu đều lỗi „ Thời gian truy cập hiệu quả (EAT) EAT = (1 – p) x thời gian truy cập bộ nhớ + p (phụ trội do lỗi trang + [swap trang ra ] + swap trang vào + phụ trội do khởi động lại) 2008-05-01 Nguyên lý Hệ điều hành 70 Ví dụ về phân trang theo yêu cầu „ Thời gian truy cập bộ nhớ = 1 microsecond „ 50% trang bị thay thế cần phải cập nhật lại (do đã có sửa đổi) Æ 50% trang cần phải được swap ra „ Thời gian Swap trang = 10 msec = 10,000 microsec EAT = (1 – p) x 1 + p (15000) 1 + 15000P (in microsec) 2008-05-01 Nguyên lý Hệ điều hành 71 2.4. Thay thế trang „ Tránh tình trạng phân phối bộ nhớ quá tải ‰ Dịch vụ lỗi trang bao gồm việc thay trang. „ Sử dụng bít sửa đổi (dirty) ‰ Giảm thời gian phụ trội của việc chuyển trang – chỉ có các trang bị sửa đổi mới phải ghi lại lên đĩa. „ Thay trang làm tăng sự tách biệt giữa bộ nhớ logic và bộ nhớ vật lý 2008-05-01 Nguyên lý Hệ điều hành 72 Yêu cầu thay trang 2008-05-01 Nguyên lý Hệ điều hành 73 Kĩ thuật thay trang cơ bản 1. Tìm vị trí của trang yêu cầu trên đĩa. 2. Tìm một frame rỗi: - Nếu có một frame rỗi, tận dụng frame đó. - Nếu không có frame rỗi, áp dụng thuật toán thay trang để lựa chọn một frame nạn nhân. 3. Đọc trang yêu cầu vào frame mới rỗi. Cập nhật trang và bảng frame.. 4. Khởi động lại tiến trình. 2008-05-01 Nguyên lý Hệ điều hành 74 Thay trang 2008-05-01 Nguyên lý Hệ điều hành 75 2.5. Các thuật toán thay thế trang „ Mục đích: tỉ lệ lỗi trang thấp nhất. „ Đánh giá thuật toán ‰ Áp dụng thuật toán trên một chuỗi các tham chiếu bộ nhớ ‰ Tính toán số lỗi trang trên chuỗi đó. „ Trong tất cả các ví dụ sau, ta sử dụng chuỗi tham chiếu sau 1, 2, 3, 4, 1, 2, 5, 1, 2, 3, 4, 5. 2008-05-01 Nguyên lý Hệ điều hành 76 Đồ thị mô tả số lỗi trang theo số Frames 2008-05-01 Nguyên lý Hệ điều hành 77 Thuật toán vào trước ra trước (FIFO) „ Chuỗi tham chiếu: 1, 2, 3, 4, 1, 2, 5, 1, 2, 3, 4, 5 „ 3 frames (mỗi tiến trình chỉ có 3 trang cùng ở trong bộ nhớ tại cùng một thời điểm) „ 4 frames „ Thay thế FIFO – Belady’s Anomaly ‰ Nhiều frames ⇒ ít lỗi trang 1 2 3 1 2 3 4 1 2 5 3 4 9 page faults 1 2 3 1 2 3 5 1 2 4 5 10 page faults 44 3 2008-05-01 Nguyên lý Hệ điều hành 78 Thay trang theo thuật toán FIFO 2008-05-01 Nguyên lý Hệ điều hành 79 Thuật toán tối ưu „ Thay trang sẽ không được sử dụng trong thời gian dài „ Ví dụ 4 frames: 1, 2, 3, 4, 1, 2, 5, 1, 2, 3, 4, 5 „ Làm thế nào biết được điều này? „ Được sử dụng để đánh giá hiệu suất thuật toán sử dụng 1 2 3 4 6 page faults 4 5 2008-05-01 Nguyên lý Hệ điều hành 80 Thuật toán thay trang tối ưu 2008-05-01 Nguyên lý Hệ điều hành 81 Thuật toán LRU (least recently used) „ Chuỗi tham chiếu: 1, 2, 3, 4, 1, 2, 5, 1, 2, 3, 4, 5 „ Thực thi counter ‰ Mọi phần tử trang có một counter; mỗi lần trang được tham chiếu đếnÆ cập nhật counter bằng thời điểm tham chiếu mới. ‰ Khi một trang cần thay đổi, xem xét các counter để xác định trang nạn nhân. 1 2 3 5 4 4 3 5 2008-05-01 Nguyên lý Hệ điều hành 82 Thuật toán LRU 2008-05-01 Nguyên lý Hệ điều hành 83 Thuật toán LRU „ Cài đặt bằng ngăn xếp ‰ Lưu giữ số hiệu trang trong một ngăn xếp „ Cài đặt một danh sách liên kết kép ‰ Tham chiếu trang: „ Chuyển lên đầu ngăn xếp „ Cần thay đổi tổng cộng 6 con trỏ ‰ Không đòi hỏi tìm kiếm khi thay trang 2008-05-01 Nguyên lý Hệ điều hành 84 Sử dụng một ngăn xếp để lưu trữ hầu hết các tham chiếu mới 2008-05-01 Nguyên lý Hệ điều hành 85 Các thuật toán xấp xỉ LRU „ Bit tham chiếu ‰ Mỗi trang liên kết với một bit, bit này được khởi tạo bằng 0 ‰ Khi một trang được tham chiếu đến, bit được thiết lập bằng 1 ‰ Thay thế bit 0 (nếu có). Tuy nhiên ta không biết thứ tự thay thế. „ Cơ hội thứ hai ‰ Cần bit tham chiếu. ‰ Thay thế đồng hồ. ‰ Nếu trang chuẩn bị được thay thế (theo thứ tự đồng hồ) có bit tham chiếu = 1. „ Thiết lập bit tham chiếu bằng 0. „ Để lại trang đó trong bộ nhớ. „ Thay thế trang kế tiếp (theo thứ tự đồng hồ), theo cùng một số luật. 2008-05-01 Nguyên lý Hệ điều hành 86 Thuật toán Cơ hội thứ hai 2008-05-01 Nguyên lý Hệ điều hành 87 2.6. Cấp phát frames „ Mỗi tiến trình cần một số lượng ít nhất các trang cần dùng „ Ví dụ: IBM 370 – cần 6 trang để thực hiện lệnh SS MOVE: ‰ Lệnh 6 bytes, lưu trong 2 trang ‰ 2 trang để xử lý from ‰ 2 trang để xử lý to „ Hai lược đồ phân phối cơ bản ‰ Phân phối cố định ‰ Phân phối ưu tiên 2008-05-01 Nguyên lý Hệ điều hành 88 Cấp phát cố định „ Cấp phát đều – Ví dụ: Nếu có 100 frames và 5 tiến trình, cấp cho mỗi tiến trình 20 frames. „ Cấp phát tỉ lệ – Cấp phát theo kích cỡ của tiến trình m S spa m sS ps i ii i ii ×== = ∑= = for allocation frames of number total process of size 5964 137 127 564 137 10 127 10 64 2 1 2 ≈×= ≈×= = = = a a s s m i 2008-05-01 Nguyên lý Hệ điều hành 89 Cấp phát ưu tiên „ Lược đồ cấp phát tỉ lệ theo độ ưu tiên (thay vì theo kích cỡ) „ Nếu tiến trình Pi phát sinh một lỗi trang ‰ Chọn để thay thế một trong các frame của nó ‰ Chọn để thay thế một frame từ một tiến trình với độ ưu tiên thấp hơn 2008-05-01 Nguyên lý Hệ điều hành 90 Cấp phát cục bộ và cấp phát toàn cục „ Cấp phát toàn cục – tiến trình lựa chọn một frame thay thế từ tập tất cả các frame; một tiến trình có thể lấy một frame của tiến trình khác. „ Cấp phát cục bộ – tiến trình chỉ lựa chọn frame thay thế từ tập các frame của nó 2008-05-01 Nguyên lý Hệ điều hành 91 2.7. Thrashing „ Nếu một tiến trình không có “đủ” trang, tỉ lệ lỗi trang có thể rất cao. ‰ Tính tận dụng CPU thấp „ Hệ điều hành muốn tăng độ đa chương trình ‰ Tiến trình mới được thêm vào hệ thống „ Thrashing ≡ một tiến trình dùng nhiều thời gian cho việc thay trang 2008-05-01 Nguyên lý Hệ điều hành 92 Thrashing (tiếp) 2008-05-01 Nguyên lý Hệ điều hành 93 Phân trang theo yêu cầu và thrashing „ Mô hình cục bộ ‰ Các tiến trình di trú từ miền cục bộ này sang miền cục bộ khác ‰ Các miền cục bộ có thể bị chồng chéo. „ Vì sao lại xuất hiện thrashing? Σ kích cỡ các miền cục bộ > dung lượng bộ nhớ 2008-05-01 Nguyên lý Hệ điều hành 94 Mô hình “tập làm việc” „ Δ ≡ cửa sổ tập làm việc ‰ Một tập cố định các tham chiếu trang ‰ Ví dụ: 10,000 lệnh „ WSSi (tập làm việc của tiến trình Pi) ‰ Tổng số trang được tham chiếu trong cửa sổ làm việc mới nhất Δ (thay đổi theo thời gian) ‰ Δ quá nhỏ sẽ không chứa được toàn bộ một miền cục bộ ‰ Δ quá lớn sẽ chứa đồng thời một số miền cục bộ ‰ Δ = ∞ ⇒ chứa toàn bộ chương trình „ D = ΣWSSi ≡ tổng các frames yêu cầu „ Nếu D > m⇒ Thrashing „ Chiến lược: Nếu D > m, thực hiện phong tỏa một trong số các tiến trình 2008-05-01 Nguyên lý Hệ điều hành 95 Mô hình tập làm việc 2008-05-01 Nguyên lý Hệ điều hành 96 Lược đồ tần suất lỗi trang „ Thiết lập một tỉ lệ lỗi trang chấp nhận được ‰ Nếu tỉ lệ lỗi thực tế thấp, tiến trình giải phóng frames ‰ Nếu tỉ lệ lỗi thực tế cao, tiến trình lấy thêm frames 2008-05-01 Nguyên lý Hệ điều hành 97 2.8. Các vấn đề khác „ Thực thi “tiền phân trang” ‰ Giảm một số lượng lớn lỗi trang xuất hiện vào thời điểm bắt đầu tiến trình ‰ Phân trước một số trang mà tiến trình có thể cần tới ‰ Thực hiện “tiền phân trang” có thể làm lãng phí thiết bị vào ra hoặc bộ nhớ „ Nếu thời gian tiết kiệm được do lỗi trang lớn hơn thời gian lãng phíÆ nên dùng tiền phân trang 2008-05-01 Nguyên lý Hệ điều hành 98 Kích cỡ trang „ Xem xét các yếu tố để quyết định kích cỡ trang: ‰ Phân mảnh ‰ Kích cỡ bảng ‰ Phụ trội do vào ra ‰ Tham chiếu cục bộ 2008-05-01 Nguyên lý Hệ điều hành 99 Cấu trúc chương trình „ Cấu trúc chương trình ‰ Int[128,128] data; ‰ Mỗi hàng được lưu trong 1 trang ‰ Chương trình 1 for (j = 0; j <128; j++) for (i = 0; i < 128; i++) data[i,j] = 0; 128 x 128 = 16,384 lỗi trang ‰ Chương trình 2 for (i = 0; i < 128; i++) for (j = 0; j < 128; j++) data[i,j] = 0; 128 lỗi trang 2008-05-01 Nguyên lý Hệ điều hành 100 3. Giao diện hệ thống file 1. Khái niệm file 2. Các phương pháp truy nhập file 3. Chia sẻ file 4. Gắn hệ thống file 5. Bảo vệ 2008-05-01 Nguyên lý Hệ điều hành 101 Hệ thống file „ Hệ thống file cung cấp kho lưu trữ lâu dài cho chương trình và dữ liệu. ‰ Để đảm bảo việc lưu trữ lâu dài, các file được lưu trữ trên đĩa ‰ Để có thể sử dụng nội dung file, CPU đọc file vào bộ nhớ trong „ Hệ thồng file bao gồm ‰ Một tập các file ‰ Một cấu trúc thư mục 2008-05-01 Nguyên lý Hệ điều hành 102 3.1. Khái niệm file „ Một tập dữ liệu được lưu trữ trong thiết bị lưu trữ thứ cấp. „ Thông thường, một file lưu trữ chương trình hoặc dữ liệu ‰ Một chuỗi các bit, bytes, dòng hoặc bản ghi ‰ Ý nghĩa của các bản ghi này được định nghĩa bởi người tạo „ Hệ điều hành trừu tượng hóa chi tiết của mỗi thiết bị lưu trữ ‰ Người dùng thấy một mảng tuyến tính các bản ghi ‰ Hệ điều hành ánh xạ file logic lên thiết bị lưu trữ 2008-05-01 Nguyên lý Hệ điều hành 103 Cấu trúc file „ Không có cấu trúc – chuỗi các từ (words), bytes „ Cấu trúc bản ghi đơn giản ‰ Các dòng ‰ Kích cỡ cố định ‰ Kích cỡ thay đổi „ Các cấu trúc phức tạp ‰ Tài liệu được định dạng ‰ File có thể định vị lại được „ Có thể cài đặt cấu trúc phức tạp bằng cách thêm một số kí tự điều khiển vào file. 2008-05-01 Nguyên lý Hệ điều hành 104 Những thông tin về file mà HĐH quản lý „ File có các thuộc tính: ‰ Tên (name) ‰ Số định danh (identifier) ‰ Kiểu (type) ‰ Vị trí (location) ‰ Kích thước (size) ‰ Bảo vệ (protection) : thông tin điều khiển truy cập ‰ OwnerID ‰ Thời gian: tạo, sửa đổi lần cuối, truy cập lần cuối 2008-05-01 Nguyên lý Hệ điều hành 105 Ví dụ về khối điều khiển file trong Linux 2008-05-01 Nguyên lý Hệ điều hành 106 Các thao tác trên file „ File là một kiểu dữ liệu trừu tượng „ Thông thường, có các thao tác trên file sau ‰ create(): tìm không gian trong hệ thống cho một file và sau đó thêm nó vào thư mục ‰ write(): thêm dữ liệu vào file tại vị trí hiện tại ‰ read(): đọc dữ liệu từ file bắt đầu từ vị trí hiện tại ‰ seek(): thay đổi vị trí con trỏ đọc hoặc ghi đến một ví trí xác định trong file ‰ delete(): xóa một file khỏi hệ thống file 2008-05-01 Nguyên lý Hệ điều hành 107 Các file mở „ Các thông tin để quản lý các file đang mở: ‰ Con trỏ file: trỏ đến vị trí đọc/ghi cuối „ Thông tin đơn tiến trình ‰ Số lần mở file – Khi các tiến trình mở file thoátÆ xóa phần tử tương ứng với file trong bảng file mở „ Thông tin hệ thống ‰ Vị trí đĩa: Lưu lại thông tin truy nhập dữ liệu ‰ Các quyền truy nhập: mode truy nhập đối với mỗi tiến trình 2008-05-01 Nguyên lý Hệ điều hành 108 Khóa các file mở „ Một số HDH và hệ thống file hỗ trợ khóa các file mở „ Sắp xếp việc truy nhập file „ Bắt buộc/Tư vấn: ‰ Bắt buộc – truy vấn bị từ chối tùy thuộc khóa và yêu cầu ‰ Tư vấn – các tiến trình kiểm tra trạng thái của khóa và xác định. 2008-05-01 Nguyên lý Hệ điều hành 109 Ví dụ khóa file trong Java import java.io.*; import java.nio.channels.*; public class LockingExample { public static final boolean EXCLUSIVE = false; public static final boolean SHARED = true; public static void main(String arsg[]) throws IOException { FileLock sharedLock = null; FileLock exclusiveLock = null; try { RandomAccessFile raf = new RandomAccessFile("file.txt", "rw"); // get the channel for the file FileChannel ch = raf.getChannel(); // this locks the first half of the file - exclusive exclusiveLock = ch.lock(0, raf.length()/2, EXCLUSIVE); /** Now modify the data . . . */ // release the lock exclusiveLock.release(); 2008-05-01 Nguyên lý Hệ điều hành 110 Ví dụ khóa file trong Java // this locks the second half of the file - shared sharedLock = ch.lock(raf.length()/2+1, raf.length(), SHARED); /** Now read the data . . . */ // release the lock exclusiveLock.release(); } catch (java.io.IOException ioe) { System.err.println(ioe); }finally { if (exclusiveLock != null) exclusiveLock.release(); if (sharedLock != null) sharedLock.release(); } } } 2008-05-01 Nguyên lý Hệ điều hành 111 Các kiểu file – tên, phần mở rộng 2008-05-01 Nguyên lý Hệ điều hành 112 3.2. Các phương pháp truy cập „ Truy cập tuần tự read next write next reset no read after last write (rewrite) „ Truy cập trực tiếp read n write n position to n read next write next rewrite n n = số hiệu tương đối của khối 2008-05-01 Nguyên lý Hệ điều hành 113 File truy nhập tuần tự 2008-05-01 Nguyên lý Hệ điều hành 114 Mô phỏng truy cập tuần tự trên một file truy nhập trực tiếp 2008-05-01 Nguyên lý Hệ điều hành 115 Ví dụ về chỉ số và các file tương đối 2008-05-01 Nguyên lý Hệ điều hành 116 3.3.Cấu trúc thư mục „ Các đĩa thường được tổ chức thành các phân vùng. „ Các thư mục thu thập và tổ chức các file trên một phân vùng F 1 F 2 F 3 F 4 F n Directory Files 2008-05-01 Nguyên lý Hệ điều hành 117 Cách thức tổ chức một hệ thống file điển hình 2008-05-01 Nguyên lý Hệ điều hành 118 Các thao tác trên thư mục „ search: tìm một file hoặc tập các file khớp với điều kiện tìm kiếm „ create: tạo một file trên một thư mục „ delete: xóa một file khỏi một thư mục „ list: xem nội dung thư mục „ rename: thay đổi tên của một file „ traverse 2008-05-01 Nguyên lý Hệ điều hành 119 Tổ chức thư mục (mức logic) „ Hiệu quả ‰ Xác định vị trí các file một cách nhanh chóng „ Đặt tên – thuận tiện cho người dùng ‰ Hai người dùng có thể dùng cùng 1 tên cho hai file khác nhau ‰ File giống nhau có thể có các tên khác nhau „ Gộp nhóm – gộp các file có cùng đặc trưng lại thành các nhóm (e.g., các file chương trình java, tất cả trò chơi, ) 2008-05-01 Nguyên lý Hệ điều hành 120 Cấu trúc đơn mức „ Một thư mục đơn cho tất cả người dùng „ Vấn đề ‰ Đặt tên ‰ Gộp nhóm 2008-05-01 Nguyên lý Hệ điều hành 121 Cấu trúc hai mức „ Mỗi người dùng có một thư mục „ Đường dẫn „ Cho phép hai người dùng khác nhau đặt cùng một tên file „ Tìm kiếm hiệu quả „ Chưa có tính năng gộp nhóm 2008-05-01 Nguyên lý Hệ điều hành 122 Cấu trúc cây 2008-05-01 Nguyên lý Hệ điều hành 123 Cấu trúc cây „ Tìm kiếm hiệu quả „ Tính năng gộp nhóm „ Thư mục hiện thời (thư mục làm việc) ‰ cd /spell/mail/prog ‰ type list 2008-05-01 Nguyên lý Hệ điều hành 124 Cấu trúc đồ thị không có chu trình 2008-05-01 Nguyên lý Hệ điều hành 125 Cấu trúc đồ thị không có chu trình „ Làm sao đảm bảo không có chu trình? ‰ Chỉ cho phép tạo liên kết đến file mà không cho tạo liên kết đến các thư mục con ‰ Thu rác (garbage collection) ‰ Mỗi khi một liên kết mới được thêm, sử dụng một thuật toán xác định chu trình để kiểm tra xem có thêm được không 2008-05-01 Nguyên lý Hệ điều hành 126 3.4.Gắn hệ thống file „ Một hệ thống file cần được gắn trước khi có thể truy cập 2008-05-01 Nguyên lý Hệ điều hành 127 Điểm gắn Hệ thống file 2008-05-01 Nguyên lý Hệ điều hành 128 3.5.Chia sẻ file „ Nhu cầu chia sẻ file trong hệ thống đa người dùng „ Thực hiện chia sẻ file thông qua lược đồ bảo vệ „ Trên các hệ thống phân tán, các file có thể được chia sẻ qua mạng „ Hệ thống file mạng (NFS) là phương pháp chia sẻ file phổ biến 2008-05-01 Nguyên lý Hệ điều hành 129 Chia sẻ file – đa người dùng „ User IDs nhận diện người dùng, cho phép cấp quyền và bảo vệ file cấp người dùng. „ Group IDs xác định nhóm người dùng, cấp quyền truy nhập theo nhóm. 2008-05-01 Nguyên lý Hệ điều hành 130 Chia sẻ file – Các hệ thống file từ xa „ Thông qua mạng để truy cập hệ thống file giữa các hệ thống ‰ Truy cập thủ công thông qua các chương trình như FTP ‰ Truy nhập tự động thông qua hệ thống file chia sẻ ‰ Truy nhập bán tự động thông qua world wide web „ Mô hình client-server cho phép khách gắn các hệ thống file của servers ‰ Server có thể phục vụ nhiều clients ‰ Việc nhận dạng người dùng trên máy client thường không bảo mật hoặc phức tạp ‰ NFS là giao thức chia sẻ file client-server chuẩn của UNIX ‰ CIFS là giao thức chuẩn của Windows. ‰ Các lời gọi file chuẩn của hệ điều hành được chuyển thành các lời gọi file từ xa. „ Các hệ thống thông tin phân tán (các dịch vụ định dạng phân tán) như LDAP, DNS, NIS, Active Directory thiết lập truy cập hợp nhất đến thông tin chia sẻ từ xa. 2008-05-01 Nguyên lý Hệ điều hành 131 Chia sẻ file – Các mode thất bại „ Các hệ thống file từ xa có thêm các mode thất bại, do mạng, do server „ Khôi phục từ thất bại cần thông tin trạng thái của mỗi yêu cầu từ xa. „ Các giao thức không hướng kết nối như NFS trong mỗi yêu cầu cho phép khôi phục dễ dàng hơn nhưng ít bảo mật hơn. 2008-05-01 Nguyên lý Hệ điều hành 132 Chia sẻ file – Tính thống nhất về mặt ngữ nghĩa „ Tính nhất quán về ngữ nghĩa xác định cách thức cho phép nhiều người dùng truy cập vào file cùng lúc. ‰ Tương tự cách đồng bộ tiến trình cộng tác „ Hệ thống file Andrew (AFS) triển khai ngữ cảnh chia sẻ file từ xa ‰ Hệ thống file Unix (UFS) thiết lập: „ Việc ghi lên một file mở có thể thấy bởi những người dùng khác ngay lập tức „ Con trỏ đến file chia sẻ cho phép nhiều người dùng truy cập đến file đồng thời. ‰ AFS có các ngữ cảnh sessions „ Việc cập nhật lên file chỉ thấy được trong những sessions sau khi file đã đóng 2008-05-01 Nguyên lý Hệ điều hành 133 3.6. Bảo vệ „ Người tạo/sở hữu phải có khả năng điều khiển ‰ Xác định ai có thể làm gì trên file „ Các kiểu truy nhập ‰ Read ‰ Write ‰ Execute ‰ Append ‰ Delete ‰ List 2008-05-01 Nguyên lý Hệ điều hành 134 Nhóm và quyền truy nhập „ Các mode truy nhập: read, write, execute „ Ba lớp người dùng RWX a) owner access 7 ⇒ 1 1 1 RWX b) group access 6 ⇒ 1 1 0 RWX c) public access 1 ⇒ 0 0 1 „ Tạo một nhóm G (tên duy nhất), và thêm người dùng vào nhóm đó. „ Với một file (vd: game) hay thư mục con, định nghĩa một quyền truy nhập xác định owner group public chmod 761 game 2008-05-01 Nguyên lý Hệ điều hành 135 Quản lý quyền truy nhập trong XP 2008-05-01 Nguyên lý Hệ điều hành 136 Liệt kê thư mục trong Unix 2008-05-01 Nguyên lý Hệ điều hành 137 4. Cài đặt hệ thống file 1. Cấu trúc và cài đặt hệ thống file 2. Cài đặt thư mục 3. Các phương pháp phân phối 4. Quản lý không gian rỗi 5. Hiệu quả, hiệu suất 6. Khôi phục 2008-05-01 Nguyên lý Hệ điều hành 138 4.1. Cấu trúc và cài đặt hệ thống file „ Cấu trúc file ‰ Đơn vị lưu trữ mức logic ‰ Tập các thông tin có liên quan đến nhau „ Hệ thống file được lưu trên thiết bị lưu trữ thứ cấp (các đĩa từ) „ Hệ thống file được tổ chức thành các tầng „ Khối điều khiển file – cấu trúc lưu trữ chứa thông tin về một file 2008-05-01 Nguyên lý Hệ điều hành 139 Hệ thống file phân tầng 2008-05-01 Nguyên lý Hệ điều hành 140 Một khối điều khiển file điển hình 2008-05-01 Nguyên lý Hệ điều hành 141 Các cấu trúc hệ thống file trong bộ nhớ „ Các cấu trúc file hệ thống cần thiết và được cung cấp bởi hầu hết các hệ điều hành. „ Hình 12-3(a) mô tả quá trình mở một file. „ Hình 12-3(b) mô tả quá trình đọc một file 2008-05-01 Nguyên lý Hệ điều hành 142 Các cấu trúc hệ thống file trong bộ nhớ 2008-05-01 Nguyên lý Hệ điều hành 143 Các hệ thống file ảo „ Các hệ thống file ảo (VFS) cung cấp một cách thức hướng đối twongj để cài đặt hệ thống file „ VFS cho phép thiết lập giao diện lời gọi hệ thống (API) chung cho các loại hệ thống file khác nhau „ API là giao diện VFS thay vì giao diện của bất kì một hệ thống file cụ thể nào 2008-05-01 Nguyên lý Hệ điều hành 144 Hệ thống file ảo 2008-05-01 Nguyên lý Hệ điều hành 145 4.2. Cài đặt thư mục „ Danh sách liên kết chứa tên file và con trỏ đến các file ‰ Đơn giản ‰ Tốn kém thời gian „ Bảng băm. ‰ Giảm thời gian tìm kiếm thư mục ‰ Va chạm – tình huống xảy ra khi hai tên file được ánh xạ vào cùng một địa điểm ‰ Kích cỡ cố định 2008-05-01 Nguyên lý Hệ điều hành 146 4.3. Các phương pháp phân phối „ Cách thức phân phối các khối đĩa cho các file: ‰ Phân phối liên tục ‰ Phân phối liên kết ‰ Phân phối chỉ số 2008-05-01 Nguyên lý Hệ điều hành 147 Phân phối liên tục „ Mỗi file lưu trong một tập các khối liên tục trên đĩa „ Đơn giản – chỉ cần điểm bắt đầu (block #) và kích cỡ (số các blocks) „ Truy nhập ngẫu nhiên „ Không tận dụng không gian tối ưu „ Các file không thể thay đổi kích cỡ 2008-05-01 Nguyên lý Hệ điều hành 148 Phân phối liên tục (tt) „ Ánh xạ từ không gian logic sang không gian vật lý LA/512 Q R Khối cần truy cập = Q + địa chỉ bắt đầu Gia số trong khối = R 2008-05-01 Nguyên lý Hệ điều hành 149 Phân phối không gian đĩa liên tục 2008-05-01 Nguyên lý Hệ điều hành 150 Các hệ mở rộng dựa trên phân phối liên tục „ Nhiều hệ thống file mới (ví dụ: Veritas File System) sử dụng một lược đồ phân phối liên tục có sửa đổi „ Các hệ thống file mở rộng phân phối khối đĩa trong các extents „ Một extent là một tập các khối đĩa liên tục ‰ Extents được phân phối cho một file ‰ Một file có thể chứa một hay nhiều extent. 2008-05-01 Nguyên lý Hệ điều hành 151 Phân phối liên kết „ Một file có thể là một danh sách khối đĩa: các khối đĩa có thể nằm rải rác . Con trỏKhối = 2008-05-01 Nguyên lý Hệ điều hành 152 Phân phối liên kết (tt) „ Đơn giản – chỉ cần địa chỉ bắt đầu „ Hệ thống quản lý không gian rỗi – Không lãng phí tài nguyên „ Không truy nhập ngẫu nhiên „ Ánh xạ Khối sắp được truy nhập tại vị tri thứ Qth trong danh sách liên kết các blocks biểu diễn file. Gia số trong blocks= R + 1 Bảng phân phối file ( bảng FAT) – phân phối không gian đĩa trong MS-DOS và OS-2 LA/511 Q R 2008-05-01 Nguyên lý Hệ điều hành 153 Phân phối liên kết 2008-05-01 Nguyên lý Hệ điều hành 154 Bảng phân phối file 2008-05-01 Nguyên lý Hệ điều hành 155 Phân phối chỉ số „ Khối index: chứa toàn bộ con trỏ đến các khối đĩa . Bảng chỉ số 2008-05-01 Nguyên lý Hệ điều hành 156 Ví dụ về phân phối chỉ số 2008-05-01 Nguyên lý Hệ điều hành 157 Phân phối chỉ số (tt) „ Cần bảng chỉ „ Truy cập ngẫu nhiên „ Phân phối động mà không sinh ra phân mảnh ngoài (chỉ tốn không gian cho bảng index) „ Ánh xạ từ không gian logic sang không gian vật lý trong một file kích cỡ tối đa là 256K từ và kích cỡ khối là 512 từ chúng ta chỉ cần một khối cho bảng index LA/512 Q R Q = chỉ số trong bảng index R = chỉ số trong khối 2008-05-01 Nguyên lý Hệ điều hành 158 Phân phối đánh chỉ số – Ánh xạ (tt) „ Ánh xạ từ không gian logic sang không gian vật lý trong một file độ dài không giới hạn (kích cỡ khối là 512 từ). „ Lược đồ liên kết – Liên kết các khối trong bảng chỉ số (không giới hạn kích cỡ). LA / (512 x 511) Q1 R1Q1 = khối của bảng chỉ số R1 được sử dụng như sau: R1 / 512 Q2 R2 Q2 = gia số trong khối chứa bảng chỉ số R2 gia số trong khối file: 2008-05-01 Nguyên lý Hệ điều hành 159 Phân phối đánh chỉ số - Ánh xạ (tt) „ Hai mức chỉ số (kích cỡ file tối đa là 5123) LA / (512 x 512) Q1 R1 Q1 = Gia số trong bảng file mức ngoài R1 được sử dụng như sau: R1 / 512 Q2 R2 Q2 = gia số trong khối của bảng chỉ số mức trong R2 gia số trong khối file: 2008-05-01 Nguyên lý Hệ điều hành 160 Phân phối file chỉ số – Ánh xạ (tt) M outer-index index table file 2008-05-01 Nguyên lý Hệ điều hành 161 Lược đồ kết hợp: UNIX (4K bytes mỗi khối) 2008-05-01 Nguyên lý Hệ điều hành 162 4.4. Quản lý không gian rỗi „ Vector bit (n khối 0 1 2 n-1 bit[i] = 6 7 8 0 ⇒ block[i] free 1 ⇒ block[i] occupied Tính toán số khối (số lượng bit mỗi từ) * (số lượng từ nhận giá trị 0) + Gia số bit 1 đầu tiên 2008-05-01 Nguyên lý Hệ điều hành 163 Quản lý không gian rỗi (tt) „ Ánh xạ bit cần thêm không gian ‰ Ví dụ: kích cỡ khối = 212 bytes kích cỡ đĩa = 230 bytes (1 gigabyte) n = 230/212 = 218 bits (or 32K bytes) „ Dễ dàng truy nhập đến file liên tục „ Danh sách liên kết (danh sách liên kết rỗi) ‰ Khó có được không gian liên tục ‰ Không lãng phí không gian 2008-05-01 Nguyên lý Hệ điều hành 164 Quản lý không gian rỗi (tt) „ Cần phải bảo vệ: ‰ Con trỏ đến danh sách rỗi ‰ Ánh xạ bit „ Phải được giữ trên đĩa „ Bản sao trong đĩa và trong bộ nhớ có thể khác nhau „ Không cho phép khối[i] ở trong trạng thái mà bit[i] = 1 trong bộ nhớ và bit[i] = 0 trên đĩa ‰ Giải pháp: „ Thiết lập bit[i] = 1 trong đĩa „ Phân phối khối[i] „ Thiết lập bit[i] = 1 trong bộ nhớ 2008-05-01 Nguyên lý Hệ điều hành 165 Danh sách liên kết không gian rỗi trên đĩa 2008-05-01 Nguyên lý Hệ điều hành 166 Hiệu năng „ Hiệu quả phụ thuộc vào: ‰ Các thuật toán phân phối đĩa và thư mục ‰ Các kiểu dữ liệu được giữ trong đầu vào thư mục chứa file „ Năng suất ‰ Cache đĩa – lưu lại một phần đĩa thường xuyên được truy nhập ‰ Giải phóng sau- đọc trước – kĩ thuật tối ưu truy nhập tuần tự ‰ Tăng năng suất làm việc cho PC 2008-05-01 Nguyên lý Hệ điều hành 167 Cache trang „ Một cache trang lưu lại các trang thay vì các khối đĩa sửa dụng bởi các kĩ thuật bộ nhớ „ Ánh xạ bộ nhớ I/O sửa dụng cache trang „ Các thao tác vào ra với hệ thống file sử dụng page(disk) cache 2008-05-01 Nguyên lý Hệ điều hành 168 I/O mà không có một tổ chức cache hợp nhất 2008-05-01 Nguyên lý Hệ điều hành 169 Sửa dụng cache bộ đệm hợp nhất „ Một cache bộ đệm hợp nhất: sử dụng không gian cache page để ‰ cache cả các trang ánh xạ bộ nhớ ‰ vào/ra các hệ thống file thông thường 2008-05-01 Nguyên lý Hệ điều hành 170 I/O sử dụng cache bộ đệm hợp nhất 2008-05-01 Nguyên lý Hệ điều hành 171 Khôi phục „ Kiểm tra tính nhất quán – so sánh dữ liệu trong cấu trúc thư mục và so sánh với khối đĩa, cố gắng giải quyết tính không nhất quán „ Sử dụng các chương trình hệ thống để back up dữ liệu từ đĩa sang các thiết bị lưu trữ khác (floppy disk, magnetic tape, other magnetic disk, optical) „ Khôi phục file hay thư mục bị mất bằng cách khôi phục lại backup