File Systems, Pt. 2 Flashcards
Steps to Opening a File
- Search the directory to find the FCB
- May need to bring multiple directory blocks from disk if they’re not already cached
- Create an entry in the per-process open-file table (PFT)
- Check whether the system-wide open-file table has an entry for this file
- If it does, increment its reference count and make the entry in the PFT point to this entry
- If it doesn’t, create a new entry, set reference count to 1, make entry in PFT point to this entry
- Return a pointer (file descriptor) to the entry in the PFT
Steps to Creating a File
- Allocate a new FCB
- For faster file creation, FCBs are usually preallocated and a free one is found
- Read relevant directory blocks in memory
- Update blocks to reflect the new file and write back to disk
- Allocate free blocks for the data of the file
Common Allocation Methods
- Contiguous
- Linked
- Indexed
Contiguous Allocation
- Each file occupies a set of contiguous blocks
- Needs only start address and length
- Compaction is possible, but expensive
Pros and Cons of Contiguous Allocation
Pros: -Simple -Efficient sequential and random access (minimal disk head seeks) Cons: -External fragmentation -Files may not be able to grow
Linked Allocation
- A file is a linked list of blocks
- Blocks could be anywhere
- Each block has a pointer to the next block
- Need start block and end block to append file
Pros and Cons of Linked Allocation
Pros:
-Simple: Need only start and end addresses
-Doesn’t waste space except for pointers
-Supports dynamically growing files
Cons:
-Expensive random access (need to follow pointers from the start)
-Reliability: if one block is corrupted, the entire chain is broken
Indexed Allocation
Bring all pointers together in an index block
Pros and Cons of Indexed Allocation
Pros: -Supports random access -Supports dynamic growing of files -No external fragmentation Cons: -Overhead of index blocks -File of one or a few data blocks still needs an index block
Choosing Size of Index Blocks
- Small size may not fit some files
- Large size may waste space
- Use linked index blocks or multilevel indices
Linked Index Blocks
- Last word in index block points to another index block
- May need to traverse the index linked list (long access time)
Multilevel Index
- First-level index block points to a set of second-level index blocks which refer to data blocks
- Shorter access time but more space overhead
Combined Index Blocks
- Used by Unix
- Each file has an index block (inode) which contains:
- Pointers that point to data blocks directly for small files
- Pointers to index blocks that may point to another level of index blocks or to data blocks
How do we know where free blocks are?
- Bit Map (one bit for each block, 0 = occupied, 1 = free)
- Linked List
- Grouping (addresses of n free blocks are stored in the first block, the last block of that group contains the next n free blocks, etc)
- Counting (keep address of first free block and count the contiguous free blocks)
Crashes can leave file system in…
…an inconsistent state
