Operating System test 2 Chatper 8 (chapter 5 of the essentials textbook)

test 2 Chatper 8 (chapter 5 of the essentials textbook)

Deadlock Characterization

state where a set of processes are permanently blocked because each holds a resource while waiting for another held by a different process. There are 4, Mutual Exclusion, Hold and wait, No preemption, and Circular Wait.

mutual exclusion

only one process at a time can use a
resource

Hold and wait

a process holding at least one resource is
waiting to acquire additional resources held by other
processes

No preemption

a resource can be released only voluntarily
by the process holding it, after that process has completed its
task

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.

Resource-Allocation Graph

a directed graph used in operating systems to visualize and detect deadlocks by representing the state of processes and resources

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

If graph contains no cycles

no deadlock

If graph contains a cycle

deadlock

if only one instance per resource type

then deadlock

if several instances per resource type

possibility of deadlock

Deadlock Prevention

designing systems to eliminate at least one of the four necessary conditions for deadlocks (Mutual Exclusion, Hold and Wait, No Preemption, or Circular Wait).

Mutual Exclusion

not required for sharable resources (e.g.,
read-only files); must hold for non-sharable resources

Hold and Wait

must guarantee that whenever a process
requests a resource, it does not hold any other resources

No Preemption

resources held by a process cannot be forcibly taken away; they must be released voluntarily.

Circular Wait

two or more processes form a circular chain where each process waits for a resource that the next process in the chain holds.

Bankers Algorithm

algorithm used in operating systems to manage resource allocation by simulating the allocation to check for safety

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 Pi may request at
most k instances of resource type Rj

Allocation

n x m matrix. If Allocation[i,j] = k then Pi is currently
allocated k instances of Rj

Need

n x m matrix. If Need[i,j] = k, then Pi may need k more
instances of Rj to complete its task

Need [i,j] = Max[i,j] – Allocation [i,j]

Deadlock Detection

an operating system mechanism that identifies when processes are stuck waiting for resources held by others, allowing the system to resolve the blockage

Available

A vector of length m indicates the number of available
resources of each type

Allocation

An n x m matrix defines the number of resources of each
type currently allocated to each process

Request

An n x m matrix indicates the current request of each
process. If Request [i][j] = k, then process Pi is requesting k more
instances of resource type Rj.

Recovery from Deadlock: Process Termination

breaks deadlock by killing processes to reclaim resources, acting as a direct recovery method after detection.

1. Priority of the process

2. How long process has computed, and how much longer to completion

3. Resources the process has used

4. Resources process needs to complete

5. How many processes will need to be terminated

6. Is process interactive or batch?