Operating Systems Lecture 9b
Dr Ronald Grau School of Engineering and Informatics Spring term 2020
Previously 1 Storage management
Persistent storage
Formats, access, operations File attributes & permissions
Today 2 Storage management
File systems implementation Implementation
Layout
Kernel data structures
Block allocation Logical file system
File system implementation 3 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
File system layout 4 Volume
Boot control block
(e.g. boot block, partition boot sector)
Volume control block (e.g. superblock, master file table)
Directory structure: where to find files
File control block for each file
Kernel data structures 5
Mount table
Available volumes
Mount point (e.g. directory, drive)
Open-file tables
Keeps track of files accessed by processes
Entry created on open(), removed on close() Identified by file descriptor (or file handle)
Reference counting for open files
Buffers and caches
Efficient locating of files
Efficient data transfer between storage and main memory
Kernel data structures 6
Block allocation 7
Storage divided into blocks, e.g. 512 bytes
Block-wise addressing
File consists of one or more blocks
Blocks are loaded into main memory on file access
Techniques
Contiguous Allocation Linked-List Allocation Indexed Allocation
Aspects to consider:
• Fragmentation
• Performance of finding and accessing blocks
• Size of tables for managing blocks
Block allocation 8 Contiguous Allocation
Block allocation
9
Contiguous Allocation
Problem: External fragmentation
After deleting files D and F:
Block allocation 10 Linked-List Allocation
Block allocation 11 Linked-List Allocation
Problem:
Needs to traverse the list to find a block
Block allocation 12 Example: File Allocation Table (FAT)
Implementation of linked list: Marker for last block of a file Marker for unused blocks
Simple to implement
Performance optimisation by caching FAT E.g. FAT-32: most widely used
Block allocation 13 Indexed Allocation
Block allocation 14
Index-Nodes (i-nodes) Multi-level indices
Block allocation 15 Example: UNIX i-nodes
Block allocation 16 Free Space Management
Bitmap:
One bit for each block
E.g. 0011110011111100011000000011100000…
Runlength encoding: Start + length
e.g. (2,4),(8,6),(25,3),… Linked list
Logical file system 17
User’s view on the file system Typically hierarchically structured:
Logical file system 18
Mounting Volumes
Unmounted volume Mounted at /users
Logical file system 19 Path names
E.g. /users/john/docs
Uniquely identifies a file in the logical file system Access path to a file
Elements separated by a delimiter, e.g. / , \ , > Absolute: from root of the file system
Relative: to current working directory of the process
Resolving a path name
Recursively search file system directory
Logical file system 20 File names implementation
We want to minimise management overheads
Logical file system 21 Shared files
UNIX:
Hard links
Symbolic links
Logical file system 22
Shared files Hard link:
Logical file system 23 Shared files
Soft (symbolic) link: By pathname
Requires resolving the pathname to find actual file Can link across volumes
No reference counting
Logical file system 24 Example: UNIX file attributes
Summary 25 File systems
File system layouts
Kernel data structures for file management
Block allocation
Contiguous allocation Linked list allocation Indexed allocation
Mounting, path names, hard vs symbolic links
Read 26 Tanenbaum & Bos., Modern Operating Systems
Chapter 4
Silberschatz et al., Operating System Concepts Chapters 10 & 11
Next Lecture
27
Introduction
Operating System Architectures Processes
Threads – Programming
Process Scheduling – Evaluation Process Synchronisation
Deadlocks
Memory Management File Systems (continued) Input / Output
Security