Bài viết sưu tầm

Cơ chế cấp phát & quản lý các block chứa tập tin trên đĩa của hệ điều hành

Trong phần này chúng ta xem xét các cơ chế khác nhau mà hệ điều hành sử dụng để theo dõi (tổ chức lưu trữ tập tin lên đĩa và đọc lại nội dung tập tin đang lưu trữ) danh sách các block đĩa mà hệ điều hành đã cấp phát cho một tập tin, để chứa hết các block của một tập tin, của tất cả các tập tin đang được lưu trữ tên đĩa.

Cơ chế cấp phát liên tục (contiguous allocation):

Trong cơ chế này, các block tập tin được lưu trữ tại các block đĩa liên tục nhau. Tức là,  nếu mỗi block đĩa là 1K thì một tập tin 50K sẽ được lưu trữ tại 50 block liên tiếp nhau trên đĩa.

Cơ chế này đơn giản, dễ cài đặt và thời gian đọc tập tin giảm xuống đáng kể, vì hệ điều hành chỉ cần biết block đĩa đầu tiên chứa các block tập tin và tổng số block đĩa chứa tập tin là có thể tiến hành đọc nội dung của tập tin mà không cần dò tìm danh sách các block đĩa chứa nội dung của tập tin.

Tuy nhiên, cơ chế này chỉ có thể được sử dụng với các tập tin có kích thước cố định, không thay đổi so với thời điểm tạo ra tập tin, hoặc với các tập tin mà hệ điều hành biết trước được kích thước tối đa của nó, trong trường hợp này hệ điều hành phải dự trữ block đĩa cho tập tin, điều này dễ dẫn đến tình trạng lãng phí trong việc sử dụng block đĩa.

Cơ chế này có thể dẫn đến hiện tượng phân mảnh trên đĩa, tức là trên đĩa có thể xuất hiện các đoạn block trống nhỏ, không đủ để chứa một tập tincó kích thước tối thiểu, nằm giữa các đoạn block chứa tập tin, các đoạn block trống này có thể là nơi lưu trữ của một tập tinnào đó mà tập tinnày đã bị xoá khỏi đĩa. Hiện tượng phân mảnh đĩa sẽ làm chậm tốc độ đọc tập tincủa hệ điều hành.                    

Các hệ điều hành hiện nay, hệ điều hành WindowsNT/2000 chẳng hạn, cải tiến cơ chế này để khắc phục các hạn chế và tận dụng những thuận lợi của nó. Bằng cách, vẫn cấp phát các block đĩa liên tục để chứa vừa đủ kích thước ban đầu của tập tin, và sau đó nếu kích thước của tập tin tăng lên thì hệ điều hành sẽ tìm và cấp phát một đoạn block khác tại một vị trí bất kỳ trên đĩa để chứa vừa đủ phần kích thước tăng lên này. Tức là, nội dung của tập tin được lưu trữ tại các đoạn block đĩa rời rạc nhau trên đĩa. Nếu kích thước tập tin giảm xuống thì hệ điều hành phải tổ chức lại việc lưu trữ tập tin để sao cho có thể giải phóng được một đoạn block đĩa chứa tập tin trước đó.

Với việc cải tiến này, hệ điều hành có thể đọc tập tin nhanh hơn, ít xảy ra phân mảnh hơn nhưng việc tổ chức lưu trữ sẽ phức tạp hơn. Chúng ta sẽ thấy cách tổ chức này trong hệ thống tập tincủa hệ điều hành windowsNT/2000 trong phần sau của chương này.      

Cơ chế cấp phát không liên tục và quản lý theo danh sách liên kết (linked list allocation):

Cơ chế này sử dụng một danh sách liên kết để quản lý các block đĩa để chứa nội dung của một tập tin. Word (2 byte) đầu tiên của mỗi block đĩa được sử dụng như một con trỏ để trỏ đến block kế tiếp, trừ word của block cuối cùng được sử dụng để chứa tín hiệu báo kết thúc danh sách của một tập tin, phần còn lại của block đĩa dùng để chứa nội dung của tập tin. Trong trường hợp này kích thước của block đĩa phải lớn hơn kích thước của block tập tin1 word.

Hình sau đây minh hoạ cho việc lưu trữ tập tin theo cơ chế này, với tập tin A được chia thành 4 block: block 0, block 1, block 2, block 3 được lưu trữ tại các block đĩa, lần lượt là 3, 7, 5, 10. Với tập tin B được chia thành 3 block: block 0, block 1, block 2, được lưu trữ tại các block đĩa, lần lượt là 4, 8, 6.

Không như cấp phát liên tục, mọi block đều có thể được sử dụng trong cơ chế này, nên sẽ không dẫn đến hiện tượng phân mảnh đĩa và khai thác tối đa không gian đĩa. Và hệ điều hành chỉ cần biết block đĩa đầu tiên chứa tập tinlà có thể đọc được toàn bộ nội dung của tập tin, block đầu tiên này được ghi ở phần tử trong bảng danh mục tương ứng với mỗi tập tin. Tốc độ đọc tập tin theo cách truy cập ngẫu nhiên trong cơ chế này sẽ rất chậm so với cách truy cập tuần tự như ở cơ chế cấp phát liên tục ở trên.       

Cơ chế cấp phát không liên tục và quản theo danh sách liên kết sử dụng chỉ mục (linked list allocation using an index):

Cấp phát theo danh sách liên kết tồn tại hai hạn chế đó là: chậm và tốn một word để chứa con trỏ đến block kế tiếp. Để khắc phục hai hạn chế này, các hệ điều hành lưu các word con trỏ nói trên vào trong một bảng chỉ mục và nạp bảng chỉ mục này vào bộ nhớ khi hệ điều hành cần đọc nội dung của tập tintrên đĩa.

Hình sau minh hoạ cho việc lưu trữ tập tintheo cơ chế này, với tập tinA được chia thành 4 block: A1, A2, A3, A4 được lưu trữ tại các block đĩa, lần lượt là 4, 10, 7, 14(cuối cùng). Với tập tinB được chia thành 4 block: B1, B2, B3, B4 được lưu trữ tại các block đĩa, lần lượt là 6, 9, 12, 15 (cuối cùng).

Với cách tổ chức này thì toàn bộ block đĩa được sử dụng để lưu trữ tập tinvà việc truy cập ngẫu nhiên trong trường hợp này sẽ dễ dàng hơn. Tuy nhiên cũng phải tồn tại một móc xích để tìm ra tất cả các blick đĩa chứa nội dung của một tập tinvà móc xích này phải được nạp vào bộ nhớ để hệ điều hành có thể tìm đọc tập tinkhi cần. Cũng như cơ chế trên block đầu tiên của một tập tinphải được chứa trong phần tử bảng danh mục tương ứng với mỗi tập tin, trong trường hợp này nó được xem như một con trỏ trỏ đến bảng chỉ mục để bắt đầu dò tìm dãy các block đĩa chứa nội dung của tập tin, mỗi khi hệ điều hành cần đọc tập tin. Hệ điều hành MS_DOS tổ chức quản lý tập tin trên đĩa dựa theo cơ chế này.

Một hạn chế lớn của cơ chế này là toàn bộ bảng chỉ mục phải nạp vào bộ nhớ trong suốt thời gian làm việc của hệ thống, điều này sẽ làm tốn thời gian nạp bảng chỉ mục của hệ điều hành và làm lãng phí không gian bộ nhớ của hệ thống, đặc biệt trong trường hợp bảng chỉ mục lớn. Bảng chỉ mục lớn là do đĩa lớn, đĩa có bao nhiêu block thì bảng chỉ mục có bấy nhiêu phần tử, mỗi phần tử trong bảng chỉ mục có thể là 1 word, 1.5 word, 2 word, 4 word, vv phụ thuộc vào kích thước đĩa, kích thước block và cách tổ chức quả lý block đĩa của mỗi hệ điều hành. 

Các hệ điều hành hiện nay khắc phục hạn chế trên đây bằng cách, không nạp tất cả bảng chỉ mục vào bộ nhớ mà chỉ nạp phần bảng chỉ mục liên quan đến các tập tin đang mở trên bộ nhớ tại một thời điểm cụ thể nào đó, tức là, phần bảng chỉ mục này luôn thay đổi trong quá trình làm việc của hệ thống. Khái niệm cửa sổ bảng FAT  trong hệ thống tập tincủa hệ điều hành windows98 là một ví dụ của trường hợp này.

Cơ chế cấp phát không liên tục và sử dụng I-nodes (index-node) để quản lý:

Trong cơ chế này, hệ điều hành thiết kế một bảng nhỏ để theo dõi các block của một tập tin, được gọi là I-node. I-node liệt kê các thuộc tính và các địa chỉ đĩa của các block của tập tin. Hình sau minh hoạ cho cơ chế này.

Đầu tiên một phần địa chỉ đĩa (các block đĩa) được lưu trữ trong chính I-node. Sau đó, đối với các tập tinnhỏ thì tất cả các thông tin cần thiết là phải chứa trong chính I-node, đó là các thông tin được nhận từ đĩa vào bộ nhớ chính khi tập tinđược mở. Đối với các tập tinlớn, gồm nhiều block, thì một trong các địa chỉ trong I-node là địa chỉ của một block đĩa, được gọi là block gián tiếp đơn. Block này chứa các địa chỉ đĩa được thêm vào. Nếu vẫn còn không đủ thì một địa chỉ khác trong I-node, được gọi là block gián tiếp đôi, sẽ chứa địa chỉ của một block mà nó chứa một danh sách các block gián tiếp đơn. Mỗi block gián tiếp đơn trỏ đến khoảng 100 block dữ liệu. Nếu vẫn còn không đủ thì có thể một block gián tiếp ba được sử dụng. Nhìn hình vẽ trên ta dẽ dàng phân biệt được sự khác nhau giữa: block gián tiếp đơn, block gián tiếp đôi và block gián tiếp ba.

Cơ chế này được windows 2000 cải tiến và sử dụng trong cấu trúc MFT trong hệ thống tập tin của nó. Chúng ta sẽ thấy điều này khi tìm hiểu hệ thống tập tincủa windows 2000 trong phần sau của chương này.

Cơ chế cấp phát không liên tục và sử dụng block chỉ mục để quản lý:

Cả hai cơ chế cấp phát, theo danh sách liên kết và theo liên kết chỉ mục đều tồn tại hạn chế là phải phân tích danh sách liên kết hay bảng chỉ mục để dò tìm ra danh sách các block đĩa chứa nội dung của tập tin cần đọc, khi đọc tập tin, dẫn đến làm chậm tốc độ đọc tập tin trên đĩa.

Để khắc phục điều này các hệ điều hành có thể cài đặt cơ chế cấp phát không liên tục với block chỉ số. Hệ điều hành sử dụng một block đĩa để chứa danh sách các block đĩa chứa nội dung của một tập tin nào đó, block đĩa này được gọi là block chỉ mục. Trong hình trên block 11 là chỉ mục của tập tinA, block 8 là chỉ mục của tập tin A. Như vậy chỉ cần thiết kế một con trỏ, tại phần tử trong bảng chỉ mục, trỏ tới block chỉ mục của tập tin trên đĩa là hệ điều hành có thể quản lý được danh sách các block đĩa chứa nội dung của một tập tin.

Với cơ chế này thì tốc độ đọc tập tin của hệ điều hành sẽ tăng lên, nhưng nó chỉ dụng được đối với các tập tin nhỏ, vì nếu tập tin lớn thì một block có thể không chứa đủ danh sách các block đĩa chứa nội dung của một tập tin. Mặt khác nếu block chỉ mục của tập tinbị hỏng thì hệ điều hành không thể đọc được tập tin, mặc dầu nội dung của tập tin vẫn còn tồn tại trên các block đĩa.

(Nguyễn Kim Tuấn - K.CNTT)