Operating Systems: Three Easy Pieces

Technical Books

In Progress

My notes & review of Operating Systems: Three Easy Pieces by Remzi H. Arpaci-Dusseau and Andrea C. Arpaci-Dusseau

Author

Tyler Hillery

Published

July 16, 2026

Notes

Preface

The three easy pieces refer to: virtualization, concurrency, persistence

Aside

Yeats famously said “Education is not the filling of a pail but the lighting of a fire.” He was right but wrong at the same time. You do have to “fill the pail” a bit, and these notes are certainly here to help with that part of your education; after all, when you go to interview at Google, and they ask you a trick question about how to use semaphores, it might be good to actually know what a semaphore is, right?

But Yeats’s larger point is obviously on the mark: the real point of education is to get you interested in something, to learn something more about the subject matter on your own and not just what you have to digest to get a good grade in some class. As one of our fathers (Remzi’s dad, Vedat Arpaci) used to say, “Learn beyond the classroom”.

We created these notes to spark your interest in operating systems, to read more about the topic on your own, to talk to your professor about all the exciting research that is going on in the field, and even to get involved with that research. It is a great field(!), full of exciting and wonderful ideas that have shaped computing history in profound and important ways. And while we understand this fire won’t light for all of you, we hope it does for many, or even a few. Because once that fire is lit, well, that is when you truly become capable of doing something great. And thus the real point of the educational process: to go forth, to study many new and fascinating topics, to learn, to mature, and most importantly, to find something that lights a fire for you.

Love this message.

Chapter 02. Introduction to Operating Systems

❓ Crux of the Problem

How does the operating system virtualize resources?

Trying to ahead a bit and this is where I believe the page table, MMU and TLB come into play. Although for other resources (disk) I’m less sure how virtualization occurs.

the OS does not create a private, virtualized disk for each application.

Well there you go, it doesn’t virtualize disks.

❓ Crux of the Problem

When there are many concurrently executing threads within the same memory space, how can we build correctly working programs?

I’m guessing this is where mutexes and semaphore would help out. How they’re implemented is something I’m not sure about.

Device Driver is some code in the operating system that knows how to deal with a specific device. (kind of a vague definition)

❓ Crux of the Problem

How to do we store data persistency?

OS takes physical resources (CPU, memory, disk) and virtualize them. It handles concurrency issues and it stores files persistently
Another responsibility of the OS is protection between applications. Isolating processes from one another is the key to protection.
Operating Systems need to be highly reliable because it runs non-stop and if it fails then all applications running on the system fail.
Key difference between a system call and procedure call is that a system call transfers control into the OS while raising the hardware privilege level.
User applications run in user mode which has more restrictions on what you can access (can’t access physical memory, initiate I/O request to disk).
System call is initiated through a hardware instruction called a trap and the hardware transfers the control to a pre-specified trap handler.
Once the OS is done with the system call is passes control back (out of kernel mode) using a return-from-trap instruction.

Chapter 04. The Process

❓ Crux of the Problem

How to Provide the Illusion Of Many CPUs?

My thoughts: The OS switches which process is running really fast to make it seem like they are all running at once.

process is a running program
The state of a process: memory (address space), registers (including PC, SP), and I/O info (such as open files).
program counter (PC) (aka instruction pointer (IP)) tells us which instruction of the program to execute next.
stack pointer and frame pointer are used to manage the stack function parameters, local vars, and return addresses.
mechanism is the answer to a how question e.g. how does an OS perform a context switch?
policy is the answer to a which question e.g. which process should the OS run right now?
process can be in three states:
- running: process is running on a process, executing instructions
- ready: ready to run but OS has chosen not to run it as this give moment
- blocked: process has performed some kind of operation that makes it not ready to run until some other event takes place
process list (aka task list) is used to keep track of the state of each process:
- register context holds the contents of its registers for stopped processes
Each entry is found in a Process Control Block (PCB), an individual structure that stores information of a process aka process descriptor.

Homework (Simulation)

Problem 1

Run process-run.py with:

./process-run.py -l 5:100,5:100

What should the CPU utilization be? Why do you know this? Use the -c and -p flags to check.

My answer before running it:

| Time | PID: 0  | PID: 1  | CPU | IO  |
|------|---------|---------|-----|-----|
| 1    | RUN:cpu | READY   | 1   |     |
| 2    | RUN:cpu | READY   | 1   |     |
| 3    | RUN:cpu | READY   | 1   |     |
| 4    | RUN:cpu | READY   | 1   |     |
| 5    | RUN:cpu | READY   | 1   |     |
| 6    | DONE    | RUN:cpu | 1   |     |
| 7    | DONE    | RUN:cpu | 1   |     |
| 8    | DONE    | RUN:cpu | 1   |     |
| 9    | DONE    | RUN:cpu | 1   |     |
| 10   | DONE    | RUN:cpu | 1   |     |

Stats: Total Time 10  
Stats: CPU Busy   10 (100.00%)  
Stats: IO Busy    00 (0.00%)

I know this because it says each process is going to run 5 instructions and 100% of the time the chances are a CPU instruction.

Solution

Result: ✅ Correct

➜  ./process-run.py -l 5:100,5:100 -c -p
Time        PID: 0        PID: 1           CPU           IOs
1        RUN:cpu         READY             1          
2        RUN:cpu         READY             1          
3        RUN:cpu         READY             1          
4        RUN:cpu         READY             1          
5        RUN:cpu         READY             1          
6           DONE       RUN:cpu             1          
7           DONE       RUN:cpu             1          
8           DONE       RUN:cpu             1          
9           DONE       RUN:cpu             1          
10          DONE       RUN:cpu             1          

Stats: Total Time 10
Stats: CPU Busy   10 (100.00%)
Stats: IO Busy    00 (  0.00%)

Problem 2

Now run process-run.py with:

./process-run.py -l 4:100,1:0

These flags specify one process with 4 instructions (all to use the CPU), and one that simply issues an I/O and waits for it to be done. How long does it take to complete both processes? Use -c and -p to find out if you were right.

My answer before running it:

| Time | PID: 0  | PID: 1     | CPU | IO  |
|------|---------|------------|-----|-----|
| 1    | RUN:cpu | READY      | 1   |     |
| 2    | RUN:cpu | READY      | 1   |     |
| 3    | RUN:cpu | READY      | 1   |     |
| 4    | RUN:cpu | READY      | 1   |     |
| 6    | DONE    | RUN:io     | 1   |     |
| 7    | DONE    | BLOCKED    |     | 1   |
| 8    | DONE    | BLOCKED    |     | 1   |
| 9    | DONE    | BLOCKED    |     | 1   |
| 10   | DONE    | BLOCKED    |     | 1   |
| 11   | DONE    | BLOCKED    |     | 1   |
| 12   | DONE    | RUN:io_done| 1   |     |

Stats: Total Time 11
Stats: CPU Busy    6 (54.54%)  
Stats: IO Busy     5 (45.45%)

This is based on the assumption of default I/O length of 5.

Solution

Result: ✅ Correct

➜ ./process-run.py -l 4:100,1:0 -c -p 
Time        PID: 0        PID: 1           CPU           IOs
1        RUN:cpu         READY             1          
2        RUN:cpu         READY             1          
3        RUN:cpu         READY             1          
4        RUN:cpu         READY             1          
5           DONE        RUN:io             1          
6           DONE       BLOCKED                           1
7           DONE       BLOCKED                           1
8           DONE       BLOCKED                           1
9           DONE       BLOCKED                           1
10          DONE       BLOCKED                           1
11*         DONE   RUN:io_done             1          

Stats: Total Time 11
Stats: CPU Busy 6 (54.55%)
Stats: IO Busy  5 (45.45%)

Problem 3

Switch the order of the processes: -l 1:0,4:100. What happens now? Does switching the order matter? Why? (As always, use -c and -p to see if you were right)

./process-run.py -l 1:0,4:100

My answer before running it:

| Time | PID: 0      | PID: 1     | CPU | IO  |
|------|-------------|------------|-----|-----|
| 1    | RUN:io      | READY      | 1   |     |
| 2    | BLOCKED     | RUN:cpu    | 1   |     |
| 3    | BLOCKED     | RUN:cpu    | 1   |     |
| 4    | BLOCKED     | RUN:cpu    | 1   |     |
| 5    | BLOCKED     | RUN:CPU    | 1   |     |
| 6    | BLOCKED     | DONE       |     | 1   |
| 7    | run:io_done | BLOCKED    | 1   |     |

Stats: Total Time 7
Stats: CPU Busy   6 (85.71%)  
Stats: IO Busy    1 (14.29%)

I don’t feel confident about this but I am basing my answer off the assumption that the OS can switch to another PID while one is blocked. This begs the question can you have IO and CPU executing at the same time?

Solution

Result: ❌ Wrong

➜ ./process-run.py -l 1:0,4:100 -c -p
Time        PID: 0        PID: 1           CPU           IOs
1         RUN:io         READY             1          
2        BLOCKED       RUN:cpu             1             1
3        BLOCKED       RUN:cpu             1             1
4        BLOCKED       RUN:cpu             1             1
5        BLOCKED       RUN:cpu             1             1
6        BLOCKED          DONE                           1
7*   RUN:io_done          DONE             1          

Stats: Total Time 7
Stats: CPU Busy 6 (85.71%)
Stats: IO Busy  5 (71.43%)

I was wrong and exactly for the reason I expected, you can have IOs and CPUs overlap.

Problem 4

We’ll now explore some of the other flags. One important flag is -S, which determines how the system reacts when a process issues an I/O. With the flag set to SWITCH_ON_END, the system will NOT switch to another process while one is doing I/O, instead waiting until the process is completely finished. What happens when you run the following two processes (-l 1:0,4:100 -c -S SWITCH_ON_END), one doing I/O and the other doing CPU work?

./process-run.py -l 1:0,4:100 -S SWITCH_ON_END

My answer before running it:

| Time | PID: 0      | PID: 1  | CPU | IO  |
|------|-------------|---------|-----|-----|
| 01   | RUN:io      | READY   | 1   |     |
| 02   | BLOCKED     | READY   |     | 1   |
| 03   | BLOCKED     | READY   |     | 1   |
| 04   | BLOCKED     | READY   |     | 1   |
| 05   | BLOCKED     | READY   |     | 1   |
| 06   | BLOCKED     | READY   |     | 1   |
| 07   | run:io_done | READY   | 1   |     |
| 08   | DONE        | RUN:cpu | 1   |     |
| 09   | DONE        | RUN:cpu | 1   |     |
| 10   | DONE        | RUN:cpu | 1   |     |
| 11   | DONE        | RUN:cpu | 1   |     |

Stats: Total Time 11
Stats: CPU Busy 6 (54.55%)
Stats: IO Busy  5 (45.45%)

If the CPU can’t switch until the IO is done then PID: 1 is just going to be waiting the whole time until PID: 0 is finished. PID: 1 wont start until the IO is done from PID 0.

Solution

Result: ✅ Correct

➜ ./process-run.py -l 1:0,4:100 -S SWITCH_ON_END -c -p
Time        PID: 0        PID: 1           CPU           IOs
1         RUN:io         READY             1          
2        BLOCKED         READY                           1
3        BLOCKED         READY                           1
4        BLOCKED         READY                           1
5        BLOCKED         READY                           1
6        BLOCKED         READY                           1
7*   RUN:io_done         READY             1          
8           DONE       RUN:cpu             1          
9           DONE       RUN:cpu             1          
10          DONE       RUN:cpu             1          
11          DONE       RUN:cpu             1          

Stats: Total Time 11
Stats: CPU Busy 6 (54.55%)
Stats: IO Busy  5 (45.45%)

Problem 5

Now, run the same processes, but with the switching behavior set to switch to another process whenever one is WAITING for I/O (-l 1:0,4:100 -c -S SWITCH ON IO). What happens now? Use -c and -p to confirm that you are right.

./process-run.py -l 1:0,4:100 -S SWITCH_ON_IO

My answer before running it:

| Time | PID: 0      | PID: 1  | CPU | IO  |
|------|-------------|---------|-----|-----|
| 1    | RUN:io      | READY   | 1   |     |
| 2    | BLOCKED     | RUN:cpu | 1   | 1   |
| 3    | BLOCKED     | RUN:cpu | 1   | 1   |
| 4    | BLOCKED     | RUN:cpu | 1   | 1   |
| 5    | BLOCKED     | RUN:CPU | 1   | 1   |
| 6    | BLOCKED     | DONE    |     | 1   |
| 7    | run:io_done | BLOCKED | 1   |     |

Stats: Total Time 7
Stats: CPU Busy   6 (85.71%)  
Stats: IO Busy    5 (71.43%)

I’m pretty sure this is the default behavior so should be the same answer as question 3.

Solution

Result: ✅ Correct

➜ ./process-run.py -l 1:0,4:100 -S SWITCH_ON_IO -c -p 
Time        PID: 0        PID: 1           CPU           IOs
1         RUN:io         READY             1          
2        BLOCKED       RUN:cpu             1             1
3        BLOCKED       RUN:cpu             1             1
4        BLOCKED       RUN:cpu             1             1
5        BLOCKED       RUN:cpu             1             1
6        BLOCKED          DONE                           1
7*   RUN:io_done          DONE             1          

Stats: Total Time 7
Stats: CPU Busy 6 (85.71%)
Stats: IO Busy  5 (71.43%)

Problem 6

One other important behavior is what to do when an I/O completes. With -I IO_RUN_LATER, when an I/O completes, the process that issued it is not necessarily run right away; rather, whatever was running at the time keeps running. What happens when you run this combination of processes? Are system resources being effectively utilized?

./process-run.py -l 3:0,5:100,5:100,5:100 -S SWITCH_ON_IO -I IO_RUN_LATER  -c -p

My answer before running it:

| Time | PID: 0      | PID: 1  | PID: 2  | PID: 3  | CPU | IO  |
|------|-------------|---------|---------|---------|-----|-----|
| 01   | RUN:io      | READY   | READY   | READY   | 1   |     |
| 02   | BLOCKED     | RUN:cpu | READY   | READY   | 1   | 1   |
| 03   | BLOCKED     | RUN:cpu | READY   | READY   | 1   | 1   |
| 04   | BLOCKED     | RUN:cpu | READY   | READY   | 1   | 1   |
| 05   | BLOCKED     | RUN:cpu | READY   | READY   | 1   | 1   |
| 06   | BLOCKED     | RUN:cpu | READY   | READY   | 1   | 1   |
| 07   | READY       | DONE    | RUN:cpu | READY   | 1   |     |
| 08   | READY       | DONE    | RUN:cpu | READY   | 1   |     |
| 09   | READY       | DONE    | RUN:cpu | READY   | 1   |     |
| 10   | READY       | DONE    | RUN:cpu | READY   | 1   |     |
| 11   | READY       | DONE    | RUN:cpu | READY   | 1   |     |
| 12   | READY       | DONE    | DONE    | RUN:cpu | 1   |     |
| 13   | READY       | DONE    | DONE    | RUN:cpu | 1   |     |
| 14   | READY       | DONE    | DONE    | RUN:cpu | 1   |     |
| 15   | READY       | DONE    | DONE    | RUN:cpu | 1   |     |
| 16   | READY       | DONE    | DONE    | RUN:cpu | 1   |     |
| 17   | run:io_done | DONE    | DONE    | DONE    | 1   |     |
| 18   | run:io      | DONE    | DONE    | DONE    | 1   |     |
| 19   | BLOCKED     | DONE    | DONE    | DONE    |     | 1   |
| 20   | BLOCKED     | DONE    | DONE    | DONE    |     | 1   |
| 21   | BLOCKED     | DONE    | DONE    | DONE    |     | 1   |
| 22   | BLOCKED     | DONE    | DONE    | DONE    |     | 1   |
| 23   | BLOCKED     | DONE    | DONE    | DONE    |     | 1   |
| 24   | run:io_done | DONE    | DONE    | DONE    | 1   |     |
| 25   | run:io      | DONE    | DONE    | DONE    | 1   |     |
| 26   | BLOCKED     | DONE    | DONE    | DONE    |     | 1   |
| 27   | BLOCKED     | DONE    | DONE    | DONE    |     | 1   |
| 28   | BLOCKED     | DONE    | DONE    | DONE    |     | 1   |
| 29   | BLOCKED     | DONE    | DONE    | DONE    |     | 1   |
| 30   | BLOCKED     | DONE    | DONE    | DONE    |     | 1   |
| 31   | run:io_done | DONE    | DONE    | DONE    | 1   |     |

Stats: Total Time 31
Stats: CPU Busy   21 ( 67.74%)  
Stats: IO Busy    15 ( 48.39%)

No, the system resources are not being used effectively. You would have been better off letting the IO complete at 07 instead of continue on with CPU instructions from PID 2, PID 3.

Solution

Result: ✅ Correct

➜ ./process-run.py -l 3:0,5:100,5:100,5:100 -S SWITCH_ON_IO -I IO_RUN_LATER  -c -p
Time        PID: 0        PID: 1        PID: 2        PID: 3           CPU           IOs
  1         RUN:io         READY         READY         READY             1          
  2        BLOCKED       RUN:cpu         READY         READY             1             1
  3        BLOCKED       RUN:cpu         READY         READY             1             1
  4        BLOCKED       RUN:cpu         READY         READY             1             1
  5        BLOCKED       RUN:cpu         READY         READY             1             1
  6        BLOCKED       RUN:cpu         READY         READY             1             1
  7*         READY          DONE       RUN:cpu         READY             1          
  8          READY          DONE       RUN:cpu         READY             1          
  9          READY          DONE       RUN:cpu         READY             1          
 10          READY          DONE       RUN:cpu         READY             1          
 11          READY          DONE       RUN:cpu         READY             1          
 12          READY          DONE          DONE       RUN:cpu             1          
 13          READY          DONE          DONE       RUN:cpu             1          
 14          READY          DONE          DONE       RUN:cpu             1          
 15          READY          DONE          DONE       RUN:cpu             1          
 16          READY          DONE          DONE       RUN:cpu             1          
 17    RUN:io_done          DONE          DONE          DONE             1          
 18         RUN:io          DONE          DONE          DONE             1          
 19        BLOCKED          DONE          DONE          DONE                           1
 20        BLOCKED          DONE          DONE          DONE                           1
 21        BLOCKED          DONE          DONE          DONE                           1
 22        BLOCKED          DONE          DONE          DONE                           1
 23        BLOCKED          DONE          DONE          DONE                           1
 24*   RUN:io_done          DONE          DONE          DONE             1          
 25         RUN:io          DONE          DONE          DONE             1          
 26        BLOCKED          DONE          DONE          DONE                           1
 27        BLOCKED          DONE          DONE          DONE                           1
 28        BLOCKED          DONE          DONE          DONE                           1
 29        BLOCKED          DONE          DONE          DONE                           1
 30        BLOCKED          DONE          DONE          DONE                           1
 31*   RUN:io_done          DONE          DONE          DONE             1          

Stats: Total Time 31
Stats: CPU Busy 21 (67.74%)
Stats: IO Busy  15 (48.39%)

Problem 7

Now run the same processes, but with -I IO RUN_IMMEDIATE set, which immediately runs the process that issued the I/O. How does this behavior differ? Why might running a process that just completed an I/O again be a good idea?

./process-run.py -l 3:0,5:100,5:100,5:100 -S SWITCH_ON_IO -I IO_RUN_IMMEDIATE  -c -p

My answer before running it:

| Time | PID: 0      | PID: 1  | PID: 2  | PID: 3  | CPU | IO  |
|------|-------------|---------|---------|---------|-----|-----|
| 01   | RUN:io      | READY   | READY   | READY   | 1   |     |
| 02   | BLOCKED     | RUN:cpu | READY   | READY   | 1   | 1   |
| 03   | BLOCKED     | RUN:cpu | READY   | READY   | 1   | 1   |
| 04   | BLOCKED     | RUN:cpu | READY   | READY   | 1   | 1   |
| 05   | BLOCKED     | RUN:cpu | READY   | READY   | 1   | 1   |
| 06   | BLOCKED     | RUN:cpu | READY   | READY   | 1   | 1   |
| 07   | run:io_done | DONE    | READY   | READY   | 1   |     |
| 08   | run:io      | DONE    | READY   | READY   | 1   |     |
| 09   | BLOCKED     | DONE    | RUN:cpu | READY   | 1   | 1   |
| 10   | BLOCKED     | DONE    | RUN:cpu | READY   | 1   | 1   |
| 11   | BLOCKED     | DONE    | RUN:cpu | READY   | 1   | 1   |
| 12   | BLOCKED     | DONE    | RUN:cpu | READY   | 1   | 1   |
| 13   | BLOCKED     | DONE    | RUN:cpu | READY   | 1   | 1   |
| 14   | run:io_done | DONE    | DONE    | READY   | 1   |     |
| 15   | run:io      | DONE    | DONE    | READY   | 1   |     |
| 16   | BLOCKED     | DONE    | DONE    | RUN:cpu | 1   | 1   |
| 17   | BLOCKED     | DONE    | DONE    | RUN:cpu | 1   | 1   |
| 18   | BLOCKED     | DONE    | DONE    | RUN:cpu | 1   | 1   |
| 19   | BLOCKED     | DONE    | DONE    | RUN:cpu | 1   | 1   |
| 20   | BLOCKED     | DONE    | DONE    | RUN:cpu | 1   | 1   |
| 21   | run:io_done | DONE    | DONE    | DONE    | 1   |     |

Stats: Total Time 21
Stats: CPU Busy   21 (100.00%)  
Stats: IO Busy    15 ( 71.43%)

It’s a good idea to let a process complete IO because it’s likely they will issue you another IO command and while IO is happening other processes can do CPU work.

Solution

Result: ✅ Correct

➜ ./process-run.py -l 3:0,5:100,5:100,5:100 -S SWITCH_ON_IO -I IO_RUN_IMMEDIATE -c -p
Time        PID: 0        PID: 1        PID: 2        PID: 3           CPU           IOs
  1         RUN:io         READY         READY         READY             1          
  2        BLOCKED       RUN:cpu         READY         READY             1             1
  3        BLOCKED       RUN:cpu         READY         READY             1             1
  4        BLOCKED       RUN:cpu         READY         READY             1             1
  5        BLOCKED       RUN:cpu         READY         READY             1             1
  6        BLOCKED       RUN:cpu         READY         READY             1             1
  7*   RUN:io_done          DONE         READY         READY             1          
  8         RUN:io          DONE         READY         READY             1          
  9        BLOCKED          DONE       RUN:cpu         READY             1             1
 10        BLOCKED          DONE       RUN:cpu         READY             1             1
 11        BLOCKED          DONE       RUN:cpu         READY             1             1
 12        BLOCKED          DONE       RUN:cpu         READY             1             1
 13        BLOCKED          DONE       RUN:cpu         READY             1             1
 14*   RUN:io_done          DONE          DONE         READY             1          
 15         RUN:io          DONE          DONE         READY             1          
 16        BLOCKED          DONE          DONE       RUN:cpu             1             1
 17        BLOCKED          DONE          DONE       RUN:cpu             1             1
 18        BLOCKED          DONE          DONE       RUN:cpu             1             1
 19        BLOCKED          DONE          DONE       RUN:cpu             1             1
 20        BLOCKED          DONE          DONE       RUN:cpu             1             1
 21*   RUN:io_done          DONE          DONE          DONE             1          

Stats: Total Time 21
Stats: CPU Busy 21 (100.00%)
Stats: IO Busy  15 (71.43%)

Chapter 05. The Process API

❓ Crux of the Problem

What interfaces should the OS present for process creation and control?

fork() creates an almost exact copy of the parent process.
exec() replaces the existing program with the new program.
The separation of fork() and exec()is hat enables building a UNIX shell as it lets the shell run code *after* the call tofork()but *before* the call toexec()`.
kill() is used to send signals to a process e.g. CTRL+C = SIGINT (interrupt), CTRL+Z SIGTSTP (stop)
signal() is used to “catch” various signals.

Homework (Simulation)

Problem 1

Run:

./fork.py -s 10 
                           Process Tree:
                               a
Action: a forks b
Process Tree?
Action: a forks c
Process Tree?
Action: c EXITS
Process Tree?
Action: a forks d
Process Tree?
Action: a forks e
Process Tree?

and see which actions are taken. Can you predict what the process tree looks like at each step? Use the -c flag to check your answers. Try some different random seeds (-s) or add more actions (-a) to get the hang of it.

My answer before running it:

# a forks b
a    
└── b
# a forks c     
a    
├── b
└── c
# c EXITS     
a    
└── b
# a forks d
a    
├── b
└── d
# a forks e
a    
├── b
├── d
└── e

Solution

Result: ✅ Correct

➜ ./fork.py -s 10 -c
                           Process Tree:
                               a

Action: a forks b
                               a
                               └── b
Action: a forks c
                               a
                               ├── b
                               └── c
Action: c EXITS
                               a
                               └── b
Action: a forks d
                               a
                               ├── b
                               └── d
Action: a forks e
                               a
                               ├── b
                               ├── d
                               └── e

Problem 2

One control the simulator gives you is the fork_percentage, controlled by the -f flag. The higher it is, the more likely the next action is a fork; the lower it is, the more likely the action is an exit. Run the simulator with a large number of actions (e.g., -a 100) and vary the fork_percentage from 0.1 to 0.9. What do you think the resulting final process trees will look like as the percentage changes? Check your answer with -c.

My answer before running it:

Well, if fork percentage is higher then you are likely going to have more processes running then if it was lower.

Solution

Result: ✅ Correct

Yes, as fork percentage was increased the number of processes at the end were far greater. The depth of the process tree was also a lot of deeper.

Problem 3

Now, switch the output by using the -t flag (e.g., run ./fork.py -t). Given a set of process trees, can you tell which actions were taken?

➜ ./fork.py -s 2 -t 
                           Process Tree:
                               a

Action?
                               a
                               └── b
Action?
                               a
Action?
                               a
                               └── c
Action?
                               a
                               └── c
                                   └── d
Action?
                               a
                               ├── c
                               │   └── d
                               └── e

My answer before running it:

1. a forks b
2. b EXITS
3. a forks c
4. c forks d
5. a forks e

Solution

Result: ✅ Correct

                           Process Tree:
                               a

Action: a forks b
                               a
                               └── b
Action: b EXITS
                               a
Action: a forks c
                               a
                               └── c
Action: c forks d
                               a
                               └── c
                                   └── d
Action: a forks e
                               a
                               ├── c
                               │   └── d
                               └── e

Problem 4

One interesting thing to note is what happens when a child exits; what happens to its children in the process tree? To study this, let’s create a specific example: ./fork.py -A a+b,b+c,c+d,c+e,c-. This example has process ’a’ create ’b’, which in turn creates ’c’, which then creates ’d’ and ’e’. However, then, ’c’ exits. What do you think the process tree should like after the exit? What if you use the -R flag? Learn more about what happens to orphaned processes on your own to add more context.

My answer before running it:

I assume that if a process exits, then all of its children will exit as well.

Solution

Result: ❌ Wrong

The children become direct children of the root process. Did not expect this. Even if the children where reparented, I would have thought they would go to the grandparent process not the root process.

➜ ./fork.py -A a+b,b+c,c+d,c+e,c-. -c
                           Process Tree:
                               a

Action: a forks b
                               a
                               └── b
Action: b forks c
                               a
                               └── b
                                   └── c
Action: c forks d
                               a
                               └── b
                                   └── c
                                       └── d
Action: c forks e
                               a
                               └── b
                                   └── c
                                       ├── d
                                       └── e
Action: c EXITS
                               a
                               ├── b
                               ├── d
                               └── e

Problem 5

One last flag to explore is the -F flag, which skips intermediate steps and only asks to fill in the final process tree. Run ./fork.py -F and see if you can write down the final tree by looking at the series of actions generated. Use different random seeds to try this a few times.

➜ ./fork.py -F -s 1
                           Process Tree:
                               a

Action: a forks b
Action: a forks c
Action: c forks d
Action: a forks e
Action: c EXITS

My answer before running it:

a
├── b
├── e
└── d

unclear if the order matters here but I put d at the bottom as it should get reparented to a after c exists.

Solution

Result: ✅ Correct

➜ ./fork.py -F -s 1 -c
                        Final Process Tree:
                               a
                               ├── b
                               ├── e
                               └── d

Problem 6

Finally, use both -t and -F together. This shows the final process tree, but then asks you to fill in the actions that took place. By looking at the tree, can you determine the exact actions that took place? In which cases can you tell? In which can’t you tell? Try some different random seeds to delve into this question.

My answer before running it:

I think you can only tell if one process forks another but it you can’t really guarantee the order of when that happens. For example, the prior problem we saw c fork d and then a fork e and then c exits but looking at the process tree there is nothing that would tell you that c existed and d was actually created before e. It would even appear as if a forked d but that’s also not the case. So you know there was forking but I don’t think you can deduce what order and which process it was forked from.

Solution

Don’t know the answer to to this one.

Homework (Code)

You can view my solutions to coding homework assignments here.

Chapter 06. Limited Direct Execution

Direction Execution Protocol (Without Limits)
- OS:
  1. Create entry for process list
  2. Allocate memory for program
  3. Load program into memory
  4. Set up stack with argc/argv
  5. Clear registers
  6. Execute call main()
- Program:
  1. Run main()
  2. Execute return from main
- OS:
  1. Free memory of process
  2. Remove from process list
While systems calls look just like procedure calls, the one thing that separates them from other normal functions is the trap instruction. When executing a system call you execution a procedure call into the C library. The library uses an agreed-upon calling convention with the kernel to put the arguments and syc call number in well-known locations (e.g. on the stack, or in specific registers), and executes the trap instruction. The code in the library after the trap unpacks return values and returns control to the program that issued the system call.
The hardware needs to save enough of the caller’s registers in order to be able to return correctly when the OS issues the return-from-trap instruction. On x86 the the processor will push the PC, flags, and few other registers onto a per-process kernel stack
The kernel uses a trap table, setup a boot time, to know which code to run inside the OS. The calling process can’t specify an address to jump to as it would allow programs to jump anywhere into the kernel.
Limited Direct Execution:
- OS @ Boot:
  1. Initialize trap table
    - Hardware remembers address of syscall handler
- OS @ Run:
  1. Create entry for process list
  2. Allocate memory for program
  3. Load program into memory
  4. Set up stack with argc/argv
  5. Fill kernel stack with reg/PC
  6. return-from-trap
- Hardware:
  1. restore regs (from kernel stack)
  2. move to user mode
  3. jump to main
- Program (User mode):
  1. Run main()
  2. …
  3. Call system call
  4. trap into OS
- Hardware:
  1. Save regs (to kernel stack)
  2. Move to kernel mode
  3. Jump to trap handler
- OS @ Run:
  1. Handle Trap
  2. Do work of syscall
  3. return-from-trap
- Hardware:
  1. restore regs (from kernel stack)
  2. move to user mode
  3. jump to PC after trap
- Program (User mode):
  1. …
  2. return from main
  3. trap via exit()
- OS @ Run:
  1. Free memory of process
  2. Remove from process list
Cooperative approach to timesharing is where the OS trusts the process of the system to behave reasonably and if they run too long they will give up the CPU so that OS can decide to run some other task. This is usually done by making system call there is also a explicit yield system call which does nothing except transfer control to the OS.
Non-cooperative approach uses teh dies of a timer interrupt to raise an interrupt every so many milliseconds, when raises the the currently running process is halted and a pre-configured trap handler in the OS runs.
Once the OS regains control a decision must be made, which process should I run next? This decision is made by the scheduler.
If the OS decides to switch processes the OS executes a low-level piece of code which we refer to as a context switch.
There are two types of register saves/restores that happen during a context switch (when timer interrupt occurs).
1. the user registers of the running process are saved by the hardware using the kernel stack of that process.
2. The OS switches to the other process, the kernel registers are saved by the software but this time into memory in the process structure of the process.

Chapter 07. Scheduling: Introduction

Turnaround time of a job is defined at the time at which the job completes minus the time at which the job arrived in the system.
convoy effect is when a number of short potential consumers get queued by a heavy weight resources. This is the downside of FIFO based policy as if you have three jobs, one that takes a really long and that long one runs first the other two are stuck waiting until that job finishes.
shortest job first is a scheduling principle where the perceived turnaround time matters. A good example of this is a grocery store with “ten-items-or-less” lines to ensure shoppers with only a few things don’t get stuck behind a family with a ton of stuff.

Question❓

How do you know how long something is going to take before you run it though? I don’t see how you can employ a SJF policy if you don’t have metrics on how long a program typically runs for.

Preemptive (where you don’t have to run a job until completion) + SJT is known as Shortest Time-to-Completion First (STCF) or Preemptive Shortest Job First (PSJF)
Response Time defined ast the time from when the job arrives in a system to the first time it is scheduled.
Round-Robin runs a job for a time slice (sometimes called a scheduling quantum) and then switches in the next job in the run queue.
Amortization is used in systems where there is a fixed cost of some operation. By incurring the loss less often the total cost to the system is reduce e.g. if a time slice is 10ms and a context switch cost is 1ms, 10% of the time is spent context switching but if we want to amortize this cost we can increase the time slice to 100ms and then it would reduce to 1% of the time.
There are other costs associated with a context switch besides saving and restore registers such as CPU caches, TLBs, branch predictors.
In general Response Time and Turnaround time are at odds with each other. Round robin with a very short time slice is great for response time because it’s constantly switching between jobs and it will be relatively short time from when your job arrives to when it’s first scheduled. But for turnaround time it’s awful because you are effectively stretching out each job as long as it can by only running it for short bit before moving to the next.

Homework (Simulation)

Problem 1

Compute the response time and turnaround time when running three jobs of length 200 with the SJF and FIFO schedulers.

./scheduler.py -p FIFO -l 200,200,200

My answer before running it:

SJF:
- turnaround time would be (200 + 400 + 600) / 3 = 400
- response time would be (0 + 200 + 400) / 3 = 200
Should be the same for FIFO because all the jobs are the same length

Solution

Result: ✅ Correct

homework/cpu-sched git:(master) ✗ 
➜ ./scheduler.py -p SJF -l 200,200,200 -c
Execution trace:
  [ time   0 ] Run job 0 for 200.00 secs ( DONE at 200.00 )
  [ time 200 ] Run job 1 for 200.00 secs ( DONE at 400.00 )
  [ time 400 ] Run job 2 for 200.00 secs ( DONE at 600.00 )

Final statistics:
  Job   0 -- Response: 0.00  Turnaround 200.00  Wait 0.00
  Job   1 -- Response: 200.00  Turnaround 400.00  Wait 200.00
  Job   2 -- Response: 400.00  Turnaround 600.00  Wait 400.00

  Average -- Response: 200.00  Turnaround 400.00  Wait 200.00

➜ ./scheduler.py -p FIFO -l 200,200,200 -c
Execution trace:
  [ time   0 ] Run job 0 for 200.00 secs ( DONE at 200.00 )
  [ time 200 ] Run job 1 for 200.00 secs ( DONE at 400.00 )
  [ time 400 ] Run job 2 for 200.00 secs ( DONE at 600.00 )

Final statistics:
  Job   0 -- Response: 0.00  Turnaround 200.00  Wait 0.00
  Job   1 -- Response: 200.00  Turnaround 400.00  Wait 200.00
  Job   2 -- Response: 400.00  Turnaround 600.00  Wait 400.00

  Average -- Response: 200.00  Turnaround 400.00  Wait 200.00

Problem 2

Now do the same but with jobs of different lengths: 100, 200, and 300.

./scheduler.py -p FIFO -l 100,200,300

My answer before running it:

FIFO
- Turnaround Time: (100 + 300 + 600) / 3 = 333.33
- Response Time: (0 + 100 + 300) / 3 = 133.33
Once again, SJF is the same because the jobs are already ordered as shortest time first.

Solution

Result: ✅ Correct

➜ ./scheduler.py -p FIFO -l 100,200,300 -c
Execution trace:
  [ time   0 ] Run job 0 for 100.00 secs ( DONE at 100.00 )
  [ time 100 ] Run job 1 for 200.00 secs ( DONE at 300.00 )
  [ time 300 ] Run job 2 for 300.00 secs ( DONE at 600.00 )

Final statistics:
  Job   0 -- Response: 0.00  Turnaround 100.00  Wait 0.00
  Job   1 -- Response: 100.00  Turnaround 300.00  Wait 100.00
  Job   2 -- Response: 300.00  Turnaround 600.00  Wait 300.00

  Average -- Response: 133.33  Turnaround 333.33  Wait 133.33

➜ ./scheduler.py -p SJF -l 100,200,300 -c
Execution trace:
  [ time   0 ] Run job 0 for 100.00 secs ( DONE at 100.00 )
  [ time 100 ] Run job 1 for 200.00 secs ( DONE at 300.00 )
  [ time 300 ] Run job 2 for 300.00 secs ( DONE at 600.00 )

Final statistics:
  Job   0 -- Response: 0.00  Turnaround 100.00  Wait 0.00
  Job   1 -- Response: 100.00  Turnaround 300.00  Wait 100.00
  Job   2 -- Response: 300.00  Turnaround 600.00  Wait 300.00

  Average -- Response: 133.33  Turnaround 333.33  Wait 133.33

Problem 3

Now do the same but also with RR scheduler and a time-slice of 1.

./scheduler.py -l 100,200,300 -p RR -q 1 -c

My solution

Turnaround time: I actually don’t know how to compute this easily. If Job 1 takes 100 seconds but it has to weight an additional 2 second before running again it’s going to be 300? Then with Job 2 same thing but once job 1 finishes it only has to weight 1 second. So (300, 200) 500? And job 3 same as job 2 with additional 100 seconds so 600? so (300 + 500 + 600) / 3 = 466.666
Response time: (0, 1, 2) / 3 = 1

Solution

Result: ✅ Correct (close enough, I off by one on both job 1 and 2)

Final statistics:
  Job   0 -- Response: 0.00  Turnaround 298.00  Wait 198.00
  Job   1 -- Response: 1.00  Turnaround 499.00  Wait 299.00
  Job   2 -- Response: 2.00  Turnaround 600.00  Wait 300.00

  Average -- Response: 1.00  Turnaround 465.67  Wait 265.67

Problem 4

For what types of workloads does SJF deliver the same turnaround times as FIFO?

My solution

When the workloads have jobs of the same length or if the jobs with the shortest duration happen to arrive first.

Solution

Result: No solution found

Problem 5

For what types of workloads and quantum lengths does SJF deliver the same response times as RR?

My solution

I don’t know, when the time slice and the job length are the same?

Solution

Result: No solution found

Problem 6

What happens to response time with SJF as job lengths increase?

My solution

Response times would get longer.

Solution

Result: No solution found

Problem 7

What happens to response time with RR as quantum lengths increase?

My solution

Response times would get long because the second job that runs will be the min of the first job length and the quantum length. This keeps applying for all subsequent jobs. So if you keep increasing the length then it’s going to increase the response times for all subsequent jobs assuming the job length is large tan the quantum length.

Solution

Result: No solution found

Chapter 08. Scheduling: The Multi-Level Feedback Queue

MFLQ varies the priority of a job based on its observed behavior e.g. a job repeatedly relinquishes the CPU while waiting for input from the keyboard, MLFQ will keep its priority high, as this is how an interactive process might behave. If the jobs uses the CPU intensively for long periods of time, MLFQ will reduce its priority and tries to learn about processes as the run and uses the history of the job to predict its future behavior.
Job’s allotment is the amount of time a job can spend at a give priority level before the scheduler reduces its priority.
It first assumes a job might be a short job.
starvation can occur when you have “too many”” interactive jobs in the system, they will combine to consume all CPU time, and long running jobs will never receive any CPU time.
game the scheduler is where a user rewrites their program to giving you more than a fair share of the resource e.g. before allotment is used you can issue I/O operation to stay in high priority queue and get an allotment refresh.
One way to avoid starvation is to periodically boost the priority of all the jobs in the system.
Another way is to not have have the allotment reset after I/O

Notes

Preface

Chapter 02. Introduction to Operating Systems

Chapter 04. The Process

Homework (Simulation)

Problem 1

Problem 2

Problem 3

Problem 4

Problem 5

Problem 6

Problem 7

Chapter 05. The Process API

Homework (Simulation)

Problem 1

Problem 2

Problem 3

Problem 4

Problem 5

Problem 6

Homework (Code)

Chapter 06. Limited Direct Execution

Chapter 07. Scheduling: Introduction

Homework (Simulation)

Problem 1

Problem 2

Problem 3

Problem 4

Problem 5

Problem 6

Problem 7

Chapter 08. Scheduling: The Multi-Level Feedback Queue

Chapter 09. Scheduling: Proportional Share