Lecture Notes for Operating Systems Concepts

26 October 2004 - Resource Management and Deadlock

Resources

A resource is anything required by a process.
Anything - os as resource manager.
Process - owns the resource.
Required - no resource, no progress; adaptive processes.
Resources - sharable, serially reusable, and consumable.

Resource Management

Resource management - protection, economy, and convenience.
Fairness, policy and mechanism
The deadlock problem

Resource Managers

Generically, most resource managers behave the same way.
Specific differences arise from (mainly) resource characteristics and management policies.
For example:
- Printers can't be shared.
- Non-sharing printer management is inconvenient.

Resource Models

Resource managers model resources abstractly.
- There are u units of the resource available.
- Processes can request up to u units of a resource.
- At any point there are 0 <= a <= u units of resource available.
These and other resource properties are stored in resource descriptors maintained by the resource manager.

Resource Characteristics

A resource's characteristics determine how (in part) it's managed.
A resource can be consumable or reusable.
A reusable resource remains after being used.
- Disks, networks, CPUs are reusable resources.
A consumable resource dissapears after begin used.
- Network packets and IPC messages are consumable resources.

Resource Counts

A static resource has a fixed or slowly changing number of units.
- Disks and CPUs are static resources.
- Reusable resources tend to be static.
A dynamic resource has a varying number of uints.
- Consumable resources necessarily are dynamic.
- They have to be created and consumed.

Dynamic Resources

Dynamic resources can be created by the outside world, the OS or user processes.
Treating static resources as bounded dynamic resources is occasionally useful.
- Managing CPUs on MMP systems.

Resource Sharing

A sharable resource can be used by more than one process at the same time.
- Input devices tend to be sharable resources.
A serially-reusable resource can be used by at most one process at a time.
- Output devices tend to be serially-reusable devices.

General Management

The typical resource management cycle is: request, grant, and release.

Management Refinements

A request may fail, or the requestor could be blocked.
- The requestor is unblocked when the resource is granted.
If the request fails, the requestor can try again later.
Adaptive processes change their request.
- They might ask for less, or a different but similar resource.

Asynchronous Management

Asynchronous resource management provides non-blocking behavior:

The requestor receives a request id.
Querying the request id eventualy indicates a grant or deny.
The requestor can block on the id utill the request is resolved.

Synchronous resource management can also provide query functions.

Because resources are shared, there can be suble race conditions.

A Situation

Suppose exec() blocks the parent until the child has terminated.

Now consider

parent
  cid = exec(1)
  put_slot(cid, 1)

child
  while not get_slot(sid, val)
  put_slot(sid, 2*val)

What happens?

The Situation

Each processes is waiting for something from the other process.
- The parent's waiting for the child to end.
- The child's waiting for a word from the parent.
Each process will never get it.
This situation is known as deadlock.
- (Technically, it's deadlock-like.)

Deadlock Background

Deadlock is an old problem.
- Train track management; traffic gridlock.
Both user processes OSs can cause and suffer from deadlock.
Finite, non sharable resources are the heart of the problem.
Deadlock is a global condition, which makes it difficult to find and deal with.

Deadlock Handling

There are four deadlock handling techniques:
1. Prevention makes deadlock impossible.
2. Avoidance
3. Detect and recover deadlock.
4. Ad hoc techniques.
Historically, ad hoc techniques have prevailed.
- Distributed and networked systems make ad hoc techniques less useful.

Ad Hoc Techniques

Ad hoc techniques, a.k.a. the therapeutic reboot
The traditional technique for handling deadlock (or any other problem).
Detecting when to reboot can be tricky.
- It's awfully quiet in here.
- There's no blinking lights.
May or may not work in distributed environments.

Deadlock Prevention

Deal with deadlock by making it impossible.
- This can be tricky to impossible.
- User processes can always deadlock over their own resources.
The idea is to eliminate the conditions under which deadlock arises.

Deadlock Conditions

The four deadlock conditions:
1. Exclusive resource access; no sharing.
2. Incremental allocation; each allocation a process blocking point.
3. Circular waiting for resources.
4. No take back resource allocation.
These are necessary conditions; if any is missing, deadlock can't occur.

Preventing Deadlock

Avoiding any of the four conditions makes deadlock impossible.
Given two non-sharable resources A and B (one unit each):
P₁ has A and blocks allocating B
P₂ has B and blocks allocating A

This is deadlock. How can it be prevented?

Shared Resources

A shared resource can't cause deadlock.
- Processes use the resource without waiting.
- P₁ doesn't block on B; P₂ doesn't block on A.
Virtualization makes resources sharable.
- A printer is unsharable.
- Virtualizing the printer with a print queue makes it sharable.

Bulk Allocation

Incremental allocation causes two problems:
1. Each allocation request potentially blocks.
2. Previously acquired resources are held during the block.
Give processes one chance to allocate everything.
- P₁ allocates A and B with one request; so does P₂.
  - One of them loses and blocks.

Analysis

Bulk allocation is similar to batch-job allocation policies.

Bulk allocation is difficult to do in general.

Realistic general resource estimates are difficult to make.
Resources may depend on data.

Bulk allocation leads to pessamistic allocation requests.

Better take extra, just in case.

Ordered Allocation

Processes waiting in a cyclic deadlock.
Prevent cycles by
- Totally order the resources.
- A process holding R_i may only allocate R_j for i < j.
Ordered resources allow incremental allocations and are efficient.
- but it's hard finding orders and it's still inconvenient.

Example

Order the resources A then B.
- P₁ requests and gets A.
- P₂ requests A and blocks.
- P₁ requests and gets B.
- P₁ ends, releasing A and B.
- P₂ unblocks with A.

Resource Take-Back

Holding resources while waiting for other resources can cause problems.
A process blocking on a resource must release all previously allocated resources.
- P₁, holding A and blocking on B, must release A.
It is hard writing programs under this condition.
- Databases do something like this (transaction abort).

Deadlock Avoidance

Always monitoring all processes for everything is expensive and restrictive.
As an alternative, a system can be in one of three states:
- Safe: undeadlocked and every request can be granted without deadlock.
- Deadlock: deadlocked and further requests (most likely) add to the deadlock.
- Unsafe: undeadlocked and some requests may lead to deadlock.
The idea is to keep the system in the Safe state and be careful when it wanders into the Unsafe state.

An Analogy

A bank has n customers C₁, C₂, ... C_n.
Each customer has a credit limit Max_i.
Customers may borrow incrementally up to their credit limit.
All customers eventually repay their loans.
Loan are either approved or denied, possibly after an arbitrary delay.

Cash On Hand

How much cash on hand should the bank have to satisfy loans?
One obvious solution: sum(i = 1, n, Max_i).
- But this is expensive and inefficient (low utilization).
A less obvious solution: min(i = 1, n, Max_i).
- This is the cheapest solution and most efficient (for the bank).

The Banker's Algorithm

Given a set of maximum claims, how much is needed to cover - the maximum maximum.
Assumptions - a maximum claim, non-maximum requests, no pre-emption, requests satisfied in any order.
Objective - if no process is maxed, make sure there's always enough on hand to satisfy some maximum.
Procedure - deny any non-maximum request that violates the objective.

Deadlock Detection and Recovery

Model the system and determine if the model indicates deadlock.
This can be a predictive or a reactive approach.
- Don't allow an allocation that the model predicts would cause deadlock.
- Allow any allocation and use the model to determine deadlock.

System State Model

A system state model is a directed graph.
Each state represents some allocation of available resources.
Each edge represents a process's request, allocation, or release.
A state with no outward edges is a deadlock state.
This is a large, expensive representation - exponential in resources.
With one resource this turns into state-based protocol analysis.

Resource Graphs

A resource graph is a directed, bipartite graph.
Each node is either a process or a resource.
Edges indicate requests (from p to r) or allocations (from r to p).
A cycle in the resource graph indicates a deadlock.
Extendible to multiple resources, but with difficulty - knots instead of cycles.

Deadlock Recovery

reboot, selective pre-emption, delete processes, check-point and roll back

This page last modified on 14 November 2004.