Computer Science 432 Operating Systems Williams College Fall 2006

Agenda

• Announcements
• Lab 6 done - last of the lab assignments
• Next milestone for final projects: progress reports before Thanksgiving break.
• Lecture assignment recap
• File Systems
  • 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 Implementation Overview
    • 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

Lecture Assignment

Due at the start of class, Thursday, November 16.

Turn in short answers to these questions. Please turn in a hard copy (typeset or handwritten are OK). We will discuss these questions during class, so no late submissions are accepted.

1. SG&G 11.2
2. What is the largest file that can be represented in the usual Unix inode scheme when the inode includes 12 direct blocks, 1 single indirect block, 1 double indirect block, and 1 triple indirect block? Assume a data block is 4KB and a block is identified and located on the disk using a 4-byte address.
3. Submit a one-page summary of the important ideas behind the Unix Buffer Cache, based on the supplemental readings.

The readings for next time are SG&G Chapter 12, UNIX Buffer Cache handout from Bach 1986.

Examples

• ls2

Links

Journaling filesystems:

• ReiserFS, a linux journaling filesystem
• ext3fs - journaling extension to Linux ext2 filesystem
• jfs, IBM journaling filesystem, available for AIX, Linux
• Related idea in FreeBSD's filesystem: Soft Updates

RAID:

• Hamming Code, as used in RAID Level 2.
• Linux RAID HOWTO