File System Implementation

File System Implementation

1. File-system Structure

   • Resides on secondary storage (may be a disk)
     • Provides user interface to storage (mapping logical to physical)
     • Provides efficient and convenient access to disk by allowing data to be stored, located, and retrieved easily.
   • Disks provide in-place rewrite and random access
   • File control block (FCB)
     • Storage structure consisting of information about a file
     • Ex. Inode in UNIX
   • Device driver
     • Controls the physical device
   • File system is organized into layers

2. Layers

   • Device drivers
     • Manages the I/O devices at the I/O control layer. It deals with low-level commands.
     • Ex.: An example of low-level command is "read drive1, cylinder 72, track 2, sector 10, into memory location 1060"
   • Basic file system
     • Translates commands with middle abstraction level to low level commands for device drivers. It also manages memory buffers (holds data in transit) and caches (holds frequently used data).
     • Ex.: An example of middle-level command is "retrieve block 123"
   • File organization module
     • Understands files, logical addresses, and physical blocks. Translates logical blocks to physical blocks. Manages free space and disk allocation.
   • Logical file system
     • Manages metadata information, directories, and protection. Uses file control blocks (FCBs) to manage the file system.
     • May increase the overhead.and decrease performance, but reduces complexity and redundancy.

3. File Control Block (FCB)

   • Contains details about the file. There is one FCB per file.
     • Details: inode number, permissions, size, dates, etc.

4. In-Memory file system structures

   • Mount table
     • Stores file system mounts, mount points, and file system types.
   • System-wide open-file table
     • Contains a copy of the FCB and other info of each file.
   • Per-process open-file table
     • Contains pointers to appropriate entries in system-wide open-file table as well as other info

5. Directory Implementation

   • Linear List
     • Simple implementation
     • Inefficient searching: O(N)
     • Could be kept sorted.
     • A B-tree could raise the performance.
   • Hash table
     • Faster search
     • Collisions
     • Good if entries have fixed size.

6. Allocation method

   • Contiguous allocation
     • Each file occupies a set of contiguous blocks. To allocate a new block, only the start location and the length of the block are necessary.
     • Generates a lot of fragmentation
     • Good performance, because it does not need too much processing to allocate the new file.
     • Problems to find free space for the file
   • Methods that describe how disk blocks are allocated for files
   • Extent-based allocation
     • It is a modified version of contiguous allocation. Disk blocks are allocated in extents (contiguous block of disks). Each extent will be a group of blocks.
   • Linked list
     • Each file is a linked list of blocks. Each block points to the next block. Implemented in low CPU power devices.
     • No external fragmentation
     • Reliability may be a problem
       • What if some middle block is corrupted?
     • Locating a block can take many I/Os and disk seeks.
     • Ex. FAT (File allocation table)
       • Uses a table. Faster on disk and cachable.
     • No user control
   • Indexed
     • Each file has its own index block table with pointers to its blocks.
     • Index table, and index table overhead
     • Random access
     • No external fragmentation
     • Combined scheme
       • Multiple indirections of index blocks. It raises the overhead but makes it possible to address greater spaces than what would be possible if only one block was used.
     • Only the table is loaded into memory, requiring low I/O

7. Free space management

   • Bitmap
     • It is a vector of bits in which each bit shows if the block related to that bit is empty or not.
     • Needs an extra space to store the bitmap
     • Easy to get contiguous files
   • Linked list
     • Can not get contiguous space easily
     • No waste of space
     • No need to traverse the entire list.
     • Grouping
       • Modify linked list to store address of next n-1 free blocks in first free block, plus a pointer to next block that contains free-block- pointers
   • Counting
     • Keep address of each first free address block and the count of following free blocks for each.

8. Page Cache

   • Caches pages rather than disk blocks (more generic) using virtual memory techniques and addresses.
   • Loses performance because page cache is a more specialized structure and requires more functioncalls.

9. Recovery

   • Consistency checking
     • Compares data in directory structure with data blocks on disk, and tries to fix inconsistencies. Can be slow and fails sometimes.
   • Backup
     • Freezes the system and copies the snapshot of the system from the disk to another storage (magnetic tape, other magnetic disk, optical).
   • Recover
     • Process of restoring data from backup

10. Log Structured (journaling) file system

    • It is a file system that records each metadata update to the file system as a transaction. The transactions in the log are asynchronously written to the file system structures. When the file system structures are modified, the transaction is removed from the log. If the file system crashes, all remaining transactions in the log must still be performed.
    • All transactions are written to a log.

Imágenes y archivos del mapa