File Allocation Method

We all save our files in the hard disk. Hence, to make the maximum out of the disk space the files have to be stored in an efficient manner. This also ensures quick access when the data from these files is required. There are three file allocation method:

  • Contiguous File Allocation
  • Linked File Allocation
  • Indexed File Allocation

Contiguous Allocation

In contiguous file allocation method each file:

Contiguous file allocation method
  • File occupy contiguous blocks
  • Directory entry contains
    • Filename
    • Starting block
    • Length (total blocks)
  • Access possible
    • Sequential
    • Direct
  • Problems
    • Finding space for new file
    • External fragmentation
    • Determining space requirement of a file

In the above example

  • File “sum” occupies blocks 2, 3 and 4.
  • File“jeep” occupies blocks 7, 8, 9, 10 and 11
  • File “song” occupies blocks 15 and 16.

Linked Allocation

In linked file allocation method each file:

linked file allocation method
  • Directory structure contains
    • Pointer to the first and last block of file
  • Advantages
    • No external fragmentation
    • No issue with increase in file size
  • Disadvantages
    • Only sequential access
    • Reliability – loss of a pointer
    • Space required for pointers
    • Solution: make cluster of blocks
    • Problem: internal fragmentation

In the above example

  • For file “car” the first data block is 8
  • Block 8 contains data and a pointer to the next data block, which is block 3.
  • Block 3 points to the next data block i.e. 16
  • Block 16 is the last block as pointed in the directory entry.

Indexed Allocation

For each file, the indexed file allocation method:

Linked file allocation method
  • Clubs all the pointers into one block – index block
  • Directory entry contains
    • Filename
    • Index block number
  • Access
    • Direct
  • Issue
    • Size of index block
    • Sol: multilevel indexing

In the above example

  • Block 8 is the index block which contains pointers to all the data blocks i.e., 10, 4, 12 and 19.
  • -1 entry in block 8 means it can contain entries to two other data blocks.
  • Indexing can be single level (in above example), two level or multi level depending upon the file size

Performance

  • Contiguous
    • Requires only 1 access to get a disk block
  • Linked
    • Requires i disk reads to read ith block
  • Indexed
    • Depends on
      • level of indexing
      • Size of file
      • Position of desired block

Example of File Allocation Method

Consider a file currently consisting of 100 blocks. Assume that the file control block (and the index block, in the case of indexed allocation) is already in memory. Calculate how many disk I/O operations are required for contiguous, linked, and indexed (single-level) allocation strategies, if, for one block, the following conditions hold. In the contiguous-allocation case, assume that there is no room to grow in the beginning, but there is room to grow in the end. Assume that the block information to be added is stored in memory.
a. The block is added at the beginning.
b. The block is added in the middle.
c. The block is added at the end.

Share your answers in the comments section below

PPT

The above discussion is summarized in the form of a PPT with animations below.
Note: Click within the slide area for animations. Clicking on the “next” slide button will not display any animation

Previous                                   Next
File Management                     Free Space Management

Leave a Reply

Your email address will not be published. Required fields are marked *