Chapter Eight Notes Flashcards
System
A system consists of a finite number of
resources to be distributed among a number
of competing threads.
If a system has four CPU’s, how many instances does it have?
Four instances
Examples of resource types
CPU cycles, files, and I/O Devices
How does each process utilize a resource?
◦ 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.
System table
Records whether each resource is free or to be allocated.
For each resource allocated, table also records the thread to which it is allocated
Deadlocks are possible in multithreaded applications (T/F)
True
When is a deadlock possible in a multithreaded application? (refer to code in slide 11)
If thread_one acquires first_mutex while thread_two acquires second_mutex
Deadlock will not occur in multithreaded application if
thread_one can acquire and release the mutex locks.
A deadlock can arise if which four conditions hold simultaneously
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.
Components of a graph
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.
Two types of edges in a graph
request edge – directed edge Ti -> Rj
assignment edge – directed edge Rj -> Ti
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)
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
If a graph contains no cycles there is a deadlock (T/F)
False, there is no deadlock
If a graph contains a cycle and there is only one instance per resource there is a deadlock (T/F)
True
If a graph contains a cycle and there are several instances per resource type, there is no possibility of a deadlock (T/F)
False