Concurrency primitives are tools that let programs handle multiple tasks that may run at the same time. This reference covers execution models, synchronization tools, and common hazards that appear in multithreaded and multiprocess programs. Students need these ideas to understand operating systems, servers, simulations, games, and modern applications.
The sheet is designed as a fast reference for reading code, writing pseudocode, and debugging shared-state problems.
The core idea is that concurrent code must control when tasks run and how they access shared data. Threads and processes describe how work is executed, while locks, semaphores, barriers, and condition variables help coordinate that work. Key hazards include race conditions, deadlock, starvation, and missed signals.
Classic patterns such as producer-consumer and readers-writers show how primitives are combined safely.
Key Facts
- A process has its own memory space, while threads in the same process share memory and must coordinate access to shared data.
- A race condition happens when program output depends on unpredictable timing, especially when two tasks read and write the same variable without synchronization.
- A critical section is code that accesses shared data and should be protected so only one thread can execute it at a time.
- A mutex lock follows the rule acquire(lock) before the critical section and release(lock) after the critical section.
- A semaphore stores an integer count and uses wait(S) to decrement or block when S = 0, and signal(S) to increment and possibly wake a waiting task.
- A condition variable is used with a lock, and the usual rule is while condition is false: wait(cv, lock), then proceed when the condition is true.
- Deadlock can occur when mutual exclusion, hold and wait, no preemption, and circular wait all happen at the same time.
- A barrier makes each thread wait until all participating threads reach the same point before any of them continue.
Vocabulary
- Thread
- A thread is a path of execution inside a process that can run concurrently with other threads and share the same memory.
- Process
- A process is a running program with its own memory, resources, and execution state.
- Mutex
- A mutex is a lock that allows only one thread at a time to enter a protected critical section.
- Semaphore
- A semaphore is a synchronization primitive that uses a counter to control access to a limited number of resources.
- Condition Variable
- A condition variable lets a thread sleep until another thread signals that a required condition may now be true.
- Deadlock
- Deadlock is a state where tasks are permanently blocked because each is waiting for a resource held by another task.
Common Mistakes to Avoid
- Forgetting to release a lock is wrong because other threads may block forever waiting to enter the critical section.
- Using if instead of while around a condition variable wait is wrong because a thread can wake up even when the condition is still false.
- Locking shared data only during writes is wrong because reads can also observe partially updated or inconsistent state.
- Acquiring multiple locks in different orders is wrong because it can create circular wait and cause deadlock.
- Assuming sleep fixes a race condition is wrong because timing delays do not guarantee safe ordering between concurrent tasks.
Practice Questions
- 1 Two threads each execute count = count + 1 one time, starting from count = 0, without a lock. What final values are possible, and why?
- 2 A semaphore starts with S = 3. Five threads call wait(S), and none has called signal(S) yet. How many threads can pass immediately, and how many block?
- 3 Thread A locks L1 then L2. Thread B locks L2 then L1. Explain how this can lead to deadlock.
- 4 Why is a condition variable usually checked with while condition is false instead of if condition is false?