Multithreading Flashcards
Spurious wakeups
When multiple threads are waiting on a single condition for different reasons and when a thread is woken up for a condition that does not apply
Extra cost is spent on the thread scheduler that could be avoided
Broadcast
Awakens all blocked threads waiting. Useful for 2 reasons:
- to simplify the program even though you know not all threads will make progress
- awakening multiple threads is useful because the resource that unlocked can be used by multiple threads
Deadlocks
Occurs when thread tries to lock a mutex that it already holds and locked or when another thread is locked on that mutex and blocked on the mutex this thread has locked.
Can also occur when using condition variables. Solution for both multiple mutexes or condition variables is same (p 20 Birrell example)
How to avoid deadlocks
Apply partial order of the threads that lock multiple shared resources. For any pair of mutexes, each thread will hold the two mutexes in the same order. Lock mutex A, then lock mutex B, WHILE condition var, then unlock B, then A
What can cause poor performance through lock conflicts
When the granularity is too large for the task and a mutex locks on an object with multiple parts that can be used for different purposes.
Solution is to use different mutexes for different parts of the object
Spurious lock conflicts
Occurs when conditional signaling occurs within the critical section. Solution is to unlock mutex first, then conditional signal
Thread starvation
Normally all threads are created equal and operate in first-in first-out rule. But when a thread never makes progress, this is referred to starvation. Example starving a writer when readers monopolize resource
Solution: programmer adds IF statement of readers to check if number of writers >0, then WAIT
Pipelining
multithreading structure in which the task of the program gets partitioned into subtasks and a thread is dedicated to each subtask
The total number of subtasks equals the number of threads
The number of partitions is the number of shared resources
“Problems” of pipelining - needed to separate subtasks such that each subtask takes about the same amount of time AND the number of stages (subtasks) statically determines the amount of concurrency
Performance parameters of multithreading
What’s cost of creating a thread?
Cost of keeping a blocked thread in existence?
Cost of a LOCK clause when the mutex is not locked?
Cost of a context switch?
What can degrade performance in multithreading?
Running more threads than there are processors
Creating and terminating threads aren’t cheap
Best thing to know is the smallest computation for which it is still profitable to fork a thread
Why use ALERT for multithreading?
if there are several algorithms to solve the same problem. If one completes, the others should be terminated. Use ALERT. Most useful when don’t know exactly what’s going on and thread could be blocked in several places.
But using ALERTs are “intrusive” and by nature less well-structured. It’s harder to verify correctness of the code and ALERTs should only be used on a forked thread
What is suggested alternative to ALERTs?
set a Boolean flag and signal a condition variable