Different file system can have different implementations, but they have essential common triats.
File System: Creating a mapping between files(a sequence of uninterrupted untyped byte) and blocks on storage device. (Block itself is another abstraction to the storage device)
File System Role
The main task of file system is to translate : from user interface functions to disk interface fucntions.
File System Implementation
Key aspects:
- Data Structures : data structures on disk and data structures in memory
- Access methods
Data structure must be on disk since disk is involatile. The metadata needed by the OS for mapping also must be on disk.
Disk Data Structures
- Data Region(actual information) -> occupies most space in FS
- User data
- free space
- Meta data
- Indicates the specific space used for user data and free space(Inode)
- house keeping stuff
We use metadata to track files, specifically, by the inode of the metadata.
Structure Implementation
- Free-list
- Bitmaps
- Data structure where each bit indicates if corresponding object is free or in use
- 1 = in use ; 0 = free
- we associate each block to a bit in bitmap
- We have inode bitmap and data bitmap
Superblock is the block used to track the metadata.
Allocation of files to blocks
Based on inode.
Criteria for good strategy
- Amount of fragmentation (external and internal)
- Ability to grow file over time
- Sequential access performance
- Random access performance
- Metadata overhead
Strategy:
Contiguous allocation
- Strategy: Allocate file data blocks contiguously on disk
- Metadata: Starting block + size of file
- Fragmentation: severe external frgamentation
- Growing: may be time intense
- Sequential access: good
- Random access: good
- Metadata overhead: low since just two number needs for matadata
The only case to use this is of the read-only.
Impractical for file system since it change files alot.
Extent-based allocation
Trying to take advantage of the fragmentation but get rid of the holes.
- Stratgey: Allocate multiple contiguous extent per file.
Linked-List Allocation
Each block likes a node in the linked list.
- Strategy: Allocate linked-list of blocks.
- Metadata: Location of first block of file, plus each block contains pointer to next block.
FAT(File-Allocation Tables)
Exactly like the linked list with the difference that pointers are store in a different data structure.
Pointers are stored in FAT.
Since Table can be stored in cache, the accession time dies down.
Index Allocation
Index Allocation with Indirect Blocks
Support Large files.
slower since an indirect node is leading in, 2 times slower. 4 more blocks.
Directory stores as files.
If the file size is larger than the size that inode can represent, then the open will fail.
Operations of data stuctures on disk
Inefficient.
If a new file is created, there’s no content in it, only inode of that file will be created.
Open it before write. The above graph omits the steps for openning the file.
Open it before read. The above graph omits the steps for openning the file.
Operations of data stuctures in memory
Cache
- Finxed contiguous area of kernel memory.
- Size = max number of chache blocks x block size
- A large chunck pf memeory of the machine
- In general, write behind is used
- For user data is OK
- For metadata, depends
Cache Directory
index in the cache pointing to the disk data (usually hash table)
(System-Wide) Active File Table
Indicates what files are in use in the system.
- One array for the entire system
- One entry per onpen file
- Each entry contains
- file inode
- Additional Information
- Reference count of number of file opens
(Per-Process) Open File Table
- One array per process
- One entry per file open of that process
- Indexed by file descriptor $fd$
- Each entry contains
- Pointer to file inode in active file table
- File pointer $fp$
- Additional Information
Open File Table and Active File Table are put together in use.
Open File Table is in the perspective of the process(PCB); Active File Table is in the perspective of the kernel.
UID is a component of the inode.
The two tables are combined instead of singally use is because of the concurrency. We wish the process can access to the file concurrently.
Combination of Memory Structure with Disk Structure
Most of the times, data bitmap and inode bitmap are in chache,even some specific inode.
If the data(info) is already cached, there’s no need to read again.
Setting up the FS
- By default, OS sees all storage devices as
- Chunks of unallocated space
- which are unusable
- Cannot start writing file to a blank drive
- Need to set up the FS first(Disk Parititioning)
Disk Partition(Slicing)
- FS needs a “container”(partition) on the storage device
- Partition allows different FS to be installed on same OS.
- Each partition appears to OS as a logical disk
- Disk stores partition info in partition table
- OS reads partition table before anyother parts of the disk
Mounting a FS
FS needs to be mounted for OS to acces its files.(Make OS know where the file system is).
- Mounting attaches FS to a directory
- Directory is called mount point
All the file systems would be attached to a root file system.
Mounting does not delete the files under the mount point; it only makes the file system can’t see the files.
If we unmount, the appearance goes to initial state.
Booting
- BIOS lookes for clues on what it needs to start OS. BIOS checkes boot block first.
- A fixed location on disk (usually sector 0), containing boot loader and partition table.
- Read by BIOS on machine boot.
Alternative File Access Method: Memory Mapping
Memory mapping: a way to not use the file system.