Computer Science 330
Operating Systems

Spring 2012, Siena College

Home     Syllabus     Schedule

Agenda

• Announcements
  • Final project progress reports due Friday
• Setting a time for the April 30 final project presentations
• Lecture assignment 19 recap
• 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

Lecture Assignment 20

Due at the start of class, Thursday, April 12.

Please submit answers to these questions either as a hard copy (typeset or handwritten are OK) or by email to jteresco AT siena.edu by the start of class. Please use a clear subject line when submitting by email (e.g., CS 330 Lecture Assignment 20, Joe Student). We will discuss these questions at the start of class, so no late submissions are accepted.

• SG&G Exercise 10.9, p. 454 (3 points)
• SG&G Exercise 10.10, p. 454 (2 points)
• SG&G Exercise 10.15, p. 455 (3 points)
• SG&G Exercise 11.16, p. 487-488 (3 points)