Operating Systems Module 4

Questions and Answers

A situation where processes never finish executing and system resources are tied up, preventing other jobs from starting.

Hold and Wait (correct)

Preemption

Circular Wait (correct)

Mutual Exclusion (correct)

False

Preventing or avoiding deadlocks, detecting and recovering from deadlocks, and ignoring the problem. Signup and view all the answers

avoidance Signup and view all the answers

All of the above Signup and view all the answers

Request, Use, Release Signup and view all the answers

Both A and C Signup and view all the answers

False Signup and view all the answers

To determine whether a deadlock has occurred in the system. Signup and view all the answers

wait-for graph Signup and view all the answers

The number of resources currently allocated to each process Signup and view all the answers

True Signup and view all the answers

Study Notes

A system includes a limited number of resources shared among competing processes.
Resource types: memory space, CPU cycles, files, and I/O devices (e.g., printers).
Resources consist of multiple identical instances; for example, two CPUs or five printers.
Processes must request resources before use and release them after completing tasks.
A request for a resource may put a process in a waiting state if the resource is already allocated.
A system table keeps track of resource allocation and availability.

A deadlock occurs when processes are unable to change state because they are waiting indefinitely for resources held by other waiting processes.
In deadlock situations, processes do not complete, and resources remain occupied, hindering other jobs.

Four necessary conditions for deadlock:
- Mutual Exclusion: At least one resource must be held in a non-sharable mode, allowing only one process to use it; others must wait if they request it.
- Hold and Wait: A process holding at least one resource waits for additional resources held by others.
- No Preemption: Resources cannot be forcibly taken; they must be voluntarily released by the process using them.
- Circular Wait: A sequence of processes exists where each process is waiting for a resource held by the next process in the sequence.

Approaches to manage deadlocks:
- Prevention: Implement protocols to ensure deadlocks can never occur by negating at least one necessary condition.
- Avoidance: The system requires advance knowledge of resources that processes will request to make informed decisions on allocation.
- Detection and Recovery: Allow the system to enter a deadlock state, then detect it and recover. Many operating systems, like UNIX and Windows, typically adopt this approach.
If neither prevention nor avoidance strategies are utilized, a deadlock may occur without detection or recovery measures.

Deadlock situations arise in systems lacking deadlock prevention or avoidance algorithms.
A deadlock detection algorithm is necessary to assess whether a deadlock has occurred in the system.
Recovery mechanisms must be in place to resolve detected deadlocks.

For systems with only one instance of each resource type, a wait-for graph is utilized for deadlock detection.
The wait-for graph is derived from the resource allocation graph by eliminating resource nodes.
Edges in the wait-for graph indicate that one process is waiting on another to release a needed resource.
A deadlock is present if the wait-for graph exhibits a cycle.
To detect cycles, the wait-for graph must be maintained, and algorithms should periodically check for cycles.

Detection algorithms leverage time-varying data structures akin to those in the banker’s algorithm for resource management.
Available Vector: Represents the number of available resources for each type, length m.
Allocation Matrix: An n x m matrix indicating resource allocations to each process.
Request Matrix: An n x m matrix showing the current resource requests by each process; if Request[i][j] equals k, process Pi requests k additional instances of resource type Rj.
Initialization involves creating vectors:
- Work initialized to the Available vector.
- Finish vector set to false for processes with allocations and true otherwise.
The algorithm seeks an index i such that:
- Finish[i] is false (process is not finished).
- Request[i] can be satisfied with the current Work state.