Wednesday, September 10, 2008

File Allocation Methods

One main problem in file management is how to allocate space for files so that disk space is utilized effectively and files can be accessed quickly. Three major methods of allocating disk space are:
* Contiguous Allocation
* Linked Allocation
* Indexed Allocation.
Each method has its advantages and disadvantages. Accordingly, some systems support all three (e.g. Data General's RDOS). More commonly, a system will use one particular method for all files.

Contiguous File Allocation
  • Each file occupies a set of contiguous block on the disk
  • Allocation using first fit/best fit.
  • A need for compaction
  • Only starting block and length of file in blocks are needed to work with the file
  • Allows random access
  • Problems with files that grow.

Linked File Allocation

  • Each file is a linked list of blocks
  • NO external fragmentations
  • Effective for sequential access.
  • Problematic for direct access

File Allocation Table (FAT)

  • Variation of the link list(MS/DOS and OS/2)

- A section of the disk at the beginning of each partition (Volume) is set aside to contain a FAT
- FAT has one entry for each disk block, pointing to the next block in the file.
- The link list is implemented in that section
- Actual file blocks contain no links

Indexed File Allocation

  • Indexed allocation is bringing all the pointers together
  • Much more effective for direct access
  • Inefficient for small files