Deadlocks (week 7)

Question 1

define deadlocks

Answer 1

A deadlock is a situation where in a group
of two or more processes/threads, each
process holds at least one resource while
making a request on another, and all
requests cannot be satisfied because the
requested resource is held by another
process that is being blocked, waiting for
another resource.

Question 2

how can deadlocks occur

Answer 2

–> multiprogramming environment where processes share the resources.

–> deadlocks can also occur between threads in the same process

–> Resource managers can also be involved in a deadlock with an application process

Question 3

what are the 4 conditions for the deadlocks to happen

Answer 3

–> Mutual exclusion
–> Hold and Wait
–> Circular wait
–> No preemption

Question 4

explain what is mutual exclusion in the scenario of deadlocks

Answer 4

–> Once a process has been allocated a
particular resource, the threads in the process have exclusive use of the resource.

–> No other processes can use a resource while it is allocated to a process.

Question 5

explain what is hold and wait in the scenario of deadlocks

Answer 5

A process may hold a resource at the same
time it requests another one.

Question 6

explain what is circular wait in the scenario of deadlocks

Answer 6

A situation can rise in which process p1 holds resource R1 while one of its threads requests resource R2, and process p2 holds R2 while one of its threads requests resource R1.

There may be more than two processes involved in the circular wait.

Question 7

explain what is non preemption in the scenario of deadlocks

Answer 7

Resources can be released only by the explicit action in a process, rather than by the action of an external authority.

This assumption includes the case in which a process places a request for a resource and the resource is not available. Then the process cannot withdraw its request.

Question 8

what are the 4 approaches to addressing deadlocks

Answer 8

prevention
avoidance
detection & recovery
manual intervention

Question 9

what is prevention

Answer 9

–> Design the system so that
deadlock is impossible

–> Address the 4 conditions so that at least one of them does not hold. (mutual exclusion, hold and wait, circular waiting, no preemption)

–> Most common strategy is to design the resource managers so that they are guaranteed to violate at least one of the conditions.

–> for example windows NT assures that there is no circular waiting

Question 10

what is avoidance

Answer 10

–> Manage deadlocks by allow resource
allocation only if it is satisfied that
deadlocks will not occur

–> implemented using Banker’s Algorithm.

Question 11

what is Detection and Recovery

Answer 11

–> it is an aggressive strategy

–> Disregards deadlocks, but aims to detect
when it does occur and takes additional
steps to remove it. (recovery)

–> Therefore, we need both a detection
mechanism and a recovery mechanism.

–> For detection, an algorithm similar to
Banker’s algorithm can be used.

Question 12

when to invoke the deadlock detection algorithm

Answer 12

–> Invoke each time a request for allocation cannot be granted immediately.

–> Invoke at regular time intervals, eg, once per hour

–> Invoke when CPU utilization drops below 40%

Question 13

what is the advantage of Invoking deadlock detection algorithm each time a request for allocation cannot be granted immediately.

Answer 13

able to identify the specific process
that caused the deadlock

Question 14

what is the disadvantage of Invoking deadlock detection algorithm each time a request for allocation cannot be granted immediately.

Answer 14

overhead in computation time (as you are using the cpu to check for deadlocks instead of running regular processes)

Question 15

Resources allocated to deadlocked
processes will be _______ until the deadlock is broken.

Answer 15

idle

Question 16

what are the 2 options to breaking deadlocks (deadlock recovery ) for the manual intervention method

Answer 16

–> Process termination
–> Resource Preemption

Question 17

what are the 2 ways of doing process termination

Answer 17

there are 2 ways of doing process termination

–> abort all the deadlocked process
–> Abort one process at a time until the deadlock cycle is broken

Question 18

why is aborting all the deadlocked process expensive

Answer 18

This method is expensive since processes may have computed for a long time, and all results must be discarded, and recomputed again.

Question 19

why is Aborting one process at a time incurring overhead

Answer 19

This method incurs overhead since after each process is aborted, deadlock detection algorithm must be invoked to check whether any process is still deadlocked.

Question 20

Aborting a process may not be _______

give an example of why this is the case

Answer 20

simple

process may be in the midst of updating a file

Question 21

what must be defined in partial termination method

Answer 21

a policy must be defined as to which process to terminate

Question 22

Factors to determine which process is chosen in process termination

Answer 22

–> The priority of process
–> How long the process has computed and how much longer to go
–> How many and what type of resources the process has used
–> How many more resources the process needs in order to complete
–> How many processes will need to be terminated
–> Whether the process is interactive or batch

Question 23

how does Resource Preemption work ?

Answer 23

Preempt some resources from processes and give these resources to other processes until the deadlock cycle is broken

Question 24

what happens to the resource allocated for processes when either process termination or resource preemption
methods occur

Answer 24

the system reclaims all resource allocated to the terminating processes.

Question 25

what are 3 issues to be addressed in resource preemption

Answer 25

–> Selecting a victim
–> Rollback
–> Starvation

Question 26

what does it mean to select a victim

Answer 26

It means which resources and processes to preempt?

the answer to that is that it depends on cost, amount of time
process execute thus far, number of resources holding, etc.

Question 27

what does the rollback issue mean

Answer 27

If we preempt a resource from a process, what should be done to the process?

Either total rollback or rollback enough to break deadlock

Question 28

what does Starvation mean

Answer 28

How to ensure starvation will not occur? That is, how can we guarantee that resources will not always be preempted from the same process?

A common solution is to include the number of rollbacks in the cost factor.

Question 29

what Combined Approach to Deadlock Handling do internal resources do

Answer 29

internal resources are used by the system and prevention is done through resource ordering

Question 30

what Combined Approach to Deadlock Handling do central memory do

Answer 30

central memory is the memory used by a user job and prevention is done through preemption

Question 31

what Combined Approach to Deadlock Handling do Job resources do

Answer 31

job resources is the devices that can be assigned, for example, tape drive, files

deadlocks are addressed though avoidance

Question 31

what Combined Approach to Deadlock Handling do Job resources do

Answer 31

job resources is the devices that can be assigned, for example, tape drive, files

deadlocks are addressed though avoided

Question 32

what Combined Approach to Deadlock Handling does Swappable space do

Answer 32

swappable space is the Space on backing store for each user job

deadlocks are addressed though Preallocation

Question 33

how to disallow hold and wait condition

Answer 33

–> Require a process to request all of its resources when it is created.

–> Require the process to release all currently held resources prior to requesting any new ones.

Question 34

give the characteristics of Requiring a process to request all of its resources when it is created.

Answer 34

–> Easy implementable in batch systems.

–> Not easy in interactive systems as processes do not ‘announce’ their resource requirements at runtime

Question 35

give the characteristics of requiring the process to release all currently held resources prior to requesting any new ones

Answer 35

–> More suitable for interactive systems.

–> Have processes request for resources based on a particular operation and then release it when proceeding onto another operation with a new set of resources.

–> Or, when a process requires a new resource, it releases all of its current resources and then acquires the old resources along with the new one.

Question 36

how to disallow circular wait (technique 1)

Answer 36

–> Use a process-resource model to detect cycles in the graph.

–> Choose a resource request strategy by which no cycle will be
introduced

–> Cycle condition will reflect circular wait if each resource type
has only one instance (non-sharable).

Question 37

how to disallow circular wait (technique 2)

Answer 37

–> Total order on all resources, then can only ask for Rj if Ri < Rj for all Ri the process is currently holding

–> Number each resource uniquely

–> A process wishing to obtain resources must obtain them in ascending or decreasing order

–> If new resource is not in the correct order, release all currently held resources and re-obtain them in the correct order.

Question 38

how to disallow preemption

Answer 38

If a process requests for a resource and the resource is not available, its currently held resources can be preempted by the OS and given to other resources.