程序代写代做代考 data structure cache file system database Object-Oriented Programming

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