Principles of Operating Systems Notes | B.Sc. (Computer Science) Semester 3 | Mumbai University | munotes

Contents

Module I Fundamentals of Operating Systems, Processes and Threads, Process Synchronization, and CPU Scheduling

1. What an Operating System Is 1
2. The Two Jobs: Handing Out the Machine, and Hiding It 5
3. Interrupts, Traps and the Two Modes 9
4. The Timer, and Why the Operating System Always Gets the Processor Back 14
5. The Functions of an Operating System 19
6. Where Operating Systems Run 23
7. The Services an Operating System Offers 27
8. The Command Line and the Desktop 31
9. What a System Call Is 35
10. Watching System Calls Happen 39
11. The Six Families of System Call 43
12. How an Operating System Is Built 46
13. Microkernels, Modules and What Linux Actually Is 49
14. What a Process Is 53
15. The Five States of a Process 57
16. The Process Control Block 61
17. The Queues, the Schedulers and the Context Switch 65
18. Creating a Process: fork 69
19. Running a Different Program: exec 73
20. Waiting, Exiting, the Zombie and the Orphan 77
21. Inter-process Communication: The Two Models 82
22. Shared Memory, in Code That Runs 86
23. Pipes 90
24. Message Queues 94
25. Blocking and Non-blocking Communication 98
26. What a Thread Is 102
27. Making Threads, and Waiting for Them 106
28. Multicore Programming, and the Limit on It 110
29. The Three Multithreading Models 114
30. Thread Pools, and Handing Work Out 118
31. Measuring It: Sequential Against Threaded 122
32. The Shape of Every Concurrent Program 127
33. A Race Condition, Made to Happen 131
34. The Critical Section Problem, and the Three Conditions 136
35. Peterson's Solution 140
36. Hardware Help: Test and Set, and Compare and Swap 144
37. The Mutex Lock 148
38. The Semaphore 152
39. The Bounded Buffer, Solved 156
40. The Readers and the Writers 161
41. The Dining Philosophers 165
42. Monitors and Condition Variables 170
43. Why Scheduling Exists: The Burst Cycle 175
44. The Dispatcher, Preemption, and What a Switch Costs 179
45. The Five Criteria, and the Arithmetic of Each 183
46. Reading and Drawing a Gantt Chart 186
47. First Come First Served 189
48. Shortest Job First 192
49. Shortest Remaining Time First 195
50. Priority Scheduling, Starvation and Ageing 198
51. Round Robin, and Choosing the Quantum 201
52. Multilevel Queue Scheduling 204
53. Multilevel Feedback Queue Scheduling 207
54. All Seven Algorithms on One Problem 211
55. Thread Scheduling, and What Linux Actually Does 215

Module II Deadlocks, Memory Management, Virtual Memory and Mass Storage, and the File System

1. What a Deadlock Is, and the System Model 219
2. The Four Conditions 223
3. The Resource Allocation Graph 227
4. The Four Ways to Handle a Deadlock 231
5. Deadlock Prevention 234
6. Safe States, and Avoidance 238
7. The Banker's Algorithm 242
8. The Resource Request Algorithm 246
9. Deadlock Detection 250
10. Recovery from Deadlock 255
11. Why Memory Needs Managing 259
12. Binding an Address: Compile, Load, Run 263
13. The Memory Management Unit 267
14. Swapping 271
15. Contiguous Allocation, and the Holes It Leaves 275
16. First Fit, Best Fit and Worst Fit 279
17. Fragmentation, Internal and External 283
18. Segmentation 287
19. Paging 291
20. Splitting an Address, and Translating One 296
21. The TLB, and the Effective Access Time 300
22. Protection and Sharing in a Paged System 305
23. The Page Table Is Too Big: Hierarchical Paging 310
24. Hashed and Inverted Page Tables 315
25. Virtual Memory: Running What Will Not Fit 319
26. Demand Paging, and the Page Fault 324
27. The Effective Access Time Under Demand Paging 329
28. Copy on Write 333
29. Page Replacement: The Problem 338
30. FIFO Replacement, and Belady's Anomaly 342
31. Optimal Replacement 346
32. LRU Replacement 349
33. Second Chance, and the Counting Algorithms 353
34. Comparing the Algorithms, and the Hit Ratio 358
35. Allocation of Frames 362
36. Thrashing, and the Working Set 366
37. What a Disk Is, and What It Costs 371
38. Disk Structure, and the Logical Block 375
39. Disk Scheduling: FCFS and SSTF 379
40. SCAN, C-SCAN, LOOK and C-LOOK 383
41. Random Scheduling, and All Six Compared 387
42. Disk Management 390
43. What a File Is 395
44. Opening a File, and What the Kernel Keeps 399
45. Access Methods 403
46. Directories, and the Shapes They Take 407
47. Mounting 413
48. File Sharing, and Locking 417
49. The Layers a Read Passes Through 422
50. On the Disk: Superblock, Inode, Data Blocks 426
51. Directory Implementation 430
52. Contiguous and Linked Allocation 434
53. Indexed Allocation, and What a Real File System Does 439
54. Free Space Management 444
55. Designing a Small File System 449