10.2 Directory Implementation

Linear list of file names with pointer to the data blocks.

       1. simple to program

       2.  time-consuming to execute

Hash Table – linear list with hash data structure.

       1. decreases directory search time

       2. collisions – situations where two file names hash to the same location

       3. fixed size

Allocation Methods

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

Contiguous allocation

Linked allocation

Indexed allocation

Contiguous Allocation

Each file occupies a set of contiguous blocks on the disk.

Simple – only starting location (block #) and length (number of blocks) are required.

Random access.

Wasteful of space (dynamic storage-allocation problem).

Files cannot grow.

Contiguous Allocation of Disk Space

Extent-Based Systems

Many newer file systems (I.e. Veritas File System) use a modified contiguous allocation scheme.

Extent-based file systems allocate disk blocks in extents.

An extent is a contiguous block of disks. Extents are allocated for file allocation. A file consists of one or more extents.

Linked Allocation

Each file is a linked list of disk blocks: blocks may be scattered anywhere on the disk.

 block =        

Linked Allocation

File-Allocation Table

Indexed Allocation

Brings all pointers together into the index block.

Example of Indexed Allocation

Need index table

Random access

Dynamic access without external fragmentation, but have overhead of index block.

Mapping from logical to physical in a file of maximum size of 256K words and block size of 512 words. We need only 1 block for index table.

Mapping from logical to physical in a file of unbounded length (block size of 512 words).

Linked scheme – Link blocks of index table (no limit on size).