File System Implementation Flashcards
What are the 4 layers in the big picture of the file system?
Top: file-system interface
VFS interface
Local/Remote file system
Disk/network
There are ___ aspects for implementing a file system
two
The two aspects for implementing a file system are _____ ________ and ______ _______
data structures, access methods
For file system data structures, there can be ________ data structures or _________ structures
On-disk, in-memory
On-disk data structures hold the directory ______, number of ______, _______ of free blocks, _____ information, etc
structure, blocks, location, boot
In-memory structures are for _______ file system at run-time and ________
managing, caching
Access methods handle ____ made by processes to open, close, read, write, etc
calls
We organize the disk by dividing it into ______
blocks
Disk block sizes are ______
fixed
Disk blocks are addressed from 0 to ____
N-1
What are the two types of disk blocks?
Data blocks and metadata blocks
Data blocks file actual ____
data
Metadata blocks ________ data
manage
What are example of metadata blocks?
inode, superblock, bitmaps, etc
What are data regions?
It reserves blocks to store user data
The file system has to track which data blocks track _____, size of ____, the file’s ______, etc
files, files, owner
The file system has to reserve some space for a ______ table
inode
An inode table is an _____ of on-disk inodes
array
If the inode table occupies 5 4kb blocks, and the inode size is 256 byte, how many inodes does the file system contain?
80
We can use ______ to track whether inodes or data blocks are free or allocated
bitmaps
In a bit map, a 0 indicates ______ and 1 indicates _____
free, in-use
A _____ bitmap tracks data regions and an ______ bitmap tracks inode regions
data, inode
What does a superblock contain? Give examples
Necessary information for the particular file system. number of inodes, begin location of inode table, etc
When mounting a file system, the OS will read the _________ first to initialize information
superblock
Each inode is referred to by an inode _______
number
We can calculate where the inode is on the disk with the inode _______
number
To get the inode location, what two steps do we do?
- Calculate offset into the inode region
(inode #) * sizeof(inode) - Add start address of the inode table
Disks are not byte addressable, but ______ addressable
sector
On disk, the address advances by ______ size, which is typically ____ bytes
sector, 512
If we need to fetch something at 20kb, the sectorSize would be __
40
An inode contains ______ that stores information about actual file data
metadata
The indoe may contain direct _______ to data blocks belonging to the file
pointers
Since inode size is limited, the number of _______ is limited, and the ____ ____ is limited
pointers, file size
Why do we use a multi-level index?
To store larger files
REVIEW MULTI-LEVEL INDEX SLIDES
REVIEW MULTI-LEVEL INDEX SLIDES
Contiguous allocation has each file occupy a set of contiguous _______
blocks
In contiguous allocation, we only need the _____ _______ and length
start address
What are two pros of contiguous allocation?
- Simple
- Efficient sequential and random access
What are three cons of contiguous allocation?
- External fragmentation
- Files may not be able to grow
- Compaction is possible but expensive
In linked allocation, a file is a _______ _____ of blocks
linked list
In linked allocation, blocks can be anywhere and each block has a _______ to the next block
pointer
In linked allocation, we need the _____ and ____ block and we must traverse the chain to reach the ________ block
start, end, desired
What are three pros of linked allocation?
- Simple (only need 2 addresses)
- Doesn’t waste space
- Support dynamically growing files
What are two cons of linked allocation?
- Expensive random access
- Reliability
What is the process that happens when we do open(“/foo/bar”)?
- Traverse the pathname and thus locate the desired inode
- Begin at the root of the file system (/)
- In most Unix file systems, the root inode number is 2
- Filesystem reads in the block that contains inode number 2
- Look inside of it to find pointer to data blocks (contents of the root)
- By reading in one or more directory data blocks, It will find “foo” directory
- Traverse recursively the path name until the desired inode(“bar”)
- Check file permissions, allocate a file descriptor for this process and returns file descriptor to user
When the inode is consulted for a read, we need to update the ______ _________ time and the file ______
last accessed, offset
When we close a file, we need to _______ file descriptor, and use _____ to persist file data
deallocate, fsync
Closing a file does not perform any disk ____
I/O
write() may allocate new _______
blocks
write() needs to update the data ______ and data _______
block, bitmap
write() needs what 5 I/O operations?
1 to read data bitmap
1 to write to the bitmap
2 to read and then write the inode
1 to write the block itself
In addition to the five I/Os required for write(), there could be more I/O required for file _______ and space allocation for _______ entry
creation, directory