Operating Systems: Deadlocks & Livelocks Flashcards
What is deadlock in the context of operating systems?
Deadlock is a state where processes are unable to proceed because each holds at least one resource while waiting for another resource held by another process, leading to an indefinite standstill.
How does the dining philosophers problem illustrate the concept of deadlock?
In the dining philosophers problem, if all philosophers try to pick up the same pair of forks simultaneously, none can acquire both required resources, causing each to wait indefinitely—thus demonstrating deadlock.
How is deadlock formally defined?
Deadlock is formally defined as a situation where a group of processes becomes permanently blocked because each is holding resources and waiting for resources held by others, preventing any from making progress.
What are the four necessary conditions for deadlock to occur?
A deadlock occurs only if all the following conditions hold simultaneously: mutual exclusion, hold and wait, no pre-emption, and circular wait.
What is the role of the mutual exclusion condition in deadlock formation?
Mutual exclusion means that some resources are non-sharable, only one process can use a resource at a time. When a resource is occupied, any other process that requests it must wait until it is released.
What does the hold and wait condition describe?
Hold and wait occurs when a process holds one or more resources and simultaneously waits to acquire additional resources that are being held by other processes.
How does the no pre-emption condition contribute to deadlock?
No pre-emption means that resources cannot be forcibly removed from a process; they can only be released voluntarily when the process has completed its task, allowing deadlock to persist.
What is meant by the circular wait condition in deadlock scenarios?
Circular wait is when a set of processes forms a closed chain where each process is waiting for a resource held by the next process in the chain, creating a cycle that prevents any process from progressing.
Are the four conditions for deadlock independent? Explain.
Not completely; for instance, the circular wait condition inherently implies a hold and wait scenario. Nonetheless, in deadlock prevention strategies, each condition is treated as a separate constraint to control the occurrence of deadlock.
What are the three primary strategies for handling deadlocks in operating systems?
The strategies are:
(1) ensuring the system never enters a deadlock state (prevention),
(2) allowing deadlocks to occur but providing mechanisms for detection and recovery, and
(3) ignoring deadlocks, assuming they are rare or manageable.
How do Resource Allocation Graphs (RAGs) assist in identifying deadlock states?
RAGs visually represent resource usage by depicting processes and resources as vertices and the relationships between them as directed edges (requests from processes to resources and assignments from resources to processes). They help identify deadlocks by revealing cycles within the graph.
What are the types of vertices and edges in a Resource Allocation Graph (RAG)?
Vertices in a RAG are of two types: processes and resources. Edges also come in two forms: request edges (directed from a process to a resource) and assignment edges (directed from a resource to a process).
How is the usage of multiple instances of a resource represented in a RAG, and what does it imply for deadlock detection?
A RAG can show a resource type with several instances, where a process may request or hold one instance. When only one instance per resource exists, a cycle in the RAG confirms deadlock; with multiple instances, a cycle indicates the possibility of deadlock but does not definitively prove it.
What is the procedure for using RAGs to determine the existence of a deadlock?
First, inspect the graph for cycles. If no cycle exists, then no deadlock is present. If a cycle exists and each resource type has only one instance, a deadlock is confirmed; if multiple instances are available, the cycle suggests the possibility of deadlock.
How can deadlock prevention be achieved by addressing the hold and wait condition?
Deadlock prevention can remove the hold and wait condition by ensuring that when a process requests a resource, it does not hold any others. This can be implemented by requiring processes to request and receive all needed resources before beginning execution.
What strategy can be used to counteract the no pre-emption condition in deadlock prevention?
A system can handle no pre-emption by requiring that if a process requests a resource that is not immediately available, it must release all currently held resources. This prevents processes from indefinitely holding resources while waiting for additional ones.
How is circular wait prevented as a deadlock prevention measure?
Circular wait can be prevented by imposing a strict ordering on resource types so that all processes request resources in that predefined order. While this ordering helps avoid cycles, some circular waiting may still be essential for proper system operation.
What distinguishes deadlock avoidance from deadlock prevention?
Deadlock avoidance does not restrict resource allocation outright; instead, it requires processes to declare their maximum resource needs in advance. The system then dynamically examines resource-allocation states before granting requests to ensure that the system remains in a safe state where deadlocks cannot occur.
What conditions define a safe state in the context of deadlock avoidance?
A safe state exists if there is a sequence of process execution such that each process can eventually obtain its required resources, complete its execution, and release its resources. In other words, even if a process’s immediate needs aren’t met, the system can allocate resources in an order that guarantees eventual completion for all processes.
How does the system verify whether a resource allocation leaves it in a safe state?
The system simulates the allocation to check if there is an order in which all processes can finish. If the sequence exists (e.g., processes waiting until previous ones complete and release resources), the allocation is safe; if not, it may lead to an unsafe state and potential deadlock.
What is the role of the Banker’s Algorithm in deadlock avoidance for systems with multiple resource instances?
For systems with multiple instances of each resource, the Banker’s Algorithm is used to dynamically assess whether resource allocation requests can be safely granted. It checks if granting a request would leave the system in a safe state, thereby preventing the possibility of a deadlock.
What is the primary idea behind deadlock detection and recovery?
Instead of attempting to prevent deadlocks, deadlock detection allows them to occur and then employs algorithms to identify and resolve the deadlock through recovery mechanisms, such as terminating processes or pre-empting resources.
How does a Wait-For Graph simplify deadlock detection?
A Wait-For Graph is derived from a Resource Allocation Graph by including only the processes and the wait relationships between them. By focusing solely on processes waiting for resources, it simplifies the detection of cycles that indicate deadlocks.
What factors should be considered when deciding how frequently to invoke a deadlock detection algorithm?
Key considerations include the computational overhead of running the algorithm, the likelihood of deadlock occurrences, and the potential cost of rolling back multiple processes. Frequent invocations may immediately identify deadlocks but can be resource-intensive, while infrequent checks might allow complex deadlock cycles to form.
