Blog

This week we learned about data structures that make common operations fast: balanced search trees and hashing for searching, and heaps for finding the largest (or smallest) value.

Balanced search trees

In a binary search tree, every key in a node’s left subtree is smaller than the node’s key, and every key in its right subtree is larger. Searching works like binary search: compare with the current node, then go left or right, which takes Θ(log n) time if the tree is balanced, but the shape depends on the order of insertion. If you insert keys in sorted order, every node only has a right child, the tree is basically a linked list, and search drops to Θ(n). Balanced search trees fix this by rebalancing as keys are inserted.

AVL trees

An AVL tree is a binary search tree where every node has a balance factor of −1, 0, or 1. The balance factor is the height of the node’s left subtree minus the height of its right subtree, with an empty tree having height −1. You have to check every node, not just the root, because a tree can look balanced at the root and still be lopsided further down.

When an insertion makes a node’s balance factor 2 or −2, you fix the unbalanced node closest to the new leaf with one of four rotations:

• R (right) rotation: the new key went into the left subtree of the left child
• L (left) rotation: the mirror image, the right subtree of the right child
• LR rotation: the new key went into the right subtree of the left child, fixed by a left rotation and then a right rotation
• RL rotation: the mirror image of LR

The trick is that the middle of the three keys involved always becomes the new subtree root.

2-3 trees

A 2-3 tree handles balancing differently. Instead of rotating, it lets nodes hold more than one key. A 2-node has one key and two children, a 3-node has two keys and three children, and all the leaves have to be on the same level. New keys always go into a leaf. If that leaf ends up with three keys, it splits: the middle key moves up into the parent, and the smallest and largest keys become their own nodes. If the parent overflows too, it splits the same way, and if the root splits, the tree gets a new root. Since the tree only ever grows at the top, all the leaves stay at the same depth, and search is Θ(log n) no matter what order the keys come in.

Heaps

A heap is a complete binary tree where every parent is greater than or equal to its children (for a max heap; a min heap is the reverse). Either way, the max (or min) is always at the root. Since the tree is complete, you can store it in an array without any pointers. With 1-based indexing, the children of index i are at 2i and 2i + 1, and its parent is at ⌊i/2⌋.

To insert a key, you put it at the end and sift it up, swapping it with its parent until the parent is bigger. To remove the max, you swap the root with the last element, shrink the heap by one, and sift the new root down, swapping it with its larger child each time. Both operations take Θ(log n).

The bottom-up heapify construction is a little tricky. Instead of inserting keys one at a time, you put them all in the array and start at the last parent, ⌊n/2⌋. Moving backward to the root, you sift each node down. By the time you reach a node, both of its subtrees are already heaps. It seems like it should be Θ(n log n), but most nodes are near the bottom and can only move down a level or two, so the whole thing is Θ(n). Heapsort builds a heap this way and then removes the max n times, putting each one into the spot that just opened up at the end of the array, sorting in place in Θ(n log n).

Hashing

Hashing uses a hash function, like h(k) = k mod m, to turn a key into an index in an array of size m. When two keys hash to the same index, that is called a collision. There are two main ways to handle collisions. Separate chaining (open hashing) keeps a linked list at each index. Linear probing (closed hashing) puts the key in the next open cell, wrapping around to the start if needed. The load factor α = n/m measures how full the table is. When it gets too high, collisions pile up, so you rehash everything into a bigger table. With a good hash function and a reasonable load factor, search, insert, and delete take Θ(1) on average, although the worst case is still Θ(n).

This week covered a lot more ground than last week. We finished divide-and-conquer with quicksort and binary tree traversal and height calculations, then moved on to two new design techniques: decrease-and-conquer and transform-and-conquer.

Divide-and-conquer

Quicksort

Quicksort does most of its work in the divide step. It picks a pivot and partitions the array so that everything less than or equal to the pivot is on its left and everything greater than or equal to it is on its right. The pivot is then in its final position, and the two sides are sorted recursively. No combine step is needed.

The efficiency depends on how even the splits are. If the pivot lands in the middle each time, the recurrence has the same form as merge sort, giving Θ(n log n). In class we used the first element as the pivot, which makes the worst case an already sorted array: the pivot is always the smallest element, so one side is empty and the other has n − 1 elements, giving Θ(n²). Median-of-three partitioning avoids this for sorted input by using the median of the first, middle, and last elements as the pivot. The average case is Θ(n log n), and quicksort sorts in place, unlike merge sort.

Binary trees

A binary tree is either empty or a root with a left and a right subtree, which are themselves binary trees, so it fits the divide-and-conquer paradigm. The height is found by computing the heights of the left and right subtrees, taking the larger one, and adding 1 for the root. The height of the empty tree is defined as −1, so a tree with a single node has height 0. The three traversals differ only in when the root is visited:

• Preorder: root, left, right
• Inorder: left, root, right
• Postorder: left, right, root

Each of these visits every node once, so they are all Θ(n). The height calculation also visits every node once, so it is Θ(n) as well.

Decrease-and-conquer

Decrease-and-conquer reduces a problem to a single smaller instance of itself, solves that, and then builds on that solution to solve the original problem. Divide-and-conquer, by contrast, solves several subproblems and combines their solutions.

Insertion sort decreases by one. Assuming the first n − 1 elements are already sorted, it inserts the last element by shifting larger elements to the right until it finds the correct spot. The worst case is a reverse-sorted array, Θ(n²). The best case is a sorted array, Θ(n), which is the opposite of quicksort with a first-element pivot. This makes it a good choice for nearly sorted input.

Kahn’s algorithm finds a topological order of a directed acyclic graph (DAG): an ordering of the vertices in which every edge points from an earlier vertex to a later one. A common example is ordering courses by their prerequisites. The algorithm is:

1. Compute the in-degree of every vertex
2. Put the vertices with in-degree 0 in a queue
3. Remove a vertex from the queue, output it, and decrement the in-degree of each vertex it has an edge to
4. Add any neighbor whose in-degree drops to 0, and repeat

Each step removes one vertex, leaving a smaller graph. If the queue empties before every vertex has been output, the graph has a cycle and no topological order exists. With an adjacency list, the running time is Θ(V + E).

Transform-and-conquer

Transform-and-conquer changes the problem into a form that is easier to solve. Presorting is the simplest example. Checking whether an array has duplicates by brute force compares every pair, Θ(n²). If we sort first with a Θ(n log n) algorithm like merge sort, any duplicates are adjacent, and one Θ(n) pass finds them. The sort dominates, so the total is Θ(n log n). The same idea works for finding the mode. This is why efficient sorting matters so much: many other problems get easier once the data is sorted.

This week we covered merge sort as an example of the divide-and-conquer technique. Since much of the week went to reviewing for the midterm, merge sort was the only new algorithm we learned.

Divide-and-conquer has three steps:

1. Divide the problem into smaller subproblems of the same type
2. Conquer (solve) each subproblem recursively
3. Combine the subproblem solutions into a solution for the original problem

Merge sort works by dividing an array into two halves, sorting each half recursively, and then merging the two sorted halves back together. An important point is that the two halves must be sorted before they can be merged.

But how do we sort the two halves? By using merge sort! This is the recursive step. The base case is an array with only one element, which is already sorted by definition.

Applying the divide-and-conquer technique to merge sort:

1. Divide: Split the array into two approximately equal subarrays
2. Conquer: Recursively sort each subarray using merge sort
3. Combine: Merge the two sorted subarrays into a single sorted array

Here is an example implementation of merge sort on Python Tutor. Notice that the comparison uses <=. This means that the element from the left half goes first when both elements are equal, which makes merge sort a stable sort, since equal elements keep their original order.

Merge sort divides the input in half at each level of recursion, producing about log₂ n levels. At each level, merging the two halves takes linear time, giving merge sort a time complexity of Θ(n log(n)).

Week 3 covered a few brute force algorithms: sequential search, string matching, and the two graph traversal algorithms (DFS and BFS). We also started learning about divide-and-conquer algorithms, which we will study more in the coming weeks.

Searching and string matching

Sequential search is a common brute force technique. Basically, you just check every item until you find the one you’re looking for.

To find a substring in a string, we can use brute-force string matching. The main idea is that you check a pattern of m characters at each of the n − m + 1 possible positions, shifting one position to the right on a mismatch, until you find the complete substring or reach the the end of the window (in which case there is no match). Levitin’s textbook provides the following pseudocode:

The worst case is m(n − m + 1), or O(nm), because the inner loop runs m times for each of the n - m + 1 iterations of the outer loop.

Exhaustive search

Exhaustive search is brute force applied to combinatorial problems, like the traveling salesman problem (TSP). The main idea is that you generate every possible combination and then pick the best one. For TSP, this means generating every possible tour that visits each city exactly once and returns to the starting city, in order to calculate the total cost of each tour and choose the shortest one. Exhaustive search is guaranteed to find the optimal solution, but it becomes impractical for large inputs because the number of possible solutions grows extremely quickly.

DFS and BFS

Depth-first search (DFS) and breadth-first search (BFS) are two common graph traversal algorithms. DFS explores as far as possible along one path before backtracking and often uses recursion. BFS explores the graph level by level, visiting all neighboring vertices before moving farther away and is usually implemented with a queue. Both can be used to visit all reachable vertices, but they explore the graph in different orders.

This week we dove more deeply into the analysis of algorithms. Last week introduced order of growth, and this week expanded on that with asymptotic notation, analysis of non-recursive and recursive algorithms, and the first design technique, brute force.

Asymptotic notation

Notation	Meaning	Formal condition
O(g(n))	Upper bound	t(n) ≤ c·g(n) for all n ≥ n₀
Ω(g(n))	Lower bound	t(n) ≥ c·g(n) for all n ≥ n₀
Θ(g(n))	Tight bound	c₁·g(n) ≤ t(n) ≤ c₂·g(n) for all n ≥ n₀

The table above is based on the definitions given in section 2.2 of the Levitin’s textbook. Big-O, Big-Omega, and Big-Theta each compare an algorithm’s running time t(n) to a simpler function g(n), such as n or n².

For orders of growth, we only care about large inputs, so each condition has to hold from some starting size n₀ onward.

O(g(n)) is the upper bound: after n₀, t(n) never grows faster than some constant multiple c of g(n).

Ω(g(n)) is the lower bound: after n₀, t(n) always grows at least as fast as a constant multiple of g(n).

Θ(g(n)) is the tight bound: t(n) stays between two constant multiples of g(n), so it is both O(g(n)) and Ω(g(n)) and has the same order of growth.

The constants are what let us ignore details. You can pick any c and n₀ that make the inequality true, so coefficients and lower-order terms don’t change the classification. For example, 2n + 3 is Θ(n) because n ≤ 2n + 3 ≤ 3n for all n ≥ 3.

Analyzing non-recursive algorithms

To analyze a non-recursive algorithm, you count the basic operation, which is usually found in the innermost loop. Once the basic operation is identified, you determine how many times it runs, in terms of n, and simplify to get the order of growth.

For example, if an algorithm’s basic operation is in a nested loop, that runs n times for the outer loop and n times for the inner loop, then the order of growth is Θ(n²)

Analyzing recursive algorithms

A recursive algorithm’s count is written as a recurrence relation plus an initial condition from the base case, which can then be solved by backward substitution.

To solve a recurrence relation, substitute repeatedly until a pattern appears, generalize the pattern in terms of i, and then choose the i that reaches the base case, in order to express the relation in terms of n.

Brute force

Brute force means solving a problem directly from its definition, usually by trying every possibility. It can often be slow, but it’s a good starting point towards a more efficient solution.

This week we moved on to the next major part of OSTEP: persistence. The lectures covered OSTEP 36, 37, 39, and 40, from I/O devices up to a working file system.

OSTEP 36: I/O Devices

I/O devices are what make computers useful. Keyboards, mice, screens, network adapters, and hard drives are all examples of I/O devices.

There are two main types of I/O devices: block devices and character devices. A block device, like a hard drive, stores data in fixed-size chunks (blocks) with addresses, allowing random access. Character devices, like keyboards, stream data one byte at a time and are not addressable. The type of device determines how the OS and software interact with it.

The CPU talks to devices through a hardware interface, usually a set of registers. There is a status register to check if the device is busy, a command register to tell it what to do, and a data register to exchange information. The main question the lecture raised is: how does the OS use these registers without freezing while waiting?

Three strategies emerged: polling, interrupts, and DMA. Polling means the CPU keeps checking the status register in a loop until the device finishes. It is simple but wasteful because the CPU just spins. Interrupts let the OS issue a request and then do other work; when the device finishes, it signals the CPU to process the result. DMA (Direct Memory Access) lets the device move data into or out of memory without involving the CPU, which is much more efficient for large transfers.

The practical takeaway is that these mechanisms trade off simplicity for efficiency: polling is easiest to reason about, while interrupts and DMA better preserve CPU time for useful work.

OSTEP 37: Hard Drives

Hard drives have a long history in computing and will likely be around for a long time, even as SSDs continue to replace them. This lecture explained the physical mechanisms that make hard drives work.

A hard drive has one or more platters (spinning metal disks), and each platter has two surfaces. Moving arms with heads read or write data as the platter spins. Accessing data on a hard drive requires three steps: seek time (moving the arm to the right track), rotational delay (waiting for the desired sector to spin under the head), and transfer time (actually reading or writing the data).

There are two ways to address a disk block: CHS and LBA. CHS is an older format, which specifies the cylinder (track), head (surface), and sector. Modern drives use Logical Block Addressing (LBA), which is just a single number for each block. The analogy from lecture is that CHS is like a home address (with a number, street, and city), whereas LBA is like if every house had its own serial number.

Because seek time and rotational delay dominate the cost of a disk access, the order in which the OS services requests matters a lot. This is where disk scheduling comes in; a few scheduling algorithms were mentioned in the lecture and OSTEP.

• SSTF (Shortest Seek Time First): always pick the pending request closest to the current head position. Fast on average, but can starve requests that are far away.
• SCAN / C-SCAN (the elevator algorithm): sweep the head across the disk in one direction servicing requests along the way, then reverse. Fairer than SSTF and avoids starvation.
• SPTF (Shortest Positioning Time First): factors in both seek and rotation. Closer to optimal but requires the OS to know detailed disk geometry, so scheduling has largely moved into the drive itself.

The key idea is that the OS works with the hard drive to find the best algorithm, and modern drives increasingly use their own internal scheduling to approach the optimal result.

OSTEP 39: Files and Directories

This lecture introduced files and directories as the key abstractions for organizing data in a file system.

A file is simply a linear array of bytes that is associated with some low-level ID, like an inode number. The inode stores metadata about the file like permissions, size, and timestamps.

A directory is a special kind of file that contains a structured list of (name, inode) pairs. Listing a directory just reads the directory file and looks up the associated inodes.

A hard link is just another name that points to the same inode. This makes it so that a single file can appear to be multiple files. Removing one name does not delete the data as long as another name still points to the inode.

A symbolic link (symlink) points to a path rather than an inode. That difference matters: symlinks can cross file system boundaries, can point to directories, and can dangle (point to something that no longer exists). Hard links can do none of those things because they are tightly bound to the inode they reference on the same file system.

A partition is a raw slice of a physical disk, while a volume is a logical unit where a file system has been created. A logical volume can consist of a single partition or span multiple disks.

A mount attaches a file system into the operating system’s main directory tree, so its contents appear under some existing path.

OSTEP 40: File System Implementation

This chapter was split into two lectures covering the two main parts of a file system: the data structures used to store files, and the access methods used to interact with stored data.

Data structures

We walked through an example file system with 64 blocks to make the idea concrete. The superblock is the first block in the file system and holds some critical information: where inodes are stored, where data blocks start, how many inodes exist, and so on. The file system looks at the superblock first to understand its own layout.

A bitmap tracks which blocks are free and which are in use — one bit per block. To allocate a new block, the file system scans the bitmap, finds a free block, marks it as used, and gives it to the file. A similar bitmap tracks free inodes.

One way to understand a file system is that it is just a data structure laid out on disk. The same kinds of pointers and structures you might see in a memory-based data structure are written to disk blocks and linked together by block numbers instead of memory addresses. The OS reads the superblock to orient itself, then uses inode numbers and block pointers to navigate.

Access methods

The second half of the chapter walked through what actually happens on common syscalls. Three operations made the cost model clear:

• open(“/foo/bar”) is surprisingly expensive. The OS has to traverse the path one component at a time: read the root inode, read the root directory’s data block, find “foo”, read the foo inode, read its data block, find “bar”, read the bar inode. Every component potentially costs an inode read and a data block read.
• read() is cheaper on an already-open file. The OS already has the inode in memory, so it consults the inode’s block pointers, reads the right data block, and updates the file’s offset.
• write() can be the most expensive. If the write extends the file, the OS must consult the data bitmap to find a free block, update the bitmap, update the inode (new size, new block pointer), and then write the actual data: multiple I/Os for a single logical write.

What was most interesting is that every step in path traversal follows the same pattern: get an inode, read its data block, search for the next entry. There is no special logic for subdirectories because directories are just files. That made the whole traversal algorithm feel intuitive.

Reflection

This is the last section of the course, but there is still more to OSTEP that I may revisit to round out the picture. What changed for me is less the volume of facts and more how I think about software and its relationship to hardware.

Before this course, things like “the file system” or “memory” were opaque boxes, but now I’m able to think of them as data structures with access methods. A path lookup is not magic; it is a sequence of inode and block reads. A context switch is not magic; it is a saved set of registers and a scheduling decision.

The core problems that operating systems solve, like virtualization (abstraction), concurrency, and persistence, show up in many technical contexts. Knowing how things work at the OS level will help me to build a better intuitive understanding of these recurring problems, which should serve me well as I continue to develop my technical skillset.

This week we continued learning about concurrency, focusing on synchronization. We covered OSTEP 30, 31, and 32, as well as a technique for writing concurrent code called the Anderson/Dahlin method.

OSTEP 30: Condition Variables

This lecture started with an example of why locks alone are sometimes not enough. Locks either let a thread proceed or block it from executing, but have no way to communicate anything beyond “this resource is in use.” If a thread needs to be notified when some condition becomes true, another mechanism is needed.

Condition variables allow signaling between threads. A thread can go to sleep, and another thread can send a signal for it to wake up, or broadcast to wake up multiple threads. The lecture used a temperature monitor as an example: with a lock, another thread monitoring a temperature variable would have to repeatedly poll for changes, wasting CPU time. With a condition variable, it can go to sleep and wake up when the temperature variable changes.

Bounded Buffer Problem

This was a hands-on lecture walking through a thread-safe queue as an example of a bounded buffer. The bounded buffer problem involves a shared, limited storage area (a buffer), where multiple producer threads add data, while consumer threads remove data from it. There are a few problems that can arise with bounded buffers:

1. Buffer overflow: a producer thread can overflow the buffer by adding data when it is full
2. Buffer underflow: a consumer may try to remove data while the buffer is empty
3. Race conditions: threads may attempt to access the buffer at the same time, leading to indeterminate behavior

The demo showed how race conditions can lead to indeterminate behavior. When threads adding to the queue raced against threads trying to read from it, the output could include -1 (returned when the queue is full or empty) in different orders across runs. To prevent race conditions, threads can continually poll the queue to make sure that it isn’t full or empty, but this is inefficient, since the spinning thread will waste CPU time.

To make the queue more efficient, the condition variables is_not_empty and is_not_full were added, signaling to waiting threads when the queue is ready, so that they don’t need to spin and waste CPU.

Anderson/Dahlin Method

This lecture presented a repeatable process for turning a regular class into a concurrent, thread-safe class. The Anderson/Dahlin method is a five-step procedure that uses only locks and condition variables.

First, design the class as normal (without any concurrency), then add concurrency by following these steps:

1. Add a single lock
2. Use the lock around critical sections of the code
3. Add condition variables for situations where a thread will need to wait
4. Add signal and broadcast calls to coordinate threads
5. Add wait conditions within loops, so threads will sleep when the condition variable is false, then check it again when it wakes up

One thing to keep in mind is that state variable names should make the condition obvious. For example, can_push and can_pop make it clear when the push and pop methods can be used.

OSTEP 31: Semaphores

Semaphores are a synchronization primitive that combines the behavior of a lock and a condition variable. It’s based on an integer value, which supports two operations after initialization: increment (signal) and decrement (wait). The integer value of the semaphore represents how many “slots” are available for threads to run.

The initialization value of the semaphore matters. Setting a semaphore to 1 makes it behave like a mutex. Setting it to 0 makes the first wait block immediately, which is useful for ordering.

Threads can also use semaphores to “rendezvous”, so that both threads will wait until the other thread has reached a certain point before proceeding. This can be accomplished by initializing the semaphore to 0, then having the thread signal with one semaphore, while it waits on the semaphore that the other thread will use to signal.

Synchronization Barriers

This lecture introduced the concept of a synchronization barrier, which is like the rendezvous pattern mentioned above, but extended to many threads.

The example in the lecture used two semaphores and a shared counter to create a synchronization barrier:

• A mutex semaphore (initialized to 1) ensures that updates to the counter are atomic
• A barrier semaphore (initialized to 0) blocks all threads until the last one arrives
• A shared count varaible tracks how many threads have checked in

Each thread locks the mutex, increments count, then unlocks it so the next thread can update the counter. After that, the thread waits at the barrier. When the count is equal to the number of threads, that means it’s the last thread, so it uses the barrier semaphore to signal to the other threads that they can all proceed.

The synchronization barrier example made it clear how semaphores can act as both a lock and a condition variable. In the same piece of code, one semaphore acts as a mutex and the other acts as a gate that signals when it is safe to move forward.

Reflection

After reviewing the lectures and readings from this week, I feel like I have a better understanding of concurrency and the kinds of bugs that can appear in concurrent programs. The code examples were especially helpful, since they made the problems more concrete and showed how synchronization tools like condition variables and semaphores can solve common issues. The Anderson/Dahlin method was also helpful, since it provides a structured process for designing thread-safe code.

Looking ahead, next week focuses on persistence, which should pair well with our group project on the Google File System. For the project, I’ve been learning about the challenges involved in designing a distributed file system, so it will be helpful to compare it to the challenges that are involved with a traditional file system.

This week we switched gears from memory management to concurrency, covering OSTEP chapters 26, 27, 28, and 29.

OSTEP 26: Concurrency and Threads

Concurrency is an important topic for this course because the OS must handle simultaneous activities that can overlap or interfere with each other. For example, two separate processes may attempt to write to the same file at the same time, and the OS needs to be able to manage that somehow. Since concurrency is an issue that the OS has dealt with for a long time, operating systems have developed many techniques to manage concurrency.

One of those techniques is to use threads. A thread is similar to a separate instance of a process, except a multi-threaded program runs multiple threads inside the same process, giving the process multiple points of execution. Threads in a process share the same virtual address space with other threads, allowing threads to interact with each other and requiring less overhead than launching a new process. Each thread has its own execution context, which includes CPU registers and a call stack.

Threads introduce some benefits and drawbacks. One of the benefits is parallelism, which splits work across CPUs to improve performance. Another benefit is responsiveness, since separate threads can handle different tasks, which reduces blocking the program’s execution. Threads are useful when a process needs to handle multiple events simultaneously, while still allowing shared access to the same data.

One of the drawbacks of threads is that they can make a program’s execution indeterminate, since threads will not always execute in the same order. Even in a simple program, execution order can change across runs. A related issue introduced by threads is a race condition, which is a situation where multiple threads “race” to modify shared data. Code where shared data or resources are accessed is called a critical section, where race conditions can be an issue. Since the execution order of threads can vary, race conditions cause unpredictable behavior in programs.

OSTEP 27: Thread API

This chapter introduced the thread API in C. The pthread (POSIX thread) library offers several functions to manage concurrency with threads. A few of the important functions are:

• pthread_create creates a new thread
• pthread_join waits (blocking) until the specified thread completes, optionally capturing a pointer to its return value
• pthread_mutex_lock protects a critical section with a lock, blocking other threads from accessing it
• pthread_mutex_unlock releases control of the mutex so that other threads will be able to access it
• pthread_cond_wait puts a thread to sleep until it receives a signal
• pthread_cond_signal sends the signal to wake a sleeping thread

The main synchronization primitives covered in this course are locks and condition variables. Locks provide safety by preventing other threads from accessing critical sections of code, while condition variables enable coordination between threads through signaling.

OSTEP 28: Locks

Locks provide a mechanism to solve the race condition problem introduced by multiple threads, by allowing a thread to block other threads from accessing a shared resource (critical section) while the lock is held.

There are two main types of locks: spinning and blocking.

• Spinning locks cause a thread to repeatedly check if a lock is available, which is fast but wastes CPU
• Blocking locks cause a thread to go to sleep until the lock is released, which doesn’t waste CPU like a spinning lock, but requires more overhead to handle the context switch

The main goals of lock implementations are correctness, fairness, and performance.

• Correctness: does the lock actually provide mutual exclusion?
• Fairness: is there an orderly process for fulfilling lock requests?
• Performance: does the lock minimize overhead and maximize throughput?

Locks are designed to balance these goals using a combination of hardware support to ensure correctness, queues to provide fairness, and hybrid spinning/blocking strategies to maximize performance.

OSTEP 29: Lock-Based Concurrent Data Structures

The key idea with lock-based data structures is to make the data structure thread safe, so that multiple threads can use it and always produce the correct results. In general, this can be accomplished by integrating locks into the data structure around critical sections of the code, where shared data is modified.

When designing a lock-based data structure, a simple coarse-grained approach is usually a good starting point, where a single “big lock” can be placed around the entire data structure, which should produce a correct result. From there, a more fine-grained approach can be used, but more concurrency adds additional complexity and does not always improve performance.

Reflection

Concurrency is a practical topic that comes up a lot in programming, for example, in distributed systems, databases, and even a simple web server. It’s been helpful to learn more about it, since it’s an important topic to understand. We will continue to learn about concurrency in the next section of the course, and it looks like we’ll be working with threads more in the next programming assignment, which should be helpful.

This week we continued to learn about how the OS handles virtual memory. The lectures and readings got into the details of how the OS works with hardware to optimize performance and solve problems that arise when dealing with virtual memory, while the assignments helped with learning how the mechanisms involved work.

Topics covered this week

This week’s lectures covered OSTEP chapters 17, 19, 20, 21, and 22.

OSTEP 17: Free-Space Management

This chapter/lecture explained how the OS keeps track of free (unused) memory. The main design goals include the following:

• Correctness: in-use memory should never be corrupted, and free memory should actually be unused; this is the most important goal.
• Speed: memory allocation should be as fast as possible.
• Avoid memory overhead: minimize space used for metadata to maximize space for actual memory allocations.
• Satisfy as Many Requests as Possible: memory allocation should not fail and should not be a bottleneck.

To achieve these goals, the OS can choose from different allocation policies, like first fit, best fit, and worst fit.

• Best fit: finds the smallest chunk of free memory that fits.
• Worst fit: finds the largest chunk of free memory.
• First fit: finds the first chunk of free memory that will fit.

We also discussed two mechanisms, splitting and coalescing, that work together to reduce wasted memory space.

• Splitting breaks large blocks of memory into smaller ones when allocating, so that the free space isn’t wasted.
• Coalescing combines smaller blocks of adjacent free memory into larger blocks, so that it becomes contiguous free space.

Together, these mechanisms keep memory efficient and flexible.

OSTEP 19: Translation Lookaside Buffers (TLBs)

This chapter/lecture explained the TLB and why we need it. Paging involves an extra memory lookup, which makes it slow compared to accessing the memory directly. The TLB solves this problem by providing a hardware cache that returns cache hits in a single clock cycle.

The TLB uses the locality of memory access patterns to determine what is cached:

• Temporal locality: caching memory that was used recently.
• Spatial locality: caching memory addresses that are near recently used ones, since they are more likely to be accessed soon.

We also learned how the TLB performs an address translation:

1. Split virtual address (VA) into VPN and offset.
2. Check the TLB cache for the VPN → PFN mapping.
   • If there is a cache hit, use the PFN from the cache.
   • If there is a cache miss, get the PFN from the page table and cache it for the next translation.
3. Check if the memory access is valid.
4. Use PFN plus offset to form the physical address (PA).

OSTEP 20: Multi-Level Paging

This chapter/lecture introduced a problem with paging and its solution. Each process needs its own page table, and much of the address space for each process is not used, which leads to a lot of wasted memory. The solution is multi-level paging, which only allocates the memory that is necessary and stores an index of page table chunks in the page directory. Both the page directory index and page table index are included in the VPN.

This improves memory utilization, but requires an additional step to perform address translations. The TLB caches the PFN to speed up memory access, so only TLB cache misses will require the additional PD lookup step.

OSTEP 21-22: Swapping

This lecture covered chapters 21 & 22 in OSTEP, which describe the mechanisms and policies involved with swapping memory. Storage space in RAM is limited, so the OS must store some memory pages in secondary storage, which has a lot more space to work with.

Swapping introduces the present bit, which indicates whether a page is in memory, or if the OS must fetch the page from disk. The mechanics of swapping look like this:

1. Check TLB for VPN.
   • If VPN is in the TLB, return the PFN.
2. Otherwise, lookup the VPN in the page table.
3. Check if the present bit is set in the PTE.
   • If it is set, cache the PFN in the TLB and return the PFN.
   • If it is not set, raise a page fault.

The OS handles the page fault by fetching the page from disk and storing it in memory.

The OS needs a policy to determine which pages get swapped out when memory is full. There are a few different policies for this:

1. FIFO: evict the oldest page.
2. LRU: evict the least recently used page.
3. Random: select a random page to evict.
4. Optimal (Belady): evict the page that is used furthest in the future.

The Optimal (Belady) strategy is not achievable in practice, since we can’t know the future, but it can be helpful for comparison when benchmarking.

There were two metrics described that are useful for benchmarking:

1. Cache hit rate: the percentage of requests that result in cache hits. Calculated as (hits / total requests) where total requests can include or exclude compulsory misses, when the page is first requested.
2. Average Memory Access Time (AMAT): the average time to access a page in memory, considering cache hits and misses. Calculated as (hit rate * memory access time) + (miss rate * disk access time).

Reflection

After reviewing the course material for this week and the previous week (which also covered virtual memory), I’m feeling like I have a better handle on the topic. Looking ahead, next week we’re going to learn about concurrency, which should be an interesting shift from memory management into how the OS can do multiple things at the same time.

Concurrency in programming is something that I’m familiar with, but haven’t learned about in detail, so it will be interesting to find out how it’s handled at the OS level. I know that some programming languages support multithreading, while others do not, so it will be a good opportunity to explore this topic more.