Skip to content
CampusPrep
CS-405 · Operating Systems/Quick Revision Short Notes

Operating Systems (CS-405) - Unit 2 Short Notes

How unit 2 is examined

This unit covers files, disks, tapes, allocation, directories, protection and disk scheduling; file concept, allocation and disk scheduling carry the marks.

File Concept

<span style="display:inline-block;padding:.16em .6em;border:1.5px solid currentColor;border-radius:999px;font-size:.68em;font-weight:700;letter-spacing:.06em;text-transform:uppercase;opacity:.75">High weight</span>

Definition. <mark>A file is a named collection of related information recorded on secondary storage, presented by the operating system as the smallest logical unit of storage.</mark>

Key points.

  1. A file has contents that the OS treats as bytes, records or lines.
  2. Name is the human-readable label, while the identifier is a unique number (such as the inode number) used internally.
  3. Type tells the system how to interpret the file, shown by an extension (.c, .exe) or a magic number in the file.
  4. Location points to the device and blocks holding the file, and size is its length.
  5. Protection holds access permissions (read, write, execute), and time, date and user identification record creation and use.
  6. Basic operations are create, write, read, reposition (seek), delete and truncate (append and rename are common additions); truncate erases the contents but keeps the attributes (name, owner, permissions), so length becomes zero.
  7. The open-file table lets open() load attributes once, avoiding a directory search on every call.

Comparison: type tracked by the system versus left to the user.

Point System tracks type Left to user
Protection Blocks wrong use, e.g. executing a text file No safety net
Operation Picks the right program automatically User chooses
Flexibility Rigid, new formats need OS support Any file treated any way
OS size Larger Simple byte streams
Example Old Macintosh, VMS UNIX

Macintosh and VMS track type so the system can refuse wrong use (executing a text file) and launch the right program when a file is opened; UNIX leaves it to the user because a plain byte stream keeps the OS simple and lets any program process any file. Verdict: the UNIX byte stream is better for a general-purpose system, because flexibility and a small OS outweigh safety, which extensions and magic numbers still largely recover; typed files win only where safety is critical.

Answer frame. Open with the definition; tabulate the attributes with one-line meanings; give each operation a line. For the type question, give the table and close with your verdict.

Asked: [7 marks] (Nov 2019, Nov 2023) What is File? What are the different File attributes and operations? Asked: [7 marks] (Nov 2023) What is a File? Write different file attributes and operations? Asked: [7 marks] (Jun 2024) Why do some systems keep track of the type of file, while others leave it to the user or do not implement multiple file types? Which system is better? Pitfall: Listing attributes and operations as bare words earns little; give each a one-line meaning.

User's and System Programmer's View of File System

<span style="display:inline-block;padding:.16em .6em;border:1.5px solid currentColor;border-radius:999px;font-size:.68em;font-weight:700;letter-spacing:.06em;text-transform:uppercase;opacity:.75">Low weight</span>

Definition. The user's view is how files are named, grouped in directories and accessed; the system programmer's view is how they are mapped onto disk blocks, buffers and tables.

Key points.

  1. The user sees files, directories, names and operations, and does not care where bytes sit.
  2. The system programmer sees block allocation, free-space records and buffering.
  3. Sequential access reads records one after another, as in a payroll run, a backup job, a compiler reading source or music playback.
  4. Random (direct) access jumps to any block by number, as in a database, a bank account record, an ATM balance or an airline reservation table.
  5. Random access uses lseek(fd, offset, SEEK_SET) to move the position before read or write, while sequential access needs only read and write.
  6. Verdict: neither is better overall; sequential suits whole-file processing, random suits small look-ups, and a good file system supports both.

Asked: [7 marks] (Jun 2025) Give an example of an application in which data in a file should be accessed (i) sequentially, (ii) randomly.

Disk Organization

<span style="display:inline-block;padding:.16em .6em;border:1.5px solid currentColor;border-radius:999px;font-size:.68em;font-weight:700;letter-spacing:.06em;text-transform:uppercase;opacity:.75">Medium weight</span>

Definition. <mark>A disk is organised as platters with concentric tracks divided into sectors, and the same track on all platters forms a cylinder.</mark>

Diagram.

<figure class="ds-fig" style="margin:1.4rem 0;overflow-x:auto"><svg xmlns="http://www.w3.org/2000/svg" id="dsfig-u2-01" viewBox="0 0 596 252" width="596" height="252" role="img" aria-label="Disk geometry. Spn spindle, Plt platter, Trk track, Sec sector, Hd head, Arm actuator arm."><style>#dsfig-u2-01 .e{stroke:#454C5A;stroke-width:1.4;fill:none}#dsfig-u2-01 .e.hi{stroke:#2340B8;stroke-width:2.6}#dsfig-u2-01 .n{fill:#FFFFFF;stroke:#16181D;stroke-width:1.4}#dsfig-u2-01 .n.hi{fill:#E3E9FC;stroke:#2340B8;stroke-width:2.2}#dsfig-u2-01 .n.rb-b{fill:#16181D;stroke:#16181D}#dsfig-u2-01 .n.rb-r{fill:#BD3227;stroke:#BD3227}#dsfig-u2-01 text{font-family:"JetBrains Mono",ui-monospace,Menlo,Consolas,monospace;font-size:13px}#dsfig-u2-01 .t{fill:#16181D;font-weight:500}#dsfig-u2-01 .t.inv{fill:#FFFFFF;font-weight:700}#dsfig-u2-01 .kd{stroke:#16181D;stroke-width:1.2}#dsfig-u2-01 .dot{fill:#16181D}#dsfig-u2-01 .ann{fill:#2340B8;font-size:11px;font-weight:700}#dsfig-u2-01 .lbl{fill:#6F7787;font-family:system-ui,-apple-system,sans-serif;font-size:12px;font-weight:700}#dsfig-u2-01 .ptr{fill:#2340B8;font-size:12px;font-weight:700}#dsfig-u2-01 .ah{fill:#454C5A}#dsfig-u2-01 .ah.hi{fill:#2340B8}#dsfig-u2-01 .wl rect{fill:#FFFFFF;stroke:#DCE0E7}#dsfig-u2-01 .wl .t{font-size:12px;font-weight:700}#dsfig-u2-01 .wl.hi rect{fill:#2340B8;stroke:#2340B8}#dsfig-u2-01 .wl.hi .t{fill:#FFFFFF}html.dark #dsfig-u2-01 .e{stroke:#B1B7C3}html.dark #dsfig-u2-01 .e.hi{stroke:#8FA3FF}html.dark #dsfig-u2-01 .n{fill:#161920;stroke:#E6E8ED}html.dark #dsfig-u2-01 .n.hi{fill:#1E2748;stroke:#8FA3FF}html.dark #dsfig-u2-01 .n.rb-b{fill:#E6E8ED;stroke:#E6E8ED}html.dark #dsfig-u2-01 .n.rb-r{fill:#FF7E71;stroke:#FF7E71}html.dark #dsfig-u2-01 .t{fill:#E6E8ED}html.dark #dsfig-u2-01 .t.inv{fill:#0F1115}html.dark #dsfig-u2-01 .kd{stroke:#E6E8ED}html.dark #dsfig-u2-01 .dot{fill:#E6E8ED}html.dark #dsfig-u2-01 .ann{fill:#8FA3FF}html.dark #dsfig-u2-01 .lbl{fill:#858D9C}html.dark #dsfig-u2-01 .ptr{fill:#8FA3FF}html.dark #dsfig-u2-01 .ah{fill:#B1B7C3}html.dark #dsfig-u2-01 .ah.hi{fill:#8FA3FF}html.dark #dsfig-u2-01 .wl rect{fill:#161920;stroke:#2A2E37}html.dark #dsfig-u2-01 .wl.hi rect{fill:#8FA3FF;stroke:#8FA3FF}html.dark #dsfig-u2-01 .wl.hi .t{fill:#0F1115}</style><defs><marker id="ah7" viewBox="0 0 10 10" refX="9" refY="5" markerWidth="7" markerHeight="7" orient="auto-start-reverse"><path class="ah" d="M0,1 L9,5 L0,9 z"/></marker><marker id="ahh7" viewBox="0 0 10 10" refX="9" refY="5" markerWidth="7" markerHeight="7" orient="auto-start-reverse"><path class="ah hi" d="M0,1 L9,5 L0,9 z"/></marker></defs><path class="e" d="M59,126 L148,126" marker-end="url(#ah7)"/><path class="e" d="M184.8,115.5 L280.5,51.6" marker-end="url(#ah7)"/><path class="e" d="M184.8,136.5 L280.5,200.4" marker-end="url(#ah7)"/><path class="e" d="M313.8,50.5 L409.5,114.4" marker-end="url(#ah7)"/><path class="e" d="M313.8,201.5 L409.5,137.6" marker-end="url(#ah7)"/><path class="e" d="M446,126 L535,126" marker-end="url(#ah7)"/><circle class="n" cx="40" cy="126" r="18"/><text class="t" x="40" y="126" dy=".35em" text-anchor="middle">Spn</text><circle class="n" cx="169" cy="126" r="18"/><text class="t" x="169" y="126" dy=".35em" text-anchor="middle">Plt</text><circle class="n" cx="298" cy="40" r="18"/><text class="t" x="298" y="40" dy=".35em" text-anchor="middle">Trk</text><circle class="n" cx="298" cy="212" r="18"/><text class="t" x="298" y="212" dy=".35em" text-anchor="middle">Sec</text><circle class="n" cx="427" cy="126" r="18"/><text class="t" x="427" y="126" dy=".35em" text-anchor="middle">Hd</text><circle class="n" cx="556" cy="126" r="18"/><text class="t" x="556" y="126" dy=".35em" text-anchor="middle">Arm</text></svg><figcaption style="font-size:.82em;opacity:.72;margin-top:.45rem">Disk geometry. Spn spindle, Plt platter, Trk track, Sec sector, Hd head, Arm actuator arm.</figcaption></figure>

Key points.

  1. A platter is a circular magnetic disk, with a read/write head per surface on a common arm.
  2. Each surface has concentric tracks divided into sectors, the smallest unit read or written.
  3. Tracks at the same arm position on all platters form a cylinder.
  4. The disk controller takes a block address, moves the arm and transfers data.
  5. The arm seeks to the cylinder (seek time), the sector rotates under the head (rotational latency), then data transfers (transfer time).
  6. To write, the controller moves the arm to the track, waits for the sector to pass under the head, and the head magnetises the surface in a pattern of bits; to read, the head senses that pattern as changing magnetic flux, which the controller converts back to data. A sector holds a header (sector number, sync bytes), the data area (512 B or 4 KB), and an error-correcting code, separated from the next sector by a gap.
  7. A file system is the part of the OS that stores, names and retrieves files, allocating space in blocks (one or more sectors, e.g. 4 KB).
  8. Logical organisation is the user's view of a file as records or a byte stream, mapped by the file system to blocks.
  9. Access methods: sequential reads in order, direct jumps to block n, and indexed looks up a key in an index and then reads its block.
  10. Example: seek 10 ms, latency at 7200 rpm is 60000/7200/2 = 4.17 ms, transfer of 4 KB at 100 MB/s is 0.04 ms, so access time = 10 + 4.17 + 0.04 = 14.21 ms.

Answer frame. Define; draw the disk; develop structure, controller, seek, latency, transfer; close with access time as their sum.

Asked: [7 marks] (Nov 2023, Jun 2026) Explain disk structure. How data is read and written on disk? Explain file systems and disk organization.

Tape Organization

<span style="display:inline-block;padding:.16em .6em;border:1.5px solid currentColor;border-radius:999px;font-size:.68em;font-weight:700;letter-spacing:.06em;text-transform:uppercase;opacity:.75">Low weight</span>

Definition. Magnetic tape is a long plastic strip coated with magnetic material, storing data serially in tracks along its length.

Key points.

  1. Advantages: it is cheap per byte, has very large capacity, is portable and reliable for long-term backup and archival.
  2. Disadvantages: access is strictly sequential, so a record is reached by winding past earlier ones.
  3. Tape is sensitive to dust, heat and magnetic fields and cannot be updated in the middle, so it serves backups and archives, not online data.
  4. Data is written in blocks separated by inter-block gaps that let the drive stop and restart.
|BOT|block|gap|block|gap|block|gap|EOT|

Asked: [7 marks] (Jun 2023) List the advantages and disadvantages of Magnetic Tape memory.

Different Modules of a File System

<span style="display:inline-block;padding:.16em .6em;border:1.5px solid currentColor;border-radius:999px;font-size:.68em;font-weight:700;letter-spacing:.06em;text-transform:uppercase;opacity:.75">Not asked since 2022</span>

Definition. The file system is built in layers, each using the layer below it.

Key points.

  1. Applications call the logical file system, which manages directories, names and protection.
  2. The file-organisation module maps logical to physical blocks and free space.
  3. The basic file system sends generic commands to the device driver, which talks to the hardware.

Disk Space Allocation Methods – Contiguous, Linked, Indexed

<span style="display:inline-block;padding:.16em .6em;border:1.5px solid currentColor;border-radius:999px;font-size:.68em;font-weight:700;letter-spacing:.06em;text-transform:uppercase;opacity:.75">High weight</span>

Definition. <mark>Allocation decides which disk blocks hold each file, and the three classic methods are contiguous, linked and indexed.</mark>

Diagram.

<figure class="ds-fig" style="margin:1.4rem 0;overflow-x:auto"><svg xmlns="http://www.w3.org/2000/svg" id="dsfig-u2-02" viewBox="0 0 596 166" width="596" height="166" role="img" aria-label="Linked allocation. Directory holds first block 9; each block points to the next; the last is nil."><style>#dsfig-u2-02 .e{stroke:#454C5A;stroke-width:1.4;fill:none}#dsfig-u2-02 .e.hi{stroke:#2340B8;stroke-width:2.6}#dsfig-u2-02 .n{fill:#FFFFFF;stroke:#16181D;stroke-width:1.4}#dsfig-u2-02 .n.hi{fill:#E3E9FC;stroke:#2340B8;stroke-width:2.2}#dsfig-u2-02 .n.rb-b{fill:#16181D;stroke:#16181D}#dsfig-u2-02 .n.rb-r{fill:#BD3227;stroke:#BD3227}#dsfig-u2-02 text{font-family:"JetBrains Mono",ui-monospace,Menlo,Consolas,monospace;font-size:13px}#dsfig-u2-02 .t{fill:#16181D;font-weight:500}#dsfig-u2-02 .t.inv{fill:#FFFFFF;font-weight:700}#dsfig-u2-02 .kd{stroke:#16181D;stroke-width:1.2}#dsfig-u2-02 .dot{fill:#16181D}#dsfig-u2-02 .ann{fill:#2340B8;font-size:11px;font-weight:700}#dsfig-u2-02 .lbl{fill:#6F7787;font-family:system-ui,-apple-system,sans-serif;font-size:12px;font-weight:700}#dsfig-u2-02 .ptr{fill:#2340B8;font-size:12px;font-weight:700}#dsfig-u2-02 .ah{fill:#454C5A}#dsfig-u2-02 .ah.hi{fill:#2340B8}#dsfig-u2-02 .wl rect{fill:#FFFFFF;stroke:#DCE0E7}#dsfig-u2-02 .wl .t{font-size:12px;font-weight:700}#dsfig-u2-02 .wl.hi rect{fill:#2340B8;stroke:#2340B8}#dsfig-u2-02 .wl.hi .t{fill:#FFFFFF}html.dark #dsfig-u2-02 .e{stroke:#B1B7C3}html.dark #dsfig-u2-02 .e.hi{stroke:#8FA3FF}html.dark #dsfig-u2-02 .n{fill:#161920;stroke:#E6E8ED}html.dark #dsfig-u2-02 .n.hi{fill:#1E2748;stroke:#8FA3FF}html.dark #dsfig-u2-02 .n.rb-b{fill:#E6E8ED;stroke:#E6E8ED}html.dark #dsfig-u2-02 .n.rb-r{fill:#FF7E71;stroke:#FF7E71}html.dark #dsfig-u2-02 .t{fill:#E6E8ED}html.dark #dsfig-u2-02 .t.inv{fill:#0F1115}html.dark #dsfig-u2-02 .kd{stroke:#E6E8ED}html.dark #dsfig-u2-02 .dot{fill:#E6E8ED}html.dark #dsfig-u2-02 .ann{fill:#8FA3FF}html.dark #dsfig-u2-02 .lbl{fill:#858D9C}html.dark #dsfig-u2-02 .ptr{fill:#8FA3FF}html.dark #dsfig-u2-02 .ah{fill:#B1B7C3}html.dark #dsfig-u2-02 .ah.hi{fill:#8FA3FF}html.dark #dsfig-u2-02 .wl rect{fill:#161920;stroke:#2A2E37}html.dark #dsfig-u2-02 .wl.hi rect{fill:#8FA3FF;stroke:#8FA3FF}html.dark #dsfig-u2-02 .wl.hi .t{fill:#0F1115}</style><defs><marker id="ah8" viewBox="0 0 10 10" refX="9" refY="5" markerWidth="7" markerHeight="7" orient="auto-start-reverse"><path class="ah" d="M0,1 L9,5 L0,9 z"/></marker><marker id="ahh8" viewBox="0 0 10 10" refX="9" refY="5" markerWidth="7" markerHeight="7" orient="auto-start-reverse"><path class="ah hi" d="M0,1 L9,5 L0,9 z"/></marker></defs><path class="e" d="M57,117.5 L193.2,49.4" marker-end="url(#ah8)"/><path class="e" d="M231,40 L320,40" marker-end="url(#ah8)"/><path class="e" d="M360,40 L449,40" marker-end="url(#ah8)"/><path class="e" d="M489,40 L535,40" marker-end="url(#ah8)"/><circle class="n" cx="40" cy="126" r="18"/><text class="t" x="40" y="126" dy=".35em" text-anchor="middle">Dir</text><circle class="n" cx="212" cy="40" r="18"/><text class="t" x="212" y="40" dy=".35em" text-anchor="middle">B9</text><circle class="n" cx="341" cy="40" r="18"/><text class="t" x="341" y="40" dy=".35em" text-anchor="middle">B16</text><circle class="n" cx="470" cy="40" r="18"/><text class="t" x="470" y="40" dy=".35em" text-anchor="middle">B1</text><circle class="n" cx="556" cy="40" r="18"/><text class="t" x="556" y="40" dy=".35em" text-anchor="middle">B25</text></svg><figcaption style="font-size:.82em;opacity:.72;margin-top:.45rem">Linked allocation. Directory holds first block 9; each block points to the next; the last is nil.</figcaption></figure>

<figure class="ds-fig" style="margin:1.4rem 0;overflow-x:auto"><svg xmlns="http://www.w3.org/2000/svg" id="dsfig-u2-03" viewBox="0 0 510 80" width="510" height="80" role="img" aria-label="Contiguous allocation. Directory holds start 14 and length 4."><style>#dsfig-u2-03 .e{stroke:#454C5A;stroke-width:1.4;fill:none}#dsfig-u2-03 .e.hi{stroke:#2340B8;stroke-width:2.6}#dsfig-u2-03 .n{fill:#FFFFFF;stroke:#16181D;stroke-width:1.4}#dsfig-u2-03 .n.hi{fill:#E3E9FC;stroke:#2340B8;stroke-width:2.2}#dsfig-u2-03 .n.rb-b{fill:#16181D;stroke:#16181D}#dsfig-u2-03 .n.rb-r{fill:#BD3227;stroke:#BD3227}#dsfig-u2-03 text{font-family:"JetBrains Mono",ui-monospace,Menlo,Consolas,monospace;font-size:13px}#dsfig-u2-03 .t{fill:#16181D;font-weight:500}#dsfig-u2-03 .t.inv{fill:#FFFFFF;font-weight:700}#dsfig-u2-03 .kd{stroke:#16181D;stroke-width:1.2}#dsfig-u2-03 .dot{fill:#16181D}#dsfig-u2-03 .ann{fill:#2340B8;font-size:11px;font-weight:700}#dsfig-u2-03 .lbl{fill:#6F7787;font-family:system-ui,-apple-system,sans-serif;font-size:12px;font-weight:700}#dsfig-u2-03 .ptr{fill:#2340B8;font-size:12px;font-weight:700}#dsfig-u2-03 .ah{fill:#454C5A}#dsfig-u2-03 .ah.hi{fill:#2340B8}#dsfig-u2-03 .wl rect{fill:#FFFFFF;stroke:#DCE0E7}#dsfig-u2-03 .wl .t{font-size:12px;font-weight:700}#dsfig-u2-03 .wl.hi rect{fill:#2340B8;stroke:#2340B8}#dsfig-u2-03 .wl.hi .t{fill:#FFFFFF}html.dark #dsfig-u2-03 .e{stroke:#B1B7C3}html.dark #dsfig-u2-03 .e.hi{stroke:#8FA3FF}html.dark #dsfig-u2-03 .n{fill:#161920;stroke:#E6E8ED}html.dark #dsfig-u2-03 .n.hi{fill:#1E2748;stroke:#8FA3FF}html.dark #dsfig-u2-03 .n.rb-b{fill:#E6E8ED;stroke:#E6E8ED}html.dark #dsfig-u2-03 .n.rb-r{fill:#FF7E71;stroke:#FF7E71}html.dark #dsfig-u2-03 .t{fill:#E6E8ED}html.dark #dsfig-u2-03 .t.inv{fill:#0F1115}html.dark #dsfig-u2-03 .kd{stroke:#E6E8ED}html.dark #dsfig-u2-03 .dot{fill:#E6E8ED}html.dark #dsfig-u2-03 .ann{fill:#8FA3FF}html.dark #dsfig-u2-03 .lbl{fill:#858D9C}html.dark #dsfig-u2-03 .ptr{fill:#8FA3FF}html.dark #dsfig-u2-03 .ah{fill:#B1B7C3}html.dark #dsfig-u2-03 .ah.hi{fill:#8FA3FF}html.dark #dsfig-u2-03 .wl rect{fill:#161920;stroke:#2A2E37}html.dark #dsfig-u2-03 .wl.hi rect{fill:#8FA3FF;stroke:#8FA3FF}html.dark #dsfig-u2-03 .wl.hi .t{fill:#0F1115}</style><defs><marker id="ah9" viewBox="0 0 10 10" refX="9" refY="5" markerWidth="7" markerHeight="7" orient="auto-start-reverse"><path class="ah" d="M0,1 L9,5 L0,9 z"/></marker><marker id="ahh9" viewBox="0 0 10 10" refX="9" refY="5" markerWidth="7" markerHeight="7" orient="auto-start-reverse"><path class="ah hi" d="M0,1 L9,5 L0,9 z"/></marker></defs><path class="e" d="M59,40 L191,40" marker-end="url(#ah9)"/><path class="e" d="M231,40 L279,40"/><path class="e" d="M317,40 L365,40"/><path class="e" d="M403,40 L451,40"/><circle class="n" cx="40" cy="40" r="18"/><text class="t" x="40" y="40" dy=".35em" text-anchor="middle">Dir</text><circle class="n" cx="212" cy="40" r="18"/><text class="t" x="212" y="40" dy=".35em" text-anchor="middle">B14</text><circle class="n" cx="298" cy="40" r="18"/><text class="t" x="298" y="40" dy=".35em" text-anchor="middle">B15</text><circle class="n" cx="384" cy="40" r="18"/><text class="t" x="384" y="40" dy=".35em" text-anchor="middle">B16</text><circle class="n" cx="470" cy="40" r="18"/><text class="t" x="470" y="40" dy=".35em" text-anchor="middle">B17</text></svg><figcaption style="font-size:.82em;opacity:.72;margin-top:.45rem">Contiguous allocation. Directory holds start 14 and length 4.</figcaption></figure>

<figure class="ds-fig" style="margin:1.4rem 0;overflow-x:auto"><svg xmlns="http://www.w3.org/2000/svg" id="dsfig-u2-04" viewBox="0 0 381 260.6" width="381" height="260.6" role="img" aria-label="Indexed allocation. The index block lists the file's blocks in order."><style>#dsfig-u2-04 .e{stroke:#454C5A;stroke-width:1.4;fill:none}#dsfig-u2-04 .e.hi{stroke:#2340B8;stroke-width:2.6}#dsfig-u2-04 .n{fill:#FFFFFF;stroke:#16181D;stroke-width:1.4}#dsfig-u2-04 .n.hi{fill:#E3E9FC;stroke:#2340B8;stroke-width:2.2}#dsfig-u2-04 .n.rb-b{fill:#16181D;stroke:#16181D}#dsfig-u2-04 .n.rb-r{fill:#BD3227;stroke:#BD3227}#dsfig-u2-04 text{font-family:"JetBrains Mono",ui-monospace,Menlo,Consolas,monospace;font-size:13px}#dsfig-u2-04 .t{fill:#16181D;font-weight:500}#dsfig-u2-04 .t.inv{fill:#FFFFFF;font-weight:700}#dsfig-u2-04 .kd{stroke:#16181D;stroke-width:1.2}#dsfig-u2-04 .dot{fill:#16181D}#dsfig-u2-04 .ann{fill:#2340B8;font-size:11px;font-weight:700}#dsfig-u2-04 .lbl{fill:#6F7787;font-family:system-ui,-apple-system,sans-serif;font-size:12px;font-weight:700}#dsfig-u2-04 .ptr{fill:#2340B8;font-size:12px;font-weight:700}#dsfig-u2-04 .ah{fill:#454C5A}#dsfig-u2-04 .ah.hi{fill:#2340B8}#dsfig-u2-04 .wl rect{fill:#FFFFFF;stroke:#DCE0E7}#dsfig-u2-04 .wl .t{font-size:12px;font-weight:700}#dsfig-u2-04 .wl.hi rect{fill:#2340B8;stroke:#2340B8}#dsfig-u2-04 .wl.hi .t{fill:#FFFFFF}html.dark #dsfig-u2-04 .e{stroke:#B1B7C3}html.dark #dsfig-u2-04 .e.hi{stroke:#8FA3FF}html.dark #dsfig-u2-04 .n{fill:#161920;stroke:#E6E8ED}html.dark #dsfig-u2-04 .n.hi{fill:#1E2748;stroke:#8FA3FF}html.dark #dsfig-u2-04 .n.rb-b{fill:#E6E8ED;stroke:#E6E8ED}html.dark #dsfig-u2-04 .n.rb-r{fill:#FF7E71;stroke:#FF7E71}html.dark #dsfig-u2-04 .t{fill:#E6E8ED}html.dark #dsfig-u2-04 .t.inv{fill:#0F1115}html.dark #dsfig-u2-04 .kd{stroke:#E6E8ED}html.dark #dsfig-u2-04 .dot{fill:#E6E8ED}html.dark #dsfig-u2-04 .ann{fill:#8FA3FF}html.dark #dsfig-u2-04 .lbl{fill:#858D9C}html.dark #dsfig-u2-04 .ptr{fill:#8FA3FF}html.dark #dsfig-u2-04 .ah{fill:#B1B7C3}html.dark #dsfig-u2-04 .ah.hi{fill:#8FA3FF}html.dark #dsfig-u2-04 .wl rect{fill:#161920;stroke:#2A2E37}html.dark #dsfig-u2-04 .wl.hi rect{fill:#8FA3FF;stroke:#8FA3FF}html.dark #dsfig-u2-04 .wl.hi .t{fill:#0F1115}</style><defs><marker id="ah10" viewBox="0 0 10 10" refX="9" refY="5" markerWidth="7" markerHeight="7" orient="auto-start-reverse"><path class="ah" d="M0,1 L9,5 L0,9 z"/></marker><marker id="ahh10" viewBox="0 0 10 10" refX="9" refY="5" markerWidth="7" markerHeight="7" orient="auto-start-reverse"><path class="ah hi" d="M0,1 L9,5 L0,9 z"/></marker></defs><path class="e" d="M59,126 L148,126" marker-end="url(#ah10)"/><path class="e" d="M186,117.5 L322.2,49.4" marker-end="url(#ah10)"/><path class="e" d="M187.8,123.2 L320.2,103.3" marker-end="url(#ah10)"/><path class="e" d="M187.6,129.7 L320.4,156.3" marker-end="url(#ah10)"/><path class="e" d="M185.6,135.2 L322.6,210.5" marker-end="url(#ah10)"/><circle class="n" cx="40" cy="126" r="18"/><text class="t" x="40" y="126" dy=".35em" text-anchor="middle">Dir</text><circle class="n" cx="169" cy="126" r="18"/><text class="t" x="169" y="126" dy=".35em" text-anchor="middle">Idx</text><circle class="n" cx="341" cy="40" r="18"/><text class="t" x="341" y="40" dy=".35em" text-anchor="middle">B9</text><circle class="n" cx="341" cy="100.2" r="18"/><text class="t" x="341" y="100.2" dy=".35em" text-anchor="middle">B16</text><circle class="n" cx="341" cy="160.4" r="18"/><text class="t" x="341" y="160.4" dy=".35em" text-anchor="middle">B1</text><circle class="n" cx="341" cy="220.6" r="18"/><text class="t" x="341" y="220.6" dy=".35em" text-anchor="middle">B25</text></svg><figcaption style="font-size:.82em;opacity:.72;margin-top:.45rem">Indexed allocation. The index block lists the file's blocks in order.</figcaption></figure>

Key points.

  1. Contiguous allocation stores a file in consecutive blocks, and the directory holds only the start block and length.
  2. Contiguous merits: sequential and direct access are both fast, and seek time is small.
  3. Contiguous demerits: external fragmentation, difficulty in finding a hole, and a file cannot easily grow since its size must be known in advance.
  4. Placement uses first fit (first hole big enough, fast) or best fit (smallest hole big enough, slower, leaves tiny holes); extents let a full file take another contiguous chunk, so it can grow.
  5. Linked allocation stores each block with a pointer to the next block, and the directory holds the first block.
  6. Linked merits: no external fragmentation, and the file can grow freely.
  7. Linked demerits: direct access is slow because the chain must be traversed, pointers take space, and one lost pointer breaks the file.
  8. FAT moves all pointers to a table at the start of the disk, so direct access is faster; the directory holds start block 9 and the chain is read from the table. Its drawbacks are that the table must be cached in memory to be fast, and without the cache each access moves the head to the table and back to the data.

<figure class="ds-fig" style="margin:1.4rem 0;overflow-x:auto"><svg xmlns="http://www.w3.org/2000/svg" id="dsfig-u2-05" viewBox="0 0 596 80" width="596" height="80" role="img" aria-label="FAT chain 9, 16, 1, 25, end of file."><style>#dsfig-u2-05 .e{stroke:#454C5A;stroke-width:1.4;fill:none}#dsfig-u2-05 .e.hi{stroke:#2340B8;stroke-width:2.6}#dsfig-u2-05 .n{fill:#FFFFFF;stroke:#16181D;stroke-width:1.4}#dsfig-u2-05 .n.hi{fill:#E3E9FC;stroke:#2340B8;stroke-width:2.2}#dsfig-u2-05 .n.rb-b{fill:#16181D;stroke:#16181D}#dsfig-u2-05 .n.rb-r{fill:#BD3227;stroke:#BD3227}#dsfig-u2-05 text{font-family:"JetBrains Mono",ui-monospace,Menlo,Consolas,monospace;font-size:13px}#dsfig-u2-05 .t{fill:#16181D;font-weight:500}#dsfig-u2-05 .t.inv{fill:#FFFFFF;font-weight:700}#dsfig-u2-05 .kd{stroke:#16181D;stroke-width:1.2}#dsfig-u2-05 .dot{fill:#16181D}#dsfig-u2-05 .ann{fill:#2340B8;font-size:11px;font-weight:700}#dsfig-u2-05 .lbl{fill:#6F7787;font-family:system-ui,-apple-system,sans-serif;font-size:12px;font-weight:700}#dsfig-u2-05 .ptr{fill:#2340B8;font-size:12px;font-weight:700}#dsfig-u2-05 .ah{fill:#454C5A}#dsfig-u2-05 .ah.hi{fill:#2340B8}#dsfig-u2-05 .wl rect{fill:#FFFFFF;stroke:#DCE0E7}#dsfig-u2-05 .wl .t{font-size:12px;font-weight:700}#dsfig-u2-05 .wl.hi rect{fill:#2340B8;stroke:#2340B8}#dsfig-u2-05 .wl.hi .t{fill:#FFFFFF}html.dark #dsfig-u2-05 .e{stroke:#B1B7C3}html.dark #dsfig-u2-05 .e.hi{stroke:#8FA3FF}html.dark #dsfig-u2-05 .n{fill:#161920;stroke:#E6E8ED}html.dark #dsfig-u2-05 .n.hi{fill:#1E2748;stroke:#8FA3FF}html.dark #dsfig-u2-05 .n.rb-b{fill:#E6E8ED;stroke:#E6E8ED}html.dark #dsfig-u2-05 .n.rb-r{fill:#FF7E71;stroke:#FF7E71}html.dark #dsfig-u2-05 .t{fill:#E6E8ED}html.dark #dsfig-u2-05 .t.inv{fill:#0F1115}html.dark #dsfig-u2-05 .kd{stroke:#E6E8ED}html.dark #dsfig-u2-05 .dot{fill:#E6E8ED}html.dark #dsfig-u2-05 .ann{fill:#8FA3FF}html.dark #dsfig-u2-05 .lbl{fill:#858D9C}html.dark #dsfig-u2-05 .ptr{fill:#8FA3FF}html.dark #dsfig-u2-05 .ah{fill:#B1B7C3}html.dark #dsfig-u2-05 .ah.hi{fill:#8FA3FF}html.dark #dsfig-u2-05 .wl rect{fill:#161920;stroke:#2A2E37}html.dark #dsfig-u2-05 .wl.hi rect{fill:#8FA3FF;stroke:#8FA3FF}html.dark #dsfig-u2-05 .wl.hi .t{fill:#0F1115}</style><defs><marker id="ah11" viewBox="0 0 10 10" refX="9" refY="5" markerWidth="7" markerHeight="7" orient="auto-start-reverse"><path class="ah" d="M0,1 L9,5 L0,9 z"/></marker><marker id="ahh11" viewBox="0 0 10 10" refX="9" refY="5" markerWidth="7" markerHeight="7" orient="auto-start-reverse"><path class="ah hi" d="M0,1 L9,5 L0,9 z"/></marker></defs><path class="e" d="M59,40 L148,40" marker-end="url(#ah11)"/><path class="e" d="M188,40 L277,40" marker-end="url(#ah11)"/><path class="e" d="M317,40 L406,40" marker-end="url(#ah11)"/><path class="e" d="M446,40 L535,40" marker-end="url(#ah11)"/><circle class="n" cx="40" cy="40" r="18"/><text class="t" x="40" y="40" dy=".35em" text-anchor="middle">F9</text><circle class="n" cx="169" cy="40" r="18"/><text class="t" x="169" y="40" dy=".35em" text-anchor="middle">F16</text><circle class="n" cx="298" cy="40" r="18"/><text class="t" x="298" y="40" dy=".35em" text-anchor="middle">F1</text><circle class="n" cx="427" cy="40" r="18"/><text class="t" x="427" y="40" dy=".35em" text-anchor="middle">F25</text><circle class="n" cx="556" cy="40" r="18"/><text class="t" x="556" y="40" dy=".35em" text-anchor="middle">EOF</text></svg><figcaption style="font-size:.82em;opacity:.72;margin-top:.45rem">FAT chain 9, 16, 1, 25, end of file.</figcaption></figure>

FAT entry 9 16 1 25
Value 16 1 25 EOF
  1. Indexed allocation gathers all block pointers of a file into one index block, and the directory points to it; it supports direct access without external fragmentation.
  2. Indexed demerits: the index block is overhead, since even a one-block file needs a whole index block.
  3. Large files (4 KB blocks, 1024 pointers per block) use linked index blocks (1023 pointers plus a next pointer), two-level index (1M blocks = 4 GB) or the UNIX inode (12 direct = 48 KB, then single, double and triple indirect blocks).
  4. The five file-system design points are: file management, which fixes the attributes, operations and access methods offered; directory structure, which decides how names map to files; allocation, which decides which blocks hold a file and how free space is tracked; reliability, so data survives crashes through backups and consistent updates; and performance, through caches, buffering and fewer seeks.

Address mapping (block 512 bytes, byte address $A$). $L = A \div 512$, $O = A \bmod 512$.

Method Physical block Reads
Contiguous $start + L$ 1
Linked follow $L$ pointers; data per block is $512-p$, so $L = A \div (512-p)$, $O = A \bmod (512-p)$ $L+1$
Indexed $index[L]$ (file under 512 blocks, one index block) 2, or 1 if cached

File information is already in memory, so the first or index block address needs no disk access. Example. $A = 1000$, $p = 4$, start 50: contiguous block 51, $O=488$; linked $L = 1$, $O = 492$, 2 reads; indexed block $index[1]$.

Comparison: contiguous and indexed.

Point Contiguous Indexed
Directory holds Start and length Index block address
Fragmentation External None external
Access speed Fastest Fast, one extra read
Growth Hard Easy
Reliability Good Index block loss is fatal
Overhead None Index block per file

Answer frame. Define allocation; develop each method as concept, merits, demerits with its diagram; for comparison use the table. For mapping, state assumptions, then formulas and example.

Asked: [7 marks] (Jun 2020, Jun 2026) Describe various space allocation strategies with their merits/demerits. Asked: [7 marks] (Nov 2019) What are points to be considered in file system design? Explain linked list allocation in detail. Asked: [7 marks] (May 2019) Explain in brief: (i) contiguous and linked list allocation; (ii) file attributes and file operations. Asked: [7 marks] (Jun 2024) With 512-byte logical and physical blocks and file information in memory, how is logical to physical address mapping done for contiguous, linked and indexed allocation (file under 512 blocks)? Asked: [7 marks] (Jun 2026) Compare contiguous and indexed file allocation methods. Pitfall: For linked allocation, state that direct access is slow; forgetting it is a common lost mark.

Free space management. Free space management keeps track of unused blocks so the file system can allocate them to new files.

Key points.

  1. Bit vector (bitmap) uses one bit per block, 1 for free and 0 for allocated; it is simple and finds runs quickly but needs memory.
  2. Linked list links all free blocks together with the head pointer in memory; it wastes no space but traversal is slow.
  3. Grouping stores addresses of n free blocks in the first free block, the last pointing to the next such block, so many are found at once.
  4. Counting stores the first free block address and the count of contiguous free blocks after it, which is short when free space is in runs.
  5. Bitmap size = disk size / block size bits: a 1 GB disk with 4 KB blocks has $2^{30}/2^{12} = 262144$ blocks, so 262144 bits = 32 KB.
  6. Example: free blocks 2, 3, 5, 8, 9, 10, 11 of blocks 0-11 give bitmap 001101001111 (1 = free, 0 = allocated).
block  0 1 2 3 4 5 6 7 8 9 10 11
bit    0 0 1 1 0 1 0 0 1 1 1  1     bitmap (1 = free)
grouping: block 2 [3,5,8] -> block 8 [9,10,11]
counting: (2,2) (5,1) (8,4)

<figure class="ds-fig" style="margin:1.4rem 0;overflow-x:auto"><svg xmlns="http://www.w3.org/2000/svg" id="dsfig-u2-06" viewBox="0 0 616 58" width="616" height="58" role="img" aria-label="Linked free list of the example."><style>#dsfig-u2-06 .e{stroke:#454C5A;stroke-width:1.4;fill:none}#dsfig-u2-06 .e.hi{stroke:#2340B8;stroke-width:2.6}#dsfig-u2-06 .n{fill:#FFFFFF;stroke:#16181D;stroke-width:1.4}#dsfig-u2-06 .n.hi{fill:#E3E9FC;stroke:#2340B8;stroke-width:2.2}#dsfig-u2-06 .n.rb-b{fill:#16181D;stroke:#16181D}#dsfig-u2-06 .n.rb-r{fill:#BD3227;stroke:#BD3227}#dsfig-u2-06 text{font-family:"JetBrains Mono",ui-monospace,Menlo,Consolas,monospace;font-size:13px}#dsfig-u2-06 .t{fill:#16181D;font-weight:500}#dsfig-u2-06 .t.inv{fill:#FFFFFF;font-weight:700}#dsfig-u2-06 .kd{stroke:#16181D;stroke-width:1.2}#dsfig-u2-06 .dot{fill:#16181D}#dsfig-u2-06 .ann{fill:#2340B8;font-size:11px;font-weight:700}#dsfig-u2-06 .lbl{fill:#6F7787;font-family:system-ui,-apple-system,sans-serif;font-size:12px;font-weight:700}#dsfig-u2-06 .ptr{fill:#2340B8;font-size:12px;font-weight:700}#dsfig-u2-06 .ah{fill:#454C5A}#dsfig-u2-06 .ah.hi{fill:#2340B8}#dsfig-u2-06 .wl rect{fill:#FFFFFF;stroke:#DCE0E7}#dsfig-u2-06 .wl .t{font-size:12px;font-weight:700}#dsfig-u2-06 .wl.hi rect{fill:#2340B8;stroke:#2340B8}#dsfig-u2-06 .wl.hi .t{fill:#FFFFFF}html.dark #dsfig-u2-06 .e{stroke:#B1B7C3}html.dark #dsfig-u2-06 .e.hi{stroke:#8FA3FF}html.dark #dsfig-u2-06 .n{fill:#161920;stroke:#E6E8ED}html.dark #dsfig-u2-06 .n.hi{fill:#1E2748;stroke:#8FA3FF}html.dark #dsfig-u2-06 .n.rb-b{fill:#E6E8ED;stroke:#E6E8ED}html.dark #dsfig-u2-06 .n.rb-r{fill:#FF7E71;stroke:#FF7E71}html.dark #dsfig-u2-06 .t{fill:#E6E8ED}html.dark #dsfig-u2-06 .t.inv{fill:#0F1115}html.dark #dsfig-u2-06 .kd{stroke:#E6E8ED}html.dark #dsfig-u2-06 .dot{fill:#E6E8ED}html.dark #dsfig-u2-06 .ann{fill:#8FA3FF}html.dark #dsfig-u2-06 .lbl{fill:#858D9C}html.dark #dsfig-u2-06 .ptr{fill:#8FA3FF}html.dark #dsfig-u2-06 .ah{fill:#B1B7C3}html.dark #dsfig-u2-06 .ah.hi{fill:#8FA3FF}html.dark #dsfig-u2-06 .wl rect{fill:#161920;stroke:#2A2E37}html.dark #dsfig-u2-06 .wl.hi rect{fill:#8FA3FF;stroke:#8FA3FF}html.dark #dsfig-u2-06 .wl.hi .t{fill:#0F1115}</style><defs><marker id="ah12" viewBox="0 0 10 10" refX="9" refY="5" markerWidth="7" markerHeight="7" orient="auto-start-reverse"><path class="ah" d="M0,1 L9,5 L0,9 z"/></marker><marker id="ahh12" viewBox="0 0 10 10" refX="9" refY="5" markerWidth="7" markerHeight="7" orient="auto-start-reverse"><path class="ah hi" d="M0,1 L9,5 L0,9 z"/></marker></defs><text class="ptr" x="14" y="29" dy=".35em" text-anchor="start">head</text><line class="e" x1="52" y1="29" x2="75" y2="29" marker-end="url(#ah12)"/><rect class="n" x="76" y="14" width="46" height="30" rx="3"/><text class="t" x="91" y="29" dy=".35em" text-anchor="middle">2</text><line class="kd" x1="106" y1="14" x2="106" y2="44"/><circle class="dot" cx="114" cy="29" r="2.6"/><line class="e" x1="114" y1="29" x2="155" y2="29" marker-end="url(#ah12)"/><rect class="n" x="156" y="14" width="46" height="30" rx="3"/><text class="t" x="171" y="29" dy=".35em" text-anchor="middle">3</text><line class="kd" x1="186" y1="14" x2="186" y2="44"/><circle class="dot" cx="194" cy="29" r="2.6"/><line class="e" x1="194" y1="29" x2="235" y2="29" marker-end="url(#ah12)"/><rect class="n" x="236" y="14" width="46" height="30" rx="3"/><text class="t" x="251" y="29" dy=".35em" text-anchor="middle">5</text><line class="kd" x1="266" y1="14" x2="266" y2="44"/><circle class="dot" cx="274" cy="29" r="2.6"/><line class="e" x1="274" y1="29" x2="315" y2="29" marker-end="url(#ah12)"/><rect class="n" x="316" y="14" width="46" height="30" rx="3"/><text class="t" x="331" y="29" dy=".35em" text-anchor="middle">8</text><line class="kd" x1="346" y1="14" x2="346" y2="44"/><circle class="dot" cx="354" cy="29" r="2.6"/><line class="e" x1="354" y1="29" x2="395" y2="29" marker-end="url(#ah12)"/><rect class="n" x="396" y="14" width="46" height="30" rx="3"/><text class="t" x="411" y="29" dy=".35em" text-anchor="middle">9</text><line class="kd" x1="426" y1="14" x2="426" y2="44"/><circle class="dot" cx="434" cy="29" r="2.6"/><line class="e" x1="434" y1="29" x2="475" y2="29" marker-end="url(#ah12)"/><rect class="n" x="476" y="14" width="46" height="30" rx="3"/><text class="t" x="491" y="29" dy=".35em" text-anchor="middle">10</text><line class="kd" x1="506" y1="14" x2="506" y2="44"/><circle class="dot" cx="514" cy="29" r="2.6"/><line class="e" x1="514" y1="29" x2="555" y2="29" marker-end="url(#ah12)"/><rect class="n" x="556" y="14" width="46" height="30" rx="3"/><text class="t" x="571" y="29" dy=".35em" text-anchor="middle">11</text><line class="kd" x1="586" y1="14" x2="586" y2="44"/><line class="kd" x1="589" y1="41" x2="599" y2="17"/></svg><figcaption style="font-size:.82em;opacity:.72;margin-top:.45rem">Linked free list of the example.</figcaption></figure>

Method Memory cost Speed Finds contiguous run
Bit vector 1 bit per block, whole map in memory Fast, scan for a 1 Easiest, look for consecutive 1s
Linked list No extra space, head only Slow, one block read per free block Poor, must walk the chain
Grouping n addresses per free block Many blocks found per read Poor
Counting One (address, count) pair per run Fast when free space is in runs Good, the count gives run length

Free-space frame. Open with why free blocks are tracked; develop the four methods with the example; close with the table.

Asked: [7 marks] (Jun 2023) Explain in detail about various ways of free space management.

Directory Structures

<span style="display:inline-block;padding:.16em .6em;border:1.5px solid currentColor;border-radius:999px;font-size:.68em;font-weight:700;letter-spacing:.06em;text-transform:uppercase;opacity:.75">Low weight</span>

Definition. A directory is a file that holds the names and attributes of files, and the structure decides how they are organised.

Diagram.

<figure class="ds-fig" style="margin:1.4rem 0;overflow-x:auto"><svg xmlns="http://www.w3.org/2000/svg" id="dsfig-u2-07" viewBox="0 0 329 198" width="329" height="198" role="img" aria-label="UNIX tree-structured directory rooted at /"><style>#dsfig-u2-07 .e{stroke:#454C5A;stroke-width:1.4;fill:none}#dsfig-u2-07 .e.hi{stroke:#2340B8;stroke-width:2.6}#dsfig-u2-07 .n{fill:#FFFFFF;stroke:#16181D;stroke-width:1.4}#dsfig-u2-07 .n.hi{fill:#E3E9FC;stroke:#2340B8;stroke-width:2.2}#dsfig-u2-07 .n.rb-b{fill:#16181D;stroke:#16181D}#dsfig-u2-07 .n.rb-r{fill:#BD3227;stroke:#BD3227}#dsfig-u2-07 text{font-family:"JetBrains Mono",ui-monospace,Menlo,Consolas,monospace;font-size:13px}#dsfig-u2-07 .t{fill:#16181D;font-weight:500}#dsfig-u2-07 .t.inv{fill:#FFFFFF;font-weight:700}#dsfig-u2-07 .kd{stroke:#16181D;stroke-width:1.2}#dsfig-u2-07 .dot{fill:#16181D}#dsfig-u2-07 .ann{fill:#2340B8;font-size:11px;font-weight:700}#dsfig-u2-07 .lbl{fill:#6F7787;font-family:system-ui,-apple-system,sans-serif;font-size:12px;font-weight:700}#dsfig-u2-07 .ptr{fill:#2340B8;font-size:12px;font-weight:700}#dsfig-u2-07 .ah{fill:#454C5A}#dsfig-u2-07 .ah.hi{fill:#2340B8}#dsfig-u2-07 .wl rect{fill:#FFFFFF;stroke:#DCE0E7}#dsfig-u2-07 .wl .t{font-size:12px;font-weight:700}#dsfig-u2-07 .wl.hi rect{fill:#2340B8;stroke:#2340B8}#dsfig-u2-07 .wl.hi .t{fill:#FFFFFF}html.dark #dsfig-u2-07 .e{stroke:#B1B7C3}html.dark #dsfig-u2-07 .e.hi{stroke:#8FA3FF}html.dark #dsfig-u2-07 .n{fill:#161920;stroke:#E6E8ED}html.dark #dsfig-u2-07 .n.hi{fill:#1E2748;stroke:#8FA3FF}html.dark #dsfig-u2-07 .n.rb-b{fill:#E6E8ED;stroke:#E6E8ED}html.dark #dsfig-u2-07 .n.rb-r{fill:#FF7E71;stroke:#FF7E71}html.dark #dsfig-u2-07 .t{fill:#E6E8ED}html.dark #dsfig-u2-07 .t.inv{fill:#0F1115}html.dark #dsfig-u2-07 .kd{stroke:#E6E8ED}html.dark #dsfig-u2-07 .dot{fill:#E6E8ED}html.dark #dsfig-u2-07 .ann{fill:#8FA3FF}html.dark #dsfig-u2-07 .lbl{fill:#858D9C}html.dark #dsfig-u2-07 .ptr{fill:#8FA3FF}html.dark #dsfig-u2-07 .ah{fill:#B1B7C3}html.dark #dsfig-u2-07 .ah.hi{fill:#8FA3FF}html.dark #dsfig-u2-07 .wl rect{fill:#161920;stroke:#2A2E37}html.dark #dsfig-u2-07 .wl.hi rect{fill:#8FA3FF;stroke:#8FA3FF}html.dark #dsfig-u2-07 .wl.hi .t{fill:#0F1115}</style><defs><marker id="ah13" viewBox="0 0 10 10" refX="9" refY="5" markerWidth="7" markerHeight="7" orient="auto-start-reverse"><path class="ah" d="M0,1 L9,5 L0,9 z"/></marker><marker id="ahh13" viewBox="0 0 10 10" refX="9" refY="5" markerWidth="7" markerHeight="7" orient="auto-start-reverse"><path class="ah hi" d="M0,1 L9,5 L0,9 z"/></marker></defs><line class="e" x1="133.3" y1="39" x2="31" y2="103"/><line class="e" x1="133.3" y1="39" x2="124.8" y2="103"/><line class="e" x1="133.3" y1="39" x2="235.5" y2="103"/><line class="e" x1="124.8" y1="103" x2="93.5" y2="167"/><line class="e" x1="124.8" y1="103" x2="156" y2="167"/><line class="e" x1="235.5" y1="103" x2="206" y2="167"/><line class="e" x1="235.5" y1="103" x2="265" y2="167"/><circle class="n" cx="133.3" cy="39" r="17"/><text class="t" x="133.3" y="39" dy=".35em" text-anchor="middle">/</text><circle class="n" cx="31" cy="103" r="17"/><text class="t" x="31" y="103" dy=".35em" text-anchor="middle">bin</text><circle class="n" cx="124.8" cy="103" r="17"/><text class="t" x="124.8" y="103" dy=".35em" text-anchor="middle">usr</text><rect class="n" x="64" y="152" width="59" height="30" rx="8"/><text class="t" x="93.5" y="167" dy=".35em" text-anchor="middle">local</text><circle class="n" cx="156" cy="167" r="17"/><text class="t" x="156" y="167" dy=".35em" text-anchor="middle">lib</text><rect class="n" x="209.5" y="88" width="52" height="30" rx="8"/><text class="t" x="235.5" y="103" dy=".35em" text-anchor="middle">home</text><circle class="n" cx="206" cy="167" r="17"/><text class="t" x="206" y="167" dy=".35em" text-anchor="middle">ram</text><rect class="n" x="239" y="152" width="52" height="30" rx="8"/><text class="t" x="265" y="167" dy=".35em" text-anchor="middle">sita</text></svg><figcaption style="font-size:.82em;opacity:.72;margin-top:.45rem">UNIX tree-structured directory rooted at /</figcaption></figure>

Key points.

  1. Single-level has one directory for all users, so names clash and grouping is impossible.
  2. Two-level gives each user a private directory, removing name clashes but not allowing sharing.
  3. Tree structure lets directories hold subdirectories, and files are reached by absolute path (from the root, /home/ram/a.txt) or relative path (from the current directory /home, ram/a.txt).
  4. Acyclic graph allows shared files and directories through links; on deletion a reference count is kept and the file is freed only at count 0, otherwise the remaining links dangle.
  5. General graph allows cycles, which needs garbage collection to avoid loops.
  6. UNIX uses a tree structure, plus links that make it acyclic in effect.
  7. In two-level, the master file directory (MFD) lists one user file directory (UFD) per user, and a path is user plus file name.
  8. A UNIX hard link is another entry for the same inode and raises its link count; blocks are freed only at count 0. A symbolic link holds a path, so deleting its target leaves it dangling.

<figure class="ds-fig" style="margin:1.4rem 0;overflow-x:auto"><svg xmlns="http://www.w3.org/2000/svg" id="dsfig-u2-08" viewBox="0 0 186 134" width="186" height="134" role="img" aria-label="Single-level"><style>#dsfig-u2-08 .e{stroke:#454C5A;stroke-width:1.4;fill:none}#dsfig-u2-08 .e.hi{stroke:#2340B8;stroke-width:2.6}#dsfig-u2-08 .n{fill:#FFFFFF;stroke:#16181D;stroke-width:1.4}#dsfig-u2-08 .n.hi{fill:#E3E9FC;stroke:#2340B8;stroke-width:2.2}#dsfig-u2-08 .n.rb-b{fill:#16181D;stroke:#16181D}#dsfig-u2-08 .n.rb-r{fill:#BD3227;stroke:#BD3227}#dsfig-u2-08 text{font-family:"JetBrains Mono",ui-monospace,Menlo,Consolas,monospace;font-size:13px}#dsfig-u2-08 .t{fill:#16181D;font-weight:500}#dsfig-u2-08 .t.inv{fill:#FFFFFF;font-weight:700}#dsfig-u2-08 .kd{stroke:#16181D;stroke-width:1.2}#dsfig-u2-08 .dot{fill:#16181D}#dsfig-u2-08 .ann{fill:#2340B8;font-size:11px;font-weight:700}#dsfig-u2-08 .lbl{fill:#6F7787;font-family:system-ui,-apple-system,sans-serif;font-size:12px;font-weight:700}#dsfig-u2-08 .ptr{fill:#2340B8;font-size:12px;font-weight:700}#dsfig-u2-08 .ah{fill:#454C5A}#dsfig-u2-08 .ah.hi{fill:#2340B8}#dsfig-u2-08 .wl rect{fill:#FFFFFF;stroke:#DCE0E7}#dsfig-u2-08 .wl .t{font-size:12px;font-weight:700}#dsfig-u2-08 .wl.hi rect{fill:#2340B8;stroke:#2340B8}#dsfig-u2-08 .wl.hi .t{fill:#FFFFFF}html.dark #dsfig-u2-08 .e{stroke:#B1B7C3}html.dark #dsfig-u2-08 .e.hi{stroke:#8FA3FF}html.dark #dsfig-u2-08 .n{fill:#161920;stroke:#E6E8ED}html.dark #dsfig-u2-08 .n.hi{fill:#1E2748;stroke:#8FA3FF}html.dark #dsfig-u2-08 .n.rb-b{fill:#E6E8ED;stroke:#E6E8ED}html.dark #dsfig-u2-08 .n.rb-r{fill:#FF7E71;stroke:#FF7E71}html.dark #dsfig-u2-08 .t{fill:#E6E8ED}html.dark #dsfig-u2-08 .t.inv{fill:#0F1115}html.dark #dsfig-u2-08 .kd{stroke:#E6E8ED}html.dark #dsfig-u2-08 .dot{fill:#E6E8ED}html.dark #dsfig-u2-08 .ann{fill:#8FA3FF}html.dark #dsfig-u2-08 .lbl{fill:#858D9C}html.dark #dsfig-u2-08 .ptr{fill:#8FA3FF}html.dark #dsfig-u2-08 .ah{fill:#B1B7C3}html.dark #dsfig-u2-08 .ah.hi{fill:#8FA3FF}html.dark #dsfig-u2-08 .wl rect{fill:#161920;stroke:#2A2E37}html.dark #dsfig-u2-08 .wl.hi rect{fill:#8FA3FF;stroke:#8FA3FF}html.dark #dsfig-u2-08 .wl.hi .t{fill:#0F1115}</style><defs><marker id="ah14" viewBox="0 0 10 10" refX="9" refY="5" markerWidth="7" markerHeight="7" orient="auto-start-reverse"><path class="ah" d="M0,1 L9,5 L0,9 z"/></marker><marker id="ahh14" viewBox="0 0 10 10" refX="9" refY="5" markerWidth="7" markerHeight="7" orient="auto-start-reverse"><path class="ah hi" d="M0,1 L9,5 L0,9 z"/></marker></defs><line class="e" x1="81" y1="39" x2="31" y2="103"/><line class="e" x1="81" y1="39" x2="81" y2="103"/><line class="e" x1="81" y1="39" x2="131" y2="103"/><circle class="n" cx="81" cy="39" r="17"/><text class="t" x="81" y="39" dy=".35em" text-anchor="middle">D</text><circle class="n" cx="31" cy="103" r="17"/><text class="t" x="31" y="103" dy=".35em" text-anchor="middle">a</text><circle class="n" cx="81" cy="103" r="17"/><text class="t" x="81" y="103" dy=".35em" text-anchor="middle">b</text><circle class="n" cx="131" cy="103" r="17"/><text class="t" x="131" y="103" dy=".35em" text-anchor="middle">c</text></svg><figcaption style="font-size:.82em;opacity:.72;margin-top:.45rem">Single-level</figcaption></figure>

<figure class="ds-fig" style="margin:1.4rem 0;overflow-x:auto"><svg xmlns="http://www.w3.org/2000/svg" id="dsfig-u2-09" viewBox="0 0 360 198" width="360" height="198" role="img" aria-label="Two-level, MFD and UFDs"><style>#dsfig-u2-09 .e{stroke:#454C5A;stroke-width:1.4;fill:none}#dsfig-u2-09 .e.hi{stroke:#2340B8;stroke-width:2.6}#dsfig-u2-09 .n{fill:#FFFFFF;stroke:#16181D;stroke-width:1.4}#dsfig-u2-09 .n.hi{fill:#E3E9FC;stroke:#2340B8;stroke-width:2.2}#dsfig-u2-09 .n.rb-b{fill:#16181D;stroke:#16181D}#dsfig-u2-09 .n.rb-r{fill:#BD3227;stroke:#BD3227}#dsfig-u2-09 text{font-family:"JetBrains Mono",ui-monospace,Menlo,Consolas,monospace;font-size:13px}#dsfig-u2-09 .t{fill:#16181D;font-weight:500}#dsfig-u2-09 .t.inv{fill:#FFFFFF;font-weight:700}#dsfig-u2-09 .kd{stroke:#16181D;stroke-width:1.2}#dsfig-u2-09 .dot{fill:#16181D}#dsfig-u2-09 .ann{fill:#2340B8;font-size:11px;font-weight:700}#dsfig-u2-09 .lbl{fill:#6F7787;font-family:system-ui,-apple-system,sans-serif;font-size:12px;font-weight:700}#dsfig-u2-09 .ptr{fill:#2340B8;font-size:12px;font-weight:700}#dsfig-u2-09 .ah{fill:#454C5A}#dsfig-u2-09 .ah.hi{fill:#2340B8}#dsfig-u2-09 .wl rect{fill:#FFFFFF;stroke:#DCE0E7}#dsfig-u2-09 .wl .t{font-size:12px;font-weight:700}#dsfig-u2-09 .wl.hi rect{fill:#2340B8;stroke:#2340B8}#dsfig-u2-09 .wl.hi .t{fill:#FFFFFF}html.dark #dsfig-u2-09 .e{stroke:#B1B7C3}html.dark #dsfig-u2-09 .e.hi{stroke:#8FA3FF}html.dark #dsfig-u2-09 .n{fill:#161920;stroke:#E6E8ED}html.dark #dsfig-u2-09 .n.hi{fill:#1E2748;stroke:#8FA3FF}html.dark #dsfig-u2-09 .n.rb-b{fill:#E6E8ED;stroke:#E6E8ED}html.dark #dsfig-u2-09 .n.rb-r{fill:#FF7E71;stroke:#FF7E71}html.dark #dsfig-u2-09 .t{fill:#E6E8ED}html.dark #dsfig-u2-09 .t.inv{fill:#0F1115}html.dark #dsfig-u2-09 .kd{stroke:#E6E8ED}html.dark #dsfig-u2-09 .dot{fill:#E6E8ED}html.dark #dsfig-u2-09 .ann{fill:#8FA3FF}html.dark #dsfig-u2-09 .lbl{fill:#858D9C}html.dark #dsfig-u2-09 .ptr{fill:#8FA3FF}html.dark #dsfig-u2-09 .ah{fill:#B1B7C3}html.dark #dsfig-u2-09 .ah.hi{fill:#8FA3FF}html.dark #dsfig-u2-09 .wl rect{fill:#161920;stroke:#2A2E37}html.dark #dsfig-u2-09 .wl.hi rect{fill:#8FA3FF;stroke:#8FA3FF}html.dark #dsfig-u2-09 .wl.hi .t{fill:#0F1115}</style><defs><marker id="ah15" viewBox="0 0 10 10" refX="9" refY="5" markerWidth="7" markerHeight="7" orient="auto-start-reverse"><path class="ah" d="M0,1 L9,5 L0,9 z"/></marker><marker id="ahh15" viewBox="0 0 10 10" refX="9" refY="5" markerWidth="7" markerHeight="7" orient="auto-start-reverse"><path class="ah hi" d="M0,1 L9,5 L0,9 z"/></marker></defs><line class="e" x1="168" y1="39" x2="80" y2="103"/><line class="e" x1="168" y1="39" x2="256" y2="103"/><line class="e" x1="80" y1="103" x2="36" y2="167"/><line class="e" x1="80" y1="103" x2="124" y2="167"/><line class="e" x1="256" y1="103" x2="212" y2="167"/><line class="e" x1="256" y1="103" x2="300" y2="167"/><circle class="n" cx="168" cy="39" r="17"/><text class="t" x="168" y="39" dy=".35em" text-anchor="middle">MFD</text><circle class="n" cx="80" cy="103" r="17"/><text class="t" x="80" y="103" dy=".35em" text-anchor="middle">U1</text><circle class="n" cx="36" cy="167" r="17"/><text class="t" x="36" y="167" dy=".35em" text-anchor="middle">a</text><circle class="n" cx="124" cy="167" r="17"/><text class="t" x="124" y="167" dy=".35em" text-anchor="middle">b</text><circle class="n" cx="256" cy="103" r="17"/><text class="t" x="256" y="103" dy=".35em" text-anchor="middle">U2</text><circle class="n" cx="212" cy="167" r="17"/><text class="t" x="212" y="167" dy=".35em" text-anchor="middle">a</text><circle class="n" cx="300" cy="167" r="17"/><text class="t" x="300" y="167" dy=".35em" text-anchor="middle">c</text></svg><figcaption style="font-size:.82em;opacity:.72;margin-top:.45rem">Two-level, MFD and UFDs</figcaption></figure>

<figure class="ds-fig" style="margin:1.4rem 0;overflow-x:auto"><svg xmlns="http://www.w3.org/2000/svg" id="dsfig-u2-10" viewBox="0 0 338 252" width="338" height="252" role="img" aria-label="Acyclic, F shared"><style>#dsfig-u2-10 .e{stroke:#454C5A;stroke-width:1.4;fill:none}#dsfig-u2-10 .e.hi{stroke:#2340B8;stroke-width:2.6}#dsfig-u2-10 .n{fill:#FFFFFF;stroke:#16181D;stroke-width:1.4}#dsfig-u2-10 .n.hi{fill:#E3E9FC;stroke:#2340B8;stroke-width:2.2}#dsfig-u2-10 .n.rb-b{fill:#16181D;stroke:#16181D}#dsfig-u2-10 .n.rb-r{fill:#BD3227;stroke:#BD3227}#dsfig-u2-10 text{font-family:"JetBrains Mono",ui-monospace,Menlo,Consolas,monospace;font-size:13px}#dsfig-u2-10 .t{fill:#16181D;font-weight:500}#dsfig-u2-10 .t.inv{fill:#FFFFFF;font-weight:700}#dsfig-u2-10 .kd{stroke:#16181D;stroke-width:1.2}#dsfig-u2-10 .dot{fill:#16181D}#dsfig-u2-10 .ann{fill:#2340B8;font-size:11px;font-weight:700}#dsfig-u2-10 .lbl{fill:#6F7787;font-family:system-ui,-apple-system,sans-serif;font-size:12px;font-weight:700}#dsfig-u2-10 .ptr{fill:#2340B8;font-size:12px;font-weight:700}#dsfig-u2-10 .ah{fill:#454C5A}#dsfig-u2-10 .ah.hi{fill:#2340B8}#dsfig-u2-10 .wl rect{fill:#FFFFFF;stroke:#DCE0E7}#dsfig-u2-10 .wl .t{font-size:12px;font-weight:700}#dsfig-u2-10 .wl.hi rect{fill:#2340B8;stroke:#2340B8}#dsfig-u2-10 .wl.hi .t{fill:#FFFFFF}html.dark #dsfig-u2-10 .e{stroke:#B1B7C3}html.dark #dsfig-u2-10 .e.hi{stroke:#8FA3FF}html.dark #dsfig-u2-10 .n{fill:#161920;stroke:#E6E8ED}html.dark #dsfig-u2-10 .n.hi{fill:#1E2748;stroke:#8FA3FF}html.dark #dsfig-u2-10 .n.rb-b{fill:#E6E8ED;stroke:#E6E8ED}html.dark #dsfig-u2-10 .n.rb-r{fill:#FF7E71;stroke:#FF7E71}html.dark #dsfig-u2-10 .t{fill:#E6E8ED}html.dark #dsfig-u2-10 .t.inv{fill:#0F1115}html.dark #dsfig-u2-10 .kd{stroke:#E6E8ED}html.dark #dsfig-u2-10 .dot{fill:#E6E8ED}html.dark #dsfig-u2-10 .ann{fill:#8FA3FF}html.dark #dsfig-u2-10 .lbl{fill:#858D9C}html.dark #dsfig-u2-10 .ptr{fill:#8FA3FF}html.dark #dsfig-u2-10 .ah{fill:#B1B7C3}html.dark #dsfig-u2-10 .ah.hi{fill:#8FA3FF}html.dark #dsfig-u2-10 .wl rect{fill:#161920;stroke:#2A2E37}html.dark #dsfig-u2-10 .wl.hi rect{fill:#8FA3FF;stroke:#8FA3FF}html.dark #dsfig-u2-10 .wl.hi .t{fill:#0F1115}</style><defs><marker id="ah16" viewBox="0 0 10 10" refX="9" refY="5" markerWidth="7" markerHeight="7" orient="auto-start-reverse"><path class="ah" d="M0,1 L9,5 L0,9 z"/></marker><marker id="ahh16" viewBox="0 0 10 10" refX="9" refY="5" markerWidth="7" markerHeight="7" orient="auto-start-reverse"><path class="ah hi" d="M0,1 L9,5 L0,9 z"/></marker></defs><path class="e" d="M55.8,115.5 L151.5,51.6" marker-end="url(#ah16)"/><path class="e" d="M55.8,136.5 L151.5,200.4" marker-end="url(#ah16)"/><path class="e" d="M184.8,50.5 L280.5,114.4" marker-end="url(#ah16)"/><path class="e" d="M184.8,201.5 L280.5,137.6" marker-end="url(#ah16)"/><circle class="n" cx="40" cy="126" r="18"/><text class="t" x="40" y="126" dy=".35em" text-anchor="middle">R</text><circle class="n" cx="169" cy="40" r="18"/><text class="t" x="169" y="40" dy=".35em" text-anchor="middle">A</text><circle class="n" cx="169" cy="212" r="18"/><text class="t" x="169" y="212" dy=".35em" text-anchor="middle">B</text><circle class="n" cx="298" cy="126" r="18"/><text class="t" x="298" y="126" dy=".35em" text-anchor="middle">F</text></svg><figcaption style="font-size:.82em;opacity:.72;margin-top:.45rem">Acyclic, F shared</figcaption></figure>

<figure class="ds-fig" style="margin:1.4rem 0;overflow-x:auto"><svg xmlns="http://www.w3.org/2000/svg" id="dsfig-u2-11" viewBox="0 0 338 166" width="338" height="166" role="img" aria-label="General graph with a cycle"><style>#dsfig-u2-11 .e{stroke:#454C5A;stroke-width:1.4;fill:none}#dsfig-u2-11 .e.hi{stroke:#2340B8;stroke-width:2.6}#dsfig-u2-11 .n{fill:#FFFFFF;stroke:#16181D;stroke-width:1.4}#dsfig-u2-11 .n.hi{fill:#E3E9FC;stroke:#2340B8;stroke-width:2.2}#dsfig-u2-11 .n.rb-b{fill:#16181D;stroke:#16181D}#dsfig-u2-11 .n.rb-r{fill:#BD3227;stroke:#BD3227}#dsfig-u2-11 text{font-family:"JetBrains Mono",ui-monospace,Menlo,Consolas,monospace;font-size:13px}#dsfig-u2-11 .t{fill:#16181D;font-weight:500}#dsfig-u2-11 .t.inv{fill:#FFFFFF;font-weight:700}#dsfig-u2-11 .kd{stroke:#16181D;stroke-width:1.2}#dsfig-u2-11 .dot{fill:#16181D}#dsfig-u2-11 .ann{fill:#2340B8;font-size:11px;font-weight:700}#dsfig-u2-11 .lbl{fill:#6F7787;font-family:system-ui,-apple-system,sans-serif;font-size:12px;font-weight:700}#dsfig-u2-11 .ptr{fill:#2340B8;font-size:12px;font-weight:700}#dsfig-u2-11 .ah{fill:#454C5A}#dsfig-u2-11 .ah.hi{fill:#2340B8}#dsfig-u2-11 .wl rect{fill:#FFFFFF;stroke:#DCE0E7}#dsfig-u2-11 .wl .t{font-size:12px;font-weight:700}#dsfig-u2-11 .wl.hi rect{fill:#2340B8;stroke:#2340B8}#dsfig-u2-11 .wl.hi .t{fill:#FFFFFF}html.dark #dsfig-u2-11 .e{stroke:#B1B7C3}html.dark #dsfig-u2-11 .e.hi{stroke:#8FA3FF}html.dark #dsfig-u2-11 .n{fill:#161920;stroke:#E6E8ED}html.dark #dsfig-u2-11 .n.hi{fill:#1E2748;stroke:#8FA3FF}html.dark #dsfig-u2-11 .n.rb-b{fill:#E6E8ED;stroke:#E6E8ED}html.dark #dsfig-u2-11 .n.rb-r{fill:#FF7E71;stroke:#FF7E71}html.dark #dsfig-u2-11 .t{fill:#E6E8ED}html.dark #dsfig-u2-11 .t.inv{fill:#0F1115}html.dark #dsfig-u2-11 .kd{stroke:#E6E8ED}html.dark #dsfig-u2-11 .dot{fill:#E6E8ED}html.dark #dsfig-u2-11 .ann{fill:#8FA3FF}html.dark #dsfig-u2-11 .lbl{fill:#858D9C}html.dark #dsfig-u2-11 .ptr{fill:#8FA3FF}html.dark #dsfig-u2-11 .ah{fill:#B1B7C3}html.dark #dsfig-u2-11 .ah.hi{fill:#8FA3FF}html.dark #dsfig-u2-11 .wl rect{fill:#161920;stroke:#2A2E37}html.dark #dsfig-u2-11 .wl.hi rect{fill:#8FA3FF;stroke:#8FA3FF}html.dark #dsfig-u2-11 .wl.hi .t{fill:#0F1115}</style><defs><marker id="ah17" viewBox="0 0 10 10" refX="9" refY="5" markerWidth="7" markerHeight="7" orient="auto-start-reverse"><path class="ah" d="M0,1 L9,5 L0,9 z"/></marker><marker id="ahh17" viewBox="0 0 10 10" refX="9" refY="5" markerWidth="7" markerHeight="7" orient="auto-start-reverse"><path class="ah hi" d="M0,1 L9,5 L0,9 z"/></marker></defs><path class="e" d="M55.8,115.5 L151.5,51.6" marker-end="url(#ah17)"/><path class="e" d="M184.8,50.5 L280.5,114.4" marker-end="url(#ah17)"/><path class="e" d="M279,126 L61,126" marker-end="url(#ah17)"/><circle class="n" cx="40" cy="126" r="18"/><text class="t" x="40" y="126" dy=".35em" text-anchor="middle">R</text><circle class="n" cx="169" cy="40" r="18"/><text class="t" x="169" y="40" dy=".35em" text-anchor="middle">A</text><circle class="n" cx="298" cy="126" r="18"/><text class="t" x="298" y="126" dy=".35em" text-anchor="middle">B</text></svg><figcaption style="font-size:.82em;opacity:.72;margin-top:.45rem">General graph with a cycle</figcaption></figure>

Asked: [7 marks] (Jun 2023) What is a file? Briefly explain different directory structures. What kind of directory structure is used in UNIX?

File Protection

<span style="display:inline-block;padding:.16em .6em;border:1.5px solid currentColor;border-radius:999px;font-size:.68em;font-weight:700;letter-spacing:.06em;text-transform:uppercase;opacity:.75">Not asked since 2022</span>

Definition. File protection controls who may perform which operation (read, write, execute, delete) on a file.

Key points.

  1. An access-control list (ACL) names each user and the rights that user has for the file.
  2. UNIX shortens this to three classes, owner, group and others, each with rwx bits, e.g. rwxr-xr--.
  3. Per-file passwords are hard to manage.

System Calls for File Management

<span style="display:inline-block;padding:.16em .6em;border:1.5px solid currentColor;border-radius:999px;font-size:.68em;font-weight:700;letter-spacing:.06em;text-transform:uppercase;opacity:.75">Not asked since 2022</span>

Definition. System calls are the interface through which programs request file services from the kernel.

Key points.

  1. open(name, mode) returns a file descriptor and close(fd) releases it.
  2. read(fd, buffer, n) and write(fd, buffer, n) transfer n bytes at the current position.
  3. lseek(fd, offset, whence) sets the position for random access.
  4. creat/unlink create and delete files, and stat returns attributes.

Disk Scheduling Algorithms

<span style="display:inline-block;padding:.16em .6em;border:1.5px solid currentColor;border-radius:999px;font-size:.68em;font-weight:700;letter-spacing:.06em;text-transform:uppercase;opacity:.75">High weight</span>

Definition. <mark>Disk scheduling chooses the order in which pending requests are served so as to reduce total seek time, the time to move the arm to the required cylinder.</mark>

Formula. $$\text{Total head movement} = \sum |c_{i+1} - c_i|$$

Key points.

  1. FCFS serves requests in arrival order, fair but with long arm movement.
  2. SSTF serves the nearest request, giving less movement but possible starvation of far requests.
  3. SCAN (elevator) sweeps to one disk end serving requests on the way, then reverses.
  4. C-SCAN serves in one direction only, then returns to the other end without serving, giving uniform waiting time.
  5. LOOK is SCAN, but reverses at the last request instead of the disk end, saving movement.
  6. C-LOOK is C-SCAN that jumps from the last request to the first.
  7. SCAN vs LOOK: SCAN goes to cylinder 0 or 199, LOOK stops at the last request, so LOOK has less arm movement and waiting; both serve edge cylinders less often than the middle, so that is not a difference.
  8. C-SCAN and C-LOOK fix that non-uniform wait: they serve in one direction and jump back, so every cylinder waits about equally.

Example 1. 200 cylinders (0-199), queue 23, 89, 132, 42, 187. No head position is given, so assume head at 100 moving up; a return jump counts as movement.

Algorithm Working Total
FCFS 77+66+43+90+145 421
SSTF 11+43+55+145+19 273
SCAN (199-100) + (199-23) = 99+176 275
LOOK (187-100) + (187-23) = 87+164 251
C-SCAN 99 + 199 (jump to 0) + 89 387
C-LOOK 87 + 164 (jump to 23) + 66 317

Answer: FCFS 421, SSTF 273, SCAN 275, LOOK 251, C-SCAN 387, C-LOOK 317; LOOK moves least, 24 less than SCAN.

Example 2. 5000 cylinders (0-4999), head 143, previous request 125. Since 143 > 125 the head is moving up, so SCAN and LOOK go up first. Queue: 86, 1470, 913, 1774, 948, 1509, 1022, 1750, 750, 750, 750, 130.

Algorithm Working Total
SSTF path 143>130>86>750 (x3, repeats cost 0)>913> 948>1022>1470>1509>1750>1774: 13+44+664+163+35+74+448+39+241+24 1745
SCAN (4999-143) + (4999-86) = 4856+4913 9769
LOOK (1774-143) + (1774-86) = 1631+1688 3319

Answer: SSTF = 1745, SCAN = 9769, LOOK = 3319; LOOK beats SCAN by 6450 = 2 x (4999-1774), the wasted trip to the end.

Diagram. Seek sequence for Example 1 on the cylinder axis, head starts at 100 (o), each line is one leg, top to bottom, arrow shows direction.

        0     23  42          89 100     132           187199
        |     |   |           |  |       |             |  |
FCFS          <------------------o
              ---------------->
                              ----------->
                  <-----------------------
                  ------------------------------------->
SCAN                             o------------------------>
              <--------------------------------------------
LOOK                             o--------------------->
              <-----------------------------------------
C-LOOK                           o--------------------->
              <-----------------------------------------
              ---------------->

Answer frame. Open with seek time; draw the seek line; define each algorithm in a line, apply it, close with totals and the best. For SCAN vs LOOK, tabulate arm movement, waiting time and efficiency.

Asked: [7 marks] (Jun 2023, Jun 2025) 200 cylinders, queue 23, 89, 132, 42, 187: total distance for SCAN and LOOK. Also: 5000 cylinders, head 143, previous 125, queue 86, 1470, 913, 1774, 948, 1509, 1022, 1750, 750, 750, 750, 130: total distance for SSTF, SCAN, LOOK. Asked: [7 marks] (May 2019) Explain various disk scheduling algorithms with illustration. Asked: [7 marks] (Nov 2023) Difference between SCAN and LOOK disk scheduling. Pitfall: State your head-position assumption for the 200-cylinder question; SCAN goes to the disk end (199), not the last request.

Last-minute revision

  • A file is a named collection of related information on secondary storage; truncate erases contents but keeps attributes.
  • Attributes: name, identifier, type, location, size, protection, time/date/user.
  • Contiguous: fast but external fragmentation; linked: no fragmentation but slow direct access; indexed: direct access with index overhead.
  • Linked mapping: $L = A \div (512-p)$, $O = A \bmod (512-p)$.
  • Free space: bit vector, linked list, grouping, counting; bitmap bits = disk size / block size.
  • SCAN goes to the disk end; LOOK to the last request.
  • 200 cylinders (head 100 up): FCFS 421, SSTF 273, SCAN 275, LOOK 251, C-SCAN 387, C-LOOK 317.
  • 5000 cylinders: SSTF 1745, SCAN 9769, LOOK 3319.

Memory hooks

  • Contiguous = Clustered, Linked = Chain, Indexed = Index card.
  • SCAN is the lift going to the top floor; LOOK stops at the last button pressed.
  • Seek, Spin, Send: the three parts of a disk access.

Coverage checklist

  • File Concept: attributes, operations, file type question.
  • User's and System Programmer's View of File System: access examples.
  • Disk Organization: structure, read/write, file system.
  • Tape Organization: advantages and disadvantages.
  • Different Modules of a File System: layers.
  • Disk Space Allocation Methods – Contiguous, Linked, Indexed: describe, compare, mapping, design points, free space.
  • Directory Structures: five structures, UNIX.
  • File Protection: ACL, rwx.
  • System Calls for File Management: open, read, write, lseek.
  • Disk Scheduling Algorithms: numericals, SCAN vs LOOK, all six.
Go to where you left off?

Quick Add to Notes

Save questions, your own notes and screenshots into notes filed by unit. It takes a free account.

Create free account

Have an account? Log in