CST 334 – Week 5: Concurrency

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.