cps 590 chapt 6

Deadlock

A permanent blocking of a set of processes that either compete for system resources or communicate with each other.

Necessary Conditions for Deadlock

The four necessary conditions are: Mutual Exclusion, Hold and Wait, No Preemption, Circular Wait.

Resource Categories

Two categories: Reusable Resources (not depleted) and Consumable Resources (created and destroyed by processes).

Resource Allocation Graph

A directed graph that shows resource allocation and requests between processes and resources.

Deadlock Prevention

Methods to prevent deadlock by eliminating one of the necessary conditions.

Deadlock Avoidance

Dynamically analyzes resource requests to keep the system in a safe state.

Banker’s Algorithm

A deadlock avoidance strategy that simulates resource allocation before granting requests.

Safe State

A system state where at least one sequence of resource allocations allows all processes to complete without deadlock.

Deadlock Detection

Periodically checks for cycles in the resource allocation graph to find deadlocked processes.

Recovery from Deadlock

Main strategies include aborting deadlocked processes, rolling back processes, preempting resources, or killing processes incrementally.

Starvation

A process is indefinitely delayed due to other processes always being given priority for resources.

Dining Philosophers Problem

Illustrates issues of mutual exclusion, deadlock, and starvation in concurrent systems.

UNIX Concurrency Mechanisms

Includes pipes, messages, shared memory, signals, and semaphores for interprocess communication (IPC).

Real-Time Signals in Linux

RT signals differ by priority order, queuing, and can pass values alongside signals.

Spinlocks

Locks that cause a thread to wait in a loop while checking availability; effective for short critical sections.

Atomic Operations

Operations executed without interruption, crucial for preventing race conditions.

Memory Barriers

Instructions that enforce the order of memory operations for correct synchronization.

RCU (Read-Copy-Update)

A synchronization mechanism allowing multiple readers and one writer to access shared data concurrently.

Priority Inversion

When a lower-priority process holds a resource needed by a higher-priority process, causing the latter to wait.

Deadlock vs. Livelock

Deadlock: permanently blocked processes; Livelock: processes constantly changing states without progress.

Deadlock Prevention: No Preemption

Allow resources to be forcibly taken from a process to avoid deadlock.

Deadlock Prevention: Circular Wait

Impose a linear ordering of resource requests to prevent circular wait.

Deadlock Detection Algorithm

Steps to identify deadlocked processes by marking unmarked processes and checking resource availability.

Deadlock Recovery: Process Termination

Approaches include aborting all deadlocked processes or doing so incrementally.

Deadlock Recovery: Resource Preemption

Forcibly taking resources from processes to break deadlocks.

Deadlock in Real-World Systems

Example includes traffic deadlocks at intersections; solutions involve traffic management rules.

Deadlock in Databases

Handled by periodic checks for cycles in the wait-for graph and rolling back transactions to recover.

Deadlock in Distributed Systems

Challenges include lacking global state information and communication delays impacting detection.

Summary of Chapter 6

Key takeaways include deadlock definitions, necessary conditions, strategies, and real-world implications.