Mỗi một tệp trong UNIX có một chỉ số duy nhất (inode) gán cho tệp lúc tệp được tạo. Inode chứa các thông tin cần thiết để một TT truy nhập tệp, ví dụ như người sở hữu tệp, quyền truy nhập, kích thước của tệp, vị trí data của tệp trong FS. Các TT truy nhập tệp bằng các GHT và xác định một tệp bằng xâu kí tự gọi là đường dẫn tên tệp. Mỗi đường dẫn lại xác định duy nhất một tệp, và kernel sẽ biến đổi đường dẫn đó thành inode của tệp.
Chương này đề cập tới cách tổ chức của tệp nói riêng và của FS nói chung như: inode, tệp và ghi/ đọc tệp, tệp thư mục, tệp và tổ chức đĩa: inode đĩa và block đĩa cho tệp; đồng thời cũng đưa ra các thuật toán cơ sở thao tác tệp. Các thuật toán này nằm ở lớp trên của buffer cache.
2.1 Inode (Index-node), định nghĩa và cấu trúc
Inode tồn tại ở trên đĩa (disk inode) còn gọi là inode dạng tĩnh và kernel đọc inode đó vào bộ nhớ (gọi là in - core inode) để xử lí. In - core inode là một mảng trong Inode table. Một inode khi đọc vào bộ nhớ là tập hợp của hai phần gồm phần tĩnh trên đĩa và phần động inficore inode. Disk inode gồm có các trường sau đây:
- Nhận dạng người sở hữu tệp. Quan hệ sở hữu chia ra làm sở hữu cá thể và sở hữu nhóm định nghĩa một tập hợp các users có quyền truy nhập tệp. Superuser được quyền chi phối mọi tệp trong FS.
- Kiểu tệp (file type): tệp thường (regular), thư mục (directory), kí tự (character), kiểu khối đặc biệt (block special), hay FIFO (pipes). (Khi trường = 0, inode tương ứng chưa dùng (free)).
- Phép truy nhập tệp (Permission). Hệ thống bảo vệ tệp theo ba lớp: 1. người sở hữu (ownerfiu) và 2. nhóm người sở hữu (groupfig) và 3. những người khác (otherfio). Mỗi lớp lại được lập các quyền khác nhau một cách riêng biệt như: đọc (rfiread), ghi (wfiwrite), thực hiện (xfiexecute) (chạy một tệp thực thi). Riêng thư mục thực hiện là tương đương với tìm tệp trên thư mục.
- Thời điểm truy nhập tệp (access time), cho biết thời điểm tệp đã có sự thay đổi vào lần truy nhập cuối cùng và khi inode đã có thay đổi.
- Số các liên kết (link) tới tệp. Tệp có thể có nhiều tên trong cấu trúc thư mục, đó là các link của tệp.
- Bảng địa chỉ các block data đĩa cấp phát cho tệp. Mặc dù user xử lí tệp như một xâu các kí tự, thì kernel cất data của tệp trên các block đĩa không liên tục, nội dung các block đĩa khi đọc và sắp xếp lại chính là nội dung của tệp.
- Độ dài của tệp. Data trong tệp được địa chỉ hoá bằng tổng số bytes, bắt đầu từ đầu tệp và khởi động bởi offset=0 (con trỏ tệp, ứng với byte đầu tiên) và độ dài của tệp là một số lớn hơn offset lớn nhất 1 đơn vị (offset max + 1).
group os
type regular file
permission rwx r-x r-x
accessed Oct 23 1999 1:45 P.M
modified Oct 22 1999 10:30 A.M
inode changed at Oct 23 1999 1:30 P.M
size 6030 bytes
disk addresses (danh sách địa chỉ các khối đĩafidisk blocks)
Tất cả các thông tin trên là nội dung của inode, cho biết chi tiết về bản thân một tệp mà nhờ đó user truy nhập tới nội dung cỉa tệp. Khi nói tới ghi đĩa, cần phân biệt ghi nội dung của tệp lên đĩa và ghi nội dung của inode lên đĩa. Nội dung của inode thay đổi khi thay đổi nội dung của tệp hay khi thay đổi các thuộc tính như owner, permission, links. Thay đổi nội dung của tệp tự động dẫn đến thay đổi inode, nhưng thay đổi inode không dẫn tới thay đổi nội dung của tệp.
Incore - inode là bản sao nội dung inode trên đĩa (disk inode) vào bộ nhớ và để tại Inode table trong bộ nhớ sau đó sẽ có thêm các trường sau đây:
- Trường trạng thái của inode in - core cho biết:
- inode đã khoá (locked);
- có một TT đang đợi inode trong khi inode bị khóa, chờ inode được giải khóa (unlocked);
- bản in - core của inode có sự khác biệt với bản sao từ trên đĩa bởi có sự thay đổi thông tin tổ chức (data) trong inode;
- bản in - core của inode có sự khác biệt với bản sao từ trên đĩa bởi có sự thay đổi nội dung (data) trong tệp;
- tệp là một điểm ghép (mount point) của cấu trúc FS; Số thiết bị logic của FS chứa tệp.
- Số của thiết bị logic mà tệp được lưu trên thiết bị đó;
- Số của inode. Các inode đuợc cất trong một mảng tuyến tính trên đĩa, kernel nhận biết số của inode đĩa bằng vị trí của nó trong mảng. (Inode đĩa không cần có trường này).
- Các con trỏ trỏ tới các in - core inode khác. Kernel liên kết các inode trên một hàng băm (hash queue) và trong một danh sách các inode chưa sử dụng (free list). Một hàng băm thì được nhận biết bởi số của thiết bị logic của inode và số của inode. Kernel có thể chứa nhiều nhất một bản sao in - core inode của một inode đĩa, trong khi đó các inode có thể đồng thời có mặt trong hash queue và trong free list.
- Một số đếm qui chiếu (reference count) cho biết tệp mở bao nhiêu lần (actived), ví dụ khi các TT dùng hàm open() để mở cùng một tệp, mỗi lần mở số đếm này tăng lên 1 đơn vị. Một in – core inode có trong free list chỉ khi nào trường số đếm này có giá trị bằng 0 và inode đó là inactive và kernel sẽ cấp inode đó cho một disk inode khác (khi có TT open một tệp nào đó).
Free list của các inode được sử dụng giống như là một cache của các inactive inode: Khi TT truy nhập một tệp mà inode của tệp chưa có trong nhóm in - core inode, kernel sẽ cấp cho nó một in - core inode từ free list để sử dụng.
2.2. Truy nhập các inodes
Kernel nhận biết các inode qua FS và số của inode sau đó cấp cho inode đó một incore inode và việc đó được thực hiện bởi thuật toán iget(). Thuật toán này về tư duy cũng giống như getblk() tìm một block đĩa trong buffer cache. Kernel sẽ ánh xạ số của thiết bị và số của inode vào hàng băm, và tìm một hàng có inode cần tìm. Nếu không thấy inode đó (chưa có), kernel cấp một in - core inode trong free list và khoá inode đó lại. Sau đó kernel chuẩn bị để đọc bản sao của disk inode vào in - core inode vừa cấp phát: kernel biết số của inode và số của thiết bị logic, kernel tính toán block logic đĩa có chứa disk inode, tính ra số của block đó, đọc vào buffer hệ thống, lấy inode và sao vào inficore inode trong inode table.
Phép tính dựa vào công thức sau đây:
Code:
block number = ((inode number –1) / numbrer of inode per block) + start block of inode list.
Ví dụ: block số 2 là block đầu tiên của các block dành cho inode list (xem lại hình 2.3
chương 2); mỗi block có tất cả 8 inode; Hãy tìm block chứa inode số 8, inode số 9:
Bl = ((8-1) / 8) + 2 = 2; block đĩa số 2 chứa inode số 8.
Bl = ((9-1) / 8) + 2 = 3; block đĩa số 3 chứa inode số 9.
Khi biết được số của thiết bị (đĩa cứng số:.../phân hoạch số:...) và số của block đó trên đĩa cứng, kernel dùng chức năng bread() để đọc block và tìm tới offset của inode trong block bằng thuật toán:
Code:
offset của inode = ((inode number-1) modulo (number of inodes per block)) * size of disk
inode
Giả sử cấu trúc một disk inode có: 8 inodes, mỗi inode có độ dài 64 bytes. Tìm inode số 8
(byte offset bắt đầu của inode số 8):
((8-1) modulo (8)) * (64) = 448, inode số 8 bắt đầu ở byte số 448 của block đĩa inode.
Quá trình tiếp theo là:
- kernel cấp in-core inode (lấy ra từ free list), đặt in - core inode vào hàng băm;
- đặt (khởi động) số đếm qui chiếu = 1 (có một TT mở tệp này);
- copy toàn bộ các thông tin từ inode disk nói trên vào in-core inode;
- khóa (lock) in - core inode lại.
- trả lại cấu trúc (con trỏ) inode cho TT gọi.
input: số của inode trong FS ( inode number)
output: là inode đặt trong Inode Table đã khóa lại chống tranh chấp
Ở đây iget(), bread() là các chức năng (hàm) cơ sở của nhân HĐH.
2.3. Giải phóng một inode
Khi một inode được giải phóng khỏi sự sử dụng của một TT (TT close tệp nó truy
nhập), kernel giảm số đếm đi 1. Nếu số đếm trở thành 0 (không còn TT nào truy nhập tệp), kernel cập nhật (ghi) inode lên đĩa nếu bản in - core có sự khác biệt với disk inode (xem lại các tiêu chí về sự khác biệt trong phần trước). Kernel đặt inode vào free list của các inode, ẩn inode trong cache để có dùng ngay khi tái sử dụng. Kernel đồng thời giải phóng tất cả block đĩa đã dùng kết hợp cho tệp và nếu số link = 0, giải phóng luôn inode. Quá trình đó được mô tả bằng thuật toán iput().
Kernel dùng chức năng iput() /*giải phóng truy nhập cho một in - core inode*/
Input: con trỏ trỏ vào in - core inode trong bảng Inode Table;
Output: Không có mã trả lại
3. Cấu trúc của tệp thông thường (regular file hay ordinary file)
Như đã nói, inode chứa bảng địa chỉ các block data để định vị data trên đĩa. Mỗi block đĩa được đánh dấu bằng một số, do vậy bảng bao gồm tập hợp các số của các block đĩa.
Nếu data của tệp được ghi trên một vùng liên tục của đĩa (trình tự tuyến tính các block đĩa), thì lưu địa chỉ của block khởi đầu và độ dài của tệp trong inode là đủ để truy nhập tệp. Tuy nhiên chiến lược cấp phát như vậy sẽ không cho phép mở rộng và thu nhỏ các tệp trên một hệ thống tệp khi không thực hiện biện pháp phân đoạn các vùng nhớ trống trên đĩa. Hơn nữa kernel đã có thể phải cấp phát và dành riêng những vùng đĩa liên tục trước khi cho phép các thao tác tăng độ dài của tệp.
Ví dụ: User tạo 3 tệp A, B, C mỗi tệp dùng 10 block đĩa và được cấp các block liên tục (xem hình dưới). Nếu user cần mở rộng tệp B thêm 5 block vào giữa tệp, thì kernel phải sao chép lại vào vùng đĩa khác với 15 block liên tục. Bên cạnh việc thực hiện một thao tác đắt giá như vậy thì 10 block trước đó chỉ có thể cấp cho các tệp mới nhỏ hơn 10 block. Kernel có thể tối thiểu hoá sự phân đoạn như vậy bằng chạy định kì các thủ tục “gắn” các không gian đĩa lại nhưng điều đó bòn rút nhiều sức mạnh xử lí của hệ thống.
Để linh hoạt hơn, kernel phân phối một block mỗi lần cho tệp và cho phép data của tệp phân tán qua FS, tuy nhiên sơ đồ cấp phát như vậy sẽ là phức tạp nhiệm vụ định vị data.
Bảng nội dung có thể bao gồm danh sách số các block chứa data thuộc tệp, thế nhưng bằng cách tính đơn giản chỉ ra rằng danh sách tuyến tính các block trong inode khó quản lí. Nếu một block logic là 1 K bytes, thì tệp dài 10 K cần một chỉ số của 10 block, vậy nếu là 100 Kb thì số chỉ số sẽ là 100 số để đánh dấu block. ở đây ta thấy kích thước của inode do vậy sẽ thay đổi theo độ dài của tệp, hoặc sẽ có một giới hạn thấp sẽ áp đặt lên độ dài của tệp.
Để giữ cho cấu trúc inode nhỏ mà vẫn cho phép tệp lớn, bảng các block đĩa thích hợp
với cách trình bày trên hình dưới đây. Hệ UNIX System V làm việc với 13 đầu vào của bảng
các block trong một inode, nhưng nguyên tắc là độc lập với tổng số các block:
- Các đầu vào đánh dấu là “direct” cho số của block đĩa chứa data của tệp.
- Đầu vào đánh dấu “single indirect” chỉ tới một block mà nội dung của nó là danh sách số các block trực tiếp chứa data của tệp. Để lấy data qua các block gián tiếp kernel phải đọc block gián tiếp, lấy ra số của block trực tiếp, sau đó đọc block trực tiếp đó.
- Khối đánh dấu “double indirect” cho danh sách số của các block gián tiếp đôi: block gián tiếp à block gián tiếp
- Khối “triple indirect” cho danh sách số của các block gián tiếp ba: block gián tiếp à
block gián tiếp à block gián tiếp.
10 đầu vào cho 10 block trực tiếp cho 10 Kbyte
1 đầu vào cho 1 block gián tiếp cho 256 x 1 K = 256 K
1 đầu vào cho 1 block gián tiếp đôi cho 256 x 256 x 1K = 64 M byte
1 đầu vào cho 1 block gián tiếp ba cho 256x256x256x1K= 16 Gbyte
Nếu trường chứa độ dài tệp trong inode là 32 bit, thì kích thước hiệu dụng của tệp sẽ giới hạn tới 4 Gbyte (232).
Các TT truy nhập data của tệp bởi byte offset (con trỏ tệp), làm việc trong khái niệm
số đếm byte và nhìn tệp như một chuỗi các byte bắt đầu ở byte có địa chỉ bằng 0 và tiến tới cuối tệp. Kernel biến đổi cách nhìn byte của user thành cách nhìn vào block đĩa: tệp bắt đầu ở block logic 0 và tiếp tục tới block tương ứng với độ dài của tệp. Kernel truy nhập inode, biến đổi block logic vào block đĩa thích hợp. Thuật toán bmap() thực hiện biến đổi file offset thành block đĩa vật lí.
Kernel dùng chức năng bmap( )(Xem ở mã nguồn Linux) thực hiện biến đổi file offset thành block đĩa vật lí.
input: (1) inode
(2) byte offset
output: (1) số của khối đĩa (block number in file system)
(2) con trỏ trỏ vào khối đĩa (byte offset into block)
(3) số byte cần thực hiện truy nhập trong jhôid đĩa
(4) đọc trước khối đĩa cho lần đọc sau
Ví dụ: biến đổi byte offset thành số của block đĩa.
Hãy xét cách bố trí các block cho tệp ở hình sau:
Giả định rằng một block đĩa có 1024 byte. Nếu một TT muốn tìm byte thứ 9000,
kernel tính thấy byte này nằm ở block trực tiếp tại đầu vào số 8 (đếm từ đầu và đánh số từ 0) trong bảng địa chỉ các block của tệp ở đó có địa chỉ của block số 367. Với 9 block cho 1024x9=9216 byte, từ đó tính ra byte thứ 808 trong block này là byte 9000 của tệp (8 block trước đó cho 8x1024=8192 byte, 9000-8192=808). Nếu TT tìm byte thứ 350.000 trong tệp, kernel tính ra rằng phải đọc block gián tiếp đôi mà địa chỉ của block là 9156. Bởi vì 1 block gián tiếp cho 256 địa chỉ các block, vậy byte đầu tiên qua block gián tiếp đôi là byte 272.384 (256K + 10K); byte 350.000 là byte thứ 77.616 của block gián tiếp đôi. Vì mỗi một block gián tiếp đơn cho 256 K bytes, byte 350.000 phải ở block gián tiếp đơn thứ 0 của block gián tiếp đôI, ví dụ đó là block số 331 (đầu vào thứ 0 của block 9156). Block 331 cho 256 block trực tiếp mỗi block 1K, vậy byte số 77.616 của block trực tiếp sẽ trong block trực tiếp thứ 75 (giả định số của block này là 3333) của block gián tiếp đơn. Cuối cùng khi đọc block 3333, kernel tìm thấy byte thứ 816 là byte 350.000 của tệp.
Xem xét hình một cách chi tiết hơn, có một vài đầu vào trong bảng địa chỉ các block là 0, có nghĩa rằng các đầu vào của các block logic này không chứa data. Điều này xảy ra khi không có TT nào ghi data vào tệp ở bất kì vị trí nào tương ứng với các block đó, do vậy số của các block không đổi và là các giá trị ban đầu (initial). TT có thể tạo ra các block như vậy trong bảng bằng cách dùng GHT lseek() và write().
Sự biến đổi byte offset lớn, đặc biệt khi phải qui chiếu qua gián tiếp ba (triple) là một qui
trình hết sức rắc rối đòi hỏi kernel phải truy nhập thêm ba block đĩa ngay cả khi các block đã có trong cache thì phép thực hiện vẫn rất đắt giá vì kernel sẽ phải yêu cầu buffer rất nhiều lần và sẽ phải đi ngủ do buffer bị khoá. Hiệu quả thực tiễn của thuật toán này phụ thuộc vào tần xuất truy nhập các tệp lớn hay nhỏ trên hệ thống. Hãy thử xét tới khả năng tăng độ lớn của 1 block đĩa (4 K, 8K hay 12 K/block), liệu có gì khả quan hơn cũng như hiệu suất sử dụng đĩa có tồi hơn ? Hiện tượng phân đoạn có tăng lên ?
4. Tệp thư mục
Thư mục là một tệp mà data của nó là trình tự các đầu vào mà mỗi đầu vào bao gồm
một số của inode và tên của tệp chứa trong thư mục. Một đường dẫn là một xâu kí tự kết thúc trống (NULL), được phân chia ra thành các thành phần ngăn bởi kí tự “/”. Mỗi thành phần, trừ thành phần cuối cùng, phải là tên của một thư mục, và thành phần cuối cùng không phải là tệp thư mục. UNIX System V hạn chế tên của một thành phần chỉ tới 14 đến 256 kí tự và 2 bytes cho số của inode. Vậy ví dụ tên tệp là 14 kí tự, thì một đầu vào thư mục có 16 bytes, một tệp thư mục sẽ như sau:
Mỗi một thư mục chứa các tên tệp “.” (dot) và “..” (dot-dot) với số của inode là inode của thư mục đó và thư mục bố (trên một mức). Inode số “.” tại offset 0 và trị số của nó là 83. Tương tự của inode “..” có offset là vị trí thứ 16 và trị số là 2. Đầu vào của thư mục có thể “rỗng” và được biểu thị bởi số inode = 0. Ví dụ đầu vào 224 “rỗng” dù đã một lần chứa tệp có tên “crash”. Chương trình tạo hệ thống tệp khới động FS sao cho “.” và “..” của thư mục root có số inode của FS.
Kernel cất data của thư mục cũng giống như cho các tệp thường, sử dụng cấu trúc inode và các cách cấp trực tiếp, gián tiếp của các block. TT đọc tệp thư mục cùng cách thức như đọc tệp thường, nhưng kernel giành đặc quyền để ghi thư mục, do đó đảm bảo được sự chuẩn xác của thư mục. Quyền truy nhập thư mục có ý nghĩa như sau:
- quyền đọc (read) thư mục cho phép TT đọc thư mục;
- quyền ghi (write) thư mục cho phép TT tạo các đầu vào mới hay xoá đầu vào cũ (creat, mknod, link, unlink); bằng cách đó thay đổi nội dung thư mục.
- Quyền thực hiện (excute) cho phép TT thực hiện tìm kiếm tên tệp trong thư mục.
Truy nhập tệp khởi đầu bằng đường dẫn. Vì bên trong kernel làm việc với inode, chứ không bằng tên tệp qua đường dẫn, nên kernel phải chuyển đổi từ đường dẫn thành inode để truy nhập tới tệp. Thuật toán namei() làm phân tích mỗi thành phần trong đường dẫn một lần, biến đổi mỗi thành phần đó thành inode trên cơ sở tên của nó và thư mục đang tìm kiếm, cuối cùng trả lại inode.
Nhắc lại trong chương trước là mỗi một TT được kết hợp với một thư mục hiện tại (mà TT thường trú ở đó). Miền bộ nhớ ufiarea chứa một con trỏ trỏ tới inode là thư mục hiện hành. Thư mục hiện hành của TT đầu tiên trong hệ thống, TT số 0, là thư mục root. Thư mục hiện hành của mỗi TT khác bắt đầu từ thư mục bố hiện hành vào lúc TT được tạo ra. TT thay đổi thư mục bằng thực hiện GHT chdir (đổi thư mục). Việc tìm đường dẫn xuất phát từ thư mục hiện hành của TT trừ phi có dấu “/”, cho biết việc tìm thư mục phải bắt đầu từ root. Trong các trường hợp khác kernel dễ dàng tìm ra inode mà ở đó việc tìm đường dẫn bắt đầu: thư mục hiện hành có trong ufiarea của TT, và inode của root có trong biến tổng thể.
namei() /*convert path name to inode*/
input: đường dẫn (path name)
ouput: inode đã tìm được (locked inode)
Kernel thực hiện tìm tuyến tính một tệp thư mục, kết hợp với working inode (thư mục tạm thời), thử sự tương xứng của thành phần tên đường dẫn với một đầu vào của tệp thư mục (xem lại cấu trúc của tệp thư mục). Bắt đầu với byte offset = 0 trong thư mục, chuyển đổi offset này thành block đĩa tương ứng (bmap()) và đọc block đó (bread()). Kernel xử lí nội dung của block này như tuần tự các đầu vào của thư mục, tìm từng thành phần trong đường dẫn bằng cách so sánh các đầu vào, nếu tìm được, kernel lấy ra số của inode ứng với tên đường dẫn đó, giải phóng block (brelse()) và working inode cũ (iput()), cấp phát một inode của thành phần vừa tìm được (iget()), và inode mới này trở thành working inode. Nếu không có kết quả ở block này, kernel giải phóng block, điều chỉnh lại offset bằng số byte trong block (lấy byte offset tiếp theo), biến đổi offset mới thành số của block đĩa (bmap()), và đọc block đó. Kernel lặp lại chu trình này cho tới khi tìm ra inode tương ứng với thành phần (tệp) yêu cầu trong đường dẫn cho tới hết các đầu vào của thư mục.
Ví dụ: Tìm tệp passwd trong thư mục /etc: “/etc/passwd”.
Khi bắt đầu phân tích tên tệp, kernel gặp “/” và nhận đi lấy inode của root, inode này trở
thành working inode. Kernel đi thu thập xâu “etc”: sau khi kiểm tra đúng inode này là của thư mục “/” và TT có đủ quyền hạn truy nhập, kernel tìm tệp có tên ”etc”: Kernel truy nhập data trong thư mục gốc (root) hết block này tới block khác, tìm từng đầu vào của từng block cho tới khi định vị được một đầu vào “etc”. Khi tìm được đầu vào này, kernel giải phóng inode root (iput()), lấy inode ứng với “etc” (iget()), sau khi biết đích xác “etc” là tệp thư mục, kernel tìm trong các block của “etc” để đến tệp “passwd”, lấy từ đó inode ứng với “passwd”.
6. Cấp một inode cho một tệp mới tạo
Kernel dùng iget() để định vị inode đã biết (với số của inode đã được xác định trước
đó trong thuật toán namei()). Một thuật toán khác ialloc() gán một inode cho một tệp mới tạo. Hệ thống tệp có một danh sách tuyến tính các inode. Một inode là free nếu trường chứa kiểu tệp (type) là 0. Khi một TT cần inode mới, kernel có thể tìm trong danh sách inode một inode free, tuy nhiên cách làm này có thể rất đắt đòi hỏi ít nhất một thao tác đọc đĩa cho mỗi inode. Để cải thiện, super block chứa một mảng ẩn số lượng các inode free trong FS. Hãy theo dõi cho thuật toán ialloc(), tìm và cấp một inode mới:
ialloc() /*allocate inode*/
input: FS
output: inode mới (locked inode)
Thuật toán giải phóng inode đơn giản hơn.
ifree() /*inode free*/
input: FS inode number
output: none
7. Cấp phát các block đĩa
Khi một TT ghi data lên đĩa, kernel sẽ cấp các block cho nó theo cơ chế direct và indirect như đã nói. Super block có một mảng gồm nhiều block đĩa dùng để ẩn các số của các block đĩa chưa dùng (free disk block) của FS. Tiện ích mkfs() tổ chức các khối dữ liệu (data block) của FS vào một danh sách liên kết, mà mỗi một liên kết của danh sách là một block đĩa, block này chứa một mảng số hiệu của các free disk block và một đầu vào của mảng cho số của block tiếp theo của danh sách liên kết. Hình sau là ví dụ về danh sách liên kết: block đầu tiên là danh sách block chưa dùng của super block (super block free list), với các đầu vào là số của các block sẽ dùng cho cấp phát, và 1 đầu vào có số của block liên kết tiếp theo (block 109, 211, 310, 409…).
Khi kernel muốn cấp phát một block, xem thuật toán alloc(), kernel sẽ lấy block trong danh sách các free block sẵn có của super block list, và một khi đã dùng block không thể tái cấp cho tới khi nó trở lại là free. Nếu block đã cấp là block cuối cùng có trong mảng cache, kernel sẽ xử lí block đó như là con trỏ (109) trỏ vào block (109) chứa danh sách các free block khác. Kernel đọc block đó, nhập vào mảng Super block với danh sách mới số của các block chưa cấp, sau đó tiếp tục sử dụng số của block gốc, cấp buffer cho block, xoá data của block (điền zero vào). Block đĩa lúc này đã cấp phát cho tệp, kernel cũng đã có buffer để làm việc. Chương trình sẽ thông báo lỗi nếu FS không còn có free block.
alloc() /*FS block allocation*/
input: FS (number)
outout: buffer for new block
Nếu TT ghi một khối lượng data lớn, TT sẽ lặp lại yêu cầu xin cấp block, trong khi kernel chỉ thực hiện cấp mỗi lần một block. Chương trình mkfs() sẽ tổ chức danh sách liên kết của các block sao cho gần với nhau, để giảm đi thời gian tìm kiếm trên đĩa khi TT đọc tệp tuần tự.
Hình dưới mô tả số hiệu của các block với số cách quãng (interlive code = 3) đều đặn dựa
trên cơ sở tốc độ quay của đĩa. Điều lưu ý là thứ tự sắp xếp nói trên sẽ không còn khi tần xuất sử dụng block đĩa cao (cấp phát/ giải phóng) và quá trình cập nhật lại danh sách có tính ngẫu nhiên và kernel không thực hiện sắp xếp lại thứ tự gốc.
Thuật toán giải phóng block free(), ngược lại với cấp phát block. Nếu super block list không đầy, số của block vừa được giải phóng sẽ đặt vào danh sách đó. Nhưng nếu không còn chỗ (đã đầy) thì block vừa được giải phóng sẽ thành block liên kết; kernel ghi super block list vào block đĩa đó và ghi nội dung của block này lên đĩa, sau đó đặt số của block mới giải phóng vào super block list. Số của block này chỉ là thành viên của danh sách.
Thuật toán gán/giải phóng inode tệp và block đĩa là tương tự ở chỗ kernel dùng super
block như là một cache của các chỉ số cho nguồn tài nguyên chưa dùng (free), số của các
block, số của các inode. Kernel duy trì danh sách liên kết của số hiệu các block sao cho mỗi số chưa dùng hiện diện trong một thành phần của danh sách. Điều này không có đối với free inode. Sở dĩ có sự khác nhau do các nguyên nhân dưới đây:
- Kernel có thể biết inode là free bằng cách tham khảo trường Type, nếu = 0 thì inode free, nhưng đối với block đĩa thì không có cơ chế gì để nhận biết tương tự. Do vậy kernel cần có phương pháp khác để biết block là free, và đó là linked listfidanh sách liên kết.
- Các block đĩa bản thân đã là dùng danh sách liên kết: một block đĩa có thể chứa một danh sách lớn số hiệu của các block chưa cấp phát. Với cấu trúc dữ liệu lớn cho mỗi inode, không thể thực hiện như cho block đĩa.
- Việc khai thác block đĩa (đọc/ ghi nội dung tệp) là thường xuyên hơn khai thác inode (tạo, mở, ghi tệp), điều đó có nghĩa truy nhập block đĩa gay cấn hơn tìm inode.
No comments:
Post a Comment