Study guide: File Systems and Storage Management

📋 Course Outline

1. File Concepts and Structures
2. File Attributes and Operations
3. File Types and Access Methods
4. File Protection and Access Control
5. File-System Implementation
6. Directory Implementation
7. Contiguous File Allocation
8. Linked File Allocation
9. Indexed File Allocation
10. Magnetic and Solid-State Disks
11. Disk Scheduling Algorithms
12. Disk Formatting and Partitions

📖 1. File Concepts and Structures

🔑 Key Concepts & Definitions

• File: A named collection of related information recorded on secondary storage, represented as bits, bytes, lines, or records whose meaning is defined by its creator and user.

★ Must-know

• The information and structure of a file are determined by its creator and depend on the file type.

Further detail

• A text file is a sequence of characters organized into lines and possibly pages.

• A source file is organized as a sequence of functions, each containing declarations followed by executable statements.

• An executable file contains code sections that a loader can bring into memory and execute.

📖 2. File Attributes and Operations

★ Must-know

• Typical file attributes are: name, identifier, type, location, size, protection, creation, modification, and use time, date, and user identification

• Creating a file requires finding space in the file system and adding an entry for the new file to the directory.

• Writing or reading a file uses a system call and a file-position pointer that advances after each operation; a shared current-position pointer can serve both operations when a process uses one operation at a time.

📌 Truncating a file releases its contents and resets its length to zero while preserving its attributes, whereas deleting a file also removes its directory entry and releases its file space.

Further detail

📌 A file name is the human-readable symbolic name, whereas its identifier is a unique, usually numeric, non-human-readable tag within the file system.

• A file's location attribute points to the device and location where the file is stored, while its size records its current size and possibly its maximum allowed size.

• Repositioning, or seeking, changes the current file-position pointer without necessarily performing I/O, while deleting releases the file's space and removes its directory entry.

• The per-process open-file table tracks a process's open files and access rights, while the system-wide table stores process-independent file information and an open count.

📖 3. File Types and Access Methods

🔑 Key Concepts & Definitions

• Sequential Access: Processes file information in order, one record after another, using read-next and write-next operations that advance the file pointer.
• Direct Access: Views a file as numbered fixed-length logical records or blocks and permits reading or writing them in any order by specifying a block number.
• Index Access: Searches an index of pointers to locate a file block, then follows the relevant pointer to access that block directly.

★ Must-know

• Operating systems commonly support few file structures, leaving applications to interpret their own input files, but they must support an executable-file structure to load and run programs.

Further detail

• A file extension, usually separated from the file name by a period, commonly indicates file type to users and the operating system.

💡 Memory Hook

Sequential access follows the file pointer; direct access jumps to a numbered block.

📖 4. File Protection and Access Control

🔑 Key Concepts & Definitions

• Access-Control List: Associates a file or directory with user names and the types of access permitted to each user.

★ Must-know

• Controlled file operations include:

  • reading
  • writing
  • executing
  • appending
  • deleting
  • listing

• A compact protection scheme classifies users as owner, group, or universe, with three permission fields that may encode read, write, and execute access as rwx bits.

Further detail

• For access controlled by an access-control list, the operating system checks whether the requesting user is listed for the requested operation and allows or denies access accordingly.

📌 Per-file passwords require users to remember multiple passwords, while one password shared across all files makes protection all-or-none if that password is discovered.

• Duplicate copies of files, such as regular disk-to-tape backups, can provide reliability if a file system is accidentally destroyed.

📖 5. File-System Implementation

★ Must-know

• On-disk structures include:

  • a per-volume boot control block
  • a per-volume volume control block
  • a file-system directory structure
  • a per-file file control block

• In-memory structures include:

  • a mount table
  • a directory-structure cache
  • a system-wide open-file table
  • per-process open-file tables
  • buffers for blocks being read or written

• Opening a file searches the system-wide open-file table and, if needed, the directory; the system copies the file control block into the system-wide table and creates a per-process entry pointing to it.

Further detail

• In UFS, the volume control block is called the superblock, while in NTFS volume information is stored in the master file table.

• Closing a file removes its per-process entry and decrements the system-wide open count; when the count reaches zero, updated metadata is written back and the system-wide entry is removed.

📖 6. Directory Implementation

🔑 Key Concepts & Definitions

• Linear-List Directory: Stores file names and pointers to data blocks in a sequential list, so finding an entry requires a linear search.
• Hash-Table Directory: Computes a value from a file name and uses it to return a pointer to the corresponding name in a linear list.

📝 Essential Points

• A deleted linear-list directory entry can be marked unused, linked to a free-entry list, or replaced by the last entry while the directory length is decreased.

• A chained-overflow hash table resolves collisions by storing each hash entry as a linked list and adding colliding entries to that list.

💡 Memory Hook

A linear list searches entries; a hash table uses a filename-derived value to find one.

📖 7. Contiguous File Allocation

🔑 Key Concepts & Definitions

• Contiguous Allocation: Stores each file in a consecutive run of disk blocks and records the starting block and allocated length in the directory entry.

★ Must-know

• Contiguous allocation supports both sequential and direct access and usually requires few disk seeks.

• First-fit and best-fit are common strategies for choosing a free hole, but repeated allocation and deletion can cause external fragmentation.

Further detail

• A contiguous file of n blocks starting at block b occupies blocks b through b + n − 1.

• Compaction copies files elsewhere and reallocates them from one large free region, reducing external fragmentation at high cost.

📌 Preallocating a file's final size can waste space through internal fragmentation, whereas allocating too little space can prevent the file from growing without relocating it.

📖 8. Linked File Allocation

🔑 Key Concepts & Definitions

• Linked Allocation: Stores a file as disk blocks that may be scattered across the disk, with each block pointing to the next and the directory pointing to the first and last blocks.

• File-Allocation Table: Stores one entry per disk block; each entry points to the next block in a file, and a special value marks the final block.

★ Must-know

• Linked allocation avoids external fragmentation, permits files to grow as free blocks become available, and does not require disk compaction.

📌 Linked allocation supports sequential access efficiently, whereas finding a particular block requires following pointers from the beginning and is inefficient for direct access.

Further detail

• Linked allocation uses space for pointers, and grouping blocks into clusters reduces pointer overhead but can increase internal fragmentation.

• A damaged pointer in linked allocation can mislink a file into the free-space list or another file, while doubly linked lists or storing file names and relative block numbers in blocks are partial solutions.

📖 9. Indexed File Allocation

🔑 Key Concepts & Definitions

• Indexed Allocation: Gives each file an index block containing addresses of its data blocks, with the directory storing the address of that index block.

★ Must-know

• The ith entry in an index block points to the ith file block, allowing direct access without external fragmentation.

Further detail

• Indexed allocation incurs index-pointer overhead that is generally greater than the pointer overhead of linked allocation.

• Large files can be supported by: linking index blocks, using multilevel indexes, combining direct and indirect pointers in an inode

• In the described combined scheme, the first 12 inode pointers address direct data blocks and the next three point to indirect blocks.

• With 4 KB blocks and 12 direct pointers, the combined scheme can directly access up to 48 KB of file data.

📖 10. Magnetic and Solid-State Disks

🔑 Key Concepts & Definitions

• Disk Access Time: Magnetic-disk positioning time consists of seek time, which moves the arm to the desired cylinder, and rotational latency, which waits for the desired sector to rotate to the head.

★ Must-know

• Magnetic disks store information magnetically on platter surfaces divided into tracks and sectors; tracks at the same arm position form a cylinder.

📌 An SSD is nonvolatile memory used like a hard drive and can be faster, more reliable, and lower-power than a magnetic disk because it has no moving parts, seek time, or rotational latency.

Further detail

• Disk bandwidth is the total number of bytes transferred divided by the time from the first service request to completion of the last transfer.

• A head crash occurs when a disk head damages the magnetic surface of a platter.

• SSDs are more expensive per megabyte, have less capacity than larger hard disks, and may have shorter life spans than hard disks.

📖 11. Disk Scheduling Algorithms

🔑 Key Concepts & Definitions

• Disk Scheduling: Selects which pending disk I/O request to service next when a drive or controller is busy.

★ Must-know

• SSTF selects the pending request nearest the current head position and moves the head 236 cylinders for the example queue starting at cylinder 53.

• SCAN services requests while moving the disk arm from one end of the disk to the other, then reverses direction; it is also called the elevator algorithm.

📌 C-SCAN services requests in one direction across the disk and returns to the beginning without servicing requests on the return trip, whereas SCAN services requests in both directions.

Further detail

• FCFS services disk requests in arrival order; for the queue 98, 183, 37, 122, 14, 124, 65, 67 starting at cylinder 53, it moves the head 640 cylinders.

• SSTF can cause starvation because a continuing stream of nearby requests may indefinitely delay a request farther from the current head position.

📌 LOOK and C-LOOK reverse or wrap around at the final request in a direction rather than traveling to the physical end of the disk.

📖 12. Disk Formatting and Partitions

★ Must-know

• Low-level formatting divides a blank magnetic disk into sectors and writes each sector's header, data area, and trailer.

• Preparing a disk for file storage requires partitioning it into one or more groups of cylinders and then logically formatting it by writing initial file-system structures.

Further detail

• A sector's data area is usually 512 bytes, while its header and trailer contain controller information such as the sector number and error-correcting code.

• During disk I/O, the controller calculates and stores an error-correcting code when writing a sector and recalculates it when reading to detect data corruption.

• Initial file-system structures can include maps of free and allocated space and an empty directory, while grouping blocks into clusters can improve efficiency.

📌 Raw I/O accesses a disk partition as a sequential array of logical blocks without file-system data structures, whereas logical formatting creates those structures for file-based use.

💡 Memory Hook

Physical formatting lays out sectors; partitioning divides the disk; logical formatting creates the file system.

📊 Synthesis Tables

Disk Space Allocation Methods