1
Q
secondary storage
A
backs up main memory
usually a disk
2
Q
file systems provide
A
a mechanism for storage of data and programs on the disk and accessing them
files are mapped by OS to physical address
3
Q
different storage devices
A
- 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
4
Q
essential requirements for long-term information storage
A
- 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
5
Q
file system
A
- A way to organise and (persistently) store information
- An abstraction over storage devices:
- Hard disk, SSD, network, RAM, …
- Organised in files and (typically) directories
6
Q
file system flow
A
user program syscall -> virtual fs -> page cache -> fs driver (FAT, NFTS…) -> buffer cache ->storage
7
Q
files
A
- Abstract storage nodes, i.e. logical storage unit
- a file is a named collection of related information that is recorder on secondary storage
8
Q
file types
A
regular: directories, soft links
special: device files, metadata…
9
Q
file structure
A
OS perspective: files as streams of bytes
program’s perspective: archives, executables, etc.
10
Q
file naming
A
extensions
name length
case sensitivity
once a file is named it becomes independent
11
Q
file types
A
- executable
- object
- source
- batch
- text
- word processors
- library
8.print or view - archive
- multimedia
12
Q
executable file
A
exe, com, bin or none
ready-to-run machine language program
13
Q
object
A
obj, o
compiled machine language, not linked
14
Q
source code
A
c, cpp, java, py
j
15
Q
batch
A
bat, sh
commands to the command interpreter
16
Q
text
A
txt, doc
17
Q
word processor
A
wp, doc, rtf
18
Q
library
A
lib, a
libraries f routines for programmes
19
Q
print or view
A
ps, pdf, jpg
ASCII or binary in a format for printing or viewing
20
Q
archive
A
arc, zip, tar
related files grouped into one file sometimes compressed for archiving and storage
21
Q
multmedia
A
mp3,m mp4, avi
binary file containing audio or A/V info
22
Q
MAC OS X file identification
A
each file has a type specified with it to identify its type
23
Q
UNIX file identification
A
magic number stored at the beginning of some files to indicate the type
24
Q
file attributes
A
name: human readable
identifier
type
location
size
creation date
last modified
…
25
Where are file attributes stored?
in file control block
26
file operations
1. create & delete
2. open & close
3. read & write
4. append
5. seek
6. get & set attributes
7. rename
27
creating a file
1. check if space is available and find spot for it
2. make an entry in the directory
28
writing a file
1. system call with the name of the file and the info to write
2. OS finds the file
3. write from the write pointer
4. update pointer
29
reading a file
1. sys call name of the file and which part to read
2. OS locates the file
3. read from the pointer
4. update pointer
30
seek a file
1. OS finds the file
2. current-file-position pointer is repositioned to a given value
31
deleting a file
1. OS finds the file
2. release the space occupied by that file
32
truncating a file
1. keep all attributes same except file length → set to zero
2. release the file space
33
ENOENT
file doesn't exist
34
EBADF
bad file descriptor
35
opening a file returns
a handel (file descriptor) for future operations
36
unlink("file")
removing a file
37
rename("file", "new_name")
renaming
38
chmod("file", 0755)
change file permission
39
chown("file", uid, gid)
change owner
40
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
41
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
42
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
43
device directory
keeps information about the files in the system
44
.
current dir
45
..
parent dir
46
dir in Unix
/
47
dir in Windows
\
48
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)
49
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
50
deleting a non empty dir
first delete all contents
51
rm -r in UNIX
removes the whole dir
52
mounting a file system
1. OS is given the mount point (location within the file structure where the fs is to be attached)
2. OS verifies the device contains a valid fs
3. OS notes there is another fs
53
file sharing
- a user-oriented OS must
- multiple users
- system must mediate the file-sharing
- the system can either
1. allow a user to access files of other users by default
2. require that a user specifically grant access to the files
54
owner + group
owner: can change attributes and grant access
group: can execute a subset of operations defined by the owner
55
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
56
the client-server model
- machine containing the files: server
- machine seeking access: client
- client identification (e.g. IP address - unsafe, encryption keys - not scalable)
57
file system layout
MBR + partition table + disk partitions
-> boot block + superblock + free space mgmt + i-nodes + root dir + files and dirs
58
MBR
master boot
59
partition types
primary
extended
sub-partitions
60
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
61
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
62
block-based allocation strategies
linked list
FAT
indexed disk space allocation
i-nodes
i-nodes with indirect blocks
63
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
64
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
65
allocating a new block to a file with FAT
1. find the first 0-valued table entry
2. replace the previous end-of-file value with the address of the new block
3. replace 0 with the end-of-file value
66
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
67
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
68
inode
a data structure in UNIX OS that contains important information about the files
69
on-disk structures
boot control block
volume control block
directory structure per file system
per file FCV (inode)
70
boot control block
one for each volume
empty -> no OS in volume
71
volume control block
1. number of blocks in the partition
2. size of the blocks
3. free blick count
4. free-blick pointers
5. free file control block count and fcb pointers
72
directory structure per file system
file names and the associated inode numbers
73
per file FCB (inode)
file attributes
74
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
75
in memory mount table
info about each mounted volume
76
the system wide open-file table
contains a copy of the FCB of each open file
77
in-memory dir-structure cache
holds the dir info that were recently accessed
78
per-process open-file table
contains a pointer to the appropriate entry in the system-wide open-file table
79
object-oriented techniques
- allows very different file system types to be implemented
- layers:
1. the file-system interface
2. VFS interface
- consists of several dozen func- tion calls that the VFS can make to each file system to get work done
3. the layer implementing the file system type
80
directory implementation
linear list: simple but slow
hash table: faster but not scalable
81
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
82
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.
83
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.
84
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.
85
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
86
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
87
FAT entry
32 bytes
file name 8
extension 3
attributes 1
reserved 10
time 2
date 2
first block number 2
size 4
88
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
89
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
90
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)
91
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
92
free block management
- free-space list
- creating a file
1. search list
2. allocate the new list
3. space is removed from the list
- deleting a file
1. 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
- 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
93
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
94
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
95
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
96
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
97
disk failure
bad blocks
whole-disk errors
98
power failure
(meta)data inconsistency written to disk
99
software bugs
bad (meta)data written to disk
100
user errors
rm *.o
lost or stolen computer
101
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
102
fs backups
- Backups to disk are generally made to handle one of two potential problems:
1. Recover from disaster
2. Recover from stupidity
103
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
104
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
105
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
- 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)
106
creating a file system
- format partition
- create basic, FS specific, layout
- unix: mkfs
Operating Systems
flashcards
Decks in class (8)
# Cards
