Object-Oriented Programming
Operating Systems
Lecture 9b
Dr Ronald Grau School of Engineering and Informatics Spring term 2018
Previously
File systems
File systems implementation
Kernel data structures
Block allocation
1
Today
File System Management
File systems
Data consistency
Performance
Virtual file systems
2
Recap: Questions
Recap questions
1. What does the mount operation do?
2. What information does the kernel maintain for files used by processes?
3. What is reference counting in resource management?
4. What is the unit of storage allocation for files?
5. What is a file allocation table?
6. What is an i-node?
7. What is the difference between a hard and a soft link?
3
Recap: File abstraction
UNIX i-nodes
4
Recap: File abstraction
UNIX i-nodes
5
Accessing /usr/ast/mbox
Recap: File system implementation
Logical file system
Provides file interface (e.g., system calls)
File organisation module
Manages block allocation to files
E.g. i-nodes in UNIX
Basic file system
Block-based storage format
E.g. FAT-32, NTFS, ext4
I/O device drivers
Physical access to storage media
E.g. HD, DVD, USB
6
Storage devices
E.g., a hard disk
Low-level formatting:
info for disk controller,
e.g. tracks, sectors, ECCs for
fixing soft errors, bad blocks
7
Partition Tables
MBR (Master Boot Record)
Cylinder-Head-Sector
(CHS) addressing: 512MB limit
Maximum 15 partitions
(with logical partitions)
MBR-partition size limited to 2TB
Logical Block Addressing (LBA):
Today 48 or 64bit
8
Partition Tables
GPT (Globally unique identifiers PT)
Supported by all modern operating systems
9
File System Formats
Raw format
Just blocks, no file system
E.g. Linux swap space, some databases
High-level formatting:
Initialise volume with
file system data structures
10
File System Examples: FAT
FAT-12 (MS-DOS) directory entry
12 bit block number, 512B blocks size partition size 2MB
FAT-16: 16 bit cluster numbers, 32KB cluster size 2GB
FAT-32: 28 bit cluster numbers, 64KB cluster size 16TB
but 231 = 2GB file size (systems that support large files: 232 = 4GB)
No file permissions
11
File System Examples: ISO 9660
ISO 9660 (CD-ROM) directory entry
2KB blocks
Contiguous allocation (mostly)
Limitations:
Length of file names, file attributes, directory nesting, . . .
Rock Ridge (UNIX) and Joliet (Windows) extensions
12
How to choose the block size?
13
Effects of different block size
Mean file size
In 1984: 1.1KB
In 2005: 2.4KB
in 2017: ?
Internal fragmentation
4KB blocks: 10% largest files occupy 93% of utilised blocks
8KB blocks: 10% largest files occupy 90% of utilised blocks
Disk access time
Rotation speed
Seek time to position head
Small block size + non-contiguous allocation = unreasonably long access times
„defragmentation”
14
Data Storage Consistency
File system operations involve many writes (e.g. appending data in a file)
1. Update free blocks list to get a new block
2. Add pointer to that block and Increase size of file in i-node
3. Write data into block
System crash can lead to inconsistent data on storage device
How to detect inconsistencies:
E.g. UNIX fsck
Mark problems and try to recover
Drawback: time-consuming; data loss when recovery fails
Approaches: Log-Structured File Systems, RAID
15
Data Storage Consistency
Reusing ideas from database systems
Transactions
Log: Store changes on hard disk
Commit them in the background
On a crash, inconsistencies are limited to interrupted transactions
Some operations appear to be much faster
Also known as “journaling”
Examples: NTFS, ext4, . . .
16
Data Storage Consistency
Journaling FS example: ext4
48 bit block numbers, 4KB block size ?
32 bit i-node numbers; 64 bit for file size
128MB journal
17
Avoids fragmentation:
• Pre-allocation support
• Disk partitioned into block groups
Data Storage Consistency
Journaling FS example: ext4
Journaling Block Device (JBD): generic journaling layer
Journal entries:
Descriptor
(contains destination block number)
Data (data / metadata)
Commit
Revocation
Journaling modes:
journal / ordered / writeback
If interrupted, transaction is replayed
18
Data Storage Consistency
Redundant Arrays of Independent Disks (RAID)
Objectives
Increase reliability by redundant data storage
Increase performance by parallel data access
Mirroring
Assume disks fail independently
Example: MTBF 100000h, MTTR 10h
mean time to data loss 1000002=(2 * 10) ≈ 57000
Data striping
Distribute data across n disks
Write every (k mod n)th chunk of m bits onto disk k n times faster
19
Error correcting codes
RAID Levels (see also textbook)
Performance Optimisation
Block Caching
Typical policies: Clock, LRU, etc
Group blocks (superblock, i-nodes, data, etc)
Consistency: write dirty blocks as soon as possible, (e.g. when block full, periodically)
Write-Through Cache
Data written immediately
Requires more disk I/O
Data loss more unlikely for removable disks
Block Read Ahead
Speculatively read blocks ahead of time, e.g. when file is read sequentially
20
Performance Optimisation
Hard disks: reduce seek time
Clustering, block groups, . . .
Disk scheduling
(next week)
21
SSD issues: Relocate blocks that are often
written to even out wear
Virtual File Systems 22
Virtual File Systems 23
Summary
File abstraction
Unified interface to various devices
System calls:
open(), read(), write(), close(), . . .
Directory structure and Block allocation
Contiguous allocation
Linked list allocation, e.g. FAT
Indexed allocation, e.g. i-nodes
24
File System Management
File system formats and block size
Kernel data structures for file management
Consistency: Journaling, RAID, …
Optimisations: caches, clusters, …
Virtual file systems
Read
Tanenbaum & Bos., Modern Operating Systems
Chapter 4
Silberschatz et al., Operating System Concepts
Chapters 10, 11, 12
25
Next Lecture
Introduction
Operating System Architectures
Processes
Threads – Programming
Process Scheduling – Evaluation
Process Synchronisation
26
Deadlocks
Memory Management
File Systems
Input / Output
Security and Virtualisation