Operating Systems Day 06

Problems that arise when many processes compete for relatively few resources and the system is unable to service all of the processes. In particular, there are two extreme conditions: deadlock and starvation which result from a lack of process synchronization.

Problems may arise if the system is unable to service all of the processes in a synchronous manner.

Deadlock is more serious than starvation because it affects more than one job. There are seven cases of deadlock.

1. Case 1: Deadlocks on File Requests. Deadlock from multiple process file requests occurs because of jobs being allowed to hold files for the duration of their executions.
2. Case 2: Deadlocks in Databases. Deadlock may occur if two processes access and lock records in a database. The concept of locking within a database whereby one user locks out all other users while working with the database.
3. Case 3: Deadlocks in Dedicated Device Allocation. Deadlock may occur if there are a limited number of dedicated devices and many more processes requesting them.
4. Case 4: Deadlocks in Multiple Device Allocation. Deadlock may occur with multiple device allocations utilizing different device types when several processes request and hold dedicated devices while other processes act in a similar manner.
5. Case 5: Deadlocks in Spooling. Deadlock may occur if a sharable device, such as a spooling printer that requires all job output before initiating printing, encounters a full spool disk area with only partially completed output residing on it.
6. Case 6: Deadlocks in a Network. Deadlock in a network resulting from the absence of network protocols to control message flow.
7. Case 7: Deadlocks in Disk Sharing. 

Deadlock occurs due to over-commitment of resources. Four conditions that need to be simultaneously present for deadlock to occur: mutual exclusion, resource holding, no preemption, and circular wait. Each of these four individual conditions is necessary for the operating system to work smoothly, and none of them can be removed easily without causing the system’s overall functioning to suffer. Therefore, the system needs to recognize the combination of conditions before they occur and threaten to cause the system to lock up.

Starvation occurs when allocation of resources is restricted.

When a starvation occurs, a job never completes because a requested resource is not allocated.

Causes of Deadlock

1. Deadlock occurs due to over-commitment of resources

There are four methods for dealing with deadlocks: prevention, avoidance, detection, recovery.

Directed graphs are used to model the four simultaneous conditions necessary for deadlock.

In directed graphs, a solid arrow from a resource to process represents process is holding the resource.

Avoidance: the dynamic strategy of deadlock avoidance that attempts to ensure that resources are never allocated in such a way as to place a system in an unsafe state.

Circular wait: one of four conditions for deadlock through which each process involved is waiting for a resource being held by another; each process is blocked and can’t continue, resulting in deadlock.

Mutual exclusion: one of four conditions for deadlock in which only one process is allowed to have access to a resource.

Process synchronization: (1) the need for algorithms to resolve conflicts between processors in a multiprocessing environment; or (2) the need to ensure that events occur in the proper order even if they are carried out by several processes.

Race: a synchronization problem between two processes vying for the same resource.

Starvation: the result of conservative allocation of resources in which a single job is prevented from execution because it’s kept waiting for resources that never become available.

The following figure shows a deadlock event using a directed graph.

Use Directed graphs

• Circles represent processes
• Squares represent resources
• Solid arrow from resource to process
• Process holding resource
• Solid arrow from a process to resource
• Process waiting for resource
• Arrow direction indicates flow
• Dashed arrow indicates Process requests Resource

Cycle in graph indicates deadlock condition

Point out that deadlock results from the liberal allocation of resources, while starvation results from conservative allocation of resources.

Strategies for handling deadlocks

1. Prevention: prevent one of four neccessary deadlock conditions (i.e. no preemption, circular wait, mutual exclusion, resource holding) from occuring
2. Avoidance
3. Detection

References 

1. McHoes, A., & Flynn, I.M. (2008). Understanding operating systems (5th ed.). CENGAGE Learning.  
2. Melbourne Institute of Technology (Semester 1, 2012). BN104 Operating Systems Lecture Notes.