Synthèse du cours d\'OS - Synthesis of the Operating System course from Uliege PDF

Preview

Summary

University of LiègeOperating SystemINFOSynthesis OSJulienGustinJune 3, 2021Contents 1 Chapter 1: Introduction 1 What is an OS 1 Interrupt 1 Storage Structure 1 OS operations 1 Protection 1 OS components 2 Chapter 2: Operating-System Services 2 System Calls 2 System Services 2 Linkers and Loaders 2 W...

Description

University of Liège

Operating System INFO0940

Synthesis OS

Julien Gustin

June 3, 2021

Contents 1 Chapter 1: Introduction 1.1 What is an OS . . . . 1.2 Interrupt . . . . . . . . 1.3 Storage Structure . . . 1.4 OS operations . . . . . 1.5 Protection . . . . . . . 1.6 OS components . . . .

. . . . . .

. . . . . .

. . . . . .

. . . . . .

. . . . . .

. . . . . .

. . . . . .

. . . . . .

. . . . . .

. . . . . .

2 Chapter 2: Operating-System Services 2.1 System Calls . . . . . . . . . . . . . . . 2.2 System Services . . . . . . . . . . . . . . 2.3 Linkers and Loaders . . . . . . . . . . . 2.4 Why applications are OS specific . . . . 2.5 Design and Implementation . . . . . . . 2.6 OS Structure . . . . . . . . . . . . . . . 2.6.1 Monolithic Structure . . . . . . . 2.6.2 Microkernels . . . . . . . . . . . 2.7 Building and Booting an OS . . . . . . . 2.7.1 System boot . . . . . . . . . . . .

. . . . . .

. . . . . .

. . . . . .

. . . . . .

. . . . . .

. . . . . .

. . . . . .

. . . . . .

. . . . . .

. . . . . .

. . . . . .

. . . . . .

. . . . . .

. . . . . .

. . . . . .

. . . . . .

. . . . . .

. . . . . .

. . . . . .

. . . . . .

. . . . . .

. . . . . .

6 . 6 . 6 . 8 . 10 . 11 . 12

. . . . . . . . . .

. . . . . . . . . .

. . . . . . . . . .

. . . . . . . . . .

. . . . . . . . . .

. . . . . . . . . .

. . . . . . . . . .

. . . . . . . . . .

. . . . . . . . . .

. . . . . . . . . .

. . . . . . . . . .

. . . . . . . . . .

. . . . . . . . . .

. . . . . . . . . .

. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .

13 13 15 15 17 17 18 18 18 19 19

3 Chapter 3: Processes 3.1 Process Control Block . . . . . . . . . . . . . . . . 3.2 Process Scheduling . . . . . . . . . . . . . . . . . . 3.3 Context switch . . . . . . . . . . . . . . . . . . . . 3.4 Operations on Processes . . . . . . . . . . . . . . . 3.4.1 Process creation . . . . . . . . . . . . . . . 3.4.2 Process termination . . . . . . . . . . . . . 3.5 Interprocess Communication (IPC) . . . . . . . . . 3.5.1 Shared Memory . . . . . . . . . . . . . . . . 3.5.2 Message Passing . . . . . . . . . . . . . . . 3.5.3 Message Passing - Direct Communication . 3.5.4 Message Passing - Indirect Communication 3.5.5 Message Passing - Synchronization . . . . . 3.5.6 Message Passing - Buffering . . . . . . . . .

. . . . . . . . . . . . .

. . . . . . . . . . . . .

. . . . . . . . . . . . .

. . . . . . . . . . . . .

. . . . . . . . . . . . .

. . . . . . . . . . . . .

. . . . . . . . . . . . .

. . . . . . . . . . . . .

. . . . . . . . . . . . .

. . . . . . . . . . . . .

. . . . . . . . . . . . .

. . . . . . . . . . . . .

. . . . . . . . . . . . .

. . . . . . . . . . . . .

. . . . . . . . . . . . .

. . . . . . . . . . . . .

. . . . . . . . . . . . .

20 21 22 24 25 25 26 27 27 28 28 29 29 30

4 Chapter 4: Threads 4.1 What are the benefits of using threads? 4.2 Multicore Programming . . . . . . . . . 4.3 User and Kernel threads . . . . . . . . . 4.4 Multithreading Models . . . . . . . . . . 4.4.1 Many-to-One . . . . . . . . . . . 4.4.2 One-to-One . . . . . . . . . . . . 4.4.3 Many-to-Many . . . . . . . . . . 4.5 Thread Libraries . . . . . . . . . . . . . 4.6 fork() and exec() . . . . . . . . . . . . . 4.6.1 Issues . . . . . . . . . . . . . . . 4.7 Signal Handling . . . . . . . . . . . . . . 4.8 Thread cancellation . . . . . . . . . . . .

. . . . . . . . . . . .

. . . . . . . . . . . .

. . . . . . . . . . . .

. . . . . . . . . . . .

. . . . . . . . . . . .

. . . . . . . . . . . .

. . . . . . . . . . . .

. . . . . . . . . . . .

. . . . . . . . . . . .

. . . . . . . . . . . .

. . . . . . . . . . . .

. . . . . . . . . . . .

. . . . . . . . . . . .

. . . . . . . . . . . .

. . . . . . . . . . . .

. . . . . . . . . . . .

. . . . . . . . . . . .

31 31 32 32 33 33 33 33 34 34 34 34 34

1

. . . . . . . . . .

. . . . . . . . . . . .

. . . . . . . . . .

. . . . . . . . . . . .

. . . . . . . . . .

. . . . . . . . . . . .

. . . . . . . . . .

. . . . . . . . . . . .

. . . . . . . . . .

. . . . . . . . . . . .

. . . . . . . . . . . .

4.9 Thread-local storage (TLS) . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 35 4.10 Scheduler Activations (not important) . . . . . . . . . . . . . . . . . . . . . . . . 35 5 Chapter 5: CPU Scheduling 5.1 CPU Scheduler . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 5.2 Dispatcher . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 5.3 Scheduling Criteria . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 5.4 First-Come, First-Served (FCFS) Scheduling . . . . . . . . . . . . . . . . . . . . . 5.5 Shortest-Job-First (SJF) Scheduling . . . . . . . . . . . . . . . . . . . . . . . . . 5.6 Round Robin (RR) . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 5.7 Priority Scheduling . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 5.8 Multilevel Queue . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 5.8.1 Multilevel Feedback Queue . . . . . . . . . . . . . . . . . . . . . . . . . . 5.9 Thread Scheduling . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 5.10 Multiple-Processor Scheduling . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 5.11 Multicore Processors . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 5.11.1 Processor Af f inity . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .

36 37 37 38 38 39 40 41 42 43 44 44 45 . 46

6 Chapter 6: Main Memory 6.1 Address Binding . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 6.2 Dynamic loading VS Dynamic linking . . . . . . . . . . . . . . . . . . . . . . . . 6.2.1 Dynamic loading . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 6.2.2 Dynamic linking . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 6.3 Physical Address Space . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 6.3.1 Logical vs Physical address space . . . . . . . . . . . . . . . . . . . . . . . 6.3.2 Binding to Physical Memory Addresses . . . . . . . . . . . . . . . . . . . . 6.4 Contiguous Allocation . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 6.5 Fragmentation . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 6.6 Paging . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 6.6.1 Paging model of Logical and Physical Memory . . . . . . . . . . . . . . . 6.6.2 Free Frames . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 6.6.3 Implementation of page table . . . . . . . . . . . . . . . . . . . . . . . . . 6.6.4 Translation Look-Aside Buffer (demander à la QA) . . . . . . . . . . . . . 6.6.5 Effective Access Time (EAT) . . . . . . . . . . . . . . . . . . . . . . . . . 6.7 Memory Protection . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 6.8 Shared Pages . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 6.9 Structure of the Page Table . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 6.9.1 Hierarchical Page Table . . . . . . . . . . . . . . . . . . . . . . . . . . . . 6.9.2 Hashed Page Table . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 6.9.3 Inverted Page table . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 6.10 Swapping . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 6.10.1 Context Switch Time and Swapping . . . . . . . . . . . . . . . . . . . . .

47 47 48 48 49 49 49 50 51 53 54 56 57 57 59 59 60 61 62 62 64 65 66 67

7 Chapter 7: Virtual Memory 7.1 Virtual-address Space . . . . . . . . . 7.2 Demand Paging . . . . . . . . . . . . . 7.2.1 Valid-Invalid Bit . . . . . . . . 7.2.2 Handling (Hard) Page Fault . . 7.2.3 Handling (Soft) Page Fault . . 7.2.4 Step in Handling a Page Fault

68 68 69 70 71 71 72

2

. . . . . .

. . . . . .

. . . . . .

. . . . . .

. . . . . .

. . . . . .

. . . . . .

. . . . . .

. . . . . .

. . . . . .

. . . . . .

. . . . . .

. . . . . .

. . . . . .

. . . . . .

. . . . . .

. . . . . .

. . . . . .

. . . . . .

. . . . . .

. . . . . .

. . . . . .

. . . . . .

. . . . . .

7.2.5 Aspects of Demand Paging . . . . . . . . . . . . . . . . . . . . . . . . . . 7.2.6 Free-Frame List . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 7.2.7 Demand Paging Example . . . . . . . . . . . . . . . . . . . . . . . . . . . Copy-On-Write . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . What happens if there is no Free Frame? . . . . . . . . . . . . . . . . . . . . . . . 7.4.1 Page Replacement . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 7.4.2 Basic Page Replacement . . . . . . . . . . . . . . . . . . . . . . . . . . . . Page and Frame Replacement Algorithm . . . . . . . . . . . . . . . . . . . . . . . 7.5.1 FIFO algorithm . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 7.5.2 Optimal Algorithm . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 7.5.3 Least Recently Used (LRU) Algorithm . . . . . . . . . . . . . . . . . . . . 7.5.4 LRU Approximation Algorithm . . . . . . . . . . . . . . . . . . . . . . . . 7.5.5 LRU Approximation Algorithm -Second-Chance algorithm . . . . . . . . . 7.5.6 Enhanced Second-Chance Algorithm . . . . . . . . . . . . . . . . . . . . . 7.5.7 Counting Algorithm . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 7.5.8 Page-Buffering Algorithms . . . . . . . . . . . . . . . . . . . . . . . . . . . Applications and Page Replacement . . . . . . . . . . . . . . . . . . . . . . . . . Allocation of Frames . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 7.7.1 Fixed Allocation . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 7.7.2 Global vs Local Allocation . . . . . . . . . . . . . . . . . . . . . . . . . . . 7.7.3 Reclaiming Pages . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . Trashing . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . Demand Paging and Trashing . . . . . . . . . . . . . . . . . . . . . . . . . . . . . Working-Set Model . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 7.10.1 Keeping Track of the Working Set . . . . . . . . . . . . . . . . . . . . . . Page-Fault Frequency . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . Allocating Kernel Memory . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 7.12.1 Buddy System . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 7.12.2 Slab Allocation . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . Other consideration . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 7.13.1 Prepaging . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . Page Size . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 7.14.1 TLB reach . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 7.14.2 Program Structure . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .

72 73 73 74 75 75 76 76 76 77 77 78 78 79 79 79 80 80 80 80 81 82 83 83 84 84 85 85 86 87 87 87 87 88

8 Chapter 8: Mass-Storage Systems 8.1 Overview of Mass Storage Structure . . . . . . . . . . . . . . . . . . . . . . . . . 8.2 Disk Structure . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 8.3 Disk Attachment . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 8.4 Storage array . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 8.5 Storage Area Network . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 8.6 Network-Attached Storage . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 8.7 Disk Scheduling . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 8.7.1 First-Come First-Search . . . . . . . . . . . . . . . . . . . . . . . . . . . . 8.7.2 Shortest Seek Time First . . . . . . . . . . . . . . . . . . . . . . . . . . . 8.7.3 SCAN algorithm . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 8.7.4 C-SCAN algorithm . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 8.7.5 C-LOOK algorithm . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 8.8 Selecting a Disk-Scheduling Algorithm . . . . . . . . . . . . . . . . . . . . . . . .

89 89 90 90 90 91 91 92 93 93 94 94 95 95

7.3 7.4

7.5

7.6 7.7

7.8 7.9 7.10 7.11 7.12

7.13 7.14

3

8.9 8.10 8.11 8.12

Disk Management . . . . Swap Page Management RAID . . . . . . . . . . Other Features . . . . .

. . . .

. . . .

. . . .

. . . .

. . . .

. . . .

. . . .

. . . .

. . . .

. . . .

. . . .

. . . .

. . . .

. . . .

. . . .

. . . .

. . . .

. . . .

. . . .

. . . .

. . . .

. . . .

. . . .

. . . .

. . . .

. . . .

. . . .

. . . .

. . . .

. . . .

. . . .

. 96 . 97 . 98 . 99

9 Chapter 9: File System Interface 9.1 File Attributes . . . . . . . . . . . 9.2 File Operations . . . . . . . . . . . 9.3 Open Files . . . . . . . . . . . . . . 9.3.1 Open File Locking . . . . . 9.4 File Types . . . . . . . . . . . . . . 9.5 Sequential-access File . . . . . . . . 9.6 Directory/Folders Structure . . . . 9.7 Disk Structure . . . . . . . . . . . 9.8 Operations Performed on Directory 9.9 Directory Organization . . . . . . . 9.9.1 Single Level Directory . . . 9.9.2 Two-Level Directory . . . . 9.9.3 Tree-Structured Directories 9.9.4 Acyclic-Graph Directories . 9.9.5 General Graph Directory . 9.10 File System Mounting . . . . . . . 9.11 File Sharing . . . . . . . . . . . . . 9.11.1 Failure Modes . . . . . . . . 9.11.2 Consistency Semantics . . . 9.12 Protection . . . . . . . . . . . . . .

. . . . . . . . . . . . . . . . . . . .

. . . . . . . . . . . . . . . . . . . .

. . . . . . . . . . . . . . . . . . . .

. . . . . . . . . . . . . . . . . . . .

. . . . . . . . . . . . . . . . . . . .

. . . . . . . . . . . . . . . . . . . .

. . . . . . . . . . . . . . . . . . . .

. . . . . . . . . . . . . . . . . . . .

. . . . . . . . . . . . . . . . . . . .

. . . . . . . . . . . . . . . . . . . .

. . . . . . . . . . . . . . . . . . . .

. . . . . . . . . . . . . . . . . . . .

. . . . . . . . . . . . . . . . . . . .

. . . . . . . . . . . . . . . . . . . .

. . . . . . . . . . . . . . . . . . . .

. . . . . . . . . . . . . . . . . . . .

. . . . . . . . . . . . . . . . . . . .

. . . . . . . . . . . . . . . . . . . .

. . . . . . . . . . . . . . . . . . . .

. . . . . . . . . . . . . . . . . . . .

. . . . . . . . . . . . . . . . . . . .

. . . . . . . . . . . . . . . . . . . .

. . . . . . . . . . . . . . . . . . . .

. . . . . . . . . . . . . . . . . . . .

. . . . . . . . . . . . . . . . . . . .

. . . . . . . . . . . . . . . . . . . .

100 100 100 101 101 102 103 104 104 105 105 105 106 106 107 108 109 110 110 110 110

10 Chapter 10: File System Implementation 112 10.1 Layered File System . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 112 10.2 A Typical File Control Block . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 113 10.3 In-Memory File System Structures . . . . . . . . . . . . . . . . . . . . . . . . . . 114 10.4 Virtual File Systems . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 115 10.5 Directory Implementation . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 115 10.6 Contiguous Allocation . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 116 10.6.1 Contiguous Allocation . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 116 10.6.2 Extent-Based Systems . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 117 10.6.3 Linked allocation . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 117 10.7 Indexed Allocation . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 119 10.8 Free-Space Management . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 121 10.9 Efficiency and Performance . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 122 10.9.1 Page Cache . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 123 10.9.2 Unified Buffer Cache . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 123 10.10Log Structured File Systems . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 124 11 Chapter 11: Virtualization 11.1 Why virtualize . . . . . . . . . . . 11.2 Emulation . . . . . . . . . . . . . . 11.3 Container-based OS virtualization 11.3.1 Network virtualization . . . 11.3.2 Pro & Cons . . . . . . . . .

. . . . .

. . . . . 4

. . . . .

. . . . .

. . . . .

. . . . .

. . . . .

. . . . .

. . . . .

. . . . .

. . . . .

. . . . .

. . . . .

. . . . .

. . . . .

. . . . .

. . . . .

. . . . .

. . . . .

. . . . .

. . . . .

. . . . .

. . . . .

. . . . .

. . . . .

. . . . .

125 125 125 126 128 128

11.3.3 Docker . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 11.4 System virtualization . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 11.4.1 Kernel/user space . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 11.4.2 Why not running kernel in privileged mode? . . . . . . . . . . . . . . . . . 11.4.3 17 instructions that fuck-up everything . . . . . . . . . . . . . . . . . . . . 11.4.4 Memory issue . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 11.4.5 System virtualization - Binary rewriting . . . . . . . . . . . . . . ....