MODERN OPERATING SYSTEMS

Third Edition

ANDREW S. TANENBAUM

Chapter 4
File Systems

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.

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?

Tanenbaum, Modern Operating Systems 3 e, (c) 2008 Prentice-Hall, Inc. All rights reserved. 0-13-6006639
 files
• Processes (threads), address spaces, files are
the most important concepts in OS
• Files are logical units of information created
by processes
– Similar to kind of address space
• File system
– Manage files: how they are structured, named,
accessed, used, protected, implemented, etc
 File naming
• Files are abstraction mechanism
– To store information on the disk and read it back
– When a process creates a file, it gives the file a name;
and the file can be accessed by the name
• Two-part file name
– File extension: indicating characteristics of file
– In Unix, file extension is just convention; C compiler is
exception
– In windows, file extensions specify which program
“owns” that extension; when double clicking, program
assigned to it is launched
 File Naming

Figure 4-1. Some typical file extensions.

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.
Tanenbaum, Modern Operating Systems 3 e, (c) 2008 Prentice-Hall, Inc. All rights reserved. 0-13-6006639
 File Types
• Regular Files:
– ASCII files or binary files
– ASCII consists of lines of text; can be displayed and printed
– Binary, have some internal structure known to programs
that use them
• Directory
– Files to keep track of files
• Character special files (a character device file)
– Related to I/O and model serial I/O devices
• Block special files (a block device file)
– Mainly to model disks
 File Types

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

Tanenbaum, Modern Operating Systems 3 e, (c) 2008 Prentice-Hall, Inc. All rights reserved. 0-13-6006639
 File Access
• File descriptor
– A file descriptor is a small integer representing a
kernel-managed object that a process may read
from or write to
– Every process has a private space of file
descriptors starting at 0
– By convention, 0 is standard input, 1 is standard
output, and 2 is standard error
• System call: read() and write() to read from
and write to filles named by file descriptors
 File Attributes

Figure 4-4a. Some possible file attributes.

Tanenbaum, Modern Operating Systems 3 e, (c) 2008 Prentice-Hall, Inc. All rights reserved. 0-13-6006639
 Struct stat
• Struct stat{
mode_t st_mode; // file type and mode (permission)
ino_t st_ino; //inode number
dev_t st_dev; //device number
dev_t st_rdev; //device number (special)
nlink_t st_nlink; //number of links
uid_t st_uid; // user ID of owner
gid_t st_gid; // group ID of owner
off_t st_size; //size in bytes
time_t st_atime; //time of last access
……}
 File attributes
• drwxr-xr-x 2 root root 4096 Sep 24 2008 Unit2
• drwxr-xr-x 2 root root 4096 May 26 19:21 a
• -rwxr-xr-x 1 root root 10930 Aug 5 22:49 a.out
• -rwxrwx--T 1 root root 81 Aug 2 2008 a.txt
• -rwxr-x--- 1 root root 81 May 26 19:20 b.txt
• -rwx------ 1 root root 81 Jul 30 19:28 c.txt
• -rwxr-xr-x 1 root root 11193 Jul 30 19:27 cp
 File Group Everyone
Owner Owner Else

Write Read Execute

Permission Permission Permission
 UNIX

File Group Everyone

Owner Owner Else
 File Operations
The most common system calls relating to files:

• Create • Append
• Delete • Seek
• Open • Get Attributes
• Close • Set Attributes
• Read • Rename
• Write

Tanenbaum, Modern Operating Systems 3 e, (c) 2008 Prentice-Hall, Inc. All rights reserved. 0-13-6006639
Example Program Using File System Calls (1)

...
Figure 4-5. A simple program to copy a file.
Tanenbaum, Modern Operating Systems 3 e, (c) 2008 Prentice-Hall, Inc. All rights reserved. 0-13-6006639
Example Program Using File System Calls (2)

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

Tanenbaum, Modern Operating Systems 3 e, (c) 2008 Prentice-Hall, Inc. All rights reserved. 0-13-6006639
 Hierarchical Directory Systems (1)

Single-level directory system:

The simpliest

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

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.

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.

Tanenbaum, Modern Operating Systems 3 e, (c) 2008 Prentice-Hall, Inc. All rights reserved. 0-13-6006639
 Path names
• Absolute path name
– Start from root and are unique
• Relative path name
– Current working set: all path names not beginning
at the root directory are taken relative to the
working directory
– If current working directory is /usr/ast:
• then cp /usr/ast/mailbox /usr/ast/mailbox.bak
• Is: cp mailbox mailbox.bak
 Path names
• Special Entries:
– “.” and “..”
– Dot refers to the current directory; dotdot refers
to the parent directory (except root)
– cp /usr/lib/dictionary .
– cp /usr/lib/dictionary dictionary
– Cp /usr/lib/dictionary /usr/ast/dictionary
 Directory Operations
System calls for managing directories:

• Create • Readdir
• Delete • Rename
• Opendir • Link
• Closedir • Unlink

Tanenbaum, Modern Operating Systems 3 e, (c) 2008 Prentice-Hall, Inc. All rights reserved. 0-13-6006639
 Directory operation
• Hard link
– Linking allows a file to appear in more than one
directory; increments the counter in the file’s i-
node
• Symbolic link
– A name is created pointing to a tiny file naming
another file
 File System Implementation
• Users:
– How files are names, what operations are allowed
on them, what the directory tree looks like
• Implementors
– How files and directories are stored, how disk
space is managed and how to make every thing
work efficiently and reliably
 File System Layout
• File system are stored on disks.
• Most disks are divided up into several partitions
• Sector 0 is called MBR (master boot record), to boot
the computer
• BIOS reads in and executes MBR, MBR locates the
active partition, reads in the boot block, and execute
• The boot block reads in the OS contained in the
partition
 File System Layout
Superblock: contains all the key parameters about a file
system; read into memory the booted or the FS is used

Figure 4-9. A possible file system layout.

Tanenbaum, Modern Operating Systems 3 e, (c) 2008 Prentice-Hall, Inc. All rights reserved. 0-13-6006639
 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.
Tanenbaum, Modern Operating Systems 3 e, (c) 2008 Prentice-Hall, Inc. All rights reserved. 0-13-6006639
 Contiguous Allocation
• Advantage：
– Simple to implement; to record the first block and
length
– Easy to read; only one seek is needed
• Disadvantage:
– Fragmentation
 Linked List Allocation

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

Tanenbaum, Modern Operating Systems 3 e, (c) 2008 Prentice-Hall, Inc. All rights reserved. 0-13-6006639
 Linked list allocation
• To keep each file as a linked list of disk blocks
• Advantage
– Only internal fragmentation
• Disadvantage
– Random access is difficult
– Adding a pointer at the head of block; extra
overhead while copying
 Linked List Allocation Using a Table in Memory

Figure 4-12. Linked list allocation using a file allocation table

in main memory.
Tanenbaum, Modern Operating Systems 3 e, (c) 2008 Prentice-Hall, Inc. All rights reserved. 0-13-6006639
 Linked List Allocation Using a Table in Memory

• FAT-File Allocation Table

• Advantage
– Can take use of the whole block
– Random access is easy
– only to store the starting block number
• Disadvantage
– To keep the entire table in memory
– Can’t scale well
 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
 i-nodes
• Advantage
– i-node need only be in memory when the
corresponding file is open; file table grows linearly
with the disk
• Disadvantage
– Each i-node has fixed size
 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, Modern Operating Systems 3 e, (c) 2008 Prentice-Hall, Inc. All rights reserved. 0-13-6006639
 Implementing Directories (2)

Figure 4-15. Two ways of handling long file names in a directory.

(a) In-line. (b) In a heap.
Tanenbaum, Modern Operating Systems 3 e, (c) 2008 Prentice-Hall, Inc. All rights reserved. 0-13-6006639
 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, Modern Operating Systems 3 e, (c) 2008 Prentice-Hall, Inc. All rights reserved. 0-13-6006639
Disk Space Management Block Size (1)

Figure 4-20. Percentage of files smaller than a given size

(in bytes).
Tanenbaum, Modern Operating Systems 3 e, (c) 2008 Prentice-Hall, Inc. All rights reserved. 0-13-6006639
 Disk Space Management Block Size (2)

Figure 4-21. The solid curve (left-hand scale) gives the data rate
of a disk. The dashed curve (right-hand scale) gives the disk
space efficiency. All files are 4 KB.
Tanenbaum, Modern Operating Systems 3 e, (c) 2008 Prentice-Hall, Inc. All rights reserved. 0-13-6006639
 Keeping Track of Free Blocks (1)

Figure 4-22. (a) Storing the free list on a linked list. (b) A bitmap.
Tanenbaum, Modern Operating Systems 3 e, (c) 2008 Prentice-Hall, Inc. All rights reserved. 0-13-6006639
 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, Modern Operating Systems 3 e, (c) 2008 Prentice-Hall, Inc. All rights reserved. 0-13-6006639
 The MS-DOS File System (1)

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

Tanenbaum, Modern Operating Systems 3 e, (c) 2008 Prentice-Hall, Inc. All rights reserved. 0-13-6006639
 FAT versions
• FAT comes up with 3 versions:
– FAT 12
– FAT 16
– FAT 32
– Differ in how many bits a disk address contains
– Block size also varies: 512B, 1K, 2K,4K,…,32K
 The MS-DOS File System (2)

Figure 4-32. Maximum partition size for different block sizes. The
empty boxes represent forbidden combinations.
Tanenbaum, Modern Operating Systems 3 e, (c) 2008 Prentice-Hall, Inc. All rights reserved. 0-13-6006639
 The UNIX V7 File System (1)

Figure 4-33. A UNIX V7 directory entry.

Tanenbaum, Modern Operating Systems 3 e, (c) 2008 Prentice-Hall, Inc. All rights reserved. 0-13-6006639
 The UNIX V7 File System (2)

Figure 4-34. A UNIX i-node.

Tanenbaum, Modern Operating Systems 3 e, (c) 2008 Prentice-Hall, Inc. All rights reserved. 0-13-6006639
 The UNIX V7 File System (3)

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

Tanenbaum, Modern Operating Systems 3 e, (c) 2008 Prentice-Hall, Inc. All rights reserved. 0-13-6006639
 exercises
• Consider a disk with 1 MB per track, a rotation
time of 8.33 msec, and an average seek time
of 5 msec. Then what is the time to read a
block of k bytes?
 exercise
• Consider the idea behind Fig.4-21, for a disk
with a mean seek time of 8msec, a rotational
rate of 15,000 rpm, and 264,144 bytes per
track. What are the data rate for block sizes of
1KB, 2KB and 4KB, respectively?
 Exercise
• How many disk operations are needed to fetch
the i-node for the file
/usr/ast/courses/os/handout.t? Asume that
the i-node for the root directory is in memory,
but nothing else along the path is in memory.
Also assume that all directories fit in one disk
block.