Chapter Eight Notes

Question 1

System

Answer 1

A system consists of a finite number of
resources to be distributed among a number
of competing threads.

Question 2

If a system has four CPU’s, how many instances does it have?

Answer 2

Four instances

Question 3

Examples of resource types

Answer 3

CPU cycles, files, and I/O Devices

Question 4

How does each process utilize a resource?

Answer 4

◦ Request: The thread requests the
resource. If the request cannot be
granted immediately then the
requesting thread must wait until it
can acquire the resource.
◦ Use: The thread can operate on the
resource (for example, if the
resource is a mutex lock, the thread
can access its critical section).
◦ Release: The thread releases the
resource.

Question 5

System table

Answer 5

Records whether each resource is free or to be allocated.

For each resource allocated, table also records the thread to which it is allocated

Question 6

Deadlocks are possible in multithreaded applications (T/F)

Answer 6

True

Question 7

When is a deadlock possible in a multithreaded application? (refer to code in slide 11)

Answer 7

If thread_one acquires first_mutex while thread_two acquires second_mutex

Question 8

Deadlock will not occur in multithreaded application if

Answer 8

thread_one can acquire and release the mutex locks.

Question 9

A deadlock can arise if which four conditions hold simultaneously

Answer 9

1) Mutual exclusion: only one process at a time can use a resource

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,
after that process has completed its task

4) Circular wait: there exists a set {P0, P1, …, Pn} of waiting processes such that P0 is waiting
for a resource that is held by P1, P1 is waiting for a resource that is held by P2, …, Pn–1 is
waiting for a resource that is held by Pn, and Pn is waiting for a resource that is held by P0.

Question 10

Components of a graph

Answer 10

A set of vertices V and a set of edges E.
Resource

V is partitioned into two types:
◦ T = {T1 , T2 , …, Tn}, the set consisting of all the active threads in the
system
◦ R = {R1 , R2 , …, Rm }, the set consisting of all resource types in the
system.
◦ Each thread Ti is represented as a circle and each resource type Rj as
a rectangle.

Question 11

Two types of edges in a graph

Answer 11

request edge – directed edge Ti -> Rj
assignment edge – directed edge Rj -> Ti

Question 12

What does each shape in a resource allocation graph represent (circle, square/rectangle with 4 dots, circle with arrow to rectangle, rectangle with arrow to circle)

Answer 12

Circle: Thread (Ti)

Rectangle: Resource type (Rj)

Dots in rectangle: Instances

Circle with arrow to rectangle: Ti requests instance of Rj

Rectangle with arrow to circle: Ti is holding an instance or Rj

Question 13

If a graph contains no cycles there is a deadlock (T/F)

Answer 13

False, there is no deadlock

Question 14

If a graph contains a cycle and there is only one instance per resource there is a deadlock (T/F)

Answer 14

True

Question 15

If a graph contains a cycle and there are several instances per resource type, there is no possibility of a deadlock (T/F)

Answer 15

False

Question 16

Deadlock prevention

Answer 16

provides a set of
methods to ensure that at least one of the
necessary conditions cannot hold

Question 17

By ensuring at least one of which conditions can we prevent the occurrence of a deadlock

Answer 17

Mutual Exclusion – not required for sharable
resources (e.g., read-only files); must hold for
non-sharable resources; Read-only files are a
good example of a sharable resource; A
thread never needs to wait for a sharable
resource.

Hold and Wait – must guarantee that whenever a
process requests a resource, it does not hold any
other resources
◦ Require process to request and be allocated all its
resources before it begins execution or allow
process to request resources only when the
process has none allocated to it.
◦ Low resource utilization; starvation possible

Alternatively, if a thread requests some resources:
◦ We first check whether they are available. If they
are, we allocate them.
◦ If they are not, we check whether they are
allocated to some other thread that is waiting
for additional resources.
◦ If so, we preempt the desired resources from
the waiting thread and allocate them to the
requesting thread.
◦ If the resources are neither available nor held by
a waiting thread, the requesting thread must
wait.

No Preemption –
◦ If a process that is holding some resources
requests another resource that cannot be
immediately allocated to it, then all resources
currently being held are released
◦ Preempted resources are added to the list of
resources for which the process is waiting
◦ Process will be restarted only when it can regain
its old resources, as well as the new ones that it
is requesting

Question 18

What protocol ensures that the circular-wait condition cannot hold

Answer 18

◦ Let the set of threads involved in the circular
wait be {T0 , T1 , …, Tn}, where Ti is waiting for a
resource Ri , which is held by thread Ti+1 . Then, since thread Ti+1 is holding resource Ri while requesting resource Ri+1 , we must have F(Ri ) < F(Ri+1 ) for all i.

◦ But this condition means that F(R0 ) < F(R1 ) < …
< F(Rn) < F(R0 ). By transitivity, F(R0 ) < F(R0 ), which is impossible. Therefore, there can be no circular wait.

Question 19

When is a state safe?

Answer 19

A state is safe if the system can allocate resources to each thread (up
to its maximum) in some order and still avoid a deadlock.
- System is in safe state if A sequence of threads <T 1, T 2, …, Tn> is a safe
sequence for the current allocation state

Question 20

What algorithm can apply to Multiple instances of a resource type?

Answer 20

Banker’s Algorithm

Question 21

What happens in a bankers algorithm?

Answer 21

When a new thread enters the system, it
must declare the maximum number of
instances of each resource type that it may need. This number may not exceed the total number of resources in the system.

When a user requests a set of resources, the system must determine whether the allocation of these resources will leave the system in a safe state. If it will, the resources are allocated; otherwise, the thread must wait until some
other thread releases enough resources.

Question 22

Data structures for Bankers Algorithm

Answer 22

• Let n = number of processes, and m = number of resources
  types.
• Available: Vector of length m. If available [j] = k, there are k
  instances of resource type Rj available
• Max: n x m matrix. If Max [i,j] = k, then process Ti may
  request at most k instances of resource type Rj
• Allocation: n x m matrix. If Allocation[i,j] = k then Ti is currently allocated k instances of Rj
• Need: n x m matrix. If Need[i,j] = k, then Ti may need k more
  instances of Rj to complete its task
  Need [i,j] = Max[i,j] – Allocation [i,j]
• These data structures vary over time in both size and value

Question 23

Solve slide 67

Answer 23

Give this a 5

Question 24

Deadlock Detection

Answer 24

• If a system does not employ either a deadlock-prevention or a deadlock-avoidance algorithm, then a deadlock situation may occur. In this environment, the system may provide:
• Allow system to enter deadlock state
• An algorithm to recover from the deadlock
• Recovery scheme

Question 25

Recovery
from Deadlock

Answer 25

Several useful algorithms when detection determines deadlock exists:

1) Process Termination
2) Resource Preemption: Selecting victim, Rollback, Starvation

Question 26

Process Termination

Answer 26

We should abort those processes whose
termination will incur the minimum cost.

Many factors may affect which process is
chosen, including:
1. What the priority of the process is
2. How long the process has computed and
how much longer the process will compute
before completing its designated task
3. How many and what types of resources the
process has used (for example, whether the
resources are simple to preempt)
4. How many more resources the process
needs in order to complete
5. How many processes will need to be
terminated

Question 27

Resource Preemption: Selecting a victim

Answer 27

As in process termination, we must determine the order of preemption to minimize cost. Cost factors may include such parameters as the number of resources a deadlocked process is holding and the amount of time the process has thus far consumed.

Question 28

What is a less expensive Detection- Algorithm Usage?

Answer 28

A less expensive alternative is
simply to invoke the algorithm at
defined intervals—for example,
once per hour or whenever CPU
utilization drops below 40 percent.
If detection algorithm is invoked
arbitrarily, there may be many
cycles in the resource graph and so
we would not be able to tell which
of the many deadlocked processes
“caused” the deadlock.

Question 29

Resource Preemption: Rollback

Answer 29

Clearly, it cannot continue with
its normal execution; it is missing some
needed resource. We must roll back the
process to some safe state and restart it from
that state.

Question 30

Resource Preemptive: Starvation

Answer 30

How do we ensure that
starvation will not occur? That is, how can we guarantee that resources will not always be preempted from the same process?
◦ In a system where victim selection is based
primarily on cost factors, it may happen that the same process is always picked as a victim.
◦ As a result, this process never completes its
designated task, a starvation situation any
practical system must address.
◦ Clearly, we must ensure that a process can be picked as a victim only a (small) finite number
of times.
◦ The most common solution is to include the number of rollbacks in the cost factor.