OS 筆記 - Ch11 File System Implementation

Posted on Edited on In Views: Views: Disqus: Word count in article: 5.1k Reading time ≈ 5 mins.
Ch11 File System Implementation 的整理筆記

Ch11 File System Implementation 的整理筆記

  • File-System Structure
  • File System Implementation
  • Disk Allocation Methods
  • Free-Space Management

File-System Structure

  • I/O 和 Memory 之間傳輸最低單位為 blocks
    • one blocks = one or more sectors
    • one sector 通常 sectors
  • OS 可以擁有超過一種的 File System
    • NTFS, FAT32
  • FS 的設計要考量到 :
    • interface to user programs (通常差不多)
    • interface to physical storage (disk)
  • 對於 programmer 來說，我們並不想管底下有幾種
    所以底下會有個 Layered File System 當作中間層，幫忙對應

File-System Implementation

On-Disk Structure

  • 必須永久存在
  • Boot control block (per partition) : 存需要開機的 code
    • typical the first block of the partition
    • Unix File Sys. (UFS) : boot block
  • Partition control block : 硬碟可以切很多個 partition，所以需要這個來讓 OS 知道怎麼去 access 眾多的 block
    • 會放一些 detail : blocks 數量、大小、free block list、free-FCB 等等
    • UFS : superblock
  • File control block** (per file)** : File detail
    • details: permissions, size, location of data blocks
    • UFS : inode
  • Directory structure (per file system) : organize files

看圖會比較好懂 !

In-Memory Structure

  • in-memory partition table : information about each mounted partition
    • 知道這個 partition 長什麼樣子然後就可以做操作
  • in-memory directory structure : information of recently accessed directories
    • 不需要整個 load 進來，只 load entry，可能是之後要的一小塊
  • system-wide open-file table : contain a copy of each opened file's FCB
  • per-process open-file table : pointer (file handler/descriptor) to the corresponding entry in the above table

File-Open & File-Read

File Creation Procedure

  1. OS allocates a new FCB
    • 一定要先 create FCB 他才會存在
  2. Update directory structure
    • 確認 path 是否存在，不在的話就去 load
    • 讓他對到某個位置 ( Updates the dir structure ) ( 我們要他出現在 tree 的某個 node )
    • 寫回 ( writes back the directory structure back to disk )
      • 還沒寫回 Disk 就跳電 ... 那這東西就消失惹

Virtual File System

  • VFS provides an object-oriented way of implementing file systems

    • Programmer 不用管底下，通過相同 API 去開發就好

  • VFS allows the same system call interface to be used for different types of FS

    • VFS 會自己再去找適合的方式去 access partition info (自己另外實做)

  • Four main object types defined by Linux VFS :

    • inode → an individual file (就是個 FCB)
    • file object → an open file
    • superblock object → an entire file system
    • dentry object → an individual directory entry

Schematic View of Virtual File System

Directory Implementation

  • Linear lists
    • 就 ... 串起來，好 implement 但是 poor performance
  • Hash table
    • 通常 entry 數量是固定的

Allocation Methods

  • An allocation method refers to how disk blocks are allocated for files
  • DATA block 影響到 access 方式
  • Allocation strategy :
    • Contiguous allocation
      • 要找到足夠長度去放，data 長度也會改變，是個 issue
    • Linked allocation
    • Indexed allocation

Contiguous Allocation

  • 不需要去 traversal 整個硬碟，只要給 start 去算就能直接 access 檔案

    • Both sequential & random access can be implemented efficiently
    • R/W 大檔案都挺不錯，相比另外兩個

  • Problems :

    • External fragmentation
      • Solution : compaction
      • 其實內外碎都有
    • **File cannot grow **
      • Solution : Extend-based FS

  • 現在 OS 通常都會用 modified contiguous allocation scheme (改良版)
    Extent-based file systems

    • 定義 **extent ** 為 a contiguous blocks
      而一個檔案可以有多個 extents
    • 但 Random access 花費更多。
      • 因為你要找下一個 extend，必須把前一個給 load 進來，讀到最後面的 info
        會有多次的 I/O request
      • 註 : 並不是說可以只擷取 block 的最後一小塊 (next entry) 來讀就好
        這跟 link list 一樣，node 一定要 load 進來

  • 且 internal & external fragmentation 都可能出現。

Linked Allocation

  • 每個檔案都是 linked list of blocks
    • Each block contains a pointer to the next block
  • 優點 : 與 Contiguous 相反，create 只要 O(1)，資源使用非常有效率；沒外碎
  • Only good for sequential-access files
    • Random access 要 traversal 全部，某種方面來說也就是不 support
    • Each access to a link list is a **disk I/O **
      (because link pointer is stored inside the data block)
  • 會需要空間來儲存 pointer (雖然很小)
    • 可能會組多個 blocks 當作一個 cluster，這樣 pointer 的占率就會相對小
  • 只要有一個 link 斷了就 ... GG 了

FAT (File Allocation Table) file system

  • 為了解決 random access traverse overhead
    考量到每次想要知道下一個 entry (next node pointer) 都要全部 Load
    所以 ... 乾脆把 這個 entry info 另外單獨儲存 !

  • 這東西會被 cached 進 Memory，所以不用擔心找 next 會是 I/O request

    • Disk head find the location of any block by reading FAT

  • 是一個大 table，會放多個檔案的 entry (相對於 index allocation)

  • FAT32 :

    • 32 bits per table entry
    • located in a section of disk at the beginning of each partition

Indexed Allocation

  • The directory contains the address of the file index block
    (directory 有 all index)

    • index block 是固定大小的，例如 512 B

  • Each file has its own index block

  • 會有欄位儲存 幾個 blocks

Indexed Allocation Example

  • 優點 :
    • Implement direct and random access efficiently (Link 不 support，我做到了 ! )
    • No external fragmentation (有空的位置我就可以加入)(保有 Link 的優點)
    • Easy to create a file (no allocation problem) (改善 Contiguous )
  • 缺點 :
    • 需要空間去儲存 index (如果檔案很小那成本相對高)
    • 但如果檔案很大 ... 可能又會超過 index block
      • 解法 :
        • linked scheme
          • 把 index block 的 index 串起來
          • 如果真的跳很遠還是要 access 多個 index block
        • multilevel index
        • combined scheme (inode in BSD UNIX)
          • 混和型，可以 multilevel 也可以 single level 和 direct

Free-Space Management

Free Space

  • Free-space list : 記錄所有 free disk blocks
  • Free space 就只是個 file，然後需要有個 DS 來把它們串起來
  • Scheme
    • Bit vector
    • 以下三個其實就跟前面介紹的一樣，只是換了個名字，也不用刻意記
    • Linked list (same as linked allocation)
    • Grouping (same as linked index allocation)
      • store address of n free blocks in the 1st block
      • the first (n-1) pointers are free blocks
      • 最後一個 pointer 連到 grouping block
    • Counting (same as contiguous allocation)
      • keep the address of the first free block and number of contiguous free blocks

Bit vector

  • Bit Vector (bitmap) : one bit for each block

  • 多少個 block，多少個 bit → 只要是 0 都是可以用的

  • 存在的意義 : 有時候我們會想要加入不同的條件
    像是我給一個 index，然後要找 離他最近 的一組 0，且我要 k 個 0 以上。
    這種就不是 linked-list 等的可以好找的。(離他近的好處是可以減少磁頭移動 )

  • 優點

    • simplicity , efficient
      • HW support bit-manipulation instruction

  • 缺點

    • bitmap must be cached for good performance
      • A 1-TB(4KB block) disk needs 32MB bitmap


Review

P.15

  • Transfer unit between memory and disk ?
  • App → LFS → FOM → BFS → I/O Control → Devices

Layered File System

  • On-disk structure
    • Boot control block, Partition control block
    • File control block, Directory structure
  • In-memory
    • Partition table, Directory structure
    • System-wide open-file table
    • Per-process open-file table
  • Steps to open file, read/write file and create file ?
  • Purpose of VFS ?

p. 34

  • Allocation :
    • Contiguous file allocation ?
      Extent-based file system ?
    • Linked allocation ?
    • Indexed allocation ?
      • Linked scheme
      • multilevel index allocation
      • Combine scheme
  • Free space :
    • Bit vector, linked list, counting, grouping

參考

周志遠教授 PPT 與影片

END

-----------------------------------

2020.01.08