Modern Operating Systems by Herbert Bos ...
Modern_Operating_Systems_by_Herbert_Bos_and_Andrew_S._Tanenbaum_4th_Ed.pdf-M ODERN O PERATING S YSTEMS
Showing 354-355 out of 1137
Modern Operating Systems by Herbert Bos and Andrew...
Modern_Operating_Systems_by_Herbert_Bos_and_Andrew_S._Tanenbaum_4th_Ed.pdf-M ODERN O PERATING S YSTEMS
Modern Operating Systems by Herbert...
Modern_Operating_Systems_by_Herbert_Bos_and_Andrew_S._Tanenbaum_4th_Ed.pdf-M ODERN O PERATING S YSTEMS
Page 354
SEC. 4.5
Block size
0.5 KB
2 MB
1 KB
4 MB
2 KB
8 MB
128 MB
4 KB
16 MB
256 MB
1 TB
8 KB
512 MB
2 TB
16 KB
1024 MB
2 TB
32 KB
2048 MB
2 TB
Figure 4-31.
Maximum partition size for different block sizes. The empty boxes
represent forbidden combinations.
In addition to supporting larger disks, the FAT -32 file system has twoother ad-
vantages overFAT -16. First,an 8-GB disk using FAT -32 can be a single partition.
Using FAT -16 it has to be four partitions, which appears to the Windows user as the
, and
logical disk drives. It is up to the user to decide which file to
place on which drive and keep track of what is where.
The other advantage of FAT -32 overFAT -16 is that for a givensize disk parti-
tion, a smaller block size can be used. For example, for a 2-GB disk partition,
FAT-16 must use 32-KB blocks; otherwise with only 64K available disk addresses,
it cannot cover the whole partition.
In contrast, FAT -32 can use, for example,
4-KB blocks for a 2-GB disk partition. The advantage of the smaller block size is
that most files are much shorter than 32 KB.
If the block size is 32 KB, a file of 10
bytes ties up 32 KB of disk space.
If the average file is, say, 8 KB, then with a
32-KB block, three quarters of the disk will be wasted, not a terribly efficient way
to use the disk. With an 8-KB file and a 4-KB block, there is no disk wastage, but
the price paid is more RAM eaten up by the FAT .
With a 4-KB block and a 2-GB
disk partition, there are 512K blocks, so the FAT must have 512K entries in memo-
ry (occupying 2 MB of RAM).
MS-DOS uses the FAT to keep track of free disk blocks. Any block that is not
currently allocated is marked with a special code.
When MS-DOS needs a new
disk block, it searches the FAT for an entry containing this code. Thus no bitmap or
free list is required.
4.5.2 The UNIX V7 File System
Even early versions of UNIX had a fairly sophisticated multiuser file system
since it was derived from MULTICS. Below we will discuss the V7 file system,
the one for the PDP-11 that made UNIX famous. We will examine a modern
UNIX file system in the context of Linux in Chap. 10.
The file system is in the form of a tree starting at the root directory, with the
addition of links, forming a directed acyclic graph. File names can be up to 14

Page 355
characters and can contain any ASCII characters except / (because that is the sepa-
rator between components in a path) and NUL (because that is used to pad out
names shorter than 14 characters).
NUL has the numerical value of 0.
A UNIX directory entry contains one entry for each file in that directory. Each
entry is extremely simple because UNIX uses the i-node scheme illustrated in
Fig. 4-13.
A directory entry contains only two fields: the file name (14 bytes) and
the number of the i-node for that file (2 bytes), as shown in Fig. 4-32. These pa-
rameters limit the number of files per file system to 64K.
File name
Figure 4-32.
A UNIX V7 directory entry.
Like the i-node of Fig. 4-13, the UNIX i-node contains some attributes. The at-
tributes contain the file size, three times (creation, last access, and last modifica-
tion), owner, group, protection information, and a count of the number of directory
entries that point to the i-node. The latter field is needed due to links.
Whenever a
new link is made to an i-node, the count in the i-node is increased. When a link is
removed, the count is decremented.
When it gets to 0, the i-node is reclaimed and
the disk blocks are put back in the free list.
Keeping track of disk blocks is done using a generalization of Fig. 4-13 in
order to handle very large files. The first 10 disk addresses are stored in the i-node
itself, so for small files, all the necessary information is right in the i-node, which
is fetched from disk to main memory when the file is opened. For somewhat larger
files, one of the addresses in the i-node is the address of a disk block called a
gle indirect block
This block contains additional disk addresses.
If this still is
not enough, another address in the i-node, called a
double indirect block
, contains
the address of a block that contains a list of single indirect blocks. Each of these
single indirect blocks points to a few hundred data blocks.
If even this is not
enough, a
triple indirect block
can also be used. The complete picture is given in
Fig. 4-33.
When a file is opened, the file system must take the file name supplied and
locate its disk blocks. Let us consider how the path name
is looked
up. We will use UNIX as an example, but the algorithm is basically the same for
all hierarchical directory systems. First the file system locates the root directory.
In UNIX its i-node is located at a fixed place on the disk. From this i-node, it
locates the root directory, which can be anywhere on the disk, but say block 1.
After that it reads the root directory and looks up the first component of the
, in the root directory to find the i-node number of the file
. Locating

Ace your assessments! Get Better Grades
Browse thousands of Study Materials & Solutions from your Favorite Schools
Concordia University
Great resource for chem class. Had all the past labs and assignments
Leland P.
Santa Clara University
Introducing Study Plan
Using AI Tools to Help you understand and remember your course concepts better and faster than any other resource.
Find the best videos to learn every concept in that course from Youtube and Tiktok without searching.
Save All Relavent Videos & Materials and access anytime and anywhere
Prepare Smart and Guarantee better grades

Students also viewed documents