OS ch 5

Consequences of Poor Synchronization

• Deadlock: Two processes stuck waiting for each other.

• Livelock: Two processes keep reacting to each other but don’t make progress.

• Starvation: A process waits forever because resources never free up.

Deadlock affects

• the whole system, not just one job. Worse in real-time systems.

Modeling Deadlocks with Directed Graphs

• Circle = process, Square = resource.

• Solid arrow: Resource held by process.

• Dashed arrow: Process waiting for resource.

• Cycle in graph = deadlock!

Examples of Deadlocks

• File Requests: Two programs need each other’s files = deadlock.

• Databases: Two users lock records and wait for each other.

• Dedicated Device Allocation: Two processes want two devices but get blocked.

• Multiple Devices: 3 programs each waiting on a different device (scanner, printer, plotter).

• Spooling: Not enough disk space for printer jobs = deadlock.

• Disk Sharing (Livelock): Disk arm moves back and forth endlessly.

Conditions for Deadlock

• Mutual Exclusion: Only one process can use a resource at a time.

• Resource Holding: Hold one resource, wait for another.

• No Preemption: Can't take resources back.

• Circular Wait: Chain of processes each waiting for another.

Deadlock Detection Using Graphs

• If there’s a cycle → deadlock.

• If you can reduce the graph by removing finished processes → no deadlock.

Strategies to Handle Deadlocks First Step

Prevention

• Mutual exclusion: Share resources (e.g., spooling printers).

• Resource holding: Request all resources at once.

• No preemption: Allow OS to take back resources.

• Circular wait: Order resources so they’re requested in a sequence.

Strategies to Handle Deadlocks Second Step

Avoidance

• Use Banker’s Algorithm (Dijkstra, 1965):

  • Like lending money: don't give out resources unless it's safe.

  • Avoid unsafe states where deadlock might happen.

Strategies to Handle Deadlocks Third Step

Detection

• Build graphs.

• Detect cycles.

• If deadlock → recover.

Strategies to Handle Deadlocks Fourth Step

Recovery

• Terminate all jobs (extreme!).

• Terminate only involved jobs.

• Preempt resources from non-deadlocked jobs.

• Choose a victim based on least damage (ex: don't kill high-priority jobs).

Starvation

• A job never gets resources.

• Happens due to very cautious resource allocation.

• Solution: Aging — gradually increase priority the longer a job waits.

Example: Dining Philosophers Problem — if one philosopher never gets two forks, they starve.