Deadlocks

Question 1

A deadlock is a set of __________ each holding a resource and waiting to acquire a resource held by another _______

Answer 1

processes, process

Question 2

What are 2 reasons why deadlocks occur?

Answer 2

• Complex dependencies

- Encapsulation

Question 3

Complex dependencies can cause deadlocks because it’s easy to create _________ _____________

Answer 3

circular dependencies

Question 4

____________ can cause deadlocks because each module hides its implementation details without coordinating with other modules

Answer 4

Encapsulation

Question 5

What four conditions if held simultaneously MAY cause a deadlock?

Answer 5

• Mutual exclusion
• Hold and wait
• No preemption
• Circular Wait

Question 6

What is mutual exclusion?

Answer 6

Threads requiring exclusive control of resources

Question 7

What is hold and wait?

Answer 7

hreads are already holding resources but also are waiting for additional resources being held by other threads

Question 8

What does no preemption mean?

Answer 8

resource released only voluntarily by the thread holding it

Question 9

What is circular wait?

Answer 9

here exists a set {P0, P1, …, Pn} of processes such that P0 is waiting for a resource that is held by P1, P1 is waiting for P2, …, Pn–1 is waiting Pn, and Pn is waiting for P0

Question 10

What are 3 methods to avoid or recover from deadlocks?

Answer 10

• Prevention (ensure one condition does not hold)
• Avoidance
• Detection and recovery

Question 11

To prevent circular wait, we enforce that each thread requests resources in a ________ _______. We impose a _______ ________ on all resource types

Answer 11

consistent order, total ordering

Question 12

To prevent hold and wait, we acquire ____ locks ___________

Answer 12

all, atomically

Question 13

A disadvantage in preventing hold and wait is that we must know which locks to acquire in ________ and it decreases _________

Answer 13

advance, concurrency

Question 14

To prevent no preemption, we make processes that fail to get a lock _____ __ all already-holding lock and _______

Answer 14

give up, retry

Question 15

To prevent no preemption, we can specify a _______ for a thread if it does not get all its locks

Answer 15

timeout

Question 16

Preventing no preemption can cause a __________, where all threads are __________ steps

Answer 16

livelock, repeating

Question 17

To solve a livelock, we can add random ______ between retries

Answer 17

delays

Question 18

To prevent mutual exclusion, we can use ________ algorithms using ______ instructions

Answer 18

lock-free, atomic

Question 19

Lock-free algorithms may achieve high ________ and prevent creation of ________, but are very ____________, as threads must handle data races explicitly

Answer 19

performance, deadlocks, error-prone

Question 20

Avoiding deadlocks by scheduling works in 2 steps. What are they?

Answer 20

1. Know which locks might be requested by which threads

2. Schedule threads in a way that guarantees no deadlocks can occur

Question 21

A disadvantage of avoiding deadlock by scheduling is that it requires _______ _______ about all participating threads and resources

Answer 21

global knowledge

Question 22

Review deadlock avoidance slides

Answer 22

Review deadlock avoidance slides

Question 23

A disadvantage of avoiding deadlock by scheduling is that it can possibly _______ the time needed to complete jobs

Answer 23

increase

Question 24

A _______ and ________ solution allows deadlocks to occur, then take actions to resolve it

Answer 24

detect, recover

Question 25

In detect and recover, a deadlock _______ runs periodically

Answer 25

detector

Question 26

In detect and recover, a possible deadlock detector maintains a _____ that summarizes _________ and check for _______

Answer 26

graph, dependencies, cycles

Question 27

In detect and recover, once a deadlock is detected, the system can _____ system or ______ some threads/victims

Answer 27

restart, preempt

Question 28

Detect and recover is common in _______ _______

Answer 28

database systems