tenta Flashcards
What is a data race and how does it differ from a race condition?
- A data race occurs when two or more threads access the same shared variable concurrently, at least one thread writes, and there is no proper synchronization.
– A race condition is a broader concept where the outcome of a program depends on the timing or interleaving of threads (it may or may not involve a data race).
What is a monitor and what two main components does it combine?
A monitor is a high-level synchronization construct that combines:
– Mutual exclusion: Only one thread can execute a monitor’s procedure at a time.
– Condition variables: Allow threads to wait and be signaled (using wait/signal operations) for certain conditions to become true.
Describe Peterson’s algorithm for two threads.
Peterson’s algorithm uses two boolean flags and a turn variable. Each thread sets its flag and assigns turn to the other thread before entering the critical section. This guarantees mutual exclusion, progress, and bounded waiting for two threads.
What are the four necessary conditions for deadlock?
- Mutual Exclusion: Only one thread can use a resource at a time.
- Hold and Wait: A thread holding at least one resource is waiting to acquire additional resources held by others.
- No Preemption: Resources cannot be forcibly removed from threads once allocated.
- Circular Wait: A circular chain of threads exists, each waiting for a resource held by the next.
What is the dining philosophers problem and name one common strategy to avoid deadlock in its solution.
It’s a classic concurrency problem where philosophers must pick up two forks (resources) to eat, leading to potential deadlock if every philosopher holds one fork. A common strategy is to impose an ordering (or use a global lock) so that at least one philosopher picks up both forks only if both are available, breaking the circular wait.
Explain the producer–consumer problem.
It is a synchronization problem where producers generate items and place them in a bounded buffer while consumers remove items. The challenge is to coordinate these actions so that producers wait when the buffer is full and consumers wait when it is empty. Solutions often use semaphores, monitors, or condition variables.
What is a semaphore, and what is the difference between a binary and a counting semaphore?
A semaphore is a synchronization primitive that uses a counter to control access to resources.
– A binary semaphore has a capacity of 1 (similar to a lock).
– A counting semaphore has a capacity greater than 1, allowing a fixed number of concurrent accesses.
What is a barrier and what property must it guarantee?
A barrier is a synchronization mechanism that forces threads to wait until all have reached a certain point before any proceed. It must guarantee that no thread continues until the predetermined number of threads have arrived (ensuring coordinated progress without deadlock or starvation).
Define lock-free data structures and explain the role of compare-and-swap (CAS).
Lock-free data structures allow multiple threads to operate on shared data without using traditional locks, reducing contention. The CAS operation is an atomic primitive that updates a value only if it matches an expected value, helping to safely perform concurrent updates without locks.
What is the Fork/Join framework in Java, and when is it typically used?
The Fork/Join framework is used for parallel recursive algorithms (divide-and-conquer). It works by recursively breaking tasks into smaller subtasks, forking them, and then joining their results. It is particularly useful for problems where tasks can be executed concurrently on multiple cores.
What is Amdahl’s Law and what does it tell you about the limits of parallel speedup?
Amdahl’s Law states that if a fraction 𝑝 of a program is parallelizable and the remaining (1-p) is sequential, then the maximum speedup with 𝑛 processors is given by:
speedup = 1/((1-p) + p/n)
As 𝑛 approaches infinity, the maximum speedup approaches
1/(1-p)
What is Software Transactional Memory (STM) and its main benefit?
STM is a concurrency control mechanism where code is executed in transactions that appear atomic. It helps avoid common pitfalls of lock-based programming by allowing automatic rollback and retries when conflicts occur, thereby simplifying concurrent programming.
How can you implement a token ring protocol in Erlang?
In a token ring protocol, processes are arranged in a circle. Each process (token body) waits for a message (the token), performs its action (e.g., printing a number), and then sends the token to the next process. The ring is closed by linking the last process to the first.
What is fine-grained locking and what advantage does it offer over coarse-grained locking?
Fine-grained locking involves locking only a small part of a data structure (e.g., individual nodes in a linked list) rather than the entire structure. This allows for higher concurrency because multiple threads can operate on different parts of the structure simultaneously, reducing contention.
Describe the difference between signal-and-wait and signal-and-continue in monitors.
– Signal-and-wait: The signaling thread relinquishes the monitor immediately and waits until the signaled thread takes over the monitor.
– Signal-and-continue: The signaling thread continues executing its critical section while the waiting thread is simply awakened and waits for its turn.
What are the challenges in implementing a concurrent queue?
Challenges include:
– Ensuring that concurrent enqueue and dequeue operations do not corrupt the internal structure.
– Avoiding data races and ensuring visibility between threads.
– Balancing performance (using lock-free or fine-grained locking techniques) with correctness.
Why are volatile variables used in concurrent programming (e.g., in Java)?
Declaring a variable as volatile ensures that reads and writes are directly made to main memory, so changes by one thread become immediately visible to other threads. This is crucial for avoiding stale data in concurrent algorithms.
What synchronization mechanism would you add to a non-deterministic counter increment program to guarantee a final value (e.g., counter=10) regardless of thread interleaving?
You can enforce the intended behavior by using a lock (or monitor) around the read–modify–write sequence, ensuring that only one thread increments the counter at a time. Alternatively, atomic operations (like Java’s AtomicInteger.incrementAndGet()) could be used.
What is the purpose of a barrier with a manager in concurrent programming?
A barrier forces threads to wait until a required number have reached the barrier before any can proceed. A manager (or coordinator) can be used to release all waiting threads once the barrier condition is met, ensuring coordinated progress without deadlock or starvation.
What role does lazy evaluation play in concurrent algorithms that use compound conditions?
Lazy evaluation allows a compound condition (e.g., in a loop waiting on a condition) to stop evaluating further terms if an earlier condition is false. This can prevent unnecessary execution of costly operations (like CAS), and it can also help avoid side effects in concurrent loops.
