Operating Systems: Three Easy Pieces

Technical Books

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

Author

Tyler Hillery

Published

October 27, 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

Chapter 10. Multiprocessor Scheduling (Advanced)

❓ Crux of the Problem

How should the OS schedule jobs on multiple CPUs? What new problems arise? Do the same old techniques work, or are new ideas required?

cache coherence is the problem where one core may read a value from main memory and update it but it only gets updated in that core’s cache so when another core reads this value and it goes to main memory it will get the old value.
cache affinity it’s often advantageous to run the same program on the same CPU core as it builds up a bit of state in the caches.
most basic approach is single queue multiprocessor scheduling or SQMS.
- Pros
  - easy to build
  - load balances well
- Cons
  - Doesn’t scale
  - Cache affinity
multi-queue multiprocessor scheduling or MQMS
- Pros
  - Scales
  - Handles Cache affinity
- Cons
  - Load balancing

TODO

Homework (Simulation)

Chapter 13. The Abstraction: Address Space

Seems like much of the need for memory virtualization stems from wanting the ability to have multiple processes running on the same machine.
stack is used to keep track of where it is in the function call chain as well as to allocate local variables and pass parameters and return values to and from routines.
heap is used for dynamically-allocated, user-managed memory like you use get using malloc().
Typically address space is organized where the code segment is first and then the heap and the stack is at the end. The heap grows positively while the stack grows negatively. Stack overflow can happen when you run out of free memory space. Commonly this shows up in very long recursive calls if tail call optimization isn’t being used because every recursive call keeps pushing more and more stuff onto the stack.

TODO

Homework (Code)

Chapter 14. Interlude: Memory API

❓ Crux of the Problem

In UNIX/C programs, understanding how to allocate and manage memory is critical in building robust and reliable software. What interfaces are commonly used? What mistakes should be avoided?

stack allocations and deallocations are managed implicitly by the compiler for you, for this reason it sometimes referred called automatic memory.
For long lived memory the heap is used.
The example brings up a good point int *x = (int *) malloc(sizeof(int)); x still has to pushed onto the stack which is the space for the ptr (virtual address space for the memory for the int).
malloc() is the main interface UNIX/C give you to manually allocate memory.
size_t is something that I still fully don’t grasp. I always have to remind myself what it means.
Wait NULL isn’t a real value in C but just a macro? #define NULL 0? TIL.
Good reminder that sizeof() is an operator as it evaluates at compile time not runtime.
This example always trips me up

int *x = malloc(10 * sizeof(int));  
printf("%d\n", sizeof(x));             // will be the size of a ptr

int *x = malloc(10 * sizeof(int));  
printf("%d\n", sizeof(x));             // will the the size of 10 ints

free() is how you deallocate memory
brk is a sys call that changes the location of the end of the heap.
malloc() and free() are no sys calls but are more like library calls. The implementation of these functions are what’s actually doing the system calls. (I also assume this is what’s referred to as the memory allocator?).
mmap() is another way to obtain memory from the OS called an anonymous memory region which is a region not associated with any particular file but rather swap space.
calloc() and realloc() are a couple of nice helpers as well.

TODO

Homework (code)

Chapter 15. Mechanism: Address Translation

❓ Crux of the Problem

How can we build an efficient virtualization of memory? How do we provide the flexibility needed by applications? HOw do we maintain control over which memory locations on an application can access, and thus ensure that application memory accesses are properly restricted? How do we do all of this efficiently?

hardware-based address translation is where the hardware transforms each memory access (fetch, load, store) changing the virtual address provided by the instruction to a physical address.
In many ways, what the OS does for virtualizing memory to give the programs it’s own private memory address reminds me of partition disks (with some minor differences) but they both generalize to the program not knowing actual size of the physical space they are just given this section and they are free to do what they want with that section.
The base and bounds registers are hardware structures kept on the chip (one pair per CPU) and commonly referred to as the memory management unit (MMU).
free list is a data structure that is used to keep track of which parts of free memory are not in use, which is a list of ranges of the physical memory which are currently not in use.
OS must save and restore the base and bounds pair when it switches between processes, this gets saved to the process structure or process control block.

TODO

Homework (Simulation)

Chapter 16. Segmentation

❓ Crux of the Problem

How do we support a large address space with a lot of free space between the stack and the heap?

Interesting, so the term segmentation fault comes from the fact that the code, stack and heap all get their base and bounds pair and are stored independently in their own segment. The fault occurs when trying to access an address that lives outside of the segment.
External fragmentation occurs when the physical memory becomes full of little holes of free space, making it difficult to allocate new segments.
One solution to external fragmentation is compaction by rearranging the segments to get rid of the little holes but this is expensive.
There are also a bunch of algorithms for free-list management such as best-fit, worst-fit, first-fit and buddy algorithm.

TODO

Homework (Simulation)

Chapter 17. Free-Space Management

Free space management becomes tricky when dealing with variable sized units like you get from malloc() and free().

❓ Crux of the Problem

How should free space be managed, when satisfying variable-sized requests? What strategies can be used to minimized fragmentation? What are the time and space overheads of alternate approaches?

Splitting occurs when the request amount memory is smaller than the smallest region available. In that case the memory allocator will split the free region subtracting only the amount of memory it needs.
Coalescing is like the opposite, when a memory region gets freed, instead of adding a new node to the free list it will merge the memory region with any existing memory region if it’s continuous.
sbrk is a system call to grow the heap.
Segregated Lists is a technique used to maintain a separate list just to manage objects of the same size. A popular implementation of this is the slab allocator and there is a great talk here about the allocator: Down memory lane: Two decades with the slab allocator – Bryan Cantrill.
The Binary Buddy Allocator is an interesting technique that deals with free memory as spaces of 2^N. Then it wil keep diving the bigger space into a smaller space until it’s the smallest it can be to fulfill the request memory size. Because it only does with powers of 2 this technique does have internal fragmentation where it can give out more memory then the process needed. The benefit here is it’s really easy to coalesce the spaces back up because it’s really easy to find the “buddy” of a block. Each address of each buddy pair only differs by a single bit (the benefit of only using power of 2) which bit is determined by the level of the buddy tree.

TODO

Homework (Simulation)

Chapter 18. Paging: Introduction

Paging is about chopping up space into fixed-sized pieces.
Each fixed sized unit is called a page.
page frames in physical memory are an array of fixed-sized slots.

❓ Crux of the Problem

How can we virtualize memory with pages, so as to avoid problems of segmentation? What are the basic techniques? How do we make those techniques work well, with minimal space and time overheads?

Page table is a per process data structure that records the address translation for each of the virtual pages to the physical memory each page resides.
Two components make up the virtual address, the virtual page number and the offset
Offset stays the same during translations because it just tells us which byte within the page we want.
A basic data structure you can use for the page table is a linear page table which is just an array. The OS indexes the array by virtual page number and looks up the page-table entry (PTE) in order to find the desired physical frame number (PFN).

❓

What’s the difference between the page table and page table entry, is the page table just a collection of all the entries? e.g. a row vs a table.

protection bits indicate if the page can be read from, written to or executed from.
present bit indicates if the page is in physical memory or on disk.
dirty bit indicates if the page has been modified since it was brought into memory.
reference bit is used to track if page has been accessed, and useful when determining which pages are popular.
page-table base register contains the physical address of the starting location of the page table.
The main benefit of paging is enabling sparse use of virtual address spaces whereas segmentation requires a continuous unit.

TODO

Homework (Simulation)

Chapter 19. Paging: Faster Translations (TLBs)

Because paging requires a large amount of mapping information and this information is stored in physical memory, paging requires an extra memory lookup for each virtual address. Going to memory for translation information before every instruction fetch or explicit load or store is prohibitively slow.

❓ Crux of the Problem

How can we speed up address translation, and generally avoid the extra memory reference that paging seems to require? What hardware support is required? What OS involvement is needed?

translation-lookaside buffer or TLBU is part of the chip’s memory-management unit (MMU) and is a hardware cache of popular virtual-to-physical address translations.
What happens on a TLB Miss?
- in CISC days the hardware would handle the miss entirely by using a page-table base register e.g. Intel x86 uses a fixed multi-level page table
- RISC uses a software-managed TLB, hardware raises and exception and jumps to a trap handler.
Fully associative TLB means that any given translation can be anywhere in the TLB.

❓ Crux of the Problem

When context-switching between processes, the translations in the TLB for the last process are not meaningful to the about-to-be-run process. What should the hardware or OS do in order to solve this problem?

TLB is only valid for the currently running process but it can have a address space identifier (ASID) that helps in distinguish which PID the TLB entry belongs to.

❓ Crux of the Problem

Which TLB entry should be replaced when we add a new TLB entry? The goal, of course, being to minimize the mise rate (or increase hit rate) and thus improve performance.

TODO

Homework (Measurement)

Chapter 20. Paging: Smaller Tables

❓ Crux of the Problem

Simple array-based pages tables (usually called linear page tables) are too big, taking up far too much memory. How can we make page tables smaller? What are the key ideas? What inefficiencies arise as a result of these new data structures?

Multi-level page table turns a linear page table into a tree like structure.
page directory is a data structure used to tell you where a page of the page table is. It’s a two level table, one entry per page of the page table which consist of page directory entires.
Trade off is on a TLB miss, it now requires two loads from memory to get the right translation.
1. One for the page directory
2. One for the PTE itself compared to the one load with the linear page table.
Inverted page table keeps a single page table that has an entry for each physical page of the system. The entry shows which process is using this page, and which virtual page of that process maps this physical page.

TODO

Homework (Measurement)

Chapter 21. Beyond Physical Memory: Mechanisms

❓ Crux of the Problem

How can the OS make use of larger, slower device to transparently provide the illusion of a large virtual address space?

swap space allows pages to be stored on disk versus main memory
present bit is used in the page table entry to determine if the page is present in physical memory.
page fault is accessing a page that is not in physical memory. OS page-fault handler is what runs to handle the page fault.
If memory is full the OS may need to page out one or more pages to make room. The process of picking a page to kick out is known as the page-replacement policy

TODO

Homework (Measurement)

Chapter 22. Beyond Physical Memory: Policies

❓ Crux of the Problem

How can the OS decide which page (or pages) to evict from memory? This decision is made by the replacement policy of the system, which usually follow some general principles but also includes certain tweaks to avoid corner-case behaviors

LRU is expensive to implement because each page access a data structure needs to b updated to move the page to the front of the list.

❓ Crux of the Problem

Given that it will be expensive to implement perfect LRU, can we approximate it in some way, and still obtain the desired behavior?

Approximating the LRU can be done with the help from hardware support in the form of a use bit also referred to as a reference bit.
If a page has been modified while in memory it is considered dirty, if it is dirty it must be written to disk to evict it
OS has to decide when to bring a page to memory, to commonly used techniques are demand paging, bring the page into memory when access or prefetching, bring the page ahead of time.
OS can group writes to disk which is called clustering and grouping.
When memory is oversubscribed where the set of running processes simply exceeds the available memory the system will constantly be paging, this is commonly referred to as thrashing.

TODO

Homework (Simulation)

Chapter 23. Complete Virtual Memory Systems

❓ Crux of the Problem

What features are needed to realize a complete virtual memory system? How do they improve performance, increase security, or otherwise improve the system?

Chapter 24. Summary Dialogue on Memory Virtualization

No notes.

Chapter 25. A Dialogue on Concurrency

No notes.

Chapter 26. Concurrency: An Introduction

State of a single thread:
- a program counter (PC) to track where the program is fetching instructions from
- own private set of registers used for computation
- a context switch must occur when switching from one thread to another but the key difference is the address space stays the same.
- processes saved state to a process control block while threads use thread control blocks
- Each thread gets is own stack

❓ Crux of the Problem

What support do we need from the hardware in order to build useful synchronization primitives? What support do we need from the OS? How can we build these primitives correctly and efficiently? How can programs use them to get the desired results?

Critical section is a piece of code that accesses a shared resource
Race condition arises if multiple threads of execution enter the critical section at roughly the same time; both attempt to update the shared data structure.
Indeterminate is the opposite of deterministic
Mutual Exclusion primitives gives guarantees that only a single thread ever enters a critical section.

Chapter 27. Interlude: Thread API

❓ Crux of the Problem

What interfaces should the OS present for thread creation and control? How should these interfaces be designed to enable ease of use as well as utility?

TODO

Homework (code)

Chapter 28. Locks

❓ Crux of the Problem

How can we build an efferent lock? Efficient locks provide mutual exclusion at low cost, and also might attain a few other properties we discuss below. What hardware support is needed? What OS support?

I understand the purpose of locks but really struggling understanding how lock implementations work like the spin lock using test-and-set
Test-and-set, Compare-and-swap, load-linked & store-conditional, fetch-and-add

❓ Crux of the Problem

How can we develop a lock that doesn’t needlessly waste time spinning on the CPU?

Instead of spinning the thread can give up control using yield().
A thread can be in one of three states: running, ready, blocked. Calling yield() moves the thread from running to ready

❓ Question

What’s the data structure used to build the queue for the Lock with queues? If you have multiple threads trying to enqueue to acquire the lock what happens when two threads do this at the the same time?

TODO

Homework (Simulation)

Chapter 29. Lock-based Concurrent Data Structures

❓ Crux of the Problem

When given a particular data structure, how should we add locks to it, in order to make it work correctly? Further, how do we add locks such that the data structure yields high performance, enabling many threads to access the structure at once, i.e., concurrently?

hand-over-hand locking aka lock coupling is a technique used for concurrent linked lists data structures that uses a lock per node of the list instead of a global one for the entire list.

TODO

Homework (code)

Chapter 30. Condition Variables

❓ Crux of the Problem

In multi-threaded programs, it is often useful for a thread to wait for some condition to become true before proceeding. The simple approach, of just spinning until the condition becomes true, is grossly inefficient and wastes GPU cycles, and in some cases, can be incorrect. Thus, how should a thread wait for a condition?

condition variable is an explicit queue that threads can put themselves on when some state of execution (i.e. some condition) is not as desired (by waiting on the condition); some other thread, when it changes said state, can then wake one (or more) of these waiting threads and thus allow them to continue (by signaling on the condition).
producer/consumer aka bounded buffer problem is when one more producer threads and one or more consumer threads where the producers are generating data items and place them in a buffer and the consumers grab the items from the buffer and consume them in some way.
pipes are a good example of bounded buffers e.g. grep foo file.txt | wc -l

TODO

Homework (code)

Chapter 31. Semaphores

❓ Crux of the Problem

How can we use semaphores instead of locks and condition variables? What is the the definition of a semaphore? What is a binary semaphore? Is it straightforward to build a semaphore out of locks and condition variables? To build locks and condition variables out of semaphores?

So for the concurrency section has been the hardest for me to grok. At a high level I understand why would need primitives to protect critical sections against data races. I understand why you want to ensure you have mutual exclusion which can be implemented with various ways like mutexes, spin locks etc. I understand why you would want to have signaling mechanisms like conditional variables so a thread doesn’t have to constantly poll a variable to see if it can proceed to do some work. Semaphores I am a bit fuzzy on but high level I get they can be used to similar things like provide mutual exclusion, ordering/signaling, and throttling. I understand you can implement them with locks and condition variables. I am still not fully understand how these primitives are actually implemented though.

TODO

Homework (code)

Chapter 32. Common Concurrency Problems

❓ Crux of the Problem

Concurrency bugs tend to come in a variety of common patterns. Knowing which ones to look out for is the first step to writing more robust, correct concurrent code.

❓ Crux of the Problem

How should we build systems to prevent, avoid, or at least detect and recover from deadlock? Is this a problem in systems today?

TODO

Homework (code)

Chapter 33. Event-based Concurrency (Advanced)

❓ Crux of the Problem

How can we build a concurrent server without using threads, and thus retain control over concurrency as well as avoid some of the problems that seem to plague multi-threaded applications?

TODO

Homework (code)

Chapter 36. I/O Devices

❓ Crux of the Problem

How should I/O be integrated into systems? What are the general mechanisms? How can we make them efficient?

CPU is connected to various components through something called buses
Memory Bus typically the closest to the CPU uses proprietary interconnect
General I/O Bus for something like GPU may use PCI
Peripheral I/O Bus uses SCSI, SATA, USB
This is more of a legacy overview of systems as nowadays there are specialized chisels and faster point-to-point interconnects.
firmware software withing a hardware device
programmed I/O (PIO) is when the main CPU is involved with the data movement.

❓ Crux of the Problem

How can the OS check device status without frequent polling, and thus lower the CPU overhead required to manage the device?

Instead of polling, the OS can put the process to sleep and when the I/O device is done it can raise a hardware interrupt causing the CPU to jump into the os at a predetermined interrupt service routine (ISR) aka interrupt handler.

❓ Crux of the Problem

With PIO, the CPU spends too much time moving data to and from devices by hand. How can we offload this work nad thus allow the CPU to be more effectively utilized?

Direct memory access (DMA) engine is a specific device withing a system that can orchestrate transfers between devices and main memory without much CPU intervention.

❓ Crux of the Problem

How should the hardware communicate with a device? Should there be explicit instructions? Or are there other ways to do it?

memory mapped I/O the hardware makes device registers available as if they were memory locations.

❓ Crux of the Problem

How can we keep most of the OS device-neutral, thus hiding the details of device interactions from major OS subsystems?

device driver encapsulates all the specifics of a device inside this driver.

Interestingly, because device drivers are needed for any device you might plug into your system, over time they have come to represent a huge percentage of kernel code. Studies of the Linux kernel reveal that over 70% of OS code is found in device drivers [C01]

Wow, had no idea that much code is related to device drivers

Chapter 37. Hard Disk Drives

❓ Crux of the Problem

How do modern hard-disk drives store data? What is the interface? How is the data actually laid our and accessed? How does disk scheduling improve performance?

A drive consists of a large number of sectors (512-byte blocks). Each sector is number 0 to n -1.
Multi-sector operations are allowed by drive manufactory only guarantee that a single 512-byte write is atomic.
If only a portion of large write completes this is a called a torn write.
platter circular hard surface which data is stored by inducing magnetic changes.
A disk may have one or more platters, each platter has 2 sides which is called a surface.
Platters are bound together around a spindle.
track is a centric circle of sectors. A single surface can contain thousands and thousands of tracks.
seek is what happens when moving the head between difference tracks

\[ T_{I/O} = T_{seek} + T_{rotation} + T_{transfer} \]

❓ Crux of the Problem

How ca we implement a shortest seek time first (SSTF) like scheduling but avoid starvation?

❓ Crux of the Problem

How can we implement an algorithm that more closely approximates SJF by taking both seek and rotation into account?

TODO

Homework (Simulation)

Chapter 38. Redundant Arrays of Inexpensive Disks (RAIDs)

❓ Crux of the Problem

How can we keep most of the OS device-neutral, thus hiding the details of device interactions from major OS subsystems?

TODO

Homework (Simulation)

Chapter 39. Interlude: Files and Directories

❓ Crux of the Problem

How should the OS manage a persistent device? What are the APIs? What are the important aspects of the implementation?

file is a linear array of bytes
file has a low-level commonly called an inode number
directory also has a inode number but its contents are a list of (user-readable name, inode number) pairs.
file descriptor is an integer, private per process, that is used in UNIX systems to access files. 0 is stdin, 1 is stdout, and 2 is stderr.
An array on the proc struct is where it stores all file descriptors for the process and the file descriptor number is used to index into the array which returns a pointer to struct file struct file *ofile[NOFILE].
Each process maintains an array of file descriptors, each of which refers to an entry in the system wide open file table. Each entry in this table tracks which underlying file the descriptor refers to, the current offset, and other relevant details such as whether the file is readable or writeable.
For each file a process opens, the OS tracks a “current” offset.
dup() system call allows you to create a file descriptor that refers to the same underlying file as the existing descriptor.
Memory mapping is an alternative way to access persistent data in files. The mmap() sys call creates a correspondence between byte offsets in a file and virtual addresses in the calling process; the former is called the backing file and the latter its in-memory image. The process can then access the backing file user CPU instructions (i.e., loads and stores) to the in-memory image.
rename() is atomic meaning it will be named the old name or new name and not some weird inconsistent state. This is often used by programs where a write is done to file.txt.tmp and after written then it will rename it to the actual file name.
A hard link creates another name to refer to the same inode number. The inode number will actually keep a reference count of all the files that reference it. This is why when you remove a file you call unlink() even when it’s the only file.
Symbolic links on the other hand create an actually file with their own inode number. The file just contains the path to real file. This is needed because hard links are limited in that they can’t create one to a directory, you can’t hard link to files in other disk partitions (because inode numbers are only unique within a particular file system).
dangling reference occurs when you delete the file a symbolic link points to.
To make file system you give it a file system type and a disk partition. Then you run mount() to takes an existing dir as a target mount point and paste a new file system onto the directory tree at that point, this is needed because when a filesystem is created it still needs to be made accessible within the uniform file-system tree.

TODO

Homework (Code)

Chapter 40. File System Implementation

❓ Crux of the Problem

How can we build a simple file system? What structures are needed on the disk? What do they need to track? How are they accessed?

The inode will contain metadata about the file and the associated data blocks where the file is stored.
allocation structures are used to track which data blocks and inodes are free. You can use something like a free list, bitmap or B-tree. Similar to the lessons we learned on virtual memory chapters.
superblock is used to contain information about the file system such as how many inodes and data blocks are the file system, where the inode table begins etc.
direct pointers (disk addresses) is one way inodes refer to data blocks, each pointer refers to on disk block that belongs to the file. This is challenges for really big files e.g. bigger than the block size * # of direct pointers in the inode.
indirect pointer points to a block that contains more pointers each of which point to user data.
double indirect pointer same thing but points to a block of indirect pointers.
extents can be used instead of pointers. An extent is a disk pointer plus a length (in blocks) thus, instead of requiring a pointer for every block of a file all one needs is a pointer and a length to specify the on-disk location of a file.
A single extent is limiting, as one may have a trouble finding a contiguous chunk of on-disk free space when allocating a file.
When comparing the two, pointer-based approach are the most flexible but use a large amount of metadata per file. Extent-based approaches are less flexible but more compact; in particular, they work well when there is enough free space on the disk and the files can be laid out contiguously.
This imbalanced tree is referred to as the multi-level index.
The root inode number must be “well known”.

❓ Crux of the Problem

Even the simplest of operations like opening, reading or writing a file incurs a huge number of I/O operations, scattered over the disk. What can a file system do to reduce the high costs of doing so many I/Os?

Early file systems introduced a fixed-size cache to hold popular blocks.
This static partitioning of memory can be wasteful; what if the file system doesn’t need 10% of memory at a give time?
Dynamic partition is used in many modern operating systems where they integrate virtual memory pages and file system pages into a unified page cache.
write buffering occurs by delaying writes so they can batch some updates together. The trade off is there can be data loss if the buffered writes aren’t written to disk if the system crashes before then.
Some applications like databases don’t like the tradeoffs of write buffering so they can use fsync() to force writes to disk.

TODO

Homework (Simulation)

Chapter 41. Locality and The Fast File System

❓ Crux of the Problem

How can we organize file system data structures so as to improve performance? WHat types of allocation policies do we need on top of those data structures? How do we make the file system “disk aware”?

block groups are a consecutive portion of the disk’s address space.

TODO

Homework (Simulation)

Chapter 42. Crash Consistency: FSCK and Journaling

❓ Crux of the Problem

The system may crash or lose power between any two writes, and thus the on-disk state may only partially get updated. After the crash, the system boots and wishes to mount the file system again (in order to access files and such). Given that crashes can occur at arbitrary points in time, how do we ensure the file system keeps the on-disk image in a reasonable state?

Problems that can occur:
- Just the updated inode is written to disk: if we trust the pointer, we will read garbage data from the disk. There is also inconsistency because the on disk bit map is saying the data block isn’t allocated but the inode is saying it is.
- Just the updated bitmap is written to disk: Bitmap indicates the data block is allocated but but there is no inode that points to it. If unresolved this can result in a space leak
Really you have one logical operation that carries out several physical I/Os that you want to be all done atomically (update inode, bitmap and data blocks).
fsck seems like a dumb way to solve this problem, basically says just let the problems exist and periodically run a scanner to check for inconsistencies
write-ahead logging (taken from the database world) but it fs world it’s called journaling. The basic idea is before writing the structures in place, first write down a little note describing what you are about to do.
A typical journal log would contain 5 blocks: TxB (transaction start), I[v2] (inode update), B[v2] (bit map update), Db (data block write), TxE (transaction end).
Once the journal log is safely on disk, then you can overwrite the old structures in the file system, this process is called checkpointing.
Write buffering is sometimes also called immediate reporting
There is a problem with the journal write though, you don’t want to have to issue each write sequentially but issues aries if you turn five writes into a single sequential write. The disk internally may perform scheduling and complete small prices of the big write in any order. Thus you might get TxB, I[v2], B[v2] and TxE but not Db. This looks like a valid transaction so if system recovers from the log and replies this transaction though the inode is going to be pointing at some garbage data.
The middle solution is two issues the write in steps, everything except TxE and then TxE.
An even better solution was developed by former UW-Madison grad student, Vijayan Prabhakaran, when writing a transaction to a journal include a checksum of the contents of the journal in the begin and end blocks. This was the entire journal write can be done at once and if a crash occurs the filesystem can recompute the checksum to see if it matches and if it doesn’t it can discard the file-system update.
The last step is called free where at some time later after the checkpoint, the file system will mark the transaction free in the journal by updating the journal super block. This is important to prevent the journal from growing indefinitely.
Another issues with this type of journaling is having to write the data block to the disk twice, once during the journal write and once during checkpointing. An alternative method is called ordered journaling or metadata journling except the data block is not written to the journal. Instead the data block is written to the file system proper right away. This should happen BEFORE the journal write. This ensures that a pointer will never point to garbage and this rule is called “write the pointed-to-object before the object that points to it”.

TODO

Homework (Simulation)

Chapter 43. Log-structured File Systems

Aside

All interesting systems are comprised of a few general ideas and a number of details. Sometimes, when you are learning about these systems, you think to yourself “Oh, I get the general idea; the rest is just details,” and you use this to only half-learn how things really work. Don’t do this! Many times, the details are critical. As we’ll see with LFS, the general idea is easy to understand, but to really build a working system, you have to think through all of the tricky cases.

Couldn’t agree more.

Log-structured File System would first buffer all updates in an in-memory segment; when the segment is full, is it written to disk in on long, sequential transfer to an unused part of the disk. LFS never over writes existing data but rather always writes segments to free locations.

❓ Crux of the Problem

How can a file system transform all writes into sequential writes? For reads, this task is impossible, as the desired block to be read may be anywhere on disk. For writes the file system always has a choice and it is exactly this chose we hope to exploit.

Finding inodes is easy in file systems that keeps all inodes at a a fixed portion of the disk. Given the inode number and the start address, to find an inode you can calculate the exact disk address simply by multiplying the inode number by the size of an inode, and adding that to the start address of the on-disk array;
Things can get more complicated if the file system chunks and places the inodes into a group but if you know how big each chunk of inodes is and the start address of each you can do the calculations.
LFS is much harder because there is no fixed portion of the disk where the inodes are stored, instead they are scattered through the disk.
LFS uses a level of indirection between inode numbers and inodes called the inode map (imap).

❓

I don’t understand so they use this inode map to find the inodes but yet it stores chunks of the inode map right next to where it is writing all the other new information. Thus you are left with the same problem, how do you find the inode map if it’s spread across the disk? The file system must have a fixed and known location on the disk to begin the file lookup so they use a checkpoint region (CR).

TODO

Homework (Simulation)

Chapter 44. Flash-based SSDs

solid-state storage devices have no mechanical or moving parts like hard drives but instead are built out of transistors, much like memory and processors.
flash or NAND-based flash is the backing technology that makes SSDs persistent.
To write to a given chunk of flash (flash page) you first have to erase a bigger chunk (flash block) which be expensive and writing too often to a page will cause it to wear out.

❓ Crux of the Problem

How can we build a flash-based SSD? How can we handle the expensive nature of erasing? How can we build a device that lasts a long time, given that repeated overwrite will wear the device out? Will the march of progress in technology ever cease? Or cease to amaze?

single-level cell (SLC) flash, only a single bit is stored within a transistor.
multi-level cell (MLC) flash, two bits are encoded into difference levels of a charge.
Flash chips are organized into banks or planes which contain a large number of cells.
A bank is accessed in two difference sized units:
- blocks (aka erase blocks)
- pages
Each bank there are large number of blocks and with in each block there are large number of pages
To write to a page in a block you have to erase the entire block
read is used to read a page and erase and program are used in tandem to write.
SSDs can access any location uniformly, often this means the device is a random access device
Pages are a state machine of INVALID, ERASED, and VALID
SSD internals contain flash chips, SRAM (volatile memory) useful for caching and buffering of data and mapping tables, control logic or orchestration device
One major function of the control logic is to satisfy client reads and writes, turning them into internal flash operations, this is called the flash translation layer or FTL.
The FTL takes read and write requests on logical blocks (OS only knows about block devices) and then turns them into low-level read, erase and program commands on the underlying physical blocks and physical pages.
FTL aims to reduce write amplification which is defined as the total write traffic (in bytes) issued to the flash chips by the FTL divided by the total write traffic (in bytes) issued by the client to the SSD.
wear leveling is the term used to describe ensuring that all blocks wear our at roughly the same time
trim is introduced as another command that you can call to let the SSD know it’s that this logical block is no longer needed. If you don’t call trim the OS wont tell the SSD that this data is no longer needed and wont be able to GC it. Hard disk drives don’t have this issue because they can update data in place whereas SSDs can’t

TODO

Homework (Simulation)

Chapter 45. Data Integrity and Protection

❓ Crux of the Problem

HOw should systems ensure that the data written to storage is protected? What techniques are required? How can such techniques be made efferent, with both low space and time overheads?

Review

Must read.

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

Homework (Simulation)

Chapter 10. Multiprocessor Scheduling (Advanced)

Homework (Simulation)

Chapter 13. The Abstraction: Address Space

Homework (Code)

Chapter 14. Interlude: Memory API

Homework (code)

Chapter 15. Mechanism: Address Translation

Homework (Simulation)

Chapter 16. Segmentation

Homework (Simulation)

Chapter 17. Free-Space Management

Homework (Simulation)

Chapter 18. Paging: Introduction

Homework (Simulation)

Chapter 19. Paging: Faster Translations (TLBs)

Homework (Measurement)

Chapter 20. Paging: Smaller Tables

Homework (Measurement)

Chapter 21. Beyond Physical Memory: Mechanisms

Homework (Measurement)

Chapter 22. Beyond Physical Memory: Policies

Homework (Simulation)

Chapter 23. Complete Virtual Memory Systems

Chapter 24. Summary Dialogue on Memory Virtualization

Chapter 25. A Dialogue on Concurrency

Chapter 26. Concurrency: An Introduction

Chapter 27. Interlude: Thread API

Homework (code)

Chapter 28. Locks

Homework (Simulation)

Chapter 29. Lock-based Concurrent Data Structures

Homework (code)

Chapter 30. Condition Variables

Homework (code)

Chapter 31. Semaphores

Homework (code)

Chapter 32. Common Concurrency Problems

Homework (code)

Chapter 33. Event-based Concurrency (Advanced)

Homework (code)

Chapter 36. I/O Devices

Chapter 37. Hard Disk Drives

Homework (Simulation)

Chapter 38. Redundant Arrays of Inexpensive Disks (RAIDs)

Homework (Simulation)

Chapter 39. Interlude: Files and Directories