MODERN OPERATING SYSTEMS
Third Edition
ANDREW S. TANENBAUM
Chapter 4
File Systems
Slides modified from:
Tanenbaum, Modern Operating Systems 3 e, (c) 2008 Prentice-Hall, Inc. All rights reserved. 0-13-6006639
File Systems (1)
Essential requirements for long-term
information storage:
• It must be possible to store a very large amount
of information.
• The information must survive the termination of
the process using it.
• Multiple processes must be able to access the
information concurrently.
Slides modified from:
Tanenbaum, Modern Operating Systems 3 e, (c) 2008 Prentice-Hall, Inc. All rights reserved. 0-13-6006639
File Systems (2)
Think of a disk as a linear sequence of fixed-size
blocks and supporting reading and writing of
blocks. Questions that quickly arise:
• How do you find information?
• How do you keep one user from reading another’s data?
• How do you know which blocks are free?
Slides modified from:
Tanenbaum, Modern Operating Systems 3 e, (c) 2008 Prentice-Hall, Inc. All rights reserved. 0-13-6006639
File Structure
Figure 4-2. Three kinds of files. (a) Byte sequence.
(b) Record sequence. (c) Tree.
Slides modified from:
Tanenbaum, Modern Operating Systems 3 e, (c) 2008 Prentice-Hall, Inc. All rights reserved. 0-13-6006639
File Types
Figure 4-3. (a) An executable file. (b) An archive.
Slides modified from:
Tanenbaum, Modern Operating Systems 3 e, (c) 2008 Prentice-Hall, Inc. All rights reserved. 0-13-6006639
File Attributes
Figure 4-4a. Some possible file attributes.
Slides modified from:
Tanenbaum, Modern Operating Systems 3 e, (c) 2008 Prentice-Hall, Inc. All rights reserved. 0-13-6006639
Hierarchical Directory Systems (2)
Figure 4-7. A hierarchical directory system.
Slides modified from:
Tanenbaum, Modern Operating Systems 3 e, (c) 2008 Prentice-Hall, Inc. All rights reserved. 0-13-6006639
Path Names
Figure 4-8. A UNIX directory tree.
Slides modified from:
Tanenbaum, Modern Operating Systems 3 e, (c) 2008 Prentice-Hall, Inc. All rights reserved. 0-13-6006639
File System Layout
Figure 4-9. A possible file system layout.
Slides modified from:
Tanenbaum, Modern Operating Systems 3 e, (c) 2008 Prentice-Hall, Inc. All rights reserved. 0-13-6006639
Implementing Files
• A file on the disk may span several
blocks
• Need to keep track of which disk block
go with which file
• Various methods are used in different
OSs for such tracking
• Contiguous allocation
• Linked list allocation
Contiguous Allocation
Figure 4-10. (a) Contiguous allocation of disk space for 7 files.
(b) The state of the disk after files D and F have been removed.
Slides modified from:
Tanenbaum, Modern Operating Systems 3 e, (c) 2008 Prentice-Hall, Inc. All rights reserved. 0-13-6006639
Contiguous Allocation
• Advantages
• Simple to implement – just need to remember two numbers: i)
disk address of the first block; ii) number of blocks in the file
• Excellent read performance – seek and rotational delays are
minimized
• Bo the sequential and random accesses are fast
• Disadvantages
• Disk becomes fragmented over time
• Need to specify the size of the file at the time of file creation to
locate the right size hole in the fragmented disk to store the file
• How about word processing (document) files
• Works for CDROM where all the file sizes are known in advance.
Linked List Allocation
Figure 4-11. Storing a file as a linked list of disk blocks.
Slides modified from:
Tanenbaum, Modern Operating Systems 3 e, (c) 2008 Prentice-Hall, Inc. All rights reserved. 0-13-6006639
Linked List Allocation
• Advantages
• No space is lost to disk fragmentation
• Directory entry (I-node) can store the address of the
first block
• Disadvantages
• Sequential access is straightforward; however,
random access is extremely slow
• To get to block n, the OS has to start at the
beginning and read all the n-1 blocks first
• Amount of data stored in each block is not a power of
two because the pointer takes a few bytes – having
peculiar size is less efficient because many programs
read and write in blocks whose size is a power of two
Linked List Allocation
• Both disadvantages of linked list allocation can
be eliminated by taking the pointer word from
each disk block and putting it in a table in
memory
Linked List Allocation Using a Table in Memory
File A uses blocks 4, 7, 2, 10, and 12
File B users blocks 6, 3, 11, and 14
Such table in memory is called File Allocation Table (FAT)
Slides modified from:
Tanenbaum, Modern Operating Systems 3 e, (c) 2008 Prentice-Hall, Inc. All rights reserved. 0-13-6006639
FAT
• Disadvantages
• The entire table must be kept in memory
• With a 200-GB disk and 1-KB block size, need to
store 200 million entries
• 4bytes per entry 800MB of main memory for
FAT
• FAT does not scale well to large disks
I-nodes
Figure 4-13. An example i-node.
Tanenbaum, Modern Operating Systems 3 e, (c) 2008 Prentice-Hall, Inc. All rights reserved. 0-13-6006639
The Linux Ext2 File System (4)
Slides modified from:
Tanenbaum, Modern Operating Systems 3 e, (c) 2008 Prentice-Hall, Inc. All rights reserved. 0-13-6006639
The Linux Ext2 File System (4)
• If a disk block is 1 KB and the disk address is 4 bytes
- Direct disk block field – 12 blocks
- Works for files <= 12KB
- Single indirect block -- 1024/4 = 256 addresses
- works for files <= 256KB + 12KB = 268KB
- Double indirect block – 256 * 256 = 65,536 addresses
- works for files <= 12KB + 256KB + 64MB ≈ 64.26 MB
- Triple indirect block – 256*256*256 = 16,777,216 addresses
- works for files <= 12KB + 256KB + 64 MB + 16 GB
≈16.0627GB
