File Systems Flashcards
secondary storage
backs up main memory
usually a disk
file systems provide
a mechanism for storage of data and programs on the disk and accessing them
files are mapped by OS to physical address
different storage devices
- some transfer a character or a block of character at a time
- some can be accessed sequentially/randomly
- some transfer data synchronously/asynchronously
- some can be read-only/read-write
essential requirements for long-term information storage
- It must be possible to store a very large amount of information
- Information must survive termination of process using it
- Multiple processes must be able to access information concurrently
file system
- A way to organise and (persistently) store information
- An abstraction over storage devices:
- Hard disk, SSD, network, RAM, …
- Organised in files and (typically) directories
file system flow
user program syscall -> virtual fs -> page cache -> fs driver (FAT, NFTS…) -> buffer cache ->storage
files
- Abstract storage nodes, i.e. logical storage unit
- a file is a named collection of related information that is recorder on secondary storage
file types
regular: directories, soft links
special: device files, metadata…
file structure
OS perspective: files as streams of bytes
program’s perspective: archives, executables, etc.
file naming
extensions
name length
case sensitivity
once a file is named it becomes independent
file types
- executable
- object
- source
- batch
- text
- word processors
- library
8.print or view - archive
- multimedia
executable file
exe, com, bin or none
ready-to-run machine language program
object
obj, o
compiled machine language, not linked
source code
c, cpp, java, py
j
batch
bat, sh
commands to the command interpreter
text
txt, doc
word processor
wp, doc, rtf
library
lib, a
libraries f routines for programmes
print or view
ps, pdf, jpg
ASCII or binary in a format for printing or viewing
archive
arc, zip, tar
related files grouped into one file sometimes compressed for archiving and storage
multmedia
mp3,m mp4, avi
binary file containing audio or A/V info
MAC OS X file identification
each file has a type specified with it to identify its type
UNIX file identification
magic number stored at the beginning of some files to indicate the type
file attributes
name: human readable
identifier
type
location
size
creation date
last modified
…
Where are file attributes stored?
in file control block
file operations
- create & delete
- open & close
- read & write
- append
- seek
- get & set attributes
- rename
creating a file
- check if space is available and find spot for it
- make an entry in the directory
writing a file
- system call with the name of the file and the info to write
- OS finds the file
- write from the write pointer
- update pointer
reading a file
- sys call name of the file and which part to read
- OS locates the file
- read from the pointer
- update pointer
seek a file
- OS finds the file
- current-file-position pointer is repositioned to a given value
deleting a file
- OS finds the file
- release the space occupied by that file
truncating a file
- keep all attributes same except file length → set to zero
- release the file space
ENOENT
file doesn’t exist
EBADF
bad file descriptor
opening a file returns
a handel (file descriptor) for future operations
unlink(“file”)
removing a file
rename(“file”, “new_name”)
renaming
chmod(“file”, 0755)
change file permission
chown(“file”, uid, gid)
change owner
sequential file access
- information is processed in order
- most common method in editors, compilers etc.
- read: read next → advance pointer
- write: write next → appends to the end of the file → move pointer to new end of file
direct file access (relative access)
- the file is viewed as a numbered sequence of blocks or records
- great for accessing large amount of information → databases
- read: read n → reads from block n
- write: write n → writes to block n
directories
- Data structures organising and maintaining information about files
- Often stored as file entries with special attributes
- disk is split into: partitions/slices/minidisk → combined to form volumes
- each volume can be treated as a virtual disk → allows running multiple OSs and having multiple file systems
- partition: directory + files
device directory
keeps information about the files in the system
.
current dir
..
parent dir
dir in Unix
/
dir in Windows
\
single level directory system +/-
+ simple implementation
+ file operations are easily done: creating, deleting, repositioning, renaming
+ searching is fast for a small number of smaller files
- more files, bigger files
- all files must have unique names
- users can’t have same file names
- poor organisation → difficult to keep track of all the files (user view)
hierarchical directory systems
- allows users to create their own subdirectories and organise their files more efficiently
- current directory: contains most of the files that are of current interest to the process
- if a file is needed that isn’t in it the whole path name needs to be specified or cd
- absolute path: from root
- relative path: from current directory
deleting a non empty dir
first delete all contents
rm -r in UNIX
removes the whole dir
mounting a file system
- OS is given the mount point (location within the file structure where the fs is to be attached)
- OS verifies the device contains a valid fs
- OS notes there is another fs
file sharing
- a user-oriented OS must
- multiple users
- system must mediate the file-sharing
- the system can either
- allow a user to access files of other users by default
- require that a user specifically grant access to the files
owner + group
owner: can change attributes and grant access
group: can execute a subset of operations defined by the owner
remote file systems
- methods of remote file-transfer
- manually transferring files between system via programs like FTP (File Transfer Protocol
- DFS (Distributed File System)
- data stored on a server
- accessed as if it was on the local client machine
- WWW
- a browser is needed to gain access to the remote files
the client-server model
- machine containing the files: server
- machine seeking access: client
- client identification (e.g. IP address - unsafe, encryption keys - not scalable)
file system layout
MBR + partition table + disk partitions
-> boot block + superblock + free space mgmt + i-nodes + root dir + files and dirs
MBR
master boot
partition types
primary
extended
sub-partitions
contiguous allocation
- Store files as a contiguous stream of bytes → each file occupies a set of contiguous blocks
- Requires max file size, prone to fragmentation
contiguous allocation +/-
+ easy file access
+ for sequential access: the fs remembers the disk address of the last block referenced
+ for direct access: access block b + i (block start + index)
- finding space for a new file is difficult
- (external) fragmentation
block-based allocation strategies
linked list
FAT
indexed disk space allocation
i-nodes
i-nodes with indirect blocks
linked-list alloaction
each file is a linked list of disk blocks
the dir contains a pointer to the first and last blocks of the files
+ no fragmentation
+ the size of a file doesn’t need to be declared when the file is created
+ creating, reading and writing to files can be easily done
- efficient only for sequential access files
- requires a lot of space - pointers
File allocation table
linked list allocation using a file allocation table in main memory
the table has an entry for each disk block and is indexed by block number
the dir entry contain the block number of the first block of the file
the table entry indexed by that number contains the block number of the next block in the file
allocating a new block to a file with FAT
- find the first 0-valued table entry
- replace the previous end-of-file value with the address of the new block
- replace 0 with the end-of-file value
indexed disk space alloacation
- the index block: an array of disk-block addresses (i-th entry points to the i-th block of the file)
- dir entry: points to the index block
- support direct access without external fragmentation
- it suffers from wasted space
- one whole block for each file
- some larger files require bigger index blocks
- linked scheme: multiple index blocks
- multilevel index
- combined scheme
UNIX i-nodes
- when a fs is created so is a specific amount if inodes
- inode structure
- file info:
- mode: file type and permissions
- owners: access details
- timestamps: access, modification…
- size block
- count: num of blocks
- block info:
- direct blocks: direct address pointing to data blocks
- single indirect: points to an index block
- double indirect: points to one index block whick points to other index blocks → data blocks
- triple indirect
inode
a data structure in UNIX OS that contains important information about the files
on-disk structures
boot control block
volume control block
directory structure per file system
per file FCV (inode)
boot control block
one for each volume
empty -> no OS in volume
volume control block
- number of blocks in the partition
- size of the blocks
- free blick count
- free-blick pointers
- free file control block count and fcb pointers
directory structure per file system
file names and the associated inode numbers
per file FCB (inode)
file attributes
in-memory structures
the data is loaded at mount time and discarded at dismount
includes:
1. in memory mount table
2. the system wide open-file table
3. in-memory dir-structure cache
4. per-process open-file table
in memory mount table
info about each mounted volume
the system wide open-file table
contains a copy of the FCB of each open file
in-memory dir-structure cache
holds the dir info that were recently accessed
per-process open-file table
contains a pointer to the appropriate entry in the system-wide open-file table
object-oriented techniques
- allows very different file system types to be implemented
- layers:
- the file-system interface
- VFS interface
- consists of several dozen func- tion calls that the VFS can make to each file system to get work done
- the layer implementing the file system type
directory implementation
linear list: simple but slow
hash table: faster but not scalable
opening files
Before a file can be read, it must be opened. The operating system uses the path name to locate the directory entry which provides information for locating disk blocks
File Attributes Storage
- Attributes can be stored directly in directory entries or in i-nodes.
- Storing in directory entries can be space-consuming.
- i-nodes can make entries shorter with benefits in organisation.
file name length
- Modern systems support long, variable-length names.
- Simpler designs set a fixed character limit (e.g., 255), but this is inefficient.
- Variable-size directories accommodate length differences but can lead to unused space gaps.
directory Entry Structures
- Fixed-size entries with a heap for file names ensure new entries fit but require additional management.
- Directories are typically searched linearly, which can be slow for long directories.
improving Search Efficiency
Hash Tables: Allow faster searches by hashing file names to specific entries
Caching: Results of previous searches can be stored and quickly accessed, advantageous when a few files have frequent lookups
Trade-offs: Hash tables provide quicker lookups but are complex to administer. Caching speeds access at the cost of increased memory usage
FAT12/FAT16 layout
boot sector + reserver + FAT #1 + FAT #2 + root dir + clusters
- Reserved later used for FS information
- FAT #1/#2: preallocated File Allocation Tables
- Preallocated root directory
- Clusters represent addressable blocks:
- FAT contains chains indexed by starting cluster
FAT entry
32 bytes
file name 8
extension 3
attributes 1
reserved 10
time 2
date 2
first block number 2
size 4
UNIX dir entry
16 bytes
i node 2
file name 14
- Directory entry stores only name and #i-node
- Attributes are stored in the i-node
- One i-node per file, first i-node is the root
hard links
reference a shared file (i-node)
- The file is removed only with no hard links left
- Space-efficient (only 1 directory entry per hard link)
- Good to manage shared files across owners
soft (or symbolic) links
reference a file name
- Removing the file renders its soft links invalid
- Less space-efficient (need 1 i-node per soft link)
- More flexible (can reference file names across FSes)
block size
- Important speed-space tradeoff to consider
- Larger block sizes allow transferring more data per block
- Better overall data rates
- Smaller block sizes reduce space overhead for small files
- Less fragmentation
free block management
- free-space list
- creating a file
- search list
- allocate the new list
- space is removed from the list
- deleting a file
- the disk space is added to the free list
- bitmap
- each block is represented by 1 bit
- 1 - free, 0 - allocated
- easy finding the first free block
- unless kept in main memory it is inefficient
- size is fixed even if disk is full
- each block is represented by 1 bit
- linked list
- all the free blocks are linked together
- less metadata the fuller the disk gets → more efficient
- grouping
- store the addresses of n free blocks in the first free blocks
- the first n-1 of these blocks are actually free, the last block contains the addresses can now be found quickly
minimising disk access with caching
- Buffer cache: Cache disk blocks in RAM
- Page cache: Cache VFS pages (before going to driver)
- Often same data as buffer cache, so OS may merge them
cache management
- Caches have LRU semantics adapted to:
- Blocks with poor temporal locality
- Critical blocks for file system consistency
- Write-through caching vs. periodic syncing
- Disk read-ahead: read blocks that may be used soon
minimising disk access with log-structure fs
- idea: Optimise for frequent small writes
- Collect pending writes in a log segment with i-nodes, entries, blocks
- Segments are often flushed to disk and can be large (e.g., 1MB)
- i-node map to find i-nodes in the log
- Garbage collection to reclaim old log entries
Minimise Seek Time: HDD Layout Management
- Not an issue for modern SSDs
- Seek time is constant
- Important for traditional HDDs
- Different strategies to minimise HDD seek time:
- Try to allocate files contiguously
- Defragment disk
- Store small file data “inline” in i-node
- Spread i-nodes over the disk rather than at the start
disk failure
bad blocks
whole-disk errors
power failure
(meta)data inconsistency written to disk
software bugs
bad (meta)data written to disk
user errors
rm *.o
lost or stolen computer
remote file system failure modes
network failures
failures in the connection
networking implementation issues
recovery
1. maintain a state at both client and server side
2. stateless DFS
fs backups
- Backups to disk are generally made to handle one of two potential problems:
- Recover from disaster
- Recover from stupidity
backup properties
Incremental(changes from last backup) vs. full(all data)
Online vs. offline
Physical(disk blocks) vs. logical(files)
Compressed vs. uncompressed
Local vs. remote
fs consistency check
- Programs like fsck and chkdsk try to find (and fix) consistency errors in file
system metadata:- Corrupt values
- Used blocks also marked as free
- Blocks not marked as free nor used
- Blocks being used multiple times
journaling file systems
- Idea: Use “logs” for crash recovery
- First write transactional operations in log
- E.g., removing a file:
- Remove file from its directory
- Release i-node to the pool of free i-nodes
- Return all disk blocks to pool of free blocks
- E.g., removing a file:
- After crash, replay operations from log
- Single operations need to be idempotent
- Should support multiple, arbitrary crashes
- Journaling widely used in modern FSes (e.g., Ext4, NTFS)
creating a file system
- format partition
- create basic, FS specific, layout
- unix: mkfs
