Giáo trình Hệ điều hành - Chương 10: Cài đặt hệ thống tập tin - Nguyễn Phú Trường

 
235
Đại Học Cần Thơ - Khoa Công Nghệ Thông Tin - Giáo Trình Hệ Điều Hành – V1.0 
Hình 0-9 Inode của UNIX 
Cơ chế cấp phát lập chỉ mục gặp một số khó khăn về năng lực như cấp phát 
liên kết. Đặc biệt, các khối chỉ mục có thể được lưu trữ (cache) trong bộ nhớ; nhưng 
các khối dữ liệu có thể được trãi rộng khắp phân khu. 
VI.4 Năng lực 
Các phương pháp cấp phát ở trên khác nhau về tính hiệu quả lưu trữ và thời 
gian truy xuất khối dữ liệu. Cả hai yếu tố này là tiêu chuẩn quan trọng trong việc chọn 
phương pháp hợp lý hay các phương pháp cho một hệ điều hành cài đặt. 
Trước khi chọn một phương pháp, chúng ta cần xác định hệ thống sẽ được dùng như 
thế nào. Một hệ thống với hầu hết truy xuất tuần tự nên dùng một phương pháp khác 
từ hệ thống với hầu hết truy xuất ngẫu nhiên. Đối với bất cứ loại truy xuất nào, cấp 
phát kề yêu cầu chỉ một truy xuất để đạt được một khối đĩa. Vì chúng ta có thể giữ dễ 
dàng địa chỉ khởi đầu của tập tin trong bộ nhớ, chúng ta có thể tính lập tức địa chỉ đĩa 
của khối thứ i (hay khối kế tiếp) và đọc nó trực tiếp. 
Đối với cấp phát liên kết, chúng ta cũng có thể giữ địa chỉ khối kế tiếp trong 
bộ nhớ và đọc nó trực tiếp. Phương pháp này là tốt cho truy xuất tuần tự; tuy nhiên, 
đối với truy xuất trực tiếp một truy xuất tới khối thứ i phải yêu cầu đọc I đĩa. Vấn đề 
này minh hoạ lý do cấp phát liên kết không được dùng cho một ứng dụng yêu cầu truy 
xuất trực tiếp. 
Do đó, một số hệ thống hỗ trợ các tập tin truy xuất trực tiếp bằng cách dùng 
cấp phát kề và truy xuất tuần tự bởi cấp phát liên kết. Đối với các hệ thống này, loại 
truy xuất được thực hiện phải được khai báo khi tập tin được tạo. Một tập tin được tạo 
cho truy xuất tuần tự sẽ được liên kết và không thể được dùng cho truy xuất trực tiếp. 
Một tập tin được tạo cho truy xuất trực tiếp sẽ kề nhau và có thể hỗ trợ cả hai truy 
xuất trực tiếp và truy xuất tuần tự nhưng chiều dài tối đa của nó phải được khai báo 
Biên soạn: Th.s Nguyễn Phú Trường - 09/2005 Trang 
236
Đại Học Cần Thơ - Khoa Công Nghệ Thông Tin - Giáo Trình Hệ Điều Hành – V1.0 
khi nó được tạo. Trong trường hợp này, hệ điều hành phải có cấu trúc dữ liệu hợp lý 
và các giải thuật để hỗ trợ cả hai phương pháp cấp phát. Các tập tin có thể được 
chuyển từ một kiểu này sang một kiểu khác bằng cách tạo một tập tin mới của loại 
mong muốn và các nội dung của tập tin cũ được chép vào tập tin mới. Sau đó, tập tin 
cũ có thể bị xoá và tập tin mới được đổi tên. 
Cấp phát dạng chỉ mục phức tạp hơn. Nếu khối chỉ mục đã ở trong bộ nhớ rồi 
thì truy xuất có thể được thực hiện trực tiếp. Tuy nhiên, giữ khối chỉ mục trong bộ 
nhớ yêu cầu không gian có thể xem xét. Nếu không gian bộ nhớ này không sẳn dùng 
thì chúng ta phải đọc trước khối chỉ mục và sau đó khối dữ liệu mong muốn. Đối với 
chỉ mục hai cấp, đọc hai khối chỉ mục là cần thiết. Đối với tập tin rất lớn, truy xuất 
một khối gần cuối tập tin yêu cầu đọc tất cả khối chỉ mục để lần theo chuỗi con trỏ 
trước khi khối dữ liệu được yêu cầu cuối cùng được đọc. Do đó, năng lực của cấp phát 
chỉ mục phụ thuộc cấu trúc chỉ mục trên kích thước tập tin và vị trí của khối mong 
muốn. 
Một số hệ thống kết hợp cấp phát kề và cấp phát chỉ mục bằng cách dùng cấp 
phát kề cho các tập tin nhỏ (ba hay bốn khối) và tự động chuyển tới cấp phát chỉ mục 
nếu tập tin lớn lên. Vì hầu hết các tập tin là nhỏ và cấp phát kề là hiệu quả cho các tập 
tin nhỏ, năng lực trung bình là rất tốt. 
Nhiều tối ưu khác là có thể và đang được dùng. Với sự chênh lệch tốc độ giữa 
CPU và đĩa, nó là không hợp lý để thêm hàng ngàn chỉ thị tới hệ điều hành để tiết 
kiệm chỉ một vài di chuyển của đầu đọc. Ngoài ra, sự chênh lệch này tăng theo thời 
gian, tới điểm nơi mà hàng trăm của hàng ngàn chỉ thị phù hợp có thể được dùng để 
tối ưu sự di chuyển của đầu đọc. 
VII Quản lý không gian trống 
Vì không gian trống là giới hạn nên chúng ta cần dùng lại không gian từ các tập 
tin bị xoá cho các tập tin mới nếu có thể. Để giữ vết của không gian đĩa trống, hệ 
thống duy trì một danh sách không gian trống. Danh sách không gian trống ghi lại tất 
cả khối đĩa trống. Để tạo tập tin, chúng ta tìm trong danh sách không gian trống lượng 
không gian được yêu cầu và cấp phát không gian đó tới tập tin mới. Sau đó, không 
gian này được xoá từ danh sách không gian trống. Khi một tập tin bị xoá, không gian 
đĩa của nó được thêm vào danh sách không gian trống. Mặc dù tên của nó là danh 
sách nhưng danh sách không gian trống có thể không được cài như một danh sách. 
VII.1 Bit vector 
Thường thì danh sách không gian trống được cài đặt như một bản đồ bit (bit 
map) hay một vector bit (bit vector). Mỗi khối được biểu diễn bởi 1 bit. Nếu khối là 
trống, bit của nó được đặt là 1, nếu khối được cấp phát bit của nó được đặt là 0. 
Thí dụ, xét một đĩa khi các khối 2, 3, 4, 5, 8, 9, 10, 11, 12, 13, 17, 18, 25, 26, và 27 là 
trống và các khối còn lại được cấp phát. Bản đồ bit không gian trống sẽ là: 
001111001111110001100000011100000 
Lợi điểm chính của tiếp cận này là tính tương đối đơn giản và hiệu quả của nó 
trong việc tìm khối trống đầu tiên, hay n khối trống tiếp theo trên đĩa. 
Một lần nữa, chúng ta thấy các đặc điểm phần cứng định hướng chức năng 
phần mềm. Tuy nhiên, các vector bit là không đủ trừ khi toàn bộ vector được giữ 
trong bộ nhớ chính. Giữ nó trong bộ nhớ chính là có thể cho các đĩa nhỏ hơn, như trên 
các máy vi tính nhưng không thể cho các máy lớn hơn. Một đĩa 1.3 GB với khối 512 
Biên soạn: Th.s Nguyễn Phú Trường - 09/2005 Trang 
237
Đại Học Cần Thơ - Khoa Công Nghệ Thông Tin - Giáo Trình Hệ Điều Hành – V1.0 
bytes sẽ cần một bản đồ bit 332 KB để ghi lại các khối trống. Gom bốn khối vào một 
nhóm có thể giảm số này xuống còn 83 KB trên đĩa. 
VII.2 Danh sách liên kết 
Hình 0-10 danh sách không gian trống được liên kết trên đĩa 
Một tiếp cận khác để quản lý bộ nhớ trống là liên kết tất cả khối trống, giữ một 
con trỏ tới khối trống đầu tiên trong một vị trí đặc biệt trên đĩa và lưu nó trong bộ 
nhớ. Khối đầu tiên này chứa con trỏ chỉ tới khối đĩa trống tiếp theo,..Trong thí dụ trên, 
chúng ta có thể giữ một con trỏ chỉ tới khối 2 như là khối trống đầu tiên. Khối 2 sẽ 
chứa một con trỏ chỉ tới khối 3, khối này sẽ chỉ tới khối 4,(như hình X-10). Tuy 
nhiên, cơ chế này không hiệu quả để duyệt danh sách, chúng ta phải đọc mỗi khối, 
yêu cầu thời gian nhập/xuất đáng kể. Tuy nhiên, duyệt danh sách trống không là hoạt 
động thường xuyên. Thường thì, hệ điều hành cần một khối trống để mà nó có thể cấp 
phát khối đó tới một tập tin, vì thế khối đầu tiên trong danh sách trống được dùng. 
Phương pháp FAT kết hợp với đếm khối trống thành cấu trúc dữ liệu cấp phát. 
VII.3 Nhóm 
Thay đổi tiếp cận danh sách trống để lưu địa chỉ của n khối trống trong khối 
trống đầu tiên. n-1 khối đầu tiên này thật sự là khối trống. Khối cuối cùng chứa địa 
chỉ của n khối trống khác, Sự quan trọng của việc cài đặt này là địa chỉ của một số 
lượng lớn khối trống có thể được tìm thấy nhanh chóng, không giống như trong tiếp 
cận danh sách liên kết chuẩn. 
VII.4 Bộ đếm 
Một tiếp cận khác đạt được lợi điểm trong thực tế là nhiều khối kề có thể được 
cấp phát và giải phóng cùng lúc, đặc biệt khi không gian được cấp phát với giải thuật 
cấp phát kề hay thông qua nhóm. Do đó, thay vì giữ một danh sách n địa chỉ đĩa trống, 
chúng ta có thể giữ địa chỉ của khối trống đầu tiên và số n khối kề trống theo sau khối 
đầu tiên. Mỗi mục từ trong danh sách không gian trống sau đó chứa một địa chỉ đĩa và 
bộ đếm. Mặc dù mỗi mục từ yêu cầu nhiều không gian hơn một địa chỉ đĩa đơn, 
nhưng toàn bộ danh sách sẽ ngắn hơn với điều kiện là bộ đếm lớn hơn 1. 
Biên soạn: Th.s Nguyễn Phú Trường - 09/2005 Trang 
238
Đại Học Cần Thơ - Khoa Công Nghệ Thông Tin - Giáo Trình Hệ Điều Hành – V1.0 
VIII Tóm tắt 
Hệ thống tập tin định vị không đổi trên thiết bị lưu trữ phụ được thiết kế để 
quản lý một lượng lớn dữ liệu không đổi. Phương tiện lưu trữ phụ phổ biến nhất là 
đĩa. 
Đĩa vật lý có thể được chia thành nhiều phân khu để điều khiển việc sử dụng 
phương tiện và cho phép nhiều hệ thống tập tin (có thể khác nhau) trên đĩa. Các hệ 
thống tập tin này được gắn vào kiến trúc hệ thống tập tin luận lý để làm cho chúng sẳn 
dùng. Các hệ thống tập tin thường được cài đặt trong một kiến trúc phân tầng hay 
module. Những cấp thấp hơn giải quyết các thuộc tính vật lý của các thiết bị lưu trữ. 
Cấp cao hơn giải quyết các tên tập tin biểu tượng và các thuộc tính luận lý của tập tin. 
Các cấp trung gian ánh xạ các khái niệm tập tin luận lý thành các thuộc tính thiết bị 
vật lý. 
Mỗi kiểu hệ thống tập tin có các cấu trúc và giải thuật khác nhau. Một tầng VFS 
cho phép các tầng cao hơn giải quyết mỗi kiểu hệ thống tập tin khác nhau trong cùng 
một cách. Ngay cả các hệ thống tập tin ở xa có thể được tích hợp vào cấu trúc thư 
mục của hệ thống và được hoạt động trên các lời gọi hệ thống chuẩn bằng giao diện 
VFS. 
Những tập tin khác nhau có thể được cấp phát không gian trên đĩa trong 3 cách: 
kề, liên kết hay chỉ mục. Cấp phát kề có thể gặp phải sự phân mãnh ngoài. Truy xuất 
trực tiếp là kém hiệu quả với cấp phát liên kết. Cấp phát chỉ mục yêu cầu chi phí đáng 
kể cho khối chỉ mục của nó. Các giải thuật này có thể tối ưu trong nhiều cách. Không 
gian kề có thể lớn lên thông qua đoạn mở rộng để tăng khả năng linh hoạt và giảm 
phân mãnh ngoài. Cấp phát chỉ mục có thể được thực hiện trong việc nhóm nhiều 
khối để tăng thông lượng và giảm số lượng các mục từ chỉ mục được yêu cầu. Lập chỉ 
mục trong các nhóm là tương tự như cấp phát kề với các đoạn mở rộng. 
Các phương pháp cấp phát không gian trống cũng ảnh hưởng tới tính hiệu quả 
của không gian đĩa, năng lực hệ thống tập tin và khả năng tin cậy của thiết bị lưu trữ 
phụ. Các phương pháp được dùng gồm các vector bit và các danh sách liên kết. Các 
tối ưu gồm nhóm, đếm và FAT, mà đặt danh sách liên kết trong một vùng kề. 
Biên soạn: Th.s Nguyễn Phú Trường - 09/2005 Trang 
239