Giáo trình Hệ điều hành (Phần 2) - Đại học Phan Thiết

107 trang Gia Huy 16/05/2022 2880

Download

Bạn đang xem 20 trang mẫu của tài liệu "Giáo trình Hệ điều hành (Phần 2) - Đại học Phan Thiết", để tải tài liệu gốc về máy bạn click vào nút DOWNLOAD ở trên

Tài liệu đính kèm:

giao_trinh_he_dieu_hanh_phan_2_dai_hoc_phan_thiet.pdf

Nội dung text: Giáo trình Hệ điều hành (Phần 2) - Đại học Phan Thiết

CHƢƠNG 9. BỘ NHỚ ẢO Bộ nhớ ảo là một kỹ thuật hiện đại giúp cho ngƣời dùng đƣợc giải phóng hoàn toàn khỏi mối bận tâm về giới hạn bộ nhớ. Ý tƣởng, ƣu điểm và những vấn đề liên quan đến việc tổ chức bộ nhớ ảo sẽ đƣợc trình bày trong bài học này. 9.1. Dẫn nhập Nếu đặt toàn thể không gian địa chỉ vào bộ nhớ vật lý, thì kích thƣớc của chƣơng trình bị giới hạn bởi kích thƣớc bộ nhớ vật lý. Thực tế, trong nhiều trƣờng hợp, chúng ta không cần phải nạp toàn bộ chƣơng trình vào bộ nhớ vật lý cùng một lúc, vì tại một thời điểm chỉ có một chỉ thị của tiến trình đƣợc xử lý. Ví dụ, các chƣơng trình đều có một đoạn code xử lý lỗi, nhƣng đoạn code này hầu nhƣ rất ít khi đƣợc sử dụng vì hiếm khi xảy ra lỗi, trong trƣờng hợp này, không cần thiết phải nạp đoạn code xử lý lỗi từ đầu. Từ nhận xét trên, một giải pháp đƣợc đề xuất là cho phép thực hiện một chƣơng trình chỉ đƣợc nạp từng phần vào bộ nhớ vật lý. Ý tƣởng chính của giải pháp này là tại mỗi thời điểm chỉ lƣu trữ trong bộ nhớ vật lý các chỉ thị và dữ liệu của chƣơng trình cần thiết cho việc thi hành tại thời điểm đó. Khi cần đến các chỉ thị khác, những chỉ thị mới sẽ đƣợc nạp vào bộ nhớ, tại vị trí trƣớc đó bị chiếm giữ bởi các chỉ thị nay không còn cần đến nữa. Với giải pháp này, một chƣơng trình có thể lớn hơn kích thƣớc của vùng nhớ cấp phát cho nó. Một cách để thực hiện ý tƣởng của giải pháp trên đây là sử dụng kỹ thuật overlay. Kỹ thuật overlay không đòi hỏi bất kỳ sự trợ giúp đặc biệt nào của hệ điều hành , nhƣng trái lại, lập trình viên phải biết cách lập trình theo cấu trúc overlay, và điều này đòi hỏi khá nhiều công sức. Để giải phóng lập trình viên khỏi các suy tƣ về giới hạn của bộ nhớ, mà cũng không tăng thêm khó khăn cho công việc lập trình của họ, ngƣời ta nghĩ đến các kỹ thuật tự động, cho phép xử lý một chƣơng trình có kích thƣớc lớn chỉ với một vùng nhớ có kích thƣớc nhỏ . Giải pháp đƣợc tìm thấy với khái niệm bộ nhớ ảo (virtual memory). 9.2. Định nghĩa Bộ nhớ ảo là một kỹ thuật cho phép xử lý một tiến trình không đƣợc nạp toàn bộ vào bộ nhớ vật lý. Bộ nhớ ảo mô hình hoá bộ nhớ nhƣ một bảng lƣu trữ rất lớn và đồng nhất, tách biệt hẳn khái niệm không gian địa chỉ và không gian vật lý. Ngƣời 128
sử dụng chỉ nhìnthấy và làm việc trong không gian địa chỉ ảo, việc chuyển đổi sang không gian vật lý do hệ điều hành thực hiện với sự trợ giúp của các cơ chế phần cứng cụ thể. Thảo luận: Cần kết hợp kỹ thuật swapping đển chuyển các phần của chƣơng trình vào-ra giữa bộ nhớ chính và bộ nhớ phụ khi cần thiết. Nhờ việc tách biệt bộ nhớ ảo và bộ nhớ vật lý, có thể tổ chức một bộ nhớ ảo có kích thƣớc lớn hơn bộ nhớ vật lý. Bộ nhớ ảo cho phép giảm nhẹ công việc của lập trình viên vì họ không cần bận tâm đến giới hạn của vùng nhớ vật lý, cũng nhƣ không cần tổ chức chƣơng trình theo cấu trúc overlays. Hình 2.24 Bộ nhớ ảo 9.3. Cài đặt bộ nhớ ảo Bộ nhớ ảo thƣờng đƣợc thực hiện với kỹ thuật phân trang theo yêu cầu(demand paging). Cũng có thể sử dụng kỹ thuật phân đoạn theo yêu cầu ( demand segmentation) để cài đặt bộ nhớ ảo, tuy nhiên việc cấp phát và thay thế các phân đoạn phức tạp hơn thao tác trên trang, vì kích thƣớc không bằng nhau của các đoạn. 9.4. Phân trang theo yêu cầu ( demand paging) 129
Một hệ thống phân trang theo yêu cầu là hệ thống sử dụng kỹ thuật phân trang kết hợp với kỹ thuật swapping. Một tiến trình đƣợc xem nhƣ một tập các trang, thƣờng trú trên bộ nhớ phụ ( thƣờng là đĩa). Khi cần xử lý, tiến trình sẽ đƣợc nạp vào bộ nhớ chính. Nhƣng thay vì nạp toàn bộ chƣơng trình, chỉ những trang cần thiết trong thời điểm hiện tại mới đƣợc nạp vào bộ nhớ. Nhƣ vậy một trang chỉ đƣợc nạp vào bộ nhớ chính khi có yêu cầu.Với mô hình này, cần cung cấp một cơ chế phần cứng giúp phân biệt các trang đang ở trong bộ nhớ chính và các trang trên đĩa. Có thể sử dụng lại bit valid-invalid nhƣng với ngữ nghĩa mới: valid : trang tƣơng ứng là hợp lệ và đang ở trong bộ nhớ chính . invalid : hoặc trang bất hợp lệ (không thuộc về không gian địa chỉ của tiến trình) hoặc trang hợp lệ nhƣng đang đƣợc lƣu trên bộ nhớ phụ. Một phần tử trong bảng trang mộ tả cho một trang không nằm trong bộ nhớ chính, sẽ đƣợc đánh dấu invalid và chứa địa chỉ của trang trên bộ nhớ phụ. 9.5. Cơ chế phần cứng : Cơ chế phần cứng hỗ trợ kỹ thuật phân trang theo yêu cầu là sự kết hợp của cơ chế hỗ trợ kỹ thuật phân trang và kỹ thuật swapping: Bảng trang: Cấu trúc bảng trang phải cho phép phản ánh tình trạng của một trang là đang nằm trong bộ nhớ chính hay bộ nhớ phụ. Bộ nhớ phụ: Bộ nhớ phụ lƣu trữ những trang không đƣợc nạp vào bộ nhớ chính. Bộ nhớ phụ thƣờng đƣợc sử dụng là đĩa, và vùng không gian đĩa dùng để lƣu trữ tạm các trang trong kỹ thuật swapping đƣợc gọi là không gian swapping. 130
Hình 2.24 Bảng trang với một số trang trên bộ nhớ phụLỗi trang Truy xuất đến một trang đƣợc đánh dấu bất hợp lệ sẽ làm phát sinh một lỗi trang (page fault). Khi dò tìm trong bảng trang để lấy các thông tin cần thiết cho việc chuyển đổi địa chỉ, nếu nhận thấy trang đang đƣợc yêu cầu truy xuất là bất hợp lệ, cơ chế phần cứng sẽ phát sinh một ngắt để báo cho hệ điều hành. Hệ điều hành sẽ xử lý lỗi trang nhƣ sau : Kiểm tra truy xuất đến bộ nhớ là hợp lệ hay bất hợp lệ Nếu truy xuất bất hợp lệ : kết thúc tiến trình Ngƣợc lại : đến bƣớc 3 Tìm vị trí chứa trang muốn truy xuất trên đĩa. Tìm một khung trang trống trong bộ nhớ chính : Nếu tìm thấy : đến bƣớc 5 Nếu không còn khung trang trống, chọn một khung trang « nạn nhân » và chuyển trang « nạn nhân » ra bộ nhớ phụ (lƣu nội dung của trang đang chiếm giữ khung trang này lên đĩa), cập nhật bảng trang tƣơng ứng rồi đến bƣớc 5 Chuyển trang muốn truy xuất từ bộ nhớ phụ vào bộ nhớ chính : nạp trang cần truy xuất vào khung trang trống đã chọn (hay vừa mới làm trống ) ; cập nhật nội dung bảng trang, bảng khung trang tƣơng ứng. 131
Tái kích hoạt tiến trình ngƣời sử dụng. Hình 2.26 Các giai đoạn xử lý lỗi trang 9.6. Thay thế trang Khi xảy ra một lỗi trang, cần phải mang trang vắng mặt vào bộ nhớ . Nếu không có một khung trang nào trống, hệ điều hành cần thực hiện công việc thay thế trang – chọn một trang đang nằm trong bộ nhớ mà không đƣợc sử dụng tại thời điểm hiện tại và chuyển nó ra không gian swapping trên đĩa để giải phóng một khung trang dành chỗ nạp trang cần truy xuất vào bộ nhớ. Nhƣ vậy nếu không có khung trang trống, thì mỗi khi xảy ra lỗi trang cần phải thực hiện hai thao tác chuyển trang : chuyển một trang ra bộ nhớ phụ và nạp một trang khác vào bộ nhớ chính. Có thể giảm bớt số lần chuyển trang bằng cách sử dụng thêm một bit cập nhật (dirty bit). Bit này đƣợc gắn với mỗi trang để phản ánh tình trạng trang có bị cập nhật hay không : giá trị của bit đƣợc cơ chế phần cứng đặt là 1 mỗi lần có một từ đƣợc ghi vào trang, để ghi nhận nội dung trang có bị sửa đổi. Khi cần thay thế một trang, nếu bit cập nhật có giá trị là 1 thì trang cần đƣợc lƣu lại trên đĩa, ngƣợc lại, nếu bit cập nhật là 0, nghĩa là trang không bị thay đổi, thì không cần lƣu trữ trang trở lại đĩa. 132
Hình 4.27 Cấu trúc một phần tử trong bảng trang Sự thay thế trang là cần thiết cho kỹ thuật phân trang theo yêu cầu. Nhờ cơ chế này, hệ thống có thể hoàn toàn tách rời bộ nhớ ảo và bộ nhớ vật lý, cung cấp cho lập trình viên một bộ nhớ ảo rất lớn trên một bộ nhớ vật lý có thể bé hơn rất nhiều lần. 9.7. Sự thi hành phân trang theo yêu cầu Việc áp dụng kỹ thuật phân trang theo yêu cầu có thể ảnh hƣởng mạnh đến tình hình hoạt động của hệ thống. Gỉa sử p là xác suất xảy ra một lỗi trang (0≤ p ≤ 1): p = 0 : không có lỗi trang nào p = 1 : mỗi truy xuất sẽ phát sinh một lỗi trang Thời gian thật sự cần để thực hiện một truy xuất bộ nhớ (TEA) là:TEA = (1-p)ma + p (tdp) [+ swap out ] + swap in + tái kích hoạt Trong công thức này, ma là thời gian truy xuất bộ nhớ, tdp thời gian xử lý lỗi trang. Có thể thấy rằng, để duy trì ở một mức độ chấp nhận đƣợc sự chậm trễ trong hoạt động của hệ thống do phân trang, cần phải duy trì tỷ lệ phát sinh lỗi trang thấp. Hơn nữa, để cài đặt kỹ thuật phân trang theo yêu cầu, cần phải giải quyết hai vấn đề chính yếu : xây dựng một thuật toán cấp phát khung trang, và thuật toán thay thế trang. 9.8. Các thuật toán thay thế trang Vấn đề chính khi thay thế trang là chọn lựa một trang « nạn nhân » để chuyển ra bộ nhớ phụ. Có nhiều thuật toán thay thế trang khác nhau, nhƣng tất cả cùng chung một mục tiêu : 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ó thể đánh giá hiệu qủa của một thuật toán bằng cách xử lý trên một chuỗi các địa chỉ cần truy xuất và tính toán số lƣợng lỗi trang phát sinh. Ví dụ: Giả sữ theo vết xử lý của một tiến trình và nhận thấy tiến trình thực hiện truy xuất các địa chỉ theo thứ tự sau : 133
0100, 0432, 0101, 0162, 0102, 0103, 0104, 0101, 0611, 0102, 0103,0104, 0101, 0610, 0102, 0103, 0104, 0101, 0609, 0102, 0105 Nếu có kích thƣớc của một trang là 100 bytes, có thể viết lại chuỗi truy xuất trên giản lƣợc hơn nhƣ sau : 1, 4, 1, 6, 1, 6, 1, 6, 1 Để xác định số các lỗi trang xảy ra khi sử dụng một thuật toán thay thế trang nào đó trên một chuỗi truy xuất cụ thể, còn cần phải biết số lƣợng khung trang sử dụng trong hệ thống. Để minh hoạ các thuật toán thay thế trang sẽ trình bày, chuỗi truy xuất đƣợc sử dụng là : 7, 0, 1, 2, 0, 3, 0, 4, 2, 3, 0, 3, 2, 1, 2, 0, 1, 7, 0, 1 9.8.1. Thuật toán FIFO Tiếp cận: Ghi nhận thời điểm một trang đƣợc mang vào bộ nhớ chính. Khi cần thay thế trang, trang ở trong bộ nhớ lâu nhất sẽ đƣợc chọn Ví dụ : sử dụng 3 khung trang , ban đầu cả 3 đều trốn Ghi chú : * : có lỗi trang Thảo luận: Để áp dụng thuật toán FIFO, thực tế không nhất thiết phải ghi nhận thời điểm mỗi trang đƣợc nạp vào bộ nhớ, mà chỉ cần tổ chức quản lý các trang trong bộ nhớ trong một danh sách FIFO, khi đó trang đầu danh sách sẽ đƣợc chọn để thay thế. Thuật toán they thế trang FIFO dễ hiểu, dễ cài đặt. Tuy nhiên khi thực hiện không phải lúc nào cũng có kết qủa tốt : trang đƣợc chọn để thay thế có thể là trang chức nhiều dữ liệu cần thiết, thƣờng xuyên đƣợc sử dụng nên đƣợc nạp sớm, do vậy khi bị chuyển ra bộ nhớ phụ sẽ nhanh chóng gây ra lỗi trang. 134
Số lƣợng lỗi trang xảy ra sẽ tăng lên khi số lƣợng khung trang sử dụng tăng. Hiện tƣợng này gọi là nghịch lý Belady. Ví dụ: 1, 2, 3, 4, 1, 2, 5, 1, 2, 3, 4, 5 Sử dụng 3 khung trang , sẽ có 9 lỗi trang phát sinh Sử dụng 4 khung trang , sẽ có 10 lỗi trang phát sinh 9.8.2. Thuật toán tối ưu Tiếp cận: Thay thế trang sẽ lâu đƣợc sử dụng nhất trong tƣơng lai. Ví dụ : sử dụng 3 khung trang, khởi đầu đều trống: 7 0 1 2 0 3 0 4 2 3 0 3 2 1 2 0 1 7 0 1 7 7 7 2 2 2 2 2 2 2 2 2 2 2 2 2 2 7 7 7 0 0 0 0 0 0 4 4 4 0 0 0 0 0 0 0 0 0 0 1 1 1 3 3 3 3 3 3 3 3 1 1 1 1 1 1 1 * * * * * * * * * Thảo luận: 135
Thuật toán này bảo đảm số lƣợng lỗi trang phát sinh là thấp nhất , nó cũng không gánh chịu nghịch lý Belady, tuy nhiên, đây là một thuật toán không khả thi trong thực tế, vì không thể biết trƣớc chuỗi truy xuất của tiến trình! 9.8.3. Thuật toán « Lâu nhất chưa sử dụng » ( Least-recently-used LRU) Tiếpcận: Với mỗi trang, ghi nhận thời điểm cuối cùng trang đƣợc truy cập, trang đƣợc chọn để thay thế sẽ là trang lâu nhất chƣa đƣợc truy xuất. Ví dụ: sử dụng 3 khung trang, khởi đầu đều trống: Thảo luận:Thuật toán FIFO sử dụng thời điểm nạp để chọn trang thay thế, thuật toán tối ƣu lại dùng thời điểm trang sẽ đƣợc sử dụng, vì thời điểm này không thể xác định trƣớc nên thuật toán LRU phải dùng thời điểm cuối cùng trang đƣợc truy xuất – dùng quá khứ gần để dự đoán tƣơng lai. Thuật toán này đòi hỏi phải đƣợc cơ chế phần cứng hỗ trợ để xác định một thứ tự cho các trang theo thời điểm truy xuất cuối cùng. Có thể cài đặt theo một trong hai cách : a. Sử dụng bộ đếm: thêm vào cấu trúc của mỗi phần tử trong bảng trang một trƣờng ghi nhận thời điểm truy xuất mới nhất, và thêm vào cấu trúc của CPU một bộ đếm. mỗi lần có sự truy xuất bộ nhớ, giá trị của counter tăng lên 1. Mỗi lần thực hiện truy xuất đến một trang, giá trị của counter đƣợc ghi nhận vào trƣờng thời điểm truy xuất mới nhất của phần tử tƣơng ứng với trang trong bảng trang. thay thế trang có giá trị trƣờng thời điểm truy xuất mới nhất là nhỏ nhất. 136
b. Sử dụng stack: tổ chức một stack lƣu trữ các số hiệu trang mỗi khi thực hiện một truy xuất đến một trang, số hiệu của trang sẽ đƣợc xóa khỏi vị trí hiện hành trong stack và đƣa lên đầu stack. trang ở đỉnh stack là trang đƣợc truy xuất gần nhất, và trang ở đáy stack là trang lâu nhất chƣa đƣợc sử dụng. 9.9. Các thuật toán xấp xỉ LRU Có ít hệ thống đƣợc cung cấp đủ các hỗ trợ phần cứng để cài đặt đƣợc thuật toán LRU thật sự. Tuy nhiên, nhiều hệ thống đƣợc trang bị thêm một bit tham khảo ( reference): một bit reference, đƣợc khởi gán là 0, đƣợc gắn với một phần tử trong bảng trang. bit reference của một trang đƣợc phần cứng đặt giá trị 1 mỗi lần trang tƣơng ứng đƣợc truy cập, và đƣợc phần cứng gán trở về 0 sau từng chu kỳ qui định trƣớc. Sau từng chu kỳ qui định trƣớc, kiểm tra giá trị của các bit reference, có thể xác định đƣợc trang nào đã đƣợc truy xuất đến và trang nào không, sau khi đã kiểm tra xong, các bit reference đƣợc phần cứng gán trở về 0 .với bit reference, có thể biết đƣợc trang nào đã đƣợc truy xuất, nhƣng không biết đƣợc thứ tự truy xuất. Thông tin không đầy đủ này dẫn đến nhiều thuật toán xấp xỉ LRU khác nhau. Hình 4.28 Cấu trúc một phần tử trong bảng trang 9.9.1. Thuật toán với các bit reference phụ trợ Tiếp cận: Có thể thu thập thêm nhiều thông tin về thứ tự truy xuất hơn bằng cách lƣu trữ các bit references sau từng khoảng thời gian đều đặn: với mỗi trang, sử dụng thêm 8 bit lịch sử (history)trong bảng trang 137
sau từng khoảng thời gian nhất định (thƣờng là100 millisecondes), một ngắt đồng hồ đƣợc phát sinh, và quyền điều khiển đƣợc chuyển cho hệ điều hành. Hệ điều hành đặt bit reference của mỗi trang vào bit cao nhất trong 8 bit phụ trợ củatrang đó bằng cách đẩy các bit khác sang phải 1 vị trí, bỏ luôn bit thấp nhất. nhƣ vậy 8 bit thêm vào này sẽ lƣ u trữ tình hình truy xuất đến trang trong 8 chu kỳ cuối cùng. nếu gía trị của 8 bit là 00000000, thì trang tƣơng ứng đã không đƣợc dùng đến suốt 8 chu kỳ cuối cùng, ngƣợc lại nếu nó đƣợc dùng đến ít nhất 1 lần trong mỗi chu kỳ, thì 8 bit phụ trợ sẽ là 11111111. Một trang mà 8 bit phụ trợ có giá trị11000100 sẽ đƣợc truy xuất gần thời điểm hiện tại hơn trang có 8 bit phụ trợ là 01110111. nếu xét 8 bit phụ trợ này nhƣ một số nguyên không dấu, thì trang LRU là trang có số phụ trợ nhỏ nhất. Ví dụ : Thảo luận: Số lƣợng các bit lịch sử có thể thay đổi tùy theo phần cứng, và phải đƣợc chọn sao cho việc cập nhật là nhanh nhất có thể. 9.9.2. Thuật toán « cơ hội thứ hai » Tiếp cận: Sử dụng một bit reference duy nhất. Thuật toán cơ sở vẫn là FIFO, tuy nhiên khi chọn đƣợc một trang theo tiêu chuẩn FIFO, kiểm tra bit reference của trang đó : Nếu giá trị của bit reference là 0, thay thế trang đã chọn. Ngƣợc lại, cho trang này một cơ hội thứ hai, và chọn trang FIFO tiếp theo. Khi một trang đƣợc cho cơ hội thứ hai, giá trị của bit reference đƣợc đặt lại là 0, và thời điểm vào Ready List đƣợc cập nhật lại là thời điểm hiện tại. 138
Một trang đã đƣợc cho cơ hội thứ hai sẽ không bị thay thế trƣớc khi hệ thống đã thay thế hết những trang khác. Hơn nữa, nếu trang thƣờng xuyên đƣợc sử dụng, bit reference của nó sẽ duy trì đƣợc giá trị 1, và trang hầu nhƣ không bao giờ bị thay thế. Thảo luận: Có thể cài đặt thuật toán « cơ hội thứ hai » với một xâu vòng. Hình 2.29 Thuật toán thay thế trang > 9.9.3. Thuật toán « cơ hội thứ hai » nâng cao (Not Recently Used - NRU) Tiếp cận : xem các bit reference và dirty bit nhƣ một cặp có thứ tự . Với hai bit này, có thể có 4 tổ hợp tạo thành 4 lớp sau : (0,0) không truy xuất, không sửa đổi: đây là trang tốt nhất để thay thế. (0,1) không truy xuất gần đây, nhƣng đã bị sửa đổi: trƣờng hợp này không thật tốt, vì trang cần đƣợc lƣu trữ lại trƣớc khi thay thế. (1,0) đƣợc truy xuất gần đây, nhƣng không bị sửa đổi: trang có thể nhanh chóng đƣợc tiếp tục đƣợc sử dụng. 139
(1,1) đƣợc truy xuất gần đây, và bị sửa đổi: trang có thể nhanh chóng đƣợc tiếp tục đƣợc sử dụng, và trƣớc khi thay thế cần phải đƣợc lƣu trữ lại. lớp 1 có độ ƣu tiên thấp nhất, và lớp 4 có độ ƣu tiên cao nhất. một trang sẽ thuộc về một trong bốn lớp trên, tuỳ vào bit reference và dirty bit của trang đó. trang đƣợc chọn để thay thế là trang đầu tiên tìm thấy trong lớp có độ ƣu tiên thấp nhất và khác rỗng. 9.10. Các thuật toán thống kê Tiếp cận: sử dụng một biến đếm lƣu trữ số lần truy xuất đến một trang, và phát triển hai thuật toán sau : Thuật toán LFU: thay thế trang có giá trị biến đếm nhỏ nhất, nghĩa là trang ít đƣợc sử dụng nhất. Thuật toán MFU: thay thế trang có giá trị biến đếm lớn nhất, nghĩa là trang đƣợc sử dụng nhiều nhất (most frequently used). 9.11. Cấp phát khung trang Vấn đề đặt ra là làm thế nào để cấp phát một vùng nhớ tự do có kích thƣớc cố định cho các tiến trình khác nhau? Trong trƣờng hợp đơn giản nhất của bộ nhớ ảo là hệ đơn nhiệm, có thể cấp phát cho tiến trình duy nhất của ngƣời dùng tất cả các khung trang trống. Vấn đề nảy sinh khi kết hợp kỹ thuật phân trang theo yêu cầu với sự đa chƣơng : cần phải duy trì nhiều tiến trình trong bộ nhớ cùng lúc, vậy mỗi tiến trình sẽ đƣợc cấp bao nhiêu khung trang. 9.11.1. Số khung trang tối thiểu: Với mỗi tiến trình, cần phải cấp phát một số khung trang tối thiểu nào đó để tiến trình có thể hoạt động. Số khung trang tối thiểu này đƣợc quy định bởi kiến trúc của của một chỉ thị.Khi một lỗi trang xảy ra trƣớc khi chỉ thị hiện hành hoàn tất, chỉ thị đó cần đƣợc tái khởi động, lúc đó cần có đủ các khung trang để nạp tất cả các trang mà một chỉ thị duy nhất có thể truy xuất. Số khung trang tối thiểu đƣợc qui định bởi kiến trúc máy tính, trong khi số khung trang tối đa đƣợc xác định bởi dung lƣợng bộ nhớ vật lý có thể sử dụng. 140
a. Các thuật toán cấp phát khung trang Có hai hƣớng tiếp cận: Cấp phát cố định: Cấp phát công bằng: nếu có m khung trang và n tiến trình, mỗi tiến trình đƣợc cấp m /n khung trang. Cấp phát theo tỷ lệ: tùy vào kích thƣớc của tiến trình để cấp phát số khung trang : si = kích thƣớc của bộ nhớ ảo cho tiến trình pi S = Σ si m = số lƣợng tổng cộng khung trang có thể sử dụng Cấp phát ai khung trang cho tiến trình pi: ai = (si / S) mCấppháttheođộƣutiên : sử dụng ý tƣởng cấp phát theo tỷ lệ, nhƣng nhƣng số lƣợng khung trang cấp cho tiến trình phụ thuộc vào độ ƣu tiên của tiến trình, hơn là phụ thuộc kích thƣớc tiến trình: Nếu tiến trình pi phát sinh một lỗi trang, chọn một trong các khung trang của nó để thay thế, hoặc chọn một khung trang của tiến trình khác với độ ƣu tiên thấp hơn để thay thế. b. Thay thế trang toàn cục hay cục bộ Có thể phân các thuật toán thay thế trang thành hai lớp chính: Thay thế toàn cục: khi lỗi trang xảy ra với một tiến trình , chọn trang « nạn nhân » từ tập tất cả các khung trang trong hệ thống, bất kể khung trang đó đang đƣợc cấp phát cho một tiến trình khác. Thay thế cục bộ: yêu cầu chỉ đƣợc chọn trang thay thế trong tập các khung trang đƣợc cấp cho tiến trình phát sinh lỗi trang. Một khuyết điểm của thuật toán thay thế toàn cục là các tiến trình không thể kiểm soát đƣợc tỷ lệ phát sinh lỗi trang của mình. Vì thế, tuy thuật toán thay thế toàn cục nhìn chung cho phép hệ thống có nhiều khả năng xử lý hơn, nhƣng nó có thể dẫn hệ thống đến tình trạng trì trệ toàn bộ (thrashing). 9.12. Trì trệ toàn bộ hệ thống (Thrashing) Nếu một tiến trình không có đủ các khung trang để chứa những trang cần thiết cho xử lý, thì nó sẽ thƣờng xuyên phát sinh các lỗi trang , và vì thế phải dùng đến 141
rất nhiều thời gian sử dụng CPU để thực hiện thay thế trang. Một hoạt động phân trang nhƣ thế đƣợc gọi là sự trì trệ ( thrashing). Một tiến trình lâm vào trạng thái trì trệ nếu nó sử dụng nhiều thời gian để thay thế trang hơn là để xử lý ! Hiện tƣợng trì trệ này ảnh hƣởng nghiêm trọng đến hoạt động hệ thống, xét tình huống sau : Hệ điều hành giám sát việc sử dụng CPU. Nếu hiệu suất sử dụng CPU quá thấp, hệ điều hành sẽ nâng mức độ đa chƣơng bằng cách đƣa thêm một tiến trình mới vào hệ thống. Hệ thống có thể sử dụng thuật toán thay thế toàn cục để chọn các trang nạn nhân thuộc một tiến trình bất kỳ để có chỗ nạp tiến trình mới, có thể sẽ thay thế cả các trang của tiến trình đang xử lý hiện hành.Khi có nhiều tiến trình trong hệ thống hơn, thì một tiến trình sẽ đƣợc cấp ít khung trang hơn, và do đó phát sinh nhiều lỗi trang hơn. Khi các tiến trình phát sinh nhiều lỗi trang , chúng phải trải qua nhiều thời gian chờ các thao tác thay thế trang hoàn tất, lúc đó hiệu suất sử dụng CPU lại giảm Hệ điều hành lại quay trở lại bƣớc 1 Theo kịch bản trên đây, hệ thống sẽ lâm vào tình trạng luẩn quẩn của việc giải phóng các trang để cấp phát thêm khung trang cho một tiến trình, và các tiến trình khác lại thiếu khung trang và các tiến trình không thể tiếp tục xử lý. Đây chính là tình trạng trì trệ toàn bộ hệ thống. Khi tình trạng trì trệ này xảy ra, hệ thống gần nhƣ mất khả năng xử lý, tốc độ phát sinh lỗi trang tăng cao khủng khiếp, không công việc nào có thể kết thúc vì tất cả các tiến trình đều bận rộn với việc phân trang ! Để ngăn cản tình trạng trì trệ này xảy ra, cần phải cấp cho tiến trình đủ các khung trang cần thiết để hoạt động. Vấn đề cần giải quyết là làm sao biết đƣợc tiến trình cần bao nhiêu trang? Mô hình cục bộ ( Locality) : theo lý thuyết cục bộ, thì khi một tiến trình xử lý, nó có khuynh hƣớng di chuyển từ nhóm trang cục bộ này đến nhóm trang cục bộ khác . Một nhóm trang cục bộ là một tập các trang đang đƣợc tiến trình dùng đến trong một khoảng thời gian. Một chƣơng trình thƣờng bao gồm nhiều nhóm trang cục bộ khác nhau và chúng có thể giao nhau. 9.13. Mô hình « tập làm việc » (working set) Tiếp cận : 142
Mô hình working set đặt cơ sở trên lý thuyết cục bộ. Mô hình này sử dụng một tham số Δ , để định nghĩa một cửa sổ cho working set. Giả sử khảo sát Δ đơn vị thời gian (lần truy xuất trang) cuối cùng, tập các trang đƣợc tiến trình truy xuất đến trong Δ lần truy cập cuối cùng này đƣợc gọi là working set của tiến trình tại thời điểm hiện tại. Nếu một trang đang đƣợc tiến trình truy xuất đến, nó sẽ nằm trong working set, nếu nó không đƣợc sử dụng nữa , nó sẽ bị loại ra khỏi working set của tiến trình sau Δ đơn vị thời gian kể từ lần truy xuất cuối cùng đến nó. Nhƣ vậy working set chính là một sự xấp xỉ của khái niệm nhóm trang cục bộ. Hình 2.30 Mô hình working set Một thuộc tính rất quan trọng của working set là kích thƣớc của nó. Nếu tính toán kích thƣớc working set, WSSi, cho mỗi tiến trình trong hệ thống, thì có thể xem nhƣ : D = Σ WSSi với D là tổng số khung trang yêu cầu cho toàn hệ thống. Mỗi tiến trình sử dụng các trang trong working set của nó, nghĩa là tiến trình i yêu cầu WSSi khung trang. Nếu tổng số trang yêu cầu vƣợt quá tổng số trang có thể sử dụng trong hệ thống (D > m), thì sẽ xảy ra tình trạng trì trệ toàn bộ. Sử dụng: Hệ điều hành giám sát working set của mỗi tiến trình và cấp phát cho tiến trình tối thiểu các khung trang để chứa đủ working set của nó. Nhƣ vậy một tiến trình mới chỉ có thể đƣợc nạp vào hệ thống khi có đủ khung trang tự do cho working set của nó. Nếu tổng số khung trang yêu cầu của các tiến trình trong hệ thống vƣợt quá các khung trang có thể sử dụng, hệ điều hành chọn một tiến trình để tạm dừng, giải phóng bớt các khung trang cho các tiến trình khác hoàn tất. Thảo luận: Chiến lƣợc working set đã loại trừ đƣợc tình trạng trì trệ trong khi vẫn đảm bảo mức độ đa chƣơng của hệ thống là cao nhất có thể, cho phép sử dụng tối ƣu CPU. 143
Điểm khó khăn của mô hình này là theo vết của các working set của tiến trình trong từng thời điểm. Có thể xấp xỉ mô hình working set với một ngắt đồng hồ sau từng chu kỳ nhất định và một bit reference: phát sinh một ngắt đồng hồ sau từng T lần truy xuất bộ nhớ. khi xảy ra một ngắt đồng hồ, kiểm tra các trang có bit reference là 1, các trang này đƣợc xem nhƣ thuộc về working set. Một hệ thống sử dụng kỹ thuật phân trang theo yêu cầu thuần túy (một trang không bao giờ đƣợc nạp trƣớc khi có yêu cầu truy xuất) để lộ một đặc điểm khá bất lợi : một số lƣợng lớn lỗi trang xảy ra khi khởi động tiến trình. Tình trạng này là hậu quả của khuynh hƣớng đạt tới việc đƣa nhóm trang cục bộ vào bộ nhớ. Tình trạng này cũng có thể xảy ra khi một tiến trình bị chuyển tạm thời ra bộ nhớ phụ, khi đƣợc tái kích hoạt, tất cả các trang của tiến trình đã đƣợc chuyển lên đĩa phải đƣợc mang trở lại vào bộ nhớ, và một loạt lỗi trang lại xảy ra. Để ngăn cản tình hình lỗi trang xảy ra quá nhiều tại thời điểm khởi động tiến trình, có thể sử dụng kỹ thuật tiền phân trang (prepaging) : nạp vào bộ nhớ một lần tất cả các trang trong working set của tiến trình. 9.14. Tần suất xảy ra lỗi trang Tiếp cận: Tần suất lỗi trang rất cao khiến tình trạng trì trệ hệ thống có thể xảy ra. Khi tần suất lỗi trang quá cao, tiến trình cần thêm một số khung trang. Khi tần suất lỗi trang quá thấp, tiến trình có thể sỡ hữu nhiều khung trang hơn mức cần thiết. Có thể thiết lập một giá trị chặn trên và chặn dƣới cho tần suất xảy ra lỗi trang, và trực tiếp ƣớc lƣợng và kiểm soát tần suất lỗi trang để ngăn chặn tình trang trì trệ xảy ra : Nếu tần suất lỗi trang vƣợt quá chặn trên, cấp cho tiến trình thêm một khung trang Nếu tần suất lỗi trang thấp hơn chặn dƣới, thu hồi bớt một khung trang từ tiến trình 9.15. Bộ nhớ ảo-Tóm tắt Các kỹ thuật hỗ trợ các mô hình tổ chức bộ nhớ hiện đại : Swapping : sử dụng thêm bộ nhớ phụ để lƣu trữ tạm các tiến trình đang bị khóa, nhờ vậy có thể tăng mức độ đa chƣơng của hệ thống với cấu hình máy có dung lƣợng bộ nhớ chính thấp. 144
Bộ nhớ ảo : sử dụng kỹ thuật phân trang theo yêu cầu, kết hợp thêm kỹ thuật swapping để mở rộng bộ nhớ chính. Tách biệt không gian địa chỉ và không gian vật lý, nhờ đó có thể xử lý các chƣơng trình có kích thƣớc lớn hơn bộ nhớ vật lý thật sự Khi cài đặt bộ nhớ ảo, phải sử dụng một thuật toán thay thế trang thích hợp để chọn các trang bị chuyển tạm thời ra bộ nhớ phụ, dành chỗ trong bộ nhớ chính cho trang mới. Các thuật toán thay thế thƣờng sử dụng là FIFO, LRU và các thuật toán xấp xỉ LRU, các thuật toán thống kê NFU, MFU Khi mức độ đa chƣơng tăng cao đến một chừng mực nào đó, hệ thống có thể lâm vào tình trạng trì trệ do tất cả các tiến trình đều thiếu khung trang. Có thể áp dụng mô hình working set để dành cho mỗi tiến trình đủ các khung trang cần thiết tại một thời điểm, từ đó có thể ngăn chặn tình trạng trì trệ xảy ra. 9.15.1. Củng cố bài học Các câu hỏi cần trả lời đƣợc sau bài học này : 1. Bộ nhớ ảo là gì ? 2. Sự thật đằng sau ảo giác: giới hạn của bộ nhớ ảo ? Chi phí thực hiện? 3. Các vấn đề của bộ nhớ ảo : thay thế trang, cấp phát khung trang ? 4. Mô hình working set : khái niệm, cách tính trong thực tế, sử dụng ? 9.15.2. Bài Tập Bài 1. Khi nào thì xảy ra lỗi trang ? Mô tả xử lý của hệ điều hành khi có lỗi trang. Bài 2. Giả sử có một chuỗi truy xuất bộ nhớ có chiều dài p với n số hiệu trang khác nhau xuất hiện trong chuỗi. Giả sử hệ thống sử dụng m khung trang ( khởi động trống). Với một thuật toán thay thế trang bất kỳ : Cho biết số lƣợng tối thiểu các lỗi trang xảy ra ? Cho biết số lƣợng tối đa các lỗi trang xảy ra ? Bài 3. Một máy tính 32-bit địa chỉ, sử dụng một bảng trang nhị cấp. Địa chỉ ảo đƣợc phân bổ nhƣ sau : 9 bit dành cho bảng trang cấp 1, 11 bit cho bảng trang cấp 2, và cho offset. Cho biết kích thƣớc một trang trong hệ thống, và địa chỉ ảo có bao nhiêu trang ? Bài 4. Giả sử địa chỉ ảo 32-bit đƣợc phân tách thành 4 trƣờng a,b,c,d. 3 trƣờng đầu tiên đƣợc dùng cho bảng trang tam cấp, trƣờng thứ 4 dành cho offset. Số lƣợng 145
trang có phụ thuộc vào cả kích thƣớc 4 trƣờng này không ? Nếu không, những trƣờng nào ảnh hƣởng đến số lƣợng trang, và những trƣờng nào không ? Bài 5. Một máy tính có 48-bit địa chỉ ảo, và 32-bit địa chỉ vật lý. Kích thƣớc một trang là 8K. Có bao nhiêu phần tử trong một bảng trang ( thông thƣờng)? Trong bảng trang nghịch đảo ? Bài 6. Một máy tính cung cấp cho ngƣời dùng một không gian địa chỉ ảo 232 bytes. Máy tính này có bộ nhớ vật lý 218 bytes. Bộ nhớ ảo đƣợc thực hiện với kỹ thuật phân trang, kích thƣớc trang là 4096 bytes. Một tiến trình của ngƣời dùng phát sinh địa chỉ ảo 11123456. Giải thích cách hệ thống chuyển đổi địa chỉ ảo này thành địa chỉ vật lý tƣơng ứng. Phân biệt các thao tác phần mềm và phần cứng. Bài 7. Giả sử có một hệ thống sử dụng kỹ thuật phân trang theo yêu cầu. Bảng trang đƣợc lƣu trữ trong các thanh ghi. Để xử lý một lỗi trang tốn 8 miliseconds nếu có sẵn một khung trang trống, hoặc trang bị thay thế không bị sửa đổi nội dung, và tốn 20 miliseconds nếu trang bị thay thế bị sửa đổi nội dung. Mỗi truy xuất bộ nhớ tốn 100nanoseconds. Giả sử trang bị thay thế có xác suất bị sử đổi là 70%. Tỷ lệ phát sinh lỗi trang phải là bao nhiêu để có thể duy trì thời gian truy xuất bộ nhớ ( effective acess time) không vƣợt quá 200nanoseconds ? Bài 8. Xét các thuật toán thay thế trang sau đây. Xếp thứ tự chúng dựa theo tỷ lệ phát sinh lỗi trang của chúng. Phân biệt các thuật toán chịu đựng nghịch lý Belady và các thuật toán không bị nghịch lý này ảnh hƣởng. a)LRU b)FIFOc)Chiến lƣợc thay thế tối ƣu d)Cơ hội thứ hai Bài 9. Một máy tính có 4 khung trang. Thời điểm nạp, thời điểm truy cập cuối cùng, và các bit reference ®, modify (M) của mỗi trang trong bộ nhớ đƣợc cho trong bảng sau : 146
Trang nào sẽ đƣợc chọn thay thế theo : a) thuật toán NRU b) thuật toán FIFO c) thuật toán LRU d) thuật toán “ cơ hội thứ 2” Bài 10. Xét mảng hai chiều A: var A: array [1 100, 1 100] of integer; Với A[1][1] đƣợc lƣu trữ tại vị trí 200, trong bộ nhớ tổ chức theo kỹ thuật phân trang với kích thƣớc trang là 200. Một tiến trình trong trang 0 (chiếm vị trí từ 0 đến 199) sẽ thao tác ma trận này ; nhƣ vậy mỗi chỉ thị sẽ đƣợc nạp từ trang 0. Với 3 khung trang, có bao nhiêu lỗi trang sẽ phát sinh khi thực hiện vòng lặp sau đây để khởi động mảng, sử dụng thuật toán thay thế LRU , và giả sử khung trang 1 chƣá tiến trình, hai khung trang còn lại đƣợc khởi động ở trạng thái trống : a. for j:= 1 to 100 do for i :=1 to 100 do A[i][j]:= 0; b. for i :=1 to 100 do for j:=1 to 100 do A[i][j]:= 0; Bài 11. Xét chuỗi truy xuất bộ nhớ sau: 1, 2 , 3 , 4 , 2 , 1 , 5 , 6 , 2 , 1 , 2 , 3 , 7 , 6 , 3 , 2 , 1 , 2 , 3 , 6 Có bao nhiêu lỗi trang xảy ra khi sử dụng các thuật toán thay thế sau đây, giả sử có 1, 2, 3, 4, 5, 6, 7 khung trang ? a) LRU 147
b) FIFO c) Chiến lƣợc tối ƣu Bài 12. Trong một hệ thống sử dụng kỹ thuật phân trang theo yêu cầu, xét hai đoạn chƣơng trình sau đây: const N = 1024*1024 var A,B : array [1 N] of integer; [Program 1] for i:=1 to N do A[i]:=i; for i:=1 to N do B[A[i]]:=random(N); [Program 2] for i:=1 to N do A[i]:= random(N); for i:=1 to N do B[A[i]]:=i; Bài 13. Giả sử có một máy tính đồ chơi sử dụng 7-bit địa chỉ. Kích thƣớc một trang là 8 bytes, và hệ thống sử dụng một bảng trang nhị cấp, dùng 2-bit làm chỉ mục đến bảng trang cấp 1 , 2-bit làm chỉ mục đến bảng trang cấp 2. Xét một tiến trình sử dụng các địa chỉ trong những phạm vi sau : 0 15, 21 29, 94 106, và 115 127. a) Vẽ chi tiết toàn bộ bảng trang cho tiến trình này b) Phải cấp phát cho tiến trình bao nhiêu khung trang, giả sử tất cả đều nằm trong bộ nhớ chính ? c) Bao nhiêu bytes ứng với các vùng phân mảnh nội vi trong tiến trình này? d) Cần bao nhiêu bộ nhớ cho bảng trang của tiến trình này ? Bài 14. Giả sử có một máy tính sử dụng 16-bit địa chỉ. Bộ nhớ ảo đƣợc thực hiện với kỹ thuật phân đoạn kết hợp phân trang, kích thƣớc tối đa của một phân đoạn là 4096 bytes. Bộ nhớ vật lý đƣợc phân thành các khung trang có kích thƣớc 512 bytes. a) Thể hiện cách địa chỉ ảo đƣợc phân tích để phản ánh segment, page, offset b) Xét một tiến trình sử dụng các miền địa chỉ sau, xác định số hiệu segment và số hiệu page tƣơng ứng trong segment mà chƣơng trình truy cập đến : 350 1039, 3046 3904, 7100 9450, 33056 39200, 61230 63500 c) Bao nhiêu bytes ứng với các vùng phân mảnh nội vi trong tiến trình này? d) Cần bao nhiêu bộ nhớ cho bảng phân đoạn và bảng trang của tiến trình này ? 148
CHƢƠNG 10. HỆ THỐNG QUẢN LÝ TẬP TIN Trong hầu hết các ứng dụng, tập tin là thành phần chủ yếu. Cho dù mục tiêu của ứng dụng là gì nó cũng phải bao gồm phát sinh và sử dụng thông tin. Thông thƣờng đầu vào của các ứng dụng là tập tin và đầu ra cũng là tập tin cho việc truy xuất của ngƣời sử dụng và các chƣơng trình khác sau này. Trong bài học này chúng ta sẽ tìm hiểu những khái niệm và cơ chế của hệ thống quản lý tập tin thông qua các nội dung nhƣ sau: Các khái niệm cơ bản Mô hình tổ chức và quản lý các tập tin. Bài học này giúp chúng ta hiểu đƣợc tập tin là gì, cách thức tổ chức và quản lý tập tin nhƣ thế nào. Từ đó giúp chúng ta hiểu đƣợc các cơ chế cài đặt hệ thống tập tin trên các hệ điều hành. Bài học này đòi hỏi những kiến thức về : các thao tác với tập tin, một số tính chất của tập tin ở góc độ ngƣời sử dụng và những kiến thức về cấu trúc dữ liệu cũng nhƣ về kiến trúc máy tính phần cấu trúc và tổ chức lƣu trữ của đĩa. 10.1. CÁC KHÁI NIỆM CƠ BẢN 10.1.1. Bộ nhớ ngoài Máy tính phải sử dụng thiết bị có khả năng lƣu trữ trong thời gian dài (long-term) vì : Phải chứa những lƣợng thông tin rất lớn (giữ vé máy bay, ngân hàng ) Thông tin phải đƣợc lƣu giữ một thời gian dài trƣớc khi xử lý Nhiều tiến trình có thể truy cập thông tin cùng lúc. Giải pháp là sử dụng các thiết bị lƣu trữ bên ngoài gọi là bộ nhớ ngoài. 10.1.2. Tập tin và thư mục a. Tập tin Tập tin là đơn vị lƣu trữ thông tin của bộ nhớ ngoài. Các tiến trình có thể đọc hay tạo mới tập tin nếu cần thiết. Thông tin trên tập tin là vững bền không bị ảnh hƣởng bởi cácxử lý tạo hay kết thúc các tiến trình, chỉ mất đi khi user thật sự muốn xóa. Tập tin đƣợc quản lý bởi hệ điều hành. 149
b. Thƣ mục Để lƣu trữ dãy các tập tin, hệ thống quản lý tập tin cung cấp thƣ mục, mà trong nhiều hệ thống có thể coi nhƣ là tập tin. 10.2. Hệ thống quản lý tập tin Các tập tin đƣợc quản lý bởi hệ điều hành với cơ chế gọi là hệ thống quản lý tập tin. Bao gồm : cách hiển thị, các yếu tố cấu thành tập tin, cách đặt tên, cách truy xuất, cách sử dụng và bảo vệ tập tin, các thao tác trên tập tin. Cách tổ chức thƣ mục, các đặc tính và các thao tác trên thƣ mục. 10.3. Mô hình tổ chức và quản lý các tập tin 10.3.1. Tập tin : a. Tên tập tin : Tập tin là một cơ chế trừu tƣợng và để quản lý mỗi đối tƣợng phải có một tên. Khi tiến trình tạo một tập tin, nó sẽ đặt một tên, khi tiến trình kết thúc tập tin vẫn tồn tại và có thể đƣợc truy xuất bởi các tiến trình khác với tên tập tin đó. Cách đặt tên tập tin của mỗi hệ điều hành là khác nhau, đa số các hệ điều hành cho phép sử dụng 8 chữ cái để đặt tên tập tin nhƣ ctdl, caycb, tamhghau v.v , thƣờng thƣờng thì các ký tự số và ký tự đặc biệt cũng đƣợc sử dụng nhƣ baitap2 , Hệ thống tập tin có thể có hay không phân biệt chữ thƣờng và chữ hoa. Ví dụ : UNIX phân biệt chữ thƣờng và hoa còn MS-DOS thì không phân biệt. Nhiều hệ thống tập tin hỗ trợ tên tập tin gồm 2 phần đƣợc phân cách bởi dấu „.‟ mà phần sau đƣợc gọi là phần mở rộng. Ví dụ : vidu.txt. Trong MS-DOS tên tập tin có từ 1 đến 8 ký tƣ, phần mở rộng có từ 1 đến 3 ký tự. Trong UNIX có thể có nhiều phân cách nhƣ prog.c.Z. Một số kiểu mở rộng thông thƣờng là : .bak, .bas, .bin, .c, .dat, .doc, .ftn, .hlp, .lib, .obj, .pas, .tex, .txt. Trên thực tế phần mở rộng có hữu ích trong một số trƣờng hợp, ví dụ nhƣ có những trình dịch C chỉ nhận biết các tập tin có phần mở rộng là .C b. Cấu trúc của tập tin : Gồm 3 loại : 150
Dãy tuần tự các byte không cấu trúc : hệ điều hành không biết nội dung của tập tin:MS- DOS và UNIX sử dụng loại này. Dãy các record có chiều dài cố định.Cấu trúc cây : gồm cây của những record, không cần thiết có cùng độ dài, mỗi record có một trƣờng khóa giúp cho việc tìm kiếm nhanh hơn. Kiểu tập tin : Nếu hệ điều hành nhận biết đƣợc loại tập tin, nó có thể thao tác một cách hợp lý trên tập tin đó. Các hệ điều hành hỗ trợ cho nhiều loại tập tin khác nhau bao gồm các kiểu nhƣ : tập tin thƣờng, thƣ mục, tập tin có ký tự đặc biệt, tập tin khối. Tập tin thường : là tập tin text hay tập tin nhị phân chứa thông tin của ngƣời sử dụng. Thư mục : là những tập tin hệ thống dùng để lƣu giữ cấu trúc của hệ thống tập tin. Tập tin có ký tự đặc biệt : liên quan đến nhập xuất thông qua các thiết bị nhập xuất tuần tự nhƣ màn hình, máy in, mạng. Tập tin khối : dùng để truy xuất trên thiết bị đĩa. Tập tin thƣờng đƣợc chia làm hai loại là tập tin văn bản và tập tin nhị phân. Tập tin văn bản chứa các dòng văn bản cuối dòng có ký hiệu enter. Mỗi dòng có độ dài có thể khác nhau. Ƣu điểm của kiểu tập tin này là nó có thể hiển thị, in hay soạn thảo với một editor thông thƣờng.Đa số các chƣơng trình dùng tập tin văn bản để nhập xuất, nó cũng dễ dàng làm đầu vào và đầu ra cho cơ chế pipeline. Tập tin nhị phân :có cấu trúc khác tập tin văn bản. Mặc dù về mặt kỹ thuật , tập tin nhị phân gồm dãy các byte , nhƣng hệ điều hành chỉ thực thi tập tin đó nếu nó có cấu trúc đúng. Ví dụ một một tập tin nhị phân thi hành đƣợc của UNIX. Thƣờng thƣờng nó bao gồm năm thành phần : header, text, data, relocation bits, symbol table. Header bắt đầu bởi byte nhận diện cho biết đó là tập tin thi hành. Sau đó là 16 bit cho biết kích thƣớc các thành phần của tập tin, địa chỉ bắt đầu thực hiện và một số bit cờ. Sau header là dữ liệu và text của tập tin. Nó đƣợc nạp vào bộ nhớ và định vị lại bởi những bit relocation. Bảng symbol đƣợc dùng để debug. Một ví dụ khác là tập tin nhị phân kiểu archive. Nó chứa các thƣ viện đã đƣợc dịch nhƣng chƣa đƣợc liên kết. Bao gồm một header cho biết tên, ngày tạo, ngƣời sở hữu, mã bảo vệ, và kích thƣớc 151
c. Truy xuất tập tin : Tập tin lƣu trữ các thông tin. Khi tập tin đƣợc sử dụng, các thông tin này đƣợc đƣa vào bộ nhớ của máy tính. Có nhiều cách để truy xuất chúng. Một số hệ thống cung cấp chỉ một phƣơng pháp truy xuất, một số hệ thống khác, nhƣ IBM chẳng hạn cho phép nhiều cách truy xuất. Kiểu truy xuất tập tin đơn giản nhất là truy xuất tuần tự . Tiến trình đọc tất cả các byte trong tập tin theo thứ tự từ đầu. Các trình soạn thảo hay trình biên dịch cũng truy xuất tập tin theo cách này. Hai thao tác chủ yếu trên tập tin là đọc và ghi. Thao tác đọc sẽ đọc một mẫu tin tiếp theo trên tập tin và tự động tăng con trỏ tập tin. Thao tác ghi cũng tƣơng tự nhƣ vậy. Tập tin có thể tự khởi động lại từ vị trí đầu tiên và trong một số hệ thống tập tin cho phép di chuyển con trỏ tập tin đi tới hoặc đi lui n mẫu tin. 152
Truy xuất kiểu này thuận lợi cho các loại băng từ và cũng là cách truy xuất khá thông dụng. Truy xuất tuần tự cần thiết cho nhiều ứng dụng. Có hai cách truy xuất. Cách truy xuất thứ nhất thao tác đọc bắt đầu ở vị trí đầu tập tin, cách thứ hai có một thao tác đặcbiệt gọi là SEEK cung cấp vị trí hiện thời làm vị trí bắt đầu. Sau đó tập tin đƣợc đọc tuần tự từ vị trí bắt đầu. Một kiểu truy xuất khác là truy xuất trực tiếp. Một tập tin có cấu trúc là các mẫu tin logic có kích thƣớc bằng nhau, nó cho phép chƣơng trình đọc hoặc ghi nhanh chóng mà không cần theo thứ tự. Kiểu truy xuất này dựa trên mô hình của đĩa. Đĩa cho phép truy xuất ngẫu nhiên bất kỳ khối dữ liệu nào của tập tin. Truy xuất trực tiếp đƣợc sử dụng trong trƣờng hợp phải truy xuất một khối lƣợng thông tin lớn nhƣ trong cơ sở dữ liệu chẳng hạn. Ngoài ra còn có một số cách truy xuất khác dự trên kiểu truy xuất này nhƣ truy xuất theo chỉ mục d. Thuộc tính tập tin : Ngoài tên và dữ liệu, hệ điều hành cung cấp thêm một số thông tin cho tập tin gọi là thuộc tính Các thuộc tính thông dụng trong một số hệ thống tập tin : 153
Hình 8.3 Một số thuộc tính thông dụng của tập tin 154
10.3.2. Thư mục : a. Hệ thống thƣ mục theo cấp bậc : Một thƣ mục thƣờng thƣờng chứa một số entry, mỗi entry cho một tập tin. Mỗi entry chứa tên tập tin, thuộc tính và địa chỉ trên đĩa lƣu dữ liệu hoặc một entry chỉ chứa tên tập tin và một con trỏ, trỏ tới một cấu trúc, trên đó có thuộc tính và vị trí lƣu trữ của tập tin. Khi một tập tin đƣợc mở, hệ điều hành tìm trên thƣ mục của nó cho tới khi tìm thấy tên của tập tin đƣợc mở. Sau đó nó sẽ xác định thuộc tính cũng nhƣ địa chỉ lƣu trữ trên đĩa và đƣa vào một bảng trong bộ nhớ. Những truy xuất sau đó thực hiện trong bộ nhớ chính. Số lƣợng thƣ mục trên mỗi hệ thống là khác nhau. Thiết kế đơn giản nhất là hệ thống chỉ có thƣ mục đơn(còn gọi là thƣ mục một cấp), chứa tất cả các tập tin của tất cả ngƣời dùng, cách này dễ tổ chức và khai thác nhƣng cũng dễ gây ra khó khăn khi có nhiều ngƣời sử dụng vì sẽ có nhiều tập tin trùng tên. Ngay cả trong trƣờng hợp chỉ có mộtngƣời sử dụng, nếu có nhiều tập tin thì việc đặt tên cho một tập tin mới không trùng lắp là một vấn đề khó. Cách thứ hai là có một thƣ mục gốc và trong đó có nhiều thƣ mục con, trong mỗi thƣ mục con chứa tập tin của ngƣời sử dụng (còn gọi là thƣ mục hai cấp), cách này tránh đƣợc trƣờng hợp xung đột tên nhƣng cũng còn khó khăn với ngƣời dùng có nhiều tập tin. Ngƣời sử dụng luôn muốn nhóm các ứng dụng lại một cách logic. Từ đó, hệ thống thƣ mục theo cấp bậc (còn gọi là cây thƣ mục) đƣợc hình thành với mô hình một thƣ mục có thể chứa tập tin hoặc một thƣ mục con và cứ tiếp tục nhƣ vậy hình thành cây thƣ mục nhƣ trong các hệ điều hành DOS, Windows, v. v Ngoài ra, trong một số hệ điều hành nhiều ngƣời dùng, hệ thống còn xây dựng các hình thức khác của cấu trúc thƣ mục nhƣ cấu trúc thƣ mục theo đồ thị có chu trình và cấu trúc thƣ mục theo đồ thị tổng quát. Các cấu trúc này cho phép các ngƣời dùng trong hệ thống có thể liên kết với nhau thông qua các thƣ mục chia sẻ. 155
b. Đƣờng dẫn : Khi một hệ thống tập tin đƣợc tổ chức thành một cây thư mục, có hai cách để xác định một tên tập tin. Cách thứ nhất là đườ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. Ví dụ : /usr/ast/mailbox. Dạng thứ hai là đường dẫn tương đối, dạng này có liên quan đến một khái niệm là thư mục hiện hành hay thƣ mục làm việc. Ngƣời sử dụng có thể quy định một thƣ mục là thƣ mục hiện hành. Khi đó đƣờng dẫn không bắt đầu từ thƣ mục gốc mà liên quan đến thƣ mục hiện hành. Ví dụ, nếu thƣ mục hiện hành là /usr/ast thì tập tin với đƣờng dẫn tuyệt đối /usr/ast/mailbox có thể đƣợc dùng đơn giản là mailbox. Trong phần lớn hệ thống, mỗi tiến trình có một thƣ mục hiện hành riêng, khi một tiến trình thay đổi thƣ mục làm việc và kết thúc, không có sự thay đổi để lại trên hệ thống tập tin. Nhƣng nếu một hàm thƣ viện thay đổi đƣờng dẫn và sau đó không đổi lại thì sẽ có ảnh hƣởng đến tiến trình. Hầu hết các hệ điều hành đều hỗ trợ hệ thống thƣ mục theo cấp bậc với hai entry đặc biệt cho mỗi thƣ mục là “.” và “ ”. “.” chỉ thƣ mục hiện hành, “ ” chỉ thƣ mục cha. 10.4. Các chức năng 10.4.1. Tập tin : Tạo : một tập tin đƣợc tạo chƣa có dữ liệu. Mục tiêu của chức năng này là thông báo cho biết rằng tập tin đã tồn tại và thiết lập một số thuộc tính. Xóa :khi một tập tin không còn cần thiết nữa, nó đƣợc xóa để tăng dung lƣợng đĩa. Một số hệ điều hành tự động xoá tập tin sau một khoảng thời gian n ngày. Mở : trƣớc khi sử dụng một tập tin, tiến trình phải mở nó. Mục tiêu của mở là cho phép hệ thống thiết lập một số thuộc tính và địa chỉ đĩa trong bộ nhớ để tăng tốc độ truy xuất. Đóng : khi chấm dứt truy xuất, thuộc tính và địa chỉ trên đĩa không cần dùng nữa, tập tin đƣợc đóng lại để giải phóng vùng nhớ. Một số hệ thống hạn chế tối đa số tập tin mở trong một tiến trình. Đọc : đọc dữ liệu từ tập tin tại vị trí hiện thời của đầu đọc, nơi gọi sẽ cho biết cần bao nhiêu dữ liệu và vị trí của buffer lƣu trữ nó. Ghi : ghi dữ liệu lên tập tin từ vị trí hiện thời của đầu đọc. Nếu là cuối tập tin,kích thƣớc tập tin sẽ tăng lên, nếu đang ở giữa tập tin, dữ liệu sẽ bị ghi chồng lên. 157
Thêm : gần giống nhƣ WRITE nhƣng dữ liệu luôn đƣợc ghi vào cuối tập tin. Tìm :dùng để truy xuất tập tin ngẫu nhiên. Khi xuất hiện lời gọi hệ thống, vị trí con trỏ đang ở vị trí hiện hành đƣợc di chuyển tới vị trí cần thiết. Sau đó dữ liệu sẽ đƣợc đọc ghi tại vị trí này. Lấy thuộc tính: lấy thuộc tính của tập tin cho tiến trình Thiết lập thuộc tính: thay đổi thuộc tính của tập tin sau một thời gian sử dụng. Đổi tên :thay đổi tên của tập tin đã tồn tại. 10.4.2. Thư mục : Tạo : một thƣ mục đƣợc tạo, nó rỗng, ngoại trừ “.” và “ ” đƣợc đặt tự động bởi hệ thống.Xóa :xoá một thƣ mục, chỉ có thƣ mục rỗng mới bị xóa, tƣ mục chứa “.” và “ ” coi nhƣ là thƣ mục rỗng. Mở thư mục :thƣ mục có thể đƣợc đọc. Ví dụ để liệt kê tất cả tập tin trong một thƣ mục, chƣơng trình liệt kê mở thƣ mục và đọc ra tên của tất cả tập tin chứa trong đó. Trƣớc khi thƣ mục đƣợc đọc, nó phải đƣợc mở ra trƣớc. Đóng thư mục :khi một thƣ mục đã đƣợc đọc xong, phải đóng thƣ mục để giải phóng vùng nhớ. Đọc thư mục :Lệnh này trả về entry tiếp theo trong thƣ mục đã mở. Thông thƣờng có thể đọc thƣ mục bằng lời gọi hệ thống READ, lệnh đọc thƣ mục luôn luôn trả về một entry dƣới dạng chuẩn . Đổi tên :cũng nhƣ tập tin, thƣ mục cũng có thể đƣợc đổi tên. Liên kết :kỹ thuật này cho phép một tập tin có thể xuất hiện trong nhiều thƣ mục khác nhau. Khi có yêu cầu, một liên kết sẽ đƣợc tạo giữa tập tin và một đƣờng dẫn đƣợc cung cấp. Bỏ liên kết :Nếu tập tin chỉ còn liên kết với một thƣ mục, nó sẽ bị loại bỏ hoàn toàn khỏi hệ thống, nếu nhiều thì nó bị giảm chỉ số liên kết. 10.5. Câu hỏi kiểm tra kiến thức 1. Tập tin là gì ? Thƣ mục là gì ? Tại sao phải quản lý tập tin và thƣ mục ? 2. Tập tin có những đặc tính gì ? Những đặc tính nào là quan trọng ? Tại sao ? 3. Nêu các chức năng của tập tin và thƣ mục. 158
CHƢƠNG 11. CÁC PHƢƠNG PHÁP CÀI ĐẶT HỆ THỐNG QUẢN LÝ TẬP TIN Ngƣời sử dụng thì quan tâm đến cách đặt tên tập tin, các thao tác trên tập tin, cây thƣ mục Nhƣng đối ngƣời cài đặt thì quan tâm đến tập tin và thƣ mục đƣợc lƣu trữ nhƣ thế nào, vùng nhớ trên đĩa đƣợc quản lý nhƣ thế nào và làm sao cho toàn bộ hệ thống làm việc hữu hiệu và tin cậy. Hệ thống tập tin đƣợc cài đặt trên đĩa. Để gia tăng hiệu quả trong việc truy xuất, mỗi đơn vị dữ liệu đƣợc truy xuất gọi là một khối. Một khối dữ liệu bao gồm một hoặc nhiều sector. Bộ phận tổ chức tập tin quản lý việc lƣu trữ tập tin trên những khối vật lý bằng cách sử dụng các bảng có cấu trúc. Trong bài học này chúng ta sẽ tìm hiểu các phƣơng pháp tổ chức quản lý tập tin trên bộ nhớ phụ thông qua các nội dung nhƣ sau: Bảng quản lý thƣ mục, tập tin Bảng phân phối vùng nhớ Tập tin chia sẻ Quản lý đĩa Độ an toàn của hệ thống tập tin Bài học này giúp chúng ta nắm đặc điểm cũng nhƣ ƣu và khuyết điểm của các phƣơng pháp tổ chức quản lý tập tin trên đĩa và một số vấn đề liên quan khác nhờ đó có thể hiểu đƣợc cách các hệ điều hành cụ thể quản lý tập tin nhƣ thế nào. Bài học này đòi hỏi những kiến thức về :mô hình tổ chức các tập tin và thƣ mục cũng và một số cấu trúc dữ liệu. 11.1. BẢNG QUẢN LÝ THƢ MỤC, TẬP TIN 11.1.1. Khái niệm Trƣớc khi tập tin đƣợc đọc, tập tin phải đƣợc mở, để mở tập tin hệ thống phải biết đƣờng dẫn do ngƣời sử dụng cung cấp và đƣợc định vị trong cấu trúc đầu vào thƣ mục (directory entry). Directory entry cung cấp các thông tin cần thiết để tìm kiếm các khối. Tuỳ thuộc vào mỗi hệ thống, thông tin là địa chỉ trên đĩa của toàn bộ tập tin, số hiệu của khối đầu tiên, hoặc là số I-node.Cài đặt Bảng này thƣờng đƣợc cài đặt ở phần đầu của đĩa. Bảng là dãy các phần tử có kích thƣớc xác định, mỗi phần tử đƣợc gọi là một entry. Mỗi entry sẽ lƣu thông tin về tên , thuộc tính, vị trí lƣu trữ của một tập tin hay thƣ mục. 159
Ví dụ quản lý thƣ mục trong CP/M : 11.2. Bảng phân phối vùng nhớ 11.2.1. Khái niệm Bảng này thƣờng đƣợc sử dụng phối hợp với bảng quản lý thƣ mục tập tin, mục tiêu là cho biết vị trí khối vật lý của một tập tin hay thƣ mục nào đó nói khác đi là lƣu giữ dãy các khối trên đĩa cấp phát cho tập tin lƣu dữ liệu hay thƣ mục. Có một số phƣơng pháp đƣợc cài đặt. 11.2.2. Các phương pháp a. Định vị liên tiếp : Lƣu trữ tập tin trên dãy các khối liên tiếp. Phƣơng pháp này có 2 ƣu điểm : thứ nhất, dể dàng cài đặt. Thứ hai, dể dàng thao tác vì toàn bộ tập tin đƣợc đọc từ đĩa bằng thao tác đơn giản không cần định vị lại. Phƣơng pháp này cũng có 2 khuyết điểm : không linh động trừ khi biết trƣớc kích thƣớc tối đa của tập tin. Sự phân mảnh trên đĩa, gây lãng phí lớn. 160
b. Định vị bằng danh sách liên kết : Mọi khối đều đƣợc cấp phát, không bị lãng phí trong trƣờng hợp phân mảnh và directory entry chỉ cần chứa địa chỉ của khối đầu tiên. Tuy nhiên khối dữ liệu bị thu hẹp lại và truy xuất ngẫu nhiên sẽ chậm. 161
11.2.3. Danh sách liên kết sử dụng index : Tƣơng tự nhƣ hai nhƣng thay vì dùng con trỏ thì dùng một bảng index. Khi đó toàn bộ khối chỉ chứa dữ liệu. Truy xuất ngẫu nhiên sẽ dễ dàng hơn. Kích thƣớc tập tin đƣợc mở rộng hơn. Hạn chế là bản này bị giới hạn bởi kích thƣớc bộ nhớ . 11.2.4. I-nodes : Một I-node bao gồm hai phần. Phần thứ nhất là thuộc tính của tập tin. Phần này lƣu trữ các thông tin liên quan đến tập tin nhƣ kiểu, ngƣời sở hữu, kích thƣớc, v.v Phần thứ hai chứa địa chỉ của khối dữ liệu. Phần này chia làm hai phần nhỏ. Phần nhỏ thứ nhất bao gồm 10 phần tử, mỗi phần tử chứa địa chỉ khối dữ liệu của tập tin. Phần tử thứ 11 chứa địa chỉ gián tiếp cấp 1 (single indirect), chứa địa chỉ của một khối, trong khối đó chứa một bảng có thể từ 210 đến 232 phần tử mà mỗi phần tử mới chứa địa chỉ của khối dữ liệu. Phần tử thứ 12 chứa địa chỉ gián tiếp cấp 2 (double indirect), chứa địa chỉ của bảngcác khối single indirect. Phần tử thứ 13 chứa địa chỉ gián tiếp cấp 3 (double indirect), chứa địa chỉ của bảng các khối double indirect. 162
Cách tổ chức này tƣơng đối linh động. Phƣơng pháp này hiệu quả trong trƣờng hợp sử dụng để quán lý những hệ thống tập tin lớn. Hệ điều hành sử dụng phƣơng pháp này là Unix (Ví dụ : BSD Unix) 11.3. Tập tin chia sẻ Khi có nhiều ngƣời sử dụng cùng làm việc trong một đề án, họ cần chia sẻ các tập tin. Cách chia sẻ thông thƣờng là tập tin xuất hiện trong các thƣ mục là nhƣ nhau nghĩa là một tập tin có thể liên kết với nhiều thƣ mục khác nhau. Để cài đặt đƣợc, khối đĩa không đƣợc liệt kê trong thƣ mục mà đƣợc thay thế bằng một cấu trúc dữ liệu, thƣ mục sẽ trỏ tới cấu trúc này. Một cách khác là hệ thống tạo một tập tin mới có kiểu LINK, tập tin mới này chỉ chứa đƣờng dẫn của tập tin đƣợc liên kết, khi cần truy xuất sẽ dựa trên tập tin LINK để xác định tập tin cần truy xuất, phƣơng pháp này gọi là liên kết hình thức. Mổi phƣơng pháp đều có những ƣu và khuyết điểm riêng. 163
Ở phƣơng pháp thứ nhất hệ thống biết đƣợc có bao nhiêu thƣ mục liên kết với tập tin nhờ vào chỉ số liên kết. Ở phƣơng pháp thứ hai khi loại bỏ liên kết hình thức, tập tin không bị ảnh hƣởng. Hình 9.5 11.4. Quản lý đĩa Tập tin đƣợc lƣu trữ trên đĩa, do đó việc quản trị đĩa là hết sức quan trọng trong việc cài đặt hệ thống tập tin. Có hai phƣơng pháp lƣu trữ : một là chứa tuần tự trên n byte liên tiếp, hai là tập tin đƣợc chia làm thành từng khối. Cách thứ nhất không hiệu quả khi truy xuất những tập tin có kích thƣớc lớn, do đó hầu hết các hệ thống tập tin đều dùng khối có kích thƣớc cố định. 164
11.5. Kích thƣớc khối Một vấn đề đặt ra là kích thƣớc khối phải bằng bao nhiêu. Điều này phụ thuộc vào tổ chức của đĩa nhƣ số sector, số track, số cylinder. Nếu dùng một cylinder cho một khối cho một tập tin thì theo tính toán sẽ lãng phí đến 97% dung lƣợng đĩa. Nên thông thƣờng mỗi tập tin thƣờng đƣợc lƣu trên một số khối. Ví dụ một đĩa có 32768 byte trên một track, thời gian quay là 16.67 msec, thời gian tìm kiếm trung bình là 30 msec thì thời gian tính bằng msec để đọc một khối kích thƣớc k byte là : 30 + 8.3 + (k/32768) x 16.67 Từ đó thống kê đƣợc kích thƣớc khối thích hợp phải < 2K . Thông thƣờng kích thƣóc khối là 512, 1K hay 2K. 11.6. Lƣu giữa các khối trống Có hai phƣơng pháp. Một là sử dụng danh sách liên kết của khối đĩa. Mỗi khối chứa một số các địa chỉ các khối trống. Ví dụ một khối có kích thƣớc 1 K có thể lƣu trữ đƣợc 511 địa chỉ 16 bit. Một đĩa 20M cần khoảng 40 khối. Hai là, sử dụng bitmap. Một đĩa n khối sẽ đƣợc ánh xạ thành n bit với giá trị 1 là còn trống, giá trị 0 là đã lƣu dữ liệu. Nhƣ vậy một đĩa 20M cần 20K bit để lƣu trữ nghĩa là chỉ có khoảng 3 khối. Phƣơng pháp thứ hai này thƣờng đƣợc sử dụng hơn. 165
11.7. Độ an toàn của hệ thống tập tin Một hệ thống tập tin bị hỏng còn nguy hiểm hơn máy tính bị hỏng vì những hƣ hỏng trên thiết bị sẽ ít chi phí hơn là hệ thống tập tin vì nó ảnh hƣởng đến các phần mềm trên đó. Hơn nữa hệ thống tập tin không thể chống lại đƣợc nhƣ hƣ hòng do phần cứng gây ra, vì vậy chúng phải cài đặt một số chức năng để bảo vệ. 11.7.1. Quản lý khối bị hỏng Đĩa thƣờng có những khối bị hỏng trong quá trình sử dụng đặc biệt đối với đĩa cứng vì khó kiểm tra đƣợc hết tất cả. Có hai giải pháp : phần mềm và phần cứng. Phần cứng là dùng một sector trên đĩa để lƣu giữ danh sách các khối bị hỏng. Khi bộ kiểm soát tực hiện lần đầu tiên, nó đọc những khối bị hỏng và dùng một khối thừa để lƣu giữ. Từ đó không cho truy cập những khối hỏng nữa. Phần mềm là hệ thống tập tin xây dựng một tập tin chứa các khối hỏng. Kỹ thuật này loại trừ chúng ra khỏi danh sách các khối trống, do đó nó sẽ không đƣợc cấp phát cho tập tin. 11.8. Backup 166
Mặc dù có các chiến lƣọc quản lý các khối hỏng, nhƣng một công việc hết sức quan trọng là phải backup tập tin thƣờng xuyên. Tập tin trên đĩa mềm đƣợc backup bằng cách chép lại toàn bộ qua một đĩa khác. Dữ liệu trên đĩa cứng nhỏ thì đƣợc backup trên các băng từ. Đối với các đĩa cứng lớn, việc backup thƣờng đƣợc tiến hành ngay trên nó. Một chiến lƣợc dể cài đặt nhƣng lãng phí một nữa đĩa là chia đĩa cứng làm hai phần một phần dữ liệu và một phần là backup. Mỗi tối, dữ liệu từ phần dữ liệu sẽ đƣợc chép sang phần backup. Hình 9.7:Backup 11.9. Tính không đổi của hệ thống tập tin Một vấn đề nữa về độ an toàn là tính không đổi. Khi truy xuất một tập tin, trong quá trình thực hiện, nếu có xảy ra những sự cố làm hệ thống ngừng hoạt động đột ngột, lúc đó hàng loạt thông tin chƣa đƣợc cập nhật lên đĩa. Vì vậy mỗi lân khởi động ,hệ thống sẽ thực hiện việc kiểm tra trên hai phần khối và tập tin. Việc kiểm tra thực hiện , khi phát hiện ra lỗi sẽ tiến hành sữa chữa cho các trƣờng hợp cụ thể: 167
Hình 9.8 Trạng thái của hệ thống tập tin 11.10. Câu hỏi kiểm tra kiến thức 1. Vai trò của bảng thƣ mục tập tin 2. So sánh các phƣơng pháp cài đặt bảng phân phối vùng nhớ. 3. Tập tin chia sẻ là gì ? 4. Vì sao phải lƣu ý đến độ an toàn của hệ thống tập tin ? 11.11. Bài tập 168
Giả sử một đĩa mềm có 2 side, mỗi side có 128 track, mỗi track có 18 sector. Thƣ mục gốc của đĩa có tối đa là 251 tập tin (hoặc thƣ mục), mỗi entry có kích thƣớc 32 bytes. Một cluster = 2 sector. Đĩa sử dụng phƣơng pháp định bằng bảng chỉ mục mỗi phần tử trong bảng có kích thƣớc 12 bits. Hỏi muốn truy xuất cluster 10 thì phải đọc những sector nào ? 169
CHƢƠNG 12. GIỚI THIỆU MỘT SỐ HỆ THỐNG TẬP TIN Trong bài học này chúng ta sẽ tìm hiểu các phƣơng pháp tổ chức quản lý tập tin của một số hệ điều hành sau: MS-DOS Windows 95 Windows NT Unix Bài học này giúp chúng ta hiểu đƣợc cách một số hệ điều hành thông dụng quản lý tập tin nhƣ thế nào. Bài học này đòi hỏi những kiến thức từ hai bài học trƣớc. 12.1. MS-DOS 12.1.1. Đặc điểm Hệ thống tập tin của MS-DOS bắt nguồn từ hệ thống tập tin của hệ điều hành CP/M. Nó có những đặc điểm nhƣ sau : Hệ thống cây thƣ mục. Khái niệm thƣ mục hiện hành. Đƣờng dẫn tƣơng đối và đƣờng dẫn tuyệt đối Thƣ mục “.” và “ ”. Có tập tin thiết bị và tập tin khối. Tên tập tin 8+3. Đƣờng dẫn \. Không phân biệt chữ thƣờng và chữ hoa.Không có khái niệm ngƣời sở hữu. Không có khái niệm nhóm và bảo vệ. Không có liên kết. Không có mount hệ thống tập tin. Có thuộc tính của tập tin. 12.1.2. Cài đặt Cài đặt trên đĩa mềm cũng tƣơng tự nhƣ trên đĩa cứng, những trên đĩa cứng phức tạp hơn. Phần này khảo sát trên đĩa cứng. Lúc đó, hệ điều hành MS-DOS đƣợc cài đặt trên một partition. Sector đầu tiên của partition là bootsector. Sau bootsector là FAT (File Allocation Table), lƣu giữ tất cả không gian trên đĩa theo phƣơng pháp danh sách liên kết có chỉ mục. Thông thƣờng có từ hai FAT trở lên để phòng hờ. Mỗi entry của FAT quản lý một khối (còn gọi là cluster đƣợc đánh số bắt đầu từ 2) trên đĩa. Kích thƣớc khối đƣợc lƣu trong bootsector thông thƣờng từ 1 đến 8 sector. Có hai loại FAT là FAT 12 và FAT 16. FAT 12 có thể quản lý đƣợc 4096 khối còn FAT 16 có thể quản lý 64 K khối trên một partition. 170
Giá trị trong mỗi phần tử (entry) có ý nghĩa nhƣ sau : Có một ánh xạ một một giữa entry và khối ngoại trừ hai entry đầu tiên, dùng cho đĩa. Khi hệ thống mở một tập tin, MS-DOS tìm trong bảng mô tả tập tin trong PSP, sau đó kiểm tra tên tập tin xem có phải là con, lpt, tiếp theo kiểm tra các đƣờng dẫn để xác định vị trí trong bảng thƣ mục. 171
Hình 10.2 Một entry thƣ mục trong MS-DOS Bảng thƣ mục nằm ngay sau FAT, và mỗi entry là 32 byte. Mƣời một byte đầu tiên mô tả tên và phần mở rộng(không lƣu trữ dấu chấm phân cách). Sau đó là byte thuộc tính, với giá trị : 1 : tập tin chỉ đọc 2 : tập tin ẩn 4 : tập tin hệ thống 8 : nhãn đĩa 16 : thƣ mục con 32 : tập tin chƣa backup Byte thuộc tính có thể đƣợc đọc ghi trong quá trình sử dụng. Tiếp theo là 10 byte trống dàng riêng sử dụng sau này. Sau đó là 4 byte lƣu trữ giờ, ngày với 6 bit cho giây, 4 bit cho giờ, 5 bit cho ngày, 4 bit cho tháng và 7 bit cho năm (từ 1980). Hai byte kế tiếp chứa số hiệu của khối đầu tiên (khối trong MS-DOS còn đƣợc gọi là cluster) và bốn byte sau cùng lƣu trữ kích thƣớc của tập tin. Ví dụ :Trên đĩa 1.44Mb, đƣợc format dƣới hệ điều hành MS-DOS gồm có 2880 sector: 172
Sector đầu tiên là bootsector, bao gồm bảng tham số vật lý của đĩa và chƣơng trình khởi động của hệ điều hành (nếu có). 18 sector tiếp theo là FAT (FAT12), gồm 2 bảng, mỗi bảng 9 sector. Ba bytes đầu tiên của FAT lƣu số hiệu loại đĩa.(240, 255, 255). 14 sector kế tiếp chứa bảng thƣ mục còn gọi là root directory entry table(RDET) Các sector còn lại dùng để lƣu dữ liệu (1 cluser = 1 sector). 12.2. Windows95 12.2.1. Bộ quản lý cài đặt hệ thống tập tin (IFS) Hệ thống tập tin của Windows 95 là 32-bit và cho phép những hệ thống tập tin khác sử dụng đƣợc trên hệ thống này. Nó cũng làm cho máy tính nhanh hơn và linh hoạt hơn, có nghĩa là bạn có nhiều vùng hơn để cô lập xử lý các vấn đề. Bộ quản lý IFS quản lý các thao tác bên trong của hệ thống tập tin đƣợc cài đặt. Các thành phần của IFS bao gồm IFSHLP.SYS và IFSMGR.VXD. Trong Windows 95, hệ thống tập tin là một thành phần của ring 0 của hệ điều hành. Sau đây là các bƣớc cài đặt của hệ thống tập tin trong Windows 95 : VFAT- Bảng định vị file ảo cho truy cập file 32-bit. CDFS- hệ thống tập tin của CD-ROM (thay thế MSCDEX) Bộ định hƣớng lại-Sử dụng cho truy xuất mạng. 173
Ngƣời sử dụng cũng có thể cài đặt hệ thống tập tin khác. Ví dụ hệ thống tập tin cài đặt trên hệ thống Windows 95 có thể xử lý trên những hệ thống tập tin trên những hệ điều hành khác nhƣ Macintosh hay UNIX. Bộ quản lý IFS quản lý vận chuyển nhập xuất tập tin cho chế độ bảo vệ của bộ định hƣớng lại, mode bảo vệ của server, VFAT, CDFS, và hệ thống tập tin của MS-DOS. Những hệ thống khác có thể đƣợc thêm vào trong tƣơng lai.VFAT VFAT là hệ thống tập tin FAT MS-DOS ảo 32 bit cung cấp truy xuất 32 bit cho Windows 95. VFAT.VXD là driver điều khiển quá trình ảo hóa và sử dụng mã 32 bit cho tất cả các truy xuất tập tin. VFAT chỉ cung cấp truy xuất ảo cho những volume đĩa cứng có các thành phần truy xuất đĩa 32 bit đƣợc cài đặt. Những dạng volume khác sẽ có cài đặt hệ thống tập tin cho chính nó. Ví dụ hệ thống tập tin của CD-ROM là CDFS. VFAT ảo hóa đĩa và sử dụng mã 32 bit để truy xuất tập tin. Bộ quản trị nhập/xuất đƣợc cài đặt từ Win 311 là *KHỐIDEV. Bộ quản trị nhập/xuất của Windows 95 cung cấp *KHỐIDEV những dịch vụ cho những driver FastDisk cũ. Ngoài ra nó có những chức năng sau : Đăng ký driver. Gửi và lập hàng đợi cho yêu cầu nhập/xuất 174
Gửi những thông báo đến driver khi cần thiết. Cung cấp những dịch vụ cho driver để định vị bộ nhớ và hoàn tất yêu cầu nhập/xuất.Theo dõi volume luôn hiện hữu khi có một thiết bị thông tin có thể đƣợc loại bỏ. Nó có trách nhiệm đảm bảo rằng thông tin đúng với thiết bị cũng nhƣ là kiểm tra và báo cáo những thông tin không thích hợp đƣợc loại bỏ hay chèn vào. Nó thực hiện theo hai cách : Đối với đĩa không bảo vệ, theo dõi volume sẽ ghi một ID duy nhất vào đầu FAT của đĩa. ID này khác với số serial của volume. Trên đĩa có bảo vệ, theo dõi volume lƣu trữ nhãn đĩa, số serial và khối tham số của BIOS. 12.2.2. Bộ điều khiển mô tả kiểu (TSD) TSD làm việc với những thiết bị đƣợc mô tả. Ví dụ, đĩa mềm và cứng là một kiểu điều khiển nhƣng đĩa CD là kiểu khác. TSD lam cho các yêu cầu nhập/xuất có hiệu lực, chuyển đổi những yêu cầu logic thành yêu cầu vật lý, và thông báo khi yêu cầu đã hoàn tất. Có thể xem TSD nhƣ một bộ dịch giữa bộ điều khiển vật lý và bộ quản trị nhập/xuất. a. VCACHE Vcache là vùng bộ nhớ mode bảo vệ đƣợc sử dụng bởi các bộ điều khiển hệ thống tập tin ở chế độ bảo vệ (ngoại trừ CDFS) : VFAT, VREDIR, NWREDIR. VCACHE đƣợc cài đặt tƣơng tự nhƣ Win 3.11. Bộ điều khiển này thay thế cho phần mềm SMARTDrive disk cache 16-bit ở mode thực của MS-DOS và Win3.1. Đặc điểm của VCACHE là thuật toán thông minh hơn SMARTDrive trong lƣu trữ thông tin nhập và xuất từ bộ điều khiển đĩa.VCACHE cũng quản lý vùng lƣu trữ cho CDFS và NWREDIR 32-bit. Việc sử dụng VCACHE là phụ thuộc với thiết bị. Ví dụ VCACHE dùng để truy xuất đĩa cứng khác với VCACE truy xuất CD-ROM. Tất cả bộ điều khiển hệ thống tập tin của Windows 95 trừ CDFS đều sử dụng mode bảo vệ để đọc buffer. CDFS cung cấp cơ chế riêng. VFAT dùng VCACHE để giảm bớt việc ghi. Bộ điều khiển cổng đƣợc thiết kế để cung cấp những truy xuất cho adapter. 175
b. SCSI Trong Windows 95, lớp SCSI là trung gian giữa lớp TSD và bộ điều khiển cổng. Có ba lớp SCSI đƣợc mô tả dƣới đây: Hình 10.5 c. Bộ dịch SCSI : Bộ dịch SCSI làm việc với tất cả những thiết bị SCSI nhƣ đĩa cứng, CD-ROM. Bộ dịch chịu trách nhiệm xây dựng khối mô tả lệnh SCSI cho những lớp của thiết bị SCSI và thực hiện tìm lỗi ở cấp thiết bị. d. Bộ quản trị SCSI : Bộ quản trị SCSI quản lý việc giao tiếp giữa bộ dịch SCSI và bộ điều khiển miniport. Bộ điều khiển cổng SCSI khởi động bộ điều khiển mimiport, chuyển đổi dạng yêu cầu nhập/xuất, thực hiện những thao tác giao tiếp với bộ điều khiển miniport. Khi liên kết với nó, bộ quản trị SCSI cung cấp cùng chức năng nhƣ Windows 95 chuẩn hoặc bộ điều khiển Fast Disk cũng nhƣ quan tâm đến những lớp cấp cao hơn. e. Bộ điều khiển miniport : 176
Làm việc với tập hợp những adapter SCSI đƣợc mô tả. Bộ điều khiển phụ thuộc vào những thủ tục lớp bên dƣới để khởi động adapter, quản lý ngắt, chuyển những yêu cầu nhập/xuất cho thiết bị, và thực hiện những khôi phục lỗi ở mức adapter. Khi kết hợp với bộ quản lý SCSI, nó cung cấp cùng những chức năng nhƣ bộ điều khiển cổng chuẩn của Windows 95. Bộ ánh xạ chƣơng trình giao tiếp SCSI cao cấp (ASPI) của Windows 95 là APIX.VXD, cung cấp hỗ trợ mode bảo vệ cho những thiết bị và chƣơng trình cần giao tiếp ASPI. Bộ quản lý ASPI cung cấp những giao tiếp giữa bộ điều khiển thiết bị và adapter chuẩn và thiết bị SCSI đƣợc nối trên adapter chủ. Bộ điều khiển ASPI gọi bộ quản trị ASPI. Bộ quản trị ASPI chuyển lời gọi cho CDB (Command Descriptor Khối) gọi tới những thành phần SCSI. Bộ quản trị ASPI cần thiết cho những trƣờng hợp sau đây : Nhiều adapter chủ. Đĩa cứng SCSI với SCSI ID khác 0 hay 1. SCSI tape, máy in, máy vẽ, máy quét.CDFS 177
CDFS thay thế cho VFAT trong điều khiển thiết bị CD-ROM. Chức năng của CDFS tƣơng tự nhƣ VFAT cho đĩa cứng. Các thành phần khác đều tƣơng thích với version của CD-ROM. Một yêu cầu nhập/xuất tập tin trên CD-ROM đƣợc thực hiện bởi một trong bốn cách sau Bộ điều khiển IDE hỗ trợ mode bảo vệ : ESDI_506.PDR. Bộ điều khiển SCSI hỗ trợ bộ điều khiển miniport mode bảo vệ. Bộ điều khiển ƣu tiên hỗ trợ những bộ điều khiển ở mode bảo vệ đƣợc liệt kê trong tập tin ADAPTER.INF. Bộ điều khiển thiết bị CD-ROM ở mode thực sử dụng FAT MS-DOS và MSCDEX nhƣ hệ thống tập tin mở rộng CD-ROM cho FAT. CDFS sử dụng bộ lƣu trữ chia sẻ với VCACHE. 12.2.3. Hỗ trợ tên tập tin dài :(LFN) Windows 95 cho phép đặt tên tập tin dài không còn bị giới hạn bởi 8.3 nữa. Tuy nhiên, mỗi lần tạo(LFN), một tên 8.3 đƣợc tự động gán cho nó.Một LFN có thể có tới 256 ký tự bao gồm luôn cả khoảng trắng. Đƣờng dẫn có thể lên đến 260 ký tự. Việc gán tên 8.3 cho LFN theo quy tắc sau : Bỏ tất cả những ký tự đặc biệt sau : \ ? : * “ | 178
Lấy 6 ký tự đầu tiên của LFN thêm dấu ~ và một số bắt đầu từ 1 đến 9, nếu không đủ thì chỉ lấy 5 ký tự với số từ 10 đến 99 v.v Đối với phần mở rộng, sử dụng 3 ký tự hợp lệ đầu tiên sau dấu chấm cuối cùng. Nếu không có dấu chấm thì không có phần mở rộng. Khi sao chép tập tin dƣới MS-DOS, LFN sẽ mất đi, chỉ còn lại tên 8.3 mà thôi. Nếu tập tin đƣợc tạo dƣới MS-DOS thì LFN cũng chính là tên đó. Cũng có thể sử dụng LFN trong ứng dụng MS-DOS nhƣng khi đó, tên tập tin phải đƣợc đặt trong nháy kép. LFN sử dụng vùng dành riêng của FAT. Chƣơng trình dùng phần dành riêng của FAT để tìm kiếm thông tin LFN.Windowns NT Hệ điều hành WindowsNT hỗ trợ nhiều loại hệ thống tập tin bao gồm FAT trên MS- DOS và Windows95 và OS/2. Tuy nhiên nó cũng có hệ thống tập tin riêng, đó là NTFS. 12.2.4. Đặc điểm của NTFS NTFS là một hệ thống tập tin mạnh và linh động, những đặc điểm nổi bật là : Khả năng phục hồi An toàn Quản lý đƣợc đĩa dung lƣợng lớn và kích thƣớc tập tin lớn Quản lý hiệu quả. 12.2.5. Cấu trúc tập tin và volume của NTFS NTFS sử dụng những khái niệm sau : Sector, cluster, volume Cluster là đơn vị định vị cơ bản trong NTFS. Kích thƣớc tập tin tối đa trong NTFS là 232 cluster, tƣơng đƣơng 248 bytes. Sự tƣơng ứng giữa kích thƣớc volume và cluster nhƣ hình sau : 179
Cấu trúc volume của NTFS : Bao gồm bốn vùng. Vùng thứ nhất là các sector khởi động của partition (có thể đến 16 sectors) bao gồm các thông tin về cấu trúc của volume, cấu trúc của hệ thống tập tin cũng nhƣ những thông tin và mã nguồn khởi động. Vùng tiếp theo là bảng Master File (MFT) lƣu các thông tin về tất cả tập tin và thƣ mục trên volume NTFS này cũng nhƣ thông tin về các vùng trống. Sau vùng MFT là vùng các tập tin hệ thống có kích khoảng 1Mb bao gồm : MFT2 : bản sao của MFT Log file : thông tin về các giao tác dùng cho việc phục hồi. Cluster bitmap : biểu diễn thông tin lƣu trữ của các cluster Bảng định nghĩa thuộc tính : định nghĩa các kiểu thuộc tính hỗ trợ cho volume đó. MFT đƣợc tổ chức thành nhiều dòng. Mỗi dòng mô tả cho một tập tin hoặc một thƣ mục trên volume. Nếu kích thƣớc tập tin nhỏ thì toàn bộ nội dung của tập tin đƣợc lƣu trong dòng này. mỗi dòng cũng lƣu những thuộc tính cho tập tin hay thƣ mục mà nó quản lý. 180
Hình 10.10 Các kiểu thuộc tính của tập tin và thƣ mục của Windows NTFSUnix 12.3. Hệ thống tập tin của Unix : Một tập tin đƣợc mở với lời gọi hệ thống OPEN, với tham số đầu tiên cho biết đƣờng dẫn và tên tập tin , tham số thứ hai cho biết tập tin đƣợc mở để đọc, ghi hay vừa đọc vừa ghi. Hệ thống kiểm tra xem tập tin có tồn tại không. Nếu có, nó kiểm tra bit quyền để xem có đƣợc quyền truy cập không, nếu có hệ thống sẽ trả về một số dƣơng nhỏ gọi là biến mô tả tập tin cho nơi gọi. Nếu không nó sẽ trả về –1. Khi một tiến trình bắt đầu, nó luôn có ba giá trị của biến mô tả tập tin : 0 cho nhập chuẩn, 1 cho xuất chuẩn và 2 cho lỗi chuẩn. Tập tin đƣợc mở đầu tiên sẽ có giá trị là 3 và sau đó là 4 Khi tập tin đóng, biến mô tả tập tin cũng đƣợc giải phóng. Có hai cách mô tả tên tập tin trong UNIX. Cách thứ nhất là dùng đƣờng dẫn tuyệt đối, tập tin đƣợc truy cập từ thƣ mục gốc. Thứ hai là dùng khái niệm thƣ mục làm việc hay thƣ mục hiện hành trong đƣờng dẫn tƣơng đối. UNIX cung cấp đặc tính LINK, cho phép nhiều ngƣời sử dụng cùng dùng chung một tập tin, hay còn gọi là chia sẻ tập tin. Ví dụ nhƣ hình sau, fred và lisa cùng làm việc trong cùng một đề án, họ cần truy cập tập tin lẫn nhau. Giả sử fred cần truy cập tập 181
tin x của lisa, anh ta sẽ tạo một entry mới trong thƣ mục của anh ta và sau đó có thể dùng x với nghĩa là /usr/lisa/x. Ngoài ra UNIX cho phép một đĩa có thể đƣợc mount thành một thành phần của hệ thống cây thƣ mục của một đĩa khác. 182
Một đặc tính thú vị khác của hệ thống tập tin của UNIX là khóa (locking). Trong một số ứng dụng, một số tiến trình có thể sử dụng cùng một tập tin cùng lúc. Có hai loại khóa là chia sẻ hay loại trừ. Nếu tập tin đã chứa khóa chia sẻ thì có thể đặt thêm một khóa chia sẻ nữa, nhƣng không thể đặt một khoá loại trừ nhƣng nếu đã đƣợc đặt khóa loại trừ thì không thể đặt thêm khóa nữa. Vùng khóa có thể đƣợc ghi chồng. 12.3.1. Cài đặt hệ thống tập tin của Unix Hệ thống tập tin của UNIX thông thƣờng đƣợc cài đặt trên đĩa nhƣ ở hình sau : Khối 0 thƣờng chứa mã khởi động của hệ thống. Khối 1 gọi là khối đặc biệt (super block), nó lƣu giữ các thông tin quan trọng về toàn bộ hệ thống tập tin, bao gồm: Kích thƣớc của toàn bộ hệ thống tập tin. Địa chỉ của khối dữ liệu đầu tiên.Số lƣợng và danh sách các khối còn trống. Số lƣợng và danh sách các I-node còn trống. Ngày super block đƣợc cập nhật cuối cùng. Tên của hệ thống tập tin. Nếu khối này bị hỏng, hệ thống tập tin sẽ không truy cập đƣợc. Có rất nhiều trình ứng dụng sử dụng thông tin lƣu trữ trong super block. Vì vậy một bản sao super block của hệ thống tập tin gốc đƣợc đặt trong RAM để tăng tốc độ truy xuất đĩa. Việc cập nhật super block sẽ đƣợc thực hiện ngay trong RAM và sau đó mới ghi xuống đĩa. Sau khối đặc biệt là các I-node, đƣợc đánh số từ một cho tới tối đa. Mỗi I-node có độ dài là 64 byte và mô tả cho một tập tin duy nhất (chứa thuộc tính và địa chỉ khối lƣu trữ trên đĩa của tập tin). Sau phần I-node là các khối dữ liệu. Tất cả tập tin và thƣ mục đều đƣợc lƣu trữ ở đây. Một entry của directory có 16 byte, trong đó 14 byte là tên của tập tin và 2 byte là địa chỉ của I-node. Để mở một tập tin trong thƣ mục làm việc, hệ thống chỉ đọc thƣ mục, so sánh tên đƣợc tìm thấy trong mỗi entry cho đến khi tìm đƣợc, từ đó xác định đƣợc chỉ số I-node và đƣa vào bộ nhớ để truy xuất. 183
Tập tin đƣợc tạo hay tăng kích thƣớc bằng cách sử dụng thêm các khối từ danh sách các khối còn trống. Ngƣợc lại, khối đƣợc giải phóng sẽ trả về danh sách khối trống khi xóa tập tin. Super block sẽ chứa địa chỉ của 50 khối trống. Trong đó địa chỉ cuối cùng chứa địa chỉ của một khối chứa địa chỉ của 50 khối trống kế tiếp và cứ tiếp tục nhƣ thế. Unix sử dụng khối trống trong super block trƣớc. Khi khối trống cuối cùng trong super block đƣợc sử dụng, 50 khối trống kế tiếp sẽ đƣợc đọc vào trong super block. Ngƣợc lại, khi một khối đƣợc giải phóng, địa chỉ của nó sẽ đƣợc thêm vào danh sách của super block. Khi đã đủ 50 địa chỉ trong super block, khối trống kế tiếp sẽ đƣợc dùng để lƣu trữ 50 địa chỉ khối trống đang đặt trong super block thay cho super block. 12.4. Bài tập Bài 1 : Cho dãy byte của FAT12 nhƣ sau (bắt đầu từ đầu): Cho biết những phần tử nào của FAT có giá trị đặc biệt, ý nghĩa của phần tử đó. Nếu sửa lại phần tử 5 là FF0 thì dãy byte của FAT12 này có nội dung nhƣ thế nào ? Bài 2:Biết giá trị(dƣới dạng thập phân) trong một buffer (mỗi phần tử 1 byte) lƣu nội dung của FAT12 nhƣ sau (bắt đầu từ phần tử 0): Cho biết giá trị của từng phần tử trong FAT (dƣới dạng số thập phân) Bài 3: Chép 1 tập tin kích thƣớc là 3220 bytes lên một đĩa 1.44Mb còn trống nhƣng bị hỏng ở sector logic 33. Cho biết giá trị từng byte của Fat (thập phân) từ byte 0 đến byte 14 . Bài 4 :Giả sử một đĩa mềm có 2 side, mỗi side có 128 track, mỗi track có 18 sector. Thƣ mục gốc của đĩa có tối đa là 251 tập tin (hoặc thƣ mục). Một cluster = 2 sector. Đĩa sử dụng Fat 12. Hỏi muốn truy xuất cluster 10 thì phải đọc những sector nào ? Bài 5 :Hiện trạng của FAT12 và RDET (mỗi entry chỉ gồm tên tập tin và cluster đầu tiên)của một đĩa nhƣ sau : 184
Cho biết hiện trạng của FAT12 và RDET sau khi xoá tập tin vd.txt và chép vào tập tin bt.cpp có kích thƣớc 1025 bytes ( giả sử 1 cluster = 1 sector) Bài 6 :Một tập tin đƣợc lƣu trên đĩa tại những khối theo thứ tự sau : 20, 32, 34, 39, 52, 63, 75, 29, 37, 38, 47, 49, 56, 68, 79, 81, 92, 106, 157, 159, 160, 162, 163, 267, 269, 271, 277, 278, 279, 380, 381, 482, 489, 490, 499. Vẽ I_node của tập tin này, giả sử mỗi khối chỉ chứa đƣợc 3 phần tử. 185
CHƢƠNG 13. HỆ THỐNG QUẢN LÝ NHẬP-XUẤT Một trong những chức năng chính của hệ điều hành là quản lý tất cả những thiết bị nhập/xuất của máy tính. Hệ điều hành phải ra các chỉ thị điều khiển thiết bị, kiểm soát các ngắt và lỗi. Hệ điều hành phải cung cấp một cách giao tiếp đơn giản và tiện dụng giữa các thiết bị và phần còn lại của hệ thống và giao tiếp này phải độc lập với thiết bị. Trong bài này chúng ta tìm hiểu hệ điều hành quản lý nhập/xuất nhƣ thế nào với những nội dung sau: Khái niệm về hệ thống nhập/ xuất Phần cứng nhập / xuất Phần mềm nhập / xuất Qua bài học này, chúng ta hiểu đƣợc cơ chế quản lý nhập/xuất của hệ điều hành một cách tổng quát. Từ đó chúng ta có thể hiểu rõ hơn quá trình nhập xuất diễn ra trên máy tính thông qua hệ điều hành nhƣ thế nào. Bài học này cũng giúp cho việc tìm hiểu cơ chế tƣơng tác giữa hệ điều hành và các thiết bị nhập/xuất cụ thể(đƣợc đề cập trong bài học sau) dễ dàng hơn. Bài học này đòi hỏi những kiến thức về : kiến trúc máy tính, cơ chế ngắt trên máy tính. 13.1. KHÁI NIỆM VỀ HỆ THỐNG QUẢN LÝ NHẬP/XUẤT Hệ thống quản lý nhập/xuất đƣợc tổ chức theo từng lớp, mỗi lớp có một chức năng nhất định và các lớp có giao tiếp với nhau nhƣ sơ đồ sau : 186
Ví dụ: Trong một chƣơng trình ứng dụng, ngƣời dùng muốn đọc một khối từ một tập tin, hệ điều hành đƣợc kích hoạt để thực hiện yêu cầu này. Phần mềm độc lập thiết bị tìm kiếm trong cache, nếu khối cần đọc không có sẵn, nó sẽ gọi chƣơng trình điều khiển thiết bị gửi yêu cầu đến phần cứng. Tiến trình bị ngƣng lại cho đến khi thao tác đĩa hoàn tất. Khi thao tác này hoàn tất, phần cứng phát sinh một ngắt. Bộ phận kiểm soát ngắt kiểm tra biến cố này, ghi nhận trạng thái của thiết bị và đánh thức tiến trình bị ngƣng để chấm dứt yêu cầu I/O và cho tiến trình của ngƣời sử dụng tiếp tục thực hiện.[TAN] 13.2. Phần cứng nhập-xuất Có nhiều cách nhìn khác nhau về phần cứng nhập/xuất. Các kỹ sƣ điện tử thì nhìn dƣới góc độ là các thiết bị nhƣ IC, dây dẫn, bộ nguồn, motor v.v .Các lập trình viên thì nhìn chúng dƣới góc độ phần mềm - những lệnh nào thiết bị chấp nhận, chúng sẽ thực hiện những chức năng nào, và thông báo lỗi của chúng bao gồm những gì, nghĩa là chúng ta quan tâm đến lập trình thiết bị chứ không phải các thiết bị này hoạt động nhƣ thế nào mặc dù khía cạnh này có liên quan mật thiết với các thao tác bên trong của chúng. Phần này chúng ta đề cập đến một số khái niệm về phần cứng I/O liên quan đến khía cạnh lập trình. 13.2.1. Thiết bị I/O Các thiết bị nhập xuầt có thể chia tƣơng đối thành hai loại là thiết bị khối và thiết bị tuần tự. Thiết bị khối là thiết bị mà thông tin đƣợc lƣu trữ trong những khối có kích thƣớc cố định và đƣợc định vị bởi địa chỉ. Kích thƣớc thông thƣờng của một khối là khoảng từ 128 bytes đến 1024 bytes. Đặc điểm của thiết bị khối là chúng có thể đƣợc truy xuất (đọc hoặc ghi) từng khối riêng biệt, và chƣơng trình có thể truy xuất một khối bất kỳ nào đó. Đĩa là một ví dụ cho loại thiết bị khối. Một dạng thiết bị thứ hai là thiết bị tuần tự. Ở dạng thiết bị này, việc gửi và nhận thông tin dựa trên là chuỗi các bits, không có xác định địa chỉ và không thể thực hiện thao tác seek đƣợc. Màn hình, bàn phím, máy in, card mạng, chuột, và các loại thiết bị khác không phải dạng đĩa là thiết bị tuần tự. 187
Việc phân chia các lớp nhƣ trên không hoàn toàn tối ƣu, một số các thiết bị không phù hợp với hai lớp trên, ví dụ : đồng hồ, bộ nhớ màn hình v.v không thực hiện theo cơ chế tuần tự các bits. Ngoài ra, ngƣời ta còn phân loại các thiết bị I/O dƣới một tiêu chuẩn khác : Thiết bị tƣơng tác đƣợc với con ngƣời : dùng để giao tiếp giữa ngƣời và máy. Ví dụ : màn hình, bàn phím, chuột, máy in Thiết bị tƣơng tác trong hệ thống máy tính là các thiết bị giao tiếp với nhau. Ví dụ : đĩa, băng từ, card giao tiếp Thiết bị truyền thồng : nhƣ modem Những điểm khác nhau giữa các thiết bị I/O gồm :Tốc độ truyền dữ liệu , ví dụ bàn phím : 0.01 KB/s, chuột 0.02 KB/s Công dụng. Đơn vị truyền dữ liệu (khối hoặc ký tự). Biểu diễn dữ liệu, điều này tùy thuộc vào từng thiết bị cụ thể. Tình trạng lỗi : nguyên nhân gây ra lỗi, cách mà chúng báo về 13.2.2. Tổ chức của chức năng I/O Có ba cách để thực hiện I/O : Một là, bộ xử lý phát sinh một lệnh I/O đến các đơn vị I/O, sau đó, nó chờ trong trạng thái “busy” cho đến khi thao tác này hoàn tất trƣớc khi tiếp tục xử lý. Hai là, bộ xử lý phát sinh một lệnh I/O đến các đơn vị I/O, sau đó, nó tiếp tục việc xử lý cho tới khi nhận đƣợc một ngắt từ đơn vị I/O báo là đã hoàn tất, nó tạm ngƣng việc xử lý hiện tại để chuyển qua xử lý ngắt. Ba là, sử dụng cơ chế DMA (nhƣ đƣợc đề cập ở sau) Các bƣớc tiến hóa của chức năng I/O : Bộ xử lý kiểm soát trực tiếp các thiết bị ngoại vi. Hệ thống có thêm bộ điều khiển thiết bị. Bộ xử lý sử dụng cách thực hiện nhập xuất thứ nhất. Theo cách này bộ xử lý đƣợc tách rời khỏi các mô tả chi tiết của các thiết bị ngoại vi. Bộ xử lý sử dụng thêm cơ chế ngắt. Sử dụng cơ chế DMA, bộ xử lý truy xuất những dữ liệu I/O trực tiếp trong bộ nhớ chính. 188
Bộ điều khiển thiết bị Một đơn vị bị nhập xuất thƣờng đƣợc chia làm hai thành phần chính là thành phần cơ và thành phần điện tử. Thành phần điện tử đƣợc gọi là bộ phận điều khiển thiết bị hay bộ tƣơng thích, trong các máy vi tính thƣờng đƣợc gọi là card giao tiếp. Thành phần cơ chính là bản thân thiết bị. Một bộ phận điều khiển thƣờng có bộ phận kết nối trên chúng để có thể gắn thiết bị lên đó. Một bộ phận điều khiển có thể quản lý đƣợc hai, bốn hay thậm chí tám thiết bị khácnhau. Nếu giao tiếp giữa thiết bị và bộ phận điều khiển là các chuẩn nhƣ ANSI, IEEE hay ISO thì nhà sản xuất thiết bị và bộ điều khiển phải tuân theo chuẩn đó, ví dụ : bộ điều khiển đĩa đƣợc theo chuẩn giao tiếp của IBM. Giao tiếp giữa bộ điều khiển và thiết bị là giao tiếp ở mức thấp. Chức năng của bộ điều khiển là giao tiếp với hệ điều hành vì hệ điều hành không thể truy xuất trực tiếp với thiết bị. Việc thông tin thông qua hệ thống đƣờng truyền gọi là bus. Công việc của bộ điều khiển là chuyển đổi dãy các bit tuần tự trong một khối các byte và thực hiện sửa chửa nếu cần thiết. Thông thƣờng khối các byte đƣợc tổ chức thành từng bit và đặt trong buffer của bộ điều khiển. Sau khi thực hiện checksum nội dung của buffer sẽ đƣợc chuyển vào bộ nhớ chính. Ví dụ : bộ điều khiển cho màn hình đọc các byte của ký tự để hiển thị trong bộ nhớ và tổ chức các tín hiệu để điều khiển các tia của CRT để xuất trên màn ảnh bằng cách quét các tia dọc và ngang. Nếu không có bộ điều khiển, lập trình viên hệ điều hành phải tạo thêm chƣơng trình điều khiển tín hiệu analog cho đèn hình. Với bộ điều khiển , hệ điều hành chỉ cần khởi động chúng với một số tham số nhƣ số ký tự trên một dòng, số dòng trên màn hình và bộ điều khiển sẽ thực hiện điều khiển các tia. 189
Mỗi bộ điều khiển có một số thanh ghi để liên lạc với CPU. Trên một số máy tính, các thanh ghi này là một phần của bộ nhớ chính tại một địa chỉ xác định gọi là ánh xạ bộ nhớ nhập xuất. Hệ máy PC dành ra một vùng địa chỉ đặc biệt gọi là địa chỉ nhập xuất và trong đó đƣợc chia làm nhiều đoạn, mỗi đoạn cho một loại thiết bị nhƣ sau : Hệ điều hành thực hiện nhập xuất bằng cách ghi lệnh lên các thanh ghi của bộ điều khiển. Ví dụ : bộ điều khiển đĩa mềm của IBMPC chấp nhận 15 lệnh khác nhau nhƣ : READ, WRITE, SEEK, FORMAT, RECALIBRATE, một số lệnh có tham số và các tham số cũng đƣợc nạp vào thanh ghi. Khi một lệnh đã đƣợc chấp nhận, CPU sẽ rời bộ điều khiển để thực hiện công việc khác. Sau khi thực hiện xong, bộ điều khiển phát sinh một ngắt để báo hiệu cho CPU biết và đến lấy kết quả đƣợc lƣu giữ trong các thanh ghi. 190
13.2.3. DMA (Direct Memory Access) Đa số các loại thiết bị, đặc biệt là các thiết bị dạng khối, hỗ trợ cơ chế DMA (direct memory access). Để hiểu về cơ chế này, trƣớc hết phải xem xét quá trình đọc đĩa mà không có DMA. Trƣớc tiên, bộ điều khiển đọc tuần tự các khối trên đĩa, từng bit từng bit cho tới khi toàn bộ khối đƣợc đƣa vào buffer của bộ điều khiển. Sau đó máy tính thực hiện checksum để đảm bảo không có lỗi xảy ra. Tiếp theo bộ điều khiển tạo ra một ngắt để báo cho CPU biết. CPU đến lấy dữ liệu trong buffer chuyển về bộ nhớ chính bằng cách tạo một vòng lặp đọc lần lƣợt từng byte. Thao tác này làm lãng phí thời gian của CPU. Do đó để tối ƣu, ngƣời ta đƣa ra cơ chế DMA. Cơ chế DMA giúp cho CPU không bị lãng phí thời gian. Khi sử dụng, CPU gửi cho bộ điều khiển một số các thông số nhƣ địa chỉ trên đĩa của khối, địa chỉ trong bộ nhớ nơi định vị khối, số lƣợng byte dữ liệu để chuyển.Sau khi bộ điều khiển đã đọc toàn bộ dữ liệu từ thiết bị vào buffer của nó và kiểm tra checksum. Bộ điều khiển chuyển byte đầu tiên vào bộ nhớ chính tại địa chỉ đƣợc mô tả bởi địa chỉ bộ nhớ DMA. Sau đó nó tăng địa chỉ DMA và giảm số bytes phải chuyển. Quá trình này lập cho tới khi số bytes phải chuyển bằng 0, và bộ điều khiển tạo một ngắt. Nhƣ vậy không cần phải copy khối vào trong bộ nhớ, nó đã hiện hữu trong bộ nhớ. 13.3. Phần mềm nhập xuất Mục tiêu chung của thiết bị logic là dể biểu diễn. Thiết bị logic đƣợc tổ chức thành nhiều lớp. Lớp dƣới cùng giao tiếp với phần cứng, lớp trên cùng giao tiếp tốt, thân thiện với ngƣời sử dụng. Khái niệm then chốt của thiết bị logic là độc lập thiết bị, ví dụ : có thể viết chƣơng trình truy xuất file trên đĩa mềm hay đĩa cứng mà không cần phải mô tả lại chƣơng trình cho từng loại thiết bị. Ngoài ra, thiết bị logic phải có 191
khả năng kiểm soát lỗi. Thiết bị logic đƣợc tổ chức thành bốn lớp : Kiểm soát lỗi, điều khiển thiết bị, phần mềm hệ điều hành độc lập thiết bị, phần mềm mức ngƣời sử dụng. 13.3.1. Kiểm soát ngắt Ngắt là một hiện tƣợng phức tạp. Nó phải cần đƣợc che dấu sâu trong hệ điều hành, và một phần ít của hệ thống biết về chúng. Cách tốt nhất để che dấu chúng là hệ điều hành có mọi tiến trình thực hiện thao tác nhập xuất cho tới khi hoàn tất mới tạo ra một ngắt. Tiến trình có thể tự khóa lại bằng cách thực hiện lệnh WAIT theo một biến điều kiện hoặc RECEIVE theo một thông điệp. Khi một ngắt xảy ra, hàm xử lý ngắt khởi tạo một tiến trình mới để xử lý ngắt. Nó sẽ thực hiện một tín hiệu trên biến điều kiện và gửi những thông điệp đến cho các tiến trình bị khóa. Tổng quát, chức năng của ngắt là làm cho một tiến trình đang bị khóa đƣợc thi hành trở lại. 13.3.2. Điều khiển thiết bị (device drivers) Tất cả các đoạn mã độc lập thiết bị đều đƣợc chuyển đến device drivers. Mỗi device drivers kiểm soát mỗi loại thiết bị, nhƣng cũng có khi là một tập hợp các thiết bị liên quan mật thiết với nhau. Device drivers phát ra các chỉ thị và kiểm tra xem chỉ thị đó có đƣợc thực hiện chính xác không. Ví dụ, driver của đĩa là phần duy nhất của hệ điều hành kiểm soát bộ điều khiển đĩa. Nó quản lý sectors, tracks, cylinders, head, chuyển động, interleave, và các thành phần khác giúp cho các thao tác đĩa đƣợc thực hiện tốt. Chức năng của device drivers là nhận những yêu cầu trừu tƣợng từ phần mềm nhập/xuất độc lập thiết bị ở lớp trên, và giám sát yêu cầu này thực hiện. Nếu driver đang rảnh, nó sẽ thực hiện ngay yêu cầu, ngƣợc lại, yêu cầu đó sẽ đƣợc đƣa vào hàng đợi. Ví dụ, bƣớc đầu tiên của yêu cầu nhập/xuất đĩa là chuyển từ trừu tƣợng thành cụ thể. Driver của đĩa phải biết khối nào cần đọc, kiểm tra sự hoạt động của motor đĩa, xác định vị trí của đầu đọc đã đúng chƣa v.v Nghĩa là device drivers phải xác định đƣợc những thao tác nào của bộ điều khiển phải thi hành và theo trình tự nào. Một khi đã xác định đƣợc chỉ thị cho bộ điều khiển, nó bắt đầu thực hiện bằng cách chuyển lệnh vào thanh ghi của bộ điều khiển thiết bị. Bộ điều khiển có thể nhận một hay nhiều chỉ thị liên tiếp và sau đó tự nó thực hiện không cần sự trợ giúp của hệ điều hành. Trong khi lệnh thực hiện. Có hai trƣờng hợp xảy ra : Một là device 192
drivers phải chờ cho tới khi bộ điều khiển thực hiện xong bằng cách tự khóa lại cho tới khi một ngắt phát sinh mở khóa cho nó. Hai là, hệ điều hành chấm dứt mà không chờ, vì vậy driver không cần thiết phải khóa. Sau khi hệ điều hành hoàn tất việc kiểm tra lỗi và nếu mọi thứ đều ổn driver sẽ chuyển dữ liệu cho phần mềm độc lập thiết bị. Cuối cùng nó sẽ trả về thông tin về trạng thái hay lỗi cho nơi gọi và nếu có một yêu cầu khác ở hàng đợi, nó sẽ thực hiện tiếp, nếu không nó sẽ khóa lại chờ đến yêu cầu tiếp theo. 13.4. Phần mềm nhập/xuất độc lập thiết bị Mặc dù một số phần mềm nhập/xuất mô tả thiết bị nhƣng phần lớn chúng là độc lập với thiết bị. Ranh giới chính xác giữa drivers và phần mềm độc lập thiết bị là độc lập về mặt hệ thống, bởi vì một số hàm mà đƣợc thi hành theo kiểu độc lập thiết bị có thể đƣợc thi hành trên drivers vì lý do hiệu quả hay những lý dó khác nào đó. Giao tiếp đồng nhất cho device drivers Đặt tên thiết bị Bảo vệ thiết bị Cung cấp khối độc lập thiết bị Tổ chức buffer Định vị lƣu trữ trên thiết bị khối Cấp phát và giải phóng thiết bị tận hiến Báo lỗi Chức năng cơ bản của phần mềm nhập/xuất độc lập thiết bị là những chức năng chung cho tất cả các thiết bị và cung cấp một giao tiếp đồng nhất cho phần mềm phạm vi ngƣời sử dụng. Trƣớc tiên nó phải có chức năng tạo một ánh xạ giữa thiết bị và một tên hình thức. Ví dụ đối với UNIX, tên /dev/tty0 dành riêng để mô tả I-node cho một file đặc biệt, và I-node này chứa chứa số thiết bị chính, đƣợc dùng để xác định driver thích hợp và số thiết bị phụ, đƣợc dùng để xác định các tham số cho driver để cho biết là đọc hay ghi. Thứ hai là bảo vệ thiết bị, là cho phép hay không cho phép ngƣời sử dụng truy xuất thiết bị. Các hệ điều hành có thể có hay không có chức năng này. Thứ ba là cung cấp khối dữ liệu độc lập thiết bị vì ví dụ những đĩa khác nhau sẽ có kích thƣớc sector khác nhau và điều này sẽ gây khó khăn cho các phần mềm ngƣời 193
sử dụng ở lớp trên. Chức năng này cung cấp các khối dữ liệu logic độc lập với kích thƣớc sector vật lý. Thứ tƣ là cung cấp buffer để hỗ trợ cho đồng bộ hóa quá trình hoạt động của hệ thống. Ví dụ buffer cho bàn phím. Thứ năm là định vị lƣu trữ trên các thiết bị khối. Thứ sáu là cấp phát và giải phóng các thiết bị tận hiến. Cuối cùng là thông báo lỗi cho lớp bên trên từ các lỗi do device driver báo về. 13.5. Phần mềm nhập/xuất phạm vi ngƣời sử dụng Hầu hết các phần mềm nhập/xuất đều ở bên trong của hệ điều hành và một phần nhỏ của chúng chứa các thƣ viện liên kết với chƣơng trình của ngƣời sử dụng ngay cả những chƣơng trình thi hành bên ngoài hạt nhân. Lời gọi hệ thống, bao gồm lời gọi hệ thống nhập/xuất thƣờng đƣợc thực hiện bởi các hàm thƣ viện. Ví dụ khi trong chƣơng trình C có lệnh count = write(fd, buffer, nbytes) ; Hàm thƣ viện write đƣợc địch và liên kết dƣới dạng nhị phân và nằm trong bộ nhớ khi thi hành. Tập hợp tất cả những hàm thƣ viện này rõ ràng là một phần của hệ thống nhập/ xuất. Không phải tất cả các phần mềm nhập/xuất đều chứa hàm thƣ viện, có một loại quan trọng khác gọi là hệ thống spooling dùng để khai thác tối đa thiết bị nhập/xuất trong hệ thống đa chƣơng. Các hàm thƣ viện chuyển các tham số thích hợp cho lời gọi hệ thống và hàm thƣ viện thực hiện việc định dạng cho nhập và xuất nhƣ lệnh printf trong C. Thƣ viện nhập/xuất chuẩn chứa một số hàm có chức năng nhập/xuất và tất cả chạy nhƣ chƣơng trình ngƣời dùng. Chức năng của spooling là tránh trƣờng hợp một tiến trình đang truy xuất thiết bị, chiếm giữ thiết bị nhƣng sau đó không làm gì cả trong một khoảng thời gian và nhƣ vậy các tiến trình khác bị ảnh hƣởng vì không thể truy xuất thiết bị đó. Một ví dụ củaspooling device là line printer. Spooling còn đƣợc sử dụng trong hệ thống mạng nhƣ hệ thống e-mail chẳng hạn. 194
CHƢƠNG 14. GIỚI THIỆU MỘT SỐ HỆ THỐNG I-O Cơ chế quản lý nhập/xuất(I/O) của hệ điều hành đƣợc minh họa cụ thể qua việc điều khiển các thiết bị I/O cụ thể. Trong bài này chúng ta tìm hiểu một số hệ thống I/O sau: Hệ thống nhập xuất đĩa Hệ thống nhập xuất chuẩn Cài đặt đồng hồ Qua bài học này, chúng ta hiểu đƣợc cơ chế quản lý nhập/xuất của hệ điều hành đƣợc thể hiện cụ thể trên một số thiết bị I/O. Chúng ta cũng nắm đƣợc cơ chế tƣơng tác giữa hệ điều hành với các thiết bị đó và trên hết chúng ta thấy đƣợc vai trò của độc lập thiết bị. Bài học này đòi hỏi những kiến thức về : kiến trúc máy tính, hệ thống quản lý I/O của hệ điều hành. 14.1. HỆ THỐNG I/O ĐĨA Hầu nhƣ tất cả các máy tính đều có đĩa để lƣu trữ thông tin. Đĩa có ba ƣu điểm chính hơn sử dụng bộ nhớ chính để lƣu trữ : Dung lƣợng lƣu trữ lớn hơn rất nhiều. Giá trên một bit rẻ hơn. Thông tin không bị mất đi khi không còn cung cấp điện. Phần cứng đĩa Một đĩa bao gồm nhiều cylinder, mỗi cylinder chứa nhiều track trên các head. Mỗi track đƣợc chia làm nhiều sector (từ 8 đến 32). Mỗi sector có số byte là nhƣ nhau dù vị trí của nó ở gần tâm hay ở ngoài rìa đĩa, những khoảng trống thừa không dùng đến. Một đặc điểm thiết bị cài đặt quan trọng cho driver của đĩa là khả năng của bộ điều khiển thực hiện tìm kiếm trên hai hay nhiều driver cùng lúc gọi là tìm kiếm chồng. Trong khi bộ điều khiển và phần mềm đợi việc tìm kiếm hoàn tất trên một đĩa, bộ điều khiển có thể khởi động việc tìm kiếm trên đĩa khác. Các bộ điều khiển không thể cùng lúc đọc hoặc ghi trên hai driver vì khả năng này có thể làm giảm thời gian truy xuất trung bình. 195
14.1.1. Các thuật toán đọc đĩa Tất cả mọi công việc đều phụ thuộc vào việc nạp chƣơng trình và nhập xuất tập tin, do đó điều quan trọng là dịch vụ đĩa phải càng nhanh càng tốt. Hệ điều hành có thể tổ chức dịch vụ truy xuất đĩa tốt hơn bằng cách lập lịch yêu cầu truy xuất đĩa. Tốc độ đĩa bao gồm ba phần. Để truy xuất các khối trên đĩa, trƣớc tiên phải di chuyển đầu đọc đến track hay cylinder thích hợp, thao tác này gọi là seek và thời gian để hoàn tất gọi là seek time. Một khi đã đến đúng track, còn phải chờ cho đến khi khối cần thiết đến dƣới đầu đọc. Thời gian chờ này gọi là latency time. Cuối cùng là vận chuyển dữ liệu giữa đĩa và bộ nhớ chính gọi là transfer time. Tổng thời gian cho dịch vụ đĩa chính là tổng của ba khoảng thời gian trên. Trong đó seek time và latency time là mất nhiều thời gian nhất, do đó để giảm thiểu thời gian truy xuất hệ điều hành đƣa ra các thuật toán lập lịch truy xuất. a. Lập lịch FCFS : Phƣơng pháp lập lịch đơn giản nhất là FCFS(first-come,first-served). Thuật toán này rất dể lập trình nhƣng không cung cấp đƣợc một dịch vụ tốt. Ví dụ : cần phải đọc các khối theo thứ tự nhƣ sau : 98, 183, 37, 122, 14, 124, 65, và 67 Giả sử hiện tại đầu đọc đang ở vị trí 53. Nhƣ vậy đầu đọc lần lƣợt đi qua các khối 53, 98, 183, 37, 122, 14, 124, 65, và 67 nhƣ hình sau : b. Lập lịch SSTF (shortest-seek-time-first) Thuật toán này sẽ di chuyển đầu đọc đến các khối cần thiết theo vị trí lần lƣợt gần với vị trí hiện hành của đầu đọc nhất. Ví dụ : cần đọc các khối nhƣ sau : 196
98, 183, 37, 122, 14, 124, 65, và 67Giả sử hiện tại đầu đọc đang ở vị trí 53. Nhƣ vậy đầu đọc lần lƣợt đi qua các khối 53, 65, 67, 37, 14, 98, 122, 124 và 183 nhƣ hình sau : Với ví dụ này, thuật toán SSTF làm giảm số khối mà đầu đọc phải di chuyển là 208 khối. c. Lập lịch SCAN Theo thuật toán này, đầu đọc sẽ di chuyển về một phía của đĩa và từ đó di chuyển qua phía kia. Ví dụ : cần đọc các khối nhƣ sau : 98, 183, 37, 122, 14, 124, 65, và 67 Giả sử hiện tại đầu đọc đang ở vị trí 53. Nhƣ vậy đầu đọc lần lƣợt đi qua các khối 53, 37, 14, 0 , 65, 67, 98, 122, 124 và 183 nhƣ hình sau : 197
Thuật toán này còn đƣợc gọi là thuật toán thang máy. Hình ảnh thuật toán giống nhƣ hình ảnh của một ngƣời quét tuyết, hay quét lá. d. Lập lịch C-SCAN Thuật toán này tƣơng tự nhƣ thuật toán SCAN, chỉ khác là khi nó di chuyển đến một đầu nào đó của đĩa, nó sẽ lập tức trở về đầu bắt đầu của đĩa. Lấy lại ví dụ trên, khi đó thứ tự truy xuất các khối sẽ là : 53, 65, 67, 98, 122, 124, 183, 199, 0, 14, 37 nhƣ hình sau : e. Lập lịch LOOK: Nhận xét rằng cả hai thuật toán lập lịch SCAN và C-SCAN luôn luôn chuyển đầu đọc của đĩa từ đầu này sang đầu kia. Nhƣng thông thƣờng thì đầu đọc chỉ chuyển đến khối xa nhất ở mỗi hƣớng chứ không đến cuối. Do đó SCAN và C-SCAN đƣợc chỉnh theo thực tế và gọi là lập lịch LOOK. Nhƣ hình sau : 198
14.1.2. Lựa chọn thuật toán lập lịch : Với những thuật toán lập lịch, vấn đề là phải lựa chọn thuật toán nào cho hệ thống. Thuật toán SSTF thì rất thông thƣờng. Thuật toán SCAN và C-SCAN thích hợp cho những hệ thống phải truy xuất dữ liệu khối lƣợng lớn. Với bất kỳ thuật toán lập lịch nào, điều quantrọng là khối lƣợng về số và kiểu khối cần truy xuất. Ví dụ , nếu số khối cần truy xuất là liên tục thì FCFS là thuật toán tốt. a. Quản lý lỗi Đĩa là đối tƣợng mà khi truy xuất có thể gây nhiều lỗi. Một trong số các lỗi thƣờng gặp là : Lỗi lập trình : yêu cầu đọc các sector không tồn tại. Lỗi lập trình xảy ra khi yêu cầu bộ điều khiển tìm kiếm cylinder không tồn tại, đọc sector không tồn tại, dùng đầu đọc không tồn tại, hoặc vận chuyển vào và ra bộ nhớ không tồn tại. Hầu hết các bộ điều khiển kiểm tra các tham số và sẽ báo lỗi nếu không thích hợp. Lỗi checksum tạm thời : gây ra bởi bụi trên đầu đọc. Bụi tồn tại giữa đầu đọc và bề mặt đĩa sẽ gây ra lỗi đọc. Nếu lỗi tồn tại, khối có thể bị đánh dấu hỏng bởi phần mềm. Lỗi checksum thường trực : đĩa bị hƣ vật lý trên các khối. Lỗi tìm kiếm : ví dụ đầu đọc đến cylinder 7 trong khi đó phải đọc 6. Lỗi điều khiển : bộ điều khiển từ chối thi hành lệnh. 199
b. RAM Disks Ý tƣởng RAM disk khá đơn giản. Thiết bị khối là phần lƣu trữ trung gian với hai lệnh : đọc một khối và ghi một khối. Thông thƣờng những khối này đƣợc lƣu trữ trên đĩa mềm hoặc đĩa cứng. RAM disk dùng một phần đã định vị trƣớc của bộ nhớ chính để lƣu trữ các khối. RAM disk có ƣu điểm là cho phép truy xuất nhanh chóng (không phải chờ quay hay tìm kiếm). Nhƣ vậy nó thích hợp cho việc lƣu trữ những chƣơng trình hay dữ liệu đƣợc truy xuất thƣờng xuyên. Hình trên mô tả ý tƣởng của RAM disk. Một RAM disk đƣợc chia làm nhiều khối, số lƣợng tùy thuộc vào dung lƣợng của vùng nhớ. Mỗi khối có cùng kích thƣớc và vừa đúng bằng kích thƣớc của khối thực sự trên đĩa. Khi driver nhận đƣợc chỉ thị là đọc hoặc ghi một khối, nó sẽ tìm trong bộ nhớ RAM disk vị trí của khối, và thực hiện việc đọc hay ghi trong đó thay vì từ đĩa mềm hay đĩa cứng. 200
c. Interleave Bộ điều khiển đọc ghi đĩa phải thực hiện hai chức năng là đọc/ghi dữ liệu và chuyển dữ liệu vào hệ thống. Để thực hiện đƣợc đồng bộ hai chức năng này, bộ điều khiển đọc đĩa cung cấp chức năng interleave. Trên đĩa các sector số hiệu liên tiếp nhau không nằm kế bên nhau mà có một khoảng cách nhất định, khoảng cách này đƣợc xác định bởi quá trình format đĩa. Ví dụ : giả sử hệ thống chỉ có 17 sector, và interleave đƣợc chọn là 4 thì các sector đƣợc bố trí theo thứ tự nhƣ sau : 1, 14, 10, 6, 2, 15, 11, 7, 3, 16, 12, 8, 4, 17, 13, 9, 5 Cách đọc lần lƣợt nhƣ sau : Lần 1:1, 14, 10, 6, 2, 15, 11, 7, 3, 16, 12, 8, 4, 17, 13, 9, 5 Lần 2: 1, 14, 10, 6, 2, 15, 11, 7, 3, 16, 12, 8, 4, 17, 13, 9, 5 Lần 3: 1, 14, 10, 6, 2, 15, 11, 7, 3, 16, 12, 8, 4, 17, 13, 9, 5 Lần 4: 1, 14, 10, 6, 2, 15, 11, 7, 3, 16, 12, 8, 4, 17, 13, 9, 5 Nhƣ vậy sau bốn lần thứ tự các sector đọc đƣợc vẫn là từ 1 đến 17 14.2. Hệ thống I-O chuẩn (terminals) Mọi máy tính đều liên lạc với một hay nhiều terminals. Terminals có rất nhiều dạng khác nhau. Bộ điều khiển terminals ẩn dấu mọi sự khác biệt, vì vậy phần độc lập thiết bị của hệ điều hành và chƣơng trình ngƣời sử dụng không cần thiết phải viết lại cho mỗi loại terminal. 14.2.1. Phần cứng terminal Dƣới quan điểm của hệ điều hành, terminal đƣợc chia làm hai loại lớn dựa vào cách liên lạc với hệ điều hành. Loại thứ nhất bao gồm những loại terminal giao tiếp theo chuẩn RS-232. Loại thứ hai là những terminal dùng ánh xạ bộ nhớ. Mỗi loại đƣợc chia làm nhiều loại nhỏ nhƣ hình sau : 201
Terminal RS-232 là những thiết bị bao gồm nhƣ bàn phím và màn hình. Đây là thiết bị giao tiếp tuần tự, mỗi lần một bit. Những terminals này dùng connector 25-pin, một pin dùng để chuyển dữ liệu, một pin dùng để nhận dữ liệu, một pin là nền, 22 pin còn lại có những chức năng khác nhau, hầu hết thƣờng thƣờng không dùng đến. Để gởi một ký tự cho terminal RS-232, máy tính mỗi lần chuyển một bit, ngoài ra có một bit bắt đầu, và sau đó có 1 hoặc 2 bit kết thúc để giới hạn một ký tự. Thƣờng thƣờng tốc độ vận chuyển là 1200, 2400, 4800, 9600 bps. Vì cả máy tính và terminal đều làm việc với ký tự mà phải liên lạc với nhau bằng bit nên hệ thống phải thiết kế bộ chuyển đổi gọi là UART. Bộ phận này đƣợc gắn vào các card giao tiếp của RS-232. 202
Để in một ký tự, bộ điều khiển terminal ghi một ký tự lên card giao tiếp, sau đó sẽ chuyển cho UART. Terminal RS-232 đƣợc chia làm nhiều loại. Dạng đơn giản nhất là terminal hardcopy(printing). Ví dụ các ký tự đƣợc nhập vào từ bàn phím và chuyển cho máy tính. Các ký tự từ máy tính xuất ra máy in. Dạng tƣơng tự nhƣ vậy nhƣng ký tự đƣợc xuất trên màn hình gọi là “glass ttys” do đó nó cũng có chức năng tƣơng tự nhƣ trên. Terminals intelligent dùng trong máy tính nhỏ. Điểm khác biệt với loại trên dƣới quan điểm hệ điều hành là nó sẽ gữi ký tự ASCII ESC sau những ký tự khác nhau dùng để chuyển cursor đến vị trí bất kỳ trên màn hình, chèn một dòng vào giữa màn hình. Blit là một terminal có bộ xử lý mạnh và một màn hình có 1024x800 điểm giao tiếp với máy tính bằng RS-232. 14.2.2. Terminal ánh xạ bộ nhớ Dạng thứ hai của terminal là terminal ánh xạ bộ nhớ. Loại này không giao tiếp với máy tính qua đƣờng serial. Nó là một phần của của hệ thống máy tính. Terminal ánh xạ bộ nhớ giao tiếp bằng một bộ nhớ đặc biệt gọi là video RAM, là một phần của bộ nhớ chính đƣợc định vị bởi CPU. Trên card video RAM có một chip gọi là bộ điều khiển video. Chip này sẽ lấy thông tin từ video RAM và tạo ra tín hiệu video để điều khiển màn hình. Màn hình tạo những tia điện tử quét từ trên xuống dƣới. Thƣờng thƣờng có khoảng từ 200 đến 1200 dòng, trên mỗi dòng có từ 200 đến 1200 điểm. Mỗi điểm đƣợc gọi là pixel. Bộ điều khiển tín hiệu sẽ xác định mỗi điểm là sáng hay tối. Màn hình màu sẽ có ba tia là đỏ, lục và xanh. 203
Thông thƣờng màn hình mono xây dựng một ký tự trong một box có chiều rộng là 9 pixel và chiều cao là 14 pixel (bao gồm khoảng trống giữa những ký tự) nhƣ vậy sẽ có 25 dòng và mỗi dòng có 80 ký tự. Mỗi khung đƣợc vẽ lại từ 45 đến 70 lần trong một giây. Bộ điều khiển video đặt các dòng 80 ký tự vào trong video RAM. Một ví dụ về màn hình ánh xạ ký tự trên máy IBM PC. Một phần bộ nhớ chính bắt đầu từ địa chỉ 0xB000 cho màn hình đơn sắc và 0xB800 cho màn hình màu. Mỗi ký tự trên màn hình chiếm hai bytes trong bộ nhớ. Byte thấp chứa giá trị ASCII của ký tự, byte cao chứa thuộc tính nhƣ màu sắc, nhấp nháy v.v Màn hình 80x25 sẽ chiếm 4000 bytes bộ nhớ video RAM Khi CPU ghi một ký tự vào video RAM, nó xuất hiện trên màn hình theo mỗi lần hiển thị (1/50 giây cho mono, 1/60 cho màu ). CPU có thể nạp 4K ảnh màn hình đã đƣợc tính trƣớc vào video RAM trong vài phần triệu giây. Với tốc độ 9600 bps, ghi 2000 ký tự vào terminal RS-232 mất khoảng 2083 phần triệu giây. Terminal ánh xạ bộ nhớ cho phép truy xuất rất nhanh. Terminal bit-map tƣơng tự nhƣ vậy, ngoại trừ là mọi bit trong video RAM kiểm soát mỗi điểm trên màn hình. Màn hình có 1024x800 pixel cần dùng 100 K bộ nhớ nhƣng khó thiết kế font và kích thƣớc cho ký tự. Bàn phím giao tiếp thông qua cổng song song và giao tiếp RS-232. Mỗi khi gõ phím vào, CPU bị ngắt, bộ điều khiển bàn phím xác định kiểu ký tự đƣợc đọc từ cổng I/O. Đôi khi bàn phím chỉ cung cấp số hiệu phím , không phải mã ASCII. Trên IBM PC khi gõ phím A mã ký tự 30 đƣợc đƣa vào thanh ghi I/O. Bộ điều khiển xác định ký tự là chữ hoa hay chữ thƣờng hay là tổ hợp phím. 204