File System Implementation Flashcards
How does the OS implement a file system?
Disks provide the bulk of secondary storage.
Data transferred block at a time from disk.
File system imposed on secondary storage for convenience.
What types of File System data structures are there?
On-disk structures
- Arrangement of data on the physical storage device
In-memory structures.
- OS structures held in memory.
List the on-disk structures?
- Boot control block
- File control Block
- Directory
- Volume
What is the Boot control block?
Contains the information needed to boot an OS from a disk
Collection of blocks holding a memory image.
What is a Volume Control Block
Structure describing how storage device is separated
Contains partition size, location of free blocks and FCBs
What does the directory structure do?
Organises files.
What is the FCB?
File control block, describes individual file.
Contains:
Permissions, dates, owner, group, ACL, size and data block numbers.
What are the in-memory structures?
Table listing storage volumes in use, and cache of recently accessed directories.
System-wide open file table and Per-Process file table
Fastest structure
How are files created?
- Allocate new FCB
- Read appropriate directory into memory
- Update with file name and FCB.
- Write directory back to disk.
How are files opened?
- Traverse directory structure to obtain FCB with file name/dir path given.
- Copy FCB from disk into System-wide open file table.
- Add pointer to per-process open file table.
- Return File Descriptor
How are files read?
Transfer data blocks in secondary storage to memory by finding them from the System-wide open-file table.
What does a Virtual File System do?
Allows UNIX/linux to support the use of multiple different file systems.
Require concurrent access to multiple file systems, data can be stored on a number of different devices and can have different implementations
What does the VFS allow for?
The same system call interface can be used for different types of file system.
Defines file system operations and semantics
How does VFS abstract the file system?
Builds a single directory tree composed of multiple file systems.
Distinguishes local files from remote ones, activating local file-system-specific operations on ones it knows.
What are the objects that make up the VFS?
- Inode
- File
- Superblock
- Dentry
What is an Inode
Represents an individual file in a file system
What is a file object (VFS)
Represents an open file
What is a superblock object?
Represents an entire file system
What is a Dentry object?
Represent an individual directory entry.
How does the DFS allow access to it’s objects?
Defines an interface for each object type, and a set of operations on the object. This is an abstraction over each file system’s implementation.
List the disk allocation methods.
- Contiguous allocation
- Linked allocation
- Indexed allocation
How is data accessed sequentially when using contiguous allocation
Usually no head movement to get next block, assuming nothing else is using the disk.
Move one track when switching cylinders
How is data accessed directly when using contiguous allocation
Access i’th block of file starting at block b, b+i
How are files created when using contiguous allocation?
Dynamic storage allocation problem, find first/best fit.
How are files expanded when using contiguous allocation?
Have to copy whole file to a larger space, may run up against other files in the sequential memory space.
What is the effect on external fragmentation when using contiguous allocation?
Need to compact information in sequential space, very expensive.
Performed off-line and relatively infrequently.
How is data accessed sequentially when using linked allocation?
Need to move head in order to get next block, which can be anywhere on the disk.
How is data accessed directly when using linked allocation?
Not possible, have to read file sequentially to get to required position. Location of i’th block stored in block i - 1.
What are the advantages of linked allocation?
File creation and expansion are easy. No external fragmentation problem.
What are the disadvantages of linked allocation?
Slower access time because linked list has to be traversed in order to find the node.
What is clustering in linked allocation?
Allocate blocks in sequential cluster, reducing space overhead and head movement.
Increased internal fragmentation as not every file may fit into space.
What is the File Allocation Table?
Variation on linked allocation.
Section of disk at beginning of volume holds FAT, one entry per disk block and indexed by block number.
How does FAT help find files?
Directory contains block number of first block of file.
Table entry indexed by that block number and contains block number of next block.
Last block has EOF value.
(Basically jumps around LL to each node that is in the same file)
How are blocks accessed sequentially when using indexed allocation?
Same as linked allocation. Head movement overhead.
How are blocks directly accessed when using indexed allocation?
Address of any block can be calculated from the index.
Address of block i in the i’th entry of the index.
When happens when files are created when using indexed allocation?
Index block allocated, keeps the mapping between index and memory location.
What are the the drawbacks of using indexed allocation?
There is unused space in each index block
How is file expansion done when using indexed allocation?
Select free block and update index block.
Index block may fill up.
Can have have linked list of index blocks or multi-level index.
What is multi-level indexing?
n level block points to n+1 blocks.
Number of levels, n, determines maximum file size.
What is a hybrid-scheme?
Combination of indexing and multi-level indexing.
FCB implementation. First 15 pointers of index block stored in file’s inode.
First 12 point to direct blocks. Next three point to indirect blocks.
- Single indirect block
- Double indirect block.
- Triple indirect block
How is maximum file size calculated?
block size * 2^10 (for 32-bit block addresses)
How does the file system inode table work?
Entry for each inode
inodes are addressed by their index in the table.
What is a (hard) link?
When more than one directory entry exists for a single inode.
Link count kept in inodes. When count == 0 block can be freed. This only works on Acyclic structures.
Cant make hard link to dir.
What is a symbolic link?
Soft link, file containing the path to the link target.
When can consistency issues arise?
As file systems read, modfy and ptentially delay write-back for some time then if the system crashes there can be consistency issues.
fsck checks consistency of files.
What are the features of a journaling file system?
Meta-data updates are written sequentially to journal, a log stored in disk. Write occurs before updating the file system.
Transaction-oriented approach
What happens when a transaction written to the journal is committed?
System call returns and log entries are replayed across the actual file system structures.
Completed transaction are removed from the log
How does a journaling file system recover from a crash?
> = 0 transactions in log, replay log entries to make file system consistent and undo changes made by partially executed transaction.
What is the drawback of journaling?
Overheads - write meta-data twice.
