Mass Storage Structure and Disk Management

Mass Storage Structure and Disk Management

16.1 The Magnetic Disk: Structure, Attachment, and Performance

16.1.1 The Magnetic Disk Mechanism

The previous session covered the disk structure and the disk attachment; this session continues with disk scheduling and disk management. Everything here rests on one device: the magnetic disk, the workhorse of secondary storage. Before you can judge its performance, you need to know how it works mechanically.

A magnetic disk is a flat platter coated with a magnetic material, and its surface is organized in a simple geometric way. The surface carries many concentric circles — circles that share the same center at the spindle — and these circles are called tracks. Each track is further divided into sectors, and each sector is capable of holding certain blocks. A block is the unit of data transfer: when the disk controller reads or writes, it deals in blocks. The disk also has a head — a read/write arm — that currently points to one particular position on the disk, and the arm can be positioned at any place on the platter. In a real drive, each platter surface has its own head, and all heads move together as one unit, so every surface is always positioned at the same ring at the same time.

To reach data, the disk has to go through a fixed sequence of finds: first find the right track, then find the sector on that track, then find the block inside the sector, and only then transfer the information. The whole system is built around this hunt. Two costs dominate this process:

• Seek time — the time the arm takes to travel to the particular track. Seek time depends on seek distance: the farther the head has to travel to reach the target block, the longer the seek. An efficient scheduling algorithm reduces this travel.
• Rotational latency — the time the platter takes to spin the wanted sector under the head. Once the head is parked on the right track, the disk still has to rotate until the exact sector passes beneath it; on average that is half a revolution.

These two are the things to manage on a magnetic disk. A useful way to picture the mechanism: draw the platter as a dartboard circle seen from above, with the tracks as the rings and the sectors as the pie slices cut across all rings. The head sits at the end of an arm that can swing from the rim to the spindle; a block is the intersection of one ring and one slice. Seeking is swinging the arm to the right ring; rotational latency is waiting for the right slice to come around. The seek part the OS can influence by choosing which request to serve next; the rotation part is mostly fixed by physics once the request is chosen.

Real-world: magnetic disks remain the dominant secondary storage device in general-purpose computers, which is exactly why the structure and the attachment of the disk matter enough to study. Even in an age of flash storage, the hard disk's mechanical model — seek, rotate, transfer — is the model behind every disk-scheduling algorithm you will meet.

16.1.2 Hard Disk Performance Metrics

Once the mechanism is clear, performance is described with a small set of measurable quantities: transfer rate, seek time, average seek time, latency, and average latency. From these you must be able to calculate the access time — and the average access time.

• Transfer rate (how fast data flows): the rate at which data move between the drive and the computer once the head is positioned, usually given in megabytes per second.
• Seek time (how far the arm flies): the time to move the arm to the requested track. Because the arm starts from wherever it last stopped, the actual seek time varies per request.
• Average seek time (typical arm flight): the average of seek times over many requests landing at arbitrary positions.
• Latency / rotational latency (how long the disk must spin): the time for the desired sector to rotate under the head. Average latency is half a full rotation, because the wanted sector is equally likely to be anywhere on the circle when the head arrives.
• Access time (the total bill): seek time + latency + transfer time + controller overhead — everything that passes between requesting data and receiving it.

The parts add up cleanly. When you check the average access time, you take the average latency plus the average seek time, and then the transfer time is there, and the controller overhead; together these form the average access time:

$$\text{average access time}=\text{average seek time}+\text{average rotational latency}+\text{transfer time}+\text{controller overhead}$$

Here average seek time is the typical time for the arm to move to the requested track, average rotational latency is the typical time for the desired sector to rotate under the head, transfer time is the time to move the data between disk and memory once the head is positioned, and controller overhead is the processing time spent by the disk controller itself. Each component is an average because requests land at arbitrary positions.

The one piece of conversion you must know is the link between the disk's rotation speed and the average latency: you should know what the RPM is for the corresponding average latency. A disk spinning at $R$ RPM completes one revolution in $60/R$ seconds, and on average the wanted sector is half a rotation away, so:

$$\text{average rotational latency}=\frac{1}{2}\cdot \frac{60}{\text{RPM}}\text{ seconds}$$

This is the standard relationship: rotation time comes from "revolutions per minute" (RPM) via $60/\text{RPM}$ seconds per revolution, and the "average" halves it. For example, a disk at 7200 RPM turns once in $60/7200=0.00833$ seconds (8.33 ms), so its average rotational latency is 4.17 ms; a 10,000 RPM disk turns in 6 ms and averages 3 ms of rotational latency. A problem of this exact type — where one of the RPM values is given and you use it to find the average latency, then plug it into the average access time — is shown in the presentation, and the same type of problem may come in the comprehensive exam.

16.1.3 Disk Bandwidth

Alongside time, there is bandwidth. Disk bandwidth is how many bytes of data get transferred, always divided by the total time between the first request — the moment the request to a particular block is made — and the time taken to complete the transfer:

$$\text{disk bandwidth}=\frac{\text{total number of bytes transferred}}{\text{total time between the first request and the completion of the transfer}}$$

So bandwidth captures the whole journey: making the request, seeking, waiting for the sector, and moving the bytes. It is a throughput figure, not a raw media speed: a drive that can read 200 MB/s off the platter will still deliver a low bandwidth number if the request order forces long seeks between every small transfer.

The aim in this game is simple: have a fast access time, keep the bandwidth consumed low, and minimize the seek time as much as possible. The seek time and the rotation latency are the two quantities a scheduling algorithm can attack; the bandwidth tells you how efficiently the transfer part is being carried out.

16.1.4 Magnetic Tape vs Magnetic Disk (Q&A)

A student interrupts here: solid-state drives and magnetic tape are both secondary storage — so what is the difference between a solid-state drive and a magnetic tape?

Real-world: tape survives today exactly in that backup-and-archive role — bulk storage that is written once and read rarely, and the medium for moving large datasets between systems. Robotic tape libraries back up entire data centers, and long-term archives (legal records, scientific data, media masters) live on tape precisely because its cost per gigabyte is far below disk.

16.1.5 Disk Structure

The disk structure itself deserves a precise picture. The concentric circles on the platter are the tracks; the tracks are divided further into sectors; each sector is capable of holding certain blocks. When a request arrives, the disk address is expressed in terms of cylinders — you can treat the matching tracks stacked across the platters as imaginary cylinders — so the lookup is: find the right cylinder, then the sector, then the block present in that sector. That is how the disk controller locates information, whether it is placing information (a write) or retrieving it (a read).

Picture the address as a stack of floor plans: each floor is one platter, the cylinder is the set of rooms that sit at the same ring position on every floor, the sector is one room on one floor, and the block is the shelf inside that room. Give the controller (cylinder, sector, block) and it swings all the heads to that cylinder, waits for that sector to rotate under its head, and reads or writes the block.

The controller actually deals with a flat list of logical block numbers (each usually 512 bytes, or 1024 bytes on some formatted disks) that it maps onto this three-part address in order: first across the sectors of a track, then across the tracks of a cylinder, then across cylinders from the outside in. The cylinder-based address is the mental model — the reason the lookup reads "cylinder, then sector, then block."

16.1.6 Disk Attachment and Storage Networks

How does the disk get connected to the system at all? There are several attachment paths, all reviewed from the previous session:

• Fiber channel — a high-speed serial connection used to attach disks to a system. It runs over optical fiber or copper, and its switched form connects many hosts and many storage devices in one fabric.
• SCSI — the classic parallel command protocol for connecting disks (the small computer system interface). One SCSI bus carries a host adapter plus up to fifteen storage devices, each able to accept commands addressed to individual logical units.
• Storage arrays — a collection of disks attached over the network, one type of network storage where information can be stored and retrieved. The array manages its own disks (often as a RAID set) and presents volumes to the host.
• Network attached storage (NAS) — another type of storage system, and the name tells you the point: it is not a local storage device. The protocols used are network file system (NFS) over RPC, and the transport protocol used underneath is TCP or UDP. That is how network attached storage works — your system talks to a storage system elsewhere on the network.

The NAS stack is worth unpacking because each layer has a job. The network file system (NFS) is the file-level protocol: your machine asks, in file terms, "give me bytes 0–4095 of file report.pdf." The remote procedure call (RPC) wraps that request as a function call that travels to a remote machine. The transport layer (TCP or UDP) carries the RPC packet over the IP network. So the whole path is file request → RPC → TCP/UDP → network → remote storage server.

Real-world: NAS appliances in offices and data centers follow exactly this shape — NFS over RPC over TCP/IP — which is why a file server can be shared by many client machines. When the storage must not share bandwidth with ordinary network traffic (for example, a database cluster), the same fiber channel technology reappears as a separate storage area network (SAN): a private switched network connecting servers to storage arrays, which is how large installations give many hosts fast access to the same disk pools.

16.2 Disk Scheduling

16.2.1 Why We Schedule

Disk scheduling is one of the important parts of the disk, and the reason is the aim stated above: fast access time. Requests for I/O — input or output — come from many sources: the operating system, system processes, and user processes. Each request arrives with a disk address in terms of cylinders, sector, and block (plus the direction of the transfer, the memory address to use, and the number of sectors to move). When more than one request comes at the same time, the system maintains a queue: if the disk is idle, the work is done immediately; otherwise the disk puts the processes in the queue, and according to the type of scheduling algorithm, the service is done. The algorithm decides the order in which queued requests reach the head — and because seek time depends on seek distance, a clever order means a much shorter total head journey.

So the game is: minimize the seek time as much as possible, because that is the only part of access time the scheduling order can influence. An efficient scheduling algorithm, used to find the block present in the sector, reduces the seek time. Below, every algorithm is worked on the same request queue so the head movements can be compared directly. The queue holds block numbers between 0 and 199, the head currently points at block 53, and the requests in order of arrival are: 98, 183, 37, 122, 14, 124, 65, 67.

16.2.2 FCFS — First Come, First Served

FCFS means first come, first served: the request that comes first is served first. The request, in this context, is in the form of a block number. It is the simplest policy — the disk serves the queue exactly in arrival order, with no reordering at all. If a problem gives very large numbers (in the thousands), you still start the trace from the given head position and move through the queue in order.

That 640 is the problem with FCFS. The head is dragged back and forth across the disk — for instance, from 183 all the way back to 37, and later from 122 to 14 and 14 to 124 — because arrival order takes no account of where the head is. No attempt is made to serve nearby requests while passing them. Its only virtue is fairness: requests are served in the order they arrived, so nobody is overtaken. But fairness buys no performance, and on a busy disk the wild swings cost real time.

16.2.3 SSTF — Shortest Seek Time First

The next algorithm picks the request with the minimum seek time, measured from the current head position. It works like the SJF scheduling we saw in CPU scheduling: whichever request has the smallest distance from where the head stands gets served first. SSTF is also called the shortest-seek-time-first scheduling, and it is common, with a natural appeal — serve the nearest thing first.

That is a large reduction from FCFS's 640. But we cannot say SSTF is optimal. The order depends on the direction the head picks first. In this trace the head moves forward first; had it charted backward instead, it would have encountered 37 first, then 14, and from there moved up to 65, 67, and on to 98. The lecture estimated that path at roughly 203 to 205 cylinders; the exact recomputation of the order 53 → 37 → 14 → 65 → 67 → 98 → 122 → 124 → 183 gives 16 + 23 + 51 + 2 + 31 + 24 + 2 + 59 = 208 cylinders, which is the figure the textbook works out as well. Either way, the point is the same: SSTF is not optimal, because the choice of initial direction can change the answer. In the worst case a request far away can starve while nearer requests keep arriving — since it always stops at whichever request has the shortest seek time, the head can bounce back and forth, exactly as this trace shows.

When to pick which: FCFS only when you value strict fairness over speed; SSTF when you want a quick, greedy improvement and can tolerate starvation risk.

16.2.4 SCAN — the Elevator Algorithm

SCAN behaves like an elevator. Think of a real elevator: it starts from one position and moves up to an end, then comes down, then moves up again — it goes to the extreme end, then comes back, servicing on the way. SCAN is the disk version: when the head moves toward one end of the disk, it services all the requests that come on its way, until it reaches the end of the disk; then it reverses itself and services to the other end, until it reaches the other end of the disk.

Either way, SCAN is no better than SSTF on this queue — and the real problem is different: when the head moves one side, requests on the other side wait, even if they arrived first. Requests like 98, 122, or even 183, which arrived earlier, still have to wait because the head must go to one end, come back all along, and reach the other end. If the density of requests is uniform across the disk, this is not a problem; if it is not uniform, the side with more density — the side with the heaviest load — waits the longest. That is the weakness of SCAN.

16.2.5 C-SCAN — Circular SCAN

C-SCAN is a small variation of SCAN, and its effect is to make the wait time uniform. Here the head moves from one end to the other end only, servicing whatever requests come on its way; the change is that when it reaches the other end, it immediately returns to the beginning of the disk — it moves in a circular motion. The return trip is a dead return: no request is serviced on the way back. Then it starts servicing again as it moves forward.

The key property to remember is the uniform wait time: every cylinder gets visited once per circular sweep, so no position waits for two full sweeps the way a far side does under SCAN. This is a circular list, as the name suggests — imagine the cylinder range bent into a ring, with the head always moving the same way around the ring and jumping back through the seam. Under plain SCAN, a request just behind the head can wait for nearly two full sweeps (down to the end, up to the other end, and back); under C-SCAN every request waits at most about one full sweep.

16.2.6 LOOK and C-LOOK

If we want to be smarter, we take the variations of SCAN: LOOK, and the variation of C-SCAN, C-LOOK. The rule change is tiny but important: instead of travelling to the end of the disk, the arm stops at the last request in the current direction, then turns.

• LOOK: the arm starts from the current position, services all requests on its way, and does not go till the end — before reaching the end it stops wherever the last request is, then immediately turns and services the requests on the way back. (If it is SCAN, it has to go to the end; if it is LOOK, it goes only to the last request.)
• C-LOOK: since it is circular LOOK, it does not service any request on the return trip; it immediately returns to the beginning of the first request — note, not the beginning of the disk, but the beginning of the first request (here 14) — and starts servicing in the forward direction, going up to whichever is the last request, then reversing (in LOOK) or jumping back to the first request (in C-LOOK).

In practice, most systems implement LOOK-style behavior rather than raw SCAN: the arm "looks ahead," checks whether any request remains in the current direction, and turns around as soon as the direction is empty. The names capture the behavior — the algorithm looks before it continues.

16.2.7 Choosing a Disk Scheduling Algorithm

How do you select an algorithm? The lecture gives three guide rails:

1. SSTF is common and has a natural appeal — serve the nearest request — but we have seen it is not optimal, and the initial direction of the head can change the answer.
2. SCAN and C-SCAN are better when the load on the disk is heavy: starvation is less there compared to SSTF, because the head sweeps the whole disk and every request on the sweep path gets served eventually.
3. The choice depends on the number of requests and what type of requests come — the performance of the algorithm lies in that fit, so different workloads call for different algorithms.

If you want to pick, you can select either SSTF or a LOOK variant — those are the two reasonable defaults, as the textbook also concludes. Whatever the scheduling algorithm, it attacks the seek time only. The rotational latency is a different, harder problem: the arm should be placed on the particular track, then we are trying to find the sector, and after finding the sector, the desired block, and from there the data has to be retrieved. Rather than merely placing the head on the track, you must place it on the correct position within the block — that is why rotational latency is more difficult than seek time for any of the disk scheduling algorithms.

16.2.8 Practice Problem and Exam Notes

A practice problem is given to work out. Suppose you have 5000 tracks, numbered from 0 to 4999. The arm initially starts at track 200, and it moves toward the last track. There are 1000 disk access requests, and the specific task is: what is the total amount of head movement required by the SCAN scheduling algorithm? You are asked to draw the scheduling for this problem — at least two or three of the algorithms, not necessarily all of them, but all the algorithms that have been mentioned are fair game.

16.3 Disk Management

16.3.1 Low-Level Formatting and the Error Correcting Code

Disk management controls how a raw disk becomes a usable store. A raw disk is a disk that arrives without any file system — typically straight from the manufacturer, produced without any type of formatting. The first step is low-level formatting, also called physical formatting: dividing the disk into many sectors so that the disk controller can read and write. The tags already exist on the platter; formatting organizes them into sectors.

Each sector carries three kinds of information: a header, a trailer, and the data. The header holds the sector number and related bookkeeping; the trailer holds the ECC — the error correcting code; the data is where the information is placed. Data blocks are laid out in terms of 512 or 1024 bytes, and the information is placed on those blocks.

The ECC exists for a reason, and the checking walkthrough goes like this. When information is written, error correcting codes are placed in the trailer. Later, when a user accesses the same data, some of the bytes are taken, the error correcting code is calculated from those bytes, and it is compared with the ECC present in the trailer. If the two are the same, the disk is not corrupted and the information is there as such; if they differ, something has happened to the disk — it might have been corrupted or crashed — and the disk has to be reformatted.

One precision from the textbook is worth carrying: the controller's ECC is usually strong enough to identify which bits changed and to report a recoverable soft error — the sector is read, corrected, and life goes on. A mismatch that the code cannot repair (a hard error) means the sector is genuinely bad, and that is where the sparing machinery of 16.3.4 takes over. So "reformat the disk" is the last resort, not the first reaction: the ECC check tells you that something is wrong, and only an unrecoverable read failure makes the sector unusable.

16.3.2 Logical Formatting, Partitions, and Clusters

Physical formatting alone is not enough — before files can live on the disk, another structure has to be created: logical formatting, which is the creation of the file system. For that, the disk has to be partitioned first. Each partition contains one or more groups of cylinders and is treated as a logical disk; a partitioned raw disk is divided into these logical disks, and each logical disk gets its own file system.

The two steps have different jobs. Partitioning divides the raw array of blocks into chunks — for example, one partition for the operating system's executable code, another for user files — and from then on the OS treats each partition as a separate disk. Logical formatting writes the file system's own data structures onto a partition: the map of free and allocated space (a FAT or inodes), and an initial empty directory. Only after both steps can you create files and directories on that partition.

Why make a file system at all? Because it lets you group blocks into clusters. The transfer works like this: disk I/O is always performed in terms of blocks, whereas file I/O can be done in terms of clusters by grouping blocks — imagine four blocks joined into a cluster. The trade-off is instructive: when you try to transfer a cluster, the time taken to read the information is more (you gather more blocks), but the time taken to transfer it is less, because you are moving more bytes per operation. So the time to transfer a cluster differs from the time to perform the I/O in terms of blocks.

On the exam, keep the pairing straight: disk I/O deals in blocks, file I/O deals in clusters, and a cluster is a fixed group of blocks (for example, four). The cluster size is chosen when the file system is created and is a classic performance dial — too small and file I/O pays the per-block tax, too big and space is wasted on small files.

16.3.3 Bootstrap, Boot Partitions, and the Master Boot Record

When a raw disk is partitioned, the system still needs a way to start. Whenever the system is switched on, it is initialized with the help of the bootstrap program. The bootstrap can be stored in read-only memory — the advantage being that ROM cannot be changed, and it is always going to be read. When you make a partition, you can make a boot partition: place the boot block there, and inside the boot block put the bootstrap loader program. Instead of the full bootstrap program, a bootstrap loader has a real advantage — it is easier to load it directly into memory and start executing the system.

The bootstrap chain works in two stages. Stage one is a tiny bootstrap loader living in ROM: its only job is to read the boot block from a fixed location on the disk into memory and hand over control. Stage two is the full bootstrap program stored in that boot block: it knows enough to find the operating system kernel anywhere on the disk, load it into memory, and jump to its start. Keeping the big stage on disk matters because ROM is physically permanent — updating the full bootstrap would mean replacing hardware chips — whereas the disk-resident bootstrap can be updated simply by writing a new version to the boot block. A disk with a boot partition is called a boot disk or system disk.

16.3.4 Bad Blocks and Sparing

Not every sector stays healthy, and bad blocks must be handled. Some sectors might be spared — reserved for handling the bad blocks alone. A spare sector does not hold data; it holds only the configurations for setting up the data, so if something is wrong, that particular sector handles it. It helps if the spare sector is the first sector of the disk: then it is easier to find out the bad blocks and handle them (though it may be placed anywhere).

The mechanics make the "first sector" advice concrete. The controller discovers a bad sector when the ECC check fails permanently; it then records the bad address and points it at a spare. If the spares are scattered across the disk, this redirection can confuse the operating system's own scheduling (the OS schedules the logical order of requests, but the head physically travels to the spare). Keeping spares near the sectors they protect — even reserving a whole spare cylinder — keeps the physical movement close to the logical movement. A simple alternative scheme, sector slipping, shifts every sector after the bad one down by one position so the data stays in order; that keeps the layout sequential at the cost of moving many sectors at once.

16.4 Swap Space Management

16.4.1 Swap Partitions and Swap Maps

Virtual memory tries to use the physical memory larger than whatever is present — it manages the physical memory to look bigger — and to do that, virtual memory uses the disk space as an extension of the main memory. The main memory capacity is very small and cannot hold everything, so information has to be transferred to secondary storage: find space in the secondary storage, take the information from there, and place it back when needed. That is swap space management.

So when the disk is partitioned, a separate partition should be allocated mainly for the swap space. Whenever a process starts, there will be space to hold both the text — that is, the program — and also the data. The first thing is the kernel: the operating system kernel is loaded into memory and starts execution, and then it tracks the swap space using swap maps. Because a single swap partition can run out, the system should have multiple swap spaces.

Two design choices matter here. First, where the swap space lives: either a raw partition (no file system at all, managed by a dedicated allocator tuned for speed) or a large file inside a normal file system (easy to create and resize, but slower because every access traverses the file system's structures). Second, how much: a system that runs out of swap space must abort processes or crash, so it is safer to overestimate than underestimate. Multiple swap areas, usually on separate disks, let the paging load spread over several I/O devices instead of hammering one.

16.4.2 Solaris and Linux Swap Management

Two real systems show the two designs.

16.5 RAID Structure

16.5.1 Motivation: MTTF, MTTR, and Mean Time to Data Loss

Once pages live on the disk, something can go wrong — natural causes, a corrupted head, or a head arm placed on a corrupted position can all damage data. There must be an alternative option: the RAID structure — a redundant array of inexpensive disks. The idea behind RAID is that redundant information can be placed on multiple disks, so even if one disk becomes inaccessible, another disk is still accessible and the information can be retrieved. Multiple disk drives provide reliability and also redundancy.

The main aim is to increase the mean time to failure (MTTF) — the time taken for a particular disk to get failed. Alongside it stand the mean time to repair (MTTR) — if one disk fails, a backup must be provided for the data loss, and MTTR is the time taken for that repair in the particular disk — and the mean time to data loss, the time after which data can no longer be recovered. All these have to be calculated, and performance is judged from them.

The assumption of independent failures is worth flagging: power failures and natural disasters (earthquakes, fires, floods) can damage both copies at once, and manufacturing defects make failures in one batch correlate. In those cases the mirror's advantage shrinks toward the single-disk number. To improve things further, a disk can combine in an NVRAM — a non-volatile RAM. Even if the power is switched off, the information present in NVRAM does not vanish, and it helps to improve write performance — the time taken to repair becomes somewhat better compared to a disk without this non-volatile capability. NVRAM acts as a write-back cache that survives power loss, so a write can be considered complete once it reaches NVRAM rather than waiting for the slow platter.

16.5.2 Mirroring and Striping

Two mechanisms run through all RAID levels.

Mirroring is the typical one: imagine a mirror — whatever is in one disk is the same in the other disk. Mirroring provides the reliability.

Striping is the performance mechanism: one piece of information is taken and put across all the disks — with five disks, the information is spread across the disks. Striping can be done in terms of bits (bit-level striping), in terms of bytes (byte-level striping), in terms of sectors (sector-level striping), or in terms of blocks (block-level striping); block-level striping is the most common. By striping, performance improves; and redundancy can improve too. So the pair to remember: mirroring gives reliability, striping gives performance — and when you strip the information across the disks you can provide both performance and reliability.

The two mechanisms answer two different questions. Mirroring asks: what if this disk dies? — and answers with a second copy, at the cost of double the disks and double the writes. Striping asks: how do I get more data per second? — and answers by letting every disk work on every large transfer at once, at the cost of introducing a single point of failure (now one dead disk damages a piece of every striped record). The RAID levels below are the menu of ways to combine these two ideas.

16.5.3 RAID Level 0 — Striping

RAID 0 is striping without redundancy: assume four disks, all non-redundant — no information is seen in multiple disks — and the striping is done, at bit level or byte level. To locate a block, a formula is used. With $n$ disks, the disk holding block $i$ is:

$$\text{disk}=(i\mathrm{mod}n)+1$$

The formula walks blocks around the array in a round-robin cycle: block 1 goes to disk 2, block 2 to disk 3, and so on around the ring, wrapping from disk $n$ back to disk 1. Because the block numbers repeat the same pattern every $n$ blocks, you only need the remainder $i\mathrm{mod}n$ to know where any block sits.

The problem with RAID 0: to access one full piece of information you have to access all the disks, because the information is stripped across them, so the time taken to access is more — but the access can be done in parallel, since the disks are all independent. And with no redundancy, RAID 0 protects nothing: any single disk failure destroys part of every striped record. It is a performance-only choice, used where data loss is tolerable.

16.5.4 RAID Level 1 — Mirroring

RAID 1 is the mirrored level: everything is mirrored. With four disks, the standard layout is two mirrored pairs — two full copies of every block — so if the first disk fails, its pair-mate serves the data; if the second fails, there is still the other pair; the data survives as long as at least one member of each pair survives. The problems: you have to write the information twice — once for the original and once for the copy — and, if both the disk and its mirror fail together (for example, a natural disaster destroying both), there is no information left and you have to starve for the data. That is the main problem with RAID 1.

16.5.5 RAID Level 2 — Memory-Style Error Correcting Codes

RAID 2 borrows the memory-style error correcting codes. With four disks, $n-1=3$ disks are dedicated mainly to correcting the errors when bits are accessed: error correcting codes are present in the three disks, for the four independent disks, in terms of parity. The parity rule: accessing in terms of bits, if the number of bits that are one is even, it is an even parity; otherwise it is odd parity. If it is even parity, the parity bit is set to 0; if it is odd parity, it is set to 1. If any of the bits change in any one of the disks, it is not even parity anymore — the value automatically becomes odd, and the parity present in the parity disk no longer matches what is currently computed. From this mismatch you can find out which particular disk has been corrupted and replace it.

The overhead here: parity checking has to be done, the error correcting codes have to be computed and checked against the parity disks — and that is the reason to move to the next levels. RAID 2 stores error-correction bits on $n-1$ extra disks for $n$ data disks (3 extra for 4 data disks), which is better than RAID 1's 4 extra disks but still heavy — the memory-style scheme was designed for memory chips, where every bit error is a surprise; a disk controller, by contrast, can already tell when a whole sector failed to read, which is why the next level needs only one parity disk.

16.5.6 RAID Levels 3 and 4 — Bit-Interleaved and Block-Interleaved Parity

RAID 3 — bit-interleaved parity. Here there is only one disk for the parity bits — specifically, bit-level striping is employed, and one specific disk, not more than one, contains the information about all the disks. If one disk changes, it has to be checked across this particular parity disk, then corrected. Because it is bit level, the problem returns: the time taken to read or write is more in the case of bit-level parity.

RAID 3's single parity bit works because the disk controller already knows which sector failed: when one disk is damaged, the controller reconstructs each missing bit by parity — if the parity of the remaining bits matches the stored parity, the missing bit is 0, otherwise it is 1. One parity disk replaces three ECC disks, and large transfers run at $n$ times the single-disk speed because every disk participates. The costs: every request, large or small, involves every disk, so the number of independent I/Os per second is low.

RAID 4 — block-interleaved parity. With block-interleaved parity the information is placed across the disks in terms of blocks, so the information can be accessed in parallel, but the time taken to access is still more. Checking the parity again costs: to access information in a first disk, you have to check the corresponding parity block; if any of the values have changed when it is computed, you have to replace it.

RAID 4 keeps one dedicated parity disk, but stripes by blocks: a block read touches only the one disk holding that block, so different reads run in parallel on different disks. The catch is the read-modify-write cost of small writes: writing part of a block requires reading the old data block and the old parity block, computing the new parity, then writing both the new data and new parity — four disk accesses for one logical write, all against the single parity disk, which becomes the bottleneck.

16.5.7 RAID Level 5 — Block-Interleaved Distributed Parity

RAID 5 fixes the weakness of keeping one particular disk for parity: if that parity disk itself gets damaged, there is no provision to check the correctness of the data present in the disks. The next level — block-interleaved distributed parity — places the parity bits across all the disks. The rule to remember above all: the parity for a particular disk is never on the same disk as that data. If $P$ is the parity block present in a given disk, it is not the parity bit for that same disk. The location is found with the same formula as striping: with five disks, to find the third parity block, $3\mathrm{mod}5+1=4$ — the fourth disk holds the parity block for the third. It is kept across the disks for protection.

RAID 5 is the most common parity RAID in practice: it keeps RAID 4's block-level parallel reads, spreads the parity load across all disks, and tolerates any single disk failure — one disk's data is rebuilt from the remaining data blocks plus the parity blocks. The price is the same read-modify-write cycle as RAID 4 for small writes, since every write still touches both a data block and its parity block.

16.5.8 RAID Level 6 — P+Q Redundancy

A further variation is RAID 6, the P plus Q redundancy level: some of the disks hold redundant information of the parity bits or parity blocks. For example, out of six disks, for 4 bits of data there should be 2 bits of parity across the disks. Because of the redundancy, the time taken to access the information is always more here, and placing the information itself takes some time.

RAID 6 stores two independent redundancy codes — the conventional parity $P$ plus a second code $Q$ computed with error-correcting codes such as Reed–Solomon — so it survives two disk failures at once. With 4 data bits and 2 parity bits per group, the usable space overhead is 50%, and every write must update both $P$ and $Q$, which makes writes the slowest of the parity levels. The payoff is the window of safety: while one failed disk is being rebuilt (a process that can take hours on large arrays), a second disk can fail without data loss.

16.5.9 RAID 0+1 and 1+0

When one level is not enough, levels are combined: RAID 0+1 is a combination of 0 and 1, and 1+0 is the other order — generally, 1+0 is somewhat better.

• 0+1: first strip across the disks — with 8 bits and 8 disks, strip each bit in each disk (with 4 bits and 4 disks, each disk gets one bit) — and after stripping, produce a mirror of the stripped set. The name decodes as: 0 means non-redundant striping, 1 means mirrored. So the data is stripped, then mirrored.
• 1+0: first mirror, then strip — whatever is mirrored must also be checked vertically. If something happens to one set, the other set — the mirror of this set — is still there, and the mirror of that, and so on. That is why 1+0 is somewhat better compared to RAID 0+1.

Both are described as stripped or mirrored strips, and they provide high performance and reliability.

16.5.10 Extensions: Snapshots, Replication, and Hot Spare

Beyond the levels, extra features can be added to overcome disadvantages:

• Snapshot: take a snapshot of the file just before the changes take place, and make a duplication of it in a separate place. Modern implementations use copy-on-write: the snapshot starts as a tiny record, and only the blocks that are about to be overwritten get copied into it — so hundreds of snapshots can coexist cheaply, each a frozen picture of the file system at one instant.
• Replication: duplicate the data either synchronously or asynchronously — as soon as some changes happen, they can be written into a separate site (synchronous), or only after completing all the writes (asynchronous). Synchronous replication guarantees that both copies hold the same data before a write is reported complete — safe, but every write waits for the remote site. Asynchronous replication batches writes and sends them periodically — fast and distance-unlimited, but a primary-site failure can lose the writes still in flight. This is the mechanism behind disaster recovery across data centers.
• Hot spare disk: a disk dedicated mainly to replacing the failed disk — it carries no information, so whenever a disk fails, another disk is used in its place and is rebuilt. The hot spare mainly decreases the mean time to repair. A hot spare is configured into the array and does nothing until a disk fails; then the array rebuilds the failed disk's data onto the spare automatically, restoring the RAID level without waiting for a human to install a replacement.

Still, failures and corruptions will occur at times and cannot be prevented, so they must be detected and then corrected.

Exam Guidance Summary

With this, the disk management and the mass storage structure topics are complete. The remaining storage implementation topic is very small and optional — it is not required reading, it is not important, and if you want, you can go through it, since many topics are already covered and whichever is relevant for the course has been dealt with.

The central guidance from this session is the weight distribution. Give more importance to the post-mid-semester portions — deadlocks, memory management (paging, segmentation, page replacement), and this mass storage structure. The earlier portions are not forgotten: one or two questions will come from them, but not more. On the numerical side, focus on the post-mid-semester topics; one or two subdivisions of theoretical portions will also be there, and maybe 10 marks will come from the pre-mid-semester portions.

Study plan: go through the course presentations and do the problems in them, and refer to the textbook for the theoretical information. The worked scheduling problem from this session is available to practice: draw at least two or three scheduling algorithms for a given request list and compute the total head movement. Before the exam, revise the mass storage topics with the same weight you give deadlock, paging, segmentation, and page replacement.

Key Industry Applications

• Magnetic tape — the first secondary storage medium, still used for archival backup and for transferring large data between systems; its access time is about a thousand times slower than a magnetic disk. Robotic tape libraries and hierarchical storage management (HSM) systems keep rarely used data on tape precisely because the cost per gigabyte is far below disk.
• Network attached storage (NAS) — enterprise and office file servers follow the NFS-over-RPC-over-TCP/UDP model described for disk attachment, letting many client machines share one pool of files; storage area networks (SANs) extend the same idea on a private fiber channel fabric for database and virtualization clusters.
• Windows booting — the master boot record with boot code and a partition table is the standard booting mechanism on Windows systems; the same MBR layout is what boot managers and disk utilities inspect when a machine will not start.
• Solaris 2 — allocates swap space lazily, only when a dirty page (identified through the reference bit) is forced out of physical memory, so modern machines with large memories avoid reserving swap for pages that are never evicted.
• Linux swap — swap areas are divided into slots tracked by swap maps; a value of 0 means free and a value greater than zero means occupied (e.g., 3 means three processes sharing the slot), which is how shared memory regions that get paged out stay correctly tracked.
• RAID arrays — the standard reliability tool of storage systems: mirroring (RAID 1) for reliability, striping (RAID 0) for performance, parity levels (RAID 2–6) for error correction with less overhead, and combined levels (0+1, 1+0) for both; RAID 5 is the most common parity layout, and enterprise arrays add hot spares so failed disks are rebuilt automatically.
• NVRAM — non-volatile RAM inside disk controllers keeps information after a power loss and improves write performance; it is the same technology that lets storage arrays treat writes as complete once they reach the controller cache.
• Hot spare disks — dedicated standby disks that replace failed disks and reduce the mean time to repair; a hot spare lets a RAID array rebuild itself and restore its protection level without waiting for a human technician.
• Solaris ZFS — stores checksums for both data and metadata so corruption is detected and corrected, and manages file system space from a shared storage pool instead of a volume manager, which is why ZFS appliances dominate in environments where silent data corruption is unacceptable.