3 Synchronization
Week 3 & 4: September 12 - 23, 2022
On Synchronization Primitives
- DINOS Chapter 6
- LOVE Chapter 9, Pgs 203-206
On Deadlocks
- DINOS Chapter 8
On Multi-threading vs. Event Processing
- Why Threads are Bad? Slides by Ousterhoust
- Why Events are Bad? by von Behren, Condit & Brewer
- They really are the same! by Lauer & Needham
- LOVE Chapter 10
- Birell Threads especially to get a sense of Condition Variables and why multi-threading is useful.
Super-Optional Readings — Not really an OS concept, more a PL one
- Language Unification of Events & Threads by Li and Zdancewic
As we have alluded to in the past lectures, there can be multiple “kernel” threads (e.g. threads executing a system call in kernel mode in process-context) currently executing within the one and only shared kernel space. These threads can accessing and manipulating shared variables or data structures. For example, two processes execute a fork() system call to create new processes and they need to get a new process id but they end up accessing a global variable to find the next available process id at exactly the same time, each ending up with the same id! How can this possibly happen?
Modern kernels are reentrant — multiple threads can be executing the same code pade at the same time), preemptible — a kernel thread can be preempted by the kernel scheduler in favor of another thread, interruptible — an interrupt can interrupt a currently executing kernel thread. All that means is that you can’t guarantee that the variables or data structures that a thread accesses and modifies don’t change while it is executing by other threads! Symmetric multi-processing (SMP) means that you can have different processors each executing different threads but still all these threads are sharing the same address space.
So how can you write a kernel (or any code) that is interrupt-safe, preempt-safe and SMP-safe? How can you write code that allows for concurrent access to shared data?
We will learn about different synchronization methods in this unit and what hardware support we can rely on to build synchronization primitives like locks? How kernels can expand locking primitives to semaphores that combine locking with waiting?
3.1 A video summary
3.1.4 Multithreading vs. Event-driven Programming
At the end of the class, you collectively worked on summarizing the three papers related to this topic. You can find the class notes here. Excellent Job!
Learning Objectives
- What are race conditions? What are possible consequences?
- When would you use a spin lock vs a mutex (blocking lock) or semaphore?
- Can the underlying architecture (uni-processor, multiprocessor, support for certain instructions, etc.) affect your synchronization choice? If so how?
- How can mutexes, semaphores, monitors and condition variables be used to solve different critical section problems?
- What is the producer/consumer problem?
- What is the main idea behind the Banker’s algorithm in terms of maximizing concurrency and resource allocation?
- What are deadlocks and how can they occur?
- Describe Coffman’s 4 conditions for a deadlock.
- Apply the 4 conditions to assess if there is a deadlock to different problems like the Dining Philosophers.
- What is the intuition behind deadlock detection algorithms, what are they looking for?
- Describe a deadlock elimination, avoidance or prevention technique in relation to the four conditions.
- Define the related concepts of starvation and priority inversion?
- Explain how a naive algorithm for the dining philosopher’s problem may eliminate/avoid deadlocks but still cause starvation? What is the intuition behind the textbook solution to the problem?
- Describe the differences between the multithreading and event-driven programming design paradigms.
- What operating contexts lead the opposing authors (see papers assigned above) to favor one paradigm over another even though both paradigms are essentially duals?
Beyond OS
- Can you find example of contemporary applications/services designed in one paradigm? What are the design arguments used to favor their design choice?
Problem-Solving
Can you correctly use synchronization primitives to solve different concurrency problems? Here are some midterm-style synchronization questions:
- Breathing: 2 Oxygen threads combine with 1 Carbon when we breath to form carbon dioxide. Create an oxygen and carbon thread that wait around until there is enough oxgyen and carbon for the energizing combination to occur!
- London-bridge is falling down: A bridge can only hold \(x\) cars traveling in the same direction. Any more than \(x\) it will collapse. Create an arrive-bridge(int direction) and an exit-bridge() that lets car threads wait on semaphores or CVs until it is safe for them to cross based on the direction they are heading and release the locks correctly on exit.