Deadlock Prevention

This method imposes a total order on all resource types in the system. Every agent must request resources in this strictly increasing order. This prevents the circular wait condition, as it's impossible for Agent A to hold Resource 1 and wait for Resource 2 while Agent B holds Resource 2 and waits for Resource 1 if Resource 1 < Resource 2 in the global order.

• Implementation: Assign a unique integer to each resource class (e.g., printer=1, scanner=2, disk drive=3).
• Example: An agent needing a disk drive and a printer must request the printer (1) first, then the disk drive (3). It cannot hold the disk drive and later request the printer.
• Trade-off: Can lead to reduced resource utilization and potential pre-allocation, as agents must request lower-numbered resources they don't yet need to maintain the order.

This method attacks the mutual exclusion condition by designing resources to be shareable whenever possible. If a resource does not require exclusive access, deadlock cannot occur for that resource.

• Applicability: Best suited for read-only resources like data in a cache or immutable files. It is not feasible for resources that inherently require serialized access, such as write operations, actuators, or communication ports.
• Techniques: Use immutable data structures or implement copy-on-write semantics to allow concurrent reads. For example, a configuration file can be loaded into a shared, immutable memory space accessible by all agents.
• Limitation: Many critical resources (mutexes, database records for update, hardware devices) are fundamentally non-sharable, making this method only a partial solution.

This strategy eliminates the hold and wait condition by requiring agents to request all required resources at once (atomic request) before execution begins, or by ensuring an agent holds no resources when it makes a new request.

• Static (One-Shot) Allocation: An agent must declare its maximum resource needs upfront. The system grants all or none. This is simple but leads to severe resource starvation and poor utilization, as resources are locked idle for long periods.
• Dynamic Protocol: An agent must release all currently held resources before making a new request. This can be highly inefficient, as it forces agents to relinquish state and potentially re-acquire resources later, increasing overhead and the risk of livelock.
• Use Case: Often used in batch processing systems where a job's requirements are fully known in advance.

This method counters the no preemption condition by allowing the system to forcibly take resources away from a waiting agent. If an agent's request is denied because the resource is held by another, the system can preempt (roll back or checkpoint) the holding agent, freeing the resource for the requester.

• Mechanism: Requires the ability to save an agent's state (checkpoint) so it can be safely restarted later. The preempted agent is rolled back to its pre-allocation point and must re-request its needed resources.
• Challenges: Introduces significant overhead for state saving/restoration. It is only practical for resources whose state can be easily saved and restored (e.g., CPU registers, memory). It is unsuitable for non-preemptible resources like a mutex in the middle of a critical section or a printer mid-job.
• Relation to Protocols: Forms the basis for the Wait-Die and Wound-Wait protocols, which use transaction timestamps to decide who preempts whom.

This is a dynamic, runtime prevention technique. The system maintains a Wait-For Graph (WFG) where nodes are agents and a directed edge from A to B indicates Agent A is waiting for a resource held by Agent B. The system proactively denies any resource request that would create a cycle in this graph.

• Operation: Before granting a request, the system adds a tentative edge to the WFG. It then runs a cycle detection algorithm (e.g., depth-first search). If a cycle is detected, the request is denied, and the requesting agent must wait without the resource, preventing the circular wait from forming.
• Overhead: Requires continuous maintenance of the graph and cycle checking on every resource request, which can be computationally expensive in systems with many agents and resources.
• Distinction from Detection: This is prevention; the system acts before the deadlock occurs. Deadlock detection allows the cycle to form and then later invokes a recovery routine.

A pragmatic, fault-tolerance-inspired method where agents waiting for a resource are assigned a timeout. If the resource is not acquired within the timeout period, the request is assumed to be part of a potential deadlock, and the agent is forced to release all its held resources, back off, and retry later.

• Implementation: Simple to implement and is common in distributed systems and databases (e.g., SQL Server's lock timeout). It doesn't strictly guarantee deadlock prevention but makes them statistically unlikely and ensures system liveness.
• Advantage: Handles scenarios that formal models miss, such as communication failures or unresponsive agents that mimic deadlock.
• Drawback: Can cause livelock if multiple agents timeout and retry in synchrony. Requires careful tuning of timeout values and backoff strategies (e.g., exponential backoff) to be effective. It is often combined with other methods as a safety net.

Deadlock detection is a reactive strategy that allows a system to enter a deadlocked state but employs a dedicated algorithm to periodically analyze the resource allocation graph (RAG) or wait-for graph to identify cycles. Upon detection, a recovery mechanism (e.g., agent termination or resource preemption) is triggered to break the deadlock. This approach avoids the overhead of prevention but incurs the cost of rollback and potential service interruption.

Deadlock avoidance is a dynamic, predictive strategy that requires agents to declare their maximum future resource needs in advance. Before granting any resource request, the system (e.g., via the Banker's Algorithm) performs a safe state check—a simulation to determine if a sequence exists where all agents can complete without deadlock. If granting the request leads to an unsafe state, the request is delayed. This method is more flexible than prevention but requires a priori knowledge of resource requirements.

These are timestamp-based deadlock prevention schemes used in database systems and applicable to agent resource contention.

• Wait-Die: An older agent (based on timestamp) waits for a resource held by a younger agent. A younger agent requesting a resource held by an older agent is aborted (dies) and restarted.
• Wound-Wait: An older agent preempts (wounds) a younger agent holding a needed resource, forcing it to restart. A younger agent waits if the resource is held by an older agent. Both ensure no circular wait by enforcing a unidirectional wait condition based on agent age.

The Banker's Algorithm is the canonical deadlock avoidance algorithm. It models the system with:

• Available: Vector of available resource instances.
• Max: Maximum demand of each agent.
• Allocation: Resources currently held by each agent.
• Need: Remaining resources each agent may request (Need = Max - Allocation). Before granting a request, it performs a safety algorithm to find a hypothetical sequence (safe sequence) for all agents to finish. If no sequence exists, the request is denied, keeping the system in a safe state and avoiding deadlock.

Pessimistic concurrency control is a broad conflict prevention strategy that assumes conflicts are likely and prevents them using locking mechanisms. Agents acquire locks (e.g., mutexes, read/write locks) on resources before accessing them, blocking other agents until the lock is released. While effective at preventing conflicts like deadlocks (especially with strict two-phase locking), it can severely reduce system throughput and concurrency due to blocking, and requires careful lock ordering to prevent deadlocks.

Optimistic Concurrency Control (OCC) is an alternative to deadlock prevention. It allows agents to proceed with local work without acquiring locks, assuming conflicts are rare. Changes are made to private workspace copies. During a commit phase, a validation step checks for conflicts with other committed transactions. If a conflict is detected, the transaction is rolled back and must be retried. OCC avoids deadlocks entirely (no holding-and-waiting) but suffers overhead from aborts under high contention.