Page 159 - DCAP403_Operating System

Operating System

Notes 8.9.2 Linked Allocation

The problems in contiguous allocation can be traced directly to the requirement that the spaces
be allocated contiguously and that the files that need these spaces are of different sizes. These

requirements can be avoided by using linked allocation.

In linked allocation, each file is a linked list of disk blocks. The directory contains a pointer to the

first and (optionally the last) block of the file. For example, a file of 5 blocks which starts at block

4, might continue at block 7, then block 16, block 10, and finally block 27. Each block contains a
pointer to the next block and the last block contains a NIL pointer. The value -1 may be used for
NIL to differentiate it from block 0.
With linked allocation, each directory entry has a pointer to the fi rst disk block of the fi le. This

pointer is initialized to nil (the end-of-list pointer value) to signify an empty file. A write to a fi le
removes the first free block and writes to that block. This new block is then linked to the end of

the file. To read a file, the pointers are just followed from block to block.

There is no external fragmentation with linked allocation. Any free block can be used to satisfy a
request. Notice also that there is no need to declare the size of a file when that file is created. A fi le

can continue to grow as long as there are free blocks. Linked allocation, does have disadvantages,

however. The major problem is that it is inefficient to support direct-access; it is effective only for

sequential-access fi les. To find the ith block of a file, it must start at the beginning of that fi le and

follow the pointers until the ith block is reached.
Note Note that each access to a pointer requires a disk read.
Another severe problem is reliability. A bug in OS or disk hardware failure might result in
pointers being lost and damaged. The effect of which could be picking up a wrong pointer and
linking it to a free block or into another fi le.

Figure 8.7: Diagram of Linked Allocation

152 LOVELY PROFESSIONAL UNIVERSITY