CS @ the University of Washington

Back to main

March 1st 2024

Operating System Notes

This is the aggregation of all my notes from the University of Washington's CSE 451 Operating Systems course.

Week 1

Physical memory

Storage devices

Other devices

Typical abstractions

Why provide abstractions?

Motivation

Protection Rings

Types of Mode Transfer

PC - Program Counter

Types of mode transfers

Mode Transfer Mechanisms

Week 2

Mode Transfer control flow

Processes

Process Implementation

How processes share a CPU (core)

Fork & Exec combo

We spent time copying parent’s memory content, set up a translation table

Set up process’s new VAS, resource intensive

Copy on write (COW)

Share the same physical memory for as long as possible (while only servicing reads)

The moment write occurs, we need to make a copy

Both of the above, HW detects memory permission violation

Mark shared memory as read-only, even if the parent VAS memory was writable

The moment a write occurs, page fault, then detected by hardware (kernel must determine if copy on write, or real permission violation)

Process creation transition

Ready State (RUNNABLE)

Running state

Blocked State (waiting)

Grocery Line Example

procstate is scheduling state (runnable, waiting, zombie)

Process APIs

pid = fork()
if (pid == 0) {
    fd = open("output.txt");
    close(stdout);
    dup(fd);
    exec("ls");
}
 // Redirection logic is written under the child case (pid == 0)
 // Fork gives you the opportunity to configure a bunch of things
 // without the knowledge of another program being involved

Process APIs

fork, exec, cow fork (performance optimization)

exit()

OS is responsible for reclaiming these resources after termination

wait() (xk = waitpid(-1)) / waitpid() (unix)

Scheduling

Week 3

Scheduling methods

Threads

Process

Thread

Creating threads, pthread API

Threads

Process

Thread

Creating threads, pthread API

Threads

Locks

Lock Implementation

struct lk { // this struct itself is a shared state
	int locked; // boolean
	holder;
	id/name;
}

// What protects lock_acquire from other threads attempting
// to lock simultaneously
void lock_acquire(*lk lock_pointer) {
	while(lk->locked) {
		continue;
	}
	lk->locked = 1; // Lock the lock, how we acquire it
	return;
}

// Alternate implementation
void lock_acquire(*lk lock_pointer) {
	if (!locked) {
		lk->locked = 1 // Lock the lock
		return;
	} else {
		while(lk->locked) {
			continue;
		}
	}
}

lock_release(*lk lock_pointer) {
	
}

Problem: multiple threads can attempt to lock simultaneously

Solution: requires hardware support for atomically performing read & modify

void lock_acquire() {
	while (test&set & locked) {
		// upon exit the locked is already 1
		// then test&set = 1, and locked = 0, breaking loop
	}
}

Types of locks

Types of locks

Lock granularity

Disable interrupt

We need to coordinate threads based on events → Monitors

Monitors

Week 4

The Morning Coffee Problem

Lock lk;
int coffee = 0;
Condvar coffee_cv;

get_coffee() {
	lk.acquire();
	// For condition variables, we should expect
	// spurious/fake wakeups with missing resources
	while (coffee <= 0) {
		coffee_cv.wait(lk);
	}
	coffee--;
	lk.release();
}

make_coffee() {
	lk.acquire();
	coffee++;
	coffee_sv.signal();
	lk.release();
}

Implement a Sleeplock

Lock lk;
bool free = False;
Condvar lock_cv;

lock_acquire() {
	lk.acquire();
	while (!free) {
		lock_cv.wait(lk);
	}
	free = False;
	lk.release();
}

lock_release() {
	lk.acquire(); // assert(!free)
	free = True;
	lock_cv.signal();
	lk.release();
}

Implement a Fair Sleeplock with Bounded Waiting

// Lock must be acquired in FIFO order
// New thread can't acquire the lock untill
// all prior waiters have done so.
// Maybe we could implement a queue?
Lock lk;
bool free = False;
Condvar lock_cv;
wait_queue = [];
Condvar wait_cv;

lock_acquire() {
	lk.acquire();
	wait_queue.append(self); // Wait for our turn to acquire the lock
	while (wait_queue.head() != self) {
		wait_cv.wait(lk);
	}
	while (!free) {
		lock_cv.wait(lk);
	}
	free = False;
	wait_queue.remove_head();
	wait_cv.signal();
	lk.release();
}

lock_release() {
	lk.acquire();
	free = True;
	lock_cv.signal();
	lk.release();
}

Bounded buffer problem

Common system design regarding locking

Lock lk;
buffer[N]
int consume_ofs = 0;
int produce_ofs = 0;
int total_items = 0;

produce(item) {
	lk.acquire();
	while (total_items == N) {
		not_full_cv.wait(lk); // Releases the lock
	}
	total_items++;
	buffer[produce_ofs] = (produce_ofs + 1) % N;
	not_empty_cv.signal(); // Signal consumers
	lk.release();
}

consume() {
	lk.acquire()
	while (total_items == 0) {
		non_empty_cv.wait(lk); // Releases the lock
	}
	total_item--;
	item = buffer[consume_ofs] % N;
	not_full_cv.signal(); // Signal producers
	lk.release;
}

Pipe

Read writer locks

Top Comment Example (scrolling down)

Read writer locks (RWL) in depth

Write Preferring RWL

Lock lk;
Condvar reader_cv;
Condvar writer_cv;
// Need to know if reader active to block
int active_readers = 0; // Don't need waiting readers
int waiting_writers = 0; // Need to track number to wake readers later
bool active_write = False; // Check for current writer
read_acquire() {
	lk.acquire();
	// Waiting writers condition prioritizes writers
	// Notice: Readers can be interleaved with no active writers
	while (active_write || waiting_writer > 0) {
		reader_cv.wait(lk);
	}
	active_readers++;
	...
	lk.release();
}

write_acquire() {
	lk.acquire();
	waiting_writers++; // Write about to happen, prioritize writers
	// Check if another writer inprogress
	// But wait to finish up readers before writing new
	while (active_write || active_readers > 0) { 
		writer_cv.wait(lk);
	}
	waiting_writers--;
	active_write = True;
	...
	lk.release();
}

Write Preferring Reader Writer Locks (RWL)

Read and write acquire spec:

Lock lk;
Condvar reader_cv;
Condvar writer_cv;
// Need to know if reader active to block
int active_readers = 0; // Don't need waiting readers
int waiting_writers = 0; // Need to track number to wake readers later
bool active_write = False; // Check for current writer
read_acquire() {
	lk.acquire();
	// Waiting writers condition prioritizes writers
	// Notice: Readers can be interleaved with no active writers
	while (active_write || waiting_writer > 0) {
		reader_cv.wait(lk);
	}
	active_readers++;
	...
	lk.release();
}

write_acquire() {
	lk.acquire();
	waiting_writers++; // Write about to happen, prioritize writers
	// Check if another writer inprogress
	// But wait to finish up readers before writing new
	while (active_write || active_readers > 0) { 
		writer_cv.wait(lk);
	}
	waiting_writers--;
	active_write = True;
	...
	lk.release();
}

Read and write release spec:

read_release() {
	lk.acquire();
	active_readers--;
	// Signal write because we write-preferring
	if (active_readers == 0 && waiting_writers > 0) {
		write_cv.signal();
	}
	lk.release();
}

write_acquire() {
	lk.acquire();
	active_write = False;
	// Writers can block both readers and writers
	// Checking and waking writers before waking readers
	// is the implementation of write-preferring policy
	if (waiting_writers > 0) {
		writer_cv.signal();
	} else {
		// As a writer, we can unblock any number of concurrent readers
		// We do not care if multiple readers, as long as no current writers
		// Or no waiting writers
		reader_cv.broadcast();
	}
	lk.release();
}

Read Preferring vs Write Preferring

Deadlocks

Deadlock Example 1:

// Classic deadlock
Lock A;
Lock B;

thread_func1() {
	A.acquire();
	B.acquire();
}

thread_func2() {
	B.acquire();
	A.acquire();
}

Deadlock example 2: Even without locks, blocking conditions

// 2 Bounded Buffer Deadlock
buffer A[];
buffer B[];

thread_func1() {
	A.consume(); // Blocks because A is empty, waits
	B.produce(item);
}

thread_func2() {
	B.consume(); // Blocks because B is empty, waits
	A.produce(item);
}

Deadlock example 3: Monitor lock vs General Lock

// Nested locking issue, common issue
// Can happen with general lock and pipe lock etc.
Lock lk;
Boundedbuf A[];

thread_func1() {
	lk.acquire(); // General lock
	...
	A.consume(); // Monitor-specific lock release
	...
	lk.release();
}

thread_func2() {
	// General lock
	lk.acquire(); // Cannot be acquired because t1 holds
	...
	A.produce(item); // Will not be run
	...
	lk.release();
}

Dining philosophers

Week 5

Safe, unsafe, and deadlock states

Example:

Last deadlock prevention, deadlock detection

Physical memory management

Problem: Many processes, limited physical memory, possible solutions includ

Attempt 3: Finer-grained translation & permission management

Kernel must track what VAS are valid and should be brought into memory, versus what address should not be accessed

Strategy is called paging: translation table

Attempt 3: divide virtual & physical memory

Page table, storing translations for all pages

Translation Lookaside Buffer (TLB)

Multilevel page table

Screenshot 2024-05-08 at 10.36.33 PM.png

Example:

x86 Page Table

Screenshot 2024-05-08 at 11.00.01 PM.png

Screenshot 2024-05-08 at 11.07.00 PM.png

Page Faults

Week 6

Page Fault

Handling valid page fault

Eviction mechanism (swapping)

For eviction, we need to allocate swap space from the bitmap (allocate on disk/persistent memory)

Eviction policy

When we are under memory pressure, when we need to allocate a frame when there aren’t an

Eviction with swap partition

Eviction policies

Optimal algorithm for page replacement policy

How to implement LRU

Clock

Cost of eviction

Signals: Interprocess communication (IPC), a predefined set of events that processes can use to communicate to each other

Mechanism of signals (software exceptions)

How would we implement the “kill” call?

And receive signals

User level threads

Week 7

User threads

What happens if a user thread blocks?

Storage Devices

Hard drives

IOPS

Solid State Drive

Operations SSD performs

Reliability of SSD

Latency of SSD request

Abstraction

Path

Filesys Implementation

Data layout

Week 8

Data layout

Case Study: Fast File System (FFS)

NTFS: New Technology File System

Filesys operations

Filesys = inode cache, block cache (bio.c)

Crash Consistency

Resolving inconsistency

Transaction: group arbitrary number of updates into a single atomic unit