File Systems and Mass Storage Structure

This session wraps up the file-system implementation topics — directory structures, allocation methods, free space management, and the network file system — and then opens the mass storage structure: magnetic disks, their performance, and the three ways a disk attaches to a system. Disk scheduling and disk management are left for the next contact session.

The main path through the session runs as follows:

1. File system structure — from a raw disk, to partitions, to volumes, to directories (15.1–15.3).
2. Allocation methods — contiguous, linked (with FAT), and indexed (with UNIX's combined scheme), and when each is the right tool (15.4).
3. Free space management — bitmap, linked list, grouping, counting, and ZFS space maps (15.5).
4. The network file system (NFS) — mounting remote directories, stateless servers, RPC and XDR, path resolution, and caching (15.6).
5. Mass storage hardware — magnetic disk anatomy, the performance formulas, the worked example, SSDs and tape (15.7–15.9).
6. Disk structure and attachment — logical blocks, CAV vs CLV, host-attached storage, SANs, and NAS (15.10).

The session closes with the professor's answer to the standard question: the comprehensive exam carries both theory and problems, with the problem-style material (disk performance, disk scheduling, paging, segmentation, deadlocks, CPU scheduling) weighted more heavily than theory detail.

15.1 File System Concepts: From Raw Disks to Volumes

15.1.1 General File System Concepts

The general file system ideas were covered in the previous module, so most of them are already familiar from everyday use — every programming language and every operating system touches them. This subsection is a fast recap; the session spends its real time on what comes after.

A file is the named unit of stored information on secondary storage, and it carries a set of file attributes:

• Name — the symbolic string we type (for example, report.txt).
• Identifier — a unique tag, usually a number, by which the file system knows the file internally; it is the non-human-readable name.
• Type — needed on systems that support several kinds of files (source, binary, directory).
• Location — a pointer to the device and to the position of the file on that device.
• Size — the current size in bytes, words, or blocks.
• Protection — access-control information deciding who may read, write, or execute.
• Owner and timestamps — who created it, and when it was created, last modified, and last used; these are useful for protection, backup decisions, and usage monitoring.

File operations are the actions performed on files: create (find space and make a directory entry), open (search the directory and copy the entry into the open-file table), read (using a current-file-position pointer), write, reposition (seek — moving the pointer without I/O), delete (release the space and erase the entry), and truncate (erase contents but keep the attributes). Most operating systems expect open() before active use so that repeated searches of the directory are avoided; the open call returns a handle (called a file descriptor in UNIX, a file handle in Windows) used for all later operations.

Files also come in different file structures and file types:

• None — a stream of bytes with no imposed structure (the UNIX view).
• Simple record structure — a sequence of fixed-length records.
• Complex formatted structure — for example, a document or a database with internal structure managed by the application.

Access methods describe how we reach the data. Sequential access reads from the beginning onward, one record after another — the natural method for tapes and for logs. Direct (random) access jumps straight to any record using its relative position; disks support this directly because any block can be reached by moving the head and waiting for rotation. The professor's framing: sequential access is like reading a book page by page from page 1; direct access is like opening the book at chapter 7 without turning the earlier pages.

15.1.2 Raw Disks, Partitions, and Volumes

Disk structure is the starting point for understanding any file system. Without a file system, a disk is raw: just a bare device that can only be read and written in blocks. Raw disk is still used in special places — UNIX swap space uses a raw partition because it has its own format, and some databases format raw disk to suit their needs.

When the disk is raw, we can partition it into several parts, each of which can be treated as a mini disk. When a file system is placed on a partition, we call that partition a volume — the professor's picture is a vault: a volume is like a vault that contains folders, and each folder holds information or files.

On a typical machine with a C: drive and a D: drive, we first make partitions and then store information on them; each partition (volume) gets its own file system. Alongside this, the device holds some information directly — a device directory — which acts as the table of contents for the whole partition or vault: it records how many blocks the partition has, the block size, and the free-block information for that volume. In UNIX terms this volume-level information is called the superblock; in Windows NTFS it lives in the master file table. That is how the typical file organization looks: raw disk → partitions → volumes with file systems → directories → files.

15.1.3 Directories: Purpose and Operations

A directory is itself a file with respect to the UNIX operating system — a file whose "type" field marks it as a directory, and whose contents are the names and identifiers of the files it contains. Directories support a fixed set of operations:

• Search for a file — find the entry for a given name (and, often, match patterns).
• Create a file — add a new entry.
• Delete a file — remove the entry and free its space.
• List a directory — list the files and their entries.
• Rename a file — change the name, possibly moving the file's position in the structure.
• Traverse — walk from one file system to another, which is how backup and recovery tools visit every file.

Why organize the disk into directories at all? The professor gives three reasons, in order:

1. Efficiency — with directories we can locate a particular file quickly. A flat pile of files would force a linear search of every name on the disk; the directory narrows the search to one small table.
2. Convenience — if we keep folders named after a course or a project, the person using the machine finds things easily without remembering exact paths.
3. Grouping — project-based information lives in a particular folder or directory, so files are grouped logically. That grouping is the main aim of the directory.

15.2 Directory Structures

15.2.1 Single-Level and Two-Level Directories

The simplest arrangements are the single-level directory structure and the two-level directory structure.

In a single-level structure, one directory holds every file on the system; any two files need distinct names. It is easy to support and understand, but it fails as soon as the system has more than one user or many files. If two users both call their file test, the unique-name rule is violated. The professor's warning: the failure is not a theoretical curiosity — even a single user with a few hundred files quickly loses track of what is stored where.

The two-level structure gives each user a directory of their own. The textbook machinery: a master file directory (MFD) is indexed by user name or account number, and each entry points to that user's user file directory (UFD), which lists only that user's files. When a user logs in, the system looks up their UFD; every reference searches only that UFD, so two users may each have a file named test without conflict. The trade-off: users are now isolated from each other. That is an advantage when users are independent, but a disadvantage when a team must cooperate — the two-level scheme gives no clean way to share a file between two users.

Both designs share a structural limitation: they offer no way to organize a single user's files into projects. Those disadvantages are the reason the next design, the tree structure, exists.

15.2.2 Tree-Structured Directories

The tree-structured directory is the hierarchy we all know from UNIX and Windows. The professor asks us to picture an inverted tree: the root sits at the top, the subdirectories are the internal nodes, and what we call the leaf of a sub-tree is at the bottom — the leaf marks the end of that branch of the hierarchy, whether it is the left tree, the center one, or the right tree.

                       (root)
                       /  |  \
                    bin  usr  tmp
                        /  \
                     home  shared
                     /  \      \
                  alice bob   projects
                  /               \
               docs             os-lab

The tree has a root directory, and every file in the system has a unique path name from the root to it. A directory is simply another file — in UNIX one bit in each directory entry marks the entry as a file or a subdirectory — and each process keeps a current directory so that short relative path names work. The advantages of the tree structure are concrete:

• No naming conflicts. The same file name can appear in two different directories, and the same subdirectory name can appear inside two different subdirectories. There is no conflict because the full path disambiguates them — /home/alice/docs/report.txt and /home/bob/report.txt name different files.
• Per-user space. When a group of users is present, each user can be assigned a particular directory (a folder) and keep their files there; inside it they can build whatever sub-tree they like.

The slides cover how to create entries and how to delete them, and all the operations present in the tree level — the same behaviour we have seen in UNIX and Windows, so no command-by-command detail is repeated here. One policy point worth remembering: when deleting a non-empty directory, some systems refuse unless the directory is empty first (MS-DOS), while others offer a recursive delete of the whole sub-tree in one command (rm -r in UNIX) — more convenient, but dangerous because one mistake removes an entire branch.

15.2.3 Cyclic Graph and General Graph Directories

A cyclic graph directory is built from nodes that are connected to each other, like a general graph. The key rule for a cyclic graph structure is that a cycle must not form within the graph — forming a cycle is the problem the design must avoid — which is why it is called an acyclic graph: sharing is allowed, cycles are not.

The advantage of a cyclic graph is sharing. Suppose an organization has two groups — two different teams or domains — that must communicate through a particular file. A cyclic graph directory lets that one file be shared by the two groups: the same file (or subdirectory) appears in two places at once, but it is still one file, not two copies. If one group changes the file, the other group sees the change immediately; a new file created inside a shared subdirectory appears automatically in both views.

The disadvantages follow directly from sharing:

• A mistake made by one group affects the other group too.
• If one team unknowingly deletes the shared file, the other team is left pointing at a file that no longer exists. This is called a dangling pointer — a directory entry that points to a file that is not there. That is one of the problems that must be resolved.

So to build a proper acyclic graph directory, we have to overcome these difficulties. The general graph directory structure is mentioned next; most of the graph rules apply there as well, and the slides walk through it. In a general graph, cycles are permitted, and with them comes the harder problem of garbage collection — deciding when a file that can be reached through several paths is truly no longer needed.

15.2.4 Path Naming Across Operating Systems

Different operating systems represent the path to a file differently, and the session compares them:

• DOS: the path name is built from a drive letter and backslash-separated components — for example, C:\userb\test names volume C, directory userb, file test.
• VMS (virtual management system): the volume is identified by a letter — C, for example — followed by a colon. The colon separates the volume from the directory, so the volume name reads like "C:". The directory is written inside square brackets, followed by the name of the file. The arrangement is: volume letter + colon, directory in square brackets, then the file name — for example, C:[users.jdeck]login.com, with users and jdeck being nested directories and login.com the file.
• UNIX: the volume name itself is treated as part of the directory name. The forward slash / is the root from which the file system starts. Under the root we have, say, home, and inside home a folder is created in the name of each user — that folder is also a file — and inside it we can create many subdirectories. This is how the arrangement works in UNIX: the path /home/alice/report.txt names the file without ever mentioning a drive letter.

The session does not go into the commands in depth, but notes that to search for a file we navigate to it and use the ls command to list; other commands give information about a particular file.

15.3 File System Mounting and Virtual File Systems

15.3.1 Mounting and Mount Points

A partition often starts with no information in it. To make it usable we place a file system inside the partition, and for that the file system has to be mounted. Mounting means attaching a file system to an existing volume — that is the whole meaning of the term.

Mounting is a privileged operation: not everyone can do it, only super users can, and the file system has to be checked for correctness before it is attached. The operating system verifies that the device actually contains a valid file system (typically by reading its volume control block / device directory and checking the expected format) before it records the mount in its in-memory mount table. The mount point is the place where the file system gets attached; wherever we attach the file system, that location is called the mount point.

The textbook fills in the mechanics with two examples:

• Windows-style: each volume gets its own name space denoted by a letter and a colon (F:); the system places a pointer to the file system in the device structure for that letter, and any path starting with F: traverses that file system. Newer Windows versions can also mount a file system at any point inside the existing directory structure.
• UNIX-style: a file system can be mounted at any directory. The kernel marks the in-memory inode of that directory with a mount-point flag and points it to an entry in the mount table; the mount table entry holds a pointer to the superblock of the mounted file system. Because the flag lives in the inode, the operating system can traverse the whole directory tree and switch seamlessly among file systems of varying types without the user noticing.

15.3.2 File System Types and the Virtual File System

File systems come in different types. The lecture distinguishes a file-layered file system from a virtual file system (VFS). The example is Linux, which uses a virtual file system.

Why do we need a layer between the user and the file system at all? A modern operating system must support several concrete file systems at once — on a Linux machine, ext4, FAT, NTFS, ISO 9660 for CDs, procfs for process information, and NFS for remote files can all be mounted at the same time. Writing separate directory and file routines for each type would be a maintenance nightmare. The VFS is the object-oriented answer: it defines one uniform interface, and each concrete file system supplies its own implementation behind it.

The Linux VFS works with only four objects, and each object represents a particular entity:

1. an inode object — an individual file,
2. a file object — an open file,
3. a superblock object — an entire file system,
4. a dentry object — an individual directory entry.

Every file in the file system falls into one of these four categories, and the VFS layer lets Linux support many concrete file systems behind one uniform interface.

This is also the layer where a network file system plugs in: NFS rides on top of the VFS, so a remote file looks like just another file type. The three-layer NFS architecture in section 15.6.4 is the same idea made concrete.

15.4 Allocation Methods

15.4.1 Contiguous Allocation and Fragmentation

Once the file system exists, we have to place each file somewhere. If memory is available the file can live there; otherwise we go to the secondary storage device.

The first method is continuous (contiguous) allocation: starting from one block, we allocate blocks continuously — two or three blocks, depending on the size of the file. The file's blocks sit side by side on the disk: if the file is $n$ blocks long and starts at block $b$, it occupies blocks $b,b+1,b+2,\dots ,b+n-1$. The directory entry records the starting block and the length. This is the fastest way to read a file — sequential access rarely moves the head — and direct access to block $i$ is trivial: just read block $b+i$.

Gathering the scattered free pieces means compaction: shuffling all the allocated blocks to one side of the disk and all the free spaces to the other side. Compaction is time-consuming and expensive, so it is not done every time; that is why we look at other allocation methods. The classic textbook picture of the whole problem: contiguous allocation is just the dynamic storage-allocation problem in another disguise, and the familiar first-fit and best-fit strategies for choosing a hole apply — both beat worst-fit, and first-fit is generally the fastest.

15.4.2 Linked Allocation and the File Allocation Table

Linked allocation is easy to picture. For a particular file, the directory entry mentions the starting block and the ending block — only the location (the address) of the first block and the address of the last block are stored. To read the file we follow the link from the first block to the second block, then to the third, until we reach the end. The blocks may be scattered anywhere on the disk: nothing forces them to be neighbors. Linked allocation is somewhat better than contiguous allocation because we are not going to waste any space — no internal fragmentation from partially filled neighbors, no need for compaction.

The costs are real, though:

• Pointer overhead. Every block must reserve space for the pointer (the address) that points to the next block. That space is overhead. The textbook gives the arithmetic: if a block is 512 bytes and a disk address takes 4 bytes, the user sees only 508 bytes of usable space per block — about 0.78% of the disk goes to pointers. The usual remedy is to group blocks into clusters (say, four blocks) and link clusters instead of blocks, so the pointer overhead is spread over more data — at the price of some internal fragmentation inside the last, partially filled cluster.
• Broken links. If one of the pointers gets cut — corrupted for any reason — we cannot find the path to the next block and the rest of the file is lost. There is no way to rebuild the chain from the surviving blocks.
• No efficient direct access. To reach block $i$ we must walk the chain from the start; each hop is a disk read. So linked allocation suits sequential access only.

Real-world: the FAT (file allocation table) is this idea made into a table. Instead of storing a pointer inside every block, a separate table — one entry per block, indexed by block number — holds the chain. The starting block number is given, and by following the table we reach the other blocks till we come to the end: the table entry for block 217 says "next is 618", the entry for 618 says "next is 339", and the entry for 339 holds the end-of-file value. An unused block is marked with a 0 in the table, so allocating a block is a matter of finding the first 0 entry. MS-DOS and OS/2 use FAT. The price: the disk head must travel to the table at the start of the volume to read a chain step, then to the data block — a lot of movement unless the FAT is cached in memory.

There is also a variation of linked allocation: the first block, the one pointed to by the file, holds the indexes of the other blocks where the information is present. We start from the first entry and, following the sequence, we reach and find the information. The drawback of that variation is that one block has to be reserved for the index — a block that could otherwise be useful for any other file. That is the problem with this linked variation.

15.4.3 Indexed Allocation and Multi-Level Indexing

Indexed allocation is familiar from database management: to map from the logical entity to the physical place where the file is present, we allocate some bytes specifically for an index table. One block is allocated for the index table. The index holds the displacements — the addresses of the data blocks — and to read data we first go to the index, then travel from the index entry to the block itself.

The next level is multi-level indexing: two (or more) levels of indexing. The problem of indexed allocation is that the overhead of maintaining the index table itself is larger than the data blocks it describes — the index can cost more space than the file contents. The textbook's example: a file of only one or two blocks still needs a whole index block, and if an index block holds $1,024$ four-byte pointers, two levels of indexes address $1,024^2=1,048,576$ data blocks — files of up to 4 GB with 4 KB blocks. The professor's point stands: the index is a permanent per-file tax, whether the file is tiny or huge.

15.4.4 UNIX Multi-Level Indexing

UNIX combines the levels instead of picking one. The scheme has:

• Direct blocks: direct addresses to data blocks are stored in the file's metadata (the inode), but only a limited number of them — 12 in the classic layout, which covers small files of up to 48 KB with 4 KB blocks without any extra index.
• Single indirect block: after the direct entries, one single indirect block points to an index table, and inside that table are the addresses of the data blocks.
• Double indirect: two levels of indexing — the first level of indexing takes you to the second level, which then points at the data blocks.
• Triple indirect: three levels — we travel through three levels of index tables before reaching the data.

The idea: small files pay almost nothing (direct pointers only), while huge files can still be addressed through the indirect levels. Each level of indirection multiplies the addressable size by the number of pointers per block, so the scheme covers files far beyond what a single index block could address.

Inside a data block the record we want may not sit in the first position; we may have to search through the block to reach a particular record or a group of records. Indexing is key-based: entries are sorted on a key, and the index takes us to the particular data block. Even so, we may still have to travel inside the block — that travel is itself an overhead. The payoff is that we can locate data properly: with indexing the data is kept sorted and in sequence, and that is the advantage of this type of indexed allocation.

15.5 Free Space Management

15.5.1 Bit Vector (Bitmap)

Whenever space is allocated, whatever is left over is tracked in a free space list. The list has to be tracked because the free blocks may later be allocated to a file that needs a block. Different file systems use different concepts for the free space list; the first one discussed is the bit vector or bitmap.

With the help of bits, we can find out which blocks are free and which are allocated. For a list of $n$ blocks, the bitmap is a string of bits such as 1 1 0 0 ... — here 1 means that particular block is free and 0 means that particular block is allocated.

To find a particular block number, the CPU does a small calculation. The professor describes it as: take the number of bits per word, multiply it by the number of zero-valued words (the words scanned so far), and add the offset of the first set bit — that gives the block number. The textbook confirms the same rule verbatim (number of bits per word × number of 0-value words + offset of first 1 bit), so the formula is:

$$\text{block number}=(\text{bits per word})\times (\text{zero-valued words scanned})+(\text{offset of the first set bit})$$

The CPU performs this calculation to find the block number and retrieve the information. The problem: the bitmap itself requires space — we have to store all those bits, one per block.

The lecture works a concrete example. Suppose the block size is 4 KB, which is $2^{12}$ bytes, and the total disk size is $2^{40}$ bytes (1 TB). The number of blocks is:

$$n=\frac{2^{40}}{2^{12}}=2^{28}\text{blocks}$$

The professor then states the storage cost of the bitmap: with $2^{28}$ entries the bitmap takes about 256 MB, and if we combine blocks into clusters of 4 blocks, the bitmap takes about 64 MB. Making the blocks into clusters reduces the space needed for the bitmap to some extent — dividing $2^{28}$ entries by 4 gives $2^{26}$ entries, and $256÷4=64$ MB.

The only problem: we must first find the bitmap, then reach the file — but after reaching the block, the file content is there. The deeper limitation the textbook flags: a bitmap is efficient only if the whole vector fits in main memory (with periodic writes to disk for recovery); on very large disks, a full bitmap can itself be huge (a 1-PB file system would need a 32-GB bitmap), which is exactly the problem ZFS's space maps (§15.5.4) were designed to solve.

15.5.2 Linked List Free List

Another type of free space management is the linked list. The linked list gives us the list of free files and the list of allocated ones. Here, as we said for allocation, there is no wastage of space — but we cannot allocate blocks one after another easily, because we have to travel the whole list to find out how many free blocks there are and which ones have been allocated.

The free list head is stored, and from the head we walk the list: block 2 is free, next 3 is free, next 4, next 5, and again 8 is free — like this. In the textbook's picture, each free block holds a pointer to the next free block, and the head pointer (cached in memory) points to the first one; the pointer inside the last free block ends the chain. The entire list must be traveled every time, and that is the only problem in the linked-list type of free space management.

15.5.3 Grouping and Counting

Grouping improves on the plain linked list. We take a particular block — the first free block, say — and store in it the addresses of the next $n-1$ free blocks. If the first block is free, we take it, and we store how many free blocks there are: counting the first one, the remaining $n-1$ free blocks are recorded, and we also store the pointer to the first free block. Example: if 4 free blocks are there, $4-1=3$, so the addresses of the remaining 3 free blocks are recorded. Like this we can group.

Counting is a second approach: we keep the count of how many free blocks are there and the address of the first free block, and then we can allocate continuously. It exploits the fact that free blocks often come in runs: rather than storing every free address, store an entry of the form (address of first free block, number of contiguous free blocks following it). The professor highlights the difference between the two: in grouping we take the first free block and store the count of the remaining $n-1$ free blocks plus a pointer; in counting we store the address of the first free block and the count of how many free blocks are there, along with addresses. Any of these can be used by the operating system.

15.5.4 Space Maps

The third type, the space map, is mainly used in the ZFS system (Sun's ZFS file system — the "Zeta 5" heard in the recording is the phonetic rendering of ZFS). First we have to consider metadata: everything except the data itself — all information with respect to the input/output — is stored in the file system. Metadata includes the directory structure, the free-space records, and all bookkeeping; the actual file contents are the data. The whole space is divided into many units called metaslabs. Many metaslabs are managed by a particular volume — a volume will have hundreds of metaslabs — and each metaslab has a space map.

The space map uses the counting algorithm we just saw: it records how many free blocks there are and their addresses. Everything related to block activity is recorded in the space map — it is, in the textbook's words, a log of all block activity (allocating and freeing), in time order, in counting format. When we need to know how many free spaces there are and what their addresses are, the space map is loaded into memory and indexed with the help of an offset; then it is checked, and the space is allocated to a particular set of bytes. In ZFS the in-memory structure is a balanced tree indexed by offset, and the log is replayed into that tree; contiguous free blocks are condensed into single entries. That is how the space map works.

The problem: the space map itself occupies some space in memory, and first it is on the disk and later it is taken into memory. Everything has to be managed — even the metaslabs have to be maintained. That is the ZFS trade-off, but it is the scheme used in the ZFS system.

15.6 Network File System (NFS)

15.6.1 The NFS Model: Remote Directories and Mounting

The network file system (NFS) is a type of file system where many workstations are connected: each workstation is an independent machine with an independent file system, and some information is shared among the file systems. When information is shared between the file systems of different machines, a remote directory has to exist, and every machine has its own local file system. The remote directory must be mounted over the local file system — only then can a particular user or machine access the file system that exists elsewhere, on an interconnected workstation.

Two properties follow. First, the information about the remote directory is not transparent: it is not available to every machine by itself. Only a super user can mount it into the local file system; after that, any user at the workstation can use it. Ordinary users cannot mount — mounting is a privileged operation. Second, the remote file system has to be mounted on top of the local directory; the professor stresses that this point is very important.

Why design it this way? Because it works on any type of machine, any type of operating system, any type of architecture — irrespective of all that, NFS can be used. The textbook makes the same point: one of NFS's design goals was to operate in a heterogeneous environment of different machines, operating systems, and network architectures, and that independence is achieved by building everything on RPC primitives over XDR (both described below).

15.6.2 Mount Protocol and File Handles

How does communication take place between one workstation and another? With the help of XDR — external data representation — and the remote procedure call (RPC). The RPC is applied to transfer information between the file systems. In NFS, one side is a client — the local machine that wants the information — and the other is the server — the machine where the information is stored. The only things that have to be mentioned during the operation are the name of the remote directory and the name of the server machine where it is stored.

When a mount is requested, the client first sends a request; the server confirms it and returns a file handle. Only when the file handle is returned can the client proceed. The file handle consists of:

• a file system identifier, and
• an inode.

The inode identifies the mounted directory within the exported one — because the file system comes from the server, an identifier is needed to say where it is exported from and where it is going, and that is what is mentioned in the file handle. The textbook's framing: the file handle contains all the information the server needs to distinguish an individual file it stores — in UNIX terms, a file-system identifier plus an inode number. The server keeps an export list stating which file systems it exports and which machines may mount them (edited only by a super user). We use the NFS protocol for this mounting, together with a set of remote procedure calls. Once the RPC is confirmed between client and server, everything else can happen: searching for a file, reading a set of directories, manipulating or accessing file attributes, reading, and writing.

15.6.3 Stateless Servers and Concurrency Control

The servers in this design are stateless. Stateless means: once the request and response are over, the server keeps no information about the request or about the client. Every time, we must give the full set of arguments again — the file identifier, the position inside the file, the data — with every request. There are some versions that are stateful — they remember the client, so the full information need not be given again — but the stateless model is the core one.

One thing to note: NFS does not provide any concurrency control mechanism. Concurrency means more than one user trying to operate on a particular file. If the users are only reading the file, it is okay. But if two or three workstations have two different users trying to access a particular file on some other workstation and trying to manipulate it, there is no concurrency control in NFS to coordinate them.

15.6.4 NFS Architecture: Three Layers, XDR, and RPC

Based on the architecture, NFS has three layers:

1. the VFS interface — the top layer,
2. the file system interface layer — the middle layer,
3. the service layer — the bottom layer.

The file system interface carries out the system calls — open, read, write — and works out which calls are local and which are remote. The client sits on one side, the server on the other, and the network lies between them. When a system call such as open is made, the VFS first tries to find out whether the target is in the local file system. If it is local, the data is taken from the disk and given back. If it is not in the local file system but represents some other type of file system that exists on the same system, the information is taken from that same system. Otherwise the file is treated as NFS: the VFS acts as a network file system client and makes an RPC.

The data being sent as a request is not understandable by the server, so it has to be converted into a common representation — that is what XDR, the external data representation, is for. Through XDR and the RPC, the information is sent to the server, and when it arrives it is unpacked so that the particular server can understand it. The NFS on the other side acts as a server: it takes the information, finds it in its local file system, and gives it back. The response comes back through the same path — it is packed on the server side and unpacked on the client side. That is how NFS works end to end.

The professor connects this to Java: in Java we used to call the two sides of an RPC the stub and the skeleton — the stub is the client side and the skeleton is the server side.

15.6.5 Path Name Resolution in NFS

We should know how to resolve a path name — this is with respect to the UNIX file system, where the path starts with a slash /, the root. First we have to find whether it is the root directory; if it is the root, we find the next name that is present; the directory entries are separated with the help of the front slash. This is how we break up and translate the path name when we perform a lookup operation in the network file system.

We first have to reach the mount point: after the root we go to "user", and there the mount point sits. From that place we have to find where "local" is present. For each component, we take the component out, check the name, and find out where it is present. Because this is a network file system, each of these lookups requires an RPC: as many RPCs as the number of directories or subdirectories used in the path. That makes path translation a very expensive scheme. If, once we find one thing, we can find all the other subdirectories easily, the scheme becomes somewhat efficient. And if the server keeps no state, it is another burden: all these translations have to be repeated every time a request comes from any client to the server.

NFS follows the paradigm of the remote service. There is no direct correspondence between the remote operation and the RPC — every time, with the help of the RPC, we have to find out that file block and the file attributes. One practical remedy: if we are going to use the same file again, we can keep it locally — if it is kept locally, there is no need to go for the remote operation every time and no need to make an RPC every time. The client-side directory-name-lookup cache does exactly this: it remembers the vnodes for recently resolved remote directory names, so a repeated reference to the same initial path portion hits the cache instead of the network. The cache is discarded when the server's attributes no longer match the cached entry.

15.6.6 Caching: Attribute Cache, Read-Ahead, and Delayed Write

To cache information, we can use either a file attribute type of cache or a file block cache. When we try to open a particular file, we check with the remote server — where the file is present — whether the attributes are proper. Only after checking the attributes can the file blocks be used. That means the file attribute has to be up to date, so it has to be updated regularly: after every 60 seconds, whatever has been cached is rechecked, and the new attribute is updated if we try to use the file. This 60-second timeout is the standard NFS attribute-cache behaviour: cached attributes are, by default, discarded after 60 seconds, and the cached file blocks are trusted only while the cached attributes are current.

For the actual transfer we can use read-ahead and delayed write techniques. Delayed write means the update is not performed as soon as every change happens: after making a set of changes, after a period of time, the system checks whether the data is up to date; if it is not, whatever has been updated so far on the disk is reflected in the file attribute cache. This is how remote file operations can be performed easily with the help of these caches.

Beyond NFS, the textbook works through two example file systems in detail: the virtual file system (VFS), which we already saw in section 15.3, and one more whose name came through the source unclearly — it is the WAFL (write-anywhere file layout) file system from Network Appliance, a file system optimized for network file servers, best known for its snapshots. (The name heard in the recording resolves to WAFL; the same design family also includes log-structured ideas, but the textbook's second worked example is WAFL.)

15.6.7 Student Q&A: RPC in Industry Practice

The professor's answer makes the course-agnostic point: RPC is a general mechanism, not a language feature. The student's example is exactly how RPC is used today — cloud development platforms use RPC (for example in Golang services) as a communication mechanism that practitioners often find more secure than plain HTTP — but the underlying idea (call a function that executes on a remote machine, with the stub on your side and the skeleton on the other) is the same one NFS uses and the same one Java's RMI illustrates.

15.7 Mass Storage: Magnetic Disk Fundamentals

15.7.1 Magnetic Disk Anatomy and Terminology

Magnetic disk is a form of secondary storage — we already know the difference between primary and secondary storage (primary = main memory, fast and volatile; secondary = persistent storage, slow and cheap). The lecture focuses on the magnetic disk because most of the remaining material is about it; magnetic tape gets an overview only.

The anatomy of a disk drive: we have an arm assembly with many disks combined together with the help of a spindle — the center piece. The spindle rotates, and the rotation makes the tracks move and lets the arm find the desired sector within the tracks. Each arm is attached to each disk, on both ends, because both surfaces of every disk are readable — a drive with $k$ platters carries $2k$ read-write heads, one per surface. On each surface we have many concentric circles, and the concentric circles are called tracks. Interconnecting each circle with the corresponding circle on every other disk forms a cylinder.

       ____ side view:    |   platter 1 (surfaces 0,1)  |
                          |   platter 2 (surfaces 2,3)  |    <- spindle through the center
                          |   platter 3 (surfaces 4,5)  |
       arm moves all heads together; heads at the same
       radius on every surface -> one imaginary cylinder

Moving from the inner track to the outer track, the number of sectors increases — each track is divided into sectors, and outer tracks hold more sectors than inner tracks. The bit density moves the other way: the density of bits per track is higher in the inner zone and lower in the outer zone. That is the difference. (The mechanism behind it is the topic of §15.10.2 — CAV vs CLV.)

15.7.2 Seek Time, Rotational Latency, and Access Time

Two times dominate disk performance. Seek time is the time taken to move the disk arm to the desired cylinder (track). Because the disk is rotating, the desired block — inside a sector, inside a track — may not be under the head yet; rotational latency is the time taken for the disk to rotate until the head is placed on the desired sector. These two together give the random access time — the time taken to find the block.

Apart from these, some other overheads exist (transfer time and controller overhead — both measured in the worked example of §15.8). The drives attach to the system through different I/O buses — Fibre Channel, SCSI, and the like. Every system has a host controller, which communicates with the disk controller present in each and every disk: through the host controller, the communication happens with the system; through the disk controller, the communication happens with the disk. (The three attachment schemes of §15.10 are built on these buses.)

15.7.3 Disk Performance Metrics

Common performance metrics apply to any type of disk:

• Transfer rate — the rate of flow of data between the system and the drive. Theoretically this is about 6 GB per second as stated in the source; in this lecture's convention "GB" in that phrase means gigabits per second (the same convention used in the §15.8 worked example, where 1 Gbps is given). Read as 6 Gbps — roughly the interface speed of a modern SATA link — while real sustained data rates are lower because the head must actually read the bits. (Interface speeds such as 6 Gbps are bus limits; effective transfer rates are media-limited and smaller.)
• Positioning time / random access time — the time taken to find the block, made of seek time plus rotational latency.

Several formulas go with these metrics. The average seek time can be measured with the help of one third of the number of tracks:

$$t_{\text{avg seek}}\approx \frac{1}{3}\times (\text{number of tracks})$$

The reasoning: if a request can be anywhere and the head starts anywhere, the expected distance is about one third of the full travel — the maximum seek divided by three. It is a rule-of-thumb estimate, not a physical law; manufacturers quote measured average seek times (typically under 10 ms on modern disks).

The latency — the time for one full rotation — depends on the spindle speed, given in rotations per minute (RPM). Converting minutes to seconds:

$$T_{\text{rotation}}=\frac{1}{\text{RPM}/60}=\frac{60}{\text{RPM}}\text{seconds}$$

Half of that latency gives the average latency (average rotational delay):

$$t_{\text{avg latency}}=\frac{1}{2}\times T_{\text{rotation}}$$

Why half? The desired sector can be anywhere around the circle when we arrive; on average it is halfway around, so the average wait is half a revolution.

The random access time (the lecture warns it should not be called "average access time" when a specific transfer is meant) is:

$$t_{\text{access}}=t_{\text{avg seek}}+t_{\text{avg latency}}$$

For the fastest disks the seek can be at most about 5 milliseconds; slower disks take longer. If the problem gives you some information and asks for the random access time, combine these pieces.

Throughput is the number of input/output operations per second multiplied by the transfer size:

$$\text{throughput}=(\text{I/O operations per second})\times (\text{transfer size})$$

If the throughput is given, fine; if it is not required, leave it. To find the average I/O time:

$$t_{\text{avg I/O}}=t_{\text{access}}+\frac{\text{amount to transfer}}{\text{transfer rate}}+t_{\text{controller overhead}}$$

The controller overhead is the host controller overhead or the disk controller overhead — in a disk-transfer problem it would be given. Note the structure: the I/O time is the positioning time (seek + latency) plus the data movement time (transfer) plus the electronics time (controller overhead). The textbook's equivalent formulation is $T_a=T_s+\frac{1}{2r}+\frac{b}{rN}$, where $r$ is rotations per second and $N$ is bytes per track — the same three ingredients.

If the data transfer rate is not given, it can be computed. The professor's formula: the transfer rate is the number of heads times the capacity of one track times the number of rotations per second:

$$\text{transfer rate}=(\text{number of heads})\times (\text{capacity of one track})\times (\text{rotations per second})$$

If values are in minutes, convert to seconds — whatever is required, we do that. And the capacity of one track comes from the number of sectors per track and the number of bytes per sector:

$$\text{capacity of one track}=(\text{sectors per track})\times (\text{bytes per sector})$$

So: with the number of sectors per track and bytes per sector, find the track capacity; with track capacity, the number of heads, and the rotations per second, find the transfer rate. These are all small pieces that a question can ask for.

15.7.4 Hard Disk Specifications

Hard disks come in known specifications. The platter diameter (the diameter of one full circle of the disk) can vary from 0.85 inches to 14 inches; the commonly used ones are 3.5, 2.5, and 1.8 inches. The space per drive starts from 30 GB and goes to 3 TB, and now it is more (the "3 dB" heard in the recording reads as 3 TB). The spindle speeds — the rotations per minute — have some typical values, which are mentioned in a table: 4,200 RPM, 5,400 RPM, and so on. Depending on the speed, the vendor mentions the RPM of the spindle and sometimes the transfer rate, and we have to find the seek time or the latency ourselves.

For the common RPM values, remember the small table — the lecture gives one value as an example: for 7200 RPM, the average latency is 4.17 ms. Check it with the formula: $60/7200=8.33$ ms per rotation, half of that is 4.17 ms — the formula and the table agree. The table has only about five values, and it makes problems faster. If the rotation time is given directly, apply the half formula; otherwise assume the values from the table. That is all there is to it.

The source also mentions historical information about the first commercial disk drive: when it was invented and by whom, how many characters it can store, what the diameter of the platter was, and what the access time was. These facts are on the slides and are worth knowing as background — the key takeaway is how far the technology has come from that first drive to today's multi-terabyte drives.

15.8 Hard Disk Performance: Worked Example

15.8.1 Problem Setup and Given Values

The lecture works a complete problem: transferring a 4 KB block. The given values are:

• block to transfer: 4 KB,
• spindle speed: 7200 RPM,
• average seek time: 5 ms (given),
• transfer rate: 1 Gbps (given — the professor explicitly notes that GB here is gigabits per second, and the block size is in kilobytes, so we multiply by 8),
• controller overhead: 0.1 ms (given).

We have to find the average access time.

The professor sets up the formula: the average access time is the average seek time plus the average latency. Written elaborately, it is the average seek time plus the average rotational delay — the lecture notes both names mean the same thing — plus the other factors, namely the transfer time and the controller overhead. So:

$$t_{\text{access}}=t_{\text{avg seek}}+t_{\text{transfer}}+t_{\text{avg latency}}+t_{\text{controller overhead}}$$

The structure is the same one from §15.7: positioning time (seek + latency) plus data movement (transfer) plus electronics (controller overhead).

15.8.2 Transfer Time Computation

First we need the transfer time. The transfer time is the size of the block divided by the transfer rate:

$$t_{\text{transfer}}=\frac{\text{block size}}{\text{transfer rate}}$$

The units need care — and the professor calls this step very important. The block size is in kilobytes (bytes), while the transfer rate is in gigabits per second (bits), so:

1. Multiply the block size by 8 to convert bytes to bits: $4\text{KB}\times 8=32\text{Kbit}$.
2. Convert the rate to the same unit: from giga we go to mega, and from mega to kilo, multiplying by 1024 each time — $1\text{Gbit}=1024\times 1024\text{Kbit}$.

Putting it together:

$$t_{\text{transfer}}=\frac{4\times 8}{1024\times 1024}\text{seconds}\approx 3.05\times 10^{-5}\text{seconds}\approx 0.031\text{ms}$$

15.8.3 Average Rotational Latency

The average latency, or average rotational delay, is half of the latency, and the latency is the time taken to make one full rotation:

$$t_{\text{avg latency}}=\frac{1}{2}\times T_{\text{rotation}}$$

For 7200 RPM:

$$T_{\text{rotation}}=\frac{60}{7200}\text{s}=0.00833\text{s}=8.33\text{ms}$$

$$t_{\text{avg latency}}=\frac{1}{2}\times 8.33\text{ms}=4.17\text{ms}$$

which is the table value for 7200 RPM from §15.7.4. If the time for one full rotation is given in the problem, apply the formula directly; if not, take the value from the table for the five common RPM values.

15.8.4 Final Average Access Time

Now put every piece into the formula:

$$t_{\text{access}}=5\text{ms}+0.031\text{ms}+4.17\text{ms}+0.1\text{ms}=9.301\text{ms}$$

The average access time for transferring the 4 KB block is 9.301 ms.

The class is asked whether there is any doubt about the computation; there is none, and the professor repeats the useful summary: average rotational delay is half of the latency, latency is the time for one full rotation, and if the data is not given, assume the values from the table.

15.9 Solid-State Drives and Magnetic Tape

15.9.1 Solid-State Drives (SSDs)

After the first commercial disk drives came solid-state drives (SSDs). Their advantages: they are reliable, and they are non-volatile — even if the power is switched off, the information is still there. The problem: even for a small SSD you have to pay more; the capacity is smaller for the price, but it is faster. In some systems the operating system itself is loaded from an SSD.

Real-world: SSD boot drives are standard in modern systems precisely because the OS loads faster without seek time and rotational latency. The trade-off the professor states is the enduring one — price per gigabyte is higher and capacity per drive is smaller for the same money — which is why big storage pools still mix media: an SSD for the hot, frequently-read data (the OS, active files) and magnetic disks for bulk storage.

15.9.2 Magnetic Tape

Magnetic tape is very old — it was the first secondary storage medium. It evolved from open reels to cartridges, and it is capable of holding a large quantity of data; it is also permanent. The problem is the time taken to access the information: the professor states it is about a thousand times slower than the disk — "thousand times less" — so imagine how slow that is. In order to speed up operations, the industry went for magnetic disks and solid-state types instead.

Real-world: tape remains the standard medium for long-term backup archives, where cost per terabyte matters more than access speed. The professor's cost ladder runs the other way from the performance ladder: RAM is fastest and most expensive, SSDs next, hard disks after, and tape cheapest per byte — so the industry allocates data by how often it is touched, exactly the principle behind backup tiers that spill cold data onto tape.

15.10 Disk Structure and Disk Attachment

15.10.1 Logical Disk Structure: Blocks, Sectors, Cylinders

Think of a disk drive as a one-dimensional array. In that array, each element is a logical block — the smallest unit of data transfer (usually 512 bytes, sometimes 1,024). Whenever a disk is formatted, these blocks are created. The blocks are mapped to sectors sequentially: this block after that block, each belonging to one particular sector. Sector zero is the first sector of the first track of the outermost cylinder. From there the mapping proceeds: we can move through the other tracks of that cylinder, then from cylinder to cylinder, from the outermost cylinder to the innermost cylinder — that is how the logical blocks are traversed.

15.10.2 Constant Angular Velocity and Constant Linear Velocity

The number of sectors per track is tied to the disk's rotation scheme. Constant angular velocity (CAV) means the number of sectors per track is uniform — every track holds the same number of sectors. Constant linear velocity (CLV) describes the bits: if the number of bits per track is uniform, we call that constant linear velocity. So: uniform sectors per track → constant angular velocity; uniform bits per track → constant linear velocity.

15.10.3 Host Attached Storage

Disk attachment comes in three types. The first is host attached storage — storage that is like local storage, present in each and every system, connected through the I/O buses. We can have up to 16 devices on one cable. Each target SCSI device performs up to eight logical units — the blocks it serves. The architecture for sending and receiving information is done with the help of Fibre Channel; one variant is the arbitrated Fibre Channel. The address space that can be fabricated is a 24-bit address space, and this is the basis for the other storage area networks. When the host sends an I/O, the request is directed to the bus ID, the device ID, and the logical unit — everything has to be mentioned.

15.10.4 Storage Area Networks (SAN)

The second type is the storage area network (SAN). Picture a storage array — an array of disks, thousands of disks. Each array has a controller, which helps to attach the array to a particular host or to the disks, and the ports are connected to the host with the help of the arrays; there is memory as well. When very large information has to be stored, we go for a storage area network. In the local system these storage areas are just storage present in the same system, but when connected to the network, the storage area can serve the other systems that are connected through a LAN or a WAN. A client that needs space makes a request, gets some space, and uses it.

Real-world: Google Drive can be taken as a storage area network — we, as clients, make a request to have some space and use it; the service acts as a storage array storing information. In such a setup, separate data processing centers or web content providers are also attached into the network, and multiple hosts can attach to the storage array with the help of the storage area network.

15.10.5 Network Attached Storage (NAS)

The third type is network attached storage (NAS). It is another type of storage system, but it is not a local connection — it is a network. We remotely attach our system to another file system, and we can use either the network file system (NFS) or the CIFS file system — the common protocols file system, as the source phrases it. The standard expansion of the acronym: CIFS = Common Internet File System, the file-sharing protocol used by Windows machines (the professor's "common protocols file system" is the same thing in plain words). The implementation again takes place with the help of RPC, and the protocol that is followed can be either TCP or UDP.

Different products exist today — Synology and many more are examples of network attached storage. If we compare Synology with Google Drive: Synology is mainly used for smaller systems, or medium- or larger-sized systems to be stored; Google is capable of any type of system. The NAS is connected to the client either through the LAN or in the way we attach it. Remember: using RPC only, we have to implement this network attached storage — the client makes a request, then it takes the available space in the network for its purpose.

These are the three different types of attachment with respect to the disk. Disk scheduling and disk management come in the next session.

15.10.6 Student Q&A: The Comprehensive Exam

The professor's message is a study plan in one paragraph: rework the solved problems — deadlocks, paging and segmentation, disk performance, disk scheduling, CPU scheduling — because the exam problems will be similar in type, and spend less effort memorizing deep theory detail, because theory questions ask for less. Disk scheduling is called out as easier than CPU scheduling, so it is the safest place to pick up marks.

Exam Guidance Summary

The session's exam guidance, collected in one place:

• The comprehensive exam contains both problems and theory. Expect problem types similar to those practiced in class — the best preparation is reworking the solved problems.
• Problem topics to practice: deadlocks, memory management (paging and segmentation), hard disk performance, disk scheduling, and CPU scheduling. Disk scheduling is somewhat easier than CPU scheduling.
• Theory questions appear, but the detail level asked for theory is always less than for problems.
• Expect one question on disk performance. Master the formulas:
• average seek time ≈ one third of the number of tracks;
• rotation time = $60/\text{RPM}$ seconds;
• average latency = half of the rotation time;
• random access time = average seek time + average latency;
• throughput = I/O operations per second × transfer size;
• average I/O time = average access time + transfer amount ÷ transfer rate + controller overhead;
• transfer rate = heads × track capacity × rotations per second;
• track capacity = sectors per track × bytes per sector.
• For latency, either use the formula (half of the full rotation time) or read the average latency for the five common RPM values from the table — for 7200 RPM it is 4.17 ms.
• In transfer-time problems, convert bytes to bits by multiplying by 8, and convert between giga, mega, and kilo using 1024 factors. In the worked example the 4 KB block gave a transfer time of 0.031 ms and a final average access time of 9.301 ms.
• For the bitmap, be ready for small computations such as $n=2^{40}/2^{12}=2^{28}$ blocks, and know that 1 means free and 0 means allocated in a bitmap.

Key Industry Applications

• Google Drive as a storage area network: clients request space from a storage array over the network, and the service acts as the array storing the information — the SAN model (§15.10.4) in consumer form.
• Synology and similar appliances as NAS: network attached storage for small to medium and larger systems, implemented over RPC with TCP or UDP, using NFS or CIFS — the SAN/NAS comparison (§15.10.5) in hardware form.
• FAT in real file systems: the file allocation table is the linked-allocation idea made practical (MS-DOS, OS/2): the starting block number is stored and blocks are followed to the end through the table (§15.4.2).
• Linux's virtual file system: four object types (inode, file, superblock, dentry) let many concrete file systems share one interface — the reason a single Linux machine can mount ext4, FAT, NTFS, ISO 9660, and NFS side by side (§15.3.2).
• NFS in practice: workstations with independent file systems share directories; mounting is a super-user operation and the mount is placed on top of the local directory; the stateless server model keeps crash recovery simple (§15.6).
• RPC in modern cloud development: used for example in Golang services, where practitioners often find it more secure than plain HTTP; Java expresses RPC as a client-side stub and a server-side skeleton — the professor's bridge from the lecture to the industry (§15.6.7).
• SSD boot drives: SSDs have no seek time and no rotational latency, which is why operating systems are typically loaded from an SSD for faster boot (§15.9.1).
• Magnetic tape for archives: tape remains the cheap, permanent medium for backups and infrequent data, even though access is about a thousand times slower than disk (§15.9.2).
• ZFS space maps: Sun's ZFS manages enormous file systems by dividing space into metaslabs, each tracked by a space map in counting format — the industry answer to bitmap scalability (§15.5.4).
• Fibre Channel SANs: the 24-bit address space of the switched-fabric Fibre Channel variant is the basis of storage area networks, letting multiple hosts and storage arrays share one flexible fabric (§15.10.3–15.10.4).