1
Ch 2: Operating System Structures 8
OS Services 8
User and OS Interface 8
Command Interpreters 8
GUI 8
Touch Screen 9
System Calls 10
API 10
Types of System Calls 10
Process Control 10
File Management 10
Device management 10
Information maintenance 10
Communications 10
Protection 10
System Services 11
Linkers & Loaders 11
OS Structure 12
Monolithic Structure 12
Layered Approach 12
Microkernels 12
Modules 12
Hybrid Systems 13
Ch 3: Processes 14
Process Concept 14
The Process 14
Process State 14
Process Control Block 14
Thread 14
Process Scheduling 14
Scheduling Queues 14
CPU Scheduling 15
Operation on Processes 15
Process Creation 15
Process Termination 15
Inter Process Communication 16
IPC in Shared-Memory Systems 16
IPC in Message-Passing Systems 16
Ch 4: Threads & Concurrency 16
Benefits 17
Multicore Programming 17
Programming Challenges 17
, 2
Admahl’s Law 17
Types of Parallelism 17
Multithreading Models 17
Many-to-One Model 18
One-to-One Model 18
Many-to-Many Model 19
Threaded Libraries 19
Implicit Threading 19
Thread pools 19
Fork Join 19
OpenMP 19
Grand Central Dispatch (GCD) 20
Intel Thread Building Blocks (TBB) 20
Threading Issues 20
The fork() and exec() System Calls 20
Signal Handling 20
Thread Cancelation 20
Thread-Local Storage (TLS) 21
Scheduler Activations 21
Ch 5: CPU Scheduling 21
Basic Concepts 21
CPU – I/O Burst Cycle 21
CPU Scheduler 21
Preemptive and Nonpreemptive Scheduling 21
Dispatcher 22
Scheduling Criteria 22
Scheduling Algorithms 22
First-Come, First-Served Scheduling (FCFS) 22
Shortest-Job-First Scheduling (SJF) 22
Round-Robin Scheduling (RR) 22
Priority Scheduling 23
Multilevel Queue Scheduling 23
Multilevel Feedback Queue Scheduling 23
Multiprocessor Scheduling 24
Approaches to Multiple-Processor Scheduling 24
Multicore Processors 24
Load Balancing 24
Processor Affinity 24
Heterogeneous Multiprocessing (HMP) 25
Real-Time CPU Scheduling 25
Minimizing Latency 25
Rate-Monotonic Scheduling 25
Earliest-Deadline-First Scheduling 26
Proportional Share Scheduling 26
, 3
Ch 6: Synchronization Tools 26
The Critical-Section Problem 26
Peterson’s Solution 27
Hardware Support for Synchronization 27
Memory Barriers 27
Hardware Instructions 28
test_and_set() (TAS) 28
compare_and_swap() (CAS) 28
Atomic Variables 29
Mutex Locks 29
Semaphores 29
Monitors 29
Monitor Usage 29
Liveness 30
Deadlock 30
Priority Inversion 31
Evaluation 31
CH 7: synchronization Examples 31
Classic Problems of Synchronization 32
The Bounded-Buffer Problem 32
The Readers-Writers Problem 32
The Dining-Philosophers Problem 32
Synchronization within the Kernel 32
Sync in Windows 33
Sync in Linux 33
POSIX Sync (Pthreads) 33
Mutex Locks 33
Semaphores 34
Condition Variables 34
Ch 8: Deadlocks 34
System Model 35
Deadlock in Multithreaded Applications 35
Livelock 35
Deadlock Characterization 35
Necessary Conditions 35
Resource-Allocation Graph 35
Methods for Handling Deadlocks 36
Deadlock Prevention 36
Mutual Exclusion 36
Hold and Wait 36
No Preemption 36
Circular Wait 36
Deadlock Avoidance 36
Safe State 37
, 4
Resource-Allocation-Graph Algorithm 37
Banker’s Algorithm 37
Deadlock Detection 38
Single Instance of Each Resource Type 38
Several Instances of a Resource Type 38
Detection-Algorithm Usage 38
Recovery from Deadlock 38
Process and Thread Termination 38
Resource Preemption 38
Ch 9: Main Memory 39
Contiguous Memory Allocation 39
Memory Protection 39
Memory Allocation 40
Fragmentation 40
Paging 40
Basic Method 41
Hardware Support 41
Protection 42
Shared Pages 42
Structure of the Page Table 42
Hierarchical Paging 42
Hashed Page Tables 42
Inverted Page Tables 42
Swapping 43
Standard Swapping 43
Swapping with Paging 43
Swapping on Mobile Systems 44
Ch 10: Virtual Memory 44
Demand Paging 44
Basic Concepts 44
Free-Frame List 45
Performance of Demand Paging 45
Copy-on-Write 45
Page Replacement 45
Basic Page Replacement 46
FIFO Page Replacement 46
Optimal Page Replacement (OPT or MIN) 46
LRU Page Replacement 46
Counting-Based Page Replacement 47
least frequently used (LFU) 47
most frequently used (MFU) 47
Allocation of Frames 47
Minimum Number of Frames 47
Allocation Algorithms 47
Ch 2: Operating System Structures 8
OS Services 8
User and OS Interface 8
Command Interpreters 8
GUI 8
Touch Screen 9
System Calls 10
API 10
Types of System Calls 10
Process Control 10
File Management 10
Device management 10
Information maintenance 10
Communications 10
Protection 10
System Services 11
Linkers & Loaders 11
OS Structure 12
Monolithic Structure 12
Layered Approach 12
Microkernels 12
Modules 12
Hybrid Systems 13
Ch 3: Processes 14
Process Concept 14
The Process 14
Process State 14
Process Control Block 14
Thread 14
Process Scheduling 14
Scheduling Queues 14
CPU Scheduling 15
Operation on Processes 15
Process Creation 15
Process Termination 15
Inter Process Communication 16
IPC in Shared-Memory Systems 16
IPC in Message-Passing Systems 16
Ch 4: Threads & Concurrency 16
Benefits 17
Multicore Programming 17
Programming Challenges 17
, 2
Admahl’s Law 17
Types of Parallelism 17
Multithreading Models 17
Many-to-One Model 18
One-to-One Model 18
Many-to-Many Model 19
Threaded Libraries 19
Implicit Threading 19
Thread pools 19
Fork Join 19
OpenMP 19
Grand Central Dispatch (GCD) 20
Intel Thread Building Blocks (TBB) 20
Threading Issues 20
The fork() and exec() System Calls 20
Signal Handling 20
Thread Cancelation 20
Thread-Local Storage (TLS) 21
Scheduler Activations 21
Ch 5: CPU Scheduling 21
Basic Concepts 21
CPU – I/O Burst Cycle 21
CPU Scheduler 21
Preemptive and Nonpreemptive Scheduling 21
Dispatcher 22
Scheduling Criteria 22
Scheduling Algorithms 22
First-Come, First-Served Scheduling (FCFS) 22
Shortest-Job-First Scheduling (SJF) 22
Round-Robin Scheduling (RR) 22
Priority Scheduling 23
Multilevel Queue Scheduling 23
Multilevel Feedback Queue Scheduling 23
Multiprocessor Scheduling 24
Approaches to Multiple-Processor Scheduling 24
Multicore Processors 24
Load Balancing 24
Processor Affinity 24
Heterogeneous Multiprocessing (HMP) 25
Real-Time CPU Scheduling 25
Minimizing Latency 25
Rate-Monotonic Scheduling 25
Earliest-Deadline-First Scheduling 26
Proportional Share Scheduling 26
, 3
Ch 6: Synchronization Tools 26
The Critical-Section Problem 26
Peterson’s Solution 27
Hardware Support for Synchronization 27
Memory Barriers 27
Hardware Instructions 28
test_and_set() (TAS) 28
compare_and_swap() (CAS) 28
Atomic Variables 29
Mutex Locks 29
Semaphores 29
Monitors 29
Monitor Usage 29
Liveness 30
Deadlock 30
Priority Inversion 31
Evaluation 31
CH 7: synchronization Examples 31
Classic Problems of Synchronization 32
The Bounded-Buffer Problem 32
The Readers-Writers Problem 32
The Dining-Philosophers Problem 32
Synchronization within the Kernel 32
Sync in Windows 33
Sync in Linux 33
POSIX Sync (Pthreads) 33
Mutex Locks 33
Semaphores 34
Condition Variables 34
Ch 8: Deadlocks 34
System Model 35
Deadlock in Multithreaded Applications 35
Livelock 35
Deadlock Characterization 35
Necessary Conditions 35
Resource-Allocation Graph 35
Methods for Handling Deadlocks 36
Deadlock Prevention 36
Mutual Exclusion 36
Hold and Wait 36
No Preemption 36
Circular Wait 36
Deadlock Avoidance 36
Safe State 37
, 4
Resource-Allocation-Graph Algorithm 37
Banker’s Algorithm 37
Deadlock Detection 38
Single Instance of Each Resource Type 38
Several Instances of a Resource Type 38
Detection-Algorithm Usage 38
Recovery from Deadlock 38
Process and Thread Termination 38
Resource Preemption 38
Ch 9: Main Memory 39
Contiguous Memory Allocation 39
Memory Protection 39
Memory Allocation 40
Fragmentation 40
Paging 40
Basic Method 41
Hardware Support 41
Protection 42
Shared Pages 42
Structure of the Page Table 42
Hierarchical Paging 42
Hashed Page Tables 42
Inverted Page Tables 42
Swapping 43
Standard Swapping 43
Swapping with Paging 43
Swapping on Mobile Systems 44
Ch 10: Virtual Memory 44
Demand Paging 44
Basic Concepts 44
Free-Frame List 45
Performance of Demand Paging 45
Copy-on-Write 45
Page Replacement 45
Basic Page Replacement 46
FIFO Page Replacement 46
Optimal Page Replacement (OPT or MIN) 46
LRU Page Replacement 46
Counting-Based Page Replacement 47
least frequently used (LFU) 47
most frequently used (MFU) 47
Allocation of Frames 47
Minimum Number of Frames 47
Allocation Algorithms 47
