Shared Memory Programming Flashcards
pragma omp parallel
Use the parallel directive to start multiple threads.
pragma omp critical
Protect sections using critical to ensure only one thread executes a block at a time.
pragma omp atomic
For operations that can be performed atomically to improve efficiency.
omp_lock_t lock;
omp_init_lock(&lock);
#pragma omp parallel
{
omp_set_lock(&lock);
// Critical section
omp_unset_lock(&lock);
}
omp_destroy_lock(&lock);
Manage access to critical sections more explicitly with locks.
pragma omp parallel for
Divide loop iterations among threads, avoiding loop-carried dependencies.
pragma omp parallel for private(x) shared(y)
Explicitly declare variable scope to avoid unintended data sharing.
pragma omp parallel for reduction(+:sum)
Parallelize reduction operations efficiently.
pragma omp barrier
Synchronize all threads at a certain point.
A structured parallel region
- One point of entry: Execution can only start at the beginning of the block.
- One point of exit: Execution leaves the block at one specific point, ensuring a clear and predictable flow of control.
- Limited branching: The only allowed branching out of the structured block is through an
exit() call or reaching the end of the block.
pragma omp parallel default(private)
By default, variables declared before a parallel block have shared scope among all threads, unless specified otherwise. However, you can change this default behavior using the default clause.
pragma omp parallel for schedule(static, 1)
Distributes the iterations in a round-robin fashion among the threads.
pragma omp parallel for schedule(dynamic, 3)
Iterations are divided into chunks. When a thread finishes its chunk, it requests another, continuing until all iterations are completed.
pragma omp parallel for schedule(guided, 2)
Similar to dynamic, but the chunk size decreases as threads complete their tasks. This can lead to more efficient utilization of threads towards the end of the task list.
pragma omp parallel for schedule(runtime)
export OMP_SCHEDULE=”dynamic,4”
The scheduling strategy is determined at runtime based on the OMP_SCHEDULE environment
variable. This allows flexibility as the same code can use different scheduling by just changing an environment variable.
pragma omp task
Tasks are created within a single execution block to ensure that only one thread is involved in task creation, avoiding unnecessary duplication of work.
Deadlocks
A situation where a set of processes is blocked, each waiting for an event that only another process in the set can cause
Conditions for Deadlock
- Mutual Exclusion: Only one process can use a resource at any given time.
- Hold and Wait: A process holding at least one resource is waiting to acquire additional
resources held by other processes. - No Preemption: A resource can be released only voluntarily by the process holding it.
- Circular Wait: There exists a set of processes {P1, P2, …, Pn} such that P1 is waiting for
a resource held by P2, P2 is waiting for a resource held by P3, and so on until Pn is waiting for a resource held by P1.
Deadlock Prevention
- Eliminate Mutual Exclusion (not always possible).
- Avoid Hold and Wait by requiring processes to request all needed resources at once.
- Preempt resources when needed.
- Prevent Circular Wait by imposing a total ordering of resource types.
Deadlock Avoidance
- Banker’s Algorithm
- Safe State Algorithm
- Resource Ready Algorithm
Deadlock Detection
- Search for cycles in resource-allocation graph
- If single, transform RAG into wait-for graph
- If not, then use the Banker’s
Recovery from Deadlock
- Process Termination: Abort all deadlocked processes or abort them one at a time until
the deadlock cycle is broken. - Resource Preemption: Take a resource from some other process and give it to another.
- Selection and Rollback: Choose a “victim” to roll back (undo the process to a safe state) to break the deadlock, considering factors like the number of resources the process has consumed and the time the process has consumed resources.
- Starvation: Ensuring that the same process is not always chosen as the victim during recovery from deadlock, to prevent it from being starved of resources.
TestAndSet()
An atomic operation used to set a target boolean variable to TRUE
and return its previous value.
Swap()
An atomic operation that exchanges the values of two boolean variables.
Sephamore
- Used like a lock, initialized to 1.
- wait(S) : Decrements the semaphore if it’s positive, otherwise waits until it becomes positive.
- signal(S) : Increments the semaphore, potentially unblocking a waiting thread. Solution: