Page 232 - DCAP103_Principle of operating system

Unit 6: File Management

Linked allocation does have disadvantages. However, the major problem is that it can be used Notes
effectively only for sequential-access files. To find the ith block of a file, we must start at the
beginning of that file and follow the pointers until we get to the ith block. Each access to a
pointer requires a disk.

Figure 6.9: File Allocation Table

Directory entry
Test ... 217
Name Start block
0

217 618

339

339
618 339

Number of disk blocks –1
FAT

An important variation on linked allocation is the use of a file-allocation table (FAT). This simple
but efficient method of disk-space allocation is used by the MS-DOS and OS/2 operating systems.
A section of disk at the beginning of each volume is set aside to contain the table. The table has
one entry for each disk block and is indexed by block number. The FAT is used in much the
same way as a linked list. The directory entry contains the block number of the first block of the
file. The table entry indexed by that block number contains the block number of the next block
in the file. This chain continues until the last block, which has a special end-of-file value as the
table entry. Unused blocks are indicated by a 0 table value. Allocating a new block to a file is
a simple matter of finding the first 0-valued table entry and replacing the previous end-of-file
value with the address of the new block. For a file consisting of disk blocks 217, 618, and 339.
The FAT allocation scheme can result in a significant number of disk head seeks, unless the
FAT is cached. The disk head must move to the start of the volume to read the FAT and find
the location of the block in question, then move to the location of the block itself. In the worst
case, both moves occur for each of the blocks. A benefit is that random-access time is improved,
because the disk head can find the location of any block by reading the information in the FAT.

6.10.2 File Allocation Methods—Chained
The opposite extreme to contiguous allocation is chained allocation. Here, the blocks allocated
to a file form a linked list (or chain), and as a file’s length is extended (by appending to the file),
a new block is allocated and linked to the last block in the file.

LOVELY PROFESSIONAL UNIVERSITY 225