# CHap. 10 - File system interface

> 課程內容 : 清華大學開放式課程 周志遠教授
> 參考書目 : Operating System Concepts (9th), Abraham Silberschatz, Peter Baer, Galvin, Greg Gagne
>
> 其他科目內容請參見 [[Here]](https://hackmd.io/@ChenZE/By4SOO6Jyl)

## Content

* [File concept](#File-concept)
* [1. File operations](#1-File-operations)
* [Access methods](#Access-methods)
* [1. Sequential access](#1-Sequential-access)
* [2. Direct access](#2-Direct-access)
* [3. Index access](#3-Index-access)
* [Directory structure](#Directory-structure)
* [1. Single-level directory](#1-Single-level-directory)
* [2. Two-level directory](#2-Two-level-directory)
* [3. Tree-structure directory](#3-Tree-structure-directory)
* [4. Acyclic graph directory](#4-Acyclic-graph-directory)
* [5. General graph directory](#5-General-graph-directory)
* [Mounting(掛載)](#Mounting掛載)
* [Sharing](#Sharing)
* [1. Access control list](#1-Access-control-list)

## File concept

檔案(file)是一個由 OS 建立的邏輯儲存單元(logical storage unit)，內容就是由一堆 bytes 所組成的資料，像是檔名等。由 OS 將儲存裝置(Ex: 硬碟/磁碟)上的對應位置的內容抽象化所形成。

檔案的屬性(attributes)是對檔案的描述方式，通常會有多種屬性提供使用者或 OS 使用。

* Identifier: 提供給 OS 的識別碼(non human readable)
* Name: 檔名
* Type: 檔案類型(副檔名)
* 副檔名其實在 file system 中沒有實質意義，只是用來提示 OS 可以用何種應用程式打開
* Location: 檔案位置
* Size: 檔案大小
* Protection
* Last-access/Last-update time

### 1. File operations

OS 對檔案的操作與運算包含以下幾種

* Create file
* Write file
* Read file
* Reposition with file
* 讓指標(read/write pointer)移動到檔案中的某個位置進行讀寫
* Delete file
* Truncate file

檔案管理方面，每個檔案被打開後都會有相關的紀錄。每個 process 打開檔案後都會有一個 open-file table 用來儲存 process 對該檔案的所有資訊。當檔案被打開後 OS 也會針對該檔案建立一個 system-wide table 儲存該檔案系統等級的資訊(似 global information)並分享給所有與該檔案相關的 process。

(1) open-file table
每個 process 都會有自己的 open-file table 用來追蹤與紀錄該 process 所開啟的檔案的資訊例如：檔案指標(file pointer)、存取權限(access right)等。open-file table 會存在 process 的 process control block(i.e., PCB) 中

(2) System-wide table
OS 也會有一個自己的表格(system-wide table)用來紀錄開啟的檔案以及和 process 無關的檔案資訊，像是磁碟位置(disk location)、檔案開啟數量(file open count)等。每個 process 的 open-file table 中的檔案都會指向 system-wide table(如下圖)。

將這些資訊獨立於每個 process 外而不是複製到各自的 open-file table 是為了避免檔案的重要資訊在不同的地方遭到修改。


## Access methods

Access methods 指的是檔案系統讀寫檔案的方式，常見的存取方法有 3 種：

* Sequential access
* Direct access
* Index access

(檔案的讀寫是以 block 為單位)

### 1. Sequential access

Sequential access 是以循序漸進的方式存取檔案，提供有 3 種方法：

* Read/write next block
* 檔案指標(file pointer)會依序往下一個 block 前進做存取
* Reset
* 重新設定 file pointer 的位置到起點
* Skip/rewind
* 跳過或是往反方向的順序做存取

適合用在影音的串流資訊或簡單的文字檔


### 2. Direct access

直接指定檔案中的任意位置存取，需要指定 #block 做為參數。這種模式也稱為隨機存取(random access)

> [!Caution] **Random access in memory v.s. file system**
> 記憶體中的隨機存取(RAM)指的是 CPU 存取記憶體中的任何位址速度幾乎相同，因為是採用 array 的設計快速找到要存取的位址。檔案系統中的隨機存取指的是可以存取某個檔案中的任意位置，不用依照漸進的方式從頭開始。

依照 file system 所提供的 API 在不同情境下使用不同的方式，但通常是 sequential 居多，因為比較符合檔案儲存的方式與儲存位置。


### 3. Index access

與 direct access 類似較適合大型的 database 系統，透過 index table 紀錄檔案中的每個 block 對應的硬碟位置。存取時直接從 index table 找到對應的磁碟位置進行。


## Directory structure

File system 中有 3 個不同的層級單位

(1) Partition
將磁碟分割成不同的區域，每個區域都是一個 partition 且可以當作獨立的磁碟使用，是最底層的層級的單位(不包含 file system)。Partition 可以是磁碟(disk)的一部份，也可以由多個磁碟組成。

(2) Volume
將一個或多個 partition 格式化後加上 file stsyem 的區域稱為 volumn，OS 能夠透過 file system 管理這個區域的內容。例如 WIndows 系統中的 C 槽、D 槽。

(3) Directory
File system 用來管理/儲存檔案資訊的最上層的單位。Directory 本身也是一種檔案，用來儲存檔案清單與資訊。

Directory 包含以下幾種操作與運算：

* Search file
* Create file
* Delete file
* List a directory
* 最耗時間，因為要把整個 file system 從磁碟中搬出來
* Rename file
* Traverse the file system


> [!Note] **Directory v.s. File**
> Directory 是包含檔案資訊的節點的集合，不論是 directory 或 file 都會存在磁碟中。
> 

### 1. Single-level directory
屬於早期的設計，所有檔案放在同一個 directory 中，每個檔案的檔名都必須是獨立的。

/file1.txt
/file2.txt
/file3.txt

> [!Note]
> 嚴格說起來 single-level directory 並沒有 directory 的概念，只是把檔案散佈在由 OS 所管理的區塊(檔案池)之中，沒有任何組織。
> 

### 2. Two-level directory

將每個使用者各自的檔案分開，並開始有路徑(path)的概念。path = user name + file name。


### 3. Tree-structure directory

現代檔案系統都採用樹狀結構，使用者目錄下還有更多的子目錄。每個檔案都有兩種路徑:

* Absolute path: 從根目錄(root)開始到該檔案/目錄的路徑
* Relative path: 從某個目錄開始到其他檔案/目錄的路徑


### 4. Acyclic graph directory

樹是一種最簡單的非循環圖結構，因此再進階可以使用非循環圖結構的 directory 來組織/管理檔案。每個檔案可以在多個 directory 中出現，但不是使用複製的方式，而是使用一個 link 將多個 directory 指向同一個檔案，也因此每個檔案會有多個絕對路徑。這種方式可以節省空間，且更新檔案時也不會有不同步的問題，但缺點是當檔案被刪除時，某個指向該檔案的 link 就會斷掉。

可以使用 counter/reference counter 解決，每當少一個 directory 指向檔案，則 counter 數量減 1。直到 counter 為 0 表示沒有 directory 指向該檔案，此時才做刪除。


### 5. General graph directory

圖狀結構的 directory 系統會包含 cycle，此時 reference count 將無法使用，因為 directory 之間會互相指向，reference count 不會 = 0。這種 directory 結構採用 garbage colleciton 機制來處理 cycle:

* 第一次走訪整個圖並標記(mark)可存取的檔案/目錄
* 第二次走訪將沒有被標記的檔案/目錄回收記憶體

缺點：當檔案數量很大時效率不好

## Mounting(掛載)

一個新的 file system 被存取前需要 mount 到作業系統下的檔案系統中。通常在以下時機點會需要做 mount 的動作

* boot time
* 開機時需要將裝有 OS 的檔案系統掛載好，但此動作會自動完成
* Automatically at run time
* 插入隨身碟或其他儲存裝置時會自動做掛載
* Manually at run time


被掛載的檔案系統會被標記(m)起來，搜索時如果找到 mount point 就會跳至該檔案系統開始尋找。

> [!Note] **Mount point**
> 掛載點指的是新加入的檔案系統插入的節點位置，可以是根目錄(root)也可以是其他 directory。

## Sharing

每個 user 會有兩種 ID: (userID, groupID)，相同 group 的 user 對該 group 所屬的檔案會有相同權限。此外每個檔案也都有三種屬性: owner, group, others

* Owner: 此屬性描述檔案的擁有者對該檔案的特權
* group／other: 同上

### 1. Access control list

每個檔案上面都會有一個串列(list)，上面紀錄每個 user 的權限。結合 user 身份(owner/group/other)的不同，每個 file 會有 3 個 ACL，每個 ACL 都會紀錄不同使用者對該檔案的權限

* R: read
* W: write
* X: execute


以 owner 來說，7$_{10}$ = 111$_2$ = RWX 表示 owner 有讀取/寫入/執行的權限。在 Linux 系統中可以使用 `chmod` 指令修改權限，如 `chmod 664 intro.ps` 表示將 owner/group/other 的權限改為 6/6/4