# :writing_hand: ==LECTURE OPERATING SYSTEM (CONT.)==
## :pushpin: Chapter :four: : File & Disk Management
:::success
* **File System:** hiểu một cách đơn giản, nó là một **tập hợp** bao gồm các **quy tắc**, các **cấu trúc dữ liệu** và các **cách thức**, **phương pháp truy cập**, **xử lý** trên các cấu trúc dữ liệu này.
$\implies$ Hỗ trợ cho người dùng các ++thao tác++ **lưu trữ** thông tin trên ổ đĩa mà che đi (**không cần quan tâm**) hết tất cả phần **vật lý** bên dưới.
* **File System** sẽ bao gồm $03$ tầng lớp:
* (1) File System Interface: Hệ thống giao diện tập tin.
* (2) File System Implementation: Hệ thống thực thi tập tin.
* (3) Disk Storage: Hệ thống lưu trữ tập tin vào ổ đĩa.
:::
### I. File System Interface (End - users view)
::: info
* **File System Interface** là phần sẽ trực tiếp tương tác với *end-users*.
* **File System Interface** sẽ cung cấp cho *end-users* hai khái niệm ảo, đó là:
* **++File++** (Tập tin)
* **++Directory++** (Folder)
* **Nguyên nhân:** Do hệ thống cơ sở bên dưới chỉ biết lưu dữ liệu byte theo byte nên hệ thống cốt lỗi này sẽ không thể biết được các khái niệm ào hay về tầng giao diện người dùng.
* **Mục đích**
* Giúp cho người dùng có thể **tương tác trực tiếp** với các khái niệm này mà **không cần phải hiểu, quan tâm về các cấu trúc vật lý hạ tầng** của thiết bị lưu trữ dữ liệu bên dưới.
* Cung cấp cho người dùng các **cách thức thao tác** có thể thực thi tập tin (CRUD: tạo tập tin / thư mục mới, đọc (hiển thị) tập tin / thư mục, xóa và cập nhật file /directory $\to$ bản chất là các *system calls* gọi lên hệ thống tập tin thực thi) trên hai đối tượng khái niệm ào này
$\to$ tối đa hóa hiệu suất và đơn giản hóa thao tác quản lý và sử dụng tập tin của người dùng $\to$ đỡ tốn thời gian, công sức và chi phí từ người dùng.
:::
#### 1. File (Tập tin)
##### a. File Concepts
* An **==abstract concept==** $\to$ hệ thống tập tin sẽ không thể biết về khái niệm này mà chỉ biết nó là dãy các bytes $\to$ người dùng đơn giản hóa thao tác và ngữ nghĩa về hệ thống tập tin $\to$ tăng hiệu suất sử dụng hệ thống.
* A **==logical storage unit==** of a collection of related data on disks $\to$ là đơn vị lưu trữ thông tin **++nhỏ nhất++** trên đĩa của hệ điều hành.
* **==File types==** (Kiểu File)
* Ordinary / Regular file: ASCII or binary files $\to$ là tập tin chứa nội dung thông tin bình thường của người dùng được lưu trữ ở cấu trúc nhị phân hay mã ASCII trong hệ thống tập tin $\to$ thường liên quan đến file thực thi hoặc file nén.
* **ASCII file**: là tập tin văn bản chứa các văn bản cuối dòng có ký tự xuống dòng (ký tự enter) $\to$ có thể được mở bằng bất kỳ trình văn bản nào (ví dụ: notepad, .txt, word, $\dots$)
* **Binary file**: là tập tin nhị phân gồm các dãy byte, có cấu trúc tùy theo chương trình tạo ra file $\to$ phải mở bằng các trình duyệt hiểu được cấu trúc nhị phân (ví dụ: trong file cơ sở dữ liệu (database), file .sql là file text, tức là có thể mở bằng notepad, .txt, $\cdots$ vẫn hiểu được file binary $\to$ nhưng bản thân file lưu trữ dữ liệu (file lock hay file nằm trong hệ quản trị phải detect ở text ra) thì bản thân chúng không thể mở bằng file tập tin văn bản thông thường được mà phải mở bằng file nhị phân nằm trong hệ cơ sở quản lý dữ liệu)
* Directory file: Nếu ordinary / regular file được hệ thống xem là một tập tin bình thường lưu trữ nội dung dưới dạng văn bản hay nhị phân , thì directory file được hệ điều hành xem là một tập tin đặc biệt chứa nội dung bao gồm các danh sách thư mục và tập tin con chứa trong nó $\to$ tác dụng đóng gói các tập tin con thành tập tin cha.
* Shortcut file: thông thường, shortcut file sẽ link đến một file vật lý nào đó $\to$ không được xem là một tập tin thực sự.
* Windows $\to$ shortcut file,
* LINUX $\to$ (simple) link file
* Special file (i.e, device file that represents a physical device): những hệ điều hành LINUX, UNIX hoặc là những hệ điều hành dựa trên kiến trúc của UNIX $\to$ hỗ trợ thêm **Special File** (tập tin thiết bị gắt với một tập tin vật lý thiết bị nào đó đính kèm với máy tính: ổ đĩa, máy in, ... thao tác trên các thiết bị này)
* **==File attributes==** (i.e, metadata used for file management): name, size, location, creator, date (creation, access, modification), type, permission / protection, ... $\to$ là một **metadata** (phải gọi là metadata) chứa các thông tin liên quan đến file đó $\to$ dùng để quản lý tập tin, số thuộc tính của file tùy thuộc theo từng hệ điều hành khác nhau nhưng thường có các thuộc tính sau:
* **File Name (Tên tập tin):** là một khái niệm ảo dùng để phân biệt file này với file khác, UNIX phân biệt tên file chữ thường với tên file chữ hoa nhưng WINDOWS thì không phân biệt. Trong UNIX tên file có thể có nhiều phân cách (vd: prog.c.Z, $\dots$) nhưng WINDOWS chỉ có một phân cách (vd: file.txt, $\dots$). Hệ điều hành dùng phần mở rộng để nhận dạng kiểu của file và các thao tác có thể thực hiện trên kiểu file đó, ví dụ phần mở rộng là $*$.exe, $*$.com thì hệ điều hành hiểu là file kiểu nhị phân có thể thực thi nhưng nếu không thực thi được thì là do cấu trúc file không đúng quy định của file $*$.com, $*$.exe
* **File Size (Kích thước file):** Kích thước hiện thời, kích thước tối đa của file tính bằng bytes / words / blocks /...
* **File Location (Vị trí file):** danh sách các khối (cluster) trên đĩa đã cấp cho file.
* **Creator, Date** (creation, access, modification) (Người tạo file, Ngày giờ tạo file):
* Ngày, giờ tạo file
* Ngày, giờ cập nhật file gần nhất
* Ngày, giờ sử dụng file sau cùng
* Người tạo file
* **File Type (Loại File):** file ẩn, file chỉ đọc, file hệ thống, file lưu trữ, file thư mục, ...
* **File Permission / Protection (Bảo vệ File):** những hệ điều hành hiện đại (Windows, MAC, LINUX $\to$ multi-users OS: cho phép nhiều người sử dụng trong hệ điều hành $\to$ có nhiều hệ thống tập tin khác nhau $\to$ cần phải được bảo vệ trước sự xâm nhập khỏi những sự truy cập trái phép của những hệ điều hành khác) dùng account (username, password), owner / creator hoặc dùng quyền đã cấp cho user, group trên file hay thư mục, gồm các quyền sau: quyền đọc (Read), ghi (Write), xóa (Delete), thực thi (Execute), liệt kê (List), thêm (Append), ...
##### b. File Operations
* Hệ điều hành cần cung cấp các lời gọi hệ thống (system call) xử lý file như là:
* Tạo file (create): Ghi một mục chứa thông tin file vào cấu trúc thư mục và tìm một khối cung cấp cho file.
* Xóa file (delete): Tìm tên file trong cấu trúc thư mục, giải phóng tất cả khối đĩa mà file chiếm giữ, xóa mục tương ứng trong cấu trúc thư mục.
* Mở file (open): Khi lần đầu tiên file được truy xuất, thông tin về file được đọc từ cấu trúc thư mục và lưu vào bảng open-files trong bộ nhớ. Nếu file chưa đóng, thì những lần truy xuất sau sẽ không phải tìm thông tin về file trong cấu trúc thư mục nữa mà lấy trong bảng open-files.
* Đóng file (close): Ghi mục tương ứng trong bảng open-files vào cấu trúc thư mục, và hủy mục này trong bảng open-files.
* Đọc file (read): Tìm tên file trong cấu trúc thư mục, biết được vị trí lưu trữ file , đọc file vào bộ nhớ, dùng một con trỏ đọc (read pointer) để ghi nhận vị trí cho lần đọc kế tiếp.
* Ghi file (write): Tìm tên file trong cấu trúc thư mục, lấy được số hiệu khối nhớ đầu tiên cấp phát cho file, ghi dữ liệu của file vào vị trí này, dùng một con trỏ ghi (write pointer) để ghi nhận vị trí cho lần ghi kế tiếp.
* Ghi thêm vào cuối (append)
* Lấy thuộc tính (get attribute)
* Đặt thuộc tính (set attribute)
* Đặt tên file (rename)

| System Calls | Description |
| ------------------------------------- | ----------------------------------------- |
| fd = create (name, mode) | One way to create a new file |
| fd = open (file, how, ...) | Open a file for reading, writing, or both |
| s = close (fd) | Close an open file |
| n = read (fd, buffer, nbytes) | Read data from a file into a buffer |
| n = write (fd, buffer, nbytes) | Write data from a buffer into a file |
| position = lseek (fd, offset, whence) | Move the file pointer |
| s = stat(name, &buf) | Get a file's status information |
| s = fstat(fd, &buf) | Get a file's status information |
| s = pipe(&fd[0]) | Create a pipe |
| s = fcntl(fd, cmd, ...) | File locking and other operations |
##### c. Access Methods - `phương thức truy cập`
* Sequential access: truy cập tuần tự $\to$ phương pháp này thường dùng bởi những hệ điều hành hơi cũ hay những special file như file văn bản, file video, recording file
* Data blocks are accessed one by one in order $\to$ open một file ra thì nó load từng byte một.
* Direct random access: truy cập trực tiếp ngẫu nhiên
* A desired data block is accessed directly without traversing its prior blocks (vd: các file database, ...)
* Indexed sequential access: truy cập dựa vào chỉ mục
* Assign an index to some data blocks for accessing these blocks
* Built on top sequential access
* Thông thường được sử dụng trên hệ điều hành UNIX dựa trên kiến trúc I-nodes $\to$ thường sử dụng một chỉ mục nào đó trong đó chứa các pointers trỏ đến data blocks và thông qua các pointers có thể lấy các data blocks tương ứng với từng file thay vì truy cập chỉ số mặc định trên data block.
##### d. File Structure - `cấu trúc file`
* Sequence of unstructured bytes/words *(most used in modern OS, including Windows, Linux)* $\to$ OS ko thể hiểu file là gì ?
* Sequence of fixed-length records (used in early mainframes - batch OS (punched cards)) $\to$ early OS xử lý file theo từng records one by one $\to$ hiện giờ không còn sử dụng nữa
* Tree of records (still used in large systems for commercial processing) $\to$ biến thể của `sequence of fixed-length records`, trong đó mỗi nodes được xem là một record thể hiện một tập các thông tin liên quan với nhau của một đối tượng nào đó $\to$ vẫn còn sử dụng trong các hệ thống máy tính lớn xử lý nghiệp vụ thương mại phức tạp cần đóng gói các đối tượng đặc biệt thành một records.
<center>
<img src = https://scontent.xx.fbcdn.net/v/t1.15752-9/427975450_3260398770929363_5559931311803073505_n.png?_nc_cat=103&ccb=1-7&_nc_sid=5f2048&_nc_ohc=OBliswd_yygAb56rYzn&_nc_ht=scontent.xx&oh=03_Q7cD1QHpoX1hDhbRJVZcIvRDB6SE399qZmA4qULtD4dARB-MAA&oe=6649FFD3>
</center>

:::warning
**Kiến thức trọng tâm**
* File là một tập hợp thông tin được đặt tên (abstract concepts) và lưu trữ trên đĩa.
* File là đơn vị lưu trữ thông tin nhỏ nhất trên đĩa của hệ điều hành.
* File có thể lưu trữ chương trình hay dữ liệu, có thể là dãy tuần tự các bytes không có cấu trúc hoặc có cấu trúc dòng (kết thúc bằng ký tự enter), hoặc cấu trúc mẫu tin có chiều dài cố định hay thay đổi.
* Cấu trúc file do hệ điều hành hoặc chương trình quy định.
* File có thể truy xuất tuần tự (đọc các byte theo thứ tự từ đầu file), hoặc truy xuất ngẫu nhiên (đọc / ghi tại một vị trí bất kỳ trong file).
:::
#### 2. Directory (Folder - Thư mục)
##### a. Directory Concepts
* **Directory**: a collection of files/subdirectories.
* Cấu trúc thư mục là cấu trúc dùng để quản lý tất cả tập tin các file trên đĩa, được ghi trên đĩa và gồm nhiều mục (directory entry), mỗi mục lưu thông tin của một file.
* Thông thường, thông tin của một file gồm có: thuộc tính file (file attributes) và danh sách các số hiệu khối lưu trữ trên file. Khi một file được truy xuất, hệ điều hành sẽ tìm tên file trong cấu trúc thư mục, nếu tìm thấy sẽ lấy thuộc tính và các số hiệu khối lưu trữ file đưa vào một bảng trong bộ nhớ (bảng open-files), các lần sau khi truy xuất file hoặc thay đổi thông tin file thì không cần truy xuất đĩa mà truy xuất bảng open-files trong bộ nhớ chính và sẽ nhanh hơn nhiều.
* Hệ điều hành cũng cần cung cấp các system calls để thao tác trên thư mục tương tự như đối với file. Các thao tác trên thư mục có thể là: Create, Delete, Open, Close, Read, Rename, Link, Unlink, $\dots$
<center>
<img src = https://scontent.xx.fbcdn.net/v/t1.15752-9/429861635_712038711093719_2494589442740252647_n.png?_nc_cat=107&ccb=1-7&_nc_sid=5f2048&_nc_ohc=HNqVv3Ne2dQAb43Vynk&_nc_ad=z-m&_nc_cid=0&_nc_ht=scontent.xx&oh=03_Q7cD1QEybdj0E8QSn1VTNFOr0gZaDZeGW1J9gMSJFbVKOQ7wTQ&oe=664A08E2>
<p style="text-align: center;"><strong>Mô tả cấu trúc thư mục, mỗi cấu trúc thư mục quản lý một file hoặc thư mục con</strong></p>
</center>
* Two **types of path** for accessing a file/directory:
* Absolute path - `đường dẫn tuyệt đối`: C:\user\home\...\myfile.doc
* Relative path - `đường dẫn tương đối`: .\myfile.doc
* **Directory attributes**: name (without extension), path, creator, date (creation, access, modification), permission/protection
##### b. Directory Operations (Sytem calls for UNIX OS)
| System Calls | Description |
| -------------------------- | -------------------------------------- |
| s = mkdir(path, mode) | Create a new directory |
| s = rmdir(path) | Remove a directory |
| s = link(oldpath, newpath) | Create a link to an existing file |
| s = unlink(path) | Unlink a file |
| s = chdir(path) | Change the working directory |
| dir = opendir(path) | Open a directory for reading |
| s = closedir(dir) | Close a directory |
| dirent = readdir(dir) | Read one directory entry |
| rewinddir(dir) | Rewind a directory so it can be reread |
##### c. Directory Organization
* **Criteria** $\to$ Cấu trúc thư mục phải đáp ứng các tiêu chí sau:
* Efficiency (in searching/accessing a file)
* Naming
* Grouping capability according to users’ need
* Sharing
* ...
* **Single-level directory** (thư mục một cấp)
:::info
* Cấu trúc **single -level directory** sẽ chứa các thuộc tính của tất cả các file của tất cả người dùng.
* Cấu trúc này **đơn giản** nhưng gây ra khó khăn do đặt tên file (naming) không được trùng nhau và người sử dụng không thể phân nhóm (grouping) cho file cũng như hiệu suất tìm kiếm chậm khi số lượng file nhiều.
:::
* Advantages:
* Implementation $\to$ dễ thực thi nhanh chóng, không phải qua nhiều layer.
* Searching $\to$ dễ dàng tìm kiếm, truy xuất file khi số lượng file đủ nhỏ.
* Disadvantages:
* Naming $\to$ không thể đặt tên trùng nhau
* Grouping $\to$ không thể phân nhóm cho file
* Searching $\to$ khó tìm kiếm file nếu số lượng file quá lớn.
<center>
<img src = https://scontent.xx.fbcdn.net/v/t1.15752-9/427980712_670770805047427_8828202059668197503_n.png?_nc_cat=107&ccb=1-7&_nc_sid=5f2048&_nc_ohc=ZUfhH6iaQFQAb6KG41n&_nc_ht=scontent.xx&oh=03_Q7cD1QHg2gvu1SOHq_HWBcpp2c94EShuZguy1_EZ1xRH3-9tGA&oe=664A34FE>
<p style="text-align: center;"><strong>Hình 2.c.1. Cấu trúc thư mục một cấp</strong></p>
</center>
* **Two-level directory** (thư mục hai cấp)
:::info
Do sự bất tiện của cấu trúc thư mục một cấp là nhầm lẫn về đặt tên file giữa những người dùng.
$\implies$ **Solution:** tạo thư mục riêng (user file directory - UFD) cho mỗi user. Mỗi UFD có cấu trúc giống nhau nhưng chỉ quản lý file của một user, như vậy các user có thể có file cùng tên nhưng user chỉ được truy xuất các file trong thư mục của user đó.
$\implies$ Giải pháp tìm kiếm file nhanh hơn, nhưng vẫn không có khả năng nhóm file.
$\implies$ Cấu trúc này chỉ có thể áp dụng cho các hệ thống cơ bản (như: máy nghe nhạc, ...)
:::
* Advantages:
* Naming $\to$ có thể đặt tên trùng nhau giữa các users.
* Searching $\to$ có thể tìm kiếm nhanh hơn (vì 1 user chỉ cần tìm số lượng file nằm trong folder của mình nên số lượng file truy xuất ít đi)
* Disadvantages:
* Grouping $\to$ người dùng không thể chia nhỏ thư mục ra được.
<center>
<img src = https://scontent.xx.fbcdn.net/v/t1.15752-9/427154483_2696786040471091_369313056767635076_n.png?_nc_cat=111&ccb=1-7&_nc_sid=5f2048&_nc_ohc=wEK7axtuC-kAb7oSh9n&_nc_ht=scontent.xx&oh=03_Q7cD1QHsWyfC1SbRGNDLd_5920rTxSbM7H0GYr-FuawynwDLOg&oe=664A044A>
<p style="text-align: center;"><strong>Hình 2.c.2. Cấu trúc thư mục hai cấp</strong></p>
</center>
* **Tree - structure directory** (thư mục đa cấp)
:::info
* Cấu trúc thư mục đa cấp bao gồm: thư mục gốc (root directory) và trong đó có các thư mục con.
* Mỗi user có thể tạo những thư mục con riêng, trong mỗi thư mục con chứa file và có thể chứa những thư mục con khác.
* Cấu trúc này cho phép users có thể truy xuất đến file của users khác thông qua quyền được cấp và cho phép tìm kiếm hiệu quả hơn, cũng như có khả năng phân nhóm file.
* Users có thể truy xuất đến file hay thư mục hiện hành đang làm việc thông qua relative path $\to$ cách truy cập hiệu quả phụ thuộc vào vị trí của thư mục hiện hành đang làm việc.
:::
* Advantages:
* Naming $\to$ nhiều file / thư mục có thể đặt tên trùng nhau giữa các folders / users.
* Grouping $\to$ có thể phân nhóm các file/directory.
* Searching $\to$ tìm kiếm nhanh chóng thông qua relative / absolute path.
* Disadvantages:
* Accessing a file $\to$ do cấu trúc cây có rất nhiều cấp nên việc truy cập vào những file/directory khác nhau ở các cấp khác nhau sẽ gây ra hao phí rất lớn về mặt thời gian + hiệu suất và phức tạp hóa việc truy xuất dữ liệu vì phải qua rất nhiều tầng trung gian $\implies$ Solution: hệ điều hành sẽ cho phép users truy cập files/subdirectories thông qua absolute / relative path dựa trên thuật toán tìm kiếm đường đi ngắn nhất $\to$ tăng hiệu suất truy cập tập tin / thư mục.
* Same file in multiple directories $\to$ xảy ra sự đụng độ giữa nhiều phiên bản khác nhau của cùng một file thư mục hay trên các vị trí khác nhau, các file có thể khó đồng nhất với nhau về nội dung.
* Sharing $\to$ gây khó khăn cho việc sharing các tập tin chứa trong thư mục hay các thư mục con vì hệ thống yêu cầu các người dùng không thể sử dụng các file dùng chung và lưu trữ vào trong từng thư mục cá nhân người dùng.
<center>
<img src = https://scontent.xx.fbcdn.net/v/t1.15752-9/427844622_314786064485035_5036415928983848900_n.png?_nc_cat=102&ccb=1-7&_nc_sid=5f2048&_nc_ohc=RGcJYA2oGTAAb5g9E0d&_nc_ht=scontent.xx&oh=03_Q7cD1QH2y6qJyKa76mjyA682tLEjoKwV5IgHO8yNQsQeo5eBIg&oe=664A0BB5>
<p style="text-align: center;"><strong>Hình 2.c.3. Cấu trúc thư mục đa cấp</strong></p>
</center>
* **Graph directory** (thư mục đồ thị)
* Advantages:
* More flexible
* Sharing
* Disadvatages:
* More costly $\to$ hệ thống sẽ tốn chi phí để dọn rác những link không hoạt động do một trong hai đường link từ hai file / thư mục đến cùng một file/thư mục bị ngắt kết nối.
<center>
<img src = https://scontent.xx.fbcdn.net/v/t1.15752-9/427898064_382493457719110_7569763869282225628_n.png?_nc_cat=102&ccb=1-7&_nc_sid=5f2048&_nc_ohc=aXCgM-_rilEAb7fw7OP&_nc_oc=AdjG8XEMVI0TXTvbYEbSL_n0HDKbo3WsCMBMpBfeBJZo0EIjyoearCGjH6f8Grlu8Z0&_nc_ht=scontent.xx&oh=03_Q7cD1QG9YrCQBKEfcPdqGEoBUPnooKwlCieGbT_RIF-pD5Kuww&oe=664A0E9A>
<p style="text-align: center;"><strong>Hình 2.c.4. Cấu trúc thư mục đồ thị</strong></p>
</center>
</center>
##### d. Directory Table (bảng thư mục)
* Bảng thư mục là một dạng cài đặt bằng dãy một chiều của cấu trúc thư mục (Directory Structure).
* Bảng thư mục có nhiều mục (directory entry), mỗi mục lưu trữ thông tin của một file / thư mục, thông tin file gồm thuộc tính của file và địa chỉ trên đĩa của toàn bộ file hoặc số hiệu của khối đầu tiên chứa file hoặc là số I-node của file. Mỗi đĩa có một bảng thư mục gọi là bảng thư mục gốc, cài đặt ở phần đầu của đĩa và có thể có nhiều bảng thư mục con.
* Ví dụ:
* Mỗi mục trong bảng thư mục của hệ điều hành MSDOS / WINDOWS (FAT) chỉ lưu số hiệu khối đầu tiên của mỗi file/thư mục. Khí đó để biết số hiệu các khối còn lại của file/thư mục, hệ điều hành sẽ dùng bảng cấp phát file (FAT).
<center>
<img src = https://scontent.xx.fbcdn.net/v/t1.15752-9/431317775_980377583763098_7906529454524202495_n.png?_nc_cat=111&ccb=1-7&_nc_sid=5f2048&_nc_ohc=QQshcWx-frUAb4rsWOy&_nc_ad=z-m&_nc_cid=0&_nc_ht=scontent.xx&oh=03_Q7cD1QF3RknOZe5Ris3ziv2OePOpIi3R7rK9X_dSv4PtF6lcOg&oe=664A247A>
<p><b>Cấu trúc một mục trong Directory Table của MSDOS/WINDOWS (FAT)</b></p>
</center>
* Mỗi mục trong bảng thư mục của hệ điều hành CP/M chứa tất cả các số hiệu khối chứa file/thư mục, khi đó không cần dùng bảng cấp phát file (FAT).
<center>
<img src = https://scontent.xx.fbcdn.net/v/t1.15752-9/429982049_794883009165460_5507859021479868929_n.png?_nc_cat=106&ccb=1-7&_nc_sid=5f2048&_nc_ohc=_ElW65Ts1E0Ab7Ga00L&_nc_ad=z-m&_nc_cid=0&_nc_ht=scontent.xx&oh=03_Q7cD1QH66Ggz7I-o8I4mG8NmuQCN-5z8oMA7EO5c8KP8w8cVUg&oe=664A12CE>
<p><b>Cấu trúc một mục trong bảng thư mục của CP/M</b></p>
</center>
* Mỗi mục trong bảng thư mục của hệ điều hành UNIX lưu số hiệu I-node.
<center>
<img src = https://scontent.xx.fbcdn.net/v/t1.15752-9/429798297_1349021732455508_706909203408769119_n.png?_nc_cat=111&ccb=1-7&_nc_sid=5f2048&_nc_ohc=BVSXpHG0jKIAb7eaL9a&_nc_ad=z-m&_nc_cid=0&_nc_ht=scontent.xx&oh=03_Q7cD1QFqRkeVEL0Q0QmldrOIQsnfzrvxleeIhtIn7k7sFmfzTA&oe=664A19EC>
<p><b>Cấu trúc một mục trong bảng thư mục của UNIX</b></p>
</center>
##### e. Directory Partitions (phân vùng thư mục)
* Hệ điều hành có thể chia đĩa cứng thành nhiều phân vùng (partition), mỗi phân vùng gồm nhiều từ trụ (cyclinder) liên tiếp, hoặc tập hợp nhiều đĩa cứng thành một phân vùng. Mỗi phân vùng sẽ có cấu trúc thư mục riêng để quản lý các tập tin trong phân vùng đó.
<center>
<img src = https://scontent.xx.fbcdn.net/v/t1.15752-9/429823461_785078693509460_7982994371124473026_n.png?_nc_cat=103&ccb=1-7&_nc_sid=5f2048&_nc_ohc=J--5W_feLi4Ab403_Yz&_nc_ad=z-m&_nc_cid=0&_nc_ht=scontent.xx&oh=03_Q7cD1QEnHdzeyjsvkyxhv51UhBAL4ZSmKvjfhe1aqpXZfg-buw&oe=664A1904>
<p><b>Tổ chức phân vùng đĩa</b></p>
</center>
#### 3. Protection
* Mode of access: read ( R ), write( W ), execute( X )
* Three classes of users: owner (chính user đó), group (phải do admin tạo, không được user bình thường tạo $\to$ mỗi group có 3 bits ACL để thể hiện group đó, tương đương với Read( R ), Write( W ), Execute( E )), universe (public $\to$ là tất cả các file / thư mục không thuộc những file/thư mục trong group) $\to$ nhằm đơn đơn giản hóa việc cấp quyền, UNIX hỗ trợ 3 nhóm users khác nhau.
* Example of access control list (ACL): rwxrw---x or 761
* Access control list (ACL): là một danh sách bao gồm các bits thể hiện quyền truy cập của một đối tượng người dùng nào đó cho thao tác gì đó trên file. Mỗi file hay thư mục sẽ được gắn kèm một ACL. Khi người dùng thực hiện các thao tác trên một file, hay thư mục $\to$ hệ thống sẽ kiểm tra ACL gắn với file hay thư mục đó để xem users có được quyền thực thi file hay thư mục đó hay không.
<center>
<img src = https://scontent.xx.fbcdn.net/v/t1.15752-9/428106224_1428273951443754_4795111492255305043_n.png?_nc_cat=100&ccb=1-7&_nc_sid=5f2048&_nc_ohc=ENErFq9nDYYAb59W7Tr&_nc_oc=AdhV7eWxza1JmBwFhA0HQ8x2qSRZHq-7RvS64dNDEp3oNe_dIAMb7BQDycmcdRGuzJk&_nc_ht=scontent.xx&oh=03_Q7cD1QEe0vmT5fJYWvJNtt0BJcDsJdqCfGFE3Cdn9mZ-RrfFQQ&oe=664A14C9>
</center>
### II. File System Implementation (System view)
:::success
**File System Implementation** sẽ giúp hệ thống quản lý tài nguyên tập tin dưới dạng cấu trúc bytes, tức là:
* Allocation / Deallocation: cấp phát và thu hồi dữ liệu vùng nhớ tập tin (block của disk) của máy tính (giúp quản lý dữ liệu hiệu quả)
* **Mapping** một tập tin ở mức trừu tượng ở logic người dùng sang các block đĩa thực sự ở bên dưới các cấu trúc vật lý.
:::
#### 1. Overview
##### a. File System
* Chức năng của File System
* User’s point of view: how a file is named, structured, manipulated.
* System’s point of view: how to store a file on disk blocks.
<center>
<img src = https://scontent.xx.fbcdn.net/v/t1.15752-9/427882648_1262149548304068_9186046799496166972_n.png?_nc_cat=111&ccb=1-7&_nc_sid=5f2048&_nc_ohc=hckEi_tNxt8Ab6TsjjE&_nc_ht=scontent.xx&oh=03_Q7cD1QEqTOgcm4_WWq9uq3q4gophxLNvdA_9iTvVW6hYbpUlfw&oe=664A1884>
</center>
##### b. Secondary Storage : Disk Drive (nói sơ)
* A ++hard disk drive++ (HDD) can be divided into multiple partitions $\to$ quản lý được việc mỗi một phân vùng này sẽ độc lập với mỗi phân vùng khác, có thể chia phân vùng để có thể làm nhiều việc khác nhau trên những vùng khác nhau, mỗi vùng này có thể được xem như một disk riêng biệt $\to$ tránh trường hợp cài đặt hệ điều hành bị virus thì sẽ mất dữ liệu nên cần tách ra phân vùng cài hệ điều hành và dữ liệu riêng biệt (đôi khi việc xóa một phân vùng bất kỳ không ảnh hưởng đến các phân vùng còn lại)
* Một ổ đĩa có thể chia tối đa 4 phân vùng ở mức vật lý, tuy nhiên một phân vùng này có thể được chuyển thành các extended partitions - `phân vùng mở rộng`, trong mỗi extended partitions có thể chia thành các logical disks khác nhau. Trên từng logical disks, có thể cài một file systems khác nhau để quản lý dữ liệu lưu trong ổ đó.
* Đối với **Windows**, ổ **C** là ổ cài hệ điều hành (quy tắc ngầm) $\to$ bắt buộc phải dùng một file systems nào đó để cài hệ điều hành Windows. Còn các ổ **D**, **E**, **F**, ... là các ổ lưu trữ dữ liệu nên cần một file systems khác với file system ở ổ **C** để quản lý, lưu trữ dữ liệu.
* Need to install a file system on each partition to manipulate files storing on it.
* Examples of common file systems
* NTFS (Windows)
* ext2, ext3, ext4 (Linux) $\to$ là những extended file system cho những hệ thống LINUX, UNIX hoặc tương tự UNIX.
* HFS, HFS+, APFS (macOS)
* FAT32, exFAT (flash disk, removable device) $\to$ không còn dùng trên các hệ điều hành Windows nữa.
##### c. Windows File System: FAT / exFAT
* **File Allocation Table (FAT)**: early file system on Windows
* Variants: FAT12/FAT16/FAT32
* **FAT32** is compatible with most of OS (other versions of Windows, macOS, Linux, and many others)
$\implies$ *still used for* *USB* *or removable devices (no files larger than 4GB)*
* Enhanced version of FAT: exFAT (extended FAT)
* **exFAT** is compatible with all other versions of Windows, modern macOS, and Linux with some additional software required
$\implies$ *appropriate choice for flash drives (maximum file size 16EB $\to$ gần như không có giới hạn)*
$\implies$ không tương thích với các phiên bản cũ của hệ điều hành Windows.
##### d. Windows FIle System: NTFS
* **New Technology File System (NTFS)** $\to$ hầu như hệ điều hành hiện nay sử dụng hệ thống mới nhất cho các máy tính cá nhân $\to$ không tương thích với các OS khác (removable disk $\to$ ko thể hiện hành được)
* Primary file system for recent versions of Windows
* Advanced features: journaling, backup & restore, file and folder protection, compression, decryption/encryption, ...
* Support for large files and volumes
* Maximum file size: 16EB
* Limited support in macOS (read-only support) and Linux
<center>
<img src = https://scontent.xx.fbcdn.net/v/t1.15752-9/427892262_1143825063312192_5693068269822454563_n.png?_nc_cat=110&ccb=1-7&_nc_sid=5f2048&_nc_ohc=RryCGDhZ0jAAb6rK0Rc&_nc_ht=scontent.xx&oh=03_Q7cD1QEpFR0ls-vK7udmYS2773clAxlyqMCRCJK3zm4qSNqULQ&oe=6649FFE2>
<p><b>Example of file system (NTFS) in Windows</b></p>
</center>
##### e. UNIX - based File System: ext2/ext3/ext4
* Extended file system (ext) for Unix/Linux.
* Versions: ext2/ext3/ext4
* Modern Linux uses ext4 as the default file system
* Advance features: journaling (with checksum support), support for large file size ($16$GB to $16$TB)
* A directory may have a maximum of $64000$ subdirectories
<center>
<img src = https://scontent.xx.fbcdn.net/v/t1.15752-9/428004860_917814113078593_5838840218760298398_n.png?_nc_cat=109&ccb=1-7&_nc_sid=5f2048&_nc_ohc=mMjKSAljsD0Ab7F-bur&_nc_ht=scontent.xx&oh=03_Q7cD1QHvpBevqmJSGA1ESohbH-2C2_K-Ga_48I-nUUa9bttHxw&oe=664A18EF>
<p>
<b>Example of file system (ext4) in Linux</b>
</p>
</center>
:::danger
:x: **Chú ý**: một partions / ổ đĩa ở mức logic thì muốn lưu trữ được dữ liệu thì bắt buộc ổ đĩa này phải được format dưới một file systems nào đó $\to$ file systems này mới có thể quản lý được hết tất cả tập tin của ổ đĩa đó.
:::
#### 2. File and Directory Implementation
##### 2.1. File Management Implementation - `Cài đặt hệ thống quản lý file`
:::info
Việc cài đặt hệ thống quản lý file phụ thuộc vào việc hệ điều hành chọn phương pháp cấp phát khối nhớ cho file là liên tục hay không liên tục:
* Cấp phát khối nhớ liên tục:
* Contiguous Allocation
* Cấp phát khối nhớ không liên tục:
* Linked List Allocation
* Indexed Allocation
* Windows: File - Allocation Table (FAT)
* UNIX - based: Indexed Allocation (I - nodes)
* Free - space Management
:::
###### a. Fundamentals
* Allocation methods deal with how to allocate disk blocks to files
* Contiguous Allocation
* Linked List Allocation
* Indexed Allocation
* Case study #1: Linked List Allocation with File-Table Allocation (Windows)
* Case study #2: Multilevel Indexed Allocation (Unix-based
###### b. Contiguous Allocation - `cấp phát khối nhớ liên tục`
###### b.1. Contiguous Allocation - `cấp phát liên tục`
**++Tổng kết kiến thức++**
:::warning
* Khi cấp phát khối nhớ liên tục, để cài đặt hệ thống quản lý file, hệ điều hành chỉ cần dùng **bảng thư mục (directory table)**, ++mỗi mục++ trong ++bảng thư mục (directory table)++ chứa:
* Những **thuộc tính thông thường của file**
* **Số hiệu khối bắt đầu** (start)
* **Số lượng khối** đã cấp cho file (length).
* Phương pháp này **dễ cài đặt**, **dễ thao tác** vì toàn bộ file được đọc từ các khối liên tiếp trên đĩa không cần định vị lại, nhưng có khuyết điểm là **file không thể phát triển** (không đủ không gian để lưu trữ các file lớn) và có thể **gây ra lãng phí do sự phân mảnh trên đĩa** (fragmentation) $\to$ cực kì nghiêm trọng.
:::
**++Chi tiết kiến thức++**
* Definition:
* The entire file must be stored in contiguous blocks on the disk
* Advantages:
* Simple to implement $\to$ dễ cài đặt, đơn giản hóa truy xuất các data blocks vì chỉ cần tìm một khối liên tục chứa các data blocks trên đĩa mà không cần định vị lại.
* High performance $\to$ tốc độ truy xuất nhanh vì hệ thống tập tin không mất thời gian định vị các blocks ở những vị trí khác nhau.
* Disadvantages:
* Fragmentation (vấn đề phân mảnh ngoại vi) $\to$ the biggest issue
* Find enough space for large files? $\to$ không tìm đủ vùng không gian đủ lớn để lưu trữ các file cực kì lớn.
* Must know the final file size when creating a new file $\to$ gây khó khăn khi tạo file vì file system khó xác định kích thước cuối cùng của file
* nếu kích thước file quá lớn $\to$ không đủ để mở rộng vùng data
* nếu kích thước file quá nhỏ $\to$ bị dư không gian data blocks $\to$ gây lãng phí vùng tài nguyên.
<center>
<img src = https://scontent.xx.fbcdn.net/v/t1.15752-9/428078101_913083707026124_5757865735961175812_n.png?_nc_cat=107&ccb=1-7&_nc_sid=5f2048&_nc_ohc=3G4btu1adyQAb5hIEpU&_nc_ht=scontent.xx&oh=03_Q7cD1QFC31ObNB8ZsWi5eYavJSM3RFXW8nkag5kW701Cjl-CYw&oe=664A10FE>
<p><b> Bảng thư mục trong mô hình cấp phát liên tục</b></p>
</center>
###### c. Non-contiguous Allocation - `cấp phát khối nhớ không liên tục`
Khi cấp phát khối nhớ liên tục, để cài đặt hệ thống quản lý file, hệ điều hành sử dụng **bảng thư mục - `directory table`** và cần phải **sử dụng thêm** một trong các **cấu trúc** sau:
###### c.1. Linked List Allocation - `cấp phát danh sách liên kết`
**++Tổng kết kiến thức++**
:::warning
* Mỗi mục trong **bảng thư mục (directory table)** chứa:
* **số hiệu của khối đầu tiên (start)**
* **số hiệu của khối kết thúc (end)**
* Mỗi khối trên đĩa (disk) dành **một số bytes đầu hoặc cuối** (thường là $4$ bytes)
$\to$ **lưu số hiệu khối kế tiếp** của file, phần **còn lại** của khối sẽ **lưu dữ liệu** của file.
* Phương pháp này **không bị lãng phí do phân mảnh ngoại vi**, nhưng **truy xuất ngẫu nhiên - `random access file` chậm** và **rất khó bảo vệ cho các số hiệu khối** của file.
:::
**++Chi tiết kiến thức++**
* Definition:
* The file can be stored in non-contiguous blocks on the disk, each of them contains the data and the pointer to the next block
* Advantages:
* Solving fragmentation problem (giải quyết vấn đề phân mảnh ngoại vi)
* Flexibility $\to$ linh động vì kích thước file dễ dàng mở rộng, chỉ cần thêm data blocks và pointers vào disk blocks mà không bị giới hạn.
* Disadvatages:
* No direct random access $\to$ không được truy cập ngẫu nhiên mà phải truy cập tuần tự liên tục.
* Need space to store pointers $\to$ cần phải có một không gian lưu trữ các pointers trỏ đến các data blocks tiếp theo.
* What if a block is lost? $\to$ nếu một data blocks bị mất thì nguyên cả file bị hỏng vì các data blocks không thể liên kết với nhau để truyền tín hiệu.
<center>
<img src = https://scontent.xx.fbcdn.net/v/t1.15752-9/428023319_423422567019080_2038164218826039663_n.png?_nc_cat=100&ccb=1-7&_nc_sid=5f2048&_nc_ohc=JVRLYfd5oA0Ab7Zk-zJ&_nc_ht=scontent.xx&oh=03_Q7cD1QGnVGgubjzrT_erN-3rG5HgiI3KcAwEPX2tt-dPYxOxTg&oe=664A1E3A>
<p>
<b>Mô hình cấp phát không liên tục, sử dụng danh sách liên kết</b>
</p>
</center>
###### c.2. Indexed Allocation - `cấp phát bảng chỉ mục`
**++Tổng kết kiến thức++**
:::warning
* Mỗi file có một **bảng chỉ mục (index table)** chiếm **một hoặc vài khối**, **bảng chỉ mục (index table)** chứa ++tất cả các số hiệu khối của một file++. Khi đó **một mục trong bảng thư mục (directory table)** sẽ **lưu số hiệu khối chứa bảng chỉ mục (index table)** của file.
* Phương pháp này **dễ bảo vệ các bảng chỉ mục (index table)**, nghĩa là **bảo vệ được các số hiệu khối của file** nhưng **tốn nhiều khối nhớ để lưu các bảng chỉ mục (index table)**.
:::
**++Chi tiết kiến thức++**
* Definition:
* The file can be stored in non-contiguous blocks on the disk
* Data blocks for storing data
* Index block for storing pointers to all data blocks
* Advantages:
* Direct random access $\to$ truy cập trực tiếp các file một cách ngẫu nhiên.
* Solving lost block problem $\to$ giải quyết vấn đề mất data block ko bị ảnh hưởng đến data blocks khác.
* Disadvantages:
* Need entire block for pointers $\to$ cần 1 blocks chuyên biệt để lưu các pointers này.
* Inefficiency for small files $\to$ không hiệu quả đối với các file có kích thước nhỏ.
<center>
<img src = https://scontent.xx.fbcdn.net/v/t1.15752-9/426758549_354831937389259_6531887909740161142_n.png?_nc_cat=103&ccb=1-7&_nc_sid=5f2048&_nc_ohc=2uc1wuTLfVAAb6VwGuX&_nc_ht=scontent.xx&oh=03_Q7cD1QEP0HPlME_Efo0keyMKfFRIOtfDOi4bhtfcHImCYXsPbQ&oe=664A0685>
<p><b>Mô hình cấp phát không liên tục, sử dụng bảng chỉ mục</b></p>
</center>
* **++Example:++** Cho đĩa cứng có dung lượng $32$ GB, kích thước 1 khối là $512$ Bytes. Hỏi kích thước một bảng chỉ mục là bao nhiêu nếu muốn quản lý file có kích thước lớn nhất là $256$ KB?
++**Đáp án**++
:::spoiler
$32$ GB $=25 \times 2^{10} \times 2^{10}$ KB $= 225$ KB $= 216$ khối $\implies$ có $216$ địa chỉ trên đĩa $\implies$ mỗi phần tử bảng chỉ mục cần $2$ byte. File kích thước $256$ KB $= 256 \times 1024$ byte $= 512$ khối $\implies$ bảng chỉ mục cần có $512$ phần tử $\implies$ một bảng chỉ mục chiếm hai khối data.
:::
###### c.3. Windows: File - Allocation Table (FAT)
**++Tổng kết kiến thức++**
:::warning
* Nếu mỗi mục trong bảng thư mục (directory table) chỉ chứa **số hiệu của khối đầu tiên**, thì các số hiệu khối còn lại của file sẽ được lưu trong một bảng gọi là **bảng cấp phát file (bảng FAT)**.
* Phương pháp này **dễ bảo vệ các số hiệu khối đã cấp cho file**, **random access file dễ dàng hơn**, **kích thước file dễ mở rộng** hơn nhưng **bảng FAT bị giới hạn bởi kích thước bộ nhớ** dành cho nó.
* Đây chính là cách mà hệ điều hành **MSDOS**, **OS/2**, **Windows (FAT)** sử dụng để quản lý file.
:::
**++Chi tiết kiến thức++**
* Definition:
* Enhanced version of linked list allocation: all pointers of linked list element stored in File-Allocation Table (FAT).
* Advantages:
* Resolve drawbacks of original linked list allocation method
* Random access file easier
* Have enough space to store a file
* If a block is lost, it doesn't create a big problem for remaining blocks.
* Disadvantages:
* Limits the size of FAT table to store many blocks.
* Example:
* Giả sử file test.txt được lưu trữ lần lượt ở 3 khối trên đĩa có số hiệu là: 217, 618, 339. Số hiệu khối đầu là 217 ghi trong một mục của bảng thư mục, các số hiệu khối tiếp theo là 618, 339 ghi trong bảng cấp phát file.
<center>
<img src = https://scontent.xx.fbcdn.net/v/t1.15752-9/427023332_912208470544298_2040689590992851851_n.png?_nc_cat=100&ccb=1-7&_nc_sid=5f2048&_nc_ohc=2TwzLc9aP2cAb5wiF6B&_nc_ht=scontent.xx&oh=03_Q7cD1QHAnX-K4bo9DAogknNT8SLdyphqs-OPHPG9pNiQFHhZrA&oe=664A1DEE>
<p><b>Mô hình cấp phát file không liên tục, sử dụng bảng FAT</b></p>
</center>
* Giả sử file A và file B được cấp phát gồm các khối theo thứ tự sau:
* file A: 4, 7, 2, 10, 12
* file B: 6, 3, 11, 14

Khi đó trong bảng thư mục sẽ có một mục lưu file A và số hiệu khối đầu của file A là 4. Tương tự có một mục lưu tên file B và số hiệu khối đầu của file B là 6. Các số hiệu khối tiếp theo của file A và file B lưu trong bảng cấp phát file (FAT).
<center>
<img src = https://scontent.xx.fbcdn.net/v/t1.15752-9/429901965_753504790116889_3138666800929328529_n.png?_nc_cat=104&ccb=1-7&_nc_sid=5f2048&_nc_ohc=hNcFPCXWvOIAb6l1WzP&_nc_ad=z-m&_nc_cid=0&_nc_ht=scontent.xx&oh=03_Q7cD1QGm-GqkqjKgIUxVvXeVdp6nhrbycG3urD9gFejQ0Ne4cQ&oe=664A35AA>
<img src = https://scontent.xx.fbcdn.net/v/t1.15752-9/431030135_1337032817007151_7917942761988389274_n.png?_nc_cat=102&ccb=1-7&_nc_sid=5f2048&_nc_ohc=FoOBy76vysMAb6RK0sl&_nc_ad=z-m&_nc_cid=0&_nc_ht=scontent.xx&oh=03_Q7cD1QFFzgK2-a1itU4rPv8hI0dqOcXf86-zWCxTkQBuLj5X9g&oe=664A1143>
<p><b>Mô hình cấp phát không liên tục, sử dụng bảng FAT cho cả hai file</b></p>
</center>
###### c.4. UNIX - based: Indexed Allocation (I - nodes)
**++Tổng kết kiến thức++**
:::warning
* Mỗi file được quản lý bằng một cấu trúc gọi là I-node, mỗi I-node gồm hai phần: phần thứ nhất lưu trữ thuộc tính file, phần thứ hai gồm 13 phần tử:
* Direct blocks: 10 phần tử đầu chứa 10 số hiệu khối đầu tiên của file (tức là lưu vị trí 10 pointers khác nhau mà mỗi pointers yêu cầu một kích thước nhất định trỏ đến 10 data blocks khác nhau)
* Single indirect: phần tử thứ 11 chứa số hiệu khối chứa bảng single.
* Double indirect: phần tử thứ 12 chứa số hiệu khối chứa bảng double.
* Triple indirect: phần tử thứ 13 chứa số hiệu khối chứa bảng triple.
* Trong đó, mỗi phần tử của **bảng triple** chứa số hiệu khối chứa **bảng double**, mỗi phần tử của **bảng double** chứa số hiệu khối của **bảng single** và mỗi phần tử của **bảng single** chứa số hiệu khối dữ liệu tiếp theo cấp cho file (tức là **bảng triple** chứa $n > 0$ pointers trỏ đến $n > 0$ **bảng double**, **bảng double** chứa $m > 0$ pointers trỏ đến $m > 0$ **bảng single**, **bảng single** chứa $k > 0$ pointers trỏ đến $k > 0$ **data blocks** tiếp theo của file).
:::danger
:large_blue_circle: **++Chú ý:++** Hệ điều hành **UNIX** sử dụng cấu trúc này và số phần tử của phần tử thứ hai, không nhất thiết là $13$ mà có thể thay đổi tùy theo phiên bản của **UNIX**.
:::
**++Chi tiết kiến thức++**
* Definition:
* Multilevel indexed allocation $\to$ cấp phát chỉ mục theo nhiều cấp.
* Direct blocks point to data blocks
* Indirect blocks point to address blocks containing pointers to data blocks (single indirect) or other address blocks (double or triple indirect).
* Advatages: Flexible for both large and small files
* Disadvantages: :x: None
<center>
<img src = https://scontent.xx.fbcdn.net/v/t1.15752-9/426758624_1123328568839785_4870981452532121591_n.png?_nc_cat=103&ccb=1-7&_nc_sid=5f2048&_nc_ohc=vhurOCPP7oAAb7DY2zU&_nc_ht=scontent.xx&oh=03_Q7cD1QFJLxWqe_-V_6wAuw1rwOX_rGZawW5EUJFmwVMda3io-g&oe=664A00F6>
<p>
<b>Cấu trúc một I-node trong bảng I-nodes</b>
</p>
</center>
###### d. Free - Space Management - `quản lý các khối trống`
:::info
:red_circle: Thông thường, có hai phương pháp mà hệ điều hành thường sử dụng để quản lý các khối trống là sử dụng danh sách liên kết hoặc bit vector (bit map).
:red_circle: Ở mức vật lý, sector là đơn vị lưu trữ nhỏ nhất của ổ đĩa. Mỗi sector trên HDD có kích thước là 512 bytes tùy theo nhà sản xuất $\to$ dùng để lưu trữ tập tin ở mức vật lý.
:red_circle: Ở mức quản lý hệ thống, mức logic, để tăng hiệu suất lưu trữ (vì nếu dùng sector $\to$ kích thước quá nhỏ để lưu trữ), một số hệ thống sẽ map nhiều sector liên tục lại thành khối cấp phát là cluster (khái niệm trên WINDOWS). Cluster là một khái niệm ở mức logic, là tập hợp các sector liên tiếp nhau. Một cluster có thể có $2, 4 , \dots, k^2$ sectors do nhà sản xuất định nghĩa khi họ format đĩa.
:red_circle: Ở mức hệ thống quản lý tập tin, disk block (nói chung chung, còn WINDOWS là cluster) là đơn vị cấp phát nhỏ nhất ở mức logic mà hệ thống sử dụng cho cấp phát thư mục.
:::
* **Bit Map** or **Bit Vector** (dãy bit) is a collection of bits, each of them corresponds to a **disk block**.
:::success
* Bit thứ $i = 1$ là khối thứ $i$ trống, bit thứ $i = 0$ là khối thứ $i$ đã được sử dụng (được cấp phát).
* Bit Vector được lưu trên một hoặc nhiều khối đĩa, khi cần sẽ đọc vào bộ nhớ để xử lý nhanh.
* Bit Vector ít tốn khối nhớ hơn là danh sách liên kết nhưng kích thước Bit Vector là cố định và hệ điều hành cần đồng bộ Bit Vector trong bộ nhớ và Bit Vector trên đĩa.
:::
* 1: free-block; 0: allocated block
* **Example of a ++free-space bit map++:** 000**11**0**111**00... (free-block: 3, 4, 6, 7, 8, ...)
* Xét lại ví dụ trên, nếu dùng vector bit, hãy tính kích thước vector bit.
:::spoiler **Answer**
Đĩa $20$M có $20 \times 2^{10}$ khối nên kích thước vector bit là: $$20 \times 2^{10} \quad \text{(bit)} = \displaystyle \frac{20 \times 2^{10}}{8 \times 2^{10}} \approx 3 \quad \text{(khối)}$$.
:::
* **Advantages:**
* Simplicity $\to$ đơn giản hơn so với việc duyệt disk block, không gian lưu trữ cũng ít.
* Efficiency
* **Disadvantages:**
* Need to load the entire bit map into the main memory $\to$ nếu kích thước của đĩa quá lớn, thì dãy bit rất lớn $\to$ hệ thống không thể nạp nổi bit map vào bộ nhớ chính $\to$ chỉ phù hợp với những hệ thống có kích thước đĩa không quá lớn.
* **Linked list** (danh sách liên kết) of free-blocks: a free-block points to its next free-block
:::success
* Mỗi nút trong danh sách liên kết là một khối chứa một bảng gồm các số hiệu khối trống, phần tử cuối của bảng lưu số hiệu khối tiếp theo trong danh sách.
* **Nhận xét:** tốn khá nhiều khối nhớ cho danh sách liên kết nếu đĩa hoàn toàn trống, nhưng sẽ ít tốn khối nhớ cho danh sách liên kết nếu đĩa gần đầy.
:::
* Disadvantages:
* Free - block traversing $\to$ quản lý linked list bằng file mà không có sự hỗ trợ của FAT (bảng này sẽ lưu các truy vết của từng nodes dưới dạng index trong linked list nên có thể truy xuất từng nodes dễ dàng), bắt buộc hệ thống phải duyệt tất cả các blocks mà không có duyệt tuần tự $\implies$ vấn đề này không nghiêm trọng vì chúng ta không cần duyệt các khối trống kế tiếp khi ta đã tìm thấy khối trống đầu tiên (vì hệ thống sẽ lấy khối trống đầu tiên ra để cấp phát cho file) $\to$ không có nhu cầu duyệt hết các linked lists đó.
* **++Example:++**
* Giả sử khối đầu tiên trong danh sách liên kết là khối $2$. Trong khối $2$ lưu các số $75$, $53$, $70$, $59$ là các số hiệu khối trống, các khối $3$ là khối chứa bảng số hiệu khối trống tiếp theo ... Hệ điều hành chỉ cần biết số hiệu khối đầu tiên của danh sách liên kết.
<center>
<img src = https://scontent.xx.fbcdn.net/v/t1.15752-9/431058651_1222243172493924_5433836327715780725_n.png?_nc_cat=103&ccb=1-7&_nc_sid=5f2048&_nc_ohc=BNmBfcNA6woAb48dYTs&_nc_ad=z-m&_nc_cid=0&_nc_ht=scontent.xx&oh=03_Q7cD1QGTb6f1PG6HRD7m-_1vrE-Gk1_m8NCZxmEJZu9jKeUwug&oe=664A32AF>
</center>
* Một đĩa $20$ M, dùng khối có kích thước $1$ K. Để quản lý đĩa này, nếu đĩa hoàn toàn trống thì danh sách liên kết cần bao nhiêu khối (số nút tối đa của danh sách liên kết) ?
**++Answer++**
:::spoiler
Ta có: $20$ M = $20 \times 2^{10}$ khối $\approx 2^{15}$ khối $\implies$ cần dùng $16$ bit $= 2$ byte để lưu một số hiệu khối $\implies 1$ khối $= 1024$ byte lưu được $511$ số hiệu khối trống $\implies$ để quản lý đĩa có $20$ M hoàn toàn trống, danh sách liên kết cần $\displaystyle \frac{20 \times 2^{10}}{511} \approx 40$ khối.
:::
<center>
<img src = https://scontent.xx.fbcdn.net/v/t1.15752-9/434844120_1399532514064764_8457835539151226671_n.png?_nc_cat=106&ccb=1-7&_nc_sid=5f2048&_nc_ohc=zKATuQHK8yYAb5i6Bxg&_nc_ad=z-m&_nc_cid=0&_nc_ht=scontent.xx&oh=03_Q7cD1QH-lQZtrpNGvjxcAbK74IUZHqXIu-jcv1mqZDerMWqreA&oe=664AC324>
<p><b>Quản lý danh sách các khối trống sử dụng danh sách liên kết</b></p>
</center>
* Giả sử khối đĩa $1$ KB và một số hiệu khối đĩa là $32$ bit thì một khối đĩa có thể ghi được $256$ số hiệu $-1$ khối đĩa trống.
<center>
<img src = https://scontent.xx.fbcdn.net/v/t1.15752-9/429980769_1416507675901055_6496786654569558973_n.png?_nc_cat=109&ccb=1-7&_nc_sid=5f2048&_nc_ohc=wYTTvHaSPTwAb4dn9g9&_nc_ad=z-m&_nc_cid=0&_nc_ht=scontent.xx&oh=03_Q7cD1QFKfdyAJiruAuz2KXU6lGpdJsyAvfq6a_cZtuTUoF34Lg&oe=664A2898>
<p><b>Quản lý danh sách các khối trống sử dụng danh sách liên kết và vector bit</b></p>
</center>
* **Grouping** $n$ free-blocks together
* First block of the group contains addresses of all free-blocks
* The block (n-1) points to another n-free-blocks
* **Counting** $n$ contiguous free-blocks following a block chosen as the first block
* Each element of the free-block linked list contains
* its address
* the number of its next contiguous free-block ($n$)
##### 2.2. Directory Implementation - `quản lý cài đặt thư mục`
* **Linear linked list of filenames** (filenames là tập tin đại diện tên tập tin / thư mục đó) $\to$ cách thường được sử dụng nhiều nhất
* Each entry in the list points to its data blocks, and the next entry.
* Disadvantages:
* Linear searching for files $\to$ tốc độ truy xuất kém nếu files đó nằm ở cuối danh sách liên kết.
* **Hashed table** (có hai cột là ==**KEY**== và ==**VALUES**==) used along with a **linked list** to optimize searching
* Each filename will be hashed and put in the hash table as a key (khóa lưu giá trị con trỏ tìm kiếm ra file).
* A value is associated with a key for finding the corresponding file.
<center>
<img src = https://scontent.xx.fbcdn.net/v/t1.15752-9/429812105_777868164243822_5300029891939887865_n.png?_nc_cat=107&ccb=1-7&_nc_sid=5f2048&_nc_ohc=uKhuyT1QjDYAb4cXrwR&_nc_ad=z-m&_nc_cid=0&_nc_ht=scontent.xx&oh=03_Q7cD1QGtY69nTgI7HoqkQqbuIevbYH11Kl9ZHLmroj6Xml9UaA&oe=664A0517>
<p><b>Cơ chế lưu trữ và truy xuất files của thư mục</b></p>
</center>
#### 3. File System Structure
* Mỗi file system sẽ có file system structure khác nhau. Hệ thống tập tin sẽ được cài trên một partition nào đó của ổ cứng hoặc là cài trên một ổ đĩa logic.
* Phân biệt khái niệm `Disk Partition` và `Logical Drive` ?
##### a. Disk Layout
* **Master Boot Record (MBR)** resides on the first sector of any hard disk $\to$ sử dụng hệ thống tập tin **NTFS**, **FAT**, **ext4**, ... nếu ổ đĩa đó chuẩn theo phân vùng cũ của **MBR** thì luôn luôn có sector đầu tiên chứa **MBR** (độc lập với việc cài file system hay hệ điều hành do nhà sản xuất đĩa lập trình sẵn)
* **Master Boot Record (MBR)** contains information for OS booting, also including the program that reads **boot sector** record of the disk partition `(chia tối đa được 4 partition: primary partition (dùng để cài hệ điều hành) và extended partition (chia thêm ổ đĩa logic để lưu trữ dữ liệu))` containing OS
$\to$ chứa thông tin phân vùng để quản lý phân vùng của toàn bộ ổ đĩa, phân vùng nào đang cài đặt hệ điều hành, không những chứa thông tin quản lý mà còn chứa đoạn mã chương trình đặc biệt để kích hoạt phân vùng đang chạy hệ điều hành.
<center>
<img src = https://scontent.xx.fbcdn.net/v/t1.15752-9/429913676_923139972631531_3366711852591931244_n.png?_nc_cat=107&ccb=1-7&_nc_sid=5f2048&_nc_ohc=U3rKHz9L15cAb4VdO5H&_nc_ad=z-m&_nc_cid=0&_nc_ht=scontent.xx&oh=03_Q7cD1QFAZqqv2MDeoeVKas9FMQgJFkvkKozvpli_C6g3ziIY5A&oe=664A1B76>
<p><b>Example of a disk layout (general format)</b></p>
</center>
* *Quá trình boot hệ điều hành dựa trên BIOS*
* Đầu tiên, BIOS phải khởi động chương trình trong ROM (kiểm tra thiết bị ...) $\to$ kích hoạt programs nằm trong MBR $\to$ programs trong MBR chạy lên kiểm tra phân vùng xem có partition nào đang active, chứa hệ điều hành (vì nếu chưa có phân vùng chứa hệ điều hành thì có nghĩa là máy chưa cài HĐH nên không thể hoạt động) $\to$ tìm ra phân vùng $X$ đang active chứa hệ điều hành có thể dùng để boot hệ điều hành vào $\to$ code kích hoạt programs nằm trong **Boot Sector** (là chương trình nằm đầu phân vùng có cài hệ điều hành, sử dụng để boot Hệ điều hành vào Main Memory) $\to$ programs trong Boot Sector boot hệ điều hành vào trong máy tính $\to$ giao quyền cho HĐH nắm quyền hệ thống của mình.
* Tất cả partition ổ đĩa của hệ thống phải có 1 phân vùng active chứa hệ điều hành, các partition còn lại dù không chứa hệ điều hành thì phải được format theo định dạng của một file system nào đó thì mới được đưa vào sử dụng.
<center>
<img src = https://scontent.xx.fbcdn.net/v/t1.15752-9/429880416_3371875019776674_6662444520604615326_n.png?_nc_cat=111&ccb=1-7&_nc_sid=5f2048&_nc_ohc=hGn8r2DtoekAb7t9KFc&_nc_ad=z-m&_nc_cid=0&_nc_ht=scontent.xx&oh=03_Q7cD1QH5Dj5stwc862SH6FFArPoiuQiB0ASBL6jmxIfqCBrW_g&oe=664A2E7F>
</center>
* *Phương pháp tổ chức quản lý đĩa bằng NTFS (Master File Table - WINDOWS)*
<center>
<img src = https://scontent.xx.fbcdn.net/v/t1.15752-9/431695100_921222936365227_8388155498738280770_n.png?_nc_cat=106&ccb=1-7&_nc_sid=5f2048&_nc_ohc=DAD4RTT0rQkAb6Ghd6U&_nc_ad=z-m&_nc_cid=0&_nc_ht=scontent.xx&oh=03_Q7cD1QFNZunrSK1PjQtwdjoRAelLIoOpTWOaP2Y7an0BMSNA1A&oe=664A08DB>
<p><b>Example of disk layout (Windows format)</b></p>
</center>
* *Phương pháp tổ chức quản lý đĩa bằng I-nodes (LINUX / UNIX)*
* MBR (Master Boot Record): là sector đầu tiên chứa thông tin về đĩa.
* Partition Table: bảng phân vùng chứa các thông tin về mỗi phân vùng.
* Mỗi phân vùng được tổ chức thành các phần sau: boot block, super block, free-space mgmt, i-nodes, root dir, files and directories. Trong đó, I-nodes là bảng I-nodes gồm nhiều mục, mỗi mục gọi là một i-node, chứa một cấu trúc i-node ghi thông tin của một file. Mỗi mục trong bảng thư mục gốc (root dir) ghi tên file và số hiệu i-nodes của file.
* Phương pháp này tương đối linh động và hiệu quả khi quản lý những hệ thống file lớn.
* Ví dụ: hệ điều hành muốn đọc file ./usr/ast/mbox, trước tiên tìm tên thư mục "usr" trong bảng thư mục gốc (root dir), và nhận thấy thư mục "usr" có i-nodes là $6$. Tiếp theo truy xuất phần tử i-node thứ $6$ trong bảng i-nodes, lấy được số hiệu khối đầu của "usr" là $132$, khối này sẽ chứa bảng thư mục con (sub dir) của "usr". Tiếp theo tìm tên thư mục "ast" trong bảng thư mục con của "usr", và tìm được thư mục "ast" của i-nodes là $26$. Tiếp theo, truy xuất phần tử i-node thứ $26$ trong bảng i-nodes, lấy được số hiệu khối đầu của "ast" là $406$, khối này sẽ chứa bảng thư mục con của "ast". Tiếp theo, tìm tên file "mbox" trong bảng thư mục con này, và tìm được file "mbox" có i-nodes là $60$. Truy xuất phần tử i-node thứ $60$ trong bảng i-nodes, lấy được các số hiệu khối của file "mbox".
<center>
<img src = https://scontent.xx.fbcdn.net/v/t1.15752-9/431507238_1481413115921852_309154596745772566_n.png?_nc_cat=107&ccb=1-7&_nc_sid=5f2048&_nc_ohc=RZabTthbFF0Ab4IVFdu&_nc_ad=z-m&_nc_cid=0&_nc_ht=scontent.xx&oh=03_Q7cD1QEhEYS65ojh6RFx0XezqhPOp_bDnb1cimip1Dtu0h2b1Q&oe=664A15D5>
<p><b>Mô hình cấp phát không liên tục, sử dụng bảng i-nodes chi tiết</b></p>
<img src = https://scontent.xx.fbcdn.net/v/t1.15752-9/429844646_1477021903167341_6641415324347340346_n.png?_nc_cat=110&ccb=1-7&_nc_sid=5f2048&_nc_ohc=u2m7iTQ56GwAb5w8BCi&_nc_ad=z-m&_nc_cid=0&_nc_ht=scontent.xx&oh=03_Q7cD1QGUAWD-xVZH3HQ4nKD1KqyVIFKXmXe_pTOOtKOBZcORTg&oe=664A051C>
<p><b>Example of disk layout (general Unix format)</b></p>
</center>
##### b. Master Boot Record
<center>
<img src = https://scontent.xx.fbcdn.net/v/t1.15752-9/429470496_1650738588996973_6897168856737182792_n.png?_nc_cat=101&ccb=1-7&_nc_sid=5f2048&_nc_ohc=tOQZK4Np1EkAb6ramGe&_nc_ad=z-m&_nc_cid=0&_nc_ht=scontent.xx&oh=03_Q7cD1QFeVtm9WiJMdNba9aciLNUZqjrpfs4UATkBqlJMmKlBNQ&oe=664A0B62>
<img src = https://scontent.xx.fbcdn.net/v/t1.15752-9/429501622_721585620177567_5280191846767388998_n.png?_nc_cat=109&ccb=1-7&_nc_sid=5f2048&_nc_ohc=53sovuFnS7wAb6vbn-O&_nc_ad=z-m&_nc_cid=0&_nc_ht=scontent.xx&oh=03_Q7cD1QE-CWnPOojijAlSxebgREdalt2pES1DI8Pzh4I_56kzSA&oe=664A26EF>
</center>

##### c. FAT Structure (hệ thống tập tin của MSDOS / Windows)
* **FAT12**: $32$ MB
* **FAT16**: $4$ GB
* **FAT32**: $8$ TB
<center>
<img src = https://scontent.xx.fbcdn.net/v/t1.15752-9/429468518_380969558053864_587495093184231809_n.png?_nc_cat=105&ccb=1-7&_nc_sid=5f2048&_nc_ohc=DNlzGlMOOcMAb7e2E9Z&_nc_ad=z-m&_nc_cid=0&_nc_ht=scontent.xx&oh=03_Q7cD1QEZq6QjWtecoXMmnv9Sn1lMkXrdANZ8u4QqOW631edm8A&oe=664A0572>
<p><b>FAT Structure</b></p>
</center>
* Hệ điều hành MSDOS hoặc Windows (sử dụng hệ thồng FAT) sẽ quản lý hệ thống tập tin thông qua 3 cấu trúc sau: Boot Sector, bảng FAT, bảng Root directory.
* **++Boot Sector:++** Ở sector đầu tiên, track 0, side 0 của đĩa mềm, đối với đĩa cứng thì vị trí này là bảng partition, rồi mới tới boot sector của partition thứ nhất, đối với các partition khác, boot sector là sector đầy tiên. Boot Sector chứa bảng tham số đĩa BPB (Bios Parameter Block) và chứa đoạn mã boot dùng để nạp các file hệ thống, boot sector hợp lệ phải có giá trị AA55 ở offset 1FE. Trên máy tính IBM PC sau khi thực hiện thao tác POST (Power On Self Test), ROM BIOS tìm boot sector hợp lệ, đọc boot sector vào địa chỉ 0X7C00, gán CS=0000h, IP=7C00h và cho thực thi lệnh đầu tiên trong boot sector (lệnh JMP). Boot sector có cấu trúc như sau:
| Offset(hex) | Size (byte) | Content | Giải thích |
|:-----------:|:-----------:|:---------------:|:--------------------------------------------------------------------------------------------------:|
| 00 | 3 | JMP | Lệnh nhảy đến đầu đoạn mã boot |
| 03 | 8 | Version | Phiên bản hệ điều hành |
| 0B | 2 | SectSiz | số byte/một sector, thường là 512 (đây là bắt đầu của BPB) |
| 0D | 1 | ClustSize | số sector/một cluster (khác 0) |
| 0E | 2 | ResSecs | số sector dành riêng trước bảng FAT, tính luôn boot sector (đối với FAT12, FAT16 = 1, FAT32 = 20h) |
| 10 | 1 | FatCnt | Số bảng FAT (thường là 2) |
| 11 | 2 | RootSiz | Số mục trong bảng ROOT DIR |
| 13 | 2 | TotSecs | Tổng số sector trên đĩa hay trên một partition ($\leq 65535$) |
| 15 | 1 | MediaDescriptor | Byte nhận dạng đĩa (F8: đĩa cứng, F0: $1.44$ MB) |
| 16 | 2 | FatSize | Số sector / một bảng FAT ($\leq 65535$), FAT32 = 0 |
| 18 | 2 | TrkSecs | Số sector/một track |
| 1A | 2 | HeadCnt | Số đầu đọc |
| 1C | 4 | HidnSecs | Số sector ẩn (ở giữa bảng partition và partion) |
| 20 | 4 | BigTotSecs | Tổng số sector trên đĩa hay trên một partition ($> 65535$) |
| 24 | 4 | BigFatSize | Số sector/một bảng FAT ($> 65535$) |
| ... | ... | ... | ... |
| 1D | | | (Kết thúc BPB) |
| 1E | | | đầu đoạn mã boot |
| ... | | | ... |
| 1FF | | | cuối đoạn mã boot |
<center><p><b>Cấu trúc một boot sector</b></p></center>
* **++Bảng FAT:++** Sau Boot Sector là bảng FAT (File Allocation Table), thường có hai bảng FAT để an toàn. Mỗi mục của FAT quản lý một khối (cluster) dữ liệu (khối dữ liệu được đánh số bắt đầu từ 2). Hai mục đầu tiên của bảng FAT chứa thông tin mô tả loại đĩa. Kích thước khối được lưu trong boot sector thông thường từ 1 đến 8 sector. Có ba loại FAT là: FAT12, FAT16, FAT32. FAT12 (mỗi mục trong bảng FAT12 có kích thước là 12bits) có thể quản lý được $2^{12} = 4096$ khối, FAT16 có thể quản lý $2^{16} = 64$ K khối, FAT32 có thể quản lý $2^{32} =4$G khối trên một partition. Các giá trị có thể có trong một entry của bảng FAT.
| (0)000 | Cluster còn trống |
| --------------- | ---------------------------------------------------------------- |
| (0)002 - (F)FEF | Cluster chứa dữ liệu của File, giá trị này là số hiệu cluster kế |
| (F)FF0 - (F)FF6 | Dành riêng, không dùng |
| (F)FF7 | Cluster hỏng |
| (F)FF8 - (F)FFF | Cluster cuối cùng của chuỗi (kết thúc file) |
<center><p><b>Cấu trúc một mục (entry) trong bảng FAT</b></p></center>
* **++Bảng ROOT DIR++** (**RDET** - bảng thư mục gốc): nằm ngay sau bảng FAT, và mỗi mục của bảng **DIR** là $32$ byte. Khi hệ thống mở một File / Directory, MS-DOS tìm tên File / Directory trong bảng **ROOT DIR (RDET)**, lấy số hiệu khối đầu đã cấp cho file/directory và tìm số hiệu khối tiếp theo trong bảng FAT.
<center>
<img src = https://scontent.xx.fbcdn.net/v/t1.15752-9/429810078_868623421683275_5501409216960410227_n.png?_nc_cat=101&ccb=1-7&_nc_sid=5f2048&_nc_ohc=A3AmyrMb4iYAb7ssnsQ&_nc_ad=z-m&_nc_cid=0&_nc_ht=scontent.xx&oh=03_Q7cD1QEjZ3mlfzI6oTMutDedilGFekGqd17gaQithwZZnheEmw&oe=664A334B>
</center>

| Kích thước | Thuộc tính |
|:----------:|:------------------------------------------------------------------------------------:|
| 8 byte | Tên File |
| 3 byte | Phần mở rộng |
| 1 byte | Thuộc tính: A-D-V-S-H-R |
| 10 byte | Dành riêng để sử dụng sau này |
| 2 byte | Giờ : 5 bit cho giờ, 6 bit cho phút, 5 bit cho giây (thiếu 1, nên lưu đơn vị 2 giây) |
| 2 byte | Ngày : 7 bit cho năm (từ 1980), 4 bit cho tháng, 5 bit cho ngày |
| 2 byte | Số hiệu khối đầu tiên của file |
| 4 byte | Kích thước File |
<center><p><b>Cấu trúc một mục trong bảng ROOT DIR / SUB DIR</b></p></center>

Giá trị của byte thuộc tính:
* 1 : File chỉ đọc (Read-only)
* 2 : File ẩn (Hidden)
* 4 : File hệ thống (System)
* 8 : Nhãn đĩa (Volume)
* 16 : Thư mục con (Directory)
* 32 : File chưa được sao lưu (Archive)
* Example: Xét đĩa $1.4$ **MB**, được format dưới hệ điều hành **MS-DOS / WINDOWS (FAT12)** gồm có $2880$ sectors ($1.4$ **MB** $\geq \displaystyle \frac{1.4 \times 1024 \times 1024}{512} = 2880$ sector), và 1 khối (cluster) = 1 sector nên mỗi mục của bảng FAT chỉ cần $12$ bit.
* Sector đầu tiên là **boot sector**, 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.
* 18 sector tiếp theo là **FAT (FAT12)**, gồm 2 bảng, mỗi bảng có 9 sector (có $3072$ mục, nếu $8$ sector thì không đủ để quản lý $2880$ khối). Ba bytes đầu tiên của mỗi bảng **FAT** lưu số hiệu loại đĩa ($240, 255, 255$).
* 14 sector kế tiếp chứa **bảng thư mục gốc (bảng ROOT DIR)**.
* Các sector còn lại dùng để **lưu dữ liệu (DATA)**, cluster đánh số từ 2.
<center>
<img src = https://scontent.xx.fbcdn.net/v/t1.15752-9/429908818_400680292571938_8793222105358043517_n.png?_nc_cat=111&ccb=1-7&_nc_sid=5f2048&_nc_ohc=L0AHXWjMY_EAb5DzPel&_nc_ad=z-m&_nc_cid=0&_nc_ht=scontent.xx&oh=03_Q7cD1QFxBdg8Cey-dnH1p7c8ljYFXOJhfYFJd4XpM0n-nGXzQQ&oe=664A287C>
<p><b>Cấu trúc lưu trữ dữ liệu dùng FAT12</b></p>
</center>

* **++==Cấu trúc ROOT DIR==++**
<center>
<img src = https://scontent.xx.fbcdn.net/v/t1.15752-9/429849981_7308816325864734_8096059427112529079_n.png?_nc_cat=100&ccb=1-7&_nc_sid=5f2048&_nc_ohc=iSk1XhsFMUMAb5f7CAn&_nc_ad=z-m&_nc_cid=0&_nc_ht=scontent.xx&oh=03_Q7cD1QHx0t6uiNrHK0amA2LkdbWpWt-Adr7VM7KcXg8DfcmpTQ&oe=664A1ECF>
<p><b>Cấu trúc một mục trong bảng ROOT DIR</b></p>
</center>

Ta có: Bảng DIR $= 14$ sectors ($1$ sectors $= 512$ bytes) $= 14 \times 512 = 7168$ bytes $= 224$ entry (mỗi entry $= 32$ bytes), $1$ sector $= 16$ entry
Đĩa $1.44$ **MB** ở thư mục gốc có tối đa $224$ file hoặc thư mục con. Nếu file có kích thước file $= 0$ thì số hiệu khối đầu $= 0$. Kí tự đầu của tên file có giá trị là $0$ (trống), dấu chấm (dành riêng cho DOS), **0xE5** (file đã bị xóa: khi xóa file, DOS sẽ điền kí tự **0xE5** vào kí tự đầu của file).
* **++==Cấu trúc bảng FAT==++**
<center>
<img src = https://scontent.xx.fbcdn.net/v/t1.15752-9/430409117_710268464594977_9037221319045557530_n.png?_nc_cat=110&ccb=1-7&_nc_sid=5f2048&_nc_ohc=viSRZ0ZsLeAAb4dG-r5&_nc_ad=z-m&_nc_cid=0&_nc_ht=scontent.xx&oh=03_Q7cD1QGvxdSIGaNaX4lqm6BPfxBCqAwcpB_kiH1Zu5mYMkUX5w&oe=664A0A5D>
<p><b>Cấu trúc bảng FAT12</b></p>
</center>

Ta có: Bảng **FAT12** $= 9$ sectors $= 4608$ bytes $= 3072$ entry (mỗi entry chiếm $12$ bit)
* Đọc/ghi FAT12
* Ví dụ: ghi vào entry 2 giá trị **F2Ah** và entry 3 giá trị **BC5h**. Do byte 0, 1, 2 lưu số hiệu đĩa, nên entry 2 sẽ được ghi vào byte thứ 3, 4 và entry 3 sẽ được ghi vào byte thứ 4, 5. Cách ghi như sau:
<center><img src = https://scontent.xx.fbcdn.net/v/t1.15752-9/429834673_1596739054494108_713508126266441072_n.png?_nc_cat=111&ccb=1-7&_nc_sid=5f2048&_nc_ohc=RfwXQXv8RtMAb4MdWnX&_nc_ad=z-m&_nc_cid=0&_nc_ht=scontent.xx&oh=03_Q7cD1QF2GsJs8_IWHvADlhRWHp6C1ZXtO6sSJ1TlUNnIuv8Eeg&oe=664A1D14></center>

			unsigned char fat[512 * 9]; //mảng chứa bảng fat đọc từ đĩa
			void WriteFat(unsigned new_fat, unsigned k) // ghi giá trị new_fat vào entry thứ k = 2, 3, 4, ..., 3071
			{
				unsigned i = k * 3 / 2; // entry k sẽ được ghi vào byte thứ i và i + 1
				ìf (k % 2 == 0) // k chẵn
				{
					// đặt 8 bits cuối của new_fat vào byte thứ i
					fat[i] = new_fat&0x0FF;
					// đặt 4 bits cao của new_fat vào 4 bits cuối của byte thứ i + 1
					fat[i + 1] = (fat[i + 1]&0xF0) | (new_fat >> 8);
				}
				else // k lẻ
				{
					// đặt 8 bits cao vào byte thứ i + 1
					fat[i + 1] = new_fat >> 4;
					// đặt 4 bits thấp vào 4 bits cao của byte thứ i
					fat[i] = ((new_fat&0x0F) << 4) | (fat[i]&0x0F);
				}
			}

* Ví dụ: giả sử new_fat = 1AB, lưu vào entry k = 7 $\to$ lưu vào byte i = 10 và i + 1 = 11
| 9 | 10 | 11 | Ghi chú |
|:---:|:---:|:---:|:---------------:|
| AB | CD | EF | (trước khi ghi) |
| AB | BD | 1A | (sau khi ghi) |

				unsigned ReadFat (unsigned k) // Đọc giá trị của entry thứ k (k>=2)
				{
					unsigned i=k*3/2; //entry thứ k ở byte thứ i, i+1
					unsigned val_fat=(fat[i+1]<<8) | fat[i]; // hoặc val_fat=fat[i+1]*256+fat[i]; 
					if (val_fat%2==0) 
						val_fat=val_fat & 0x0FFF;
					else 
						val_fat=val_fat>>4;
					return val_fat;
				}

* Đọc/ghi giờ, phút, giây:
time(2 byte) = 5 bit giờ, 6 bit phút, 5 bit giây (thiếu 1, nên lưu đơn vị 2 giây)
* Ghi:

			time = (h <<11)|(m<<5)|(s>>1)

* Đọc:

			h = (time>>11);
			m = (time>>5)&0x3F;
			s = (time&0x1F)<<1;

* Đọc/ghi ngày, tháng, năm
date (2 byte) = 7 bit cho năm (từ 1980), 4 bit cho tháng, 5 bit cho ngày
* Ghi:

			y -= 1980;
			date = (y << 9) | (m << 5) | d;

* Đọc:

			y = (date >> 9) + 1980;
			m = (date >> 5)&0xF;
			d = date&0x1F;

##### d. NTFS Structure (Hệ thống tập tin của Windows NT)
* Sử dụng hệ thống NTFS, kích thước File tối đa trong NTFS là 232 cluster. Cấu trúc volume của NTFS như sau: partition boot sector, Master File Table (MFT), system files (các tập tin hệ thống), file area (vùng dữ liệu)
* **++Partition Boot Sector:++** là sector khởi động của partition ($\leq 16$ sector) gồm các thông tin về cấu trúc của volume, cấu trúc của hệ thống File và mã nguồn khởi động.
* **++Master File Table (MFT):++** là bảng lưu các thông tin về tất cả các file và thư mục của volume **NTFS** này cũng như danh sách các khối trống. **MFT** được tổ chức thành nhiều dòng, mỗi dòng lưu những thuộc tính cho một file hoặc một thư mục trên volume. Nếu kích thước file nhỏ thì toàn bộ nội dung của file được lưu trong dòng này, còn nếu kích thước file lớn, không thể lưu dữ liệu toàn bộ nội dung mà chỉ lưu indexed pointers trỏ đến những vùng extended khác nhau, những vùng extended này chính là những data blocks chứa dữ liệu file đó.
* **++Systems files:++** có kích thước khoảng $1$ Mb bao gồm:
* MFT2: bản sao của MFT
* Log file: thông tin dùng cho việc backup & restore (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.
| Kiểu thuộc tính | Mô tả |
| -------------------- | -------------------------------------------------------------------------------------- |
| Thông tin chuẩn | Bao gồm các thuộc tính truy xuất (chỉ đọc, đọc / ghi), nhãn thời gian, chỉ số liên kết |
| Danh sách thuộc tính | sử dụng khi tất cả thuộc tính vượt quá 1 dòng của MFT |
| Tên File | |
| Mô tả an toàn | thông tin về người sở hữu và truy cập |
| Dữ liệu | |
| Chỉ mục gốc | dùng cho thư mục |
| Chỉ mục định vị | dùng cho thư mục |
| Thông tin volume | như tên version và tên volume |
| Bitmap | hiện các dòng trong MFT |
<center><p><b>Các kiểu thuộc tính của File và thư mục trong Windows NTFS</b></p></center>
* **++File area:++** vùng chứa dữ liệu bình thường của người dùng.
<center>
<img src = https://scontent.xx.fbcdn.net/v/t1.15752-9/429449557_1095900304867641_5387856642645650534_n.png?_nc_cat=106&ccb=1-7&_nc_sid=5f2048&_nc_ohc=ty3yINe81qoAb5MgQQt&_nc_ad=z-m&_nc_cid=0&_nc_ht=scontent.xx&oh=03_Q7cD1QFGDggvMdlxjQv04HTm_Og9QLv2rtj_zbtu86uS_S076Q&oe=664A2BEB>
</center>
##### e. UNIX I-node Structure (Hệ thống file của UNIX)
* Single Indirect: $256$ **KB**
* Double Indirect: $256 \times 256 = 65$ **MB**
* Triple Indirect: $256 \times 256 \times 256 = 16$ **GB**
<center>
<img src = https://scontent.xx.fbcdn.net/v/t1.15752-9/429507703_3505273156400081_7298259447049624451_n.png?_nc_cat=111&ccb=1-7&_nc_sid=5f2048&_nc_ohc=VujctuGy16AAb6zfCCa&_nc_ad=z-m&_nc_cid=0&_nc_ht=scontent.xx&oh=03_Q7cD1QEscy5Q_iDW30LeIg3wpjREVXeWpFa-tDcBtd4nv1vjDg&oe=664A14AF>
<img src = https://scontent.xx.fbcdn.net/v/t1.15752-9/423944354_3643857779219562_576167681518107955_n.png?_nc_cat=103&ccb=1-7&_nc_sid=5f2048&_nc_ohc=wVE9BePQY1cAb5ObRl6&_nc_ad=z-m&_nc_cid=0&_nc_ht=scontent.xx&oh=03_Q7cD1QGf3qXv3jE7R6YFNZTLyx8WJ6rGc8Rd0tBk0WxFQ6vulw&oe=664A0034>
</center>
* Hệ thống file của UNIX thông thường được cài đặt trên đĩa gồm các khối theo thứ tự sau: boot block, super block, i-nodes, file and directories (các khối dữ liệu).
* **++Boot Blocks:++** chứa đoạn mã khởi động của hệ thống.
* ++**Super Blocks:**++ chứa thông tin về toàn bộ hệ thống file, bao gồm:
* Kích thước của toàn bộ hệ thống file.
* Địa chỉ của khối dữ liệu đầu tiên.
* Số lượng khối trống và danh sách khối trống.
* Số lượng I-node trống và danh sách I-node trống.
* Ngày super block được cập nhật sau cùng.
* Tên của hệ thống file.
Nếu khối này bị hỏng, hệ thống file 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 của super block đượ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. Các I-nodes được đánh số từ 1, mỗi I-node có độ dài 64 bytes và mô tả cho một file duy nhất, chứa thuộc tính và địa chỉ các khối lưu trữ trên đĩa của file. Tất cả file và thư mục được lưu trữ ở các khối dữ liệu.
* ++**I-nodes:**++ là bảng I-nodes gồm nhiều mục, mỗi mục gọi là một i-node, chứa một cấu trúc i-node ghi thông tin của một file. Mỗi mục trong bảng thư mục gốc (root dir) ghi tên file và số hiệu i-nodes của file.
##### f. In - Memory File System Structure
* Đa số hệ điều hành đều yêu cầu tiến trình dùng chức năng tường minh khi mở files trước khi thao tác (đọc/ghi...) thực thi trên file.
<center>
<img src = https://scontent.xx.fbcdn.net/v/t1.15752-9/429868855_375417238744537_1035199261785787074_n.png?_nc_cat=111&ccb=1-7&_nc_sid=5f2048&_nc_ohc=t3D2R9LmzCwAb7_mCmn&_nc_oc=AdiMaG2vaNuRKGbPwQJunCetkrSqHXLxBVksTBiDtVGTozXke3FhJWc3GPOiLd7HIaSMDw0aIiFTByO03g9fCf1f&_nc_ad=z-m&_nc_cid=0&_nc_ht=scontent.xx&oh=03_Q7cD1QG-diWikl7nqL8fMkHVtF71UmWjPjc3YOT_pGhRLWGxyg&oe=664A1DA7>
</center>

### III. Disk Storage
:::success
Phần này sẽ đi sâu hơn mức hệ điều hành, tức là mức phần cứng bên dưới, có nhiều thiết bị lưu trữ, nhưng chúng ta chỉ quan tâm đến thiết bị lưu trữ ổ đĩa.
Xem xét cấu trúc vật lý thực sự của ổ đĩa, lưu trữ dữ liệu ra làm sao, cấp phát / thu hồi các khối đĩa như thế nào ?
:::
#### 1. Disk Management
##### a. Disk Structure
* $8$ sectors (of $512$ bytes) per track
* $4$ tracks (or heads) per cylinder
* $7$ cylinders ($\Leftrightarrow 7$ tracks per head)

$\implies$ Total no. of sectors: $224$
$\implies$ Disk capacity: $\approx 112$ **KB** (trừ một số dung lượng dành cho một vài lý do đặc biệt khác)
* Đĩa cứng được định dạng thành các vòng tròn đồng tâm gọi là rãnh (track), mỗi rảnh được chia thành nhiều phần bằng nhau gọi là cung (sector). Một khối (cluster) gồm một hoặc nhiều cung và dữ liệu được đọc / ghi theo đơn vị khối. Việc sử dụng đơn vị khối để tăng hiệu quả trong việc đọc/ghi và giảm chi phí quản lý số địa chỉ trên đĩa. Ngoài ra khi đĩa cứng lớn, có thể chia thành nhiều phân vùng (partition), mỗi phân vùng gồm một số từ trụ(cyclinder) liên tiếp. Một từ trụ là tập hợp các rãnh cùng bán kính.

<center>
<img src = https://scontent.xx.fbcdn.net/v/t1.15752-9/423766141_285802161208424_5688079441809537666_n.png?_nc_cat=105&ccb=1-7&_nc_sid=5f2048&_nc_ohc=G4w8RPuVRrkAb5sELbL&_nc_ad=z-m&_nc_cid=0&_nc_ht=scontent.xx&oh=03_Q7cD1QEUDm6Z5QkUUSqRZ9ty7kec0F6Yz8ge-s_uE3YpxSulYg&oe=664A140A>
<img src = https://scontent.xx.fbcdn.net/v/t1.15752-9/431653189_370454825953870_2611410483135476326_n.png?_nc_cat=106&ccb=1-7&_nc_sid=5f2048&_nc_ohc=yZqX2R9XYxYAb4PgEwm&_nc_ad=z-m&_nc_cid=0&_nc_ht=scontent.xx&oh=03_Q7cD1QH4oDZmBkJ-vGjO5DIYaEKRLEFsHhC7zOw6ZH7rH6lOPg&oe=664777E8>
</center>

##### b. Disk Formatting
<center>
<img src = https://scontent.xx.fbcdn.net/v/t1.15752-9/429345272_7336314779764917_3135253431767219666_n.png?_nc_cat=109&ccb=1-7&_nc_sid=5f2048&_nc_ohc=NPlrKgZhqwUAb5JzpDR&_nc_ad=z-m&_nc_cid=0&_nc_ht=scontent.xx&oh=03_Q7cD1QGqGiFuzq-IH486YRzGE7mKXCT3ZXzcau4sZDBrdFVC2w&oe=664A24D8>
<img src = https://scontent.xx.fbcdn.net/v/t1.15752-9/431502992_6582832661819510_8611913893862416708_n.png?_nc_cat=102&ccb=1-7&_nc_sid=5f2048&_nc_ohc=5KpYXUw3CqEAb6b-V7l&_nc_ad=z-m&_nc_cid=0&_nc_ht=scontent.xx&oh=03_Q7cD1QGB6uTaJMQCg4LWpj2G-rcCMIBiSJNsoUWp6uUpNlossA&oe=66477971>
</center>

##### c. Disk Accessing
* Để truy xuất các khối trên đĩa, trước tiên phải di chuyển đầu đọc đến track thích hợp, thao tác này gọi là seek và thời gian để hoàn tất thao tác này 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à chuyển dữ liệu từ đĩa vào bộ nhớ chính, thời gian này 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 (seek time + latency time + transfer time). 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 cần đưa ra các thuật toán lập lịch dời đầu đọc sao cho tối ưu.
<center>
<img src = https://scontent.xx.fbcdn.net/v/t1.15752-9/429804592_2027717094289201_4142180512264177727_n.png?_nc_cat=110&ccb=1-7&_nc_sid=5f2048&_nc_ohc=iCm9NKB8ricAb7Jxvor&_nc_ad=z-m&_nc_cid=0&_nc_ht=scontent.xx&oh=03_Q7cD1QHPCk12I_wjtB6KTO2OgeX4ipWV3P8wEkPciwfVU7F2ZA&oe=664A0CC8>
<img src = https://scontent.xx.fbcdn.net/v/t1.15752-9/429473022_428900006248540_6223002279454450158_n.png?_nc_cat=100&ccb=1-7&_nc_sid=5f2048&_nc_ohc=gZLcCvMcgrIAb7WAgb4&_nc_ad=z-m&_nc_cid=0&_nc_ht=scontent.xx&oh=03_Q7cD1QHKJLVZiR3xNgzNmHfRFRG1OUvC-Fr8iUA2SF2eyyJO-A&oe=66477831>
</center>

* **CHS (Cylinder - Head - Sector)**
* Disk blocks located by a tuple of (cylinder | track, head, sector)
<center>
<img src = https://scontent.xx.fbcdn.net/v/t1.15752-9/429041996_906631024537830_2143068303300166767_n.png?_nc_cat=108&ccb=1-7&_nc_sid=5f2048&_nc_ohc=MDn3S380ONQAb5ZJg82&_nc_ad=z-m&_nc_cid=0&_nc_ht=scontent.xx&oh=03_Q7cD1QGUu6ggQj-JgqfwDmYNGB-gg2hK6fJtf9CCzJBw3_sL6Q&oe=664A3444>
</center>
* **LBA (Logical Block Addressing)**
* Disk blocks located by an integer index starting at 0.
<center>
<img src = https://scontent.xx.fbcdn.net/v/t1.15752-9/429487442_398051396396985_9097818009081908648_n.png?_nc_cat=106&ccb=1-7&_nc_sid=5f2048&_nc_ohc=SvK7irSyG4AAb41Yngb&_nc_ad=z-m&_nc_cid=0&_nc_ht=scontent.xx&oh=03_Q7cD1QG7gICyYSb4bJZslDcBkuaonUBW-WVmnLAQqUMRdNRunA&oe=664A1C91>
</center>
##### d. CHS - LBA Mapping
* **CHS to LBA address:** $LBA = (C \times N_{\text{heads}} + H) \times N_{\text{sectors}} + (S - 1)$
* **LBA to CHS address:**
* $C = \displaystyle \frac{LBA}{N_{\text{heads}} \times N_{\text{sectors}}}$
* $H = \displaystyle \frac{LBA}{N_{\text{sectors}}} \% N_{\text{heads}}$
* $S = (LBA \% N_{\text{sectors}}) + 1$
* Trong đó:
* $C$ : cylinders | track number
* $H$ : head number
* $S$ : sector number
* $N_{\text{heads}}$ : no.of heads | tracks per cylinder
* $N_{\text{sectors}}$ : no.of sectors per track
* Assume a hard disk having:
* $4$ heads / cylinder ($N_{\text{heads}}$)
* $8$ sectors / track ($N_{\text{sectors}}$)
* Example of LBA-CHS Mapping
<center>
<img src = https://scontent.xx.fbcdn.net/v/t1.15752-9/429474256_1505134980402739_8338776610265290813_n.png?_nc_cat=106&ccb=1-7&_nc_sid=5f2048&_nc_ohc=gOjIw5xQ9bMAb7dnUSS&_nc_ad=z-m&_nc_cid=0&_nc_ht=scontent.xx&oh=03_Q7cD1QF_oii5ek8Ju5_aRlI6iuXJ6t5NK5j3r61y7WrGu_2YqA&oe=664A0C53>
</center>
#### 2. Disk Scheduling Algorithms
##### a. Disk Access Time
<center>
<img src = https://scontent.xx.fbcdn.net/v/t1.15752-9/423568209_775216951188615_8474377021597757950_n.png?_nc_cat=107&ccb=1-7&_nc_sid=5f2048&_nc_ohc=9TQIuFzz6AwAb7_8dgh&_nc_ad=z-m&_nc_cid=0&_nc_ht=scontent.xx&oh=03_Q7cD1QEtRNmjXuB5_CEag47Ob6kcuFuDWduFKt1YD7wKfIfgEQ&oe=664A1103>
</center>

##### b. Disk Scheduling
* Disk Scheduling Algorithms
* FCFS (First-Come First-Served)
* SSTF (Shortest Seek Time First)
* SCAN (Elevator Algorithm)
* C-SCAN (Circular SCAN)
* LOOK (an optimized version of SCAN)
* C-LOOK (Circular LOOK)
##### c. FCFS (First - Come, First - Served)
* Thuật toán sẽ dời đầu đọc theo thứ tự đúng với thứ tự các khối cần đọc, thuật toán dễ lập trình nhưng chưa tốt.
* Example: cần phải đọc các khối theo thứ tự sau: $13, 2, 38, 17, 36, 7, 21$. Giả sử hiện tại đầu đọc đang ở vị trí $11$, thuật toán sẽ dời đầu đọc lần lượt đi qua các khối $11, 13, 2, 38, 17, 36, 7, 21$.
<center>
<img src = https://scontent.xx.fbcdn.net/v/t1.15752-9/431249853_415082460928789_3664396939731289037_n.png?_nc_cat=106&ccb=1-7&_nc_sid=5f2048&_nc_ohc=kLuKFQ1VSb4Ab489ZmD&_nc_ad=z-m&_nc_cid=0&_nc_ht=scontent.xx&oh=03_Q7cD1QFKqhplbFvYB-jrT1d1t1Qqu1mKeC3VL41A4Hlg2LDXqQ&oe=66476308>
</center>
##### d. SSTF (Shortest Seek Time First)
* Thuật toán sẽ di chuyển đầu đọc lần lượt đến các khối cần đọc theo vị trí gần với vị trí hiện hành của đầu đọc gần nhất.
* Example: cần đọc các khối như sau: $13, 2, 38, 17, 36, 7, 21$. Giả sử hiện tại đầu đọc đang ở vị trí $11$, thuật toán sẽ dời đầu đọc lần lượt đi qua các khối $13, 17, 21, 7, 2, 36, 38$
<center>
<img src = https://scontent.xx.fbcdn.net/v/t1.15752-9/431037280_376727215209191_1436904188958417307_n.png?_nc_cat=110&ccb=1-7&_nc_sid=5f2048&_nc_ohc=kxQrK9fcmooAb5cJbcO&_nc_ad=z-m&_nc_cid=0&_nc_ht=scontent.xx&oh=03_Q7cD1QE0avPX42DXKubHjYvHelLkd-oxSERlmWSewfo3kpa4eQ&oe=66477A5B>
</center>
##### e. SCAN
* Thuật toán sẽ di chuyển đầu đọc về một phía của đĩa và từ đó di chuyển qua phía kia.
* Example: cần đọc các khối như sau: $13, 2, 38, 17, 36, 7, 21$. Giả sử hiện tại đầu đọc đang ở vị trí $11$, đầu đọc lần lượt đi qua các khối: $13, 17, 21, 36, 38, 40, 7, 2, 0$
<center>
<img src = https://scontent.xx.fbcdn.net/v/t1.15752-9/429915633_938019077536921_1239343028687146858_n.png?_nc_cat=107&ccb=1-7&_nc_sid=5f2048&_nc_ohc=XC59uu8F3GcAb4DUUAq&_nc_ad=z-m&_nc_cid=0&_nc_ht=scontent.xx&oh=03_Q7cD1QGpG4t9zIBJifwmiyf58O29p9cFQtiWpIAWKEOvdvfeww&oe=66478D51>
</center>
##### f. C - SCAN
* Thuật toán này tương tự 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.
* Example: lấy lại ví dụ trên, khi đó thứ tự truy xuất các khối sẽ là $13, 17, 21, 36, 38, 40, 0, 2, 7$
<center>
<img src = https://scontent.xx.fbcdn.net/v/t1.15752-9/429786533_927231806077538_2310323184743153641_n.png?_nc_cat=109&ccb=1-7&_nc_sid=5f2048&_nc_ohc=OlQLhhpggoEAb68JcDB&_nc_oc=AdhrF3atOLZcrDy-1szT_aKnk9d4DYET17ge78o5W9rZ0cYTZM2PpqpsTxLRWl6y78whUjK4ZVnDSkezstvtpwnQ&_nc_ad=z-m&_nc_cid=0&_nc_ht=scontent.xx&oh=03_Q7cD1QHBdQmnJXTO1m-_yfGoiTauEM-Ufb9gkdfiOm9bAM1Hvg&oe=6647713E>
</center>
:::info
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. Thuật toán lập lịch phụ thuộc vào số khối 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.
:::
##### g. LOOK
* Example:
<center>
<img src = https://scontent.xx.fbcdn.net/v/t1.15752-9/431024561_1828511970909712_6823977013284341926_n.png?_nc_cat=107&ccb=1-7&_nc_sid=5f2048&_nc_ohc=JkucjRfI62UAb77NHBq&_nc_ad=z-m&_nc_cid=0&_nc_ht=scontent.xx&oh=03_Q7cD1QHkFHabjOf_naQTc7rGTq7mGmxag2ny-LHpLcq0jsZPWw&oe=66477E70>
</center>
##### h. C - LOOK
* Example:
<center>
<img src = https://scontent.xx.fbcdn.net/v/t1.15752-9/431185775_1215493809294591_4808554051520206871_n.png?_nc_cat=107&ccb=1-7&_nc_sid=5f2048&_nc_ohc=3Xey1FBuzdgAb4yFd4z&_nc_ad=z-m&_nc_cid=0&_nc_ht=scontent.xx&oh=03_Q7cD1QHLFleKUBL723omlerqFmQsiQ-aKNnFYrRlm-gUZxRsqg&oe=66479398>
</center>

---