Unit 3: Process Synchronization and Deadlocks

Question 1

What is process synchronization?

Answer 1

Process synchronization is necessary to manage concurrently executing processes that share common resources.

It helps to avoid conflicts and ensure data consistency.

Question 2

What is a race condition?

Answer 2

A race condition occurs when multiple processes access and modify shared data concurrently, and the final outcome depends on the order of execution.

This can lead to unpredictable results.

Question 3

How can incrementing and decrementing a shared counter lead to a race condition?

Answer 3

Incrementing (counter++) and decrementing (counter–) a shared counter by multiple processes can lead to an incorrect final value due to interleaving.

Interleaving refers to the overlapping execution of processes.

Question 4

What is a critical section?

Answer 4

A critical section is a segment of code where a process accesses shared resources.

Proper management of critical sections is essential to avoid race conditions.

Question 5

What is the goal of the critical section problem?

Answer 5

The goal of the critical section problem is to design protocols that allow processes to access shared resources safely and avoid race conditions.

Question 6

What is mutual exclusion?

Answer 6

Mutual exclusion is a requirement for critical section solutions, ensuring that only one process can be in its critical section at a time.

Question 7

What does progress mean in the context of critical sections?

Answer 7

Progress is a requirement, stating that if no process is in its critical section and some want to enter, the decision of who enters next cannot be postponed indefinitely.

Question 8

What is bounded waiting?

Answer 8

Bounded waiting is a requirement, ensuring a limit on how many times other processes can enter their critical sections after a process has requested to enter its own.

Question 9

What is Peterson’s solution?

Answer 9

Peterson’s solution is a software-based solution to the critical section problem for two processes, using shared flag and turn variables.

Question 10

In Peterson’s solution, what does flag[i] = true indicate?

Answer 10

flag[i] = true indicates that process Pi is ready to enter the critical section.

Question 11

What does the turn variable indicate in Peterson’s solution?

Answer 11

The turn variable indicates whose turn it is to enter the critical section.

Question 12

What are atomic operations?

Answer 12

Atomic operations are hardware support instructions that are non-interruptible and help solve the critical section problem.

Question 13

What does the test_and_set() instruction do?

Answer 13

test_and_set() atomically tests and sets a boolean value, returning the original value.

Question 14

How can test_and_set() be used for mutual exclusion?

Answer 14

test_and_set() can be used with a shared lock variable to enforce mutual exclusion by busy-waiting until the lock is false.

Question 15

What does the compare_and_swap() instruction do?

Answer 15

compare_and_swap() atomically compares a value with an expected value, and if they are equal, sets the value to a new value, returning the original value.

Question 16

How can compare_and_swap() be used for mutual exclusion?

Answer 16

compare_and_swap() can be used with a shared lock variable to enforce mutual exclusion by busy-waiting until the lock is 0.

Question 17

What is a semaphore?

Answer 17

A semaphore is a synchronisation tool (integer variable) accessed only through atomic wait() and signal() operations.

Question 18

What does the wait() operation do in semaphore?

Answer 18

The wait(S) operation decrements the semaphore value S, and if S becomes non-positive, the process may be blocked.

Question 19

What does the signal() operation do in semaphore?

Answer 19

The signal(S) operation increments the semaphore value S, potentially waking up a blocked process.

Question 20

What is a counting semaphore?

Answer 20

A counting semaphore can have an integer value over an unrestricted domain, used for controlling access to a finite number of resources.

Question 21

What is a binary semaphore?

Answer 21

A binary semaphore can only have values 0 or 1, functioning similarly to a mutex lock for mutual exclusion.

Question 22

How can semaphores ensure order of execution?

Answer 22

Semaphores can ensure one statement (S1 in P1) happens before another (S2 in P2) by initialising a semaphore to 0 and using signal() after S1 and wait() before S2.

Question 23

What is deadlock?

Answer 23

Deadlock is a situation where two or more processes are blocked indefinitely, each waiting for a resource held by another process in the set.

Question 24

What is the mutual exclusion condition for deadlock?

Answer 24

Mutual exclusion is a condition for deadlock, where resources are non-sharable, and only one process can use a resource at a time.

Question 25

What is the hold and wait condition for deadlock?

Answer 25

Hold and wait is a condition for deadlock, where a process holds at least one resource while waiting to acquire additional resources held by other processes.

Question 26

What is the no preemption condition for deadlock?

Answer 26

No preemption is a condition for deadlock, where a resource can only be released voluntarily by the holding process after it has completed its task.

Question 27

What is the circular wait condition for deadlock?

Answer 27

Circular wait is a condition for deadlock, where a cycle of processes exists, each waiting for a resource held by the next process in the cycle.

Question 28

What is a resource-allocation graph?

Answer 28

A resource-allocation graph visually represents processes and resources, with request edges and assignment edges indicating resource needs and allocation.

Question 29

How can a resource-allocation graph be used for deadlock detection?

Answer 29

In a resource-allocation graph with single instances per resource type, a cycle indicates a deadlock.

Question 30

What is deadlock prevention?

Answer 30

Deadlock prevention aims to prevent deadlock by ensuring that at least one of the four necessary conditions cannot hold.

Question 31

What is deadlock avoidance?

Answer 31

Deadlock avoidance allows the system to enter a potentially unsafe state but uses a priori information about resource needs to ensure that the system will never enter a deadlock state.

Question 32

What is the Banker's algorithm?

Answer 32

The Banker's algorithm is a deadlock avoidance algorithm for multiple instances of resources, using the concepts of safe and unsafe states to decide whether to grant resource requests.

Question 33

What is a safe state?

Answer 33

A system is in a safe state if there exists a sequence of all processes such that each process can acquire all its needed resources and then release them, thus avoiding deadlock.

Question 34

What is an unsafe state?

Answer 34

A system in an unsafe state may lead to a deadlock, although it is not guaranteed.

Question 35

What are deadlock detection algorithms used for?

Answer 35

Deadlock detection algorithms can be used to identify if a deadlock has occurred when deadlock avoidance is not employed.

Question 36

What is one way to recover from deadlock?

Answer 36

One way to recover from deadlock is to abort one or more of the deadlocked processes.

Question 37

What is another way to recover from deadlock?

Answer 37

Another way to recover from deadlock is to preempt resources from one or more of the deadlocked processes.

Question 38

What is the bounded-buffer problem?

Answer 38

The bounded-buffer problem is a classic synchronisation problem between producers and consumers using a buffer of limited size.

Question 39

How can semaphores be used for the bounded-buffer problem?

Answer 39

Semaphores (mutex, empty, full) can be used to synchronise producers and consumers in the bounded-buffer problem, ensuring correct access to the buffer.

Question 40

What is the readers-writers problem?

Answer 40

The readers-writers problem is where multiple readers can access shared data simultaneously, but only one writer can access it at a time.

Question 41

How can semaphores be used to solve the readers-writers problem?

Answer 41

Semaphores (rw_mutex, mutex, read_count) can be used to solve the readers-writers problem, controlling access for reading and writing.

Question 42

What is the dining-philosophers problem?

Answer 42

The dining-philosophers problem is a classic synchronisation problem illustrating challenges in resource sharing and potential for deadlock.

Question 43

How can semaphores be used in the dining-philosophers problem?

Answer 43

Semaphores (chopstick) can be used in an attempt to solve the dining-philosophers problem, and understand the potential for deadlock in a naive implementation.