Operating Systems · Unit 4
File Systems and Storage
Memory is fast but forgets everything when the power goes off. Files keep data on disks and SSDs between sessions. This unit covers how the operating system names and organises files, how it places them on a disk, how it tracks free space, and how it orders disk requests to save time.
1. Files and access methods
DefinitionA file is a named collection of related data stored on secondary storage. To the user it is the smallest unit of storage that can be named.
The OS keeps attributes for every file: its name, a unique identifier, type, location on the device, size, protection (who may read, write or run it) and timestamps. The basic operations are create, open, read, write, reposition (seek), delete and truncate.
A file can be read in three ways:
- Sequential access – records are read one after another, like a tape. Used by editors and compilers.
- Direct (random) access – any block can be read by its number, in any order. Used by databases.
- Indexed access – an index points to blocks, so a record is found by first looking it up in the index.
2. Directory structures
| Structure | How it works | Weakness |
| Single-level | All files of all users in one directory. | Names clash; no grouping. |
| Two-level | Each user has a separate directory under a master directory. | Users cannot easily share files. |
| Tree | Directories can contain subdirectories to any depth; files are named by paths. | A file has only one place in the tree. |
| Acyclic graph | A file or directory can appear in several directories through links. | Deleting a shared file needs care. |
| General graph | Links may form cycles. | Searches can loop; needs garbage collection. |
Paths can be absolute (from the root, such as /home/riya/notes.txt) or relative (from the current directory, such as notes.txt).
3. File allocation methods
A disk is divided into fixed-size blocks. The allocation method decides which blocks hold a file.
| Method | How it works | Advantages | Disadvantages |
| Contiguous | The file occupies consecutive blocks; the directory stores the start block and length. | Fast sequential and direct access. | External fragmentation; a file is hard to grow. |
| Linked | Each block holds a pointer to the next block. FAT keeps these pointers together in a table. | No external fragmentation; files grow easily. | Slow direct access; a broken pointer loses the rest of the file. |
| Indexed | An index block lists all the file's block numbers. UNIX uses an inode. | Fast direct access; no external fragmentation. | The index block takes space even for tiny files. |
Solved example: maximum file size with an inode
A classic UNIX inode has 12 direct pointers, one single indirect, one double indirect and one triple indirect pointer. Take 4 KB blocks and 4-byte pointers, so one block holds 4096 ÷ 4 = 1024 pointers.
| Pointer | Blocks reached | Data |
| 12 direct | 12 | 48 KB |
| Single indirect | 1024 | 4 MB |
| Double indirect | 1024 × 1024 | 4 GB |
| Triple indirect | 1024 × 1024 × 1024 | 4 TB |
Small files use only the direct pointers, so they are reached quickly. Large files pay for one or more extra index reads.
4. Free-space management
- Bit vector (bitmap) – one bit per block, 1 for free and 0 for in use. If blocks 2, 3, 4, 5, 8 and 9 are free in a 10-block disk, the map is 0011110011. Simple and fast to search, but the map itself needs space.
- Linked list – each free block points to the next free block. No extra space, but slow to walk.
- Grouping – the first free block stores the addresses of n free blocks, the last of which stores the next group.
- Counting – stores a starting block and how many free blocks follow it, which suits runs of free space.
5. Disk scheduling, solved
On a hard disk, the time to reach data is mostly seek time (moving the head to the right cylinder) plus rotational latency (waiting for the sector to come round). Disk scheduling orders the waiting requests to reduce head movement.
- FCFS – serve requests in arrival order. Fair but often slow.
- SSTF – serve the request nearest the head. Fast, but far requests can starve.
- SCAN (elevator) – the head sweeps to one end of the disk serving requests, then reverses.
- LOOK – like SCAN, but reverses at the last request instead of the disk's end.
- C-SCAN and C-LOOK – serve requests in one direction only, then jump back, which gives more even waiting times.
Example
Cylinders 0 to 199. The head is at 53, and the queue is 98, 183, 37, 122, 14, 124, 65, 67. For SCAN and LOOK the head is moving towards 0.
| Method | Order served | Head movement |
| FCFS | 53 → 98 → 183 → 37 → 122 → 14 → 124 → 65 → 67 | 640 cylinders |
| SSTF | 53 → 65 → 67 → 37 → 14 → 98 → 122 → 124 → 183 | 236 cylinders |
| SCAN | 53 → 37 → 14 → 0 → 65 → 67 → 98 → 122 → 124 → 183 | 53 + 183 = 236 cylinders |
| LOOK | 53 → 37 → 14 → 65 → 67 → 98 → 122 → 124 → 183 | 39 + 169 = 208 cylinders |
Exam tipWrite the order first, then add the distances one step at a time. For FCFS here: 45 + 85 + 146 + 85 + 108 + 110 + 59 + 2 = 640. Most marks are lost on arithmetic, not on the method.
6. RAID
RAID combines several disks for speed, safety or both.
| Level | Method | Survives a disk failure? |
| RAID 0 | Striping: data split across disks for speed | No |
| RAID 1 | Mirroring: every disk has an exact copy | Yes |
| RAID 5 | Striping with parity spread over all disks | Yes, one disk |
| RAID 6 | Striping with two sets of parity | Yes, two disks |
| RAID 10 | Mirrored pairs that are then striped | Yes, one disk per mirrored pair |
7. Quick revision
- Access methods: sequential, direct, indexed.
- The tree directory is the common structure; links make it an acyclic graph.
- Contiguous allocation suffers external fragmentation; linked allocation is slow for direct access; indexed allocation needs an index block.
- Inode pointers: 12 direct, then single, double and triple indirect.
- A bit vector uses one bit per block to track free space.
- SSTF can starve far requests; SCAN and LOOK sweep like a lift.
- RAID 0 is fast but unsafe; RAID 1 mirrors; RAID 5 uses parity.
8. Practice questions
Q1. The head is at cylinder 50 and the queue is 82, 170, 43, 140, 24, 16, 190. Find the total head movement for FCFS and for SSTF.
Answer: FCFS: 32 + 88 + 127 + 97 + 116 + 8 + 174 = 642. SSTF order 43, 24, 16, 82, 140, 170, 190: 7 + 19 + 8 + 66 + 58 + 30 + 20 = 208.
Q2. A block is 1 KB and a block pointer takes 4 bytes. How many pointers fit in one index block?
Answer: 1024 ÷ 4 = 256 pointers.
Q3. Which allocation method suffers from external fragmentation?
Answer: Contiguous allocation, because each file needs one unbroken run of free blocks.
|