Module 8

Question 1

Deadlocks:

Answer 1

suppose there is a finite set of resources and there are multiple
threads or processes requesting these resources. There is a deadlock if the
threads are waiting on resources held by other threads in a cycle such that none
of the threads in this cycle of dependencies will be able to proceed. T

Question 2

Mutual exclusion:

Answer 2

resources held by one process cannot be
simultaneously used by another process

Question 3

Resource preemption:

Answer 3

when a process or thread acquires a particular
resource, it holds onto the resource until it releases it; other processes or
threads cannot steal the resource

Question 4

Hold and wait:

Answer 4

a process can accumulate resources and does not have
to grab all the resources that it needs at the same time

Question 5

Circular waiting:

Answer 5

circular chain of processes that are requesting
resources from each other

Question 6

Hierarchical allocation (deadlock prevention):

Answer 6

create a policy that determines
which processes can receive which resources by creating a hierarchy between
the resources or between the processes

Question 7

Resource allocation graph (deadlock detection):

Answer 7

a RAG is a tool for deadlock
detection, because deadlock only occurs if the RAG has a cycle. To form the
RAG, there is a node for every process and a node for every resource. If a
process P currently has resource R, then we form a directed edge from R to P. If
process P is requiring process R, then we form a directed edge from P to R.

Question 8

Wait-for-graph (deadlock detection):

Answer 8

shows dependencies of processes or
threads that waiting on others. To form this graph, there is a node for each
process or thread, and there is a directed edge from Pi to Pj, if Pi is waiting on a
resource from Pj.

Question 9

Checkpointing:

Answer 9

save the state (of a process) in case of a required rollback of
operations to the process

Question 10

Safe-allocations (deadlock avoidance):

Answer 10

an allocation state is safe if there is a
sequential ordering of processes such that all the processes will be able to finish
executing

Question 11

Banker’s Algorithm (deadlock avoidance):

Answer 11

given n processes and m
resources, the algorithm only grants resources to a process if it will result in a
safe allocation state

Question 12

Req[i, j]:

Answer 12

matrix representing the number of resources Rj requested by
process Pi

Question 13

C[i, j]:

Answer 13

matrix representing the amount of resource Rj currently held by
process Pi

Question 14

M[i, j]:

Answer 14

matrix representing the maximum number of resource Rj that a
process Pi will ever request

Question 15

A[j]:

Answer 15

vector representing the number of resource Rj that are currently free