Multithreading Flashcards
What are the advantages and disadvantages of using processes for concurrency?
○ Advantages:
■ Provide memory separation, meaning no shared data
■ if one process crashes, others are unaffected
○ Disadvantages:
■High communication overheads
■Expensive context switching (information not from provided sources)
What are the advantages and disadvantages of using threads for concurrency?
○ Advantages:
■ Threads within the same process share an address space
■ Suitable for tighter integration
○ Disadvantages:
■If one thread crashes, the entire process crashes, including other threads
What are data races?
Data races occur when multiple threads access and modify shared data simultaneously without proper synchronization mechanisms like locks or semaphores. This can lead to unpredictable and incorrect program behavior as the final result depends on the unpredictable timing of thread execution
What is the basic approach to multithreading?
1.Divide the “work” among multiple threads. For example, give each thread an equal number of iterations in a loop.
2.Identify and manage shared data.
■Shared data: Global variables and heap data are shared.
■Not shared data: Local variables and read-only variables are not shared.
■Protect access to shared data within critical sections using synchronization mechanisms like mutexes to prevent data races
What are the two approaches to improve performance when a single lock inhibits parallelism in multithreaded code?
○ Fine-grain locking: Use multiple locks on individual pieces of shared data, allowing for more concurrency as different threads can acquire locks for different data simultaneously.
○ Privatization: Make shared data accesses into private data accesses.
■Create local variables within each thread to represent its portion of the shared data.
■Perform operations on these local variables, avoiding the need for locks during these computations.
■Finally, update the shared data only once after the loop, using a lock to protect this final update
What is the producer-consumer problem in multithreading?
○ The producer-consumer problem occurs when two or more threads communicate, with some threads producing data (“producers”) and others consuming that data (“consumers”).
○ They share a bounded buffer, a fixed-size queue or circular buffer, to store the produced data before it’s consumed.
○ Challenges:
■Ensure that producers don’t add data to a full buffer.
■Ensure that consumers don’t try to consume data from an empty buffer.
■Guarantee mutually exclusive access to the buffer to prevent data races
How are semaphores used to solve the producer-consumer problem?
Semaphores, acting as signaling mechanisms, help synchronize producers and consumers. In this context, two semaphores are commonly used:
○ emptyBuffer: Initialized to N (buffer size), indicating the number of empty slots in the buffer. Producers decrement it before adding data and consumers increment it after consuming data.
○ fullBuffer: Initialized to 0, representing the number of full slots in the buffer. Producers increment it after adding data and consumers decrement it before consuming data
What are the common issues and pitfalls when implementing the producer-consumer problem with semaphores, and how are they addressed?
○ Issue 1: Incorrect Buffer Index Management: If producers and consumers use shared indices (like i and j in the source examples) to access the buffer, it can lead to race conditions and incorrect data access.
■ Solution: Use thread-local variables (myi, myj) to track buffer indices and ensure that each producer/consumer grabs a unique empty/full element.
○ Issue 2: Missing Mutual Exclusion within findempty/findfull: If the logic to find an empty or full slot in the buffer (findempty, findfull) isn’t protected by a mutex, multiple producers/consumers might try to access the same buffer slot simultaneously.
■ Solution: Introduce a mutex to ensure that only one thread at a time can search for an empty/full slot.
○ Issue 3: Potential Deadlock with Mutex Placement: If the mutex is acquired before waiting on the semaphore (emptyBuffer or fullBuffer), it can lead to a deadlock situation where a thread holds the mutex while waiting, preventing others from proceeding.
■ Solution: Place the mutex acquisition after the wait on the semaphore to avoid this deadlock
Why are condition variables used in multithreaded programs, and how do they work?
Condition variables provide a way for threads to wait for specific conditions to become true before proceeding, synchronizing their execution based on shared state.
○ Waiting on a Condition: pthread_cond_wait(cond, mutex)
■ A thread calls pthread_cond_wait() to wait for a signal on a condition variable (cond).
■ It must hold the associated mutex (mutex) before calling pthread_cond_wait().
■ The call atomically releases the mutex and puts the thread to sleep, waiting for the condition to be signaled.
■ When awoken by a signal, the thread re-acquires the mutex before returning from pthread_cond_wait().
○ Signaling a Condition: pthread_cond_signal(cond, mutex) and pthread_cond_broadcast(cond, mutex)
■ pthread_cond_signal() wakes up a single thread that is waiting on the condition variable.
■ pthread_cond_broadcast() wakes up all threads waiting on the condition variable.
■ Important: The mutex must be held by the signaling thread when calling pthread_cond_signal() or pthread_cond_broadcast().
What is Peterson’s Algorithm and what are its key properties for synchronization?
Peterson’s Algorithm is a classic software-based solution for mutual exclusion, ensuring that only one process (or thread) can enter its critical section at a time. It uses two shared variables:
○ Flags: Each process has a flag indicating its intent to enter the critical section.
○ Turn: A turn variable determines whose turn it is to enter the critical section.
● Key Properties:
○ Mutual Exclusion: Guaranteed because a process enters the critical section only if its flag is set and either the other process’s flag is not set or the turn variable indicates its turn.
○ Progress: Ensured because a process outside the critical section cannot prevent another process from entering, and the turn variable ensures fair access to the critical section.
○ Bounded Waiting: A process will not wait indefinitely to enter the critical section as the turn variable provides a fair mechanism for access
