Page 157 - DCAP403_Operating System

Operating System

Notes allocation are important to know. In the former, each file is stored as a contiguous block of data

on the disk, in the latter, the file is kept as a linked list of disk blocks - the first word of each block
is used as a pointer to the next one. UNIX uses i-nodes to keep track of which blocks belong
to each file. An i-node is a table that lists the attributes and disk addresses of the fi le’s blocks.

The first few disk addresses are stored in the i-node itself, so for small files, all the necessary

information is in the i-node itself which is fetched from disk to main memory when the fi le is

opened. For larger files, one of the addresses in the i-node is the address of a disk block called
a single indirect block which contains additional disk addresses. If this is insuffi cient, another
address called the double indirect block may contain the address of a block that contains a list of
single indirect blocks.

In order to create the illusion of files from the block oriented disk drives, the OS must keep track
of the location of the sectors containing the data of the file. This is accomplished by maintaining

a set of data structures both in memory and on disk that keep track of where data is allocated to

each file, and the name to file mapping encoded in the directory structure.

The simplest allocation of files is a contiguous allocation of sectors to each file. A directory entry
would contain the name of the fi le, its size in bytes and the fi rst and last sector of the fi le. This

results in a fast read of a given file and a compact representation, but also of sizable external
fragmentation which can require compaction to correct. The analog in memory management is
the base/limit register system of memory allocation.
As with memory management, you turn to more complex data structures and non contiguous
allocation to solve the problems. I can use a bitmap to record the allocated and unallocated sectors

on the disk, and keep a list of sectors assigned to each file in its directory entry. This isn’t often

used, because it makes searching for free space difficult and replicates the allocation information
in the file itself. (When it is used, the bitmap is kept both on disk and in memory).

The other system that is used in file systems and in memory management is a linked list. A

simple mechanism is to take one integer out of every file block and us that as the next sector

following this one (similar to linking the holes in memory management).
This is an improvement over bitmaps in efficiency of storage use, but has a signifi cant drawback

in that finding the proper sector for a random access is expensive. Finding the right sector
containing a random sector is as expensive as reading to that point in the fi le.
To solve this we collect the sector pointers into a table (usually cached in main memory) separate
from the fi les. Now the OS can follow the separate pointers to fi nd the appropriate sector for a
random access without reading each disk block. Furthermore, the conceptual disk blocks and the
physical disk blocks now have the same size. This is essentially the FAT file system of MS-DOS.

Another organization is one optimized for small fi les (which research has shown dominate the

file system, in the sense that most files are small) while accommodating large ones. The system is
called the index node or i-node system. An i-node contains the attributes of the fi le and pointers
to its first few blocks.

The last 3 sector pointers are special. The first points to inode structures that contain only pointers

to sectors; this is an indirect block. The second to pointers to pointers to sectors (a double indirect
node) and the third to pointers to pointers to sectors (triple indirect).
This results in increasing access times for blocks later in the fi le. Large files will have longer

access times to the end of the file. I-nodes specifically optimize for short fi les.

8.9 Allocation Methods

One main problem in file management is how to allocate space for files so that disk space is

utilized effectively and files can be accessed quickly. Three major methods of allocating disk

150 LOVELY PROFESSIONAL UNIVERSITY