Theory
A crowded lab story
Suppose the lab server must save 3 student files and also handle 6 pending disk requests at the same time. If the server chooses badly, files become scattered and the disk arm wastes time moving back and forth. Your job in this topic is to see how the OS makes both decisions smartly.
Theory
Think of it like a library
Disk allocation is like deciding where to place books on shelves, while disk scheduling is like deciding which student gets served at the counter next.
- Good shelf placement saves space and search time.
- Good service order reduces walking around, or in a disk, reduces head movement.
Theory
The idea, formally
Disk allocation methods decide how file data blocks are stored on disk, and disk scheduling methods decide the order in which pending disk I/O requests are handled. In exams, write both parts clearly, because one is about storage layout and the other is about service order.
At a glance
Two families of methods you must not mix up
| Method | Main idea | Common issue |
|---|---|---|
| Contiguous allocation | Store all blocks together | External fragmentation, hard to grow |
| Linked allocation | Store blocks in a chain | Slow direct access |
| Indexed allocation | Use an index block to point to data blocks | Index block overhead |
| FCFS scheduling | Serve requests in arrival order | Can cause large head movement |
| SSTF scheduling | Serve nearest request first | May starve far requests |
| SCAN scheduling | Move like an elevator and serve on the way | Edge requests may wait |
Think first
Try it first
A file needs 4 blocks. Which allocation method is best if you want easy sequential access and the file will not grow much? Think mentally before you tap.
Show the answer
Contiguous allocation. All 4 blocks sit side by side, so sequential reading needs no jumps at all, and because the file will not grow much, the usual weakness of contiguous allocation (no room to expand) never bites here.
Quiz
Which disk scheduling method serves requests strictly in the order they arrive?
- FCFS
- SSTF
- SCAN
- C-SCAN
Show the answer
FCFS
FCFS is first come first served, so it does not reorder requests. SSTF chooses the nearest request, SCAN moves in one direction and back, and C-SCAN wraps around in one direction only.
Think first
Work it out
The requests arrive in this order: 98, 183, 37, 122, 14, 124, 65, and the head starts at 53. For FCFS, what is the total head movement? Try it before reading on.
Show the answer
Walk the jumps: 53 to 98 is 45, then 85, 146, 85, 108, 110, and finally 124 to 65 is 59. Total: 45 + 85 + 146 + 85 + 108 + 110 + 59 = 638 cylinders. Notice how FCFS lets the head zig-zag across the whole disk; SSTF would serve the nearest request each time and cut this total sharply.
Watch out
The trap
Do not confuse disk allocation with disk scheduling. Allocation answers, “Where are file blocks stored?” Scheduling answers, “Which request should go next?” In exams, mixing them up usually loses easy marks even if your definitions are partly right.
Quiz
Which allocation method uses a separate index block to store pointers to all data blocks?
- Contiguous allocation
- Linked allocation
- Indexed allocation
- FCFS allocation
Show the answer
Indexed allocation
Indexed allocation uses an index block. Contiguous stores blocks together, linked stores pointers inside each block, and FCFS is not an allocation method at all.
Theory
Connect it to practice
You will see these ideas again in file systems, OS scheduling, and performance questions. A neat exam recipe is: define the method, draw the structure, state one advantage, state one disadvantage, then give one use case.
Summary
Key takeaways
- Allocation decides file block placement, scheduling decides request order.
- Contiguous is fast for sequential access but grows poorly.
- Linked avoids contiguity problems but is weak for direct access.
- Indexed supports easy access with extra index overhead.
- FCFS is simple, SSTF is shorter on movement, SCAN feels like an elevator.
- Memory hook, place files well, serve requests wisely.