CONTIGUOUS ALLOCATION
Method: Lay down the entire file on contiguous sectors of the disk. Define by a
dyad <first block location, length >.

a) Accessing the file requires a minimum of head movement.
b) Easy to calculate block location: block i of a file, starting at disk address b, is b + i.
c) Difficulty is in finding the contiguous space, especially for a large file. Problem is one of dynamic allocation (first fit, best fit, etc.) which has external fragmentation. If many files are created/deleted, compaction will be necessary.
It's hard to estimate at create time what the size of the file will ultimately be. What happens when we want to extend the file we must either terminate the owner of the file,
or try to find a bigger hole.

LINKED ALLOCATION

• Each file is a linked list of disk blocks, scattered anywhere on the disk. At file creation time, simply tell the directory about the file. When writing, get a free block and write to it, enqueueing it to the file header.

• There's no external fragmentation since each request is for one block. Method can only be effectively used for sequential files. Pointers use up space in each block. Reliability is not high because any loss of a pointer loses the rest of the file.

A File Allocation Table is a variation of this.
It uses a separate disk area to hold the links.
This method doesn't use space in data blocks. Many pointers may remain in memory.
A FAT file system is used by MS-DOS.

INDEXED ALLOCATION
• Each file uses an index block on disk to contain addresses of other disk blocks used by the file.
• When the i th block is written, the address of a free block is placed at the i th position in the index block.
• Method suffers from wasted space since, for small files, most of the index block is wasted The optimum size of an index block is
• If the index block is too small, we can:
a) Link several together
b) Use a multilevel index

UNIX keeps 12 pointers to blocks in its header. If a file is longer than this, then it uses pointers to single, double, and triple level index blocks. We need a way to keep track of space currently free. This information is needed when we want to create or add (allocate) to a file. When a file is deleted, we need to show what space is freed up.

Free Space Management

BIT VECTOR METHOD
• Each block is represented by a bit
1 1 0 0 1 1 0 means blocks 2, 3, 6 are free.
• This method allows an easy way of finding contiguous free blocks. Requires the overhead of disk space to hold the bitmap.
• A block is not REALLY allocated on the disk unless the bitmap is updated.

FREE LIST METHOD
• Free blocks are chained together, each holding a pointer to the next one free.
• This is very inefficient since a disk access is required to look at each sector.
GROUPING METHOD
• In one free block, put lots of pointers to other free blocks. Include a pointer to the next
block of pointers.
COUNTING METHOD
• Since many free blocks are contiguous, keep a list of dyads holding the starting address of a "chunk", and the number of blocks in that chunk.
• Format < disk address, number of free blocks >