File System
Design & Performance

WriteWell's T_save calls one function — write(fd, buf, n) — and believes it's done. But nothing about the document is one contiguous thing on disk. It's scattered across dozens or hundreds of small blocks, and the moment T_save returns, the process could exit, the machine could reboot, another program entirely could open that same file by name. Somebody still has to know where every one of those blocks is. That somebody is the file system.

The file control block: a file's metadata, apart from its data

Every file the OS tracks has a small, fixed-size record describing it, kept separately from the file's actual bytes. Silberschatz & Gagne call this record the File Control Block (FCB); on Linux and most Unix-derived systems the same structure is called an inode (short for index node). It plays exactly the role Chapter 1's PCB played for a process: a process doesn't carry its own bookkeeping around inside itself, and neither does a file — the OS keeps it alongside.

A directory, in turn, is just a table of (name → identifier) pairs. When WriteWell opens report.txt, the OS walks the directory structure to translate that name into an inode number, reads the inode, and only then knows where any of the file's actual bytes are. The name is never stored with the data — it's why the same file can have two names (hard links, counted in that link-count field above) and why deleting a name doesn't necessarily delete the data.

Three ways to record where a file's blocks are

The Location field has to name every block the file occupies. There are three classic ways to do that, and the difference between them is almost entirely about what happens when a file grows.

Neither extreme is what real systems use for anything but the smallest files. Indexed allocation is the compromise: the FCB stores an array of block pointers directly, so any block is one lookup away — no walking a chain — without demanding the file live in one contiguous run.

Indexed allocation: direct, single-indirect, double-indirect

The catch is that the FCB itself is a small, fixed-size record — it can't hold an unbounded array of pointers for an unboundedly large file. The classic fix, used by Unix inodes since the 1970s, is to make the pointers themselves indirect once you run out of room:

• Direct pointers — a handful of pointers stored right in the FCB, each naming one data block. Cheapest possible access: read the FCB, read the block.
• Single-indirect pointer — one pointer in the FCB naming a whole extra block, and that block is filled entirely with more pointers, each naming one data block.
• Double-indirect pointer — one pointer naming a block full of single-indirect pointers, each of which names a block full of direct pointers. A tree, two levels deep, built entirely out of pointer blocks, with data blocks only at the leaves.

This chapter uses a scaled-down version of that scheme throughout, small enough to trace by hand: 1 KiB blocks, 4-byte pointers, 4 direct pointers, one single-indirect pointer, one double-indirect pointer. (Real systems use 4 KiB blocks and more direct pointers; the arithmetic below scales the same way, it's just bigger.)

Worked example — reaching a block of WriteWell's document

See it: trace any block of the document

Drag the slider to any logical block number and watch which pointers get followed. It opens on block 300, the case worked above.

Pitfalls

Practice

1. Under the same scheme (4 direct, 256 pointers per index block), the document grows to 500 KiB. How many extra accesses does logical block 400 cost, and what are its first- and second-level indices?
   Show solution

   Block 400 is past the single-indirect range (ends at 259), so it's double-indirect. Offset = 400 − 260 = 140. First-level index = 140 ÷ 256 = 0; second-level index = 140 mod 256 = 140. Same single-indirect block as block 300 used (first-level index 0), just a different pointer inside it. 2 extra accesses.

2. Suppose the scheme instead used 8-byte pointers (64-bit block addresses) at the same 1 KiB block size, keeping 4 direct pointers. Recompute the ranges, and find block 400 again.
   Show solution

   Pointers per index block = 1024 ÷ 8 = 128 (half as many as before — wider pointers buy a bigger address space per pointer at the cost of packing fewer of them into an index block). Direct: blocks 0–3. Single-indirect: blocks 4–131 (128 blocks). Double-indirect starts at 132. Block 400: offset = 400 − 132 = 268. First-level index = 268 ÷ 128 = 2; second-level index = 268 mod 128 = 12. Still 2 extra accesses — but now via a different single-indirect block (index 2, not 0) than the 4-byte-pointer scheme found. Wider pointers change which path a block takes without changing how many levels it costs.

3. Real Unix inodes use 12 direct pointers, not 4. Recompute which region blocks 0–7 (the document's title, table of contents, and footer) fall into under a 12-direct version of this scheme, and explain why a real file system would rather spend FCB space on more direct pointers than on deeper indirection.
   Show solution

   With 12 direct pointers, blocks 0–11 are all direct — so blocks 0–7 (title, TOC, footer) are entirely direct, 0 extra accesses for any of them. Under the 4-direct scheme this chapter uses, only blocks 0–3 are direct; blocks 4–7 already cost 1 extra access each, via the single-indirect block. Most files in practice are small enough to fit entirely (or almost entirely) in the direct pointers, so widening the direct set benefits the common case directly, while the indirect levels exist only to raise the ceiling for the rare large file — exactly the 340 KiB image here.

4. Synthesis. Chapter 1 gave every process a PCB kept separately from the process's own memory, so the OS could schedule and account for it without trusting the process to self-report. What's the equivalent argument for keeping a file's FCB separate from its data blocks, rather than, say, storing a file's size and permissions in its own first block?
   Show solution

   Same argument, one level down: if a file's metadata lived inside the file's own data, reading or changing that metadata would require trusting — or at least touching — content the file's writer controls, and a corrupted or malicious first block could misreport the file's own size or permissions. Keeping the FCB in a separate, OS-controlled structure means permission checks (7.5) and size accounting happen against data the file's own content can never touch, exactly as a process can't rewrite its own PCB to grant itself a higher priority.

An autosave is never really "one write." When T_save appends new text to the document, at least three things on disk have to change together: new data blocks holding the text, the inode's pointer list so those blocks are actually reachable (7.1), and the free-space structure marking those blocks as no longer available (7.3). If the power dies after the first change and before the third, the file system is now lying about something. The question this section answers is: lying about what, exactly, and how expensive is it to stop that.

The problem in one sentence: a transaction with no atomicity

A disk only guarantees that one block either gets fully written or doesn't (a single sector write doesn't tear). It makes no promise at all about several blocks written together. Writing three blocks is three separate physical events; a crash between any two of them leaves whichever finished, finished, and whichever didn't, not. Chapter 3 called this exact shape of problem a race — here the "other thread" racing T_save is the power supply.

Fix one: journaling — write the plan before the plan

A journal is a separate, append-only area of the disk. Before touching any of the real, fixed-location blocks, the file system writes a description of the whole transaction into the journal: which blocks are changing and what their new contents will be, capped by a commit record marking the transaction complete. Only after the commit record is safely on disk does the file system checkpoint — copy the changes from the journal into their real, final locations.

The payoff: recovery after a crash never has to guess. It reads the journal. Any transaction with a commit record gets replayed (redone) into its final locations. Any transaction without one is simply discarded, as if it had never been attempted — the file reverts to whatever it was before, cleanly, because none of its real blocks were touched until the journal proved the whole transaction survived. This is precisely the crash-recovery bookkeeping edits_logged was doing for WriteWell's own application-level undo history back in Chapter 3, one layer further down: a record you can trust after the fact, because it was made durable before the fact.

How much gets journaled — three real choices

Journaling doesn't have to cover everything, and what it covers is a genuine trade-off, not a solved problem. Linux's ext4 exposes exactly these three as mount options:

Fix two: log-structured design — never write in place at all

A log-structured file system (LFS) takes the idea one step further: don't keep separate "real" locations for data and metadata at all. Every write — new data blocks, the updated inode, the updated free-space bookkeeping — gets buffered and appended together, in one sequential chunk called a segment, to wherever the log currently ends. There is no checkpoint step copying things to a separate final location, because the log is the final location.

The catch is that an inode's location on disk now changes every time the file it describes is modified — it just got rewritten into the newest segment. LFS needs an extra layer, an inode map, translating a stable inode number to wherever that inode currently lives in the log, and that map itself needs a fixed, known location to bootstrap recovery from. Recovery after a crash means scanning forward from the last known-good checkpoint to find the last complete segment. And because old versions of blocks are never overwritten in place, just superseded by newer ones further down the log, disk space used by dead versions has to be reclaimed later by a background segment cleaner (garbage collector) — a cost LFS defers rather than eliminates.

Worked example — costing one autosave four ways

See it: watch a crash land at each point

Pick a design, then step through the transaction one write at a time. The panel shows what a crash right now would leave behind.

Pitfalls

Practice

1. Redo the worked example for a writeback-mode journal instead of ordered. Does the block-write count change?
   Show solution

   No. Writeback still journals only the 2 metadata blocks and checkpoints them, exactly like ordered mode: 2 (data) + 2 (journal) + 2 (checkpoint) = 6 block-writes, identical to ordered. The two modes cost the same in raw I/O; they differ only in the ordering guarantee between the data write and the journal commit, which is exactly why writeback can leave stale or garbage data after a crash even though its metadata is just as consistent as ordered mode's.

2. Repeat the worked example for a bigger autosave: 10 new data blocks instead of 2, metadata still 2 blocks. Compute all four totals and their ratios to the naive cost, and compare to the 2-data-block ratios above.
   Show solution

   Naive: 10+2 = 12. Metadata journal: 10+2+2 = 14 (14/12 ≈ 1.17×, down from 1.5× at the smaller size). Full journal: (10+2)×2 = 24 (24/12 = 2.00×, unchanged). LFS: 10+2 = 12, still sequential. Metadata-only journaling's overhead is fixed (2 extra blocks) regardless of transaction size, so its ratio shrinks as transactions grow; full journaling doubles every block it touches, so its ratio never moves.

3. Using the constant-ratio fact from the previous problem: WriteWell's original 340 KiB image is written once, as a single large sequential transaction, not many small autosaves. Roughly how many block-writes does full journaling cost for that one write, and why does the 2× overhead matter less here than it does for autosaves, even though the ratio is identical?
   Show solution

   340 data blocks, naive = 340 writes, full journal = 680 writes — exactly 2×, as always. But this is one transaction, done once, and the extra 340 writes are themselves sequential (checkpointing a large contiguous run stays contiguous). Autosaves happen repeatedly, every few seconds, for the life of the document, and their overhead is dominated by seek time between scattered small updates, not raw transfer volume — which is exactly the workload LFS was built to help, and exactly why a one-time bulk load barely notices the difference LFS makes for autosaves.

4. Synthesis. Does file-system journaling make WriteWell's own edits_logged crash-recovery counter from Chapter 3 redundant?
   Show solution

   No — they protect different things. The file system's journal guarantees the on-disk structure stays consistent: no orphaned or double-allocated blocks, regardless of what application was writing. edits_logged is WriteWell's own application-level count of edits applied, used to tell the user "recover 3 unsaved changes?" after a crash. A crash could leave the file system perfectly consistent (journal did its job) while WriteWell still lost the last few keystrokes that T_save hadn't gotten around to writing yet — the journal only protects transactions it was actually asked to make durable. The two mechanisms are complementary, not overlapping: one guards the disk's structure, the other guards the user's unsaved work.

Say WriteWell's user swaps the document's 340 KiB embedded image for a smaller, compressed one. Most of the old image's blocks are now free — nobody's file points at them anymore. Something still has to know that, or the next file created on this volume has nowhere to go. The file system needs a second piece of bookkeeping, entirely separate from any individual file's FCB: a running account of which blocks on the whole volume are currently unclaimed.

Four ways to remember what's empty

The requirement is simple to state and surprisingly fiddly to satisfy well: find a free block fast, release a block back to free fast, and don't spend much disk space doing either. Four classic designs trade those off differently.

Bit vector (bitmap)

One bit per block on the whole volume, 1 meaning free and 0 meaning allocated (or vice versa — pick a convention and never flip it). Finding a free block means scanning for a 1; finding n contiguous free blocks means scanning for a run of n ones, which a bitmap supports directly and the next two methods don't. The bitmap's size is fixed the moment the volume is formatted — it costs the same whether the disk is empty or nearly full.

Linked list (free list)

Free blocks are chained together: each free block stores, inside itself, the address of the next free block, starting from a head pointer kept in a fixed location. The appealing property: this costs essentially no dedicated disk space, because the pointers live inside blocks that are, by definition, not being used for anything else. The cost shows up on the read side instead — finding several free blocks means chasing several pointers, one disk access per block, in whatever order they happen to be linked.

Grouping

A fix for exactly that chasing cost: instead of one pointer per block, the first free block in a group stores the addresses of the next n free blocks directly. One read recovers n addresses at once instead of n separate reads.

Counting

Most deletions free a run of adjacent blocks (a file is usually written contiguously in one session), so instead of listing every free block's address individually, counting stores (start address, run length) pairs. A hundred contiguous free blocks become one entry, not a hundred.

Worked example — the same free space, four ways

A small volume, 16 blocks (0–15), 1 KiB each. The image swap above freed a contiguous run; two older, unrelated deletions left two single stray blocks elsewhere. Free blocks: 4, 5, 6, 7, 8, 9, 12, 14 — 8 of the 16.

See it: compare all four under three fragmentation patterns

Formal treatment: the cost that doesn't show up in the toy example

At 16 blocks, a bitmap's "fixed overhead" looks free. It isn't, at scale — and it's worth seeing the real number once.

128 KiB sounds small next to a gigabyte, and it is — but it's 128 KiB spent whether the volume is 1% full or 99% full, unlike a linked list, whose already-tiny overhead shrinks toward zero as the disk fills up and there's simply less free space left to chain together. The trade only flips back in the bitmap's favor because it's the only one of the four that supports scanning for a long contiguous run directly — which matters the moment a large sequential file (WriteWell's image) needs somewhere to go.

Pitfalls

Practice

1. A temp file occupying blocks 10 and 11 is also deleted, on top of the original scenario. Recompute the bitmap and the counting-method entries.
   Show solution

   Free set becomes 4,5,6,7,8,9,10,11,12,14 — 10 blocks. Blocks 4–12 are now one unbroken run of 9 (the original 4–9 run merges with the newly-freed 10, 11, and the previously isolated 12). Counting entries: (4, 9), (14, 1) — just 2 entries, down from 3, because deleting the temp file happened to bridge two previously separate free runs into one.

2. Same 16-block volume, but the 8 free blocks are fully scattered: 1, 3, 5, 7, 9, 11, 13, 15 (no two adjacent). How many entries does counting need now, and what does that say about counting's worst case?
   Show solution

   8 entries — every run has length 1, so counting stores exactly as many entries as there are free blocks. Its worst case is identical to a plain linked list's pointer count; counting never does worse than a list, it just sometimes fails to do better.

3. If the volume's block size doubled from 1 KiB to 2 KiB (same 1 GiB volume), what happens to the bitmap's size, and what did Chapter 5 call the cost of the larger block size that this savings trades against?
   Show solution

   Half as many blocks (524,288 instead of 1,048,576) means half the bitmap: 64 KiB instead of 128 KiB. In general, bitmap size is inversely proportional to block size for a fixed volume. The trade is Chapter 5's internal fragmentation: a 2 KiB block wastes up to 2 KiB per file's last, partially-used block instead of up to 1 KiB — smaller bitmaps, bigger average waste per file.

4. Synthesis. WriteWell's image swap freed a contiguous run precisely because the image was originally written as one uninterrupted sequential write (7.1's worked example: blocks 8–347, all at once). Would a heavily fragmented free-space pattern have been more or less likely if the image had instead been built up out of many small, separately-timed edits, the way the autosave transactions in 7.2 work?
   Show solution

   More fragmented. A single large sequential write tends to land in one contiguous run because the allocator can satisfy the whole request from one nearby stretch of free space. Many small edits spread over time interleave with other files' allocations and deletions happening in between, so the blocks belonging to one logical file end up scattered wherever the allocator happened to find room at each separate moment — the same reason 7.2's autosave workload (frequent, small, scattered writes) is the one log-structured design was built to help, rather than the one-shot bulk write.

7.1 through 7.3 each measured one design decision on its own terms — accesses to reach a block, writes to survive a crash, entries to describe free space. This section puts them on the same scale: bytes of metadata, and disk accesses, for the one file this chapter has followed the whole way through.

Metadata overhead: one pointer per block adds up

7.1's indexed allocation names every block with its own 4-byte pointer, however those blocks happen to sit on disk. That's fine when a file is scattered, and wasteful when it isn't — and WriteWell's 340 KiB image, written in one sequential burst (7.1), is exactly the case where it isn't.

An extent is the alternative: instead of one pointer per block, describe a whole contiguous run as (start block, length) — two numbers covering however many blocks happen to be contiguous. Modern journaling file systems (ext4, NTFS, XFS) all allocate this way by default; pure per-block indexed allocation is what older designs (FAT, early Unix) actually did.

See it: watch the crossover as the image grows

The overhead ratio above isn't fixed — it depends on whether the file is big enough to need indirection at all. Drag the image size and watch both the region it lands in (7.1) and the metadata cost (this section) update together.

Two workloads, two different bottom lines

7.2 costed a single small autosave transaction four ways: naive 4 writes, metadata-journal 6 (1.5×), full journal 8 (2.0×), log-structured 4, all sequential. Scaled up to a one-shot 340-block write (practice problem 3 of that section), full journaling still costs exactly 2× — 680 writes instead of 340 — but that overhead is far less painful there than it is for autosaves.

This is precisely the gap log-structured design was invented to close (7.2): it can't do anything for the one-shot transfer that in-place allocation wasn't already doing reasonably well, but it turns the repeated, scattered small-write workload into one sequential stream every time, which is where its win actually lives.

Pitfalls

Practice

1. Recompute the metadata overhead percentage and the indexed:extent ratio if the embedded image were 100 KiB instead of 340 KiB (title, TOC, footer unchanged).
   Show solution

   Total blocks = 2+5+1+100 = 108, which is less than 260 (direct + single-indirect capacity) — no double-indirect needed at all. Metadata: just 1 single-indirect block = 1,024 bytes. Overhead = 1,024 ÷ (108×1,024) = 0.93% (close to the 340 KiB case's 0.86%, because both are dominated by one mostly-full index block). Extent-based: still 4 extents = 32 bytes. Ratio = 1,024 ÷ 32 = 32×, down from 96× — a smaller file that never reaches double-indirection has proportionally less to gain from switching to extents.

2. Confirm that full journaling's write-amplification ratio for the one-shot 340-block image write really is exactly 2.0×, and explain in one sentence why that number never changes with size.
   Show solution

   Naive = 340, full journal = 340 (to the journal) + 340 (checkpointed to final location) = 680. 680 ÷ 340 = 2.0×, exactly, matching every other size checked in this chapter. It never changes because full journaling always writes every changed block exactly twice, by definition — the ratio is a property of the mechanism, not of how much data happens to be moving through it.

3. Using the crossover widget above: at roughly what image size does the file stop needing double-indirection at all (i.e. total blocks stays within direct + single-indirect capacity)? What happens to the metadata overhead percentage right at that boundary?
   Show solution

   Direct (4 blocks) plus a fully-used single-indirect block (256 blocks) covers 260 blocks total. Total blocks = 8 (title+TOC+footer) + image size in KiB ≤ 260 ⇒ image size ≤ 252 KiB. Just above that boundary (253 KiB, 261 total blocks), the file needs a double-indirect block it didn't need at 252 KiB — metadata jumps from 1 index block (1,024 B) to 3 (3,072 B), a discrete step up, even though the file grew by only 1 KiB. Metadata overhead under indexed allocation isn't smooth; it jumps at every boundary where a new level of indirection first gets triggered.

4. Synthesis. 7.3 showed a bitmap is the only free-space method that supports finding a long contiguous run directly. Explain why that property specifically benefits an extent-based file system more than it benefits a purely indexed one.
   Show solution

   An extent's entire value proposition is describing a run of contiguous blocks in one small entry. That only works if the allocator can actually find a long contiguous run of free blocks to hand out in the first place — which is exactly what a bitmap's run-scanning supports and a plain linked free list doesn't do efficiently. A purely indexed file system doesn't care whether the blocks it's handed are contiguous at all, since it names each one individually regardless; it can get by on whatever free-space method, including a plain list. Extent-based allocation and bitmap-style free-space tracking are a matched pair for exactly this reason.

WriteWell's document is about to stop being Alice's alone. Bob needs to review it. Alice would rather Carol, who shares Alice's team, didn't see this particular draft yet. Every question in this section is a version of the same one: the FCB's protection field (7.1) has to answer "is this specific requester allowed to do this specific thing", and the two operating systems this chapter has compared throughout answer it in genuinely different shapes.

Linux: three categories, checked in a fixed order

POSIX permissions attach three sets of rwx bits (read, write, execute) to a file: one for its owner, one for its group, one for other (everyone else). Nine bits total, conventionally written as three octal digits — rwxr-x--- is 750: owner 7 (rwx), group 5 (r-x), other 0 (none).

The part that surprises people: a request is checked against exactly one of the three categories, never more than one, decided by who's asking — not by which category happens to be most generous.

And POSIX's three fixed categories can't express some genuinely ordinary requests at all. "Let Bob read this, but not Carol, without touching the 'editors' group membership either of them has" has no answer in plain owner/group/other — there's no fourth slot for "this one specific other person." (POSIX ACLs exist as an optional extension precisely to patch this gap, at the cost of no longer being three simple numbers.)

Windows: an ordered list of named grants and denials

NTFS takes a structurally different approach: an Access Control List (ACL) attached to the file is a sequence of Access Control Entries (ACEs), each one naming a specific user or group and either Allowing or Denying a specific right. There's no fixed category count — a file can have an ACE for Alice, a separate one for Bob specifically, another for the "editors" group, as many as needed.

NTFS evaluates explicit Deny entries before any Allow entry, regardless of list position — so entry 1 blocks Carol even if she's separately a member of "editors," which entry 3 would otherwise allow. This single mechanism does both things POSIX bits above struggled with: it grants Bob access without touching group membership, and it excludes Carol from a group grant without removing her from the group. The price is that "what can Bob do?" now requires walking a list instead of reading three fixed fields.

See it: check anyone's effective access

It opens on Worked Example 7.5 (mode 640, checked as group) — matching the r-- just derived by hand above. Try owner 0, group 7, other 7, checked as owner, for the classic self-inflicted lockout — or switch to mode 604, checked as group, for the stranger-beats-member gotcha from the trap box.

Pitfalls

Practice

1. Mode is 750. Requester is the file's owner. What access do they get, and which category was actually checked?
   Show solution

   Owner bits = 7 (rwx), full access. Only the owner category is ever checked once the requester is confirmed to be the owner — group and other bits (5 and 0) are irrelevant to this specific request.

2. Mode is 604, requester is in the file's group. What access, and is it more or less than a complete stranger would get on this same file?
   Show solution

   Group bits = 0 (---), no access at all. A stranger falls to other = 4 (r--), read access — strictly more than the group member gets. Group membership was a strict downgrade here.

3. Design an ACE list (identity, Allow/Deny, right) that grants "editors" read access, denies Carol specifically even though she's an editor, and grants Alice full control — then explain why the Carol entry has to be a Deny rather than simply "no entry for Carol."
   Show solution

   (1) Carol — Deny — Read. (2) Editors — Allow — Read. (3) Alice — Allow — Full control. Carol needs an explicit Deny, not silence, because she's also a member of "editors" — without an explicit Deny, the Allow-Read entry for the group would grant her read access through that membership. "No entry" only withholds a right nothing else grants; here, something else (the group) already does.

4. Synthesis. Chapter 1 contrasted Linux and Windows kernel and threading designs throughout, and this chapter has done the same for their permission models. In one sentence each: what does the fixed-category POSIX approach buy in exchange for the gotchas above, and what does NTFS's per-identity ACL approach cost in exchange for avoiding them?
   Show solution

   POSIX buys a permission check that's always exactly three fixed fields, checkable at a glance and cheap to store and evaluate, at the cost of expressiveness (no per-individual grants without an extension, and an unintuitive fixed check order). NTFS buys arbitrary per-identity Allow/Deny grants with no such gotchas, at the cost of a variable-length structure that has to be walked, and a Deny-before-Allow evaluation rule that itself has to be learned and remembered correctly.

1. A volume's free blocks are 20, 21, 22, and 30. How many entries does the counting method need to describe them?
   Show solution

   Two: (20, 3) for the contiguous run 20–22, and (30, 1) for the isolated block 30. (7.3)

2. Which ext4 journaling mode is the one that forces a file's data blocks to reach disk before the metadata transaction referencing them is committed?
   Show solution

   ordered mode — ext4's default. writeback journals the same metadata but enforces no such ordering, which is exactly why it can leave stale or garbage data after a crash even though its metadata stays consistent. (7.2)

3. A scheme uses 512-byte blocks, 4-byte pointers, and 2 direct pointers. How many pointers fit in one index block, and what logical block range does direct-plus-single-indirect cover?
   Show solution

   Pointers per index block = 512 ÷ 4 = 128. Direct covers blocks 0–1 (2 blocks). Single-indirect then covers blocks 2 through 2+128−1 = 129, 128 blocks. (7.1)

4. Mode is 470 (owner r--, group rwx, other ---). A request comes from the file's owner. What governs the decision, and what access results — full access, since group is more generous, or something else?
   Show solution

   The owner category governs, because the check stops at the first matching category and never considers the others. Access = r-- (read only), even though the group bits (rwx) would have allowed everything. The owner's own bits are all that's ever consulted for the owner. (7.5)

5. True or false: an extent-based file system's metadata advantage over pure indexed allocation disappears once a file is fragmented into many small, non-contiguous runs.
   Show solution

   True. An extent only pays for itself when it covers many blocks in one contiguous run; a file broken into as many fragments as it has blocks needs one extent per block, which is no better than one pointer per block — the exact case pure indexed allocation already handles at the same cost. (7.4)

6. From a cold cache, which costs more disk accesses to reach: a block addressed through single-indirection, or one addressed through double-indirection — and by how much?
   Show solution

   Double-indirection, by exactly one extra access (2 extra accesses total, versus single-indirection's 1). Every additional level of indirection this scheme adds costs exactly one more disk access, every time. (7.1)

7. Log-structured design's segment cleaner reclaims a large, mostly-superseded segment and gets back one long contiguous run of newly-free blocks. Which of 7.3's four free-space methods represents that outcome most compactly?
   Show solution

   Counting — one contiguous run collapses to a single (start, count) entry regardless of how large the run is, exactly the shape a segment cleaner's output tends to take. A bitmap would represent the same run correctly, but at its usual fixed per-volume cost rather than a cost that shrinks to one entry for one big run. (7.2, 7.3)

8. An FCB's protection field and its location (block-pointer) field are both consulted before any byte of a file is returned to a requester. Why does the protection check have to happen before the location field is ever used to fetch a block?
   Show solution

   Because touching the location field at all means doing real, costly work — tracing pointers, reading index blocks, reading data — on behalf of a requester who might not be allowed to see any of it. Checking protection first means an unauthorized request is rejected before the file system spends a single disk access resolving where its data even is, and before anything about the file's size or structure is exposed to someone who has no right to know it. (7.1, 7.5)

Further reading

• Stallings, Operating Systems: Internals and Design Principles, 9th ed., Ch. 12. This course's primary text; closest match to this chapter's structure across all five sections.
• Silberschatz, Galvin & Gagne, Operating System Concepts, 10th ed., Ch. 13–14. The standard reference treatment of the file-system interface and its implementation — allocation methods, free-space management, and protection.
• McKusick, Joy, Leffler & Fabry, "A Fast File System for UNIX," ACM TOCS, 1984. The paper behind Section 7.1's inode-based indexed allocation as actually built, and the source of the block-group placement ideas that make real allocation less scattered than the worst case this chapter traces.
• Rosenblum & Ousterhout, "The Design and Implementation of a Log-Structured File System," ACM TOCS, 1992. The original paper behind Section 7.2's log-structured design and its segment cleaner, still the clearest primary source for why it exists.