Shared Memory Programming

Question 1

pragma omp parallel

Answer 1

Use the parallel directive to start multiple threads.

Question 2

pragma omp critical

Answer 2

Protect sections using critical to ensure only one thread executes a block at a time.

Question 3

pragma omp atomic

Answer 3

For operations that can be performed atomically to improve efficiency.

Question 4

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);

Answer 4

Manage access to critical sections more explicitly with locks.

Question 5

pragma omp parallel for

Answer 5

Divide loop iterations among threads, avoiding loop-carried dependencies.

Question 6

pragma omp parallel for private(x) shared(y)

Answer 6

Explicitly declare variable scope to avoid unintended data sharing.

Question 7

pragma omp parallel for reduction(+:sum)

Answer 7

Parallelize reduction operations efficiently.

Question 8

pragma omp barrier

Answer 8

Synchronize all threads at a certain point.

Question 9

A structured parallel region

Answer 9

• 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.

Question 10

pragma omp parallel default(private)

Answer 10

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.

Question 11

pragma omp parallel for schedule(static, 1)

Answer 11

Distributes the iterations in a round-robin fashion among the threads.

Question 12

pragma omp parallel for schedule(dynamic, 3)

Answer 12

Iterations are divided into chunks. When a thread finishes its chunk, it requests another, continuing until all iterations are completed.

Question 13

pragma omp parallel for schedule(guided, 2)

Answer 13

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.

Question 14

pragma omp parallel for schedule(runtime)

export OMP_SCHEDULE=”dynamic,4”

Answer 14

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.

Question 15

pragma omp task

Answer 15

Tasks are created within a single execution block to ensure that only one thread is involved in task creation, avoiding unnecessary duplication of work.

Question 16

Deadlocks

Answer 16

A situation where a set of processes is blocked, each waiting for an event that only another process in the set can cause

Question 17

Conditions for Deadlock

Answer 17

1. Mutual Exclusion: Only one process can use a resource at any given time.
2. Hold and Wait: A process holding at least one resource is waiting to acquire additional
   resources held by other processes.
3. No Preemption: A resource can be released only voluntarily by the process holding it.
4. 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.

Question 18

Deadlock Prevention

Answer 18

• 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.

Question 19

Deadlock Avoidance

Answer 19

• Banker’s Algorithm
• Safe State Algorithm
• Resource Ready Algorithm

Question 20

Deadlock Detection

Answer 20

• Search for cycles in resource-allocation graph
• If single, transform RAG into wait-for graph
• If not, then use the Banker’s

Question 21

Recovery from Deadlock

Answer 21

• 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.

Question 22

TestAndSet()

Answer 22

An atomic operation used to set a target boolean variable to TRUE
and return its previous value.

Question 23

Swap()

Answer 23

An atomic operation that exchanges the values of two boolean variables.

Question 24

Sephamore

Answer 24

• 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:

Question 25

Counting Sephamore

Answer 25

• Generalization of the binary semaphore, initialized to the number of available resources.
• Used to control access to a set number of identical resources.
• wait and signal operations are similar to binary semaphores but control multiple instances of a resource.

Question 26

Bounded-Buffer Problem
while (true) {
wait(empty);
wait(mutex);
// add item to buffer
signal(mutex);
signal(full);
}
// Consumer
while (true) {
wait(full);
wait(mutex);
// remove item from buffer
signal(mutex);
signal(empty);
}

Answer 26

This scenario involves a fixed number of buffer slots. The producer can add an item if a slot is empty, and the consumer can remove an item if a slot is full. Semaphores used:
- mutex (initialized to 1): Ensures exclusive access to add or remove items.
- full (initialized to 0): Tracks the number of full buffer slots.
- empty (initialized to n): Indicates the number of empty buffer slots.

Question 27

Readers-Writers Problem
while (true) {
wait(wrt);
// writing
signal(wrt);
}
// Reader
while (true) {
wait(mutex);
readcount++;
if (readcount == 1) wait(wrt);
signal(mutex);
// reading
wait(mutex);
readcount–;
if (readcount == 0) signal(wrt);
signal(mutex);
}

Answer 27

Involves shared data that cannot be accessed by others while being written but can be read by multiple readers simultaneously. Semaphores:
- wrt (initialized to 1): Allows one writer or multiple readers access.
- mutex (initialized to 1): Controls access to readcount variable.

Question 28

Dining Philosophers Problem

// Philosopher i
while (TRUE) {
wait(chopstick[i]);
wait(chopstick[(i + 1) % 5]);
// eat
signal(chopstick[i]);
signal(chopstick[(i + 1) % 5]);
// think
}

Answer 28

Five philosophers sit around a table with five chopsticks between them. Each must pick up the two nearest chopsticks to eat. Semaphores represent chopsticks (initialized to 1).