Operating Systems: Three Easy Pieces

Created Jan 26, 2025

Reading notes on Operating Systems: Three Easy Pieces (OSTEP), read alongside the course. Each chapter starts with the date I read it.

Virtualization: The CPU

Virtualization: Memory

Concurrency

Persistence

Appendix

Appendix B: Virtual Machine Monitors

Chapter 2: Introduction to Operating Systems

1/22/2025

What happens when a program runs? It executes instructions, and the following steps take place millions of times every second until the program is complete. This is the Von Neumann model of computing:

Processor fetches an instruction from memory
Processor decodes it
Processor executes it
Processor moves onto the next step

The operating system is a body of software makes sure that the system operates correctly and efficiently so that it can easily run programs.

Virtualization is the technique of taking a physical resource and transforming it into a virtual form that is easier to use via APIs.

A typical OS exports a few hundred system calls that applications can use.
- "the OS provides a standard library to applications"
Allows many programs to run and concurrently access devices.
- the OS is also known as a resource manager where each of the CPU, memory, and disk is a resource of the system.

We can run multiple programs at once, but how is this possible when we only have one processor?

It's actually an illusion.
The process of virtualizing the CPU is where the OS creates multiple virtual CPUs from a single or a small set of CPUs, which allows programs to seemingly run at once.

Policies are used to answer questions like: if two programs want to run at the same time, which should run.

Mechanisms are implemented by the OS.

E.g., the ability to run multiple programs at once.

Memory is an array of bytes

Read memory by specifying an address
Write/update memory by specifying the address at where to write to.
Programs keep its data structures in memory and access them through instructions like load/stores.
Instructions are also stored in memory too, which means that memory is accessed on each instruction fetch.

What happens when we run two programs that access the "same" specified memory 0x200000?

They update the value independently as if each program has its own private memory, instead of sharing it with other running programs.
In this situation, the OS is virtualizing memory.
Each process accesses its own private virtual address space, which the OS maps to a physical memory of the machine, which is shared.

Concurrency refers to the problems that arise when working on many things at once in the same program. E.g., the OS juggles running one process and the other.

modern multi-treaded programs exhibit the same problem.
the main program creates two threads using Pthread_create(). A thread is like a function running within the same memory space as the other functions, with more than one of them active at once.

Example of a concurrency problem. Say you have two threads, where each one increments a shared variable N times.

The result for high numbers of N is inconsistent, sometimes giving the right or wrong number
This happens because instructions are executed one at a time and you need three instructions to increment the counter: load the value of the counter from memory to the register, increment it, and store it back into memory. Because the three instructions do not execute atomically, strange things can happen.

Persistence. In system memory, data can be easily lost because devices like DRAM store values in a volatile manner, meaning data can be lost when there is now power. Therefore, we need hardware/software that can store data persistently.

hardware is some kind of input/output device. E.g., a hard drive or solid-state drives
software in the OS that manages the disk is called a file system; it is responsible for storing any files the user creates in a reliable and efficient manner to the disks.
OS does not create private, virtualized disk for each application because it is assumed that users would want to share the information that is in files. E.g., when you write a C program, you might use an editor to create a file and then use the compiler to turn the source code to an executable which is then ran.

What happens when you try to create a file /tmp/file that contains the string "hello world"?

three calls to OS are made
- first call is to open() which opens the file and creates it
- second call is to write(), which writes some data to the file
- last call is to close() which closes the file thus the program can't write any more data to it*
these system calls are routed to the file system, which handles the request and returns some kind of error code.
typically, file systems delay writes for a while to hopefully batch them into larger groups (for performance reasons).
file systems typically incorporate a intricate write protocol such as journaling or copy-on-write, which carefully orders writes to disk to ensure that if a failure occurs during the write sequence, the system can recover to a reasonable state afterwards. Many data structures and access methods are used to make these operations efficient.

The basic goal of an OS is to build abstractions to make the system easy to use. Other goals are:

have high performance / minimize overheads (either or both) of the OS
- overheads come in: extra time (more instructions) and extra space (in memory or disk).
provide protection between applications and between the OS and the application.
- the malicious / accidental bad behavior of one does not harm others
- leads to the principle of isolation
run non-stop because when it fails, all applications on the system will fail as well.
- so we need a high degree of reliability.
energy-efficiency
security (extension of protection) against malicious applications
mobility: run on smaller devices

A little history:

early on, the OS didn't do much. It was just a set of libraries with commonly-used functions, so that programmers didn't have to write low-level I/O handling code (OS would provide the API instead).
batch processing was when a number of jobs were set up and then run by a batch by the human operator. Computers at this point were too expensive if it was idle.
if you allowed an application to read anywhere on the disk, there would be no privacy, thus the file system as a library did not make sense and the system call was invented. Instead of providing OS routines as a library (where you would make procedure calls), you would add a special pair of hardware instructions / hardware states to make the transition into the OS a more formal, controlled process.
- system vs procedure call: a system call transfers control (jumps) into the OS while simultaneously raising the hardware privilege level. User applications would be in user mode which means the hardware restricts what apps can do (e.g., no I/O request to disk). When a system call is initiated (using a trap instruction) the hardware transfers control to a pre-specified trap handler and raises privilege level to kernel mode (full access to hardware). When the OS is done servicing the request, the control is returned to the user via a return-from-trap instruction which reverts back to user mode and passes the control back to the application where it left off.
OS took off in the era of computing beyond the main frame (minicomputer). Multiprogramming was common because it made better use of machine resources. The OS could run multiple jobs into memory and switch rapidly between them, which improved CPU utilization. I/O devices were slow, so if you made the program wait on the I/O to be serviced, then it would be a lot of wasted CPU waiting time.
- Memory protection was important because you don't want one program to be able to access the memory of another program.
- concurrency issues were now introduced because the presence of interrupts was a challenge.
- Unix OS was introduced. Important to the history of OS because it brought together great ideas, one being that small programs can be connected together to form larger workflows.
Personal computer (PC) allowed one machine per desktop.

The book doesn't cover

networking code
graphics devices
deep security issues

Book will cover

virtualization of CPU and memory
concurrency
persistence

Chapter 4: The Abstraction: The Process

1/29/2025 website

Process: a running program.

it's a lifeless thing. It has a bunch of instructions, some static data, and it waits to be sprung into action
the OS is the one that runs processes, which could be in the tens or hundreds of processes.

There are a few physical CPUs available, how do you make them readily available to programs?

Virtualizing the CPU is running one processes, stopping it, and running another, which creates an illusion that there are many virtual CPUs that exist when there is only one (or a few).

Also known as "time sharing" the CPU, which allows users to run as many concurrent processes as they would like.
- This basic technique can be used for other resources (e..g, network link). Resources are used for a little while by entities.
- The counterpart is space sharing, where a resource is divided (in space) for those who want to use it. E.g., a disk space is a space-shared resource where a block can be assigned to a file, and won't be assigned to another file until the user deletes the original file.
If many concurrent processes are being run, the CPU is shared, and the cost is performance

Mechanisms are low level methods or protocols that implement a needed piece of functionality.

One example is the context switch which gives the OS the ability to stop running one program and start running another on a given CPU.

Policies are algorithms that make decisions within the OS.

e.g., given the number of possible programs to run on a CPU which program should the OS run/ A scheduling policy in the OS will make this decision using historical information, workload knowledge, and performance metrics

Mechanisms vs policy: mechanisms answer the how question (e.g., how does the OS perform a context switch) and policies answers the which question (which process should we switch to). Separating these two concepts allows us to change policies without having to rethink mechanisms, which is a form of modularity.

The Process

At a given moment, a process can be summarized by taking an inventory of the different pieces of the system it accesses or affects during its execution.

Machine state: what a program can read / update during its execution.

At any given time, what parts of the machine are important to the execution
Components:
- Memory: the data the running program reads / writes sits in memory. The memory that the a process can access is called its address space.
- Registers
  - Special registers include the program counter (PC) which is also called the instruction pointer (IP), a register that tells us which instruction of the program will execute next.
  - Stack pointer and associated frame pointers are also used to manage the stack for function parameters, local variables, and return addresses.
- Storage devices, like I/O information (list of files that a process currently has open).

Process API

An interface an OS may offer:

Create: some method to create a new process. This is invoked when a command is entered in the shell or when you double-click an application icon.
Destroy: destroys processes forcefully. Many processes will run and exit by themselves, but the user may wish to kill them
Wait: wait for a process to stop running
Miscellaneous control: other controls. E.g., method to suspend (stop running for a while) a process and then resume it (continue it running).
Status: get status information about a process like how long it has run for or what state it is in.

Process Creation

How are programs transformed into processes, i.e., how does the OS get a program up and running?

The OS must load its code and any static data (like initialized variables) into memory, the address space of the process. Programs initially reside on the disk (or flash-based SSD) in some executable format. Thus loading the program means that the OS needs to read those bytes from the disk and place them in the memory somewhere.
1. In the early days, loading is done eagerly, meaning all at once before running the program
2. Modern OSes do it lazily, meaning pieces of code are loaded only as they are needed during program execution. This is done with paging and swapping.
3. Summary: OS does work to get program bits from disk to memory (this is because the CPU accesses the RAM only and not the disk).
Memory is allocated for the program's run-time stack also known as stack, which is used for local variables, function parameters, and return addresses. The OS allocates this memory, initializes the stack with arguments (e.g., fill parameters to the main() function with argc and argv array) and gives it to the process.
Memory is allocated for the program's heap, which is necessary for dynamically-allocated data, which is requested via malloc() and freed using free(). Data structures like linked list, hash tables, and trees use the heap.
Initialization task related to the input/output. In Unix, each process has three open file descriptors by default, for standard input, output, and error. Descriptors let programs read input from the terminal and print output.

After these steps are done, the OS now has set the stage for program execution. The last task is:

Start the program at its entry point, at main() by jumping to it through a special mechanism that will be discussed in Chapter 5. Now the OS has transferred control of the CPU to the newly-created process, and thus the program execution has begun.

Process States

A process can be in different states at a given time.

States can be

Running: process is running on a processor; it is executing instructions
Ready: ready to run but for some reason the OS has chosen not to run it at this given moment
Blocked: process has performed some operation that makes it not ready to be run until some other event takes place.

States can also include

initial: the state a process is in when it is being created.
final: when it has exited but not cleaned up (zombie state in UNIX-based systems).
- Useful because it lets other processes (typically parent) to examine the return code and see if it was executed successfully (returns zero in UNIX-based systems).
- When it is in this state, the parent state can make one final call like wait() to wait for the completion of the child. This indicates to the OS that it can clean up any relevant data structures.

When states are being moved, they have specific terms:

Scheduled is being moved from ready to running
Descheduled is being moved from running to ready.
I/O: Initiate is when a process has become blocked from running.
I/O: Complete is when the some event occur when the process is moved to be ready again from blocked

The OS must make decisions to decide what to run. These types of decisions are made by the OS scheduler.

Data Structures

Ready processes are tracked in the process list. It also includes additional information to track what processes are running.

Each entry is found in the process control block (PCB), which is a structure that contains information about the specific process.

The OS needs to track the blocked processes, when I/O events are complete, and have a way to wake up the correct process.

OS tracks the register context of a process, which holds the content of the registers. This is normally tracked when a process is stopped. Its registers are saved to this memory location. This can be restored to run the process again. This technique is known as context switching.

Chapter 5: Interlude: Process API

1/29/2025 website

In UNIX, you create new processes with fork() and exec(). wait() is used by a process that is waiting for a process it has created to be complete.

Process identifier (PID) is used to name the process.

`fork()`

The system call to create a new process.

When the process calls fork(), the OS creates a process that is almost the exact copy of the calling process. That means that to the OS there are two copies of the program running, and they both at the point where you are about to return from the fork() system call. In other words, the new process does not start running at main() and comes back into life as it had called fork() itself.

What's different?

it has a copy of its own address space, registers, PC, and the value it returns from fork() is different
- parent receives the PID of the newly-created child and the child receives the return code of 0. This is helpful so that you can write code that handles different cases.

The output of a program with forking is not deterministic. If it is running on a system with a single CPU, then either the child or parent might be scheduled to run first.

`wait()`

wait() deletes its execution until the child finishes executing and then returns to the parent. It makes the output deterministic.

`exec()`

Used to run a program different from the calling program since fork() is only useful if you want to run copies of the exact same program.

This system call is provided the name of an executable and some arguments. It loads code and static data from that executable and overwrites its current code segment and static data. The heap, stack, and other parts of the memory space of the program are re-initialized. Then, the OS runs the program and passes the arguments as the argv of that process.

Note: no new process was created; rather, it transformed the currently running program into a different running program
After exec() in the child, it's almost as if the original program that was overwritten was never ran.
Successful calls to exec() never returns.

Design

The shell is just a user program.

It shows you a prompt where it takes in the name of the executable program plus arguments
It figures out where in the file system the executable resides
Calls fork() to create a child process
Calls a variant of exec()
Waits for program to run with wait()
Prompts for input again

Why do we have this set of interface? It lets the shell run code after fork() and before exec(). This may involve altering the environment.

In the case of wc p3.c > newfile.text, the output of the wc program is redirected into the file newfile.txt.
- when the child is created, before calling exec(), the shell closes standard output and opens up the file newfile.txt. Then any output from the wc program will be sent to the file instead of the screen (this behavior is enabled by open file descriptors that are kept open across exec() calls)

How does the OS manage file descriptors?

UNIX systems start looking for free file descriptors at zero. So one way to redirect is you can close STDOUT_FILENO, which is the first one, and open a new file, which would be assigned. Subsequent writes to the standard output file will be routed to the newly-opened file instead. Note that no output will appear on the terminal after that.

UNIX pipes (i.e., queue) use the pipe() system call. The output of one procecss is used as the input to the next.

eg., grep -o foo file | wc -l

Process Control

kill() system call is used to send signals to a process.

In UNIX, certain keystroke combinations are configured to deliver a specific signal.

control-c sends a SIGINT (interrupt) to a process (which normally terminates it)
control-z sends SIGTSTP (stop) signal which pauses it mid execution. (Resumable with fg).

You can send signals to individual process or an entire process group.

A process should use the signal() system call to "catch" various signals. It ensures a particular signal is delivered to a process, and it will suspend its normal execution and run a particular piece of code in response to the signal.

Permissions to send signals?

we don't want anyone to send signals and compromise the usability and security of a system
the user notion means that after establishing credentials, it logs in and gains access to system resources. The user can launch processes and have full control over them.
- They can only control, meaning pause / kill / etc, their own processes and its the job of the OS to parcel out resources to each user and process.

Tools

The manual pages or man pages are documentation on UNIX systems. They were made before the web. You should also read the man pages for the shell you are using and the system calls your program make.

shows what return values and error conditions exist
RTFM: read the fucking man

ps allows you to see what processes are running.

top displays the processes of the system and how much CPU and other resources they are eating up.

kill sends signals to the processes

killall is more user friendly.

MenuMeters is an app for Mac that shows how much CPU is being used.

A system typically has an administer, which is not limited the way that users are.

can kill processes that are not started by this user
they can run shutdown
n UNIX, these users are called the superuser or root.

Chapter 6: Mechanism: Limited Direct Execution

1/27/2025

How do we virtualize the CPU?

by time sharing the CPU: run one process for a little while, then run another so that many jobs run seemingly at the same time

What challenges does this bring?

Performance: cannot add excessive overhead
Control: retain control over the CPU so that one process doesn’t take over the machine or access information it should not be allowed

Limited direct execution (LDE) protocol: run the program directly on the CPU. To run a program, the OS creates a process entry for it in a process list, allocates some memory for it, loads the program code into memory from disk, locates its entry point (like the main() routine), jumps to it and then starts running the user’s code. When the program returns, then it frees its memory of the process and removes it from the process list.

Limitations of direct execution
- How does the OS make sure the program doesn’t do anything that we don’t want it to do
- How does the OS stop it from running the process and switch to another, thus implementing time sharing
Advantages of direct execution
- Really fast because it runs natively
Two phases
- 1. At boot time, the kernel initializes the trap table an the CPU remembers the table’s location via a privileged instruction
- 1. When we run a process, the kernel sets up a few things (e.g., allocating a node on the process list, allocating memory) before using a return-from-trap instruction to start the execution of the process. It also switches the CPU to user mode before.
- When the process wishes to issue a system call, it traps to the OS which handles and returns control via a return-from-trap.
- When the process is complete, then it returns from main() with some stub code that will properly exit the program (like exit() system call, which traps into the OS).
- Then the OS cleans up

Restricted operations: what if the process wishes to perform a restricted operation? How do we allow it to without giving the process complete control?

A bad approach is letting the process have any I/O operation access, but it would be bad because they could read/write the entire disk.
The better approach is to introduce a new processor mode known as user mode. Code run in this mode is restricted in what it can do. For example, if a process in user mode tries to issue an I/O request, the processor would raise an exception and the OS would kill the process. In contrast, the kernel mode (which the OS or kernel runs in), can perform all privileged operations like I/O requests.
- To switch between the two modes, the OS provides special instructions to trap into the kernel, meaning it jumps into the kernel and rises the privilege level to kernel mode, and return-from-trap back to the user-mode, meaning it returns into the calling user program while simultaneously reducing the privilege level to user mode. There are instructions that allow the OS to tell the hardware where the trap table resides.
  - The hardware needs to be careful when executing the trap to make sure it saves enough of the caller’s register (program counter, flags, etc) in order to return correctly when the return-from-trap instruction is issued. This data is saved onto a per-process kernel stack and popped off when user-mode program resumes execution
  - The trap knows which code to run inside the OS using a trap table which is set up at boot time. This is needed because the calling processes can’t specify an address to jump to (or else it can jump anywhere and get the kernel to run arbitrary code sequences). The kernel must carefully control what code is executed upon a trap. At boot time, the machine is in kernel mode and can configure the machine as needed be. One of the first actions is to specify what code to run on certain exceptions (e.g., what code to run if hard disk interrupt takes place). The OS then informs the hardware of these trap handlers with some special instructions. The hardware remembers the location of these handlers so it knows what code to jump to when system call and exceptions take place.
    - To execute the instruction to tell the hardware where the trap tables is a privileged operation.
- If the user wants to perform a privileged operations then the user program can perform a system call, which allows the kernel to expose certain pieces of functionality like accessing the file system, creating/destroying processes, communicating with other processes, and allocating memories. There are a few hundred calls (see POSIX standard for details).
  - To specify the system call to make, there is a system-call number that is assigned to each system call. The user code is responsible for placing the desired system-call number in a register / specific location on stack so that the OS, when handling the system call from inside the trap handlers, can read this number, check its validity, an execute the corresponding code.
    - We use this number system because the indirection is a form of protection. The user code can never specify an exact address to jump to, but rather via the particular service number.

Switching between processes: how do you switch between processes? It’s tricky because when a process is running on the CPU, by definition it means that the OS is not running, meaning it can’t do anything at all. There’s crux: how does the OS regain control of the CPU to switch processes?

The cooperative approach is that the OS trusts the processes of the system to behave reasonably. Processes run for too long are assumed to periodically I’ve up the CPU so that the OS can run some other task. Processes do often transfer control whenever they make system calls. There is also the yield system call, which does nothing except for transfer control to the OS. Applications also transfer control when they do something illegal (e.g., divide by zero, access forbidden memory) because they will generate a trap.
- This approach fails when the process ends up in an infinite loop. This means you have to reboot the machine
The non-cooperative approach: use a timer interrupt. A timer device is programmed to raise an interrupt every so many milliseconds so that whenever it is raised, the running process is halted, and the interrupt handler is ran, which means the OS has regained control!
- As we discussed before, the interrupt handler is specified (what code to run) at boot time.
- The timer must be started at boot time and is a privileged operations. The timer can be turned off via a privileged operation.
- When this interrupt occurs, it needs to save enough state of the program so that the return-from-trap instruction can resume the running program correctly. It does so in the same style as the system-call trap. Various registers gets saved and is easily restored.
- When the OS regains control, it needs to make a decision on whether it should continue running the running process or switch. This decision is made by the scheduler.
  - If the decision is to switch, then the OS executes a low-level piece of code referred to as a context switch. switch() is simple: the OS saves a few register value (general purpose registers, PC, kernel stack pointer) for the currently-running process onto the kernel stack, for example, and then restores the soon-to-be-executed process. When the return-from-trap is executed, the system resumes execution of the other process. By switching stacks, the kernel enters the call to the switch code int he context of the interrupted process and returns in the context of the soon-to-be-executing process, which means it becomes the currently running process. The context switch is then complete. Note that there are two register saves/restores:
    - User registers of the running process are saved by the hardware using the kernel stack of that process when the timer interrupt occurs
    - When the OS switches from process A to B, the kernel registers are saved by the software (OS) into memory in the process structure of the process. This moves the system from running as if it just trapped into the kernel from A to as if it was trapped into the kernel from B.

Side note: system call (e.g., open(), read()) vs procedure call in C (a ”function”)

A system call looks just like a procedure call, so how does it know that it’s a system call?
- A system call is a procedure call, but one with a trap instruction.
When you call open(), you execute a procedure call into the C library. It uses an agreed-upon calling convention to put the arguments specified to well-known locations. The system-call number is also placed into a well-known location (stack or register). Then, the trap instruction is executed. Then the C library code will get the trap’s return value and then return control to the program. This part of the C library that makes system calls are hand-coded in assembly in order to follow conventions and execute the hardware-specific trap instruction. Someone wrote that assembly code for you!

Side note: wary of inputs in secure systems

OS must check what the user passes in and ensure that arguments are properly specified, or otherwise reject the call
Imagine with a write() system call, the user specifies a “bad” address (e.g., one inside the kernel’s portion of the address space). Then it would be possible for the user to read the kernel memory because the kernel virtual memory will include all the physical memory of the system.

Side note: application misbehavior is dealt with harshly. One strike and you are terminated. This strict approach is necessary because what else should the OS do if it tries to execute illegal instructions?

Side note: the reboot is great because it moves software back to a known and tested state. A reboot reclaims stale or leaked resources that could be too hard to handle.

Reboots Are too hard to handle which is why it is uncommon to see periodic reboots.

What happens when an a timer interrupt occurs during a system call or when you get interrupted while handling another interrupt.

One way to address this is that the OS may disable interrupts during interrupt processing. Needs to be done carefully because you could lose interrupts if paused for too long.
OS have also developed locking schemes that protect concurrent access to internal data structures. This is useful for multiprocessors when multiple activities are happening within a kernel at the same time.

In summary, limited direct execution is the idea that programs are run in the CPU but the hardware should be set up so that the processes is limited in what it can do without help from the OS.

the OS baby proofs the CPU so that the process can run efficiently on the CPU

Chapter 7: Scheduling: Introduction

2/5/2025

Scheduling policies or disciplines. Chapter 7

Workload

Workload refers to the processes running in the system.

Important to determine for building policies.

Processes are sometimes called jobs and we will make some (unrealistic) assumptions about them:

each job runs for the same amount of time
all jobs arrive at the same time
once started, each job runs to completion.
all jobs only use the CPU (i.e., they perform no I/O)
the run-time of each job is known.

Each of these assumptions are eventually relaxed.

Metrics

Scheduling metrics is the way we measure scheduling so that we can compare different scheduling policies.

Turnaround time

The time at which the job completes minus the time at which the job arrived in the system.

Performance: Fairness: an example is the Jain's Fairness Index. Response time: the time from when the job arrives in a system to the time that it is first scheduled.

imagine if you are at the terminal, typing, and having to wait 10 seconds to see a response in the system.

Performance and fairness are at odds.

Aside: non-preemptive schedulers are systems that run jobs to completion before considering whether to run a new job. Preemptive schedulers are willing to stop one process from running to run another. Thus, the scheduler needs to performs a context switch to do this.

First in, first out (FIFO)

FIFO is also known as First Come, First Served (FCFS).

FIFO's flaw is the convoy effect, where a number of relatively-short potential consumers of a resource get queued behind a heavyweight resource consumer.

Results in a high average turnaround time

Shortest Job First (SJF)

Runs the shortest job first, then the next shortest, and so on.

SJF is the optimal scheduling algorithm if the jobs are all arriving at the same time. However, this is not true and can also cause the convoy problem (slowest job comes in first)

This is a non-preemptive scheduler.

Shortest time-to-completion first (STCF)

The scheduler can pre-empt a job.

Any time a new job enters the system, the STCF scheduler determines which of the remainning jobs has the least time left, and schedules that one.

Round Robin (RR)

Runs jobs for a time slice (or scheduling quantum) and then switches to the next job in the queue until all jobs have finished

Also called time-slicing

The length of the time slice is critical:

the shorter it is, the better the response time
when the time slice is too short, then the cost of context switching will dominate the overall performance.
You have to make it long enough to amortize the cost of switching without making it so long that the system is no longer responsive.

RR has terrible turnaround time but it is fair.

Incorporating I/O

When a job initiates an I/O request, it will be blocked while waiting for I/O completion. The scheduler has to make a decision when the I/O is request is sent and when it is complete.

Overlap operations to maximize the utilization of systems. Especially when performing I/O or sending messages to remote machines. Start that operation and the switch over to other work.

Say that a 50ms request needs to perform an I/O operation every 10ms, it should then treat every CPU burst as a 10ms sub-job.

This makes sure that processes that are "interactive" get run frequently, and while they are doing I/O then the other CPU-intensive jobs run, thus better utilizing the processor.

Summary

The worst assumption of them all is that we know how long each job is. In fact, a general purpose OS knows very little. No a priori knowledge of job length.

A scheduler can use the recent past to predict the future: the multi-level feedback queue

Chapter 8: Scheduling: The Multi-Level Feedback Queue

2/5/2025 Chapter 8 Goal is to optimize turnaround time (done by running shorter jobs first but we don't know how long the job will run for) and to make the system feel responsive (minimize response time) (recall RR has good response time but bad turnaround time).

The multi-level feedback queue is an excellent example of a system that learns from the past to predict the future

learn about processes as they run
use the history of the job to predict its future behavior

Build:

Has a number of distinct queues, each with a priority level.
- A job that is ready to run is in a queue
- Priorities decide which job should run at a given time: the higher priority.
- If more than one job is in a given queue, they have the same priority
RR scheduling is used among the jobs in a queue

Summarize the above to these basic rules:

Rule 1: If Priority(A) >Priority(B), A runs (B doesn’t).
Rule 2: If Priority(A)=Priority(B), A & B run in RR

How does MLFQ scheduling set priority

They are not fixed
The priority varies based on the observed behavior. For example, if a job repeatedly relinquishes the CPU while waiting for input, then MLFQ will keep this priority high because that is the behavior of a interactive process.

A job's allotment: the amount of time a job can spend at a given priority level before its priority is reduced.

Rule 3: When a job enters the system, it is placed at the highest priority (the topmost queue).
Rule 4a: If a job uses up its allotment while running, its priority is reduced (i.e., it moves down one queue)
Rule 4b: If a job gives up the CPU (for example, by performing an I/O operation) before the allotment is up, it stays at the same priority level (i.e., its allotment is reset)
- e.g., waiting for user input from keyboard or mouse.
- when it relinquishes the CPU before its allotment is complete.

Concern is starvation: when there are too many interactive jobs int eh system and they consume all the CPU time such that long-running jobs never receive CPU time (they starve).

a developer could game the scheduler so that it can run for 99% of its allotment and then relinquish control.

Another question: what if a program changes its behavior and becomes interactive. Then will the priority raise?

What if we boost the priority of all the jobs in the system?

Rule 5: After some time period S, move all the jobs in the system to the topmost queue
- This guarantees that processes do not starve and that if a program becomes interactive then it has a chance to stay on the top priority
- What should S be? Sometimes called a voo-doo constant.

Tip: Ousterhout’s Law: configuration file filled with default parameter values that a seasoned administrator can tweak when something isn’t quite working correctly. As you can imagine, these are often left unmodified, and thus we are left to hope that the defaults work well in the field.

How do we prevent gaming?

accounting of CPU time at each level.Scheduler should keep track: once a process has used its allotment, it is demoted. Whether it uses its allotment in a long burst or many small ones, it does not matter.

Update rule 4a and 4bL

Rule 4: Once a job uses up its time allotment at a given level (regardless of how many times it has given up the CPU), its priority is reduced (i.e., it moves down one queue).

How to parameterize the scheduler?

how many queues, time slice size?
One method is to let it be easy to configure
FreeBSG scheduler uses a formula to calculate the current priority level based on how much CPU the process has used along with decay
decay-usage algorithm: priority boost
Use user advice to set priority. e.g., nice increases/decreases the priority of a job
- also called hints. Used in many parts of the OS (scheduler with nice, memory manager with madvise, and file system with informed prefetching and caching)

Almost all OS use a form of MLFQ. It observes execution and prioritizes accordingly so that it has good overall performance (similar to SJF / STCF) for short running jobs and it is fair and makes progress for long running programs.

Chapter 14: Interlude: Memory API

3/24/2025

Memory allocation interfaces in Unix. How do we allocate and manage memory?

Types of Memory

Stack memory

allocation / deallocation is managed implicitly by the compiler. It will make space on the stack when you call into the function. When you leave the function, the compiler will deallocate.
sometimes called automatic memory.

Declaring in C is easy: if you need space in your function an integer you just initialize the variable:

void func() {
	int x; // declares integer on the stack
	...
}

If you want memory that lives beyond a call invocation, do not define on the stack.

The second type of memory is heap memory

allocation / deallocation is the responsibility of the programmer.

void func() {
	int *x = (int *) malloc(sizeof(int));
}

note that a stack allocation also was made in order to store the pointer
malloc() requests space for the integer on the heap.

`malloc()` call

Pass in a size to ask for room on the heap. Success returns pointer otherwise it returns NULL.

needs inclusion of the header file stdlib.h,
In the C library, which all C programs link by default, it already has the code for malloc(). Adding the header just lets the compiler check if you are calling malloc() correctly.
parameter of type size_t, which is the number of bytes you need.

Use sizeof instead of writing the number of bytes

considered an operator because at compile time, the size is known and thus a number will be substituted in.
be careful bc strings need a end-of-string char.

malloc() returns a pointer to type void. The programmer decides what to do with it. Typically, you need to cast (not necessary).

`free()` call

Newer languages may have automatic memory management. Instead of freeing a garbage collector figures out what memory you no longer have references to and frees it for you.

Some common issues:

forgetting to allocate memory: some routines expect the memory to be allocated before you call them like strcpy(dst, src). Leads to segmentation fault.
not allocating enough memory: buffer overflow.
forgetting to initialize allocated memory. You can call malloc() properly but forget to fill in some values. It will encounter an unintiailized read where it reads from the heap some data of unknown value. Who
forgetting to free memory: memory leak. Forget to free memory and it slowly leaks memory, which eventually can run out. Then a restart is required. When you're done with a chunk of memory, you should make sure to free it. Even in modern languages you may have a reference to it thus it never is freed.
free memory before you are done with it. dangling pointer. If this pointer is used, can crash the program or overwrite valid memory.
freeing memory repeatedly. double free. The result is undefined. mem-allocation library can be confused
calling free() incorrectly. It expects a pointer from malloc() earlier. So when you pass in other values, bad things happen. called invalid frees.
use purify or valgrind to identify source of mem-related problems.

Aside: no memory is leaked once your process exists:

say you are exiting soon, do you need to free?
First level of memory management is performed by the OS: hands out memory to processes when they run, and takes it back when the processes exit (or otherwise die).
The second level of management is within each process. For example, within the heap when you call malloc() andfree(). Even if you fail to call free(), and thus leak memory in the heap, the operating system will reclaim all the memory of the process when the process is done.
thus for short-lived programs, leaking memory does not cause any operational problems. When you write a long-running server (like database or web server), then its a bigger issue.

Tip: just because a program compiles and runs, does not mean the program is correct.

Underlying OS support

malloc() are not system calls, rather library calls. The malloc library manages space within virtual address space, built on top of system calls.

One system call it uses is brk, which changes the location of the program's break (the location at the end of the heap).

takes one argument (address of new break) and thus inc or dec the size of the heap depending on whether this break is larger or smaller than the current break.
sbrk is passed an increment but otherwise is for the same purpose
These calls should never be directly called.

mmap() obtains memory from the operating system. Creates anonymous memory region: region that is not associated with any particular file but rather with the swap space. Can be treated and managed like a heap.

Other Calls

calloc() allocates memory and zeroes it before returning.

Prevents errors where you assume that memory is zeroed and forget to initailize it yourself (uninitialized reads)

realloc() is useful when you've allocated space for something (like an array) and then you need to add something to it. it copies the old region into it and returns pointer to the new area

Chapter 15: Mechanism: Address Translation

Virtualization of the CPU: Limited direct execution (LDE): letting the program run directly on the hardware, but at certain points in time (such as when a process issues a system call, or a timer interrupt occurs), arrange so that the OS gets involved and makes sure the "right" thing happens.

As a result, the program has full involvement aka its an effective virtualization. However, by imposing at critical points in time, the OS still maintains control over the hardware.

We want to use a similar strategy for virtualizing memory to achieve efficiency and control.

Control = no application can access memory that is not their own to protect applications from one another.
Flexibility = programs can use their address space in whatever way they would like.

General technique is hardware-based address translation (address translation). Hardware will translate a virtual address to a physical address where the information is actually located.

The OS must be involved to set up the hardware (since it cannot alone virtualize memory) to translate aka it must manage memory, keeping track of what locations are free and in use. It must create an illusion to the programs that it has its own private memory (where the code and data reside), but behind the scenes is that many programs are sharing memory.

Example

int x = 3000;
x = x + 3;

will be turned into

128: movl 0x0(%ebx), %eax   ; load 0+ebx into eax
132: addl $0x03, %eax       ; add 3 to eax register
135: movl %eax, 0x0(%ebx)   ; store eax back to memory

presume that the address of x has been placed on %ebx.
assume code and data are laid out in the process's address space starting at address 128 (near the top), and the address of x is at 15kb (near the bottom). Then the following memory accesses take place
- fetch instruction from 128 -> execute the load which loads the value from 15KB -> fetch instruction at 132 -> execute -> fetch address at 135 -> execute (store to 15KB).

From the perspective of this program, the address space starts at 0 and grows to a max of 16KB, so all its memory references should be between these values.

Now our demands:

what if we want to relocate this process in memory so that it is transparent to the process. (it thinks its accessing 0 but really its somewhere else)

Dynamic (hardware-based) relocation

Base and bounds or dynamic relocation is quite efficient because it requires little hardware logic and offers protection.

There are two hardware registers within each CPU that allow to place the address space anywhere we'd like in physical memory. (while ensuring the process can only access its own address space)

base register (generated by the program)
bounds or limit register ensures that he addresses are within the confines of the address space

Each program is written and compiled as if it is loaded at address zero, but the OS decides where in physical memory it should be loaded by setting the base register to that value.

Now, any memory reference is translated via physical_address = virtual_address + base. This is called address translation.

We can move address spaces even after process has started running via dynamic relocation.

The bounds register is checked by the processor first to make sure the reference is legal. If not, there will be a fault, causing an exception to be raised

The base and bounds registers are hardware structures kept on the chip (one pair per CPU)´. The part of the processor that helps with address translation is called the memory management unit (MMU). Complex technique = more circuitry.

Recap of what support from hardware is necessary:

CPU modes: a bit stored in some kind of processor status word indicates which mode the CPU is running in. It can switch on special occasions (like interrupt). The two modes are
- The OS needs to be in kernel / privileged mode so that it can access the entire machine.
- User apps are in user mode so that they are restricted.
MMU provides the base and bounds register
- Hardware needs to provide instructions to modify these registers and they should be privileged.
CPU ability to generate exceptions in situations a user program accesses an illegal memory. CPU should stop executing and arrange for an OS "out-of-bounds" exception handler, which decides how to react (likely ending process). Also, when user tries to change base/bounds register that should also be raised.
- CPU also needs to be able to inform it of the locations of these handlers, so a few more privileged instructions are needed.

OS involvement:

When a process is created
- The OS must find place for its address space in memory. To do so, the OS must track the free memory that is not in use: simplest is a free list, a list of ranges that the physical memory is not in use
When the process is terminated
- The OS must do some work to reclaim its memory for other process. It needs to put it back on the free list and clean up any associated data structures.
When programs are being switched
- Since there is only one base / bound register pair, the OS must save and restore these registers when it switches between processes. Specifically, when the OS stops running a process, it must save these values to memory in some per-process structure like the process structure or process control block.
Provide exception handler
- Install these handler at boot time via privileged instructions.
- When process accesses out of bound, CPU raises exception, OS must be prepared to take action (terminate)

To move an address space, it's simple:

deschedule the process
copy address space from current location to new location
update the saved base register.

We follow approach of Limited direct execution because the OS just sets up hardware and lets the process run directly on the CPU. It only takes over when it misbehaves.

Inefficiencies:

allocates a set amount, which could be unused and therefore a waste. This is called internal fragmentation (space inside the allocated unit not used)

Chapter 16: Segmentation

Base and bound / dynamic allocation is inefficient because

Recall internal fragmentation: waste of "free" space between a process' stack and heap.
What if the program doesn't fit into memory?

These problems are solved with segmentations: instead of having one base bound pair on MMU, why not have base and bound per logical segment of the address space. A segment is a contiguous portion of the address space of a particular length.

we can have three segments: code, stack, heap, which can be placed in diff parts of the physical memory.
- 0-16kb for OS, 16kb-24k for the stack, 24kb-32kb for code, and 32kb-64kb for the heap.
- Only used memory will be allocated in physical memory. Thus, large address spaces with large amounts of unused address space can be accommodated (sparse address spaces).

Hardware support needed:

three base and bound register pairs for each segment. Bound would be size of that segment.

Aside: segmentation fault or violation arises from a memory access on a segmented machine to an illegal address. This term persists even though machines may not support segmentation.

Example:

reference takes place (e.g., instruction fetch) to 100. we would add the base of the code segment. and check that 100 is less than the bound of the code segment.
a heap access takes place to 4200. we would need to extract the offset into the heap first. Say heap starts at virtual address 4096. Then we do 4200-4096 = 104 and then add the base of the heap segment. Check 104 is less than the bound of the heap segment.
If an access is done outside of bounds, then it will trap into the OS, leading to the segmentation fault.

How does the hardware know which segment the address refers to?

one approach is the explicit approach.
- the top two bits of the virtual address will tell the hardware what segment it is referring to, then the bottom 12 bits are the offset. Therefore, the hardware only needs to take the first two bits to determine which segment register to use.
- Issue: if you use two bits of the top, then one segment goes unused because you only have three segments (code, heap stack).
- Issue: limits the use of virtual address space because each segment is limited to a max size. It can't grow the segment
implicit approach.
- notices how the address was formed. E.g., address was generated from the program counter, then it is within the code segment. If it is based on the stack / base pointer, then it must be from the stack segment. Any other address is in the heap.

The stack grows backwards (to a lower address). it starts at 28kb (as an example) and it grows to 26 kb. The translation is different (backwards) so it needs extra hardware support. It needs to know which way the segment grows (which can be indicated by one bit).

depending on this bit, it will translate the virtual address differently. If backwards, adds a negative offset to calculate.

To save memory it is sometimes useful to share certain memory segments between address spaces. code sharing is common.

To support sharing, hardware support for protection bits is needed.

Takes form of a few bits per segment, that indicate whether a program can read / write / execute to a segment.
Each process will still think its accessing its own private memory, and the OS secretly share memory that cannot be modified. The illusion stands.
The hardware algorithm will now be: it checks the bounds to see if it can be accessible but it also has to check whether a particular access is permissible.
If a user tries to write to a read-only segment, the an exception should be raised.

Fine vs coarse grain segmentation.

segmentation is coarse-grained because it chops up the address space into fat chunks. Some systems allowed for smaller segments (fine-grained).

If there are many segments, you need a segment table stored in memory.

helps the OS learn which segments are in use and thus utilize main memory better.

Issues

What does the OS do on a context switch: segmentation registers need to be saved and restored. Each process has its own virtual address space so OS needs to make sure the registers are set up correctly.

When segments grow or shrink (like malloc() is called). The existing heap may be able to service the request, thus it finds free space for the object and returns a pointer to it to the caller. However, sometimes the heap itself needs to grow.

There is a system call to grow the heap sbrk() in unix. The OS will provide a bigger space, which then the object can be allocated in. If no physical memory is available the OS will reject this request.

When a new address space is created, the OS has to find a space in physical memory for its segments. Previously, we assumed that each address space was teh same size, thus physical memory can be thought of as a bunch of slots where processes would fit in. Now that each process has a number of segments, each segment could be a different size.

This creates the problem that physical memory could have a bunch of little holes of free space that makes it difficult to grow existing ones or allocate new segments. This is the problem of external segmentation.
- One solution is to compact physical memory space by rearranging the existing segments. To do this, you would need large chunk of free memory to stop processes, copy data to one contiguous region, change segment registers. It would cost a lot: memory and processor time. Also it would make it hard for segments to grow...
- A simpler approach is to use a free-list management algorithm that tries to keep large extends of memory available for allocation. like best fit, worstfit, first fit, buddy algo. (there are many, which means there is no best solution).

Summary

Helps build more effective virtualization, supports sparse address spaces, avoid huge waste of memory. It's fast and allows for code sharing. However, variable sized segments leads to problems listed above, like external fragmentation and difficult memory-allocation requests.

Still not flexible enough to support generalized, sparse address space.

Chapter 17: Free-Space Management

3/24/2025

Free-space management for paging is simple: maintain a list of fixed-sized units, and return the first entry.

In the case of user-level memory-allocation library, the free space consists off variable-sized units. The problem of external fragmentation arises (free space gets chopped into different sizes and there is no single contiguous space that satisfies the request)

Assumptions

when calling free() and providing a pointer, we don't tell them what the size is. The library figures that out.

The space the library manages is known as the heap, managed by a free list. This data structure contains references to all the free chunks of space in this region (ds not necessarily a list).

Internal fragmentation: an allocator hands out chunks of memory greater than requested and it remains unused.

Once memory is handed out to a client, it cannot be relocated to another location. Thus, no compaction of free space is possible.

Low level mechanisms.

Splitting and Coalescing

Say there is a chunk of 10 byte free, but a request is for something smaller than 10 bytes. Then the allocator must split. The first chunk will return to the caller and the second will remain on the free list.

The corollary mechanism is known as coalescing free space. Say a program frees memory, thus returning the space to the free list. It still may be divided. Thus we must look at the addresses of the chunk you are returning along with the nearby chunks. And if they sit next to each other, then they should be merged into a single larger free chunk.

Tracking the size of allocated regions

free(void *ptr) does not need a size parameter.

It is assumed that the mallloc library can determine the size of the region of memory simply through a given pointer. This is because allocators store information in the header block that is kept in memory, right before the handed-out chunk of memory.

The simple header:

typedef struct {
	int size;
	int magic;
} header_t

It contains size of the allocated region, maybe additional pointers to speed up deallocation, a magic number for integrity.

Steps:

The library would use simple pointer arithmetic to figure out where the header begins. (header_t *hptr = (header_t *) ptr - 1)
check that the magic number matches expected value
calculate the size of the newly-freed regions (size of header + size of region)

Embedding a free list

How to build a list inside of free space.

you can't just call malloc() when allocating a new load

Assume we have a 4096 byte chunk of memory to manage. (heap is 4kb). Initialize the said list with one entry of size 4096 (minus the header size).

typedef struct __node_t {
	int size;
	struct __node_t *next;
} node_t

Then you initialize the heap and put the first element of the free list inside that space.

// mmap() returns a pointer to a chunk of free space
node_t *head = mmap(NULL, 4096, PROT_READ|PROT_WRITE, MAP_ANON|MAP_PRIVATE, -1, 0);
head->size = 4096 - sizeof(node_t);
head->next = NULL;

The first entry will have size 4088.

After a request for 100 bytes, this chunk must be split into two.

assuming 8 byte header, it allocates a 108 byte chunk out of the free chunk and returns a pointer and stashes the header info before the allocated space
shrink the one free node to 2980 (4088-108)

When memory is freed, make sure to go through the list and merge neighboring chunks.

Growing the heap

If the heap runs out of space, the simplest approach is to fail it, thus returning NULL.

Traditional allocators start with a small-sized heap, and then request more memory from the OS when they run out via a system call (sbrk in Unix) to grow the heap and then they allocate new chunks from there.

sbrk request to the OS finds free physical pages, map them into the address space of the requesting process, and then returns the value of the end of the new heap; at this point a larger heap is available and the request can be serviced.

Basic Strategies

for managing free space. The ideal allocator is fast and minimizes fragemntation.

Best fit

Search through the free list and find chunks of free memory that are as big or bigger than the requested size. Return the smallest one. called best-fit chunk. (or smallest-fit chunk).

Intuition: by returning a block that is closest, it reduces wasted space. The cost is the exhaustive search (one pass)

Worst fit

opposite. Find the largest chunk return the requested amount. Goal is to leave big chunks free instead of lots of small chunks that can arise from best-fit.

Requires a pass (costly) and performs badly, leading to excess fragmentation

First fit

find the first block that is big enough and return it.

Advantage of speed but pollutes beginning with smallobjects.

How they manage free list order becomes an issue. Solution: address-based ordering: keep list ordered by address of free space, coalescing becomes easier and fragmentation si reduced.

Next Fit

keep an extra pointer to the location within the list where one was looking last. Idea: searches for free space throughout the list more uniformly, thus avoiding splintering of the beginning of the list. The performance of such an approach is similar to first fit.

Other approaches

Segregated lists

If a particular application has a few popular-sized requests that it makes, keep a separate list just to manage objects of that size; all other requests are forwarded to a more general memory allocator.

If you have a chunk of memory dedicated to one particular size, then fragmentation is less of a concern and allocaiton/free requests can be serviced quickly.

Questions arises:

how much memory to dedicate to the specialized pool

slab allocator: when the kernel boots up, it allocates a number of object caches for kernel objects that are requested frequently (locks, file-system inodes, etc.) the object caches thus are each segregated free lists of a given size and serve memory allocation and free requests quickly.

when the cache is running low, then it requests more slabs of memory from a more general memory allocator.
when the reference counts of the objects within a given slab all go to zero the general allocator can reclaim them from the specialized allocator, which is done with the VM system needs more memory.
keeps free objects on the list in pre-initialized state (cuz its costly)

buddy allocation

Making coalescing simple.

Binary buddy allocator: free memory is thought of as a big space of size 2^N.

when request for memory is made. the search for free space recursively divides free space by 2 until a block that is big enough to accommodate the request is found.
can suffer from internal fragmentation since it must be a power of two size block

However, when freed, it checks if its buddy block is free, and if so coalesces the blocks, and it recursively does so until there is no more buddy.

Works well because the addresses of each buddy pair only differs by a single bit, aka the level in thebuddy tree.

Other ideas

Lack of scaling: searching list is slow. Thus, use a good data structure to address these costs. Balanced binary tree, splay tree, partially ordered tree.

Modern systems have multiple processors and run multi-threaded workload, so these systems need to work on multiprocessing systems too.

Chapter 18: Paging: Introduction

Recap: variable sized pieces = segmentation.

difficulties with fragmentation which makes allocation difficult

What if the space was chopped up to fixed-sized pieces. This is paging in virtual memory.

Each fixed-size unit is a page. Physical memory is an array of fixed-size slots called page frames. Each of these frame can contain a single virtual-memory page.

can be used by OS too.

Improvement in flexibility: can support abstraction of address space effectively regardless of how a process uses the address space. No need for assumptions about direction of the heap and stack.

Improvement in simplicity: free space management is done with a free list that tracks all the free lists, and just grabs the first x pages.

Each virtual page is placed in physical memory. The OS keeps a per-process data structure known as the page table. It address translates each virtual page to the physical address space.

e.g., (virtual page 0 -> physical frame 3), (VP 1 -> PF 7).
Per-process! If another process were to run, then OS would make another page table which would have different mapping.
- This is because each address space requires translations.
structure of page table is determined by hardware in old systems and flexibly managed by the OS in modern systems

A virtual address will have a virtual page number (VPN) and an offset.

If the virtual address space of the process is 64 bytes, then we would need 6 bits total for our virtualized address (2^6=64) if every page size was 16 bytes, we would only need 4 bits for the offset (2^4=16). The top two bits will be used to store the virtual page number.
e.g., virtual address 21. In binary, 010101, where 01 is the VPN, offset is 0101. 5th byte of the virtual page. The page table will tell us what the physical frame number (PFN) or physical page number (PPN) the VPN maps to. Then just replaces the VPN with PFN and keeps the offset bits.

Page tables

Where is it stored

Page tables can be huge. Assuming you need 4 bytes per page table entry (PTE) to hold the translation, then you need 4MB of memory for each page table. If 100 processes, then thats 400mb. Imagine if the address space was bigger.
because of this, page table is not stored on the MMU. Instead, page table is stored in memory somewhere. Later we'll see the OS memory itself is virtualized, thus the page tables stored on OS virtual memory would be swapped out.

A linear page table is just an array. It indexes the array by the VPN and looks up the PTE at that index to find the PFN.

The PTE has a valid bit to indicate whether the translation is valid. All the unused space is marked as invalid (and when accessing invalid it will trap the OS and terminate the process).

Can have a protection bit to indicate whether the page can be read/write/executed from. Accessing in the wrong way generates trap to the OS.

present bit indicates if the page is in physical memory or swapped out (on disk).

swap parts of the address space to disk to support address spaces that are larger than physical memory.

dirty bit indicates whether the page memory has been modified since its been brought into memory

referenced/accessed bit tracks whether the page has been accessed in order to determine which pages are popular and therefore kept. This is useful for page replacement.

Too slow

To translate, it will need to first fetch the page table entry to do the translation. Then, after translation it needs to load the data from physical memory.

to do so, the hardware needs to know where the currently running process's page table location. Assume a page-table base register contains the physical address of the starting location of the page table. To find the location of this, the hardware needs to perform some functions

VPN = (VirtualAddress & VPN_MASK) >> SHIFT
PTEAddr = PageTableBaseRegister + (VPN * sizeof(PTE))

VPN_MASK would be 0x30 hex 30 or 110000 to pick out the VPN bits. Then it shifts by SHIFT = 4. which is the number of bits in the offset so that we move the VPN bits down (like 010000 to 01), which is page 1. This value is used as an index to the array of PTEs pointed to by the page table base register.
Once this physical address of the PTE is known, it can be fetched to extract the PFN. Which is a different formula that transforms it to the final physical address of the desired data.
This is what happens on every single memory references, quite complicated.

Problem: Page table too much memory and slow.

Chapter 19: Paging: Faster Translations (TLBs)

3/10/2025

Introduction

Paging to support virtual memory results in high performance overheads.

Mapping information is large
Mapping information is stored in physical memory, which requires an additional memory lookup for each virtual address. (very slow)
So how do we speed up address translation

Use hardware to speed up address translation using a translation-look aside buffer (TLB).

It's part of the chip's memory-management unit (MMU).
Essentially a cache of popular virtual-to-physical address translations.
Should be called an address-translation cache
How it works: When accessing a virtual memory reference, the hardware first checks the TLB to see if the desired translation is held there. If so, then the translation is performed quickly without consulting the page table (which holds all the translations).

TLB Algorithm

In a hardware managed TLB, the hardware handles the responsibility of page table accesses. It's algorithm would be

extract the virtual page number (VPN) from the virtual address
check if the TLB holds the translation
1. If success (a TLB hit)
  1. extract the page frame number (PFN) (address of the physical) from the entry
  2. concatenate that onto the offset from the virtual address to get the desired physical address (PA)
  3. access memory (assuming the protection checks do not fail)
2. If failure (TLB miss)
  1. hardware accesses the page table to find the translation.
  2. assuming the reference is valid and accessible, it updates the TLB with the translation. (costly because of the extra memory reference and the program will be noticeably slow)
  3. after TLB update, the hardware retries the instruction

Accessing an array

Example

there are 16 16-byte pages
- virtual address space is 8-bits. Within this:
- there is a 4-bit VPN (16 pages)
- each page is 16-byte so the offset is 4-bit
array with 10 4-byte integers in memory starting at virtual address 100
- a[0] (the first entry) begins on VPN=06 offset=04, so only 3 of the 4-byte integers can fit on this page. The next four numbers will fir on the next page. The last three entries are on page VPN=08.
When the first array element a[0] is accessed, the CPU will see a load to virtual address 100.
- This meant that the hardware extracted VPN=06 and used that to check the TLB for a valid translation. Assuming it is the first time, that means that there was a TLB miss
- The subsequent access to a[1] will be a TLB hit because it lives on the same page.
access to the fourth and eighth element will miss

The TLB hit rate (number of hits / total number of accesses) is 70% in the above example.

The TLB improved performance is due to spatial locality, the idea that the elements of the array are packed tightly into pages (i.e., they are close to one another in space).

A larger page size would have resulted in a better hit rate. Typical page size is 4KB.

Temporal locality is the quick re-referencing of memory items in time.

if we ran the loop of accessing all the elements again, then there would be a high hit rate.

Aside: Caching

a fundamental performance technique.
Take advantage of temporal and spatial locality.
Hardware caches keep copies on a small, fast on-chip memory so that the processor doesn't have to access the slow memory.
Why not make bigger caches? A cache must be small to be fast, as issues like the speed of light and other physical constraints must become relevant.

Who handles the TLB Miss?

Two possible answers: hardware or software.

In the old days, hardware completely did.

hardware used to have complex instruction set (CISC)
hardware had to know exactly where the page tables were located in memory and their exact format. Done through a page-table base register.
Intel x86 architectures has a hardware-managed TLB. It used a multi-level page table and the current page table is pointed to by the CR3 register.

On modern architectures, we have software-managed TLBs:

This is called reduced-instruction set computers (RISC)
On a TLB miss, the hardware raises an exception, which pauses the current instruction stream, raises the privilege level to kernel mode, and jumps to a trap handler. The code there will handle the TLB miss.
The code will look up the translation in the page table and use a special privileged instruction to update this TLB and return from the trap. At this point, the hardware retries the instruction.
- Note that the return-from-trap instruction to execute is different from one after servicing a system call. For the system call, the return-from-trap will execute the instruction after the trap into the OS. In our case, we want the return to resume execution at the instruction that caused the trap. This means that the hardware must save a different PC when trapping into the OS.
- When running TLB miss-handling code, the OS needs to be careful not to cause an infinite chain of TLB misses to occur.
  - Solution 1: keep TLB miss handlers in physical memory where they are unmapped and not subject to address translation
  - Solution 2: reserve entries in the TLB for permanently-valid translations and use those slots for the handler code itself. These wired translation will always hit in the TLB.
Advantages:
- Flexibility. It can implement the page table with whatever data structure without needing a hardware change.
- Simplicity: The hardware doesn't do much on a miss.

Aside: the valid bit on the TLB and the valid bit on a page table mean different things.

in a page table, if a page table entry (PTE) is marked as invalid, that means the page that has not been allocated by the process, and should not be accessed by a correctly working program. In this situation, it should trap to the OS and kill the process
in a TLB valid bit, it refers to whether the TLB entry has a valid translation. On boot up, every TLB entry should be invalid because no address translations have been cached. Valid entries are populated as misses occur.
TLB valid bit also can all be sit to invalid so that during a context switch, the system can ensure that about-to-be-run processes do not accidentally use a virtual-to-physical translation from a previous process.

TLB Contents

A TLB may have 32, 63, or 128 entries ("fully associative"). This means that any given translation can be anywhere in the TLB, and that the hardware will search the entire TLB in parallel to find the desired translation.

A TLB entry looks like

VPN | PFN | Other bits

Both VPN and PFN are present in each entry because the translation could be in any of of these locations, so the OS will search the entries in parallel to see if there is a match.
The "other bits" include the valid bit (does it have a valid translation), protection bits (determines how a page can be accessed like read/execute or read/write), address-space identifier, dirty bit.

Context Switches

TLBs contain virtual-to-physical translations that are only valid for the current running process, so the OS/hardware must be careful when switching from one process to another so that it does not use an translations from a previous process.

When P1 is running, assume that TLB might be caching translations for it. E.g., Page 10 == Physical frame 100. Then another process begins and decides that the Page 10 for this process == Physical frame 170. Now your table cannot distinguish which entry is ment for which process.

One approach is to flush the TLB on context switches, setting all the valid bits to 0 using a explicit and privileged hardware instruction.

Cost is that each time a process runs, there will be TLB misses if it touches its data and code pages.

Another approach is to add hardware support to share TLB across context switches.

Address space identifier (ASID) field is like a process identifier (PID) with fewer bits (8 opposed to 32).
Now, TLB can hold translations from different processes without confusion. But now the hardware must know which process is currently running when performing translations, which will be communicated via some privileged register.

Replacement policy:

Cache replacement: when we replace an old one, which to replace to minimize the miss rate.

Least-recently-used (LSR) is a common approach to take advantage of locality assuming that if an entry has not been recently used, it is good for eviction.

Random-policy evicts a mapping at random. It's simple and avoids corner-case behaviors.

One corner case is if there is a program that loops over n+1 pages with a TLB of size n. In this case, LRU misses upon every single access, whereas random does much better.

Real TLB Entry

Let's look at an example. MIPS R4000 is a modern system that uses software-managed TLBs.

It supports a 32-bit address space with 4KB pages.

It uses 19 bits for the VPN because the user addresses will only occupy half the address space and the rest is reserved for the kernel.
12-bits are used for the offset.
Supports translation up to a 24-bit physical frame number and hence supports systems up to 64 GB of physical main memory (2^24 4KB pages).
Has a global bit (G) which is used for pages that are globally-shared among processes (if set then ASID is ignored).
Has ASID (8-bits) to distinguish address space.
Has coherence (C) bits that determine how a page is cached by the hardware.
a dirty bit is marked when the page has been written to, a valid bit tells the hardware if there exists a valid translation present in this entry, and the page mask field supports multiple page sizes
Some of the pages bits are unused.

MIPS TLBs have 32 or 64 entries, most are for the users while some for the OS. A wired register can be set by the OS to tell the hardware how many slots of the TLB to reserve for it.

OS needs reserved mapping for code / data that it accesses in critical time where a TLB miss would be problematic (like in the TLB miss handler).

Because it is software managed, it needs privileged instructions to update the TLB:

TLBP: probes TLB to see if a particular translation is in there
TLBR: reads the content to TLB entry into register
TLBWI: replaces a specific TLB entry
TLBWR: replace a random TLB entry

Aside: random-access memory (RAM) implies you can access any part of the RAM as quickly as the other. However, keep in mind that if you access a particular page of memory that isn't mapped by your TLB, it will be costly. Called Culler's law.

Summary

Exceeding the TLB coverage is when the number of pages a program accesses in a short time exceeds the number of pages that can fit in the TLB, the program will generate a large number of misses.

One solution is to support larger page sizes.

TLB access can also be a bottleneck in the CPU pipeline, particularly during a physically-indexed cache. Address translation would need to take place before the cache is accessed, which can slow things down quite a bit. People have looked into all sorts of ways to access cache with virtual addresses, thus avoiding the expensive step of translation in the case of a cache hit.

Chapter 20: Paging: Smaller Tables

3/10/2025

Problem: page tables are too big and consume too much memory.

Linear page (array-based) tables. e.g., 32-bit address space with 4kb pages. each page-table entry is 4 bytes. The number of pages is: 2^32 addresses / 2^12 (4KB), making a page table 4MB. There is also one table per process.

Solution 1: Bigger pages

4x reduction in page table size if the page size 4x. Problem: big pages lead to waste within each page, called internal fragmentation. This means applications allocate pages but only use little bits of each. The memory will quickly fill up. This is why we see 4KB in x86 and 8KB in SPARCv9.

Solution 2: Paging and segment hybrid

Instead of having a single page table for the entire address space of the process, have one page table per logical segment. E.g., one page table for the code, heap, and stack.

Implementation in MMU:

base register told you each segment lived in physical memory. In this solution, it will hold the physical address of the page table.
limit or bound register that told us the size of the segment. In this solution, it will indicate how many pages it has.
switched out during context switch.

Has significant memory savings because you can be more precise in how many pages you allocate. Unallocated pages between stack and the heap no longer take up space in the page table.

Issue: segmentation assumes a certain usage pattern that when not followed, will still be useful. Can cause external fragmentation. The loss of memory is managed in page-sized units, and the page table can be of arbitrary sized (in multiples of PTEs). Finding free space can be difficult.

Solution 3: multi-level page tables

Recall the problem: how do we get rid of the invalid regions in a page table instead of keeping them in memory.

Multi-level page table: tree structure. (used in x86)

Idea: chop up the page table into page-sized units; then, if an entire page of page-table entries (PTEs) is invalid, don't allocate that page of the page table at all.

track whether a page of the page table is valid using a page directory, which is a new structure. This tells you where a page of the page table is and if that entire page of the page table contains no valid pages.
If the page directory marks 2/3 page tables at valid, only 2 pages of page table will reside.

The page directory contains one entry per page of the page table called page directory entries (PDE). It has a valid bit and a page frame number (PFN).

If a PDE is valid, it means that one of the pages of the page table that the entry points to via the PFN.
Each portion of the page table fits neatly within a page, it makes it easier to manage memory. It can grab the next free page when it needs to allocate or grow a page table. There is a level of indirection, which provides the benefit of allowing you to place page-tables whenever you would like in physical memory

Con of the multi-level table:

two loads of memory needed to get the right translation info: 1) page directory 2) PTE.
complexity. Whether its hardware or the OS handling the page-table lookup, doing so is more complex.

Aside: consider time-space trade-offs in the construction of a data structure.

usually, if you want to access a particular data structure faster, you have to pay a space-usage penalty
smaller table at a cost of more expensive TLB miss.

Example:

Let's start with assuming that the total address space: 16kb and each page will be 64-bytes (2^6).

This means we need 14 bits to represent the virtual address space

8 bit for VPN (256)
6 bit for offset (64)

Because 8 bit, the linear page table will have 256 (2^8) entries (PTEs).

Assume each PTE is 4 bytes in size. Thus 256 * 4 = 1 KB will be the size of the page table.

Recall that we want to make this two level. Therefore, this page table must be paged too.

recall that we have 64-byte pages. Therefore, the 1kb page table will be divided into 16 pages (of 64-byte pages).
Therefore, each page holds 16 pte (64 bytes / 4 bytes = 16).

Therefore, the page directory therefore needs one entry per page of the page table

16 can be represents with 4 bits of the VPN.
Thus use the top four pages of the vpn, which can be extracted as the page-directory index PDIndex. This is used to find the address of the page-directory entry (PDE) via PDEAddr = PageDirBase + (PDIndex * sizeof(PDE)).

Now say that we want to find 11 1111 1000 0000

We go to the page directory with the top 4 bits: 1111. (15th PT)
Next, check that it has valid bits, if so, then you need to fetch the address of the page table entry which will be the next 4 bits. 1110 of the page table or 14th PTE of the 15th PT. It tells us the PFN (Physical address of this).
Concatenate the PFN with the offset (000000) and you get the desired physical address.

Aside: wary of needless complexity

e.g., if disk space is abundant, don't design to use as little bytes as possible.
"premature-optimization"
perfection is attained when there is no longer anything to take away, not when there's nothing to add.

More than two levels

Sometimes deeper multi-level table is needed.

Recall goal: make each piece of the page table fit on a single page. However, sometime there are many levels needed to make them fit. e.g., if your page size is 512 bytes, and if each PTE size is 4 bytes, you can fit 128 PTEs on a single page. Therefore, you need 7 bits of VPN as an index into each Page table. The page directory is also limited to this 7 bit requirement.

translation process

Before any complicated multi-level page table access occurs, the hardware first checks the TLB; upon a hit, the physical address is formed without accessing hte page table at all. Only upon a TLB miss will the hardware do the full multi-level lookup.

The cost of traditional two-level page table: two additional memory accesses to look up a valid translation.

Inverted page tables

Extreme space saving.

Instead of having many page tables (one per process), we keep a single page table that has an entry for each physical page of the system. Each entry tell us the process that is using that page, and which virtual page of that process maps to this physical page.

Finding the correct entry is a matter of searching through this data structure.

linear scan is expensive, thus a hash table is built over the base structure.

Swapping the page table to disk

If the page table reside in kernel-owned physical memory, it is possible that it is still too big to fit into memory all at once. Thus, systems may place such page table in kernel virtual memory, thereby allowing the system to swap some of these page tables to disk when the memory pressure is tight.

Chapter 21: Beyond Physical Memory: Mechanisms

3/12/2025

So far, we've been assuming that every address space of every running process fits into memory. In reality, we need to support many concurrently-running large address spaces.

This requires another level in the memory hierarchy. However, to support large address spaces, the OS needs a place to stash away portions of address spaces that aren't in great demand somewhere that has more capacity than memory (and is typically slower): the hard disk drive. These slow hard drives are at the bottom.

Why do we want to support a single large address space for a process:

convenience + ease of use.
no need to worry if there is enough room in memory for your program's data structures. Just write programs naturally.
Illusion fro the OS makes your life simpler.
Contrast thought: memory overlays where programmers had to manually move pieces of code or data in and out of memory as they were needed.

The demand for swap space is because of the need for the OS to create an illusion of a large virtual memory for multiple concurrently running processes, it also supports multiprogramming. This is why almost all modern VM systems support this.

Swap Space

Swap space is the reserve space on the disk for moving pages back and forth.

we swap pages out of memory to it and swap pages into memory from it.

The OS must be able to

read/write to swap space in page-sized units.
remember the disk address of a given page.

The size of the swap space determines the maximum number of memory pages that can be in use by a system at a given time.

Swap space is not the only on-disk location for swapping traffic.

Assuming you run a program binary that is initially stored on disk. When the binary are found on disk, so when the program runs, they are loaded into memory, or loaded off when space is needed.

Present Bit

Upon a memory reference, the running process generates a virtual memory reference (for instruction fetches or data accesses). The hardware then translates them into physical addresses before fetching the desired data from memory (TLB hit/miss stuff).

If we wish to allow page to be swapped to disk, we need to support the case that when the hardware looks in the PTE, it may find that the page is not present in physical memory. To determine this information, each page-table entry needs a present bit. If 1, then it means the page is present in physical memory, otherwise it means that its on the disk.

Aside: terminology is weird. page fault could refer to any reference to a page table that generates a fault of some kind but sometimes we use it to refer to an illegal memory access. "page faulting" means that it is accessing parts of a virtual address space that the OS has swapped.

The act of accessing a page that is not in physical memory is referred to as a page fault.

Upon this, the OS invokes the page-fault handler.

The Page Fault

Recall there are two TLB systems: hardware managed TLBs and software-managed TLBs. If a page is not present, the OS is in charge to handle the page fault in software (almost always).

The OS needs to swap the page into memory from disk in order to service the page fault.

How does the OS know where to find the desired page? Page table is a natural place. They could use the bits in the PTE normally used for data such as the PFN of the page for the disk address. Using this, they can issue a request to disk to fetch the page into memory.
When the disk request is done, the OS then marks the page table to indicate it is present, update the PFN field, and then record the in-memory location of the newly fetched page, and then retry.
It should generate a TLB miss.
While the I/O is in flight, the process will be in the blocked state thus other ready processes while run.
Because I/O is expensive, this overlap of I/O (page fault) of one process and the execution of another is yet another way a multiprogrammed system can make the most effective use of its hardware.

Aside: why are page faults handled in software?

hardware designers hate relying on the OS to handle page fault. The reason then is because page faults to disk are slow and the hardware would need to understand swap space, how to issue i/o to disk, and a lot of details they don't have.
short answer: simplicity and performance.

What if memory is full

Memory could be full. In this case, the OS might want to page out one or more pages to make room. This process of picking the page to kick out, or replace is known as the page-replacement policy.

Policy needs to be carefully selected because disk operations are super slow.

Page Fault Control

Now, when a TLB miss occurs there are more things to check:

The page must be both present and valid. In this case, the TLB miss handler can grab the PFN from the PTE and retry the instruction.
If the page fault handler must be run if it is valid but not present
If the page is invalid, then the hardware traps the invalid access and terminates. The OS must find a

When replacements really occur

The OS proactively keeps the small portion of memory free (instead of waiting until it is full).

The OS has some kind of high watermark (HW) and low watermark (LW) that dictates when to start evicting pages from memory.

When there are fewer than LW pages available, then a background thread responsible for freeing memory begins to run. It evicts enough pages until there is HW pages available. This thread is named swap daemon or page daemon.

Systems will cluster or group a number of pages and write them out at once to the swap partition to increase the efficiency of the disk. This reduces seek and rotational overheads.

So instead of replacing directly when swapping, it would actually inform the background paging thread that free pages are needed.

Aside: working in background

work in background to increase efficiency and to allow for grouping of operations.
e.g., many systems buffer file writes in memory before writing to disk.
disk efficiency goes up, the disk can receive many writes at once and thus better be able to schedule them. Increase latency of writes and the application thinks writes are completed quickly. It also reduces work because some writes may never need to go to disk (e.g., if a file id deleted soon after). It is also a better use of idle time.

All these actions take place transparently to the process. From the POV of the process, it is just accessing its own private, contiguous virtual memory.

Chapter 22: Beyond Physical Memory: Policies

3/12/2025

Memory pressure (when little memory is free) could force the OS to start paging out pages to make room for actively-used pages. This is why the replacement policy (deciding which page to evict) is an important decision.

Cache management

The virtual memory pages in the main memory could be seen as part of a cache. Thus the goal in picking who to replace is to minimize cache misses or optimize cache hits. The number of cache miss and hits can be calculated into the average memory access time (AMAT).

$AMAT = T_M + (P_{miss} \cdot T_D)$

$T_M$ is the cost of accessing memory
$T_D$ is the cost of accessing disk
$P_{MISS}$ is the probability of not finding that data in the cache from 0.0-1.0.

Hit rate is the precent of references found in memory. Summed with miss rate = 1.0.

Optimal replacement policy

The optimal policy (called MIN) leads to the fewest number of misses.

Note: optimal is not practical

but it is helpful as a comparison point in simulation. Saying that an algo is 80% hit rate is more meaningful if you know optimal is 82%.

The policy: replace the page that will be accessed furthest in the future.

First accesses are typically misses, this scenario is often called cold-start miss (or compulsory miss).

Problem is, we don't hae infomration on the future.

Aside: types of cache isses:

compulsory / cold-start misses: first references often miss
capacity miss: cache ran out of space and had to evict an item to bring a new item to cache
conflict miss: limits on where an item can be placed in hardware cache due to set-associativity. (doesn't occur in OS page cache because such caches are always fully-associative meaning there are no restrictions on where in memory a page can be placed. )

FIFO polciy

FIFO first in first out. Problem: can't determine the importance of the blocks: even though page 0 is accessed many times, it is still kicked out.

Random

very luck deendent

LRU:

least recently used. a historically-based algorithm. Lean on past and use history as the guide.

frequency: if a a page has been accessed many times, it should not be replaced.
recency: the more recently a page has been accessed, it could be more likely to be accessed again.

principle of locality: is the family of policies that is an observation about program and their behaviors. It says:

programs tend to access certain code sequences (e.g., loop) or data structure (e.g., arrays accessed in a loop) frequently, so we should use history to figure out which pages are important.

LFU: least frequently used.

Workload

Workloads vs smaller traces are larger samples.

A no-locality workload demonstrated that

when there is no locality in the workload, all policies performed the same. The hit rate was determined just by the size of the cache.
when the cache is large enough to fit the entire workload, policy doesn't matter. 100% hit rate.

In 80-20 (80% of references made to the same 20% pages), then LRU does the best.

Looping sequence (0-50): random was best. Doesn't snag at corner cases

Implementing historical algorithms

Must track which pages have been least / most recently used. There must be some accounting work on every memory reference (affects performance).

Could use hardware support (like in the per-process page table a time field could be set to access time)? However, then scanning for that would take too long.

Approximating LRU

Approximating LRU is what modern systems do. Requires some hardware support in the form of a use bit (or reference bit).
one use bit per page of the system (lives somewhere in memory). Whenever a page is referenced (read/write) then the use bit is set to 1. The hardware doesn't clear this bit though the OS does.

Clock algorithm: all pages are of the system is arranged in a circular list. The clock hand points to some page, and if its 1, don't evict, but then set the bit to 0. Consider evicting if it is 0 (implying it has not been recently used).

scan resistance is an important part of many modern algorithms. They try to avoid worst-case behavior (such as with looping).

Considering dirty pages

One modification to clock algorithm: if a page has been modified, then it is dirty, meaning it needs to be written back to disk to evict it (expensive). If it is clean (not modified), then the eviction is free. The physical frame can just be reused for additional purposes without any additional I/O. Thus VM systems prefer to evict clean pages over dirty pages.

Neds hardware support for a modified/dirty bit. Set whenever the page is written. Thus, can be incorporated into a page-replacement algo.

the clock algo could scan for pages that both unused and clean to evict.

Other VM policies

OS also has to decide when to bring a page into memory. This is called page selection.

OS simply uses demand paging most of the time. Bring it on-demand / whenever it is accessed.

Alternatively, if they know ahead of time, they could prefetch. This should only be done if its going to be successful.

If code page P is brought into memory, you can safely assume P+1 will soon be accessed.

Clustering / grouping writes is also common.

Thrashing

What if memory is just oversubscribed. The memory demand >> available physical memory.

Results in constant paging, called thrashing.

A system could decide not to run a subset of processing with the hope it reduces the set of processes' working sets (pages they actively use) which means it will fit in memory. This approach is called admission control

better to do less work than do everything poorly.

out-of-memory killer is in Linux, and when the memory is oversubscribed, this daemon chooses a memory-intensive process and kills it. Could be troublesome if it kills something important.

Chapter 23: Complete Virtual Memory Systems

3/12/2025

VAX Virtual Memory

VAX/VMS OS was developed in 1970s and has interesting techniques for their virtual memory manager.

Memory Management Hardware

Hybrid of paging and segmentation.

Lower half of address space was the "process space" and was unique to each process.
- Lower half of the process space (P0) is where the user program is found and the heap that grows downwards.
- The second half of the process space (P1) has the stack that grows upwards.
The upper half of the address space is the system space (S) where only half is used.
- has the protected OS code and data.
- shared across the processes.

Goal 1: don't overwhelm memory with page tables.

VAX hardware pages were 512 bytes (super small). It made the linear page table super big.
Solution:
- Segment user address space into two, where each region (P0 and P1) would gets their own page table. Thus, no page-table space is needed for the ununused portion between the stack and the heap.
- User page tables (for P0 and P1, two per process) are in kernel virtual memory. Thus, when allocating / growing a table, the kernel allocates space out of its own virtual memory (in S). That way, if the memory is under pressure, the kernel can swap the pages of the page table out to disk.
  - Complex because to translate a virtual address in P0/P1, 1) consult system page table (in physical memory) to get the address of the page of the PT, 2) look up PTE for that page.

Aside: OS have the problem of the curse of the generality

tasked with general support
can't support everything well.

A Real Address Space

The address space we have assumed is for user code, user data, user heap, but its more complex than that.

Code segment never begins at page 0, since it is typically marked inaccessible in order to provide support for detecting null-pointer addresses.

aside: null pointers cause seg faults. When the hardware tries to look up the VPN 0 in the TLB, then there will be a TLB miss, and when the page table is consulted, it will find VPN 0 to be invalid, thus is an invalid access. the OS will then terminate the process.

The kernel virtual address space is part of each user address space.

during a context switch, the OS will change P0 and P1 registers to point to the appropriate page tables of the soon-to-be-run process. However, it does not change the S base and bound registers, and it results in the same kernel structures that are mapped into each user address space.
we use the same kernel for each address space because it makes life easier for the kernel. If the kernel were located entirely in physical memory, it would be hard to swap pages of the page table to disk / moving data between user application and the kernel would be complication. In this construction, the kernel appears almost as a library to its applications.

Page Replacement

the PTE contains

valid bit
protection field (4 bits)
modify / dirty bit
reserved for OS (5 bits)
physical frame number (PFN) to store the location of the page in physical memory.

There is no reference bit (determines if active).

You don't need a reference bit to figure out which pages are used in a system.
On VAX, you can use protection bits to emulate reference bits. First mark all pages as inaccessible, then when a process accesses a page and it works, revert it.

Developers were concerned about memory hogs (programs that use a lot of memory). E.g., LRU is a global policy that doesn't share memory fairly.

Solution: segmented FIFO replacement policy

each process has a maximum number of pages it can keep in memory (resident set size (RSS)). Each page is kept in a FIFO list, and when the process exceeds its RSS, the "first-in" page is evicted. FIFO clearly does not need any support from the hardware.
to improve performance: second-chance lists are where pages are placed before getting evicted. (specifically a clean-page free list or dirty-page list). So when a process P exceeds its RSS, it is put into clean list if not modified or the dirty-page list if modified. Then if another process Q needs a free page, it takes the first free page off the clean list. However, if the original process P faults on that page before it is reclaimed, P reclaims it from the list, thus avoiding a costly disk access. The bigger the global second-chance list, the closer it performs to LRU.
Another optimization is using clustering. Groups batches of page together from the global dirty list.

Other tricks.

Lazy optimizations in VMS.

demand zeroing: typically, when you find a page in physical memory to add as a page to your heap, you must zero it for security.

naively, doing it is costly particularly when the page does not get used by the process.
with demand zeroing, the OS simply puts an entry in the page table and then marks it as inaccessible. Only when accessed, it will trap, and during its handling, the OS could notice that its a demand-zero page, so then it will 1) find a physical page, 2) zero it 3) and maps it into the process's address space.

copy-on write (COW): when the OS needs to copy a page from one address to another, instead of copying it, it can map it into the target address space and mark it read-only in both address spaces. If one process does try to write, it will trap. The OS will notice that it is a COW page and thus lazily allocates a new page, fill it with the data, and then map this new page into the address space of the faulting process.The process continues with its own private copy.

Useful because any shared library should be copy only on write, thus saves a lot fo space.
In Unix, COW is more critical because of fork() (exact copy of hte address space, thus copy is slow and data intensive) and exec() (which overlays the calling process's address space with the soon-to-be exec'd program). There would be so much needless copying.

Linux Virtual Memory System

talk about x86.

Linux Address Space

Linux virtual address space consists of

a user portion (user program code, stack, heap, etc.) (the user portion of the currently-running address space changes) and
a kernel portion (kernel code, stacks, heap, and other parts) which is the same across processes.

In classic 32-bit Linux, the split is 3/4 is user.

Two types of kernel virtual address space in linux

kernel logical addresses: normal virtual address space.
- To get more memory of this type use kmalloc call in kernel code.
- Most kernel data structures reside here, like page tables, per-process kernel stacks, etc.
- cannot be swapped to disk.
- There is a direct mapping between kernel logical addresses and the first portion of physical memory (0xC0000000 and 0xC0000FFF translates to physical addresses 0xC0000000 and 0xC0000FFF respectively). This makes it easy to translate back and forth. As a result, these addresses are often treated as if they are physical.
- If a chunk of memory is contiguous in kernel logical address space, it is also contiguous in physical memory. This is suitable for operations that require contiguous physical memory to work correctly like I/O transfers to and from via direct memory access (DMA).
kernel virtual address:
- the kernel code calls a different allocator vmalloc which returns a pointer to a virtually contiguous region of the desired size. It is not contiguous in physical memory (not suitable for DMA). However, it is easier to allocate thus is used for large buffers.
- Necessary to enable kernel to address more than ~1 GB of memory.

Page Table Structure

In x86 there is a hardware managed, multi-level page table structure, with one page table per process.

The OS sets up mappings in memory, points a privileged register at the start of the page directory, and the hardware handles the rest. The OS is involved at process creation, deletion, and context switches (makes sure that the correct page is being used by the hardware MMU)

Current 64 bit systems use a four-level table. and only the bottom 48 bits are used.

because of 4KB page size, 12 botton 2 bits are used for the offset.
middle 36 bits take part in the translation. where P1 (upper most) is used for the topmost page directory and down to p4.

Large Page Support.

Allows greater than 4KB pages. up to 2MB ot 1GB pages (named "huge pages" in Linux)

reduces the number of mappings needed in page table. larger the pages -> fewer mappings.

When a process uses a large amount of memory, it quickly fills the TLB up with translations. If those translations are for 4KB, then it can be accessed without inducing TLB misses; however, for big workloads with many GB, they could spend 10% of the cycles servicing TLB misses.

Huge pages allow

the process to access a large tract of memory without TLB misses, thus using fewer slots in the TLB (huge advantage)
for shorter TLB-miss path: when TLB miss does occur, they are serviced more quickly
Allocation can be fast

Tip: incrementalism

incremental aproach is the right thing to do. First introduce specialize support- learn more about upsides and downsizes, and then if there is a real reason, then add generic support for all applications.
slow, thoughtful, and sensible progress

Implementation by linux: incrementalism

at first, you could explicitly request memory allocations with large pages with mmap() or shmget(). Most applications will be unaffected and continue to use 4KB.
later, they added transparent huge page support. The OS automatically looks for opportunities to allocate huge pages (2MB or 1GB) without requiring application modification.

Downsides / costs:

internal fragmentation: large page sparsely used. Wastful memory
Swapping doesn't work well because requires large I/O.
allocation overhead is bad

As memory demands increase, the 4KB page size is not enough.

Page Cache

To reduce the cost of accessing persistent storage, systems use caching subsystems to keep popular data items in memory.

In linux, the page cache is unified. Pages in memory are kept form three sources:

memory-mapped files: file data / metadata from devices (accessed by read() or write() calls to the file system)
anonymous memory: heap and stack pages that comprise each process (no file underneath it but rather swap space).
- kept in page cache hash table. tracks if they are clean or dirty/modified. Dirty data is periodically (time period or # of pages dirty) written to the backing store (either a specific file for file data or to swap space for anonymous regions) by background threads (pdflush).

When system is low on memory, Linux uses a modified form of 2Q replacement:

addresses the LRU problem of accessing a large file (> size of memory) because it will kick every other file out and sometimes the new info doesn't need to be retained.
Linux's version of 2Q keeps two lists, and divides memory between them. When accessed for the first time, a page is placed on one queue A1 / inactive list. When re-referenced, it's placed on Aq / active list. When replacement takes place, the candidate is taken from the inactive list. Periodically, pages are moved from the bottom of the active list to the inactive list.
This handles the cyclic large-file access problem

Approximation of LRU is used (similar to clock replacement).

Aside: ubiquity of memory mapping:

when mmap() is called on an open file descriptor, a process is returned is returned to a pointer to the beginning of a region of virtual memory where the contents of the file seem to be located. Using that pointer, a process can access any part of the file with a dereferenced.
When accessing a part of a memory-mapped file that has not been brought into memory triggers page faults, which the OS will page in that relevant data (demand paging).
Every regular Linux process uses memory mapped files, even if the code in main() doesn't call mmap() directly.
pmap command line tool shows the different mapping comprise the virtual address space of the running program. See the virtual address space of the mapping, size, protection bits, and source.

Security and buffer overflows

Glaring difference between new / old VM systems is the emphasis on security.

buffer overflow attacks: lets the attacker inject arbitrary data into the target's address space.

happens when you trustingly copy input into a buffer, but if its too long it'll overflow thus overwriting memory of the target.

Effects are Bad Things

run arbitrary computations, rent out cycles
access more resources via privilege escalation (user code gaining kernel access writes).

Ways to defend:

prevent exec of any code found within certain regions of the address space. The NX big (no execute) prevents execution from any page which has this bit set in its page table entry. Prevents code injected by an attacker into the target's stack from being executed.

Even when injected code cannot be added explicitly, arbitrary code sequences can be executed. One idea is return-oriented programming (ROP):

there are lots of bits of code (gadgets) within a program's address space, especially C programs that link with voluminous C library. Thus, an attacker can overwrite the stack such that the return address in the currently executing function points to a desired malicious instruction (or series of instructions), followed by a return. By stringing a large number of gadgets (ensuring each return jumps to the next gadget), the attacker can execute arbitrary code.
To defend, Linux uses address space layout randomization (ASLR). Instead of placing code, stack, or heap at fixed locations within the virtual address space, the OS will randomize its placement, thus making it challenging to craft code sequences. Most attacks will be able to cause crashes, but not gain control of the running program.
Also exists i kernel as Kernel address space layout randomization (KASLR)

Meltdown and Spectre are famous attacks

speculative execution: CPU guesses which instruction will be executed in the future and thus executes them ahead of time. It leaves traces of its execution in various parts of the system (processor caches, branch predictors, etc.). Attacks showed that the content of memory is vulnerable.

One way to increase kernel protection is to remove as much of the kernel address space from each use r process nad have a separate kernel page table. This concept is called kernel page-table isolation (KPTI).

no longer maps kernel's code and DS in each process.
thus when switching into kernel, a switch to the kernel page table is needed.
costly but increases security.

Chapter 26: Concurrency: An Introduction

2/3/2025 Chapter 26

Classically, there is a single point of execution within a program (i.e., a single PC where instructions are being fetched and executed from). In a multi-threaded program, tehre is more than one (i.e., multiple PCs). It's like a separate process, except that they share the same address space and access same data.

Each thread has its own PC and private set of registers for computation.

Thus, if there are two threads on one CPU, then a context switch must take place. With processes, the state is saved onto a process control block (PCB), but with thread we use thread control blocks (TCB) to store its state. Note: the address space is the same (i.e., we don't switch the page table we are using).

Address space difference:

in a single-threaded processes, there is a single stack residing at the bottom of the address space.
in multi-threaded processes, the stack segment is divided up so that there may be two stacks spread throughout the address spae of the process. Any stack-allocated variables, parameters, and return values will be placed in the thread-local storage, i.e., the stack of the relevant thread.
One issue is that you may run out of room, but stacks do nog generally have to be very large unless they use heavy recursion.

Why use threads?

parallelism. if you have multiple processors, you can't take advantage of it if there's only one processor. The act of transforming a single-threaded program to a program that does work on multiple CPU is called parallelization. It uses a thread per CPU to do work, which makes it faster on modern hardware
the other reason is to avoid blocking program process due to a slow I/O. While one thread is waiting for an explicit I/;O to complete or a page fault to finish, you can switch threads so that it utilizes the CPU. Threading enables overlap of I/O with other activities within a single program, just like how multiprogramming did for processes across programs.
Many modern server-based applications (web servers, dbms) use threads for these reasons
You could use multiple processes to do this, but threads share the address space so it's lighter. However, use processes when you need to logically separate tasks that don't share a lot of data structures in memory .

Example:

this main program has two threads, which both run mythread(), which prints an argument. One thread is given A and the other is given B.
the thread may immediately start running or be in the "ready" state.
after creating the two threads in the main program, the main thread calls pthread_join() which waits for a particular thread to complete. It does this for thread A and B.
In this situation three threads were employed: main, A and B.
Many varieties in the order of execution.

Shared Data

Say we have two thread that each add a 1e7 to a shared variable. The results will vary every time. Why is that?

It's because to add one to a counter variable, the code sequence in assembly is:

mov 0x8049a1c, %eax
add $0x1, %eax
mov %eax, 0x8049a1c

where 0x8049a1c is the address of the variable
it stores the memory value into %eax and then adds one and then stores the context back into memory at the same address.

A timer interrupt could go off when it hasn't completed the full sequence, as a result two threads may store the same result because it was holding onto the old value.

This is called a race condition or data race. The results depend on the timing of the code execution. When the result is different every time we call it indeterminate.

When a code can result in a race condition, we call it a critical section, which is a piece of code that accesses a shared variable / resource. This section cannot be executed by more than one thread.

Mutual exclusion is a property that guarantees that if one thread is executing within the critical section, the others will be prevented from doing so. This avoids races and will result in deterministic program outputs.

A series of atomic actions means all or nothing (i.e., as a unit). Either all the actions in this group has occurred or none. There is no in between state. The grouping of actions is called a transaction. Synchronization primitives turn short sequence of instructions into atomic blocks. File systems also use techniques like journaling or copy-on-write to atomically transition their on-disk state.

The hardware has a few instructions called the synchronization primitives.

Another problem of concurrency is that sometimes one thread must wait for another to complete some action before it continues. E.g., a disk I/O needs to be complete before another action.

Aside:

A disassembler can be run on an executable and it shows you what assembly instructions make up the program.

Chapter 27: Interlude: Thread API

2/3/2025 Chapter 27

Thread Creation

In POSIX, thread creation is:

#include <pthread.h>
int
pthread_create(pthread_t *thread,
	const pthread_attr_t *attr,
	void *(*start_routine)(void*),
	void *arg);

thread: pointer to the structure of type pthread_t. Use this structure to interact with the thread.
attr: any attributes this thread might have, like stack size or information about the scheduling priority
- pthread_attr_init() is used to initialize the attribute
- In most cases, defaults are fine, or you can pass NULL
start_routien, or the third argument is: what function should this thread start running in. This is called the function pointer.
- void pointers allows you to pass in any type of argument and let it return any type. In the function, you can simply cast the argument or unpack the argument to any type.
- This argument type can change. E.g., if the start function required an integer argument, the declaration would be void *(*start_routine)(int)
arg is the argument that is passed to the function where the thread begins execution.
- If passing a single value, doesn't have to be packed up as an argument and return values inside of structures

Once you create the thread, it is another live executing entity, complete with its own call stack, running within the same address space as all the current existing threads.

#include <stdio.h>
#include <pthread.h>

typedef struct {
	int a;
	int b;
} myarg_t;

void *mythread(void *arg) {
	myarg_t *args = (myarg_t *) arg;
	printf("%d %d\n", args->a, args->b);
	return NULL;
}

int main(int argc, char *argv[]) {
	pthread_t p;
	myarg_t args = { 10, 20 };
	int rc = pthread_create(&p, NULL, mythread, &args);
	...
}

Thread completion

pthread_join() waits for completion.

int pthread_join(pthread_t thread, void **value_ptr);

pthread_t specifies which thread to wait for. The thread should have been created with the thread creation routine (passed its pointer to pthread_create())
value_ptr is a pointer to the return value that you expect to get back.
- Because the routine can return anything, it's defined to return a pointer to void. This is because pthread_join() routine changes the value of the passed in argument, so you need to pass in a pointer to that value, not just the value itself.
- Pass NULL when we don't care about the return value
- Be careful about how values are returned form a thread. Never return a pointer which refers to something allocated on the thread's call stac.
  - This is because the stack of the thread will be automatically deallocated when it returns. Thus, passing back a pointer to a now-deallocated variable will lead to bad results.

A procedure call is a call to pthread_create() followed by a pthread_join().

normally you will be creating more than one thread and waiting for it all to complete.

Not all code that is multi-threaded uses this join routine.

You could have a bunch of worker threads and use the main thread to accept request and pass them to workers, indefinitely. They are long lived and don't need to join.
However, a parallel program that creates threads to execute a particular task in parallel is likely to use join to make sure all the work completes before exiting or moving onto the next stage of computation.

Locks

Locks protect critical sections by ensuring only one thread can enter this section. All locks must be properly initialized in order to guarantee that they have the correct values.

Static way: pthread_mutex_t lock = PTHREAD_MUTEX_INITIALIZER;

Dynamic:

int rc = pthread_mutex_init(&lock, NULL);
asser (rc == 0); // always check success

dynamic way is preferred
the argument is the address to the lock
second argument is the optional set of attributes. NULL uses defaults.
these routines can fail so check error codes. The above is the simple version

wrappper:

// Keeps code clean; only use if exit() OK upon failure

void Pthread_mutex_lock(pthread_mutex_t *mutex) {
	int rc = pthread_mutex_lock(mutex);
	assert(rc == 0);
}

In non-toy programs, you should check for failure and do something appropriate when the call doesn't succeed since you cannot exit. thread_mutex_destroy() should be used when done with the lock.

Two calls of lock acquisition. Generally avoid them, though there are useful cases:

trylock returns failure if the lock is already held.
timedlock returns after a timeout or after acquiring the lock, whichever happens first.

Condition Variables

Condition variables are useful to signal that something must take place between threads. If one thread is waiting to do something before it can continue.

int pthread_cond_wait(pthread_cond_t *cond,
					  pthread_mutex_t *mutex);
int pthread_cond_signal(pthread_cond_t *cond);

a lock is associated with this condition.

pthread_cond_wait() puts the calling thread to sleep, and waits for some other thread to signal it. Example code:

pthread_mutex_t lock = PTHREAD_MUTEX_INITIALIZER;
pthread_cond_t cond = PTHREAD_COND_INITIALIZER;

Pthread_mutex_lock(&lock);
while (ready == 0)
	Pthread_cond_wait(&cond, &lock);
Pthread_mutex_unlock(&lock);

if ready is not true, then it calls the wait routine to sleep
the reason that pthread_cond_wait uses a lock is because that once the thread is put to sleep, the lock is released. Then, before it is woken up, it re-acquires the lock.
we use a while loop to check for ready rather than an if because there is a case that the waiting thread is woken up.

The code that wakes it would look like this

Pthread_mutex_lock(&lock);
ready = 1;
Pthread_cond_signal(&cond);
Pthread_mutex_unlock(&lock);

The alternative is to spin and check the condition, but this is bad because it is wasteful and error prone.

man -k pthread for more informatio

Chapter 28: Locks

2/10/2025 Chapter 28|

Recall that locks are used to execute a series of instructions atomically.

Introduction

To use lock, you just add some code around a critical section

lock_t mutex; // globally allocated lock
...
lock(&mutex);
balance = balance + 1;
unlock(&mutex);

A lock is just a variable that needs to be declared and it holds the state of the lock at any instant.

A lock can be available (or unlocked or free) or acquired (or locked or held). The thread that holds a lock is called the owner of the lock.

A lock could also store what thread holds the lock or the queue for ordering lock acquisition (hidden from user).

lock() semantics:

calling lock() attempts to acquire a lock
- if no other threads hold the lock, then it will acquire it and enter the critical section.
- if another thread holds the lock, it will not return, which means it is prevented from entering the critical section.

unlock() semantics:

when the owner of the lock calls unlcok(), the lock is free again.
- If there are waiting threads, one of them will notice the change in the lock state and acquire the lock
- If there are no waiting threads, then the lock state will be changed to free.

Pthread locks

POSIX library calls the lock a mutex since it provides mutual exclusion between threads.

pthread_mutex_t lock = PTRHEAD_MUTEX_INITIALIZER;
Pthread_mutex_lock(&lock);
bal = bal + 1;
Pthread_mutex_unlock(&lock);

Concurrency can be increased by using different locks to protect different variables (fine-graned locking strategy) instead of using one big lock that is used any time the critical section is accessed (which is called a coarse-grained locking strategy**).

Evaluating locks

Goals of the lock

provide mutual exclusion
fairness: does each thread contending for the lock get a fair shot at acquiring it once its free
- does any thread contending for the lock starve, or never obtains it
performance: time overhead added by using the lock.
how does it perform when there are multiple CPUs involved.

Implementation method 1: Controlling interrupts

Disable interrupt for critical section. This was made for single-processor system.

Ensures the code inside the critical section will not be interrupted so that it will execute as if it was atomic.

Positives:

simple.

Negatives:

requires the calling thread to perform a privileged operation and you have to trust that it will not abuse this facility.
- A greedy program could monopolize the processor or it can go into endless loop. Then, the OS never regains control of the system and you must restart it.
- Simply requires too much trust in programs.
Does not work on multiprocessors.
Interrupts can become lost if interrupts are turned off for extended periods of time.
- E.g., the CPU misses the fact that the disk device has finished reading a request.

When it is used:

OS will use to guarantee atomicity when accessing its own data structure. Or, to prevent messy interrupt handling situations from arising.
- Trust issue disappears inside the OS because it can always trust itself to perform privileged operations.

Implementation method 2: using loads / stores

BAD!

Use a flag variable to indicate whether some thread has possession of a lock.

When lock() is called by the first thread, it tests whether flag is equal to 1 (which it is not). Then it sets the flag to 1 so that the thread now holds the lock.
When unlock() is called the flag is cleared.
If another thread calls lock() it will spin-wait in a while loop for that thread to call unlock(), which then it will set the flag to 1.

Problems:

No mutual exclusion. We could be in a state where both threads set the flag to 1.
Performance: spin-waiting wastes time for the thread waiting to release the lock. The waste is super high on a uniprocessor to the point that the thread with the lock can't even run (until context switch occurs).

Implementation method 3: spin locks and test-and-set

Correctness achieved.

Requires hardware support for locking, which is present in all systems these days.

Test-and-set (or atomic exchange) instruction.

int TestAndSet(int *old_ptr, int new) {
	int old = *old_ptr; // fetch old value at old_ptr
	*old_ptr = new; // store ’new’ into old_ptr
	return old; // return the old value
}

It returns the old value at old_ptr and simultaneously updates said value to new. These are performed atomically. This ensures only one thread acquires the lock.

Lock implementation:

typedef struct __lock_t {
	int flag;
} lock_t;
 
void init(lock_t *lock) {
	// 0: lock is available, 1: lock is held
	lock->flag = 0;
}

void lock(lock_t *lock) {
	while (TestAndSet(&lock->flag, 1) == 1)
		; // spin-wait (do nothing)
}

void unlock(lock_t *lock) {
	alock->flag = 0;
}

If someone has already held the lock, then it will return 1, then the thread will spin and spin until the lock is released and TestAndSet returns 0.

For this lock to work, you need a preemptive scheduler (timer interrupt). This is necessary because a spinning thread will never relinquish it.

Not fair because a thread may spin forever.

Bad performance on single processors because the thread holding the lock will run for the duration of its time slice, wasting the CPU cycle.

works good on multiprocessors assuming the number of threads roughly equals the number of CPUs. Not that many cycles wasted.

Implementation method 4: Compare and Swap

Compare-and-swap or compare-and-exchange (x86 name) tests whether the value at the address specified by ptr is equal with expected

If so, update the memory location pointed by ptr with the new value
Otherwise, do nothing.

Similar to test-and-set:

void lock(lock_t *lock) {
	while (CompareAndSwap(&lock->flag, 0, 1) == 1)
		; //spin
}

checks if flag is 0, if so, then it swaps to 1 atomically.

This is more powerful (when it comes to lock-free synchronization).

Implementation method 5: load-linked and store-conditional

Load-linked and store-conditionalinstructions can be used to build concurrent structures.

load link fetches a value from memory and places it in a register.
store-conditional only succeeds (updates) if no intervening store to the address has taken place. In case of success, the store conditional returns 1 and updates the value at ptr to value; if it fails the ptr is not updated and 0 is returned

int LoadLinked(int *ptr) {
	return *ptr;
}

int StoreConditional(int *ptr, int value) {
	if (no update to *ptr since LL to this addr) {
		*ptr = value;
		return 1; // success!
	} else {
		return 0; // failed to update
	}
}

lock() executes the load-linked (returns 0 if lock is not held) and then attempts to store-conditional. Even if two thread execute the load-linked, only one thread will successfully store-conditional.

void lock(lock_t *lock) {
	while (LoadLinked(&lock->flag) ||
		!StoreConditional(&lock->flag, 1))
	; // spin
}

Implementation method 6: fetch and add

Increments a value while returning the old value at a particular address.

int FetchAndAdd(int *ptr) {
	int old = *ptr;
	*ptr = old + 1;
	return old;
}

Aside:

Lauer's Law: little concise code is always preferred because it's easier to read and fewer bugs.

The ticket lock uses a ticket and turn variable in combination.

When a thread wishes to acquire a lock, it fetch-and-adds on the ticket value. That value is considered the thread's myturn. The globally shared lock->turn is used to determine which thread's turn it is. When myturn==turn, then the thread can enter the critical section.
To unlock, you increment the turn so that the next waiting thread can enter.

This solution ensures progress for all threads because once a thread is assigned a ticket value, then it will be scheduled some point in the future (once those in front of it have passed through the critical section). Recall that in the previous attempts, no guarantee existed because other threads could always starve one.

Avoiding spin locks

Implementations 1-6 are hardware-based. They are easy to implement but are inefficient because the spinning is a waste of a CPU time slice. The problem gets worse when N threads are contending for a lock.

Aside: you also want to avoid spin locks because of the problem known as priority inversion. Say T2 is priority High, T1 is priority low. T1 holds a lock T2 is waiting for. T2 will always be scheduled since it has higher priority, thus it spins forever.

solution can be to avoid spin locks
or generally, the higher priority thread temporarily can boost the lower priority thread in a technique known as priority inheritance.

OS implementation2 1: yielding

OS support method 1 is to yield, or give up the CPU to another thread. m

void lock() {
	while (TestAndSet(&flag, 1) == 1) 
		yield(); // give up the CPU
}

It moves the caller of yield() from running to ready state. The yielding thread essentially deschedules itself. The issue is that if there are many threads contending for a lock. You may not necessarily yield to the right thread, so you do a lot of context switching.

This approach also does not address starvation. You could be caught in an endless yield loop.

OS implementation 2: queues

The previous method leave it up to chance what thread runs next (in Solaris).

Use a queue to track which threads are waiting to acquire the lock. Now, you can put a thread to sleep (park()), and wake it up when that lock is free (unpark())

because the queue dictates who gets the lock next, it avoids starvation.

Use a guard (which is a spin-lock) around flag and queue manipulation.

When a thread can't get a lock, it will be placed in a queue, then it is parked.

Risk of wakeup/waiting race: thread is about to park, but a the lock was just released. This means if it parks, it will be indefinite because no one will wake it up.

OS Implementation: 3: futex

Linux provides futex that offers more in-kernel functionalities.

A futex has an associated physical memory location.
Callers use futex to sleep / wake

futex_wait(address, expectation) puts the caller to sleep assuming the value at the address address is equal to expectation (otherwise, return)

futex_wake(address) wakes a thread waiting on the queue.

lowlevellock.h of the nptl (gnu libc) library uses a single integer to track whether the lock is held using the highest pit of the integer and the number of waiters on the lock using the rest of the bits.

if the lock is negative, it is held
when there is no contention for hte lock, very little work is done - using the atomic bit test-and-set to lock and atomic add to release the lock.

Two-Phase Lock

Two-phase lock realizes that spinnign can be useful if the lock is about to be released.

lock spins for a while, but if it is not acquired, then it enters a sleep phase.

The linux lock spins once before using futex to sleep.

This is an example of an hybrid approach, where you combine both ideas to yield a better one.

Chapter 29: Lock-based Concurrent Data Structures

2/10/2025 Chapter 29 Locks in data structures make the structure thread safe. How do we add locks so that the data structure is still high performance and many threads can access a structure at once, i.e., concurrently.

Concurrent Counters

Trivial data structure that requires little code to implement.

It is a single lock, which is acquired when calling a routine that manipulates the data structure, and is released when returning from the call.

To test performance, run a benchmark in which each thread updates a single shared counter a fixed number of times.
Problem with this method is that it scales poorly. Single thread can complete a million counter updates in 0.03s but having two threads update the counter is 5s.

Ideally, threads should complete quickly on multiple processor as a single thread does on one. Achieving this is called perfect scaling. Even though more work may be done, it is done in parallel.

How do we make it more scalable? The approximate counter: represents a single logical counter via numerous local physical counters, one per CPU core, and a single global counter. There is a lock for each local counter and one for the global lock.

When a thread running on a given core wants to increment the counter, it increments its local counter.
- because threads across CPU can update local counter without contention, the counter is scalable
Global counter is kept up to date by transferring the local values periodically. This is done by acquiring the global lock and incrementing it by the local counter's value, which is then reset to zero.
- How often this occurs is determined by S. The smaller it is, the more the counter behaves like the non scalable counter. The bigger it is, the more further off the global value might be.
- You could simply acquire all local locks and the global lock to get an exact value, but that is not scalable.

Concurrent Linked List

An issue arises if malloc() fails. The code must release the lock before failing the insert. How can we rewrite the insert and lookup routines to remain correct under concurrent but avoid the case where the failure path requires us to add the call to unlock.

We can rearrange so that the lock and release only surrounds the critical section in the insert code and that the common exit path is used in the lookup code.

This means that malloc() is outside the lock code.

Next, say there is a lookup routing (iterate through every value of the list) instead of unlocking and return the value when found, break out of the loop and have a single path of return.

reduces the number of lock release point adn thus decreases the chance of accidentally introducing bugs.

How do we make it more scalable? Because this technique does not scale well. Hand-over-hand locking or lock coupling. Instead of having a single lock for the entire list, have one per node. When traversing the list, the code grabs the next node's lock and releases the current.

However, the overhead of acquiring and releasing the locks is prohibitive. It is unlikely to be faster than grabbing a singe lock. Maybe some hybrid is good?

Tip: be wary of control flow changes that lead to function returns, exits, or error conditions that can halt the execution of a function.

If a function begins by acquiring a lock and is doing some stateful operation, the code has to undo all of the state before returning, which is error prone.

Concurrent Queues

You could always just add a big lock.

The Michael and Scott design uses two locks: one for the head and one for the tail. This makes it possible to enable concurrency of dequeue and enqueue operations.

Concurrent Hash Table

Built using concurrent lists.

good performance becuase it has a lock per hash bucket.

Tip: avoid premature optimization. No value in making something faster if doing so will not improve the overall performance of the application

Chapter 30: Condition Variables

Chapter 30 2/12/2025

Cases when a thread wishes to check a condition is true before execution

e.g., parent waiting for child thread to finish before joining.
You could spin, but it wastes CPU time and can be incorrect.
We want a way to make the parent sleep until the condition we are waiting for comes true.

Definition and routines

Condition variable is a explicit queue that threads can put themselves on when some state of execution (i.e., some condition) is not as desired (i.e., waiting on the condition). When some other thread changes the sate, it can wake one or more of those waiting threads and allows them to continue (signaling the condition).

To declare a condition variable, write something like pthread_cond_t c; and initialize it. There are two operations

wait() which is the POSIX call pthread_cond_wait(pthread_cond_t *c, pthread_mutex_t *m);
- needs a mutex because it assumes the mutex is locked when wait() is called, so it will release the lock to put it to sleep (atomically). When the thread wakes up, the lock is re-acquired before returning. This is done to prevent race conditions when the thread is trying to put itself to sleep.
signal() which is pthread_cond_signal(pthread_cond_t *c);

Tip: hold the lock while signaling when using condition variables. Hold the lock when calling wait because it is needed by the semantics of wait.

wait always assumes the lock is held when you call it
releases the lock when putting caller to sleep
re-acquires the lock before returning.

Producer Consumer (Bounded Buffer) Problem

There are one or more producers (generate data items and place them in buffers) and one or more consumers (grabs items from buffer and consumes).

e.g., in a multi-threaded web server, a producer puts HTTP requests into a work queue (i.e., bounded buffer) and the consumer threads take requests out of this queue and processes them.
e.g. piping output of one program into another. e.g., grep foo file.txt | wc -l.
- grep writes the lines from file.txt to the standard output, but the Unix shell will redirect the output to the Unix pipe (created by the pipe system call). Then the other end of the pipe is connected to the standard input of the process wc. grep is the producer and wc is the consumer. Between them is the in-kernel bounded buffer.

The bounded buffer is a shared resource, so synchronized access is required.

Only put data into the buffer when count is zero, and only read data from the buffer when the count is one.

Single buffer solution

Things to make sure:

only one consumer thread will attempt to grab from buffer
when consumer is done, it wakes up the right thread

Use two condition variables to properly signal which type of thread should wake up when the state of the system changes.

producer waits on condition empty and signals fill. Conversely, consumer waits on fill and signal empty. This way, a consumer always wakes the right one.

Tip: when checking conditions in multi-threaded programs, using a while loop rather than if is always correct. This is to handle the case of spurious wake ups. It's possible that two threads get woken up though just a single signal has taken place.

To enable more concurrency and efficiency, you can have more buffer slots so that multiple values can be produced before sleeping, and multiple values can be consumed before sleeping. This reduces context switches and allows concurrent producing / consuming to take place.

Change the conditions that producers and consumers check whether to sleep or not.
A producer should only sleep if all buffers are currently filled up. A consumer sleeps if all buffers are empty.

Covering conditions

New example of how condition variables can be used.

Problem: when a thread calls into the memory allocation code, they may have to wait in order for more memory to become free. When a thread frees memory, it needs to signal that memory is now free. Which waiting thread should be woken up first?

The waiting threads may request different amounts of memory

A solution by Lampson and Redell: pthread_cond_broadcast()to wake up all waiting threads, so that you guarantee that any thread that should be woken up are. This can negatively impact performance.

Threads will wake up, re-check the condition and then go back to sleep if the condition is not satisfied still.
This condition is called a covering condition and it covers all the cases where a thread needs to wake up.
If you find that your program only works if you need to broadcast (when you don't think it has to), then you likely have a bug.

Chapter 31: Semaphores

Chapter 31

Semaphores was made as a single primitive for all things related to synchronization. You can use semaphores as locks and condition variables.

It is an object with an integer value that you can manipulate with two routines.

sem_wait() or P(). Will decrement the value of semaphore by 1. It will either
- return right away (because the value of the semaphore is one or higher)
- Or the caller will suspend execution waiting for a subsequent post. With multiple calling threads, they must be queued.
sem_post() or V(): Increments the value of the semaphore by one and then, if there is a thread waiting to be woken, wakes one of them up.

When the value of the semaphore is negative, it is equal to the number of waiting threads.

typically unknown to the users

Initialized

#include <semaphore.h>
sem_t s;
sem_init(s, 0, 1);

declare semaphore s and initialize to value 1 (via the third argument)
the 0 means that the semaphore is shared between threads in the same process.
- this can be used to synchronize access across different processes.

Binary Semaphores (locks)

Using a semaphore as a lock. Initialize the semaphore to be 1. This means that one is available to be grabbed

Only has two states (held and not held).

Semaphores for Ordering

Useful for ordering events in a concurrent program.

E.g., a thread waiting for a list to be non empty so that it can delete an element from it.

One thread is waiting
One thread needs to make something happen and then signal it has happened, so that it can wake the waiting thread.
Thus, semaphore is used as an ordering primitive similar to the use of condition variables.

How do we use a semaphore to: a thread creates another thread, and waits for it to complete its execution.

the parent calls sem_wait() and the child calls sem_post().
The initial value would be zero.
- This is because the parent may call sem_wait() before the child called sem_post() and we would want it to be wait. The parent would decrement the semaphore to -1 which makes it wait.
- Alternatively, the child runs before the parent calls sem_wait(). Then the value would be 1 first, and when the parent runs, it will immediately work and decrement it back to 0.

Generally: the rule for setting the value of semaphore:

consider the number of resources to give away immediately after initialization.

Producer / consumer (bounded buffer) problem.

Attempt 1:

Have two semaphores:
- empty: indicates buffer entry is empty
- full: indicates buffer is filled.
A producer waits for buffer to be empty to put data in it
Consumer waits for buffer to be filled before using it.

Problem! This works if the buffer capacity is 1. However, if the capacity was 10, then we have a race condition

If two producers were put into the buffer at the same time, PA inserts an item but before it increments the counter (using sem_post(), it gets interrupted by PB and puts data into the 0th element.

Attempt 2: The filling of a buffer + incrementing the index is a critical section that should be guarded. Add a binary semaphore / lock.

Problem! if you put the lock around the entire section (full/empty semaphores + buffer + increment), you'll get a deadlock.

PC acquires lock and calls sem_wait to wait for the buffer to be filled.
The producer makes data but can't acquire the lock to add to the buffer, and it ends up waiting for the lock.
Now both the consumer and producer is waiting- a class deadlock

Attempt 3: Reduce the scope of the lock. Mutex acquire an release should only be around the critical section (put which inserts and increments fill (which says what index of buffer). The full / empty wait and signal code is always left outside the lock.

Reader writer lock

E.g., concurrent list operations like inserts and lookups. Only one insertion can happen at once. On the other hand, lookups simply read the data structure, so as long as we can guarantee that no insert is on-going, many lookups can occur concurrently.

This operation is called the reader-writer lock

We need two synchronization operations that use the writelock semaphore to ensure only one writer can acquire the lock:

rwlock_acquire_writelock()
rwlock_release_writelock()

Then, we need readers variable that tracks how many readers there are. Additionally, the reader should also acquire the read and write lock.

Once a reader has acquired a read lock, other readers can also acquire the read lock. However, if a writer wants to acquire the write lock, then it has to wait until all readers are finished. The last reader to exit should sempost() on the writelock when it done so that the writer can acquire it.

Note, it adds overhead.

Aside: The simple and dumb approach can be the best. Sometimes a simpel spin lock works best. Hill's law: big and dumb is better

Dining Philosopher

The dining philosopher problem: there are 5 philosophers sitting around the table.

Between each pair of philosopher is a single fork (thus 5 total)
philosopher could be thinking (no forks needed) or eating (needs 2 forks left and right).

The key challenge: write get_forks() and put_forks() such that there is no deadlock. No starvation and there is high concurrency (as many philosopher can eat at the same time).

Helper function. Get forks. Philosopher p's left fork is left(p)

int left(int p) { return p; }
int right(int p) { return (p + 1) % 5; }

And one semaphore per fork all initialized to 1.

sem_t forks[5]

Deadlock arises here:

void get_forks(int p) {
	sem_wait(&forks[left(p)]);
	sem_wait(&forks[right(p)]);
}

void put_forks(int p) {
	sem_post(&forks[left(p)]);
	sem_post(&forks[right(p)]);
}

If everyone grabs their left right fork, then everyone is stuck waiting for a fork that another philosopher possesses.

Change dependency:

void get_forks(int p) {
	if (p == 4) {
		sem_wait(&forks[left(p)]);
		sem_wait(&forks[right(p)]);
	} else {
		sem_wait(&forks[right(p)]);
		sem_wait(&forks[left(p)]);
	}
}

void put_forks(int p) {
	sem_post(&forks[left(p)]);
	sem_post(&forks[right(p)]);
}

Thread throttling

Use semaphore to limit how many threads can be running. This is called throttling and a form of admission control

Consider hundresds of threads are created where each acquire a large amount of memory, called the memory-intensive region. If all threads enter memory region at the same time such that the requests exceed physical amount of memory, the machine starts thrashing (swap page back and forth and the entire computation will slow down).

A semaphore can be initialized to the value of the number of threads you wish to enter the memory intensive region at once. Then put a sem_wait() / sem_post() around the region.

Implementing semaphores

Let's implement Zemaphores with locks and condition variables. The difference compared to Dijkstra's semaphore: the value will never be lower than zero (similar to linux).

typedef struct __Zem_t {
	int value;
	pthread_cond_t cond;
	pthread_mutex_t lock;
} Zem_t;

  

// only one thread can call this
void Zem_init(Zem_t *s, int value) {
	s->value = value;
	Cond_init(&s->cond);
	Mutex_init(&s->lock);
}

void Zem_wait(Zem_t *s) {
	Mutex_lock(&s->lock);
	while (s->value <= 0)
		Cond_wait(&s->cond, &s->lock);
	s->value--;
	Mutex_unlock(&s->lock);
}

void Zem_post(Zem_t *s) {
	Mutex_lock(&s->lock);
	s->value++;
	Cond_signal(&s->cond);
	Mutex_unlock(&s->lock);
}

Tip: Generalizations are generally wrong.

Tip: Allen Downey's book on concurrency

Chapter 32: Common Concurrency Problems

31/105 bugs were deadlock bugs, the others were not

Non-Deadlock bugs

Two major of this category is atomicity violation and order violation.

Atomicity - Violation Bugs

Example: one thread is in the middle of a critical section and its not locked.

Atomicity violation: desired serializability among multiple memory accesses is violated (i.e., atomic code region is not enforced during execution).

Code region would be called atomicity assumption. When the assumption is incorrect the code will not work as desired.

The solution: add locks around the shared-variable references, ensuring that when either thread accesses that data structure, the lock is held.

Order-violation bugs

Order violation: the desired order between two (groups of) memory accesses is flipped.

I.e., A should always be executed before B, but the order is not enforced
Example: access a thread before it has been initialized.

Solution is to enforce ordering. Using condition variables is an easy and robust way to add this style of synchronization into modern code bases.

Add condition variable and corresponding lock. Now, when the initialization code runs, it will set the state of the condition variable and signals to the other thread its done.

Deadlock bugs

Classic problem. -e.g., Thread T1 holds lock L1 and is waiting for L2, but T2 that holds L2 is waiting for L1 to be released.

A presence of a cycle in the graph is indicative of a deadlock.

Deadlocks occur because

complex dependencies exist between components.. Thus locking strategies in large systems must be done carefully to avoid deadlock in the case of circular dependencies
encapsulation: hide details of implementations and thus make software easier to build in a modular way. Modularity does not mesh well with locking. Seemingly innocuous interfaces invite you to deadlock because you don't know you may have two threads calling that same interface.

Conditions for deadlock to occur. They al must be met.

mutual exclusion: threads claim exclusive control of resources they require (e.g., thread grabs lock)
hold-and-wait: threads hold resources allocated to them (e.g., locks that they have already acquired) while waiting for additional resources (e.g., locks that they wish to acquire)
no preemption: resources cannot be forcibly removed from thread that are holding them
circular wait: a circular chain of threads such that each thread holds one or more resources (e.g., locks) that are being requested by the next thread in the chain.

How to prevent circular wait:

total ordering should be provided for lock acquisition.
- e. g., if there are only two locks L1 and L2, always acquire L1 before L2. This strict ordering ensures no cyclical wait arises.
If total lock ordering is difficult to achieve (or unnecessary), partial ordering structure can be used to avoid deadlock.
- e.g., memory mapping code in Linux v5.2
Ordering is just a convention, and you can always sloppily ignore the protocol and cause a deadlock. Locking requires deep understanding of the code base.

tip: enforce lock order by lock address

if a function must grab 2+ locks, the order cannot necessarily be guaranteed. E.g., do_something(mutex_t *m1, mutex_t *m2) can be called with do_something(L1, L2) and do_something(L2, L1) .
So, you can use address of each lock as a way of ordering lock acquisition. High-to-low order or low-to-high order.

if (m1 > m2) { 
	// grab in high-to-low address order
	pthread_mutex_lock(m1);
	pthread_mutex_lock(m2);
} else {
	pthread_mutex_lock(m2);
	pthread_mutex_lock(m1);
}
// Code assumes that m1 != m2 (not the same lock)

How to prevent hold-and-wait Acquire all the locks at once, atomically.

pthread_mutex_lock(prevention); // begin acquisition
pthread_mutex_lock(L1);
pthread_mutex_lock(L2);
// ...
pthread_mutex_unlock(prevention); // end

grabbing prevention ensures no untimely thread shift can occur in the middle of lock acquisition.
this also means that any time any thread grabs a lock, it must first acquire the global prevention lock.
If another thread was trying to grab L1 and L2, in a different order, it would also be okay.

Note that this solution is problematic for the following reasons:

when calling a routine, this approach requires us to know exactly which locks must be held so that we can acquire them ahead of time. Means that this technique will decrease concurrency because they must all be acquired early.

How to prevent no preemption Generally, we view that locks should be held until unlock is called. Multiple lock acquisition is troublesome because we wait for another lock as we hold another.

So some libraries provide interfaces to avoid this. E.g., pthread_mutex_trylock() grabs the lock (if available) and returns success or error code to indicate that it the lock is already held. That way, you cant ry again later.

top:
	pthread_mutex_lock(L1);
	if (pthread_mutex_trylock(L2) != 0) {
		pthread_mutex_unlock(L1);
		goto top;
}

a thread could grab lock in any order and it would be deadlock free

This causes the livelock problem. It is likely two threads could be repeatedly attempting this sequence and repeatedly failing to acquire both locks. Then it runs through this sequence many times while progress is not being made.

a solution is adding a delay before looping back, thus decreasing the odds.

This solution avoids the hard parts of using the trylock approach

encapsulation: if these locks are buried in some routine, then the jump back to beginning may be too hard to implement.
if the code has acquired some of these resources along the way, it may also be hard to release them carefully. E.g., after L1 acquisition, the code may have allocated some memory so that means it would have to release that memory upon failure to acquire L2 before jumping up to try again.

This solution also doesn't really add preemption (forcible action of taking a lock away from a thread that owns it) but rather it allows the developer to back out of the lock ownership (preempt their own ownership) in a graceful way.

How to avoid mutual exclusion

Prevent the need for mutual exclusion completely. Difficult because code does have critical sections.

Lock-free and wait-free approaches: use powerful hardware instructions so that you can build data structures in a manner that does not require explicit locking.

Example: say we have this compare-and-swam instruction provided by the hardware that does the following:

int CompareAndSwap(int *address, int expected, int new) {
	if (*address == expected) {
		*address = new;
		return 1; // success
	}
	return 0; // failure
}

If we wanted to atomically increment a value by a certain amount, we could use:

void AtomicIncrement (int *value, int amount) {
	do {
		int old = *value;
	} while (CompareAndSwap (value, old, old + amount) == 0)
}

repeatedly tries to update the value old to the new value.
it will fail if another thread has successfully updated old already.

Deadlock avoidance via scheduling In some scenarios, deadlock avoidance is preferred. Avoidance requires some global knowledge of which locks various threads might grab during their execution. Then, it schedules the thread in a way to avoid deadlocks.

If you know T1 and T2 both need L1 and L2, then you know that they cannot be scheduled at the same time. You can schedule the threads that only need 1 or 0 of those locks.
The cost is typically performance.
Only useful in limited environments, typically embedded systems where you have full knowledge of the entire set of tasks that must be run.
Limits concurrency.
Not a common, general-purpose solution.

Tip: Tom West's Law says that not everything is worth doing well. Good engineering maxim. If a bad thing happens rarely, don't put too much effort in preventing it, especially if the cost of that bad thing happening is small (otherwise too expensive to mess up).

Detect and recover: allow deadlocks to occur, but take action once it has been detected.

If OS froze once a year, just reboot it. Non-solution can be a solution.
Database systems often have deadlock detection and recovery technique.
Deadlock detector runs periodically, building a resource graph and checking it for cycles. In event of a cycle (deadlock), the system is restarted. An intricate repair of data structure is required and a human may be involved.

Chapter 36: I/O Devices

3/26/2025

Input/output (I/O) device needs input so that it change results and output which is its entire purpose.

System architecture

The classical diagram of a typical system:

has memory bus / interconnect which the CPU, and memory are connected to.
devices are connected to system via general I/O bus, which in modern systems is the PCI. Graphics and other higher-performance I/O devices found here.
peripheral bus like SCSI, SATA, USB connect slow devices to the system like disks, mice, and keyboards.

The faster the bus is, the shorter it must be. Thus, limited space for high-performance memory us. More expensive.

In modern day:

CPU directly connected to graphics via PCIe and also directly connected to Memory,
The CPU and I/O chip is connected to Intel's proprietary DMI (direct media interface).
Hard drives could connect via eSATA interface.
Other high performance system connected via PCIe (Peripheral component interconnect express) like network interface and high performance storage devices like NVMe.

Canonical Device

Devices have two important components:

Hardware must present an interface that allows the system software to control its operation.
Internal structure of the device is implementation specific and is responsible for implementing the abstraction the device presents to the system. For example, simple devices have one or few hardware chips to implement their functionality.
- Could be a device-specific chip. E.g., RAID controllers may have a hundreds of thousands of lines of firmware (software within a hardware device)

Canonical Protocol

Simplified device interface has three registers:

status register: can be read to see current status of device
command register: to tell the device to perform a certain task
data register, to pass data to the device

Typical interaction the OS might have:

While (STATUS == BUSY); // wait until device is not busy
Write data to DATA register
Write command to COMMAND register
	(starts the device and executes the command)
While (STATUS == BUSY); // wait until device is done with your request

When the device is not ready, we poll the device, but this is inefficient.

Lower cpu overhead with interrupts

The solution is to use the interrupt. When the device is done, it will raise a hardware interrupt, which causes the CPU to jump into the OS at an interrupt service routine (ISR), or the interrupt handler. This is a piece of OS code that will finish the request.

allows for overlap of computation and I/O
not always the best solution: if the device is quick, then an interrupt slows down the system because of switching the process.
- Therefore only good for slow devices.

If the speed of the device is unknown, use a hybrid that polls for a little while. If the dvice is not finished, then use an interrupt. Two-phased approach achieves the best of both world.s

Another reason against instrrupts is networks. When a huge stream of incomming packets generate an interrupt, it is possible for the OS to livelock: find itself only processing interrupts and never allowing the user-level process to run and service thos requests.

eg., web server expereinces load burst because it becomes top-ranked entry, then it is better to use polling to allow the web server to service some requests before checking for packet arrival.

coalescing: a device that interrupts waits a bit, and then other requests can complete during the wait. Multiple interrupts are coalesced into a single delivery, thus lowering overhead of interrupt processing.

tradeoff: waiting too long increases the latency of a request.

DMA data movement

More efficient.

When the programmed I/O (PIO) transfers a large chunk of data to a device, the CPU is burdened. The CPU must copy the data from memory to the device one word of a time. Thus other processes can't run.

Direct Memory Access (DMA) is a solution. It's a specific device that orchestrates transferes between the device and mainmemory.

to transfer data between devices and main memory without CPU intervention, the OS would program the DMA engine to tell it what device to send to, where the data is in memory, and how much data to copy. That's it ! The OS can proceed with other work
When DMA is complete, the DMA controller will raise an interrupt, thus OS knows its transfer is complete.

Device interaction methods

How does the OS actually communicate?

One method is have explicit IO Instructions: specify a way for the OS to send data to specific device registers, so then you can build the protocols.

e.g., in and out instructions can be used to communicate with devices. To send data to a device, the caller specifies a register with the data and a specific port which names the device. Then you execute that instruction
These instructions are privileged. OS controls device thus the only entity allowed to directly communicate with them.

Second method is Memory mapped I/O. The hardware makes device registers available as if they were memory locations.

to access register, the OS issues a load (to read) or store (to write) the address. the hardware then routes the load/store to the device instead of main memory.
nice because no new instructions are needed to support it.

There is no great advantage to one or the other.

The Device Driver

How to fit devices with specific interfaces into the OS (general thing).

Solution: abstraction. At the lowest level, a piece of software in OS must know how a device works, via the device driver.

e.g., the file system has no idea the specifics of which disk class it is using. It simply issues block read and write requests to the generic block layer, which then routes them to the appropriate device driver.
needed for any device you plug in
70% of OS code is in device drivers.

Alternative to the file system is the raw interface fir devices, which enables special apps like the file-system checker or disk defragmentation tool to directly read and write blocks without using the file abstraction. These interfaces support low-level storage management apps.

Simple IDE Disk Driver

Interface to the system, has four registers. Available by reading or writing to specific I/O addresses (like 0x3F6) using the in and out I/O instructions.

control
command block (0x1F2-0x1F6)
status
error

The protocol found in the xv6 IDE driver:

wait for drive to be ready. status register should be READY
write parameters to command. Write sector count, logical block address, and drive number, to command registers
start the I/O by writing READ or WRITE to command register
Data transfer: wiat for drive status
handle interrupts
error handling.

Uses the four function to make this protocol

ide_rw() queues a request or issues to disk via ide_start_request
in either case, the routine waits for the request to complete and the calling process is put to sleep
ide_start_request sends reqeuest to the disk using the in and out x86 indstructions
ide_wait_ready() makes sure the driver is ready
ide_intr() is invoked when interrupt takes place. it reads data from the device, wake the process, and launces the next I/O via ide_start_request() (if there are more requests in queue)

Chapter 37: Hard Disk Drives

3/26/2025

The hard drive is the main form of persistent data storage for decades.

The interface

Drive consists of many large number sectors 512-bytes which can be read/written numbered 0 to n-1 where n is the number of sectors. Also called the address space of the drive.

512-bytes are written atomically. Thus if a power loss occurs, only a portion of the larger write may complete (when this happens its called a torn write).

"unwritten contract" of disk drives:

when accessing two blocks near one-another within the drive's address space, it will be faster.
accessing blocks in a contiguous chunk is the fastest access mode compared to random access pattern

Geometry

Platter: hard circular surface which dat is stored persistently by inducing a magnetic charge.

could have 1+ platter
each platter has 2 sides, called surface
made from hard material like alumnimum and coated with thin magnetic layer that enables the drive to persist bits even when off
Bound together with a spindle, which connects to a motor that spins it around at a fixed rate measured in rotations per minute (RPM) (7200-15000).
The time of a single rotation: 6ms for 10k RPM
data written to concentric circles of the sector, each called a track.
a single surface may contain many thousands of tracks tightly packed together width of hair.

To write / write from surface, need a mechanism that allows us to sense (read) the magnetic pattern or induce a change (write) to them.

disk head does the writing. One head per surface of the drive. Attached to disk arm which moves across the surface to position on the desired track.

Disk Drive

Assume we have disk with single track. A track has 12 sectors, 512 bytes in side addressed 0-11. A single platter rotates around the spindle.

Rotational delay

How a request would be processed?

Wait for the desired sector to rotate under disk head. This wait is called the rotational delay. If the full rotation delay is R, then the disk has to incur a rotational delay about R/2 to wait for 0 to come under the head (if we start at 6.) The worse case would be a full rotational delay.

Seek time

If the disk has multiple tracks, then the arm has to move to the correct track, in a processed known as seek. Seeks are one of the most costly disk operations.

First an acceleration phase gets the arm moving
then coasting is when the arm is moving at full speed
deceleration is when arm slows down
settling is positioning: can take .5 - 2 ms because it has to find the write track.

The is still rotating, so u must wait for the rotational delay too.

transferis when data is written or read.

Other details

track skew is employed by drives to make sure that sequential reads can properly be serviced even when crossing track boundaries.

takes in account the seek time so that when the head moves to hte next track, it would be ready to read.

Reality: outer tracks have more sectors so as a result of geometry, there is more room. These tracks are called multi-zoned disk drive because the disk is organized into multiple zones, where the zone is consecutive set of tracks on a surface.

each zone has the same number of sectors per track, and outer zones have more sectors than inner zones.

cache or track buffer is a small amt of memory which the drive can use to hold data read from or written to the disk.

the drive may decide to read in all the sectors on that track and cache them in memory

Writes: write back caching is when it acknolwedges that the data has been put in its disk (also called immediate reporting)

appears "fasteR" but dangerous if the data has to bbe written in a certain order

write through: is actually written to disk.

I/O Time

$T_{I/O}= T_{seek} + T_{rotation} + T_{transfer}$

T_I/O is the common figure to do comparison with.

Divide the size of the transfer by the time it took to get the R_I/O

Testing

random workload: small reads to random locations on the disk
sequential workload: reads a large number of sectors consecutive without jumping around.

Types:

high performance drive: spin as fast as possible, low seek time, transfer data quickly
capacity drive: cost per byte is more imporant. slower but pack more bits as possible.

Tip: transfer data sequentially.

Disk scheduling

Because of high cost I/O, the OS has played a role in deciding order of I/O issued. Given a set of I/O requests, the disk scheduler examines them and decides which one to schedule next.

Unlike job scheduling, the length of each job is unknown we can only guess. Greedily pick the one that will take the least time to service first. SJF

Shortest seek time first

early approach: SSTF orders the queue of requests by track and chooses the nearest track to complete first. Works well in certain but drive geomtry is not availble to the host OS. OS can impelment nearest block first (NBF) which schedules to the nearest block address next

The second problem is starvation: imagine in our exmaple if there was asteady strma of requests to the inner track. Then any requests to the other tracks wil b eignored.

SCANmoves back and forth across the disk servicing requests in order across the tracks. It sweeps in a single pass. Thus, if a request comes for a block on a track that has already been serviced on this sweep, it will not be handled immediately.

f-scan freezes the queue when doing its sweep so that it avoids starvation

c-scan (circular): sweeps in both direction fair to inner and outer tracks.

elevator: it goes all the way up and all the way down to prevent starvation.

SCan is not good because they don't adhere to SFJ.

Shortest positioning time first: SPTF

or shortest access time first.

seek and rotation are roughly equivalent so SPTF is useful. It is difficult to perform in the OS so its done in the drive.

Where is the disk scheduling performed on modern systems?disks can acomodate multiple outstanding requests and have complicated schedulers themselves. The OS therefore picks picks the best few requests and issues them to the disk, then it is up to the disk scheduler to service requests in SPTF order.

I/O merging: series of requests means it should merge the seperate request into one bigger request. Done at the OS level to reduce number of requests sent.

work-conserving: carry out the request immediately. However, should the system wait before issuing requests? The disks will never be idle if there are requests to serve. However, anticipatory disk scheduling has shown it is ebtter to wait (non-work-conserving approach). If a new better requests arrive, the efficiency increase. Issue is deciding how long to wait.

Chapter 39: Interlude: Files and Directories

3/24/2025

Virtualization of persistent storage. Take extra care. How do we manage persistent data so that it is performant and reliable.

Files nad directory

Abstractions:

file: linear array of bytes that you can write and read
- low-level name for each file, a number. Referred to as the inode number (i-number).
- OS does not know much about the structure (pic vs text) of the file.
directory: like a file but its content is a list of user-readable, low-level name pairs (('foo', 10))
- each entry in a directory refers to file and other directories
- has low level name (inode)
- can build a directory tree (dir in dir) or directory hierarchy

The responsibility of the file system is to store data persistently on disk and make sure that when you request for it again it is what you put.

A directory hierarchy starts at the root directory (in unix that's /).

separator is used to name the sub-directories. E.g., if directory foo is in /, then a file nmaed bar.txt is in foo then its absolute pathname is /foo/bar.txt.
.txt is just a convention toindicate the type

Tip: name carefully

everything
file system empowers us to name things so taht you can access things

Creating Files

To create a file use open() and the O_CREAT flag into the function

It returns a file descriptor: integer, private per process.

used in unix
use this file descriptor to read / write file.
a capability i.e., opaque handle that gives you the power to perform certain operations.
think of it like a pointer to an object of type file. Once you have this you call call methods on it.
fds are managed per-process in a proc structure.
a simple array indexed by fd would track the files that are opened. each element in refers to an entry in the system-wide open file table, which tracks the underlying file the descriptor refers to, current offset, and other relevant details such is readable or writeable.

tip: strace provides a way to see what programs are up to.

see arguments and return code

reading and writing files

how does cat program access all these ifles.

strace on linux, dtruss on mac, or trusson other unix variants: they trace every system call made by a program while it runs and dumps them on the screen.

Steps

open the file for reading (indicated by O_RDONLY flag when we call open()) this returns 3. this is because each running process already has 3 files open: stdin, stdout, sterr. These are file descriptors 0, 1, and 2..
use read() to read some bytes.
then you write to the standard output
tries to read again, but since it is zero, it knows it is done.
then the program calls close().

Reading and writing non-sequentially.

All access has been sequential: read / write a file from beginning to the end.

Sometimes, it is useful to read / write to a specific offset.

We use lseek():

off_t lseek(int fildes, off_t offset, int whence);

the third argument, whence determines how to seek.

For each file a process opens, the OS will track the "current" offset. This determines where the next read or write will begin reading from or writing to within the file.

when you read, it implicitly updates the offset
but with lseek, you explicitly update theoffset.

This offset is kept in the struct file referenced form struct proc.

Note: different from a disk seek, which occurs when the write or read is issued!

Together, these file structures represent all the currently opened file in the table, referred to collectively as the open file table.

Shared file table entries `fork()` and `dup()`

In many cases, the mapping of file descriptor to an entry in the open file is a one to one mapping. For example, when a process runs, it might decide to open a file, read and close it. This file will have a unique entry in the open file table.

However, sometimes, processes read the file at the same time, and each process will have its own entry in the open file table. Even if this is the case, each reading/writing of the file is independent. Each has its own offset.

However, an entry in the open file table can be shared. This occurs when the parent process uses fork().

When the file table entry is shared, its reference count is incremented, only when both processes close the file will the entry be removed. Sharing can be useful, for example when working together on a task to write to the same output file without any extra coordination.

dup() allows a process to create a new fd that refers to the same underlying open file as an existing descriptor. It's useful for writing to a unix shell and performing operations like output redirection.

Writing immediately with `fsync()`

when a program calls write() it says write at some point in the future. It will likely buffer for some time. Later, the writes will be issued to the storage device.

However, in DBMS applications, it may need the ability to force writes to disk. the interface for this in unix is fsync (int fd).

forces all dirty data to disk, for the file referred to by the specified fd.

fsync() is called after write() once it returns. then the application can have confidence that it has persisted.

you also need to fsync() the directory that contains the file. This ensures that if the file is newly created that it is part of the directory.

Renaming files

Once we have a a file sometimes you need to rename it. this is done with mv.

implemented as an atomic call with respect to system crashes.

How it works:

write new version of file under new name
force it to disk with fsync()
when certain, then it renames the temporary file to the original file's name. The last step atomically swaps the new file in place while concurrently deleting the old version of the file.

Getting information about files

Expect the file system to keep a fair amount of information about each file it is storing. This is called metadata. Use stat() or fstat().

All its information is stored in something called an inode. Often mentioned when we talk about file systems. Think about it like a persistent data structure kept by the file system. All inodes reside on disk. The active ones are cached

Removing files

rm It uses unlink(). It returns 0 upon success.

Making directories

You can't write to a directory. Since its responsible for the integrity of directory data, you can't edit it directly.

When a directory is created it is considered "empty".

it has one entry that refers to itself, called "."
an entry for its parent ".."
You can see via ls -a

Reading directories

Instead of opening directory like a file, use opendir() readdir() or closedir().

dir entry as struct dirent

directories are light on information.

Deleting directories

rmdir() has the requirement that the directory is empty.

Hard links

Remove file via unlink() because the way to make an entry in the file system tree is through link(). It takes old pathname and new pathname.

when you link, it creates another way to refer to the file.
creates another name in the directory you are creating the link to. It refers to the same inode number as the original file.
the file is not copied, you just have two human-readible name.

when you create a file you

create a structure (inode)
and linking a human readable name

After you create a hard link to a file, the file system perceives no difference bewteen original file name and the newly created file name. They are both just links to the underlying metadata about the file, which is found in the inode number.

Thus to remove, use unlink() because it checks a reference count within the inode number. The reference count (or link count) (can be found with stat()) allows the file system to track how many different file names have been linked to this particular inode. When the reference count is zero, then the file system will free the inode and related data blcok, thus deleting the file.

Symbolic links

There is one other type of link that is really useful. This is called symbolic link, or soft link.

Hardlink is somewhat limited because you can't create one to a directory for fear you create a cycle
you can't hardlink to other disk partitions (inode numbers are only unique within one filesystem)

To create, do ln -s.

looks the same, but the original file can be accessed through file as well as file2.

a symbolic link is a file itself, of a different type.

4 bytes but if the pathname is longer, the link file would also be bigger
holds onto the pathname of the linked-to file and the data of the link file.

Leaves a dangling reference.

unlike hard links, removing the original file named file causes the link to point to a pathname that no longer exists.

Permission bits and access control lists

Two central virtualizations

cpu
memory

They give the illusion that it has its own CPU and private memory.

File system presents a virutal view of the disk: transforms them into raw blocks The files are commonly shared among different users and processes. they are not always private.

permission bits in unix.

-rw-r--r-- they determine who can access it and how

Permission groupings:

what owner of the file can do
what the group of the file can do
what "anyone" (or others) can do

The owner of the file can readily change these permissions, via the chmod command ( to change file mode). To remove the ability for anyone except the owner to access the file you can type: chmod 600 foo.txt. It enables the readable bit (4) and writable bit (2) for the owner. the others to 0.

AFS, a distributed file system, allows access control list (acl) per directory. Specifies who can and cannot read a set of files. fs listacl.

aside: superuser (root) can access all files regardless of privileges.

Making and mounting a file system

To make a file system, you can use mkfs. Give a device (like a disk partition) and a file system type and it writes an empty file system starting with a root directory.

Once created, it needs to be made accessible within the uniform file-system tree. This is done via the mount program. It takes an existing directory as a target mount point and pastes a new file system onto the directory tree at that point.

Imagine there is an unmounted file system. we can put it at some random mount point. Instead of having a number of separate file system, mount unifies all file systems into one tree. making them uniform and conveniet.

Tip: TOCTTOU

Time of check to time of use (TOCTTOU) problem: time interval between validity check and the operation connected. The validity-check variables could be changed during this time interval resulting in an invalid operation being performed.
one approach is to reduce the number of services that need root privilege to run. transactional file system could also solve this problem (but they don't really exist

Chapter 40: File System Implementation

4/2/2025

There is a simple file system implementation: known as vsfs (very simple file system) that is pure software (no hardware features).

also exists AFS and ZFS, which have different data structures and do things better/worse

The way to think

data structures: what on-disk structure to organize data and metadata

access methods: how does it map the calls made by a process like open onto its structures.

which structures are read during execution
which are written
how efficient would these steps be?

Overall organization

On-disk organization of the vsfs file system: disk is divided into blocks.

simple file systems use one block size (let's choose 4KB).
Each block are 4KB and they are addressed 0 to N-1.

The region of the disk used for user data is called the data region. Reserve a fixed portion for this. like 54 out of 64.

Other info is metadata, which tracks things like which data blocks comprise a file, size of file. etc. FOR each file.

this is called inode. need to reserve space for inode table. the other 5 out of 64 will be used for this.
- not that big.

another component is how we track whether inodes or data blocks are free or allocated . These allocation structures.

one way is free list. implement with bitmap. Need one for data region (data bitmap) and one for inode table (inode bitmap). simple structure: each bit is used to indicate whether the corresponding object/ block is free (0) or in use (1).

The last space is reserved for superblock. This contains infomration about this particular file system, like how many inodes and data blocks are in the file system. It also has magic number to identify the file system.

When mounting, this gets read first to intialize the parameters, and then attach. When files within the volume are accessed, the system knows where to look for the needed on-disk structures

Inode

inode is short for index node.

originally arranged in an array which is indexed into when accessing a particular inode.
tracks metadata like type, size, number of blocks allocated to it, permission, location of constituent blocks, protection information, who owns the file, who can access it, time information (created / modified / access), where data block resides on disk (e.g., pointers)
referred to by i-number.
- In vsfs, given i-number, you can directly calculate where on the disk the node is located.
how it refers to where its datablocks are: direct pointers is one approach but the problem is if the file is really big, more than how many pointers to block it can store...

The multi-level index.

To support bigger files, use indirect pointer. Instead of pointing to block that contains user data, it points to a block that contains more pointers, each which points to user data.

12 fixed direct pointer, and single indirect pointer. if big enough, then you will need an indirect block allocated (from data-blockr egion of disk).

Another approach: extents instead of pointers. A disk pointer plus a length (in blocks). 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

less metadata
works well if lots of free space and laid out contiguously

double indirect pointer refers to a block that contains pointer to indirect blocks, which each contains pointers to data blocks. Can support files over 4GB size. THen you want triple indirect pointer. Ultimately:multi-level index approach. (most common).

Truths:

most files are small. optimize for this case. 12 is typical
average file size is growing
most bytes are stored in large files
file system contains lots of files
file systems are roughly half full
directories are typically small.

Directory organizations

simple organization: list of (entry name, inode number) pairs.

for each file/dir in a dir, there is a string and a number in the data block(s) of the dir.
record length is the total bytes for the name plus left over space.
for each string there could also be a length. (assuming variable sized names)

Deleting a file can leave empty space in middle of the dir, so you should bea ble to mark that (like with reserved inode number 0).

delete is one reason the record length is used. a new entry may reuse an old, bigger entry and thus have extra space within.

Aside: linked list: insdie an inode, instead of having multiple pointers, you could point to first block of file, and tehy can point to the next. Poor performance because reading the last block of a file is random access.

to improve, the you could keep an in-memory table of link innfo instead of storing in data blocks. This is file allocation table or the FAT file system.
there are no inodes, rather directory entries that store metadata about a file and refer directly to their first block. hard links iimpossible.

Directories are treated as a special type of file. Thus, it has an inode marked as directory. It has data blocks pointed to by the inode and they live in the data block region.

Therefore, on-disk structure remains unchanged

In a simple linear list of directory entries, it is not the only way to store such information.

any DS is possible.

Free space managemnet

File system must track which inodes and datablocks are free. When we create file, we have to allocate an inode for that file. Thus, the fs will search through for free, allocate it to the file, and the fs needs to mark the inode as used, eventually update on-disk bitmap with correct info. Same thing happens when datablock is allocated.

pre-allocation is used to guarantee contiguous block for the file.

Reading a file from disk

access path

you want to open a file and close it.

when you issue the command with a filepath, the file system needs to be able to find that inode for the file you specified.

The file system needs to traverse the pathname and locate it.

It always begins in the root directory /. Ths fs will read from the disk the inode of the root directory, which will have a well known i-number. The fs must know what it is when the file system is mounted. The root inode in unix is commonly 2. It starts there.

once the inode of the root is read, it can look inside and find the pointers to its data blocks, which contains the contents of the root directory.
They read through directory, looking for desired directory.
It will recursivelye traverse path name until desired inode is fond.
perform permissions check, allocate file descriptor and returns.

To read;

consult onode to find the location of its block. and update access time.
update the in-memory open file table for this file descriptor, updating the file offset such that the next read will read the second file block.

To close:

no disk i/o take place.

Writing file to disk

same thing happens. unlike reading, writing may allocate a block (unless overwritten). When writing:

each write not only has to write data to disk but decide which block to allocate to thte file and thus update the other structures (data bitmap and inode). Thus, each write to a file generates 5 I/O:
- data bitmap (which newly-allocated block was used)
- 2 to read and write the inode (update with new block's location)
- write to the actual block itself.

If a file needs to be created:

allocate inode
allocate space within directory containing the new file
i/o traffic:
- inode bitmap (allocate)
- write to new inode (initailize)
- data of directory (link the high-level name of the file to its inode number)
- one read and write to directory inode to update
- if directory needs to grow, then additional i/o needed

Tip: alloocation structures are only accessed when you need to allocate a block.

Caching and buffering:

reading and writing files can be expensive, incurring many I/Os to the slow disk. how to combat?

use DRAM (system memory) to cache important block.

Imagine how many file opens. With a long pathname, hundreds of reads would have to be done to open a file.

early file systems had a fixed-size cache to hold popular blocks.

LRU and different variants decide which blocks to keep in cache.
10% of memory size. static.
- wasteful.
- new: dynamic partitioning. virtual memory page and file system pages into a unified page cache. Memory can be allocated flexibly across virutal memory and the file system.

With caching, subsequent file opens of that same file will hit cache.

reads will be effortless
however with write, it may need to be in order.
generally write buffering (delay) can batch updates. E.g., if created and updated, then it saves I/O. second benefit: schedule subsequent I/O and increase performance. Some writes can be avoided if deleted. 5-30 seconds. problem if system crashes. (if important then use fsync() or use direct i/o or use raw disk interface and avoid the file system)

Chapter 41: Locality and The Fast File System

original file system (old):

super block (S) has information about the file system
- how big the volume is, how many inodes, pointer to the head of the free list of blocks, etc.
Inodes region contains all the inodes for the file system.
Data: datablocks

Super simple, but it wasn't optimal.

Problem 1: Poor Performance.

This file system treated the disk like it was RAM, the data is spread all over the place without regard to the fact that it is a disk. This causes internal fragmentation, which has a few negative side effects.

contiguous file access would consist of going back and forth.
positioning cost (high cost to move around)
defragmentation tools exist to reorganize the disk data.
Block size was too small (512 bytes), which means transferring data was inefficient.
- small block minimizes internal fragmentation, but requires repositioning overhead to reach it.

FFS

Fast file system (FFS) is a faster file system.

The allocation policies should be "disk aware," thus have improved performance. Had the same interface (used the same API) but changed the internal implementation.

All modern file system adhere too this interface to preserve compatibility.

The Cylinder Group

Divides disk into cylinder groups A cylinder: set of tracks on different surfaces of a hard drive that are the same distance from the center of the drive.

FFS aggregates N consecutive cylinders (of different size) into a group. The disk can be viewed as a collection of groups.

Disks will export a logical address space of blocks and hide details of their geometry from clients. The drive is divided into block groups, each with a consecutive portion of the disk's address space.

when files are placed in the same group, the FFS can ensure that accessing one after another will not result in long seeks across the disk

Each group will have its set of structures

Super block (S) needed for mounting the file system. there are multiple copies
per-group inode bitmap (ib) and data bitmap (db) is used to track within each group whether the inodes and data blocks are allocated. Bitmaps manage free space.
inode and data block regions are normal.

File creation process in FFS is quite long. Say we create a file /foo/bar.txt that is 4kb long (one block).

New inode needs to be allocated and written to disk. Inode bitmap must be updated.
The data is allocated, thus you write to the data bitmap and the data block.
Since it is in a file-system hierarchy, the directory must be updated. )foo needs entry. If the update fits in an existing data block, then it is updated, but if it requires a new block to be allocated, then the data bitmap also needs to be updated which means the inode of foo now needs to be updated to reflect the new length of the directory and modified time.

Allocate files and directories

FFS decides how to place files and directories and associated metadata on disk to improve performance. Keep related stuff together. What's related?

Placing directories:

find cylinder group with a low number of allocated directories (to balance them across groups) and a high number of free inodes (so that you can allocated files) and place it here.

Placing files:

allocate data blocks of a file in the same group as its inode so that you don't have to have long seeks between inode and data.
All the files that placed with its directory.

File locality

SEER traces analyze how far away file accesses are from another in the directory tree.

f is opened and reopened, its 0
dir/f is opened then dir/g is opened. That's one because they share the same dir but not file.
How far up the directory tree you have to travel to find the common ancestor of two files.

Results show that nearly 40% of file accesses were the same file or the same directory. and 25% had a distance of two.

There is less namespace locality in the random traces as expected. Every file shares the same root ancestor, thus random is useful as a comparison point.

Large file exception

A large file could fill up the block group.

Bad because then the "related" files would not be in the same block group. This hurts file-access locality.

Solution with FFS: after some number of blocks are allocated in a block group, then the next large chunk of the file in another block group.

Potential issue: spreading blocks of file across disks will hurt performance

Solution: when the chunk size is large enough, the file system will spend most of its time transferring data from the disk and less time seeking between because relatively short time (this is amortization).

FFS decides chunk size via the structure of the inode. First 12 direct blocks are in the same group, sthen each subsequent indirect block and all the blocks it points to is in a different group.

If the block size is 4KB, then every 1024 block of the file is in a different group. The exception is the first 48kb of the file that is pointed to by the direct pointers.

Over the years, transfers rates improve significantly because more bits are crammed onto the same surface which means you can transfer more data between seeks

Other things

Tiny 2KB sized files were common. Because 4KB blocks, there was internal fragmentation. The solution was to use sub-blocks, which were 512byte little blocks that file systems could use to allocate to files.

1kb file would occupy two sub-blocks instead of the 4kb block. As the file grows, you allocate more, but then when it requires a 4kb block, then FFS will copy the sub-blocks into the big block and free those sub blocks.
This might seem inefficient, which is why the library actually buffers writes and issues them out in 4kb chunks.,

FFS has layout such that it skips every other block, so that it has enough time to request the next block before the disk head skipped pass it. It figures out how many blocks it should skip in the layout to prevent extra rotations. Technique is called parameterization. It figures out specific performance parameters to decide the staggered layout.

To read a certain block once, you may thing you would need to rotate around the track twice, but disks use internal disk cache ("track buffer"). When read, it is cached.

FFS allowed for long file names.

Symolik links: hard links could not point to directories (fear of oops) and can only point to files in the same volume (same inode number). Symbolick links are "alias" that are much more flexible.

rename() operation made for renaming files.

Chapter 42: Crash Consistency: FSCK and Journaling

File system data structures must persist despite power loss or system crash. This problem is called crash-consistency problem.

Example: Must write to A then B. If A is written, then the system crashes before B, then the disk will be left in an inconsistent state.

Example workload

Goal: append a data block to an existing file by 1) opening the file, 2) move the offset to the end of the file with lseek(), 3) write 4KB, and 4) close the file.

System: simple file system has inode bitmap (8 bits, one per node), data bitmap (8 bits, one per data block), inodes (8 spread between four blocks), and data blocks (8)

State:

inode number 2 is allocated, marked on inode bitmap
data block 4 is allocated and marked on data bitmap.

The inode stores information like the owner, permission, size is 1, pointer is 4 (the data block), null, null, and null, and more.

Appending requires the addition of a data block, so we need to update the inode to point to the new block and update the size, the new data block, and the data bitmap.

Now the new inode says size is 1 and pointer is 4, and 5.

Notice that this process has three separate writes to the disk. These don't happen simultaneously nor immediately after write() system call is issued. Rather, the dirty inode, bitmap, and new data will sit in main memory (in page cache or buffer cache) for some time until the file system decides to write them to the disk. The crash can occur at any stage.

Possible crash scenarios

Just the data block is written to the disk, but there is no inode that points to it nor no data bitmap that says the block is allocated. Thus, it looks like the write never occurs. This is no problem.
Just the updated inode is written to the disk. The inode points to the new data block, but this data block is not been written. When you read, it will just be garbage data (old content).
- This is called a file-system in-consistency. The inode says that it has been allocated but the data block bitmap says it hasn't. This is a disagreement that must be resolved.
Just the data bitmap has been updated but no inode points to it. This is also an inconsistency. This leads to a space leak, as block 5 would never be used by the file system.
Inode and data bitmap have been written, but not the data. Metadata is consistency, but the data is actually garbage.
Inode and data block are written, but not the data bitmap. There is inconsistency that has to be resolved.
Data bitmap and data block written, but not the inode. No clue what file this data belongs to.

These problems are generically termed crash-consistency problem or consistent-update problem.

Solution 1: File System Checker

Approach: let inconsistencies happen and fix them later (when rebooting), this is an approach for consistency taken by older file systems

The fsck is a Unix tool that finds inconsistencies and repairs them.

Pitfall: can't fix all problems, like when file system looks consistent but the data is garbage. It's limit is that it can only ensure file system metadata is internally consistent.

It is run before the file system is mounted and made available (and no other file-system activity is on-going while it runs).

Phases:

Check superblock is reasonable. Is the file system size greater than number of blocks that have been allocated.
Check free blocks. Scan inode, indirect blocks, double indirect blocks, etc. to see which blocks are allocated. This knowledge produces a correct version of the data bitmaps. Trust the information in the inode. The same type of check is performed for all the inodes to make sure they are in use and marked as such in the inode bitmap.
Check inode state: corrupted or problematic. Checks that inode has valid type field like regular file, directory, sympolic link, etc. If there are problems, then it is cleared and the bitmap is also updated.
Check inode links: verifies the link count of each allocated inode. Link count is the number of different directories that contain a reference to this particular file. Then, fsck will scan through the entire directory tree from the root and build its own link count for every file and directory. If there is a mismatch between the self-calculated count and the inode's count, then the inode is updated. If an allocated inode is discovered but no directory refers to it, it is moved to the lost+found directory.
Duplicates: checks for duplicated pointers: when two different inodes point to the same block. If one inode is obviously bad, it may be cleared. alternatively, the pointed-to-block could be copied and each inode can have its own copy.
Bad blocks: check for bad block pointers while scanning through the list of all pointers. The pointer is "bad" if it pointers to something outside its valid range (address > partition size). Remediation: it will clear the pointer from the inode / indirect block.
Directory checks: integrity checks on each directory like making sure that "." and ".." are the first entry, that each inode it refers to is allocated, and that no directory is linked to more than once in the entire hierarchy.

Issue: too slow. Scanning could take many minutes or hours. As disks grew in capacity and RAIDs became popular, it became prohibitive. It's also irrational that when there is a write, you always scan for the whole disk. (analogous to dropping your keys on the bedroom, and the searching the entire house).

Solution 2: Journaling.

Journaling (also known as write-ahead logging) is a different technique that adds overhead to each write but has quicker recovery time.

Idea: when updating the disk, before overwriting any structures, first write down a note (somewhere else on the disk in a well-known location) describing what you are about to do. Writing this note is the "write ahead" part, and we write it to a structure that we organize as a "log."

Now if a crash takes place during update, then you can go back and look at the note you made and try again. You will know exactly what to (and how to) fix after a crash.

Linux ext3 is a popular journaling file system.

Maintains ext2 structure: disk is divided into block groups, each block group contains an inode bitmap, data bitmap, inodes, and data blocks.
Additional structure that is the journal itself. It occupies some small amount of space within the partition or on another device.

Data Journaling

How does data journaling works in ext3 file system? Say we have the example above described in Example workload.

First, the log / journal will write 5 blocks:

The transaction begins (TxB). It tells us about this update, including information about the pending update to the file system (e.g., final addresses of the blocks to be updated) and a transaction identifier (TID).
Next three blocksL exact contents of the blocks themselves. This act of putting the exact physical content of the update is called physical logging. Alternatively, logical logging is to put a compact logical representation of the update in the journal (append data block Db to file X). More complex process but saves space and can be better performing.
End with a transaction end marker (TxE). This contains that TID.

Only after the transaction is logged to the disk, do we start overwriting the old structures in a process called checkpointing. To checkpoint (bring up to date with the pending update in the journal), we issue the writes. Only when the writes are successful do we consider that we have checkpointed the file system.

Issue: what if the crash occurs during the write to the journal?

Naive: if we write it all at once, it could write TxB and TxE first, and then if it crashes midway we don't know if the data in the journal is correct.
Solution: Issue the transactional write in two steps. Write all blocks except for TxE to the journal all at once, and once it completes, then issue the write of TxE.

Another thing that needs to happen to guarantee atomicity is that the disk must also guarantee atomicity. The disk guarantees that any 512 byte write will either happen or not (and not be half-written). Thus, to ensure the write of TxE is atomic, one should make it a single 512-byte block.

Summary of the three phases:

journal write: write content of transaction to log and wait for completion
journal commit: write the TxE to the log, and journal is committed once that write is done.
checkpoint: write the contents of the update to final on-disk location.

Recovery

If a crash happens before the transaction committed to the log, then the update is skipped.

If the crash happens before the checkpoint is complete, then the file system can recover the update.

At boot, the file system recovery process scans the log and looks for transactions that have committed to the disk. These transactions are replayed in order. THe file system attempts to write out teh blocks in teh transactions. This process is called redo logging. The file system is mounted after.
Note, redo logging is only done after unexpected system crash.

Batching Log Updates

Some file systems do not commit each update to the disk one at a time. They buffer all updates into a global transaction.

In the example that two files are created, the file system will just mark the in-memory inode bitmap, inodes of the files, directory data, and directory inode as dirty, which adds them to the list of blocks that form the current transactions. When it is time to write to disk, this single global transaction is committed and it contains all the updates.

This avoids excessive write traffic.

Making the Log Finite

Log will be full if we keep adding transactions, which is problematic because

The larger the log, the longer recovery will take, since it will replay all the transactions within the log (in order)
when the log is full, no transactions can be committed to the disk.

Solution: treat the log as a circular data structure, which is why its sometimes called circular log.

Once the transaction has been checkpointed, the file system should free the space it was occupying within the journal.

this can be done by marking the oldest and newest non-checkpointed transaction in a journal superblock. This block records enough information to know which transactions have not been checkpointed.

Summary of the four phases:

journal write: write content of transaction to log and wait for completion
journal commit: write the TxE to the log, and journal is committed once that write is done.
checkpoint: write the contents of the update to final on-disk location.
free: mark th etransaction free in the journal by updating the journal superblock.

Metadata Journaling

Doubling write traffic (once in journal and once in disk in what we term data journaling).

One method to speed up performance is ordered journaling or metadata journaling. It is the same, except user data is not written in the journal (just inode and data bitmap).

The data block will be written first to guarantee that pointers will never point to garbage data.

This method is more popular than full data journalling.

Summary of the four phases:

data write: write data to final location
journal metadata write: write content of transaction to log and wait for completion
journal commit: write the TxE to the log, and journal is committed once that write is done.
checkpoint: write the contents of the update to final on-disk location.
free: mark th etransaction free in the journal by updating the journal superblock.

Tricky Case: Block Reuse

Block reuse is when a block is reused for a different purpose and the problem occurs with metadata journaling.

Suppose there is a directory called foo that is updated. Thus the journal says to update the inode and its directory data block (since directories are considered metadata) at 1000.

Then, the user deletes the directory and frees it for reuse. It creates a new file bar that ends up using block 1000. In metadata journaling, it will write the data to this block, and only update the journal to include the inode of bar

Say a crash occurs and all this information is still in the log. The recovery process replays everything in the log, including the write of directory data in block 1000, thus overwriting the user data from bar with old directory contents. Now, there's no way to recovery the file contents of bar.

One solution: never reuse blocks until the delete of the blocks is checkpointed out of the journal

Second solution: add a new type of record to the journal. known as revoke. Deleting the directory causes a revoke record. When replaying the journal, the system first scans for revoke records, and any revoked data is never replayed, thus avoiding the overwrite.

Solution 3: Other Approaches

Soft Updates

Carefully order all writes to the file system to ensure that the on-disk structures are never left in an inconsistent state.

Challenge is in the implementation. Journaling is good because it needs little knowledge of the file system structure while Soft Updates requires intricate knowledgge of each file system data structure and thus adds a fair amount of complexity to the system.

Copy-on-write (COW)

Never overwrites files or directories in place. Rather, it places new updates to previously unused location on disk. After a number of updates are completed, then the COW file system flip the root structure of the file system to include pointers to the newly updated structures. This makes the file system consistently straightforward.

Chapter 43 Log-structured File Systems is an early example of COW.

Popular. Used in Sun's ZFS.

Backpointer-based Consistency (BBC)

No ordering is enforced between write. To achieve consistency, an additional back pointer is added to every block of the system.

Each data block has a reference to the inode to which it belongs.

When accessing a file, the file system can determine if the file is consistent by checking if the forward pointer (an address in the inode or direct block) points to a block that refers back to it.

If so, everything must have safely reached the disk and thus the file is consistent
If not, the file is inconsistent, and an error is returned.

This is a form of lazy crash consistency.

Other

Optimistic crash consistency: issues as many writes to disk as possible by using a generalized form of the transaction checksum.

Aside: Forcing Disk Writes

With write buffering, the disk informs the OS the write is complete when it has simply been written to cache (not disk). So now, when the OS issues a subsequent write, it is not guaranteed to occur after the previous writes, meaning there is no ordering preservation.

Other than disabling writing buffering, there is a modern technique called write barriers. All writes issued before the barrier will be written to disk before any writes issued after the barrier.

In reality, some disk manufacturers will ignore write barrier requests so that the disks seem like they are running faster but it could be incorrect.

Chapter 43: Log-structured File Systems

A new file system known as the log-structured file system.

Motivation:

System memories are growing: as memory gets bigger, more data can be cached in memory. As more data is cached, disk traffic increasingly consists of writes as reads are serviced by the cache. Thus, the performance of a file system is based on the write performance.
gap between random I/O performance and sequential I/O: hard-drive transfer bandwidth has increased as more bits are packed into the surface. Seek and rotational delay cost have decreased slowly in comparison because it is challenging to make cheap and small motors spin the platter faster or move the disk arm more quickly.
existing file systems perform poorly on many common workload: e.g., FFS performs a large number of writes just to create a new file of size one block: one for new inode, one to update inode bitmap, and one to the directory data block that the file is in, one to the new data block that the file is in, and one to the data bitmap to mark the data block as allocated. Though FFS places all these blocks within the block group, many short seeks occur.
File systems are not RAID-aware: RAID-4 and RAID-5 have the small-write problem, where a logical write to a single block causes 4 physical I/Os to take place.

Note: details matter in these systems. The general idea is easy to understanding but to really build a working system, you have to think through all the tricky cases.

The ideal file system would thus

focus on write performance
make use of the sequential bandwidth of the disk
perform well on writing out data but also on updating on-disk metadata structures
work well on RAIDs

Log-structured File System (LFS) buffers all updates (including metadata) in an in-memory segment. When the segment is full, it is written to disk in one long, sequential transfer to an unused part of the disk. LFS never overwrites existing data, but rather always writes segments to free locations.

Because segments are large, the disk (or RAID) is used efficiently.
The crux: how do you transform all writes to sequential writes? Impossible for reads, because the file system can't know where the data is.

How to write to disk sequentially

Say we want to write data D to a file. The data is get written to disk as well as other metadata like the inode (I). Have I point to D.

D can sit at A0 and I is written right after.

The basic idea: write all the updates sequentially.

Writing to disk sequentially is not alone enough to guarantee efficient writes.

Imagine we wrote a single block to address A and time T. We then ait a while and then write to disk at A+1 (next block address) at T + delta.
In between the first and second write, the disk has rotated.
The second write must wait for most of the rotation to be done before being committed (T_rotation - delta).
The key is that the issue must be for a large number of contiguous writes in order to be efficient.

This is achieved with write buffering. Before writing to the disk, LFS tracks the updates in memory, and when it has received a sufficient number of updates, it writes them to the disk all at once, thus ensuring efficient use of the disk.

large chunks of updates LFS writes at once is called a segment.

How much to buffer

Depends on the disk. How high the positioning overhead is in comparison to its transfer rate.

Every time you write, you pay the overhead of the positioning. So how much do you have to write in order to amortize that cost.

The effective rate of writing would be the amount of data written divided by the total time it takes to write it, which is the positioning cost plus the amount of time it takes to write that data.

This rate must be as close to the peak rate as possible. It is described as some fraction fo peak rate. This might belike 90%.

Problem: Finding Inodes

How do we find an inode in LFS? Recall that in a typical file system like FFS, finding inodes is easy because they are organized in an array and placed on the disk at fixed locations.

Traditionally on the old unix file system: If you have the inode number and the start address, it can be calculated by multiplying the inode number by the size of an inode and then add it to the start address.
In FFS: the inode table is split into chunks and each group of inodes is placed in each cylinder group. Thus, one must know how big each chunk of inodes is and the start addresses of each. After that, the calculation is similar.
In LFS, the inodes are scattered throughout the disk and the latest version of an inode (the one we want to keep) keeps moving.

LFS introduced a level of indirection between inode numbers and the inodes through a inode map (imap). It takes an inode number as input and produces the disk address of the most recent version of the inode. This can be implemented as an array with 4 bytes per entry (the disk pointer).

Aside: level of indirection is a solution to most problems. Ever virtualization we have studied is simply a level of indirection. The downside is that it requires extra overhead

It must live on the disk but where?

It can live on the fixed part. But if the imap had to be written to every time a file structure is updated, then the performance would suffer (disk seeks).

The LFS places chunks of the inode map right next to where it is writing all of the other new information.

Thus, when appending a data block to a file, LFS updates one more thing: it will write to the new data block, its new inode, and then a piece of the inode map onto the disk.

But at one point, the file system must have some fixed and known location the disk to begin a file lookup. This is the checkpoint region (CR). It contains pointers to the latest pieces of the inode map. The checkpoint region is updated periodically (every 30 seconds) so that it doesn't effect performance.

Recap: Reading a file

To read a file from disk: read the CR to find the inode map. LFS reads the entire inode map and caches it into memory. Now, given an inode number, its inode can be looked up. At this point, it operates like FFS< the inodes have direct or indirect pointers to read the data.

Directories

Directory structure is identical to the class unix file system. It's just a collection of (name, inode number) mappings.

so when creating a file on a disk

LFS must write: new inode, data, directory data, and inode that refers to this file.
The sequential order into the segment is: data of the file, inode for the file, directory data, inode that points to the directory, and imap that contains the location of the directory file and the newly created file.

to read a file foo.

first look at inode map to find the directory dir that foo is in. Inode map points you to directory inode, which points you to the directory data. Here, you'll find the name-to-inode-number mapping (foo, k). Then you can find inode k in the inode map. You'll read inode k to find the data block.

The recursive update problem is one that arises in file systems that don't update in place, but rather moves updates to new locations on the disk. When the inode is updated, its location on the disk changes.

To capture this update, one way would be to update the directory that points to this file, which would mandate a change to the parent of that directory, all the way up....
However, with the inode map (imap), a change in the inode location is never reflected in the directory, rather just he imap. The directory doesn't need to know where its child file is located. Indirection avoids this common problem!

Garbage Collection

Since LFS repeatedly writes the latest version of a file, it implies that old versions (called garbage) of file structures are scattered throughout the disk.

Sometimes, we can simply append a block so that the first data block is still live (current) but the first inode is garbage. The second inode and data block are both lice.

One solution is to keep the older versions around and allow users to restore old file versions. This system would be known as versioning file system.

However, LFS keeps only the latest live version of the file. Thus, LFS must periodically find and clean out the garbage, making those blocks free again.

The process of cleaning is a form of garbage collection, a technique that arises in programming languages that frees unused memory.

How does garbage collection work?

Imagine if LFS cleaner simply went through and freed single data blocks, the file system would have a bunch of holes and large contiguous regions would be hard to find.
Instead, the LFS cleaner works segment-by-segment.
- Periodically, the LFS cleaner reads in old segments and determines which block live within these segments. They write out a new set of segments with just the live blocks.
- The cleaner reads in M existing segments, compact their contents into N new segments (N < M), and then writes N segments to disk in new locations. The old M segments are all freed.

How does LFS tell which blocks within the segment are live?

Given data block D within segment S, LFS must determine if D is live.
LFS adds information to each segment to describe each block within it. For each data block D, it stores its inode number (which file it belongs to) and its offset (which block of the file it is). This information is recorded in a structure at the head of the segment known as the segment summary block.
For a block D located at A, look in the segment summary block and find its inode number N and offset T. Next, look in imap to find where N lives and read N from the disk. Using the offset T, look in the inode and see where it thinks the Tth block is. If it points to A, then we conclude D is live. If it points anywhere else, then we can conclude D is dead and can be freed.

// N is inode number, T is offset
(N, T) = SegmentSummary[A];
inode = Read(impa[N])
if (inode[T] == A) // D is alive
else // D is dead

Shortcuts for determining liveness: if a file is truncated or deleted, LFS increases its version number and records the new version number in the imap. By recording the version number in the on-disk segment, then LFS can short circuit the lonegr check by comparing the on-disk version with the version number in the imap.

How do you decide when to clean?

periodically, during idle time, or when disk is full

How to decide which segments to clean?

In the original LFS paper, the authors describe segregating hot and cold segments.
- Hot is one which the contents are being frequently over-written. Thus, wait a long time before cleaning it because more blocks are getting over-written and thus freed for use.
- Cold segments are ones that have a few dead blocks but the rest of the contents are stable.
- One should clean cold segments sooner.

What happens if the system crashes while LFS is writing to disk?

Recall <1> : during normal operations, LFS buffers writes in a segment and then writes it to disk. LFS organizes these writes in a log, i.e., the checkpoint region points to a head and tail segment, and each segment points to the next segment to be written.
Recall <2>: LFS periodically updates the checkpoint regions
Solution to <2>: To ensure the CR update happens atomically, LFS keeps two CRs. One at either end of the disk, and writes to them alternatively. It also has a careful protocol when updating the CR with the latest pointers to the inode map and the other information.
- Write out a header (with timestamp) and then the body of the CR, and then the last block( with timestamp). The system can detect that there was a crash because there will be an inconsistent pair of timestamps. LFS then chooses the most recent CR with consistent timestamps.
Solution to <1>: LFS writes to CR every ~30 seconds so the last consistent snapshot could be old. Upon reboot, it can read the checkpoint region and read that state, but the most recent seconds of updates is lost. It tries to rebuild those segments via roll forward technique.
- Start at the last CR, and find the end of the log (included in CR), and then use it to read through the next segments and see if there are any valid updates within it. If there are, LFS updates the file system and recovers much of the data and metadata written since the last checkpoint.

Summary

the approach of writing to unused portion instead of over-writing files in place is called shadow paging (database-system-speak) or copy-on-write (file- system-speak) and it enables efficient writing.

Tip: turn flaws into virtues: whenever your system has a fundamental flaw see if you can turn it into a feature. That's where versioning file system came from. Instead of cleaning, just keep it.

Large writes that LFS generate perform graet on hard drives (minimize positioning time), parity-based RAIDs (avoid small write problem), and flash based SSDs (large I/O required for high performance).

Modern systems that use this: WAFL, ZFS, btrfs, and flash-based SSD.

Appendix B: Virtual Machine Monitors

IBM used to sell expensive mainframes to large organizations.

Problem: they wanted to use different operating systems.
Solution: indirection via virtual machine monitor (VMM) or hypervisor.

The monitor sits between one or more operating system and the hardware gives the illusion to each running OS that it controls the machine. Behind the scenes, the monitor is of control in the hardware, multiplexing the different running OSes across the physical resources. The OS must believe it is interacting with the physical hardware. Thus, transparency was a big goal of the VMMs.

The OS has been the illusionist, tricking applications into thinking they have their own private CPU. Now we do it underneath the OS, such that VMM create this illusion for each OS.

Motivation

Why VMMs?

Able to consolidate multiple OSes onto fewer hardware platforms, thus lowering costs and maintenance.

Functionality, so that we users have access to native applications on one platform.

Testing and debugging: make sure your application works on different platforms.

Virtualizing the CPU

limited direct execution is the basic technique used to run a CM on top of a VMM.

To "boot" a new OS on top of the VMM, jump to the address of the first instruction and let hte OS begin running.

Assume a single processor. In a manner quite similar to context switch, a VMM must perform a machine switch between running virtual machines. It must save the entire machine state of one OS and restore the machine state of the to-be-run VM and then jump the PC of the to-be-run Vm and complete the switch.

The to-be-run VM's PC may be within the OS itself (the system executing a system call) or it may be a within a process that is running on that OS (i.e., user-mode application).

When a running application / OS tries to perform a privileged operation (like updating TLB with a translation before restarting an instruction that suffered a TLB miss) it cannot be allowed in a virtualized environment, because it then controls the machine rather than the VMM beneath it.

The VMM must somehow intercept attempts to perform privileged operations and retain control
Example: process on an OS tries to open() a file.
- Without virtualization: system call is achieved with the special instruction (trap on MIPS or int with 0x80 on x86). The trap is executed by transferring control (change PC) to a well defined trap handler within the OS. The OS establishes the address of such a routine with the hardware, (stored so that next trap it knows), and then it changes to kernel mode and the privileged operation is executed.
- With virtualization, it is the VMM who has installed a trap handler that will first get executed in kernel mode. It doesn't really know how to handle the call (doesn't know details of the OS) but it does know where the OS's trap handler (because upon boot up, it the OS tried to install its own trap handlers, which is privileged so it trapped into the VMM which recorded it all). Now, when the VMM receives a trap from a user process on a given OS, it jumps to the OS's trap handler and let the OS handle the system call as it should. Wen the OS is finished, it executes a privileged instruction to return on trap (iret on x86) which goes to the VMM. It knows its from the OS returning form trap and thus performs the real return-from-trap and returns the control back to the user and puts the machine back into user mode.
What mode would the OS run in? It can't run in kernel mode because then it would have all access to hardware. Therefore, it must be in some less privileged mode. In Disco, they took advantage of MIPS hardware's supervisor mode. It doesn't have access to privilege instructions but it can access more memory than user mode. That extra memory is used by the OS for its data structures.
- If the hardware doesn't have such a mode, then it must run the OS in user mode and user memory protection to protect the OS data structures. I.e., when switching to the OS, the monitor must make the memory for the OS data structure available to the OS via page-table protections.

Virtualizing Memory

Normally, the OS sees physical memory as a linear array of pages, and assigns each page to itself or user processes. Another layer of virtualization to make "physical memory" a virtualization on top of machine memory (real).

Each OS maps virtual-to-physical addresses via its per-process page table. Then the VMM maps the resulting physical mapping to underlying machine addresses via its per-OS page tables. There are V VMM page tables where V is the number of OS running.

Address translation in modern paged system uses a software-managed TLB.

Recall that a user process generates an address so the process generates a virtual address. The OS turns them into physical addresses with the help of the hardware TLB. It produces a fully-formed physical address. When a TLB miss occurs the OS gets involved by causing a trap into the OS which will handle the fault by looking up the VPN in the page table and installing the translation in the TLB.
With a VMM underneath, the TLB miss is handled by the VMM TLB miss handler. However, it won't know how to handle the TLB miss, so it will jump into the OS TLB miss handler (remember it knows where the trap handlers are at boot up). The OS TLB performs a table look up for the VPN and tries to install the VPN-to-PFN mapping int he TLB, however, this is privileged and it causes another trap. Instead of installing the OS's VPN-to-PFN mapping, the VMM installs the desired VPN-to-MFN mapping.
- Just like how the OS has a page table for each process, the VMM tracks the physical-to-machine mapping for each VM.
- This makes TLB misses on virtualized systems more expensive than non-virtualized. To solve this, VMM-level "software TLB" records every virtual-to-physical mapping that it sees the OS tries to install. Then on TLB misses, this is the first thing that is consulted. If found, it simply installs the virtual-to-machine mapping directly into the hardware TLB.

Aside: OS can be modified (don't assume it though) so that it can run more efficiently on top of a VMM. A modified OS to be run on a VMM is generally called para-virtualization.

research shows that properly-designed para-virtualization systems can be nearly as efficient.

Information Gap

VMM doesn't know too much about what the OS is doing or wanting. This lack of knowledge is called the information gap between VMM and OS and it leads to inefficiencies.

E.g., an OS when it has nothing to do, will go into an idle loop. If the OS is in charge of the entire machine, it knows there's nothing else that needs to run. However, the VMM doesn't know and could give more CPU time to a busier OS.
E.g., demand zeroing of pages. Most OS zero a physical frame before mapping it into a process's address space for security. VMM must zero pages it gives to each OS for the same reason, but the page may be zeroed twice (once by VMM to give to OS and once by OS to give to process).
- Solution: changed the OS to stop zeroing pages if it has already been zeroed by the underlying VMM.

One solution is to use inference or implicit information to overcome this problem.

implicit information is a powerful tool in layered systems where it is hard to change the interface between systems, but more information is needed. E.g., a block0based device might liek to know how the file system above it is using it. E.g., an application wants to know what pages are currently in the file-system page cache. Inferencing techniques gather this needed info implicitly, without requiring an explicit interface between layers. No API needed.
A VMM can detect the idle loop by noticing that the OS switched to low-power mode.
Also could use para-virtualized systems.

Summary

VMM provide their service transparently; so the OS above has little clue they aren't controlling the hardware of the machine.

Key method to do this is to extend the notion of limited direct execution by setting up the hardware to enable the VMM to interpose on key events (like traps)

What the OS does for processes the VMM does for OSes. With VMM-level virtualization the abstraction is identical to the hardware. OS abstractions provide new abstractions and nice interfaces.

The VMM's goal is not to make the hardware easier to use.

So much more

How does I/O work
What happens when a collection of OS running on VMM uses too much memory
Hosted configuration where virtualization works while running on the side with your OS.
Intel and AMD include direct support

Linked from Operating Systems

Chapter 2: Introduction to Operating Systems

Chapter 4: The Abstraction: The Process

The Process

Process API

Process Creation

Process States

Data Structures

Chapter 5: Interlude: Process API

fork()

wait()

exec()

Design

Process Control

Tools

Chapter 6: Mechanism: Limited Direct Execution

Chapter 7: Scheduling: Introduction

Workload

Metrics

First in, first out (FIFO)

Shortest Job First (SJF)

Shortest time-to-completion first (STCF)

Round Robin (RR)

Incorporating I/O

Summary

Chapter 8: Scheduling: The Multi-Level Feedback Queue

Chapter 14: Interlude: Memory API

Types of Memory

malloc() call

free() call

Underlying OS support

Other Calls

Chapter 15: Mechanism: Address Translation

Example

Dynamic (hardware-based) relocation

Chapter 16: Segmentation

Support for sharing.

Fine vs coarse grain segmentation.

Issues

Summary

Chapter 17: Free-Space Management

Assumptions

Low level mechanisms.

Splitting and Coalescing

Tracking the size of allocated regions

Embedding a free list

Growing the heap

Basic Strategies

Best fit

Worst fit

First fit

Next Fit

Other approaches

Segregated lists

buddy allocation

Other ideas

Chapter 18: Paging: Introduction

Page tables

Too slow

Chapter 19: Paging: Faster Translations (TLBs)

Introduction

TLB Algorithm

Accessing an array

Who handles the TLB Miss?

TLB Contents

Context Switches

Replacement policy:

Real TLB Entry

Summary

Chapter 20: Paging: Smaller Tables

Solution 1: Bigger pages

Solution 2: Paging and segment hybrid

Solution 3: multi-level page tables

Example:

More than two levels

translation process

Inverted page tables

Swapping the page table to disk

Chapter 21: Beyond Physical Memory: Mechanisms

Swap Space

Present Bit

`fork()`

`wait()`

`exec()`

`malloc()` call

`free()` call