Operating Systems Lecture Notes

27 February 2012 • Allocation and Deadlock

---

Outline

• Resources
• Resource management.
• 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 defined by policy and provided by 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 and expensive.

Resource Models

• Resource managers model resources abstractly.
  • There are u units of the resource available.
  • Processes request up to u resource units.
  • There are always 0 ≤ a ≤ u resource units 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.
• There are lots of possible characteristics.
  • Resource durability: reusable vs consumable.
  • Resource multiplicity: static vs dynamic.
  • Resource sharing:

Resource Durability

• Resource durability determines how a resource reacts to being used.
• 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 Multiplicity

• 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 units.
  • Consumable resources necessarily are dynamic.
  • They have to be created and consumed.

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 until the request is resolved.
• Synchronous resource management can also provide query functions.
  • Sharing can lead to suble race conditions.

Set-Up

• A system has one unit each of resources A and B allocated synchronously.
• Two threads concurrently execute

  t1:		a = request(A)
  		b = request(B)
  t2:		b = request(B)
  		a = request(A)

  What happens?

Analysis

• The resulting allocations depend on the threads’ interleaving.

  Case 1 t1: a = request(A) t1: b = request(B) t2: b = request(B) t2: a = request(A) Ok

  Case 2 t1: a = request(A) t2: b = request(B) t1: b = request(B) t2: a = request(A) ?

• Case 1 seems fine, but what about case 2?

Deadlock

Each thread holds a resource needed by the other thread.

• Each thread relies on the other thread to make progress.
• Each thread can't make progress because of the other thread.
• This is the deadlock condition.

Deadlock Background

• Deadlock is an old problem.
  • Train track management; traffic gridlock.
• Both user processes and 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. Prevent deadlock.
  2. Avoid deadlock.
  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 quiet in here, too quiet.
  • There’s no blinking lights, or the they're blinking too fast.
• 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):

  t₁ has A and blocks allocating B
  t₂ 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.
  • t₁ doesn’t block on B; t₂ 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 may block.
  2. Previously acquired resources are held during the block.
• All allocations made at once without interruption.
  • t₁ allocates A and B with one request; so does t₂.
    • 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 pessimistic 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.
  • t₁ requests and gets A.
  • t₂ requests A and blocks.
  • t₁ requests and gets B.
  • t₁ ends, releasing A and B.
  • t₂ 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.
  • t₁, 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, characterize the possibility of the system falling into deadlock.
  • No or low possibility: allocate away.
  • Otherwise, allocate with caution to avoid deadlock.

System States

• 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.
• 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: max(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.
• Maintaining an accurate model can be difficult, although analysis is easy.

Deadlock Recovery

• An organized ad hoc mechanism.
• Wait for the system to deadlock, then recover.
• Lots of recovery techniques:

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

• Detection is hard, recovery is mostly crude.

Summary

• Resource management responds to resource characteristics.
  • And management policies.
• Deadlock represents an uncorrdinated coordinated resource management failure.
• Deadlocks can be recovered from, avoided, or prevented.
• Deadlocks can be avoided by sharing, pre-emption, ordering, or one fell swoop.

---

This page last modified on 2011 October 9.