Allocation Methods
Mỗi tập tin đều được lưu ở một vùng nhớ nhất định. Để cấp phát vùng nhớ cho các tập tin (cả tập tin đã tạo và mới tạo), ta cần sử dụng các phương pháp cấp phát. Có ba phương pháp cấp phát phổ biến là:
- Cấp phát liên tục.
- Cấp phát bằng danh sách liên kết.
- Cấp phát bằng chỉ mục.
Contiguous Allocation
Cấp phát các blocks liên tục nhau trên đĩa.
Ưu điểm:
- Tốc độ rất nhanh, vì đầu đọc - ghi sẽ không phải chuyển động nhiều khi đọc các blocks liên tục của file trên đĩa.
Nhược điểm:
- Nếu cấp phát thừa thì sẽ rất lãng phí, vì các blocks thừa ra thường rời rạc và không đủ để cấp phát cho các tập tin khác.
- Nếu kích thước của tập tin được mở rộng, sẽ rất khó khăn để cấp phát vùng nhớ mới liên tục. Chỉ có thể di chuyển toàn bộ file sang một dãy các blocks liên tục khác.
Linked List Allocation
Nội dung của tập tin được lưu trữ ở những blocks rời rạc. Các blocks này được xâu chuỗi lại thành một danh sách liên kết để dễ quản lý.
Đây là phương pháp sử dụng trong hệ thống tập tin FAT (FAT File System).
Ưu điểm:
- Tận dụng hiệu quả các blocks trống.
- Có thể dễ dàng mở rộng.
Nhược điểm:
- Truy cập tập tin lâu hơn do các blocks nằm ở nhiều cylinders khác nhau.
- Không thể truy cập ngẫu nhiên (bản chất của danh sách liên kết là cần phải truy cập tuần tự).
- Lãng phí một phần bộ nhớ để lưu địa chỉ (của block tiếp theo).
Indexed Allocation
Mỗi file sẽ có một index block (ta gọi block này là inode) trỏ đến các blocks được sử dụng bởi file.
Ưu điểm:
- Có tất cả các ưu điểm của phương pháp cấp phát danh sách liên kết.
- Có thể truy cập ngẫu nhiên.
Nhược điểm:
- Tốn không gian bộ nhớ để lưu inode đối với các file có kích thước nhỏ.
Improvements
Các phương pháp cải tiến:
- Chỉ mục kết hợp với danh sách liên kết (linked scheme).
- Liên kết nhiều inodes lại để lưu các file có kích thước lớn.
- Ví dụ: dùng entry cuối cùng của inode để lưu địa chỉ của inode tiếp theo.
- Chỉ mục đa cấp (multi-level index):
- Inode cấp 1 lưu danh sách các inodes cấp 2 (sử dụng con trỏ).
- Chỉ mục kết hợp (combined scheme):
- Là sự kết hợp của linked scheme và multi-level index.
- Đây là phương pháp được sử dụng trong hệ điều hành Unix.
Free-space Management
Để quản lý các block trống trên đĩa, ta cũng có nhiều hướng tiếp cận, chẳng hạn như:
- Bit vector (bit map): mỗi block đại diện bởi 1 bit. Nếu giá trị của bit là:
0: block có chứa dữ liệu.1: block không chứa dữ liệu.
- Linked: các block trống liên kết với nhau, block trống thứ N lưu địa chỉ của block trống thứ N+1. Chỉ cần quan tâm đến địa chỉ block trống đầu tiên.
- Group: tương tự linked nhưng cần lưu thêm địa chỉ của N block trống trong block trống đầu tiên.
- Counting: với mỗi N block trống liên tiếp thì sẽ lưu địa chỉ của block trống đầu tiên và số lượng block trống (N).