代写 data structure android operating system security Operating Systems Lecture 9a

Operating Systems Lecture 9a
Dr Ronald Grau School of Engineering and Informatics Spring term 2018

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

Coursework 2 Preview 26
 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

Read 27  Tanenbaum & Bos., Modern Operating Systems
 Chapter 4
 Silberschatz et al., Operating System Concepts  Chapters 10 & 11

Next Lecture
28
 Introduction
 Operating System Architectures  Processes
 Threads – Programming
 Process Scheduling – Evaluation  Process Synchronisation
 Deadlocks
 Memory Management
 File Systems (continued)  Input / Output
 Security and Virtualisation