Concurrency & Multithreading - Locks, Semaphores & Deadlocks Flashcards

Question 1

Distinguish between Concurrency and Parallelism.

Accepted Answer

**Concurrency** is about dealing with many things at once (managing multiple tasks over time, potentially interleaved on a single core). **Parallelism** is about doing many things at once (executing multiple tasks simultaneously on multiple cores or processors). Concurrency is a property of the *design*, while parallelism is a property of the *execution*.

Question 2

What does it mean for code to be "thread-safe"?

Accepted Answer

Code is **thread-safe** if it behaves correctly when executed concurrently by multiple threads. This typically means protecting shared mutable state from race conditions and ensuring data integrity through synchronization mechanisms.

Question 3

Explain what a "race condition" is.

Accepted Answer

A **race condition** occurs when the correctness of a program depends on the relative timing or interleaving of operations by multiple concurrent threads. It typically arises when multiple threads access and modify shared data without proper synchronization, leading to unpredictable or incorrect results.

Question 4

What is a "data race," and how does it differ from a "race condition"?

Accepted Answer

A **data race** is a specific type of race condition where two or more threads concurrently access the same memory location, and at least one of the accesses is a write, and there is no synchronization to order these accesses. A data race is a *sufficient* condition for a race condition, but not all race conditions are data races (e.g., a race condition could involve ordering of events without direct shared memory access conflict).

Question 5

Define a "critical section" in concurrent programming.

Accepted Answer

A **critical section** is a segment of code that accesses shared resources (data structures, variables, I/O devices) and must not be concurrently executed by more than one thread. It requires mutual exclusion to ensure data integrity.

Question 6

What is the principle of "mutual exclusion"?

Accepted Answer

**Mutual exclusion** is a property of concurrency control, which states that no two concurrent processes or threads can be in their critical section at the same time. It's a fundamental requirement for preventing race conditions when accessing shared resources.

Question 7

Explain what a "mutex" is and how it's used.

Accepted Answer

A **mutex** (mutual exclusion lock) is a synchronization primitive that grants exclusive access to a shared resource. Only one thread can acquire the mutex at a time. Threads call `mutex.lock()` to acquire it and `mutex.unlock()` to release it. If a mutex is already locked, subsequent `lock()` calls will block until it's released.

Question 8

Describe a "counting semaphore" and its primary operations.

Accepted Answer

A **counting semaphore** is a synchronization primitive that controls access to a resource with a limited number of instances. It maintains an internal counter, initialized to the number of available resources. Its primary operations are:
*   `wait()` (or `P()`): Decrements the counter. If the counter becomes negative, the thread blocks until `signal()` is called.
*   `signal()` (or `V()`): Increments the counter. If there are blocked threads, one is unblocked.

Question 9

What is a "binary semaphore," and how does it relate to a mutex?

Accepted Answer

A **binary semaphore** is a semaphore whose counter can only be 0 or 1. It functions identically to a mutex: `wait()` acquires the lock (if available), and `signal()` releases it. While functionally similar, mutexes are typically designed for ownership (the thread that locks must unlock), whereas semaphores don't enforce ownership.

Question 10

Compare and contrast mutexes and counting semaphores, including their typical use cases.

Accepted Answer

*   **Mutex:** Provides *exclusive access* to a single shared resource. It's typically used for protecting critical sections. Only the thread that acquires the mutex can release it (ownership).
*   **Counting Semaphore:** Controls access to a pool of *N identical resources*. It's used to limit the number of concurrent users of a resource. Any thread can signal a semaphore, not just the one that waited on it (no ownership).
*   A binary semaphore is functionally equivalent to a mutex but often lacks the ownership semantics and error checking of a mutex.

Question 11

Define "deadlock" in the context of concurrent systems.

Accepted Answer

A **deadlock** is a situation where two or more competing actions are waiting for each other to finish, and thus neither ever finishes. In concurrent programming, it occurs when two or more threads are blocked indefinitely, each waiting for a resource held by another thread in the cycle.

Question 12

List and briefly explain the four Coffman conditions necessary for a deadlock to occur.

Accepted Answer

For a deadlock to occur, all four of the following conditions must hold simultaneously:
1.  **Mutual Exclusion:** At least one resource must be held in a non-sharable mode (only one thread can use it at a time).
2.  **Hold and Wait:** A thread holding at least one resource is waiting to acquire additional resources held by other threads.
3.  **No Preemption:** Resources cannot be forcibly taken from a thread; they must be voluntarily released by the thread holding them.
4.  **Circular Wait:** A set of threads $T_1, T_2, \dots, T_n$ exists such that $T_1$ is waiting for a resource held by $T_2$, $T_2$ is waiting for a resource held by $T_3$, ..., $T_{n-1}$ is waiting for a resource held by $T_n$, and $T_n$ is waiting for a resource held by $T_1$.

Question 13

How can the "Mutual Exclusion" condition be addressed to prevent deadlocks?

Accepted Answer

The Mutual Exclusion condition can be addressed by making resources sharable where possible (e.g., read-only data). However, for inherently non-sharable resources (like a printer or a writeable data structure), this condition cannot be entirely eliminated, and other prevention techniques must be applied.

Question 14

How can the "Hold and Wait" condition be addressed to prevent deadlocks?

Accepted Answer

To prevent "Hold and Wait," threads must either:
1.  Request and acquire all necessary resources at once before starting execution.
2.  Release all currently held resources before requesting new ones.
Both approaches can lead to reduced resource utilization or starvation.

Question 15

How can the "No Preemption" condition be addressed to prevent deadlocks?

Accepted Answer

To prevent "No Preemption," if a thread holding some resources requests another resource that cannot be immediately allocated, all resources currently held by that thread are preempted (released). The thread then restarts, attempting to acquire all its needed resources again. This is complex to implement and can be inefficient.

Question 16

How can the "Circular Wait" condition be addressed to prevent deadlocks?

Accepted Answer

To prevent "Circular Wait," impose a total ordering of all resource types. Threads must request resources in increasing order of enumeration. For example, if resources are $R_1, R_2, R_3$, a thread holding $R_2$ cannot request $R_1$. This breaks the possibility of a circular dependency.

Question 17

What is a "livelock," and how does it differ from a deadlock?

Accepted Answer

A **livelock** is a situation where two or more threads are actively changing their state in response to each other, but none of them make progress. Unlike a deadlock, where threads are blocked, in a livelock, threads are continuously executing instructions but are stuck in a loop of reactions, preventing any useful work from being done.

Question 18

Define "starvation" in concurrent programming.

Accepted Answer

**Starvation** occurs when a thread is repeatedly denied access to a shared resource or CPU time, even though the resource or CPU becomes available. This can happen due to unfair scheduling, low priority, or continuous contention, leading to the thread never completing its task.

Question 19

Explain the "Compare-And-Swap (CAS)" atomic operation and its significance.

Accepted Answer

**Compare-And-Swap (CAS)** is an atomic CPU instruction that takes three operands: a memory location `V`, an expected old value `A`, and a new value `B`. It atomically updates `V` to `B` *only if* the current value of `V` is equal to `A`. It returns `true` if the swap occurred, `false` otherwise. CAS is fundamental for implementing lock-free data structures.

Question 20

What are "lock-free data structures," and how does CAS enable them?

Accepted Answer

**Lock-free data structures** are concurrent data structures that guarantee system-wide progress, meaning at least one thread will always make progress, even if other threads are arbitrarily delayed. They avoid traditional locks (mutexes, semaphores) and instead rely on atomic operations like `Compare-And-Swap (CAS)` to manage concurrent access and modifications, preventing deadlocks and reducing contention.

Question 21

What are "atomic operations" and why are they crucial in concurrent programming?

Accepted Answer

An **atomic operation** is an operation that is guaranteed to complete entirely without interruption or to fail entirely, appearing as a single, indivisible operation to the rest of the system. They are crucial because they prevent partial updates or inconsistent states when multiple threads access shared data, forming the building blocks for higher-level synchronization primitives and lock-free algorithms.

Question 22

Describe a "thread pool" and its advantages.

Accepted Answer

A **thread pool** is a collection of pre-initialized, idle threads that are available to execute tasks. When a task needs to be performed, it's submitted to the pool, and one of the available threads picks it up.
*   **Advantages:** Reduces overhead of creating/destroying threads, limits the number of concurrent threads (preventing resource exhaustion), improves responsiveness by having threads ready, and allows for better resource management.

Question 23

Explain the purpose of a "condition variable" and its main operations.

Accepted Answer

A **condition variable** is a synchronization primitive used with a mutex to allow threads to wait until a particular condition becomes true. It enables threads to efficiently yield the CPU while waiting for a condition.
*   `wait(mutex)`: Atomically unlocks the mutex and blocks the calling thread until another thread signals the condition variable. Re-locks the mutex before returning.
*   `signal()`: Wakes up one waiting thread.
*   `broadcast()`: Wakes up all waiting threads.

Question 24

What is a "reader-writer lock" and when is it useful?

Accepted Answer

A **reader-writer lock** (or shared-exclusive lock) is a synchronization primitive that allows multiple "reader" threads to access a shared resource concurrently, but only one "writer" thread can access it at a time. If a writer is active, no readers can access it. It's useful for scenarios where reads are much more frequent than writes, improving concurrency compared to a simple mutex.

Question 25

What is a "memory barrier" (or "memory fence") and why is it needed?

Accepted Answer

A **memory barrier** (or fence) is a type of instruction that enforces an ordering constraint on memory operations. It ensures that memory operations issued *before* the barrier are completed before memory operations issued *after* the barrier begin, preventing compiler and CPU reordering optimizations that could lead to incorrect behavior in multi-threaded programs.

Concurrency & Multithreading - Locks, Semaphores & Deadlocks

Cards in this deck

Related Flashcard Sets

TypeScript - Advanced Type Systems, Generics & Design Patterns

Harvard ECON1011 - Intermediate Microeconomics: Game Theory & Market Structures

MIT 18.03 - Differential Equations: Ordinary Differential Equations, Laplace & Fourier

CPA Exam FAR - Financial Accounting & Reporting: US GAAP & Revenue Recognition