slides11 - File System Implementation Flashcards
1
Q
Directory
A
- symbol table that holds information about all directories and files - links name of file/directory to file control block (FCB) which points to data blocks
2
Q
Two directory implementations
A
- Linear list:
- linear list/linked list of names with pointers
- need to search whole list at creation time for uniqueness
- empty flag to mark if directory entry is being used - Hash table:
- Issues: size, handling collisions
3
Q
File space allocation methods (3)
A
- Contiguous allocation
- Linked allocation
- Indexed allocation
4
Q
Contiguous allocation
A
- Files must allocate contiguous blocks
- Directory contains first block and length
- Sequential + direct access
- External fragmentation (total free memory is enough but its not contiguous)
- Difficult to grow a file if no space
- Compacting necessary
5
Q
Linked allocation
A
- Linked list of storage
- Directory contains first and last blocks of file
- Each block contains pointer to next block
- Sequential access; no direct access
- No external fragmentation
- Weak file system integrity if a block gets corrupted
6
Q
File allocation table FAT
A
- Some blocks on disk set aside for FAT
- Directory points to FAT entry
- Direct access + no external fragmentation
7
Q
Indexed allocation
A
- Directory contains pointer to index block
- All indexes of data blocks collected into index block
- Direct access + no external fragmentation
- Internal fragmentation -> waste space
8
Q
iNodes
A
- File metadata
- 12 direct blocks (1 disk access)
- 1 single indirect block (2 disk accesses)
- 1 double indirect block (3 disk accesses)
- 1 triple indirect block (4 disk accesses)
- If B block size and disk pointer is 4 bytes -> largest file size is
12 X B + (B/4) x B + (B/4)^2 x B + (B/4)^3 x B
9
Q
Free space management
A
- Use bit map to keep track of free storage
- Each block represented by 1 bit
