Scribd
Upload
32 views18 pages

11 File System Implementation

Uploaded by

Prajwal Kandel
Copyright
© © All Rights Reserved
We take content rights seriously. If you suspect this is your content, claim it here.
Available Formats
Download as PPT, PDF, TXT or read online on Scribd
32 views18 pages

11 File System Implementation

Uploaded by

Prajwal Kandel
Copyright
© © All Rights Reserved
We take content rights seriously. If you suspect this is your content, claim it here.
Available Formats
Download as PPT, PDF, TXT or read online on Scribd
You are on page 1/ 18

File System Implementation

Allocation Methods
 An allocation method refers to how disk blocks are
allocated for files:

 Contiguous allocation

 Linked allocation

 Indexed allocation
Contiguous Allocation
 Contiguous allocation requires that each file occupy a set
of contiguous blocks on the disk.
 Disk addresses define a linear ordering on the disk. With
this ordering, assuming that only one job is accessing the
disk, accessing block b + 1 after block b normally requires
no head movement.
 When head movement is needed (from the last sector of
one cylinder to the first sector of the next cylinder), the
head need only move from one track to the next.
 Thus, the number of disk seeks required for accessing
contiguously allocated files is minimal, as is seek time
when a seek is finally needed.
 Contiguous allocation of a file is defined by the disk
address and length (in block units) of the first block.
 Accessing a file that has been allocated contiguously is
easy.
Contiguous Allocation
 Contiguous allocation has some problems, however. One
difficulty is finding space for a new file.
 Contiguous allocation suffer from the problem of external
fragmentation.
Contiguous Allocation of Disk
Space
Linked Allocation
 With linked allocation, each file is a linked list of disk blocks;
the disk blocks may be scattered anywhere on the disk. The
directory contains a pointer to the first and last blocks of the
file.

block = pointer
Linked Allocation (Cont.)
 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
 Each block contains a pointer to the next block. These
pointers are not made available to the user
 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.
 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 that file is
created.
 A file can continue to grow as long as free blocks are
available.
Linked Allocation
File-Allocation Table
Indexed Allocation
 However, in the absence of a FAT, linked allocation
cannot support efficient direct access, since the pointers
to the blocks are scattered with the blocks themselves all
over the disk and must be in order.
 Indexed allocation solves this problem by bringing all the
pointers together into one location: the index block.
 Each file has its own index block, which is an array of
disk-block addresses.
Example of Indexed Allocation
Free-Space Management
 Since disk space is limited, we need to reuse the space
from deleted files for new files, if possible.
 To keep track of free disk space, the system maintains a
free-space list.
 The free-space list records all free disk blocks—those not
allocated to some file or directory.
 To create a file, we search the free-space list for the
required amount of space and allocate that space to the
new file.
 This space is then removed from the free-space list. When
a file is deleted, its disk space is added to the free-space
list.
Bit map or bit vector
 Frequently, the free-space list is implemented as a bit map or
bit vector. Each block is represented by 1 bit.
 If the block is free, the bit is 1; if the block is allocated, the bit
is 0.
 For example, consider a disk where blocks 2, 3, 4, 5, 8, 9, 10,
11, 12, 13, 17, 18, 25,26, and 27 are free and the rest of the
blocks are allocated.
 The free-space bit map would be
 001111001111110001100000011100000 ...
 The main advantage of this approach is its relative simplicity
and its efficiency in finding the first free block or n consecutive
free blocks on the disk, indeed, many computers supply bit-
manipulation instructions that can be used effectively for that
purpose.
 Bit vectors are inefficient unless the entire vector is kept in
main memory (and is written to disk occasionally for recovery
needs).
 Keeping it in main memory is possible for smaller disks but not
necessarily for larger ones.
 Bit vector (n blocks)
0 1 2 n-1
…

0  block[i] free
bit[i] =

1  block[i] occupied

 Bit map requires extra space


 Example:
block size = 212 bytes
disk size = 230 bytes (1 gigabyte)
n = 230/212 = 218 bits (or 32K
bytes)
 Easy to get contiguous files
Linked list
 Another approach to free-space management is to link
together all the free disk blocks, keeping a pointer to the
first free block in a special location on the disk and
caching it in memory.
 This first block contains a pointer to the next free disk
block, and so on.
 In our earlier example, we would keep a pointer to block 2
as the first free block. Block 2 would contain a pointer to
block 3, which would point to block 4, which would point
to block 5, which would point to block 8, and so on .
 However; this scheme is not efficient; to traverse the list,
we must read each block, which requires substantial I/O
time. Fortunately, traversing the free list is not a frequent
action. Usually, the operating system simply needs a free
block so that it can allocate that block to a file, so the first
block in the free list is used.
Linked Free Space List on Disk
Grouping
 A modification of the free-list approach is to store the
addresses of n free blocks in the first free block.
 The first n—1 of these blocks are actually free.
 The last block contains the addresses of another n free
blocks, and so on.
 The addresses of a large number of free blocks can now be
found quickly, unlike the situation when the standard
linked-list approach is used.
Counting
 Another approach is to take advantage of the fact that,
generally, several contiguous blocks may be allocated or
freed simultaneously, particularly when space is allocated
with the contiguous-allocation algorithm or through
clustering.
 Thus, rather than keeping a list of n free disk addresses,
we can keep the address of the first free block and the
number n of free contiguous blocks that follow the first
block.
 Each entry in the free-space list then consists of a disk
address and a count.
 Although each entry requires more space than would a
simple disk address, the overall list will be shorter, as long
as the count is generally greater than 1.

You might also like