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:
[Link] must be possible to store a very large
amount of information.
[Link] must survive termination of
process using it.
[Link] 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:
[Link] block k.
[Link] block k

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

Questions that quickly arise:

[Link] do you find information?
[Link] do you keep one user from reading
another user’s data?
[Link] do you know which blocks are free?

Tanenbaum & Bo, Modern Operating Systems:4th ed., (c) 2013 Prentice-Hall, Inc. All rights reserved.
 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

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 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.
Example Program Using File System Calls (1)

Figure 4-5. A simple program to copy a file.

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

Figure 4-5. A simple program to copy a file.

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

Figure 4-5. A simple program to copy a file.

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 Layout

Figure 4-9. A possible file system layout.

Tanenbaum & Bo, Modern Operating Systems:4th ed., (c) 2013 Prentice-Hall, Inc. All rights reserved.
 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.
 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.
 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.
 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.
 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.
 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.
 Journaling File Systems

Steps to remove a file in UNIX:

[Link] file from its directory.
[Link] i-node to the pool of free i-nodes.
[Link] all disk blocks to pool of free disk
blocks.

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

Figure 4-18. Position of the virtual file system.

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

Figure 4-19. A simplified view

of the data structures and
code used by the VFS and
concrete file system
to do a read.
Tanenbaum & Bo, Modern Operating Systems:4th ed., (c) 2013 Prentice-Hall, Inc. All rights reserved.
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.
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.
 File System Backups (1)

Backups to tape are generally made to

handle one of two potential problems:
[Link] from disaster.
[Link] 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

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.
 Reducing Disk Arm Motion

Figure 4-29. (a) I-nodes placed at the start of the

disk. (b) Disk divided into cylinder groups, each
with its own blocks and i-nodes.
Tanenbaum & Bo, Modern Operating Systems:4th ed., (c) 2013 Prentice-Hall, Inc. All rights reserved.
The MS-DOS File System (1)

Figure 4-30. The MS-DOS directory entry.

Tanenbaum & Bo, Modern Operating Systems:4th ed., (c) 2013 Prentice-Hall, Inc. All rights reserved.
 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 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.
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.
 The ISO 9660 File System

Figure 4-35. The ISO 9660 directory entry.

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.