For most users, the file system is the most visible aspect of a general-purpose operating system. It provides the mechanism for on-line storage of and access to both data and programs of the operating system and all the users of the computer system. The file system consists of two distinct parts: a collection of files, each storing related data, and a directory structure, which organizes and provides information about all the files in the system. Most file systems live on storage devices, which we described in Chapter 11 and will continue to discuss in the next chapter. In this chapter, we consider the various aspects of files and the major directory structures. We also discuss the semantics of sharing files among multiple processes, users, and computers. Finally, we discuss ways to handle file protection, necessary when we have multiple users and want to control who may access files and how files may be accessed.

1. File Concept

File Attributes

  • 在大部分的系統中，file attributes 包含：
    • Name
    • Identifier：一個 unique tag，通常是以數字的形式，讓系統得以辨認他是誰
    • Type
    • Location
    • Size
    • Protection：Access-control information
    • Timestamps and user identification

File Operations

  • 有七個基本的 file operations
    • Creating a file - 首先要先在 file system 中 allocate space，再來必須在該 file 所處的 directory 增加一個新的 entry
    • Opening a file - 除了 create 及 delete 一個 file 以外，所有其他的 operation 都需要先對檔案進行 open()
    • Writing a file
    • Reading a file
    • Repositioning within the file - 移動 current-file-position pointer，也就是 file seek
    • Deleting a file - 刪除檔案必須釋放其在 file system 中佔用的空間，以及釋放他在 directory 中的 entry。在支援 hard link 的系統中，一個檔案的內容要等到所有 link 都被刪除後才會真正的被 delete
    • Truncating a file - 將檔案內容刪除 (file length = 0) 但是保留 file attributes
  • 系統會 maintain 一個 system-wide open-file table，保存目前所有有被 reference 到的檔案資訊，如：檔案在 disk 中的位置、檔案長度等
  • 每個 process 也會 maintain 一個 per-process table，存放一些 process-wide 的資訊，如目前的 file pointer (下一個讀寫的位置) 跟檔案的 access right (每個 process 開檔時 specify 的權限可能不同)，每個 entry 會指向 system-wide table 中的一個 entry
  • system-wide table 會紀錄每個 entry 的 open count，即目前有幾個 process 正開著這個檔案，每一個 close() 會讓 open count 減少一，當 open count = 0 時，file entry 就會被移除
  • 大部分系統也會提供 file lock 的機制，可以分為兩種：shared lock 是指多個 process 可以同時持有這個 lock，如 read lock；exclusive lock 是指一次只能有一個 process 持有這個 lock，如 wirte lock
  • 也可以將 lock 分為 mandatory 或者 advisory。mandatory lock 是指一但上鎖了，OS 便會防止其他人用所有可能的方法 access data；advisory lock 則沒有強制的規定，一但上鎖了其他人還是可以 access data，因此 ensure that locks are appropriately acquired and released 就是 programer 自己的責任

File Structure

  • 檔案有各式各樣的種類 (.c, .tex, .jpeg)，系統沒辦法提供每一種檔案客製化的 file structure，這樣會造成很高的 overhead
  • 大部分系統 (UNIX, Windows) 只採用最少種類的 file structure。以 UNIX 舉例，UNIX 只提供一種 structure：所有的檔案都必須是一連串的 8-bit bytes，每一個 application 必須自己決定要怎麼解讀檔案，這樣的方法 OS 給的 support 雖然很少，但可以有最大的彈性

2. Access Method

Sequential Access

  • Sequential access 是來自 tape 必須連續讀取資料的性質，照順序 process file content

Direct Access

  • 如果檔案中每一個 logical record 的長度都是定值 (像是 UNIX 系統中的 1 byte)，那麼便可以使用 direct access 的方法直接透過 logical index 讀取檔案
  • 注意 logical index 通常是 relative 的，也就相對於檔頭的位置。這樣相對的設計也可以防止 user 戳到不屬於該 file system 的空間

3. Directory Structure

  • Directory 的目的就是將 file name 對應到他們各自的 file control blocks，為了達到這個需求，directory 的結構可以有很多種，每一種結構都需要滿足以下幾種 operations：
    • Search for a file - 利用 file name 找到對應的 entry
    • Create a file - 增加新的 entry 到 file structure 中
    • Delete a file - 刪除對應的 file entry，同時必須處理刪除後可能造成的 fragment 問題
    • List a directory - 列出 directory 中的所有 file entry
    • Rename a file - 重新命名檔案，也包含移動檔案的位置
    • Traverse the file system - 遍歷 file system 中的每一個 entry，通常會用於週期性的掃描並儲存每個檔案的變化

Single-Level Directory

  • 將所有檔案都放在同一個 directory 下，最大的問題是 file name 衝突與沒有組織性

Two-Level Directory

  • 讓每一個系統中的 user 有各自的 user file directory (UFD)，並在進行 operation 時會先辨認是哪一個 user 發起的，透過 master file directory (MFD) 找到他的 directory 並在其下執行 operation
  • 若系統會允許 user access 其他 user 的 directory，那就要使用 path name 來辨認每一個檔案以防止 file name 衝突
  • system files 因為會被每一個 user 使用，為了不要耗費多餘的空間大部分系統會另外開一個 special user directory 存放這些檔案；某一個 file name 需要被 access 時，系統會先搜尋執行者的 directory 是否有該檔案，若沒有的話再到 special user directory 尋找

Tree-Structured Directories

  • 將兩層的 directory generalize 成多層的樹狀結構，任意的 directory 底下可以存在 file 或 subdirectory

Acyclic-Graph Directories

  • Tree structure 限制了一個 file or subdirectory 只能存在在一個 directory 之下，但 acyclic-graph directory 則沒有這樣的限制，一個 file or subdirectory 可以存在在多個 directories 之下
  • 在 UNIX 系統中，這種結構是用 link 實作的
  • 這樣的設計會導致同一個 file/directory 可能有多個 absolute path，導致 traverse file system 時搜尋的 overhead
  • 另一個問題是 file deletion，當某一個 user delete shared file 時，會讓其他的 file pointer 失效，甚至可能指向不一樣的檔案 (原本的空間被 reused)
    • 如果系統是使用 sysbolic link 實作的話便不會有這個問題：link 被刪除時不會影響到檔案本身，就算在檔案本身被刪除時再 access link，也只會得到 file path does not exist 的錯誤，不會戳到其他不該戳的檔案
  • 另一種方法是等到所有 file reference 都被 delete 時才真的刪除檔案，UNIX 利用 hard link 來實作這個部分：UNIX 會將檔案被 reference 的次數記在 inode 中 (所有 hard link 共用一個 inode)，並在 reference count = 0 時刪除檔案

General Graph Directory

  • 對於存在 cycle 的 directory structure，在 traverse 時如果沒有慎選演算法可能會掉進 infinite loop
  • 計算 file refernce count 也會變得更困難，因為可能會有 self-referencing 的情況發生，這時候就需要使用 garbage collection 的機制，特別去偵測這些可能的 self-cycle file
  • 因為 acyclic-graph 相對來說比較單純，不會有這些問題，通常在 traverse 時可以忽略 link 的存在，讓 graph 退化成 acyclic

4. Protection

Type of Access

  • 權限的種類通常可以分為以下幾種：Read、Write、Execute、Append、Delete、List and Attribute change

Access Control

  • 最基本的 access control 是將每一個檔案或 directory 都 assign 一個 access control list (ACL)，裡面指名所有可以 access 這個檔案的 user
  • 這種方法會有幾個問題：當可以 access 的 user 很多時，或者只是想禁止某些人使用時，ACL 就會變得很沒有效率；另外，一個 directory entry 的長度也必須是彈性的，因為每一個 entry 的 ACL 長度可能不同
  • 為了解決這些問題，可以使用 owner-group-other permission。現今大多數系統 default 使用 owner-group-other，病也支援在需要的時候可以為特定檔案加上 ACL，且當 ACL 存在時，優先序會高於 owner-group-other permission

5. Memory-Mapped Files

  • 透過將檔案 map 到 virtual memory，可以減少 read(), write() 等 system call 的次數，增進效率
  • 一開始會透過 demand paging 產生一個 page fault 將 disk 中的 data block 複製到 memory 中的某一個 physical page 裡 (有些系統可能會一次複製多個 block)，接下來的 read & write request 都會變成一般的 memory access，速度變快很多
  • 通常 memory mapping 的 write 不會馬上寫回 disk，而是等到這個檔案被 close() 時，才會一次寫回去
  • 有些系統為了加速，會將一般的 I/O request 也當成 memory-mapped 看待，只是會 map 到 kernel address-space，而不是 user space
  • Data sharing 也可以透過 memory-mapped file 達成，讓所有 process 可以同步看到檔案的變化，也可以同時支援 copy-on-write 的特性，共用 read-only data 但是各自保存有改動的部分