Department of Computer Science and Engineering
UIT-RGPV, Bhopal
Topic: File Allocation Methods
Course: Operating System
Outline
Introduction
Contiguous Allocation
Linked Allocation
Indexed Allocation
2 DoCSE, UIT-RGPV, Bhopal
Introduction
The File allocation methods define how the files are stored in
the disk blocks. There are three main disk space or file
allocation methods.
1. Contiguous Allocation
2. Linked Allocation
3. Indexed Allocation
The main idea behind these methods is to provide:
Efficient disk space utilization.
Fast access to the file blocks.
3 DoCSE, UIT-RGPV, Bhopal
1. Contiguous Allocation
Key Points:
Each file occupies a contiguous address space on disk.
Assigned disk address is in linear order.
Easy to implement.
External fragmentation is a major issue with this type of
allocation technique.
4 DoCSE, UIT-RGPV, Bhopal
Contiguous Allocation cont…
In this scheme, each file occupies a contiguous set of blocks
on the disk.
For example, if a file requires n blocks and is given a block b
as the starting location, then the blocks assigned to the file
will be: b, b+1, b+2,……b+n-1. This means that given the
starting block address and the length of the file (in terms of
blocks required), we can determine the blocks occupied by
the file.
The directory entry for a file with contiguous allocation
contains
1. Address of starting block
2. Length of the allocated portion.
5 DoCSE, UIT-RGPV, Bhopal
For Example: The file ‘mail’ in the following
figure starts from the block 19 with length = 6
[Link], it occupies 19, 20, 21, 22, 23, 24
blocks.
6 DoCSE, UIT-RGPV, Bhopal
Advantages & Disadvantages of Contiguous Allocation
Advantages:
Both the Sequential and Direct Accesses are supported by this. For direct
access, the address of the kth block of the file which starts at block b can
easily be obtained as (b+k).
This is extremely fast since the number of seeks are minimal because of
contiguous allocation of file blocks.
Disadvantages:
This method suffers from both internal and external fragmentation. This
makes it inefficient in terms of memory utilization.
Increasing file size is difficult because it depends on the availability of
contiguous memory at a particular instance.
7 DoCSE, UIT-RGPV, Bhopal
2. Linked Allocation
Key Points:
Each file carries a list of links to disk blocks.
Directory contains link / pointer to first block of a file.
No external fragmentation
Effectively used in sequential access file.
Inefficient in case of direct access file.
8 DoCSE, UIT-RGPV, Bhopal
Linked Allocation cont…
In this scheme, each file is a linked list of disk blocks which
need not be contiguous.
The disk blocks can be scattered anywhere on the disk.
The directory entry contains a pointer to the starting and the
ending file block.
Each block contains a pointer to the next block occupied by
the file.
9 DoCSE, UIT-RGPV, Bhopal
For Example: The file ‘jeep’ in following image shows
how the blocks are randomly distributed. The last block
(25) contains -1 indicating a null pointer and does not
point to any other block.
10 DoCSE, UIT-RGPV, Bhopal
Advantages of Linked Allocation
This is very flexible in terms of file size. File size can be
increased easily since the system does not have to look for a
contiguous chunk of memory.
This method does not suffer from external fragmentation.
This makes it relatively better in terms of memory utilization.
11 DoCSE, UIT-RGPV, Bhopal
Disadvantages of Linked Allocation
Because the file blocks are distributed randomly on the disk, a
large number of seeks are needed to access every block
[Link] makes linked allocation slower.
It does not support random or direct access. We cannot
directly access the blocks of a file. A block k of a file can be
accessed by traversing k blocks sequentially (sequential
access) from the starting block of the file via block pointers.
Pointers required in the linked allocation incur some extra
overhead.
12 DoCSE, UIT-RGPV, Bhopal
3. Indexed Allocation
Key Points:
Provides solutions to problems of contiguous and
linked allocation.
A index block is created having all pointers to files.
Each file has its own index block which stores the
addresses of disk space occupied by the file.
Directory contains the addresses of index blocks of
files.
13 DoCSE, UIT-RGPV, Bhopal
In this scheme, a special block known as the Index block contains the
pointers to all the blocks occupied by a file. Each file has its own index
block. The ith entry in the index block contains the disk address of the
ith file block. The directory entry contains the address of the index
block as shown in the image:
Example:
14 DoCSE, UIT-RGPV, Bhopal
Advantages & Disadvantages of Indexed Allocation
Advantages:
This supports direct access to the blocks occupied by the file
and therefore provides fast access to the file blocks.
It overcomes the problem of external fragmentation.
Disadvantages:
The pointer overhead for indexed allocation is greater than
linked allocation.
For very small files, say files that expand only 2-3 blocks, the
indexed allocation would keep one entire block (index block)
for the pointers which is inefficient in terms of memory
utilization. However, in linked allocation we lose the space of
only 1 pointer per block.
15 DoCSE, UIT-RGPV, Bhopal
Thank You
16 DoCSE, UIT-RGPV, Bhopal