Indexed Allocation

at e
• Indexed allocation solves problems of contiguous and linked allocation, by bringing all the
pointers together into one location: the index block.

ge G
l e d
n ow
[Link]
 at e
• Each file has its own index block, which is an array of disk-block addresses. The ith
entry in the index block points to the ith block of the file. The directory entry
contains the address of the index block. To find and read the ith block, we use

ge G
the pointer in the ith index-block entry.

• When the file is created, all pointers in the index block are set to null. When the

d
ith block is first written, a block is obtained from the free-space manager, and its

e
address is put in the ith index-block entry.

w l
• This point raises the question of how large the index block should be. Every file

o
must have an index block, so we want the index block to be as small as possible.
If the index block is too small, however, it will not be able to hold enough

n
pointers for a large file.

[Link]
 at e
• Linked scheme: To allow for large files, we can link together several index blocks. For
example, an index block might contain a small header giving the name of the file and a
set of the first 100 disk-block addresses. The next address (the last word in the index

ge G
block) is null (for a small file) or is a pointer to another index block (for a large file).

• Multilevel index. A variant of linked representation uses a first-level index block to

d
point to a set of second-level index blocks, which in turn point to the file blocks. To
access a block, the operating system uses the first-level index to find a second-level

l e
index block and then uses that block to find the desired data block. This approach could
be continued to a third or fourth level, depending on the desired maximum file size.

w
n o [Link]
 t e
• Combined scheme. Another alternative, used in UNIX-based file systems, is to keep the first,
say, 15 pointers of the index block in the file’s inode.

a
G
• The first 12 of these pointers point to direct blocks; that is, they contain addresses of blocks

e
that contain data of the file. Thus, the data for small files do not need a separate index block.

dg
• The next three pointers point to indirect blocks. The first points to a single indirect block,
which is an index block containing not data but the addresses of blocks that do contain data.

e
l
• The second points to a double indirect block, which contains the address of a block that
contains the addresses of blocks that contain pointers to the actual data blocks. The last

w
pointer contains the address of a triple indirect block.

n o [Link]
• Advantage

at e
• Indexed allocation supports direct access, without suffering from external
fragmentation, because any free block on the disk can satisfy a request for
more space.

• Disadvantage

ge G
d
• Indexed allocation does suffer from wasted space, however. The pointer

e
overhead of the index block is generally greater than the pointer overhead of
linked allocation.

w l
n o [Link]
used if no external fragmentation is allowed? (GATE-2017) (1 Marks)
I. Contiguous II. Linked III. Indexed
t e
Q In a file allocation system, which of the following allocation scheme(s) can be

a
(a) I and III only

ge G
d
(b) II only

(c) III only

w l e
o
(d) II and III only

n [Link]
Q The index node (inode) of a Unix-like file system has 12 direct, one

at e
single-indirect and one double-indirect pointers. The disk block size is 4 kB, and the
disk block address is 32-bits long. The maximum possible file size is (rounded off to

ge G
1 decimal place) ______ GB. (GATE-2014) (2 Marks)

l e d
n ow
[Link]
 at e
Q A file system with 300 Gbyte disk uses a file descriptor with 8 direct block addresses, 1 indirect
block address and 1 doubly indirect block address. The size of each disk block is 128 Bytes and
the size of each disk block address is 8 Bytes. The maximum possible file size in this file system is

G
(GATE-2012) (2 Marks)

e
(A) 3 Kbytes

(B) 35 Kbytes

(C) 280 Bytes

e dg
(D) Dependent on the size of the disk

w l
n o [Link]
(GATE-2008) (1 Marks)
(A) contiguous allocation (B) linked allocation

at e
Q The data blocks of a very large file in the Unix file system are allocated using

ge G
(C) indexed allocation

e d
(D) an extension of indexed allocation

l
n ow
[Link]
 at e
Q A Unix-style i-node has 10 direct pointers and one single, one double and one
triple indirect pointer. Disk block size is 1 Kbyte, disk block address is 32 bits, and
48-bit integers are used. What is the maximum possible file size? (GATE-2004) (2
Marks)
(A) 224 bytes

ge G
(B) 232 bytes

l e d
n ow
(C) 234 bytes

(D) 248 bytes

[Link]
the file depends on (GATE-2002) (1 Marks)
(a) the size of the blocks, and the size of the address of the blocks.

at e
Q In the index allocation scheme of blocks to a file, the maximum possible size of

e G
(b) the number of blocks used for the index, and the size of the blocks.

g
d
(c) the size of the blocks, the number of blocks used for the index, and the size of

e
the address of the blocks.

w
(d) None of the above
l
n o [Link]