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

Object-Oriented Programming

Operating Systems

Lecture 9a

Dr Ronald Grau School of Engineering and Informatics Spring term 2018

Previously

Storage management

 Persistent storage

 Formats, access, operations

 File attributes & permissions

1

Today

Storage management

 File systems implementation

 Implementation

 Layout

 Kernel data structures

 Block allocation

 Logical file system

2

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

3

File system layout

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

4

Kernel data structures

 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

5

Kernel data structures 6

Block allocation

 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

7

Aspects to consider:

• Fragmentation

• Performance of finding and accessing blocks

• Size of tables for managing blocks

Block allocation

Contiguous Allocation

8

Block allocation

Contiguous Allocation

9

After deleting files D and F:

Problem: External fragmentation

Block allocation

Linked-List Allocation

10

Block allocation

Linked-List Allocation

11

Problem:

Needs to traverse the list

to find a block

Block allocation

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

12

Block allocation

Indexed Allocation

13

Block allocation

Index-Nodes (i-nodes)

 Multi-level indices

14

Block allocation

Example: UNIX i-nodes

15

Block allocation

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

16

Logical file system

User’s view on the file system

 Typically hierarchically structured:

17

Logical file system

Mounting Volumes

Unmounted volume Mounted at /users

18

Logical file system

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

19

Logical file system

File names implementation

 We want to minimise

management overheads

20

Logical file system

Shared files

 UNIX:

 Hard links

 Symbolic links

21

Logical file system

Shared files

 Hard link:

22

Logical file system

Shared files

 Soft (symbolic) link:

 By pathname

 Requires resolving the pathname to find actual file

 Can link across volumes

 No reference counting

23

Logical file system

Example: UNIX file attributes

24

Summary

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

25

Coursework 2 Preview

 Select two different operating systems, e.g.

 Windows 10 and FreeBSD 11

 Android 7 and iOS 10

 …

 Compare two different implementation aspects of these systems in detail, e.g. from

 Process management

 Memory management

 Storage management

 …

 Write a report (~1500 words), due Friday 11 May, 4pm

 Marking criteria:

 Depth of comparison and discussion

 Combine information from many (primary) sources

 Appropriate referencing of sources

26

Read

 Tanenbaum & Bos., Modern Operating Systems

 Chapter 4

 Silberschatz et al., Operating System Concepts

 Chapters 10 & 11

27

Next Lecture

 Introduction

 Operating System Architectures

 Processes

 Threads – Programming

 Process Scheduling – Evaluation

 Process Synchronisation

28

 Deadlocks

 Memory Management

 File Systems (continued)

 Input / Output

 Security and Virtualisation