File Organization and Processing
Lecture 6
File System Implementation
Mohamed Mead
Linked Allocation
Each file is a linked list of disk blocks: blocks may be
scattered anywhere on the disk
Linked Allocation
Linked allocation solves all problems of contiguous allocation.
The directory contains a pointer to the first and last blocks of the
file. For example, a file of five blocks might start at block 9 and
continue at block 16, then block 1, then block 10, and finally block 25
Linked Allocation
Each block contains a pointer to the next block.
These pointers are not made available to the user.
Thus, if each block is 512 bytes in size, and a disk address
(the pointer) requires 4 bytes, then the user sees blocks
of 508 bytes.
Linked Allocation
To create a new file, we simply create a new entry in the
directory.
With linked allocation, each directory entry has a pointer
to the first disk block of the file.
This pointer is initialized to null to signify an empty file.
The size field is also set to 0.
Linked Allocation
A write to the file causes the free-space
management system to find a free block, and this
new block is written to and is linked to the end of
the file.
To read a file, we simply read blocks by following
the pointers from block to block.
Linked Allocation
There is no external fragmentation with linked allocation,
and any free block on the free-space list can be used to
satisfy a request.
The size of a file need not be declared when the file is
created.
A file can continue to grow as long as free blocks are
available.
Consequently, it is never necessary to compact disk space.
Linked Allocation
The major problem is that it can be used 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 read, and some require
a disk seek.
Consequently, it is inefficient to support a direct-access
capability for linked-allocation files.
Linked Allocation
Another disadvantage is the space required for the
pointers.
If a pointer requires 4 bytes out of a 512-byte block, then
0.78 percent of the disk is being used for pointers, rather
than for information.
Linked Allocation
another problem of linked allocation is reliability.
Recall that the files are linked together by pointers
scattered all over the disk, and consider what would happen
if a pointer were lost or damaged.
A bug in the operating-system software or a disk hardware
failure might result in picking up the wrong pointer.
This error could in turn result in linking into the free-space
list or into another file.
Linked Allocation
One solution is to use doubly linked lists, and another is to
store the file name and relative block number in each block.
However, these schemes require even more overhead for
each file.
Linked Allocation
An important variation on linked allocation is the use of a
file-allocation table (FAT).
This simple but efficient method of disk-space allocation
was used by the MS-DOS operating system.
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.
Linked Allocation
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 it reaches the last block,
which has a special end-of-file value.
Linked Allocation
An unused block is indicated by a table value of 0.
Allocating a new block to a file is a simple
finding the first 0-valued table entry and replacing the
previous end-of-file value with the address of the new
block.
Linked Allocation
for a file consisting of disk blocks 217, 618, and 339.
FAT Limitations
FAT12 - used on volumes smaller than 16MB (Floppies)
FAT16 - used on volumes 16MB to 2GB (Hard Drives)
FAT32 - used on volumes 512MB to 8TB (Hard Drives)
