Computer Science 322
Operating Systems

• Announcements
  • Exam 2: details and practice questions coming Wednesday, review time on Monday, exam out next Wednesday, due back next Friday.
  • Lab 6 due Wednesday.
• Disks and partitions
  • a system may have multiple disks, each of which contains multiple partitions
  • we create a file system (more later) in each partition
  • mounting: drive letters in Windows, paths in Unix
  • In Unix, a virtual file system layer translates generic paths to the correct partitions (local of varying types, network-accessible)
  • partitioning: why and how?
• File System Implementations
  • want to provide: convenience, protection, efficiency
  • issues:
    • allocation of disk blocks to files/directories
    • track available blocks
    • do this efficiently
• Disk block allocation methods
  • contiguous allocation
    
  • extents
  • linked allocation
    
  • variation on linked: file allocation table (FAT)
    
  • indexed allocation
    • straightforward implementation:
      
    • linked indexed allocation
    • two-level index
  • Unix inodes
    • a combination of the best features of many of the above
    • set aside special disk blocks called inodes (index nodes)
    • inode has entries pointing to direct file blocks, a single indirect block, a double indirect block, and a triple indirect block
    • a superblock keeps track of inodes and data blocks
    • see /usr/src/sys/ufs/ufs/dinode.h in FreeBSD
  • Concerns: file size limits, fragmentation, overhead, performance
• Free Space Management
  • bit vector
  • free list
• Disk Scheduling Algorithms
  • Recall: cost of a disk access includes seek time and rotational latency
  • We wish to minimize seek time by minimizing the distance the read/write head has to move in order to service the incoming requests by reordering requests based on cylinder number
  • This optimization may be done by the disk, the hardware controller, or by the operating system
  • Compare algorithms by examining their performance on a given request queue
  • First-Come First-Served (FCFS)
  • Shortest Seek Time First (SSTF)/Closest Cylinder Next
  • SCAN or Elevator Algorithm
  • LOOK Algorithm
  • Circular Algorithms
  • Comparing Disk Scheduling Algorithms
    • SSTF or LOOK are often reasonable for a default algorithm
    • SCAN and C-SCAN are better for heavily loaded systems where LOOK is unlikely to save much and SSTF runs the risk of starvation
    • performance depends on the frequency and types of requests
    • we may want to consider some of this when we decide how to organize file systems
  • FreeBSD's ufs filesystem uses an elevator algorithm (see /usr/src/sys/ufs/ufs/ufs_disksubr.c)
• Caching
  • disks are slow, we want to use caching to speed up
  • caches may be in main memory, disk controller, disk drive
  • many Unix systems use: buffer cache
  • this introduces potential inconsistencies, need consistency checkers like fsck, scandisk

Lots of good questions to ask, but let's wrap up the lab.