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
An allocation method refers to how disk blocks are allocated for files:
Each file occupies a set of contiguous blocks on the disk.
Simple – only starting location (block #) and length (number of blocks) are required.
Wasteful of space (dynamic storage-allocation problem).
Files cannot grow.
Contiguous Allocation of Disk Space
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.
Each file is a linked list of disk blocks: blocks may be scattered anywhere on the disk.
Brings all pointers together into the index block.
Example of Indexed Allocation
Need index table
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).