Chapter 6Concurrency: Deadlock and Starvation

Operating Systems: Internals and Design Principles Chapter 6 Concurrency: Deadlock and Starvation Seventh Edition By William Stallings

Operating Systems: Internals and Design Principles When two trains approach each other at a crossing, both shall come to a full stop and neither shall start up again until the other has gone. Statute passed by the Kansas State Legislature, early in the 20th century. A TREASURY OF RAILROAD FOLKLORE, B. A. Botkin and Alvin F. Harlow

Deadlock The permanent blocking of a set of processes that either compete for system resources or communicate with each other A set of processes is deadlocked when each process in the set is blocked awaiting an event that can only be triggered by another blocked

process in the set Permanent No efficient solution Potential Deadlock I need quad C and B

I need quad D and A I need quad B and C I need quad A and B

Actual Deadlock HALT until D is free HALT until A is free HALT until C is free

HALT until B is free Joint Progress Diagram No Deadlock Example Resource Categories

Reusable can be safely used by only one process at a time and is not depleted by that use processors, I/O channels, main and secondary memory, devices, and data structures such as files, databases, and semaphores Consumable one that can be created (produced) and destroyed (consumed) interrupts, signals, messages, and information in I/O buffers

Reusable Resources Example Example 2: Memory Request Space is available for allocation of 200Kbytes, and the following sequence of events occur: P1

... P2 ... Request 80 Kbytes; Request 70 Kbytes; Request 60 Kbytes; Request 80 Kbytes;

... Deadlock ... occurs if both processes progress to their second request Consumable Resources Deadlock

Consider a pair of processes, in which each process attempts to receive a message from the other process and then send a message to the other process: Deadlock occurs if the Receive is blocking Deadlock Detection

, Preventio n, and Avoidanc e Resource Allocation Graphs Resource Allocation Graphs Conditions for Deadlock

Mutual Exclusion Hold-andWait only one process may use a resource at a time a process

may hold allocated resources while awaiting assignmen t of others No Preemption no resource can be forcibly

removed from a process holding it Circular Wait a closed chain of processes exists, such that

each process holds at least one resource needed by the next process in the chain Dealing with Deadlock

Three general approaches exist for dealing with deadlock: Prevent Deadlock adopt a policy that eliminates one of the conditions Avoid Deadlock make the appropriate dynamic choices based on the current state of resource allocation

Detect Deadlock attempt to detect the presence of deadlock and take action to recover Deadlock Prevention Strategy Design a system in such a way that the possibility of deadlock is excluded

Two main methods: Indirect prevent the occurrence of one of the three necessary conditions Direct prevent the occurrence of a circular wait Deadlock Condition Prevention Mutual

Exclusion if access to a resource requires mutual exclusion then it must be supported by the OS Hold and Wait require that a process request

all of its required resources at one time and blocking the process until all requests can be granted simultaneously Deadlock Condition Prevention

No Preemption if a process holding certain resources is denied a further request, that process must release its original resources and request them again OS may preempt a lower priority process and require it to release its resources Circular Wait define a linear ordering of resource types

Deadlock Avoidance A decision is made dynamically whether the current resource allocation request will, if granted, potentially lead to a deadlock Requires knowledge of future process requests Two Approaches to

Deadlock Avoidance Resource Allocation Denial do not grant an incremental resource request to a process if this allocation might lead to deadlock

Deadlock Avoidanc e Process Initiation Denial do not start a process if its demands might lead to deadlock Resource Allocation

Denial Referred to as the bankers algorithm State of the system reflects the current allocation of resources to processes

Safe state is one in which there is at least one sequence of resource allocations to processes that does not result in a deadlock Unsafe state is a state that is not safe Determination of a Safe State

State of a system consisting of four processes and three resources Allocations have been made to the four processes Amount of existing resource s

Resources available after allocation P2 Runs to Completion P1 Runs to Completion P3 Runs to

Completion Thus, the state defined originally is a safe state Determination of an Unsafe State Deadlock Avoidance Logic

Deadlock Avoidance Logic Deadlock Avoidance Advantages It is not necessary to preempt and rollback processes, as in deadlock detection It is less restrictive than deadlock prevention

Deadlock Avoidance Restrictions Maximum resource requirement for each process must be stated in advance Processes under consideration must be independent and with no synchronization

requirements There must be a fixed number of resources to allocate No process may exit while holding resources Deadlock Strategies

Deadline Detection Algorithms A check for deadlock can be made as frequently as each resource request or, less frequently, depending on how likely it is for a deadlock to occur Advantages: it leads to early detection the algorithm is relatively simple Disadvantage

frequent checks consume considerable processor time Deadlock Detection Algorithm Recovery Strategies Abort all deadlocked processes

Back up each deadlocked process to some previously defined checkpoint and restart all processes Successively abort deadlocked processes until deadlock no longer exists Successively preempt resources until deadlock no

longer exists Dea dloc k Appr oach es Dining Philosophers Problem No two philosophers

can use the same fork at the same time (mutual exclusion) No philosopher must starve to death (avoid deadlock and starvation) Using Semaphores S ol

ut io ns Cont. A Second Solution . . . Solution Using A Monitor UNIX Concurrency

Mechanisms UNIX provides a variety of mechanisms for interprocessor communication and synchronization including: Pipes Circular buffers allowing two processes to communicate on the producerconsumer model

first-in-first-out queue, written by one process and read by another Messages A block of bytes with an accompanying type UNIX provides msgsnd and msgrcv system calls for processes to engage in message passing

Associated with each process is a message queue, which functions like a mailbox Shared Memory Fastest form of interprocess communication

Common block of virtual memory shared by multiple processes Permission is read-only or read-write for a process Mutual exclusion constraints are not part of the shared-memory facility but must be

provided by the processes using the shared memory Semaphores Generalization of the semWait and semSignal primitives no other process may access the semaphore until all operations have completed

Signa ls A software mechanism that informs a process of the occurrence of asynchronous events similar to a hardware interrupt, but does not employ priorities

A signal is delivered by updating a field in the process table for the process to which the signal is being sent A process may respond to a signal by: performing some default action executing a signal-handler function ignoring the signal

UNIX Signa ls Linux Kernel Concurrency Mechanism Includes all the mechanisms found in UNIX plus:

Atomic Operations Atomic operations execute without interruption and without interference Simplest of the approaches to kernel synchronization

Two types: Linux Atomic Operatio ns Spinlocks Most common technique for protecting a critical section in Linux

Can only be acquired by one thread at a time any other thread will keep trying (spinning) until it can acquire the lock Built on an integer location in memory that is checked by

each thread before it enters its critical section Effective in situations where the wait time for acquiring a lock is expected to be very short Disadvantage: locked-out threads continue to execute in a busywaiting mode Linux Spinlocks

Semapho res User level: Linux provides a semaphore interface corresponding to that in UNIX SVR4 Internally: implemented as functions within the kernel and are more efficient than user-visable semaphores Three types of kernel semaphores: binary semaphores

counting semaphores reader-writer semaphores Linux Semaphores Barriers

enforce the order in which instructions are executed Table 6.6 Linux Memory Barrier Operations Synchronization Primitives Solaris

Data Structu res Mutual Exclusion (MUTEX) Lock Used to ensure only one thread at a time can access the resource protected by the mutex

The thread that locks the mutex must be the one that unlocks it A thread attempts to acquire a mutex lock by executing the mutex_enter primitive Default blocking policy is a spinlock

An interrupt-based blocking mechanism is optional Semaphores Readers/Writer Locks Allows multiple threads to have simultaneous read-only access to an object protected by the lock

Allows a single thread to access the object for writing at one time, while excluding all readers when lock is acquired for writing it takes on the status of write lock if one or more readers have acquired the lock its

status is read lock Condition Variables Windows 7 Concurrency Mechanisms Windows provides synchronization among threads as part of the object architecture

Wait Functions Table 6.7 Windows Synchronizati on Objects Critical Sections Similar mechanism to mutex except that critical sections can be used only by the threads of a single

process If the system is a multiprocessor, the code will attempt to acquire a spin-lock as a last resort, if the spinlock cannot be acquired, a dispatcher object is used to block the thread so that the kernel can dispatch another thread onto the processor Slim Read-Writer

Locks Windows Vista added a user mode reader-writer The reader-writer lock enters the kernel to block only after attempting to use a spin-lock

It is slim in the sense that it normally only requires allocation of a single pointer-sized piece of memory Condition Variables Windows also has condition variables The process must declare and initialize a CONDITION_VARIABLE

Used with either critical sections or SRW locks Used as follows: 1. acquire exclusive lock 2. while (predicate()==FALSE)SleepConditionVariable()

3. perform the protected operation 4. release the lock Lock-free Synchronization Windows also relies heavily on interlocked operations for synchronization interlocked operations use hardware facilities to

guarantee that memory locations can be read, modified, and written in a single atomic operation Deadlock: the blocking of a set of processes that either compete

for system resources or communicate with each other blockage is permanent unless OS takes action may involve reusable or consumable resources Summary Consumable = destroyed when acquired by a process Reusable = not depleted/destroyed by use

Dealing with deadlock: prevention guarantees that deadlock will not occur detection OS checks for deadlock and takes action avoidance analyzes each new resource request

Recently Viewed Presentations

  • Chapter-3


    Velocity of a projectile and the shape of its trajectory. Trajectory is an inverted parabola.
  • Hardware Support for Code Integrity in Embedded Processors

    Hardware Support for Code Integrity in Embedded Processors

    CPE 619 Monitors Aleksandar Milenković The LaCASA Laboratory Electrical and Computer Engineering Department The University of Alabama in Huntsville
  • The Late Middle Ages

    The Late Middle Ages

    EUROPEAN MEDIEVAL TOWNS AND TRADE ROUTESItalian city-states and cities of the Hanseatic League dominated trade in western Europe during the late Middle Ages. Merchants from Venice and Genoa brought silks and spices from the eastern Mediterranean to northern markets, where...
  • Lecture 6 Multiple Regression - California State University ...

    Lecture 6 Multiple Regression - California State University ...

    X predicts Y through Z Mediation C is the total effect of X on Y A*B is the indirect effect C' is the direct effect Mediation 4 steps to establishing mediation (Baron and Kenny/ Regression Method) Establish x predicts y...
  • Technology in Classroom Yelena Mejova and Viet Ha

    Technology in Classroom Yelena Mejova and Viet Ha

    Technology in Classroom Yelena Mejova and Viet Ha Thuc


    The controller view displays all information on the sitrep and allows an admin or a controller to review, edit and publish sit reps. SERT Situation Report. Click to edit Master text styles. Second level. Third level. Fourth level. Fifth level....
  • Lesson 14: Starting Dc Motors - Engineering | SIU

    Lesson 14: Starting Dc Motors - Engineering | SIU

    Blocked or locked rotor current depends on E a and R. a At start-up, E a =0since n = 0 so, R a. low to minimize lossesso I a. high at startDc motor starting methods: 1.) reduced armature voltage. 2.)...
  • Statistical Method for long-range forecast

    Statistical Method for long-range forecast

    Statistical Methods for long-range forecast By Syunji Takahashi Climate Prediction Division JMA Statistical Methods for long-range forecast By Syunji Takahashi Climate Prediction Division JMA We can easily calculate the trend and may be you know how to, So I introduce...