File Systems

Chapter 4

Tanenbaum & Bo, Modern Operating Systems:4th ed., (c) 2013 Prentice-Hall, Inc. All rights reserved.
 File Systems (1)
Essential requirements for long-term
information storage:
1.It must be possible to store a very large
amount of information.
2.Information must survive termination of
process using it.
3.Multiple processes must be able to access
information concurrently.

Tanenbaum & Bo, Modern Operating Systems:4th ed., (c) 2013 Prentice-Hall, Inc. All rights reserved.
 File Systems (2)

Think of a disk as a linear sequence of

fixed-size blocks and supporting two
operations:
1.Read block k.
2.Write block k

Tanenbaum & Bo, Modern Operating Systems:4th ed., (c) 2013 Prentice-Hall, Inc. All rights reserved.
 File Systems (3)

Questions that quickly arise:

1.How do you find information?
2.How do you keep one user from reading
another user’s data?
3.How do you know which blocks are free?

Tanenbaum & Bo, Modern Operating Systems:4th ed., (c) 2013 Prentice-Hall, Inc. All rights reserved.
 File Systems
• Computer applications need to store and retrieve
information:
– need to store large amount of information
– need to store information permanently
– need to share information

• A file is a collection of data records grouped together for

purpose of access control and modification

• A file system is software responsible for creating, destroying,

organizing, reading, writing, modifying, moving, and
controlling access to files; and for management of resources
used by files.
5
 User-Level View
• Naming convention
• File structures
• File types
• File access: sequential vs random access
• File operations:
– system calls (file/directory operations)
• Memory-mapped files
• Directory structure (single-level vs. two-level vs. hierarchical
– path names
– directory operations

6
 File Naming
• Naming convention
– number of characters (e.g. limited to 8+3 in MS-DOS)
– case sensitive or not, Which chars are allowed
– special prefixes/extensions (.txt, .ps, .gif, .mpg, …..)
• The family of MS-DOS
– Win3.1, Win95, Win98
– NT, Win2000 (supports MS-DOS, but have native file
system NTFS)
• In Unix, many extensions are just conventions
– exceptions are for example compilers
• Windows assigns meaning to extensions

7
 File Naming

Figure 4-1. Some typical file extensions.

Tanenbaum & Bo, Modern Operating Systems:4th ed., (c) 2013 Prentice-Hall, Inc. All rights reserved.
 File Structure

Figure 4-2. Three kinds of files. (a) Byte sequence.

(b) Record sequence. (c) Tree.
Tanenbaum & Bo, Modern Operating Systems:4th ed., (c) 2013 Prentice-Hall, Inc. All rights reserved.
 File Types
• Unix
– regular files
• ASCII
• binary
– directory files
– character special files (I/O devices that operate on streams)
– block special files (disk I/O)
• Every OS must at least recognize its own executables
– Unix: header, text and data
– magic numbers

10
 File Types

Figure 4-3. (a) An executable file. (b) An archive

Tanenbaum & Bo, Modern Operating Systems:4th ed., (c) 2013 Prentice-Hall, Inc. All rights reserved.
 File Access
• Sequential access
– read all bytes/records from the beginning
– cannot jump around, could rewind or back up
– convenient when medium was magnetic tape
• Random access
– bytes/records read in any order
– essential for many applications
– read can be …
• move file pointer (seek), then read or …
• read and then move file marker
– all modern OS have all files as random access
12
 File Attributes
• File name
• Size information (current, limit)
• Physical address
• File type
– ASCII vs binary
– Temporary vs Permanent
• Access rights: owner, protection (who can access it)
• Access type: Sequential/Random
• History: Creator, time of last access/modification, other usage data
• Info for managing links

13
 File Attributes

Figure 4-4. Some possible file attributes.

Tanenbaum & Bo, Modern Operating Systems:4th ed., (c) 2013 Prentice-Hall, Inc. All rights reserved.
 File Operations

1. Create 7. Append
2. Delete 8. Seek
3. Open 9. Get attributes
4. Close 10. Set attributes
5. Read 11. Rename
6. Write

Tanenbaum & Bo, Modern Operating Systems:4th ed., (c) 2013 Prentice-Hall, Inc. All rights reserved.
 Single-Level Directory Systems

Figure 4-6. A single-level directory system containing four files.

Tanenbaum & Bo, Modern Operating Systems:4th ed., (c) 2013 Prentice-Hall, Inc. All rights reserved.
Hierarchical Directory Systems

Figure 4-7. A hierarchical directory system.

Tanenbaum & Bo, Modern Operating Systems:4th ed., (c) 2013 Prentice-Hall, Inc. All rights reserved.
 Path Names

Figure 4-8. A UNIX

directory tree.
Tanenbaum & Bo, Modern Operating Systems:4th ed., (c) 2013 Prentice-Hall, Inc. All rights reserved.
 Directory Operations
1. Create 5. Readdir
2. Delete 6. Rename
3. Opendir 7. Link
4. Closedir 8. Unlink

Tanenbaum & Bo, Modern Operating Systems:4th ed., (c) 2013 Prentice-Hall, Inc. All rights reserved.
 File System Implementation
• Sector 0 is called the Master Boot Record
– used to boot the computer
– contains partition table at the end
– one partition must be marked as active/primary
• BIOS (located on the parentboard) reads and executes
MBR (after trying to boot from floppy or CD-ROM)
• MBR locates the active partition and reads in its first block
• Every partitions comes with a boot block

20
 File System Layout

Figure 4-9. A possible file system layout.

Tanenbaum & Bo, Modern Operating Systems:4th ed., (c) 2013 Prentice-Hall, Inc. All rights reserved.
 Booting and Disk Layout
Sector number
• ROM (read-only, persistent) memory
contains a small bootstrap loader program 0
Boot block
• System disk contains boot block in first block 1
FAT
of each partition
• Boot block has bootstrap executable Root directory
• Bootstrap loader copies bootstrap program
into memory
• Bootstrap program initializes all registers,
finds OS kernel on disk, loads OS, and jumps
to the initial address of OS
• Why is bootstrap not in ROM?

22MS-DOS disk layout

 Disk Space Organization
• Disk can be partitioned
– Each partition can have a different OS and/or different file system
– One partition can be swap space for main memory
• First block of disk has master boot record specifying primary partition
• Each partition has
– Boot block (loads OS in kernel space)
– Superblock (contains key info about file system which is read into
memory at boot time)
– Free space management
– List of I-nodes (or other data structure) giving info about all files
– Directories and Files

23
 File Space Allocation
• Goals
– Fast sequential access
– Fast random access
– Ability to dynamically grow
– Minimum fragmentation
• Standard schemes
– Contiguous allocation (fixed)
– Linked list allocation
– Linked list with file allocation table (FAT)
– Linked list with Indexing (I-nodes)

24
 Contiguous Allocation
• Each file occupies a contiguous region of blocks
• Fast random access (only one seek needed)
• Useful when read-only devices or small devices
– CD-ROMs, DVD-ROMs and other optical media
– Embedded/personal devices
• Management is easy
– Directory entry of a file needs to specify its size and start location
• Fragmentation is a problem if deletes are allowed, or if files grow in
size
• After disk is full, new files need to fit into holes  advanced
declaration of size at the time of creation

25
 Implementing Files
Contiguous Layout

Figure 4-10. (a) Contiguous allocation of disk

space for seven files. (b) The state of the
disk after files D and F have been removed.

Tanenbaum & Bo, Modern Operating Systems:4th ed., (c) 2013 Prentice-Hall, Inc. All rights reserved.
 Linked Lists
• Natural choice: maintain a linked list of blocks that
contain each file
• Directory entry of a file points to first block, and
each block begins with a pointer to next block
• No external fragmentation
• Speed of random access is slow
– Accessing th block requires  disk accesses, i.e. -
accesses for pointers
• Data size in a block is no longer power of 2
because of pointer storage
27
 Implementing Files
Linked List Allocation

Figure 4-11. Storing a file as a linked list of disk blocks.

Tanenbaum & Bo, Modern Operating Systems:4th ed., (c) 2013 Prentice-Hall, Inc. All rights reserved.
 Linked List with FAT
• So pointers are trouble, don’t store them in blocks!
• Solution: Maintain a File Allocation Table in main memory
– FAT is an array indexed by blocks
– Each array entry is a pointer to next block
• Accessing th block would still require traversing the chain of
pointers, however, they are in main memory and no disk I/O
is needed
• Problem: the entire FAT must be in memory, and as disk size
increases, so does FAT
– 20GB disk with 1k block size needs 20 million entries,
which requires entry sizes of minimum 3 bytes, which is
results a FAT of 60MB

29
 Implementing Files
Linked List – Table in Memory

Figure 4-12. Linked list allocation using a file

allocation table in main memory.
Tanenbaum & Bo, Modern Operating Systems:4th ed., (c) 2013 Prentice-Hall, Inc. All rights reserved.
 Indexing with i-nodes
• Each file has an associated fixed length record called an i-node
• i-node maintains all attributes of the file
• i-node also keeps addresses of fixed number of blocks
• Additional levels of indexing possible to accommodate larger
files
– last address reserved for pointer to another block of
addresses
• Space required is much less than FAT
– only i-nodes of open files need to be in memory
– an array of i-node numbers, whose size is proportional to the
max # of open files allowed by the system, not disk size
• Time required to access specific block can vary
31
 Implementing
Files
I-nodes

Figure 4-13. An
example i-node.

Tanenbaum & Bo, Modern Operating Systems:4th ed., (c) 2013 Prentice-Hall, Inc. All rights reserved.
 Directories
• A directory entry provides the info needed
to find the disk data blocks of a file
– disk address of first block and size
– address of first block
– number of associated i-node
• File attributes can be stored in the directory
entry (Windows) or in its i-node (Unix)
• File name and support of variable length
and long file names (255 chars)
33
Implementing Directories (1)

Figure 4-14. (a) A simple directory containing fixed-size

entries with the disk addresses and attributes in the
directory entry. (b) A directory in which each
entry just refers to an i-node.
Tanenbaum & Bo, Modern Operating Systems:4th ed., (c) 2013 Prentice-Hall, Inc. All rights reserved.
Implementing Directories (2)

Figure 4-15. Tw o ways of handling long file names in a

directory. (a) In-line. (b) In a heap.
Tanenbaum & Bo, Modern Operating Systems:4th ed., (c) 2013 Prentice-Hall, Inc. All rights reserved.
 Links
• Convenient solution to file sharing
• Hard link
– pointer to i-node added to the directory entries
– link counter in the i-node linked to incremented
– i-node can only be deleted (data addresses cleared) if
counter goes down to 0, why?
– original owner can not free disk quota unless all hard
links are deleted
• Soft link (symbolic)
– new special file created of type LINK, which contains
just the path name
– new file also has its own i-node created
36
 Shared Files (1)

Figure 4-16. File system containing a shared file.

Tanenbaum & Bo, Modern Operating Systems:4th ed., (c) 2013 Prentice-Hall, Inc. All rights reserved.
 Shared Files (2)

Figure 4-17. (a) Situation prior to linking. (b) After the link is
created. (c) After the original owner removes the file.
Tanenbaum & Bo, Modern Operating Systems:4th ed., (c) 2013 Prentice-Hall, Inc. All rights reserved.
 Disk Space Management
• Many of the same trade-offs or issues in memory management are also
present in disk management
– keeping track of free blocks
– segmentation
– caching and paging
• Block size, how big?
– smaller block size leads to less waste in a block
– larger block size leads to better data transfer rate (block assess time is
dominated by seek time and rotational delay)
– experiments lead to estimate of median file size at 2KB
– Unix systems commonly keep 1KB, because its choice was made a long
time ago
16
– MS-Dos has a 2 limit on number of blocks, making block size
proportional to disk size

39
Disk Space Management (1)

Figure 4-20. Percentage of files smaller than a

given size (in bytes).
Tanenbaum & Bo, Modern Operating Systems:4th ed., (c) 2013 Prentice-Hall, Inc. All rights reserved.
 Disk Space Management (2)

Figure 4-21. The dashed curve (left-hand scale) gives the data rate of a disk. The
solid curve (right-hand scale) gives the disk space efficiency. All files are 4 KB.

Tanenbaum & Bo, Modern Operating Systems:4th ed., (c) 2013 Prentice-Hall, Inc. All rights reserved.
 Managing Free Disk Space
• How to keep track of free blocks?
• Linked List Method
– Maintained as a list of blocks containing addresses of free blocks
– Each block address is 32 bits or 4 Bytes
– A 1KB block used can hold addresses of 255 free blocks and an
address of the next block in the list for free space management
– Note: This list is stored in free blocks themselves
• Bitmap method:
– Keep an array of bits, one per block indicating whether that block
is free or not
– A 16-GB disk has 16 million 1 KB blocks
– Storing the bitmap requires 16 million bits, or 2048 blocks
• How do the two methods compare in terms of space requirements?
42
Keeping Track of Free Blocks (1)

Figure 4-22. (a) Storing the free list on a

linked list. (b) A bitmap.
Tanenbaum & Bo, Modern Operating Systems:4th ed., (c) 2013 Prentice-Hall, Inc. All rights reserved.
Keeping Track of Free Blocks (2)

Figure 4-23. (a) An almost-full block of pointers to free disk

blocks in memory and three blocks of pointers on disk. (b)
Result of freeing a three-block file. (c) An alternative strategy
for handling the three free blocks. The shaded entries
represent pointers to free disk blocks.
Tanenbaum & Bo, Modern Operating Systems:4th ed., (c) 2013 Prentice-Hall, Inc. All rights reserved.
 Disk Quotas

Figure 4-24. Quotas are kept track of on a

per-user basis in a quota table.
Tanenbaum & Bo, Modern Operating Systems:4th ed., (c) 2013 Prentice-Hall, Inc. All rights reserved.
 System Reliability
• Destruction of a file system is the worst disaster known to
a computer

• Backups
– recover from (natural) disaster
– recover from stupidity
• Different dumps
– full dump
– incremental dump
– physical dump
– logical dump

46
 File System Backups (1)

Backups to tape are generally made to

handle one of two potential problems:
1.Recover from disaster.
2.Recover from stupidity.

Tanenbaum & Bo, Modern Operating Systems:4th ed., (c) 2013 Prentice-Hall, Inc. All rights reserved.
 File System Backups (2)

Figure 4-25. A file system to be dumped. The squares are directories and the circles are
files. The shaded items have been modified since the last dump. Each directory and file
is labeled by its i-node number.

Tanenbaum & Bo, Modern Operating Systems:4th ed., (c) 2013 Prentice-Hall, Inc. All rights reserved.
 File System Backups (3)

Figure 4-26. Bitmaps used by the logical dumping algorithm.

Tanenbaum & Bo, Modern Operating Systems:4th ed., (c) 2013 Prentice-Hall, Inc. All rights reserved.
 File System Consistency
• Disk I/O is buffered
• There may be a crash before the modified blocks in
memory are written back to the disk
• File system consistency must be checked after a crash
– fsck
– scandisk
– block consistency – a block is either used (listed in i-
node) by only one file or is free (listed in free list)
– file consistency – a file has the same number of
directory entries (i.e. the same number of hard links)
as the link count in its i-node

50
 File System Consistency

Figure 4-27. File system states. (a) Consistent. (b) Missing

block. (c) Duplicate block in free list. (d) Duplicate data block.
Tanenbaum & Bo, Modern Operating Systems:4th ed., (c) 2013 Prentice-Hall, Inc. All rights reserved.
File System Performance (1)

Figure 4-28. The buffer cache data structures.

Tanenbaum & Bo, Modern Operating Systems:4th ed., (c) 2013 Prentice-Hall, Inc. All rights reserved.
 File System Performance (2)
• Some blocks rarely referenced two times
within a short interval.
• Leads to a modified LRU scheme, taking two
factors into account:
1. Is the block likely to be needed again soon?
2. Is the block essential to the consistency of the
file system?

Tanenbaum & Bo, Modern Operating Systems:4th ed., (c) 2013 Prentice-Hall, Inc. All rights reserved.
 MS-DOS
• Originally invented as a method for storing data on
floppy disks, first version has single directory
• Later used by MS-DOS with supports for a hierarchical
directory structure, and fixed disks as well as floppy
disks
– directory entries are fixed 32 bytes
– different versions support FAT-12, FAT-16 or FAT-32

54
 The MS-DOS File System (2)

Figure 4-31. Maximum partition size for different block sizes.

The empty boxes represent forbidden combinations.
Tanenbaum & Bo, Modern Operating Systems:4th ed., (c) 2013 Prentice-Hall, Inc. All rights reserved.
 The Classic Unix File System
• Each disk partition has 4 Regions
– block 0: boot block
– block 1: super block. Contains the size of the disk and the
boundaries of the other regions
– i-nodes: list of i-nodes, each is a 64-byte structure
– free storage blocks for the contents of files.
• Each i-node contains owner, protection bits, size, directory/file
and 13 disk addresses.
• The first 10 of these addresses point directly at the first 10 blocks
of a file. If a file is larger than 10 blocks (5,120 bytes), the 11th
points at a block for secondary indexing – single indirect block

56
 Classic Unix File System Cont.
• Second-level index block contains the addresses of the next 128
blocks of the file (70,656 bytes)
• Two levels of indirection:12th entry (double indirect block) points
at up to 128 blocks, each pointing to 128 blocks of the file
(8,459,264 bytes)
• Three levels of indirection: 13th address (triple indirect block) is
for a three layered indexing of 1,082,201,087 bytes.
• A directory is accessed exactly as an ordinary file.
It contains 16 byte entries consisting of a 14-byte name and an i-
number (index or ID of an i-node). The root of the file system
hierarchy is at a known i-number (2).

57
The UNIX V7 File System (1)

Figure 4-32. A UNIX V7 directory entry.

Tanenbaum & Bo, Modern Operating Systems:4th ed., (c) 2013 Prentice-Hall, Inc. All rights reserved.
The UNIX V7 File System (2)

Figure 4-33. A UNIX i-node

Tanenbaum & Bo, Modern Operating Systems:4th ed., (c) 2013 Prentice-Hall, Inc. All rights reserved.
 Traversing Directory Structure
• Suppose we want to read the file /usr/ast/mbox
• Location of a i-node, given i-number, can be computed
• i-number of the root directory known, say, 2
• Read in the i-node 2 from the disk into memory
• Find out the location of the root directory file on disk, and read the
directory block in memory
– If directory spans multiple blocks, then read blocks until usr found
• Find out the i-number of directory usr, which is 6
• Read in the i-node 6 from disk
• Find out the location of the directory file usr on disk, and read in the
block containing this directory
• Find out the i-number of directory ast (26), and repeat

60
The UNIX V7 File System (3)

Figure 4-34. The steps in looking up /usr/ast/mbox.

Tanenbaum & Bo, Modern Operating Systems:4th ed., (c) 2013 Prentice-Hall, Inc. All rights reserved.
 Rock Ridge Extensions
1. PX - POSIX 5. NM - Alternative
attributes. name.
2. PN - Major and 6. CL - Child location.
minor device 7. PL - Parent location.
numbers. 8. RE - Relocation.
3. SL - Symbolic link. 9. TF - Time stamps.

Tanenbaum & Bo, Modern Operating Systems:4th ed., (c) 2013 Prentice-Hall, Inc. All rights reserved.
 Joliet Extensions

1. Long file names.

2. Unicode character set.
3. Directory nesting deeper than eight
levels.
4. Directory names with extensions

Tanenbaum & Bo, Modern Operating Systems:4th ed., (c) 2013 Prentice-Hall, Inc. All rights reserved.
 End

Chapter 4

Tanenbaum & Bo, Modern Operating Systems:4th ed., (c) 2013 Prentice-Hall, Inc. All rights reserved.