File Systems

File Systems

1. Definition: Main secondary data storage

   • Extreme bottleneck
   • Logical View (programmer)
     • Tree structure of files, together with read/write operations and creation of directories
   • Physical View
     • Sequence of blocks, can be read/written

2. Mapping tree structure onto physical blocks

   • Linked list
     • Each block contains pointer to next
       • Start with the root; mark where root FS is on a particular block number, read block; if all info from directory fits in that block then ok, if not then link to next block.
     • Problem: random access costly (need to go through whole structure)
     • For each file, store block number of where that files starts
   • Indexed allocation
     • Store pointers in one location (index block)
       • Index block tells us where data is
       • Index block loaded into main memory
     • Each file has both data / index block
     • Indirect index blocks: coping with different file sizes
       • E.G. block sizes of 1kb - 1GB files = a lot of blocks
         • Indirect index block has indirection levels of a certain size (10MB) - easier to access data

3. Caching

   • Disk blocks store directors or recently used files cached in main memory
     • Blocks are periodically written to disk
   • Big efficiency gain
   • Problem introduced when system crashes

4. Journaling file systems

   • Minimise data loss at system crashes
     • Define transaction points: where cache is written to disk
     • Log file for every each write-operation
       • Can unravel any changes done after latest transaction point

5. RAID arrays

   • Increase reliability
     • Mirroring
       • Store same data on different disks
     • Parity schemes
       • Store data on n disks - use n+1 disk to store parity blocks
         • Can recover from single disk failure
         • Problem of recompiling parity bits for each write operation

6. Disk access

   • Seek
     • Head moves to appropiate track
   • Latency
     • Correct block is under head
   • Transfer
     • Data transfer
   • Time for seek and latency bigger than transfer time
     • Distribution of data and scheduling algorithms have vital impact on performance

7. Disk scheduling algorithms

   • First come first served
     • Easy to implement
     • Requires a lot of head movements
   • Shortest seek time first
     • Select job with minimal head movement
       • May cause starvation - tracks in middle of disk preferred
         • Doesn't minimise number of head movements
   • SCAN-scheduling
     • Head continuously scans disk from end to end (lift strategy)
       • Solves fairness and starvation from SSTF
       • LOOK-scheduling improvement on this
         • Head only moves as as far as the last request
   • Different tasks require different disk access algorithms
     • Swap space management - speed crucial

8. Disk scheduler

   • Kernel allows different schedulers for different file systems
   • Default scheduler based on lift strategy
     • Have separate queue for disks requests for each process
   • No-op scheduler - implements FIFO
     • Not suitable for hard disks (geometry not taken not count)
     • Suitable for SSDS's where access time for all sectors equal
       • NO head to move