UMUC CS 412, Sp 97, Deadlocks

 Silberschat and Gavin chapter 7
Tanenbaum, chapter 6
  

Outline

Synchronization

Deadlocks


Background

Example code from two different processes:
These processes cannot run concurrently, some interleavings are not equivalent to T1 T2 T3 U1 U2 U3.
 
Race condition: several processes access and manipulate the same data concurrently, and the outcome depends on the order of manipulations.

Critical section

A section of code of a process in which another process may access the same data.

Mutually exclusive - prevent other processes from accessing a critical section of code when the process is accessing that section of code.

Solution to this problem, requirements:

Two Process Solutions

Algorithm 1 (S, page 167, Figure 6.2):

Algorithm 2 (S, page 168, Figure 6.3):

Algorithm 3 (S, page 169, Figure 6.4):

Multiple processes (S, page 171, Figure 6.5):

Synchronization Hardware

Disable interrupts during critical section

Hardware solution - two atomic hardware instructions:

Semaphores

Spinlock - continuous testing of mutex signal, loop

Alternative - process self-blocks, allowing scheduler to start different process

Use semaphores with a queue of processes waiting on this semaphore

Deadlocks - waiting on intersecting processes and semaphores

Indefinite blocking or starvation - LIFO semaphore queue

Binary semaphores - a number of these can be used to simulate a counting semaphore

Classical problems

Bounded buffer (S, section 6.5.1, page 181): 

Readers and writers

Dining philosophers

Critical regions

Monitors

High-level way of deciding who gets to run and who get resources
Example, dining philosophers, S pages 193 & 194.

Solaris 2

Supports:

Atomic transactions

Typically, database operations
Group operations for all or none operations

System model

Log-based recovery

Concurrent atomic transactions

Locking protocols

Timestamps

Model

Finite number or resources for a number of processes

Cycle: request, use release

Examples:

Characterization

Necessary conditions:

  1. Mutual exclusion - one process at a time
  2. Hold and wait
  3. No pre-emption
  4. Circular wait

Resource allocation graph (S, Page 200, Figure 7.1)

Handling

 Choices:

Topics:

Prevention

 Examine necessary conditions:

Avoidance

 Each process must declare the maximum amount of resource it may require

Safe and unsafe states, example S page 228

Resource allocation graph algorithm (S, pages 230, 231, Figures 7.5, 7.6)

Banker's algorithm

Detection

Single instance of each resource:

Several instances of resources

Usage:

Recovery

 After deadlock detected, then what?

Process termination:

Resource pre-emption:

Combined approach

 Different approaches for different resources, see S, pages 240-241:


End of page