OS LU6

Process Management Overview

• This lecture covers process management, focusing on deadlocks and strategies to handle them.

Learning Objectives

• Describe causes of system deadlock and livelock.
• Explain the difference between preventing and avoiding deadlocks.
• Outline methods to detect and recover from deadlocks.
• Explain process starvation and its detection/recovery.
• Define a race condition and how to prevent it.
• Differentiate between deadlock, starvation, and race conditions.

Deadlock

• Is a "deadly embrace"
• System resource sharing includes memory management and processor sharing.
• Occurs when many programs compete for limited resources.
• Results from a lack of process synchronization.
• Two or more jobs in a HOLD state.
• Jobs wait for unavailable resources.
• System comes to a standstill.
• Requires external intervention to resolve.
• Starvation: Infinite postponement of a job

Key Definitions

• Deadlock: Two or more jobs wait for resources held by another job, creating a cycle.
• Starvation: A job is indefinitely blocked from resources, preventing its execution.

Analogy

• Bob and Jack both want to play with the same ball.
• If only one can play at a time, Bob must wait for Jack, illustrating normal resource utilization.

Deadlock Implications

• It's more serious than starvation due to indefinite postponement.
• The entire system becomes affected where all resources become unavailable.
• Traffic jams are a real-world example.
• Deadlocks are more prevalent in interactive systems and can quickly become critical.
• There is no quick fix

Deadlock Cases

• Nonsharable/non-preemptable resources are allocated to jobs requiring the same resources.
• Resource types locked by competing jobs include:
• File requests.
• Databases.
• Dedicated device allocation.
• Multiple device allocation.
• Spooling.
• Network.
• Disk sharing.

Case 1: Deadlocks on File Requests

• Occurs when jobs request and hold files.
• Example: Two programs (P1, P2) and two files (F1, F2).
• Deadlock Sequence:
• P1 has access to F1 and requires F2.
• P2 has access to F2 and requires F1.
• Deadlock remains until a program is withdrawn or forcibly removed and the file is released.
• Other programs requiring F1 or F2 will be put on hold.

Case 2: Deadlocks in Databases

• Occurs when two processes access and lock database records.
• Locking Techniques:
• One user locks out all other users.
• Three locking levels: entire database, subsection, or individual record.
• Example: Processes P1 and P2 need to update records R1 and R2.
• Deadlock Sequence:
• P1 accesses and locks R1.
• P2 accesses and locks R2.
• P1 requests R2, but it is locked by P2.
• P2 requests R1, but it is locked by P1.
• Race Conditions:
• Occur when locking is not used, causing incorrect data.
• Depend on process execution order.

Case 3: Deadlocks in Dedicated Device Allocation

• Limited dedicated devices lead to deadlock.
• Example: Two programs each need two tape drives, but there are only two in the system.
• Deadlock Sequence:
• P1 requests and gets tape drive 1.
• P2 requests and gets tape drive 2.
• P1 requests tape drive 2, but it’s blocked.
• P2 requests tape drive 1, but it’s blocked.

Case 4: Deadlocks in Multiple Device Allocation

• Several processes request dedicated devices
• Example: Three programs and three dedicated resources (tape drive, printer, and plotter.
• Deadlock sequence:
  • P1 requests and gets tape drive.
  • P2 requests and gets printer.
  • P3 requests and gets the plotter.
  • P1 requests printer, but is blocked.
  • P2 requests plotter, but is blocked.
  • P3 requests tape drive, but is blocked.

Case 5: Deadlocks in Spooling

• Spooling systems with virtual devices (e.g., printer) can lead to deadlock.
• Disk accepts output from several users.
• Serves as temporary storage.
• Output resides in disk until printer accepts job data.
• Deadlock sequence:
• The printer needs all job output before printing.
• The spooling system fills disk space.
• No one job has entire print output in the spool area.
• This results in partially completed output for all jobs, leading to deadlock.

Case 6: Deadlocks in a Network

• Deadlocks can occur in a network without message flow control.
• Example: Seven computers on a network.
• Deadlock sequence:
• All available buffer space fills.

Case 7: Deadlocks in Disk Sharing

• Conflicting commands send competing processes
• Conflict scenario: disk access with two processes.
• Processes wait for I/O requests, one at cylinder 20, the other at cylinder 310.
• Deadlock sequence:
• An I/O request is not satisfied
• The device puts the request on hold, attempting to fulfill the other request.
• Livelock results.

Conditions for Deadlock

• Four conditions must simultaneously to occur:
• Mutual exclusion: Only one process can access a resource at a time.
• Resource holding: A process holds resources while waiting for others.
• No preemption: Resources cannot be forcibly taken away from a process.
• Circular wait: Each process is waiting for a resource held by the next process in a cycle.
• All four must occur for deadlock.
• Resolution requires removing one of these conditions.

Graph Theory

Mutual Exclusion

• Each resource is either available or exclusively assigned to one process.

Resource Holding

• A process holding resources requests another resource.

No Preemption

• Resources granted cannot be forcibly taken away; they must be explicitly released.

Circular Wait

• A circular chain of two or more processes, each waiting for a resource held by the next.

Modeling Deadlocks

• Directed graphs model deadlocks.
• Circles represent processes.
• Squares represent resources.
• Solid arrow from resource to process indicates resource holding.
• Solid arrow from process to resource indicates the process waiting for a resource.
• Arrow direction indicates flow.
• Cycle in graph indicates deadlock.

Three Graph Scenarios to Detect Deadlocks

• System has three processes (P1, P2, P3) and three resources (R1, R2, R3).
• Scenario 1: No Deadlock: Resources are released before the next process requests.
• Scenario 2: Deadlock: Processes are waiting for resources held by another.
• Scenario 3: No Deadlock: Resources released before deadlock can occur.

Strategies for Handling Deadlocks

Prevention

• Preventing one of the four necessary conditions.

Avoidance

• Avoiding deadlock if it becomes likely.

Detection

• Detect deadlock when it occurs.

Recovery

• Resume system normalcy quickly and gracefully.

Deadlock Prevention

• Mutual Exclusion: Ensure resources are never exclusively assigned.
• Hold and Wait: Require processes to request all resources before execution or to release held resources.
• No Preemption: Ensure resources taken away, if necessary.
• Circular Wait: Processes are only entitled to one resource.

Prevention Assessment

Benefits

• It eliminates conditions

Complications

• Every resource cannot be eliminated from every condition.
• Mutual exclusion; must allocate exclusively. Resource holding
• Bypassed if jobs request every resource at creation.
• Multiprogramming degree id significantly decreased
• Idle peripheral devices. No preemption
• Okay if job state is saved and restored. Circular wait
• Bypassed if the OS prevents circle formation.
• It requires hierarchical ordering.

Problems with the prevention approach

• Resource allocation anticipation
• All users must be satisfied

Avoidance

• Used if conditions cannot be removed.
• The system knows ahead of time and uses Dijkstra's Bankers Algorithm.
• Regulates resources allocation to avoid deadlock.

Banker's Algorithm Rules:

• No customer loans exceeding bank's total capital. Customer given maximum credit limit. Customer allowed to borrow over limit. Sum of all loans is not exceed total capital. Unsafe State: A state where the bank cannot grant all credit lines.

Operating system protocols for deadlock avoidance:

• Never satisfy request if job state moves from safe to unsafe.
• Identify job with the lowest # of remaining resources.
• Is available=> number needed to complete?
• Request blocked if safe
• Request jeapordizes safe st

Banker Analysis

• Jobs must state their number of resources.
• Number is constant
• Number of jobs must remain
• Overhead cost, bad resource number

Detection

• Build directed resource graphs and look for cycles
• Algorithms detect circularity
• Remove process using current resources and not waiting for one Remove process waiting for one resource class Not fully allocated Repeat steps until all connecting lines removed

Recovery

• Attempt to untangle deadlock
• Terminate system
• Restart all jobs from beginning
• Only terminate involved
• Ask to resubmit
• Terminate each one until it breaks

Starvation

• Job prevented execution of services-
• Waiting never be allocate -"The Dining Philosophers" by Dijkstra
• Starvation
• Implement how job waiting
• block until satisfied

Summary

• The operating system dynamically allocates resources.
• The operating system avoids deadlock and starvation
• Remove will will deadlocks
• Avoid supports

Avoid

• Prevent safe and utillzed
• All must support from deadlocks

Explore the key characteristics distinguishing deadlocks from starvation. Learn about the conditions necessary for deadlocks, such as resource holding and no preemption. Understand how deadlocks affect system performance and strategies for resolution and prevention.