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

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

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)