Chapter Eight Notes Flashcards

1
Q

System

A

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

How well did you know this?
1
Not at all
2
3
4
5
Perfectly
2
Q

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

A

Four instances

How well did you know this?
1
Not at all
2
3
4
5
Perfectly
3
Q

Examples of resource types

A

CPU cycles, files, and I/O Devices

How well did you know this?
1
Not at all
2
3
4
5
Perfectly
4
Q

How does each process utilize a resource?

A

◦ 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.

How well did you know this?
1
Not at all
2
3
4
5
Perfectly
5
Q

System table

A

Records whether each resource is free or to be allocated.

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

How well did you know this?
1
Not at all
2
3
4
5
Perfectly
6
Q

Deadlocks are possible in multithreaded applications (T/F)

A

True

How well did you know this?
1
Not at all
2
3
4
5
Perfectly
7
Q

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

A

If thread_one acquires first_mutex while thread_two acquires second_mutex

How well did you know this?
1
Not at all
2
3
4
5
Perfectly
8
Q

Deadlock will not occur in multithreaded application if

A

thread_one can acquire and release the mutex locks.

How well did you know this?
1
Not at all
2
3
4
5
Perfectly
9
Q

A deadlock can arise if which four conditions hold simultaneously

A

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.

How well did you know this?
1
Not at all
2
3
4
5
Perfectly
10
Q

Components of a graph

A

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.

How well did you know this?
1
Not at all
2
3
4
5
Perfectly
11
Q

Two types of edges in a graph

A

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

How well did you know this?
1
Not at all
2
3
4
5
Perfectly
12
Q

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)

A

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

How well did you know this?
1
Not at all
2
3
4
5
Perfectly
13
Q

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

A

False, there is no deadlock

How well did you know this?
1
Not at all
2
3
4
5
Perfectly
14
Q

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

A

True

How well did you know this?
1
Not at all
2
3
4
5
Perfectly
15
Q

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

A

False

How well did you know this?
1
Not at all
2
3
4
5
Perfectly
16
Q

Deadlock prevention

A

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

17
Q

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

A

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

18
Q

What protocol ensures that the circular-wait condition cannot hold

A

◦ 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.

19
Q

When is a state safe?

A

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

20
Q

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

A

Banker’s Algorithm

21
Q

What happens in a bankers algorithm?

A

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.

22
Q

Data structures for Bankers Algorithm

A
  • 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
23
Q

Solve slide 67

A

Give this a 5

24
Q

Deadlock Detection

A
  • 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
25
Q

Recovery
from Deadlock

A

Several useful algorithms when detection determines deadlock exists:

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

26
Q

Process Termination

A

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

27
Q

Resource Preemption: Selecting a victim

A

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.

28
Q

What is a less expensive Detection- Algorithm Usage?

A

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.

29
Q

Resource Preemption: Rollback

A

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.

30
Q

Resource Preemptive: Starvation

A

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.