Module 2

Processes
 Outline
 Process Concept
 Process Scheduling
 Operations on Processes
 Process Concept
 An operating system executes a variety of programs that run as a
process.
 Process – a program in execution; process execution must progress
in sequential fashion. No parallel execution of instructions of a single
process
 Multiple parts
• The program code, also called text section
• Current activity including program counter, processor registers
• Stack containing temporary data
 Function parameters, return addresses, local variables
• Data section containing global variables
• Heap containing memory dynamically allocated during run time
 Process Concept (Cont.)
 Program is passive entity stored on disk (executable file);
process is active
• Program becomes process when an executable file is
loaded into memory
 Execution of program started via GUI mouse clicks, command
line entry of its name, etc.
 One program can be several processes
• Consider multiple users executing the same program
Process in Memory
Memory Layout of a C Program
 Process State

 As a process executes, it changes state

• New: The process is being created
• Running: Instructions are being executed
• Waiting: The process is waiting for some event to occur
• Ready: The process is waiting to be assigned to a processor
• Terminated: The process has finished execution
Diagram of Process State
 Process Control Block (PCB)
Information associated with each process(also called task
control block)
 Process state – running, waiting, etc.
 Program counter – location of instruction to next
execute
 CPU registers – contents of all process-centric
registers
 CPU scheduling information- priorities, scheduling
queue pointers
 Memory-management information – memory
allocated to the process
 Accounting information – CPU used, clock time
elapsed since start, time limits
 I/O status information – I/O devices allocated to
process, list of open files
 Threads
 So far, process has a single thread of execution
 Consider having multiple program counters per process
• Multiple locations can execute at once
 Multiple threads of control -> threads
 Must then have storage for thread details, multiple program
counters in PCB
 Explore in detail in Chapter 4
 Process Representation in Linux

Represented by the C structure task_struct

pid t_pid; /* process identifier */

long state; /* state of the process */
unsigned int time_slice /* scheduling information */
struct task_struct *parent;/* this process’s parent */
struct list_head children; /* this process’s children */
struct files_struct *files;/* list of open files */
struct mm_struct *mm; /* address space of this
process */
 Process Scheduling
 Process scheduler selects among available processes
for next execution on CPU core
 Goal -- Maximize CPU use, quickly switch processes onto
CPU core
 Maintains scheduling queues of processes
• Ready queue – set of all processes residing in main
memory, ready and waiting to execute
• Wait queues – set of processes waiting for an event
(i.e., I/O)
• Processes migrate among the various queues
Ready and Wait Queues
Representation of Process Scheduling
CPU Switch From Process to Process
A context switch occurs when the CPU switches from
one process to another.
 Context Switch
 When CPU switches to another process, the system must
save the state of the old process and load the saved state
for the new process via a context switch
 Context of a process represented in the PCB
 Context-switch time is pure overhead; the system does no
useful work while switching
• The more complex the OS and the PCB  the longer
the context switch
 Time dependent on hardware support
• Some hardware provides multiple sets of registers per
CPU  multiple contexts loaded at once
 Multitasking in Mobile Systems

 Some mobile systems (e.g., early version of iOS) allow only one
process to run, others suspended
 Due to screen real estate, user interface limits iOS provides for a
• Single foreground process- controlled via user interface
• Multiple background processes– in memory, running, but not
on the display, and with limits
• Limits include single, short task, receiving notification of events,
specific long-running tasks like audio playback
 Android runs foreground and background, with fewer limits
• Background process uses a service to perform tasks
• Service can keep running even if background process is
suspended
• Service has no user interface, small memory use
 Operations on Processes

 System must provide mechanisms for:

• Process creation
• Process termination
 Process Creation

 Parent process create children processes, which, in turn

create other processes, forming a tree of processes
 Generally, process identified and managed via a process
identifier (pid)
 Resource sharing options
• Parent and children share all resources
• Children share subset of parent’s resources
• Parent and child share no resources
 Execution options
• Parent and children execute concurrently
• Parent waits until children terminate
 Process Creation (Cont.)
 Address space
• Child duplicate of parent
• Child has a program loaded into it
 UNIX examples
• fork() system call creates new process
• exec() system call used after a fork() to replace the process’
memory space with a new program
• Parent process calls wait()waiting for the child to terminate
A Tree of Processes in Linux
C Program Forking Separate Process
Creating a Separate Process via Windows API
 Process Termination
 Process executes last statement and then asks the operating
system to delete it using the exit() system call.
• Returns status data from child to parent (via wait())
• Process’ resources are deallocated by operating system
 Parent may terminate the execution of children processes using
the abort() system call. Some reasons for doing so:
• Child has exceeded allocated resources
• Task assigned to child is no longer required
• The parent is exiting, and the operating systems does not
allow a child to continue if its parent terminates
 Process Termination
 Some operating systems do not allow child to exists if its parent
has terminated. If a process terminates, then all its children
must also be terminated.
• cascading termination. All children, grandchildren, etc.,
are terminated.
• The termination is initiated by the operating system.
 The parent process may wait for termination of a child process
by using the wait()system call. The call returns status
information and the pid of the terminated process
pid = wait(&status);
 If no parent waiting (did not invoke wait()) process is a
zombie
 If parent terminated without invoking wait(), process is an
orphan
 Android Process Importance Hierarchy

 Mobile operating systems often have to terminate processes to reclaim

system resources such as memory. From most to least important:
• Foreground process
• Visible process
• Service process
• Background process
• Empty process
 Android will begin terminating processes that are least important.
 Multiprocess Architecture – Chrome Browser

 Many web browsers ran as single process (some still do)

• If one web site causes trouble, entire browser can hang or crash
 Google Chrome Browser is multiprocess with 3 different types of
processes:
• Browser process manages user interface, disk and network I/O
• Renderer process renders web pages, deals with HTML,
Javascript. A new renderer created for each website opened
 Runs in sandbox restricting disk and network I/O, minimizing
effect of security exploits
• Plug-in process for each type of plug-in
Threads
 Motivation

 Most modern applications are multithreaded

 Threads run within application
 Multiple tasks with the application can be implemented by
separate threads
• Update display
• Fetch data
• Spell checking
• Answer a network request
 Process creation is heavy-weight while thread creation is
light-weight
 Can simplify code, increase efficiency
 Kernels are generally multithreaded
Single and Multithreaded Processes
Multithreaded Server Architecture
 Benefits

 Responsiveness – may allow continued execution if part of

process is blocked, especially important for user interfaces
 Resource Sharing – threads share resources of process, easier
than shared memory or message passing
 Economy – cheaper than process creation, thread switching
lower overhead than context switching
 Scalability – process can take advantage of multicore
architectures
 Multicore Programming

 Multicore or multiprocessor systems puts pressure on programmers,

challenges include:
• Dividing activities
• Balance
• Data splitting
• Data dependency
• Testing and debugging
 Parallelism implies a system can perform more than one task
simultaneously
 Concurrency supports more than one task making progress
• Single processor / core, scheduler providing concurrency
 Concurrency vs. Parallelism
 Concurrent execution on single-core system:

 Parallelism on a multi-core system:

 Multicore Programming

 Types of parallelism
• Data parallelism – distributes subsets of the same data
across multiple cores, same operation on each
• Task parallelism – distributing threads across cores, each
thread performing unique operation
Data and Task Parallelism
 User Threads and Kernel Threads

 User threads - management done by user-level threads library

 Three primary thread libraries:
• POSIX Pthreads
• Windows threads
• Java threads
 Kernel threads - Supported by the Kernel
 Examples – virtually all general-purpose operating systems, including:
• Windows
• Linux
• Mac OS X
• iOS
• Android
User and Kernel Threads
 Multithreading Models

 Many-to-One
 One-to-One
 Many-to-Many
 Many-to-One

 Many user-level threads mapped to single kernel thread

 One thread blocking causes all to block
 Multiple threads may not run in parallel on multicore system because
only one may be in kernel at a time
 Few systems currently use this model
 Examples:
• Solaris Green Threads
• GNU Portable Threads
 One-to-One

 Each user-level thread maps to kernel thread

 Creating a user-level thread creates a kernel thread
 More concurrency than many-to-one
 Number of threads per process sometimes restricted due to overhead
 Examples
• Windows
• Linux
 Many-to-Many Model
 Allows many user level threads to be mapped to many kernel threads
 Allows the operating system to create a sufficient number of kernel
threads
 Windows with the ThreadFiber package
 Otherwise not very common
 Two-level Model
 Similar to M:M, except that it allows a user thread to be bound to
kernel thread
CPU Scheduling
 Outline
 Basic Concepts
 Scheduling Criteria
 Scheduling Algorithms
 Objectives

 Describe various CPU scheduling algorithms

 Assess CPU scheduling algorithms based on scheduling criteria
 Apply modeling and simulations to evaluate CPU scheduling
algorithms
 Basic Concepts

 Maximum CPU utilization

obtained with multiprogramming
 CPU–I/O Burst Cycle – Process
execution consists of a cycle of
CPU execution and I/O wait
 CPU burst followed by I/O burst
 CPU burst distribution is of main
concern
 Histogram of CPU-burst Times

Large number of short bursts

Small number of longer bursts

 CPU Scheduler
 The CPU scheduler selects from among the processes in ready
queue, and allocates a CPU core to one of them
• Queue may be ordered in various ways
 CPU scheduling decisions may take place when a process:
1. Switches from running to waiting state
2. Switches from running to ready state
3. Switches from waiting to ready
4. Terminates
 For situations 1 and 4, there is no choice in terms of scheduling. A
new process (if one exists in the ready queue) must be selected
for execution.
 For situations 2 and 3, however, there is a choice.
 Preemptive and Nonpreemptive Scheduling

 When scheduling takes place only under circumstances 1 and

4, the scheduling scheme is nonpreemptive.
 Otherwise, it is preemptive.
 Under Nonpreemptive scheduling, once the CPU has been
allocated to a process, the process keeps the CPU until it
releases it either by terminating or by switching to the waiting
state.
 Virtually all modern operating systems including Windows,
MacOS, Linux, and UNIX use preemptive scheduling
algorithms.
 Preemptive Scheduling and Race Conditions

 Preemptive scheduling can result in race conditions

when data are shared among several processes.
 Consider the case of two processes that share data.
While one process is updating the data, it is preempted
so that the second process can run. The second process
then tries to read the data, which are in an inconsistent
state.
 Dispatcher
 Dispatcher module gives control of the
CPU to the process selected by the CPU
scheduler; this involves:
• Switching context
• Switching to user mode
• Jumping to the proper location in the
user program to restart that program
 Dispatch latency – time it takes for the
dispatcher to stop one process and start
another running
 Scheduling Criteria

 CPU utilization – keep the CPU as busy as possible

 Throughput – # of processes that complete their execution
per time unit
 Turnaround time – amount of time to execute a particular
process
 Waiting time – amount of time a process has been waiting
in the ready queue
 Response time – amount of time it takes from when a
request was submitted until the first response is produced.
 Scheduling Algorithm Optimization Criteria

 Max CPU utilization

 Max throughput
 Min turnaround time
 Min waiting time
 Min response time
 First- Come, First-Served (FCFS) Scheduling

Process Burst Time

P1 24
P2 3
P3 3
 Suppose that the processes arrive in the order: P1 , P2 , P3
The Gantt Chart for the schedule is:

P1 P2 P3
0 24 27 30

 Waiting time for P1 = 0; P2 = 24; P3 = 27

 Average waiting time: (0 + 24 + 27)/3 = 17
 FCFS Scheduling (Cont.)

Suppose that the processes arrive in the order:

P2 , P3 , P1
 The Gantt chart for the schedule is:

P2 P3 P1
0 3 6 30

 Waiting time for P1 = 6; P2 = 0; P3 = 3

 Average waiting time: (6 + 0 + 3)/3 = 3
 Much better than previous case
 Convoy effect - short process behind long process
• Consider one CPU-bound and many I/O-bound processes
 Shortest-Job-First (SJF) Scheduling

 Associate with each process the length of its next CPU burst
• Use these lengths to schedule the process with the
shortest time
 SJF is optimal – gives minimum average waiting time for a
given set of processes
 Preemptive version called shortest-remaining-time-first
 How do we determine the length of the next CPU burst?
• Could ask the user
• Estimate
 Example of SJF

Process Burst Time

P1 6
P2 8
P3 7
P4 3

 SJF scheduling chart

P4 P1 P3 P2
0 3 9 16 24

 Average waiting time = (3 + 16 + 9 + 0) / 4 = 7

 Determining Length of Next CPU Burst

 Can only estimate the length – should be similar to the previous one
• Then pick process with shortest predicted next CPU burst
 Can be done by using the length of previous CPU bursts, using
exponential averaging

 Commonly, α set to ½
Prediction of the Length of the Next CPU Burst
 Examples of Exponential Averaging
  =0
• n+1 = n
• Recent history does not count
  =1
• n+1 =  tn
• Only the actual last CPU burst counts
 If we expand the formula, we get:
n+1 =  tn+(1 - ) tn -1 + …
+(1 -  )j  tn -j + …
+(1 -  )n +1 0

 Since both  and (1 - ) are less than or equal to 1, each successor

predecessor term has less weight than its predecessor
 Shortest Remaining Time First Scheduling

 Preemptive version of SJN

 Whenever a new process arrives in the ready queue, the
decision on which process to schedule next is redone using
the SJN algorithm.
 Is SRT more “optimal” than SJN in terms of the minimum
average waiting time for a given set of processes?
 Example of Shortest-remaining-time-first

 Now we add the concepts of varying arrival times and preemption to

the analysis
Process i Arrival TimeT Burst Time
P1 0 8
P2 1 4
P3 2 9
P4 3 5
 Preemptive SJF Gantt Chart

P1 P2 P4 P1 P3
0 1 5 10 17 26

 Average waiting time = [(10-1)+(1-1)+(17-2)+(5-3)]/4 = 26/4 = 6.5

 Round Robin (RR)
 Each process gets a small unit of CPU time (time quantum q),
usually 10-100 milliseconds. After this time has elapsed, the
process is preempted and added to the end of the ready queue.
 If there are n processes in the ready queue and the time quantum
is q, then each process gets 1/n of the CPU time in chunks of at
most q time units at once. No process waits more than (n-1)q
time units.
 Timer interrupts every quantum to schedule next process
 Performance
• q large  FIFO (FCFS)
• q small  RR
 Note that q must be large with respect to context switch, otherwise
overhead is too high
 Example of RR with Time Quantum = 4

Process Burst Time

P1 24
P2 3
P3 3
 The Gantt chart is:
P1 P2 P3 P1 P1 P1 P1 P1
0 4 7 10 14 18 22 26 30

 Typically, higher average turnaround than SJF, but better response

 q should be large compared to context switch time
• q usually 10 milliseconds to 100 milliseconds,
• Context switch < 10 microseconds
Time Quantum and Context Switch Time
Turnaround Time Varies With The Time Quantum

80% of CPU bursts

should be shorter than q
 Priority Scheduling

 A priority number (integer) is associated with each process

 The CPU is allocated to the process with the highest priority (smallest
integer  highest priority)
• Preemptive
• Nonpreemptive

 SJF is priority scheduling where priority is the inverse of predicted next

CPU burst time

 Problem  Starvation – low priority processes may never execute

 Solution  Aging – as time progresses increase the priority of the

process
 Example of Priority Scheduling

Process Burst Time Priority

P1 10 3
P2 1 1
P3 2 4
P4 1 5
P5 5 2

 Priority scheduling Gantt Chart

 Average waiting time = 8.2

 Priority Scheduling w/ Round-Robin

 Run the process with the highest priority. Processes with the same
priority run round-robin
 Example:
Process a Burst Time Priority
P1 4 3
P2 5 2
P3 8 2
P4 7 1
P5 3 3
 Gantt Chart with time quantum = 2
 Multilevel Queue
 The ready queue consists of multiple queues
 Multilevel queue scheduler defined by the following parameters:
• Number of queues
• Scheduling algorithms for each queue
• Method used to determine which queue a process will enter
when that process needs service
• Scheduling among the queues
 Multilevel Queue
 With priority scheduling, have separate queues for each priority.
 Schedule the process in the highest-priority queue!
 Multilevel Queue

 Prioritization based upon process type

 Multilevel Feedback Queue
 A process can move between the various queues.
 Multilevel-feedback-queue scheduler defined by the following
parameters:
• Number of queues
• Scheduling algorithms for each queue
• Method used to determine when to upgrade a process
• Method used to determine when to demote a process
• Method used to determine which queue a process will enter
when that process needs service
 Aging can be implemented using multilevel feedback queue
 Example of Multilevel Feedback Queue
 Three queues:
• Q0 – RR with time quantum 8 milliseconds
• Q1 – RR time quantum 16 milliseconds
• Q2 – FCFS
 Scheduling
• A new process enters queue Q0 which is
served in RR
 When it gains CPU, the process receives 8
milliseconds
 If it does not finish in 8 milliseconds, the
process is moved to queue Q1
• At Q1 job is again served in RR and
receives 16 additional milliseconds
 If it still does not complete, it is preempted
and moved to queue Q2
Deadlocks
 Outline

 System Model
 Deadlock Characterization
 Methods for Handling Deadlocks
 Deadlock Prevention
 Deadlock Avoidance
 Deadlock Detection
 Recovery from Deadlock
 Objectives

 Illustrate how deadlock can occur when mutex locks are used
 Define the four necessary conditions that characterize deadlock
 Identify a deadlock situation in a resource allocation graph
 Evaluate the four different approaches for preventing deadlocks
 Apply the banker’s algorithm for deadlock avoidance
 Apply the deadlock detection algorithm
 Evaluate approaches for recovering from deadlock
 System Model

 System consists of resources

 Resource types R1, R2, . . ., Rm
• CPU cycles, memory space, I/O devices
 Each resource type Ri has Wi instances.
 Each process utilizes a resource as follows:
• request
• use
• release
 Deadlock with Semaphores

 Data:
• A semaphore S1 initialized to 1
• A semaphore S2 initialized to 1
 Two threads T1 and T2
 T1:
wait(s1)
wait(s2)
 T2:
wait(s2)
wait(s1)
 Deadlock Characterization

Deadlock can arise if four conditions hold simultaneously.

 Mutual exclusion: only one thread at a time can use a

resource
 Hold and wait: a thread holding at least one resource is
waiting to acquire additional resources held by other threads
 No preemption: a resource can be released only voluntarily
by the thread holding it, after that thread has completed its
task
 Circular wait: there exists a set {T0, T1, …, Tn} of waiting
threads such that T0 is waiting for a resource that is held by
T1, T1 is waiting for a resource that is held by T2, …, Tn–1 is
waiting for a resource that is held by Tn, and Tn is waiting for
a resource that is held by T0.
 Resource-Allocation Graph

A set of vertices V and a set of edges E.

 V is partitioned into two types:

• T = {T1, T2, …, Tn}, the set consisting of all the threads
in the system.

• R = {R1, R2, …, Rm}, the set consisting of all resource

types in the system

 request edge – directed edge Ti  Rj

 assignment edge – directed edge Rj  Ti
 Resource Allocation Graph Example

 One instance of R1
 Two instances of R2
 One instance of R3
 Three instance of R4
 T1 holds one instance of R2 and is
waiting for an instance of R1
 T2 holds one instance of R1, one
instance of R2, and is waiting for an
instance of R3
 T3 is holds one instance of R3
Resource Allocation Graph with a Deadlock
Graph with a Cycle But no Deadlock
 Basic Facts
 If graph contains no cycles  no deadlock
 If graph contains a cycle 
• if only one instance per resource type, then deadlock
• if several instances per resource type, possibility of deadlock
 Methods for Handling Deadlocks

 Ensure that the system will never enter a deadlock state:

• Deadlock prevention
• Deadlock avoidance
 Allow the system to enter a deadlock state and then recover
 Ignore the problem and pretend that deadlocks never occur in the
system.
 Deadlock Prevention
Invalidate one of the four necessary conditions for deadlock:

 Mutual Exclusion – not required for sharable resources (e.g.,

read-only files); must hold for non-sharable resources
 Hold and Wait – must guarantee that whenever a thread requests
a resource, it does not hold any other resources
• Require threads to request and be allocated all its resources
before it begins execution or allow thread to request
resources only when the thread has none allocated to it.
• Low resource utilization; starvation possible
 Deadlock Prevention (Cont.)
 No Preemption:
• If a process that is holding some resources requests another
resource that cannot be immediately allocated to it, then all
resources currently being held are released
• Preempted resources are added to the list of resources for which
the thread is waiting
• Thread will be restarted only when it can regain its old resources,
as well as the new ones that it is requesting
 Circular Wait:
• Impose a total ordering of all resource types, and require that each
thread requests resources in an increasing order of enumeration
 Circular Wait

 Invalidating the circular wait condition is most common.

 Simply assign each resource (i.e., mutex locks) a unique number.
 Resources must be acquired in order.
 If:

first_mutex = 1
second_mutex = 5

code for thread_two could not be

written as follows:
 Deadlock Avoidance
Requires that the system has some additional a priori information
available
 Simplest and most useful model requires that each thread declare
the maximum number of resources of each type that it may need
 The deadlock-avoidance algorithm dynamically examines the
resource-allocation state to ensure that there can never be a
circular-wait condition
 Resource-allocation state is defined by the number of available
and allocated resources, and the maximum demands of the
processes
 Safe State
 When a thread requests an available resource, system must
decide if immediate allocation leaves the system in a safe state
 System is in safe state if there exists a sequence <T1, T2, …, Tn>
of ALL the threads in the systems such that for each Ti, the
resources that Ti can still request can be satisfied by currently
available resources + resources held by all the Tj, with j < I
 That is:
• If Ti resource needs are not immediately available, then Ti can
wait until all Tj have finished
• When Tj is finished, Ti can obtain needed resources, execute,
return allocated resources, and terminate
• When Ti terminates, Ti +1 can obtain its needed resources, and
so on
 Basic Facts
 If a system is in safe state  no deadlocks

 If a system is in unsafe state  possibility of deadlock

 Avoidance  ensure that a system will never enter an unsafe state.

Safe, Unsafe, Deadlock State
 Avoidance Algorithms
 Single instance of a resource type
• Use a resource-allocation graph

 Multiple instances of a resource type

• Use the Banker’s Algorithm
 Resource-Allocation Graph Scheme
 Claim edge Ti  Rj indicated that process Tj may request resource
Rj; represented by a dashed line
 Claim edge converts to request edge when a thread requests a
resource
 Request edge converted to an assignment edge when the resource
is allocated to the thread
 When a resource is released by a thread, assignment edge
reconverts to a claim edge
 Resources must be claimed a priori in the system
Resource-Allocation Graph
Unsafe State In Resource-Allocation Graph
 Resource-Allocation Graph Algorithm
 Suppose that thread Ti requests a resource Rj
 The request can be granted only if converting the request edge to an
assignment edge does not result in the formation of a cycle in the
resource allocation graph
 Banker’s Algorithm
 Multiple instances of resources
 Each thread must a priori claim maximum use
 When a thread requests a resource, it may have to wait
 When a thread gets all its resources it must return them in a finite
amount of time
 Data Structures for the Banker’s Algorithm
Let n = number of processes, and m = number of resources types.

 Available: Vector of length m. If available [j] = k, there are k

instances of resource type Rj available

 Max: n x m matrix. If Max [i,j] = k, then process Ti may request at

most k instances of resource type Rj

 Allocation: n x m matrix. If Allocation[i,j] = k then Ti is currently

allocated k instances of Rj

 Need: n x m matrix. If Need[i,j] = k, then Ti may need k more

instances of Rj to complete its task

Need [i,j] = Max[i,j] – Allocation [i,j]

 Safety Algorithm
1. Let Work and Finish be vectors of length m and n, respectively.
Initialize:
Work = Available
Finish [i] = false for i = 0, 1, …, n- 1

2. Find an i such that both:

(a) Finish [i] = false
(b) Needi  Work
If no such i exists, go to step 4

3. Work = Work + Allocationi

Finish[i] = true
go to step 2

4. If Finish [i] == true for all i, then the system is in a safe state
Resource-Request Algorithm for Process Pi
Requesti = request vector for process Ti. If Requesti [j] = k then
process Ti wants k instances of resource type Rj
1. If Requesti  Needi go to step 2. Otherwise, raise error
condition, since process has exceeded its maximum claim
2. If Requesti  Available, go to step 3. Otherwise Ti must wait,
since resources are not available
3. Pretend to allocate requested resources to Ti by modifying the
state as follows:
Available = Available – Requesti;
Allocationi = Allocationi + Requesti;
Needi = Needi – Requesti;
• If safe  the resources are allocated to Ti
• If unsafe  Ti must wait, and the old resource-allocation state
is restored
 Example of Banker’s Algorithm

 5 threads T0 through T4;

3 resource types:
A (10 instances), B (5instances), and C (7 instances)
 Snapshot at time T0:
Allocation Max Available
ABC ABC ABC
T0 010 753 332
T1 200 322
T2 302 902
T3 211 222
T4 002 433
 Example (Cont.)
 The content of the matrix Need is defined to be Max – Allocation

Need
ABC
T0 743
T1 122
T2 600
T3 011
T4 431

 The system is in a safe state since the sequence < T1, T3, T4, T2, T0>
satisfies safety criteria
 Example: P1 Request (1,0,2)
 Check that Request  Available (that is, (1,0,2)  (3,3,2)  true
Allocation Need Available
ABC ABC ABC
T0 010 743 230
T1 302 020
T2 302 600
T3 211 011
T4 002 431

 Executing safety algorithm shows that sequence < T1, T3, T4, T0, T2>
satisfies safety requirement

 Can request for (3,3,0) by T4 be granted?

 Can request for (0,2,0) by T0 be granted?

 Deadlock Detection

 Allow system to enter deadlock state

 Detection algorithm

 Recovery scheme
 Single Instance of Each Resource Type
 Maintain wait-for graph
• Nodes are threads
• Ti  Tj if Ti is waiting for Tj

 Periodically invoke an algorithm that searches for a cycle in the

graph. If there is a cycle, there exists a deadlock

 An algorithm to detect a cycle in a graph requires an order of n2

operations, where n is the number of vertices in the graph
Resource-Allocation Graph and Wait-for Graph

Resource-Allocation Graph Corresponding wait-for graph

 Several Instances of a Resource Type

 Available: A vector of length m indicates the number of available

resources of each type
 Allocation: An n x m matrix defines the number of resources of
each type currently allocated to each thread.
 Request: An n x m matrix indicates the current request of each
thread. If Request [i][j] = k, then thread Ti is requesting k more
instances of resource type Rj.
 Detection Algorithm

1. Let Work and Finish be vectors of length m and n, respectively

Initialize:
a) Work = Available
b) For i = 1,2, …, n, if Allocationi  0, then
Finish[i] = false; otherwise, Finish[i] = true

2. Find an index i such that both:

a) Finish[i] == false
b) Requesti  Work

If no such i exists, go to step 4

 Detection Algorithm (Cont.)
3. Work = Work + Allocationi
Finish[i] = true
go to step 2

4. If Finish[i] == false, for some i, 1  i  n, then the system is in

deadlock state. Moreover, if Finish[i] == false, then Ti is
deadlocked

Algorithm requires an order of O(m x n2) operations to detect

whether the system is in deadlocked state
 Example of Detection Algorithm
 Five threads T0 through T4; three resource types
A (7 instances), B (2 instances), and C (6 instances)

 Snapshot at time T0:

Allocation Request Available
ABC ABC ABC
T0 010 000 000
T1 200 202
T2 303 000
T3 211 100
T4 002 002

 Sequence <T0, T2, T3, T1, T4> will result in Finish[i] = true for all i
 Example (Cont.)

 T2 requests an additional instance of type C

Request
ABC
T0 000
T1 202
T2 001
T3 100
T4 002

 State of system?
• Can reclaim resources held by thread T0, but insufficient resources
to fulfill other processes; requests
• Deadlock exists, consisting of processes T1, T2, T3, and T4
 Detection-Algorithm Usage
 When, and how often, to invoke depends on:
• How often a deadlock is likely to occur?
• How many processes will need to be rolled back?
 one for each disjoint cycle

 If detection algorithm is invoked arbitrarily, there may be many cycles

in the resource graph and so we would not be able to tell which of the
many deadlocked threads “caused” the deadlock.
 Recovery from Deadlock: Process Termination

 Abort all deadlocked threads

 Abort one process at a time until the deadlock cycle is eliminated
 In which order should we choose to abort?
1. Priority of the thread
2. How long has the thread computed, and how much longer to
completion
3. Resources that the thread has used
4. Resources that the thread needs to complete
5. How many threads will need to be terminated
6. Is the thread interactive or batch?
 Recovery from Deadlock: Resource Preemption

 Selecting a victim – minimize cost

 Rollback – return to some safe state, restart the thread for
that state
 Starvation – same thread may always be picked as victim,
include number of rollback in cost factor