Operating Systems Lecture Notes

Outline

An operating system manages physical or virtual resources.
- Network interfaces, mailboxes.
A process requests resources from the OS.
The OS grants or denies the resource request.
The process returns the resource to the OS.
- All via appropriate system calls.
Resource scheduling.

resource state transitions

Resource scheduling is a general problem.
- Similar to CPU scheduling.
Deadlock focuses on allocation and deallocation.
- Other scheduling matters come up as needed.
The problem: deadlock-cognizant resource scheduling.

Based on allocation behavior, there are three general resource types:
1. Sharable: many concurrent allocations. Clock.
2. Sequential: single allocation repeatedly. Computing engine.
3. Consumable: single allocation once. Network packet.
Mostly sequential resources are of interest.

A resource-allocation graph models a system’s resource state.
Graph nodes represent process and resources.
Resource nodes represent sequential resources.
- Dots in a resource node represent identical resource instances.

a resource-allocation graph

A set of processes P₁, P₂, … is deadlocked if
- Each P_i is blocked on a resource allocation.
- None of the requested resources will ever be granted.
Processes in deadlock never unblock.

Two processes execute

P1:
   allocate(printer)
   allocate(camera)

P2:
   allocate(camera)
   allocate(printer)

a deadlock

Unmediated concurrent access to shared resources? I know how to fix that!

mutex cameraMutex(true)
mutex printerMutex(true)

t₁:
   take(printerMutex)
   take(cameraMutex)

   allocate(printer)
   allocate(camera)

t₂:
   take(cameraMutex)
   take(printerMutex)

   allocate(camera)
   allocate(printer)

Deadlocked processes exhibit four properties:
1. Only sequential resources involved.
2. Failed allocations block.
3. Non-pre-emptable allocated resources.
4. A cycle of allocations and requests.
Be careful not to work the implication backwards.
- A system exhibiting all four properties may not be deadlocked.

The four deadlock conditions are necessary but not sufficient for deadlock to occur.

Deadlock reduces utilization.
- Resources held by deadlocked processes.
- All resources devoted to permanently blocked processes.
Large deadlocks from little deadlocks grow.
Without care, important subsystems may deadlock.
- Up to and including the operating system.

There are four approaches to dealing with deadlock:
1. Prevention — not on my watch.
2. Avoidance — don’t drive into potholes.
3. Recovery — a bandage will fix that right up.
4. Faith — and a big stick.
When not relying on faith, systems usually use several approaches.

Faith: It can’t happen here. And if it does, we’ll just restart everything.

A: The system seems to be running slow.

B: Guess it’s time for a therapeutic reboot.
Faith seems irresponsible and expensive, but
- Other deadlock handling techniques are more expensive and disruptive.
- Deadlock is a global property among all sequential resources in the system.

A process set stalled over resource access is deadlocked.
Deadlock is a consequence of ill-considered resource management.
Deadlock exhibits four characteristic properties.
- Blocking, exclusive access, non-pre-emption, and cycles.
There are four general approaches for handling deadlock.
- Prevention, avoidance, recover, and faith.

This page last modified on 2011 October 9.