Subject: Operating System

Topic: File Management

Difficulty: High

• Files are usually stored on secondary storage devices such as disk. These files are then called back when needed.
• As part of their implementation, files must be stored in the hard disk. This has to be done in such a way that the disk space is utilized effectively and the files can be accessed quickly.
• There are three methods of file allocation
  • Contiguous allocation
  • Linked allocation
  • Indexed allocation
• Contiguous Allocation:
  • Contiguous allocation requires that each file occupy a set of contiguous blocks on the disk. The word contiguous means continuous
  • Because of contiguous allocation, there is minimal or no disk-head movement which reading/writing the blocks of the file.
  • The seek time is minimal over here. Consequently, access time of a file and the I/O performance is greatly improved.

• To access a file, there we only need to know the starting location and length of the file which are stored in the directory as shown in the figure.
  • It has certain problems associated with it:

a) Finding the space for a new file (usually done with First fit and Best Fit Algorithms)

b) Problem of external fragmentation. It occurs whenever free space is broken

c) into tiny chunks.

d) Compaction (which is a solution for fragmentation) can take up lot of time and may need system to be down, wherein normal operation will not be permitted.

e) Determining space to be allocated for file, especially if it needs to grow. (for e.g. the size of a Word file grows on increasing as new data is typed in)

• Linked Allocation:
  • This method solves the problems associated with contiguous allocation.
  • Here the blocks of a single file can be scattered anywhere on the disk. The reason because the entire file is implemented as a Linked List.
  • Here every file is an element of Linked List (similar to concept of Linked List in Data Structures).
  • The directory maintained by the OS contains a pointer to the first and the last blocks of a file.
  • Each block of a file contains a pointer to the next block after it in the list.
  • For creating a new file, we need to just create a new entry in the directory and not to search for sufficient space as in contiguous.
  • The free space management system allocates space to a block for writing and is then appended to the end of the List.
  • To Read a file, we need to follow the pointers from each block.
  • Advantages include no external fragmentation, size of file need not be declared at start, a file can grow as long as free blocks are available on disk.
  • Disadvantages: It works perfectly for Sequential access only, space needs to be allocated in block for pointers, error in pointer links can lead to Invalid read.

• Indexed allocation:
  • In indexed allocation method, all the pointers (pointing to the next block in the Linked list) are gathered together into one location known as Index Block.
  • In the earlier method (i.e. Linked Allocation) the pointers along with the blocks were scattered across the disk and needed to be retrieved in order by visiting each block for access the file.
  • This problem gets eliminated here.
  • Each file has an index block of its own, which is an array of disk-block addresses.
  • The $k^{th}$ entry of the index-block is a pointer to the $k^{th}$ block of the file.
  • When a file is created initially, all pointers in the index block are set to null value. As new blocks are written, the pointers are modified accordingly.
  • Indexed allocation supports direct access and does not suffer from any external fragmentation.
  • Indexed allocation suffers from the problem of wasted space. E.g. if a file is made up of two blocks only, then a huge amount of space will be wasted.