File Systems

14.1 Files and the Scope of This Topic

14.1.1 Where We Are Going

This session covers the file systems of the operating system: how the OS manages them, what the structure of the disk directory is, how file mounting is done, how the file system is implemented on the directory, and what the different allocation methods are that the OS uses to store files. If one or two topics are left out, they continue in the next session. After that comes the mass storage structure: the secondary storage devices and the performance of the disk. At the end comes disk management, that is, disk scheduling and all those things. With that, the scope of the unit is complete.

14.1.2 What a File Is

Everyone already deals with files on their own operating system. In Windows you have a drive, and inside that drive you create as many folders as you want, and each folder holds some files. But what exactly is a file, and how does the operating system keep track of all of them?

Some properties exist for every folder we create, and on Unix or Linux even the directory itself is treated as a file. Every such file is identified by an inode (an index node): on Unix or Linux the file is always identified in the form of an inode. The inode is a control structure that carries the key information the operating system needs for that file — its attributes, permissions, and the location of its contents. Windows has the same idea under a different name: in NTFS each file has a unique ID called a file reference, a 64-bit value made of a 48-bit file number plus a 16-bit sequence number, and the file's record lives as an entry in the master file table (MFT). So the identifier concept is universal; the names differ per system.

The operating system maps files to particular devices. These devices are usually non-volatile: even if you switch the system off, or something happens to the system and you come back later, the data can be recovered. That is the property of the devices attached to the system, the secondary storage type, as opposed to main memory or primary storage. Main memory loses everything when power goes away; the secondary storage devices keep their contents. Storage structure is discussed in the next session; here the focus is files alone.

A file is a collection of information, so we give each file a name based on the type of information it holds. Consider the logical address space: as seen previously, the address generated by the CPU is called the logical address. The space in which a file is stored is usually contiguous. A file can hold different types of data — numeric data, characters, or a binary file — and even a program, since anything can be stored in the form of a file.

14.1.3 File Attributes

Whenever a file is created, the name we give it should be in a human-readable form. Beyond the name, a file has a set of attributes — the properties the operating system records about the file:

• Identifier — a unique tag assigned by the operating system within the file system; the inode in Linux is the example, and Windows also has an identifier of its own (the file reference in the MFT).
• Type — what kind of file it is: whether it is a .png file, a .txt file, a PDF, an image, an audio, or a video file, and whether the operating system supports that type.
• Location — where the file is present in the system: a pointer to the device and the position of the file on that device.
• Size — the current size of the file, in bytes, words, or blocks, and sometimes its maximum allowed size.
• Protection — who may read, write, or execute it: the access-control information of the file.
• Time and identification — when it was created, the user identification, and the dates and times. These are kept mainly for protection, security, and monitoring of the usage of the file.

All of this information about the files lives in the directory structure. The directory structure itself sits under a particular disk, and it is identified with a name and an identifier. A directory's attributes are much the same, except for one detail: because a directory is not a single file but holds any number of files, its size is greater than one block — a directory entry alone can take more than a kilobyte to record (name plus identifier plus attributes), so a directory that holds thousands of files can grow to megabytes. In other words, the directory is itself a stored structure on the disk, and its size reflects the number of entries inside it.

14.2 File Operations and Open Files

14.2.1 The File as an Abstract Type

A file is an abstract type: it becomes concrete only when we perform operations on it. Creating a file simply, on Unix, is done with the command touch — touch somefile creates a file with that name and nothing else; it has no information or content yet, so it stays abstract. To make a file real, you create it properly with the help of an editor and put some contents into it. That distinction — abstract empty creation versus concrete, content-filled creation — is the starting point for all file operations.

14.2.2 Creating, Writing, Reading, and Repositioning

The operations every file system supports, in order of use:

1. Create — make a new file (the touch case above). Two steps are needed: find space in the file system for the file, and make an entry for the new file in the directory.
2. Write — write some information into the file; a pointer specifies the location where the write happens. After each write the pointer moves to the end of the newly written data.
3. Read — read the contents with the help of a pointer. The read pointer marks where the next read begins, and it advances after each read.
4. Reposition — change the current position within the file: from the start, or from the current position, wherever it is — the middle or the end. This operation is also called a seek; it moves the current-file-position pointer without any actual I/O.
5. Delete — when a file is deleted, the space occupied by the file becomes free and is placed into the pool of free space.
6. Truncate — remove the data inside the file.

14.2.3 Deleting versus Truncating

Truncating and deleting are totally different. Truncation deletes the data present inside the file but keeps the file itself. Deletion removes the whole thing: the file, the data inside it, and the space it occupied — everything is deleted. This is a common point of confusion, so keep the two apart: truncate clears contents, delete removes the file entirely.

14.2.4 Opening Files: Handles, Descriptors, and Open File Tables

To access a file you must open it. When the open succeeds, the OS returns a file handle, called a file descriptor on Unix or Linux. With that descriptor you can perform any operation you need, and you use the same descriptor to close the file.

Why open at all? Most file operations begin by searching the directory for the file's entry. If every read and write did that search, the system would waste enormous time. So the OS copies the directory entry into an in-memory table at open time, and all later operations use an index into that table instead of searching the directory again.

Closing matters because of reference counting. When a file is opened, the process opening it has its information tracked in the file open count — a counter of how many times the file is opened. Only when a process (or group of processes) closes the file does the count get decremented; when it reaches zero, the entry is removed from the open file table. If you never closed files, the reference count would keep the entry alive even after all processes finished, and the entry would occupy memory unnecessarily.

There are two tables in play. The global (system-wide) open file table holds information about all the files opened by the group of processes. Each process additionally has a per-process open file table that holds the pertinent information for that process plus a pointer to the entry in the global table. The per-process table carries the current file position pointer — the location of the next read or write — and the access rights: whether the process has read, write, execute, or append permission for that file. The per-process pointer is how each process's information is kept updated in the global table.

14.2.5 File Locking

Not everyone can access a particular file at the same time. Access can be shared or exclusive. When a file is locked, sometimes the access is denied — that case is mandatory locking: the request stays denied until the holder is forced to release the lock, and a request for the locks to be released has to be made. In advisory locking, the file system does not force anything: the requester can see the status of the lock and proceed anyway. So mandatory locking denies access outright; advisory locking just informs.

14.2.6 Worked Example: From touch to a Real File

14.3 File Types and File Structure

14.3.1 Identifying File Types by Extension

Most operating systems recognize different types of files, and the way we identify the file type is with the extension. The extension follows the file name and tells the system what kind of file it is:

• Higher-level language source: extension based on the language name — .c, .cpp, .java.
• Word-processing document: .doc.
• PowerPoint presentation: .ppt.
• Audio or video: .mp3, .mp4, and so on.

Most file systems support whatever type is needed. When something gets modified in the source, it must be recompiled and then executed; the extension tells you which language and which toolchain applies.

14.3.2 Magic Numbers and Platform Behavior

On macOS, double-clicking a file does everything for you: the OS looks at the file's type attribute and opens the file name with the appropriate application automatically. On Unix there is (historically) a magic number: a value stored in the file at the first byte, which indicates what type of file it is. This magic-number mechanism has since been removed. It is the same idea that still shows up on the internet, where file types must be recognized from the content itself.

14.3.3 Common File Types and Extensions

The catalog of file types and their usual extensions:

With a multi-period (multi-extension) file, the extension can be .mov, .rm, or .mp3 — reading the extension tells you what kind of media it is.

14.3.4 Unix File Structure and Internal Fragmentation

Taking the Unix file system as the example: Unix supports different types of files — a directory, an executable — and everything is identified as a file. All files are stored as a string of bytes. With an editor you create the file, and the file is stored on the disk as fixed-size blocks. Because of this, when the file size is smaller than the block, the remaining space in the block is wasted — that is the internal fragmentation we have seen before, and it is always there in a block-based file system.

14.4 File Access Methods

There are different ways to access the contents of a file: sequential access, direct access, and indexed access.

14.4.1 Sequential Access

Sequential access is the method used in magnetic-tape file systems. We read each and every track and sector in order to reach the file we need. If we have to read or write from the current position, we still have to pass through everything before it — we always go through once from the beginning. The time taken to pass through the remaining space is wasted, so execution time is higher. The implementation is simple: read the next record, then the next, one by one.

14.4.2 Direct Access

Direct access is random access. With a block number $n$ we can go straight to block $n$: read the information from the block, or write information into it, or position to that block and continue with the next position from there. No passing through intermediate blocks — we read block $n$ directly and then move on. This removes the wasted traversal of sequential access.

14.4.3 Indexed Access

Indexed access (also called related-file access) keeps a separate index file. The index file has a key that identifies each and every record, and a value — in the sense of an address — that takes you to the particular location where the record's information is present. The disadvantage is the overhead: the index file itself occupies some space, and the remaining space holds the records or files in the system. Also there are two accesses instead of one — first access the index file, then, based on that, access the record — so the time taken is doubled.

14.5 Disk Partitions, Volumes, and File System Types

14.5.1 Partitions, Raw Disks, and Volumes

The disk is the main place where our files and file systems live. A whole disk is divided into partitions, and each partition may carry a particular file system. If a partition exists but no file system has been loaded into it — the partition has simply been formatted, or not even that — then the disk or partition is raw. So: a raw disk or partition is one with no file system in it. A partition can be thought of as a mini disk; you can think of the disk as cut into slices. Each slice can hold a file system.

In Windows a partition is called a volume. A volume is an entity present in the file system: each volume that has a file system also keeps track of information in a directory, or table of contents, about the files present in that file system. With two partitions you may have two different file systems with two different contents, each with its own table of contents in its own directory. Beyond these there are general-purpose and special-purpose file systems — no need to worry about those in detail.

14.5.2 Spreading a File System Across Disks

The same idea works the other way around. Take the whole disk and divide it into two partitions — or better, take one file system and two disks: the same file may be stored across the two disks, with a single directory/table of contents covering the whole thing. Both arrangements are possible: several file systems on one disk, or one file system spanning several disks.

14.5.3 Named File System Types and Their Purposes

File types and file system types are different things. On one system you can partition the disk: in one partition have the Windows file system, in another the Unix file system. The named file system types covered here:

• tmpfs — temporary file system.
• objfs — an object-based (virtual) file system.
• cdfs — a virtual file system that contains contract information.
• lofs — loopback file system.
• procfs — gives information about all the processes present in the system.

Each type of file system has its own purpose.

14.6 Directory Overview and Operations

14.6.1 What a Directory Is

The directory is like a simple table. In system software you have heard of the symbol table: the symbolic operands, along with their values and addresses, are stored in the symbol table. Imagine the directory the same way — it holds the file names and the location where each file is present. The directory can be organized in different ways — that is not a problem, the system takes care of it.

14.6.2 Directory Operations

Whatever the file system, the directory supports a standard set of operations:

• Search for a file.
• Create a file (or directory) entry.
• Delete a file (or directory) entry.
• List the directories: go inside and check the subdirectories or files.
• Rename a file or directory.
• Traverse the directory structure.

With respect to Windows you can do creating, deleting, and so on by clicking; on Unix you just type a command and it is done. Typing commands is somewhat easier once you are used to it.

14.6.3 What Directory Organization Must Provide

Whatever the directory organization, it should provide:

• Efficiency and convenience — it should be convenient for the users; if I click, I should get my files.
• Naming without conflict — the system should not allow two different files with the same name to coexist where that would conflict. But when two different users share the system (in a network, for example), the users should be allowed to use the same name for their own files — each user's files are different even though the names match.
• Grouping — the user should be able to group files logically: all the Java programs in one folder, all games in a separate folder, arranged as the user wishes.
• Locating files — being able to locate a file is very important; click and get it, and everything is easier.

14.6.4 Student Questions and Answers

14.7 Directory Structures

There are several directory structures, in increasing order of capability: single level, two level, three level, tree level, acyclic graph, and general graph.

14.7.1 Single-Level Directory

In the single-level structure, a directory is directly linked to its files: go into the directory and the files are right there. There are no multiple levels to pass through in order to reach a file. The efficiency is direct — click the directory and get the files. The disadvantage is the flip side of that simplicity: if something happens to this particular directory — it gets corrupted, or wrongly deleted — then the files become inaccessible. That is the single-level risk: one directory, and losing it loses access to its files.

14.7.2 Two-Level Directory

The two-level structure introduces two levels of indirection. At the top is the master file directory (MFD), which has an entry for every user; each user has their own directory, the user file directory (UFD), which is the next level, and through the UFD the user accesses their files.

The advantages: each user has their own space (partition) and can store their own files; and two users can use the same file name without conflicting — the same name in two different users' spaces is fine. A failure in one user's directory does not affect the next user.

The disadvantage: coordination. When users work together in a company as a group, they need some common file or directory shared between them, and that facility is not there in the two-level structure. User isolation comes at the price of no sharing, and no coordination among the users working in an organization.

14.7.3 Three-Level Directory and Path Notation

To represent a file present in a particular directory, the OS maintains a path. Usually each and every directory of the file is separated by a slash — that is the Unix convention. VMS, by contrast, uses a letter for the volume and square brackets for the directory specification. In VMS the volume is an entity that contains the directory information: a volume letter, then square brackets holding the directory and subdirectory names — for example a directory SST with a subdirectory JDAC, the two separated by a dot — and after the brackets the file name. So the VMS path shape is volume letter + [directory.subdirectory]filename.

14.7.4 Tree-Level Directory

The tree-level directory is a tree: the root at the top, the files at the bottom. The root is divided into many directories, under which are many subdirectories. Subdirectories may hold files directly, or point to another subdirectory, which in turn points to another — many levels. The directories in the middle are the internal nodes; where the structure ends and the files live are the leaves. The tree ends at different places — some branches end early, some go deep — so there are different levels present in one tree.

We can create a directory inside a directory, hold files inside a directory, and put another directory inside that with its own files. This is the structure in Unix systems.

14.7.5 Worked Example: Unix Commands for Files and Directories

Creating files has many ways:

14.7.6 Acyclic Graph Directory

The acyclic graph is a graph structure that will not create any cycle — the name says it: acyclic, no cycle. Some nodes are connected to each other, but no connection forms a cycle. The advantage is sharing: two users working in two different directories can point to the same file, just pointing to a particular location. When one user updates the file, the other also gets the updated content, because it is the same file.

The flip side: if one user deletes the file, the other may no longer be able to access it — the pointer becomes a dangling pointer. That problem exists in the acyclic graph and should not be allowed to happen.

Naming flexibility also improves: inside one directory you cannot have two subdirectories with the same name, but in two different directories you can have subdirectories with the same name — that is allowed here.

14.7.7 General Graph Directory

The general graph directory is the generalization of the tree-level and acyclic graph structures. There is a root at the top, internal nodes below it, and leaves where the actual files are. The same directory may be shared by two different users, and the same subdirectory name present in two different directories can share a particular file. These are the advantages of the generalized form.

14.8 File System Mounting

14.8.1 What Mounting Means

Any file system first has to be mounted — only then can it be accessed. Mounting means we attach the file system to the drive: whatever drive is present in the system has to get attached, and then we call it mounted.

14.8.2 Mount Points and Privileges

Mounting is a privileged operation: not everyone can do this — only the administrator has the right. First, the system checks whether it is a verified file system, and the current data structure keeps track of the mount points. We must find the mount point: the place where we are going to attach the particular file system. For example, there is a partition that is a volume for us — the C drive — and that is where we can attach a file system. The mount point has to be tracked first, and then the file system is attached there.

14.8.3 Worked Walkthrough: Mounting Over an Existing Mount Point

14.8.4 Mounted versus Unmounted File Systems

An unmounted file system is one that at present is not attached to any mount point. A mounted file system is attached to a mount point and accessible. If a mount point such as C already has some contents and some file system, attaching a new file system there superimposes it — the previous contents are no longer visible.

14.9 File System Structure

14.9.1 A Layered File System

There are different file system structures: a layered structure, or a virtual file system — the Linux file system is a different way again. Generally the file system is stored in secondary storage. We map the information present there to the physical device with the help of a sector number, that is, a block number — the block within the sector — to read or write information. I/O transfers happen like this: first we should know the track number, followed by the sector number, followed by the block number, in order to access the information present in a particular block.

14.9.2 The Layers and What Each One Does

Each layer in the layered file system takes care of some information:

• File control block (FCB) — takes care of the storage-structure information about a particular file.
• Device driver — controls the physical device we are using. The device drivers act as the input/output path to the system; they are software device drivers that have to be installed, and with their help the I/O devices are managed. When we give a command such as "read drive 1, cylinder 72, track 2, sector 11, into the memory location", the command is given to the specific controller, the controller does all the work, and the information comes back.
• Basic file system — helps translate the information given by the device drivers.
• File organization module — organizes the files as physical blocks: where the files are present, what the logical address is, in which physical block that particular address lives, how to translate a logical address into a physical block number, which free spaces are available, and how the space is allocated or has to be allocated.

In the layered file system, each inner layer takes help from the lower-level layers: the I/O takes help from the devices, the application takes help from the I/O, and so on. If the application has to run, all the other layers must cooperate to perform the execution.

The logical file system generally holds all the information except the data present in the file: where the file is present, the file handle, the file number or location (the inode number on Unix), and the file control blocks. From the logical file system we go into the file organization, which takes care of free spaces and allocation; the basic file system takes the given command and passes it to the device drivers; the device drivers translate it to the system and the response comes back. Each layer does its own work.

14.9.3 Real-World File Systems

Real systems each have their own format, organization, and implementation:

• Unix uses something called the FFS (Unix Fast File System).
• Windows uses the FAT (File Allocation Table), with variations of it.
• Unix file system versions are named ext2, ext3, ext4.
• As of now many more exist: ZFS, the Google File System, and FUSE (Filesystem in Userspace) are all there.

14.9.4 Virtual File System in Unix

The virtual file system (VFS), present in Unix, provides an object-oriented approach. Everything is treated as an object, with the operations we can perform on the object. The details of how an object is represented and how it is implemented are usually hidden: how it is implemented is unknown to the caller, and how it is represented is also unknown — everything sits behind the system. What we see is an interface: we ask for something and get some information, with the help of the APIs.

The schematic view: a file system interface helps the user interact with the VFS interface. Each VFS has its own local file system, and it can also point to a remote file system. The local file system points in turn to the secondary storage device. When we have to access a piece of information, first we check whether it is in the local file system; if it is there, we take it from the disk and give it to the user. Otherwise it has to be accessed through the remote file system, and that is done with the help of the remote file system type.

14.9.5 The Four Linux VFS Objects

Linux is different from Unix, though Linux also has a virtual file system. Four main objects are involved:

1. inode — represents the individual file.
2. file — represents how many files have been opened.
3. super block object — represents the entire file system information.
4. directory entry (dentry) — represents an individual directory.

With these four object types, a set of operations is implemented. Each object has its own pointer that points to a function table; going to the function table gives the list of addresses of the operations we can perform with respect to that object. For an inode, the object holds the addresses of the actual functions we are going to perform, and the call goes to the particular location to access it. The same applies to the different files present in the file system.

14.10 File System Implementation and In-Memory Structures

14.10.1 Boot Control Block and Volume Control Block

Whenever a file system is going to be implemented, the first thing executed is the boot control block: it controls the boot information and is the first block of the volume. Then there is the volume control block, which contains the super block and the master file table. The super block holds the entire file system information. The master file table holds information about the total numbers: how many blocks are free, how many blocks are available, what the pointer to a particular block is, and which block is free.

14.10.2 The File Control Block

With respect to each and every file, we refer to the file control block (FCB), which gives detailed information about that file:

• The inode number.
• The permissions.
• The size and the dates — a file system keeps three dates: when the file was created, when it was last accessed, and when it was last modified; these dates are updated.
• Who is the owner of the file and which group it belongs to.
• The access control — a list with respect to every person, be it owner, group, or others.
• The file size and how many data blocks it uses.
• The pointers to the particular data blocks.

Everything is present inside this file-system structure.

14.10.3 In-Memory File System Structures

In-memory structures connect the user's call to the data. If the user issues an open on a file name, control transfers to the kernel. The kernel searches the directory structure for the entry of the particular file. That entry takes us to the location where the file control block with all the information lives. If the directory is not already in memory, it first has to be brought from secondary storage, and then the file control block is searched.

For reading: if the user is going to read some information, first the open file table is checked. With respect to each and every process, an entry is made when a file has been opened — an entry in the process's open file table — which takes a pointer to the system-wide (throughout the file system) open file table entry, indicating how many processes have opened the particular file. From there we get the exact location of where the data blocks are present in secondary storage.

14.10.4 From Open Call to Data Blocks

To know about a particular file: first the information is brought from the file control block; the FCB knows how many data blocks are being used and the location of each and every data block. Once we get the information from the file control block, it directly takes us to the data blocks. That is how the in-memory file system structure works.

14.11 Partitioning, Boot Block, and Mounting at Boot

14.11.1 Boot Block and Root Partition

Whenever we do a partition: the partition can be a volume, or a volume can have two different partitions. The partition can be raw — without any file system — or it can have a boot block. The boot block is only a single block; that is enough to load the kernel from the file system. There is also the root partition: from the root partition we can have other partitions and other file systems.

14.11.2 Mounting at Boot and Consistency Checks

The root partition is mounted at boot time; the other partitions can be mounted either automatically or manually. Why do this at boot? First, the file system consistency is checked. You have seen it when the system is booting: booting information scrolls by while all the folders and file systems are checked, and only then is access to the file system allowed.

14.12 Contiguous Allocation

14.12.1 How Contiguous Allocation Works

Now we know the file system, the directory structure, and the file system structure; the remaining question is how the files are allocated in the disk blocks. The first method is contiguous allocation. With a file stored contiguously, the blocks are occupied one after another — consecutively. This method is best in some cases because it is very simple: start from the first block and access all the blocks, no problem. If we know the block number and how many blocks are required for the allocation, the allocation is done by the operating system.

14.12.2 The Growth Problem: Compaction and Downtime

The problem comes when the file is going to be extended. Instead of the file staying at, say, 1 MB, it grows by another 1 KB. Now the space that was allocated is not enough. We cannot put the remaining contents into some other block — with contiguous allocation that is not possible; the file must stay in one consecutive stretch. So we have to move the file to a free space big enough to hold the contiguous allocation again. This moving is compaction — it is also downtime: the time taken to move the file is high, and it is a cost-consuming process.

14.12.3 Worked Example: A Directory Table of Blocks

The directory may hold, for each file, the file name, the starting block number, and how many blocks are used:

The first file starts at block 0 and occupies only 2 blocks, blocks 0 and 1. File f starts at the 6th block (block 6) and uses only 2 blocks, blocks 6 and 7. This is contiguous allocation as seen in the directory, and the growth problem we discussed applies to every such entry: extend the file, and the whole contiguous stretch may have to be moved.

14.13 Linked Allocation and the File Allocation Table

14.13.1 How Linked Allocation Works

In linked allocation, each file is a linked list of blocks: from one block to another, we have a pointer (the link). There is no need for compaction and no external fragmentation. Adding a new block is easy: extend the last block of the file to point to the next block that is free.

The file allocation table (FAT) sits at the beginning of the volume and is indexed by block number — for a given block, the table tells you the next block in the chain. With the linked list we can move faster from one block to the other.

14.13.2 Worked Example: A Block Chain (File g)

The directory entry tells you in which block the file starts and where the chain ends. Example: a file called g starts at block 9. From block 9 a pointer points to block 16, then a pointer points to block 1, then to block 2, and from there to the last block. The end of the block chain is mentioned as -1 — the minus one marks the end of the chain. By following the pointers we can understand how many blocks are used.

Chain for file g: 9 → 16 → 1 → 2 → -1 (end).

14.13.3 Worked Example: The Windows FAT

This is how the FAT-type allocation works in Windows. The directory has an entry per file with the starting block mentioned; it points to that particular block. If the entry mentions 0, it means that as of now no block has been allocated for this file. When we allocate a block for this file, we remove the 0 and attach the entry to the particular address. From there the continuation goes to the next location: from that block the FAT chain goes to 339, and from 339 to some other location, and so on, until it reaches the end marker. That is the FAT allocation done in Windows.

14.13.4 Worked Example: General Linked Allocation

A more general linked allocation works the same way with many files. The directory mentions only the starting block of each file. For the first file, the starting block alone is mentioned: 19. Going to block 19 shows the list of blocks where the particular file is present — blocks 1, 9, 10, 16, all in the chain. The rest of the entries are -1, which means there are no other blocks with respect to this file.

First file chain: 19 → (blocks 1, 9, 10, 16) → -1.

14.13.5 The Broken-Pointer Problem

The problem with linked allocation: we have to maintain the pointers, and that maintenance is itself an overhead. If one pointer gets disconnected, we no longer have any way to get the particular block — the information in that block and everything after it cannot be accessed. The pointer overhead and the single point of failure are the disadvantages of linked allocation.

14.14 Indexed Allocation and the Unix Inode Scheme

14.14.1 How Indexed Allocation Works

In indexed allocation, we create an index table. The table has one attribute as the key, and next to it the address, the pointer to the particular location. With the help of the key we can directly access the particular data block that is pointed to and get the information. Access is dynamic, and there is no external fragmentation — but the problem is the overhead of the index block itself.

14.14.2 Access Cost of the Index

Suppose the block size is 512 bytes. To map the logical to the physical — to find where the data block is present — we first access the index: the displacement into the index table has to be computed, and from the displacement we go to the block where the information is present. On the whole, at least one block access is required (the index table) and at most two. The capacity of the index table depends on the index table size and the data block size: an index block can hold roughly as many entries as fit in the block:

$$n_{\text{entries}}=\frac{B}{p}$$

where $B=512$ bytes is the block size and $p$ is the pointer size in bytes. With one level of indexing, a lookup costs:

$$1\le \text{block accesses}\le 2$$

so the minimum is one access (the index block) and the maximum is two (the index block plus the data block).

14.14.3 Multiple Levels of Indexing

In the linked scheme with multiple indexing, the size is not limited. First we go to the first index table; from the first index table we get the displacement for the particular block, which takes us to the second index table; from the second index table we get the displacement for the block of the file where it is located. The problem: with a minimum of two levels of indexing, we need three levels of access in order to find a particular file.

14.14.4 The Unix Scheme: Direct, Single-Indirect, Double-Indirect, Triple-Indirect

The Unix file system in fact does this type of indexing scheme. Either you get the data block directly with the help of the direct blocks — with 10 direct blocks you can straight away access the data block, and the data block size may be up to 1024 bytes — or you go through index tables:

• 10 direct blocks: straight access to the data block. With block size 1024 bytes, the 10 direct blocks serve files up to:

$$10\times 1024\text{bytes}=10240\text{bytes}\approx 10\text{KB}$$

• Single indirect: we do not go to the data block first; we go to one table — an index table — and from there to the data block, in order to access the data.
• Double indirect: two levels of indirection — two index tables before the data block.
• Triple indirect: three levels of indexing before the data block.

In the double- and triple-indirect cases the time taken to access the data grows, and we have to maintain the three levels of indexing, which is an overhead. So the trade-off is: direct blocks give instant access, and each extra indirect level adds another table visit in exchange for supporting much larger files.

14.14.5 Student Questions and Answers

Exam Guidance Summary

No mark distribution, question pattern, or study references were given in this session. What the session did establish:

• The unit scope, which is exam-relevant: disk directory structure, file mounting, file system implementation, and the allocation methods (contiguous, linked/FAT, indexed), followed by mass storage structure and disk scheduling.
• A problems session is scheduled ahead — an upcoming problems session was announced during the directory discussion.
• The core distinctions to know: truncation versus deletion, mandatory versus advisory locking, mounted versus unmounted file systems, sequential versus direct versus indexed access, and the strengths and weaknesses of each allocation method.

Key Industry Applications

• Real-world: Windows organizes files under drives and folders, and calls a partition a volume; Windows uses the FAT (File Allocation Table) type of linked allocation, with a chain per file and 0 meaning "no block allocated".
• Real-world: Unix/Linux treats directories as files, identifies every file with an inode, and uses the FFS (Fast File System) with the ext2, ext3, and ext4 file system variants; its indexed allocation uses 10 direct blocks plus single-, double-, and triple-indirect blocks with 1024-byte blocks.
• Real-world: VMS uses a volume letter and square brackets in its path notation (for example volume:[dir.subdir]file), while Unix separates path components with slashes (/home/.../file).
• Real-world: macOS uses the file type attribute to open a file with the right application on double-click; Unix historically used a magic number in the first byte of the file for the same purpose.
• Real-world: ZFS, the Google File System, and FUSE are modern file systems with their own format, organization, and implementation.
• Real-world: tmpfs, objfs, cdfs, lofs, and procfs are special-purpose file system types, each with its own purpose (temporary, object-based, contract, loopback, and process information respectively).
• Real-world: common extensions such as .c, .cpp, .java, .doc, .ppt, .mp3, .mp4, .ps, .pdf, .mov, and .rm identify file types across systems.