Introduction Processes Inter Process Communication Deadlocks Memory Management

File Systems Protection and Security I/O Systems

1. Introduction

   processes are blocked, waiting on events that could never happen
   different from starvation ( the associated resource is in continuous use )

2. System Model
   A system consists of a finite number of resources to be distributed among a number of competing processes.
   Resources can only be used by a single process at any single instance of time
   Resources can be of different types, e.g. memory space, CPU cycles, files, I/O devices
   A process must request a resource before using it, and must release the resource after using it
   A normal operation consists of a sequence of events:

   • Request: if request cannot be granted immediately, process must wait until it can acquire the resource
   • Use: operate on the resource ( e.g. printing )
   • Release: release the resource

     Examples:

     open file, read file, close file
     allocate memory, use memory, free memory
   A set of processes is in a deadlock state when every process in the set is waiting for an event that can be caused by onother process in the set.

3. Deadlock modeling

   Four necessary conditions for deadlock:

   • mutual exclusion -- only one process at a time can use the resource
   • hold and wait -- there must exist a process that is holding at least one resource and is waiting to acquire additional resources that are currently being held by other processes.
   • no preemption -- resources cannot be preempted; a resource can be released only voluntarily by the process holding it.
   • circular wait -- {P₀, P₁, ..., P_n }

     P₀ waits for resources held P₁
     P₁ waits for resources held P₂
     ......
     P_n-1 waits for resources held P_n
     P_n waits for resources held P₀
     

   e.g. Resources are two books: Java Programming, OS Principles,
          need the two books to finish project

   Resource-allocation graphs

   the process is holding the resource

   the process is requesting the resource

   cycle ~ deadlock
   

   

   Deadlock

   if graph contains no cycles => no process is in deadlock

   if graph contains cycles => deadlock may exist

   Reduction of Resource Graph

   If a process's resource requests can be granted, then we say that the graph can be reduced by that process
   ( i.e. the process is allowed to complete its execution and return all its resources )

   If a graph can be reduced by all the processes, then there is no deadlock.
   If a graph cannot be reduced by all the processes, the irreducible processes constitute the set of deadlock processes in the graph An example of reduction of an RAG ( Resource Allocation Graph )
   
   Example of RAG with cycle but no deadlock
   

   A deadlock example in Java:

   DeadlockExamp.java

4. Deadlock handling strategies
   Ignore the problem altogether
   Prevention -- use a protocol to ensure that the system will never enter a deadlock state
   Detection and recovery -- allow the system to enter a deadlock state and then recover
   Dynamic avoidance -- by careful resource allocation

   a) The Ostrich Algorithm

   pretend there's no problem ( Windows, UNIX )
   undetected deadlock may result in deterioration of the system performance; eventually, the system will stop functioning and will need to be restarted manually

   b) Detection and Recovery

   system monitors requests and releases resources

   check resource graph to see if cycle exists; kill a process if necessary

   or if a process has been blocked for, say one hour, kill it

   c) Deadlock Prevention

   mutual exclusion
   printer cannot be shared by 2 processes
   read-only file -- sharable
   A process never has to wait for a sharable resource
   In general, it is not possible to prevent deadlocks by denying mutual-exclusion condition

   Hold and wait
   have all processes request all their resources before start execution -- inefficient, also, process don't know in advance resources needed

   before a process can request any additional resources, it must release temporarily all the resources that it currently holds, if successful, it can get teh original resources back
   may have starvation

   No preemption
   allows preemption
   OH, what if its printer

   Circular wait

   order resource types
   process requests resources in an increasing order

   Let R = { R₁, R₂, ..., R_m } be the set of resource types

   F: R → N ( set of natural numbers )

   e.g.

   F ( tape drive ) = 1
   F ( disk drive ) = 5
   F ( printer ) = 12

   Suppose a process first requests R_i, it can request R_j only if F(R_j) > F(R_i)

   Under this constraint, circular-wait condition cannot hold

   Proof

   by contradiction

   Suppose circular wait holds for
   { P₀, P₁, ..., P_n }

   P_i is waiting for R_i which is held by P_i+1

   Because P_i+1 is holding R_i while requesting R_i+1, we have

   F( R_i ) < F( R_i+1 ) for all i
   => F( R₀ ) < F( R₁ ) < ... < F( R_n ) < F( R₀ )
   => F( R₀ ) < F( R₀ )
   

   which is impossible.
   Thus circular wait does not exist.

   d) Deadlock Avoidance

   In prevention strategy, we restrain how request can be made.

   Here, we want to develop an algorithm to avoid deadlock by making the right choice all the time

   Banker's Algorithm for Single Resource Type

   Dijkstra's Banker's Algorithm is an approach to trying to give processes as much as is possible, while guaranteeing no deadlock.

   safe state -- a state is safe if the system can allocate resources to each process in some order and still avoid a deadlock.

   bank:

   credits available = 10 units
   Process	Using ( allocated )	Maximum needs
   P0	0	6
   P1	0	5
   P2	0	4
   P3	0	7

   At time t₀, the system is safe.

   At time t₁:

   credits available = 2 units
   Process	Using ( allocated )	Maximum needs	Maximum requests
   P0	1	6	5
   P1	1	5	4
   P2	2	4	2
   P3	4	7	3

   credits left = 2 ( i.e. available = 2 ), state is still safe

   delay any requests from P₀, P₁, P₃

   can grant further requests to P₂, why?

   ---

   credits available = 1 unit
   Process	Using ( allocated )	Maximum needs	Maximum requests
   P0	1	6	5
   P1	2	5	3
   P2	2	4	2
   P3	4	7	3

   This is an unsafe state; with only one credit left, if all processes request their maximum units, all need to be blocked and wait → deadlock

   Of course, unsafe state may not lead to deadlock but the bank cannot count on this.

   The banker's algorithm is to consider each request as it occurs,
   if granting the request would result in a safe state, request is granted
   otherwise, it is postponed

   Resource Trajectories

   A deadlock path

   

   • P2 requests R2
   • The OS grants the request of P2
   • P1 requests R1
   • The OS grants the request of P1
   • P2 requests R1
   • The OS cannot grant the request of P2, because R1 is locked.
   • P1 requests R2
   • The OS cannot grant the request of P1, because R2 is locked.
   • No further progress is possible, i.e. we have a deadlock.

   An avoidance path

   

   • P2 requests R2
   • The OS grants the request of P2
   • P1 requests R1
   • The OS postpones granting the request of P1, because it would lead to an unsafe state.
   • P2 requests R1
   • The OS grants the request of P2
   • P2 releases R1
   • The OS grants the request of P1 for R1
   • P1 requests R2
   • The OS cannot grant the request of P1, because it R2 is still locked by P2.
   • P2 releases R2
   • The OS grants the request of P1 for R2
   • P1 releases R2
   • P1 releases R1

5. Banker's Algorithm for Multiple Resource Type

   Let

   n = # of processes in system
   m = # of resource types

   Example

   

   	a b c d
   EXISTING =	( 6 3 4 2 )
   POSSESSED =	( 5 3 2 2 )
   AVAILABLE =	( 1 0 2 0 )

   Notation

   for two vectors X, Y of length m,
   X ≤ Y if and only if X[i] ≤ Y[i]   for all i = 1, 2, ..., m

   e.g. A = ( 1, 7, 3, 2 ), and B = ( 0, 3, 1, 1 ) then B ≤ A

   X < Y if X ≤ Y and X ≠ Y
   i.e. at least one element of X is strictly smaller than the corresponding element of Y

   Safe Algorithm

   1. Assume m resource types, n processes
      define two matrices
      AVAILABLE = ( ... )   of length m

      TERMINATE = ( ... )   of length n

   2. initialize
      AVAILABLE = available resources

      TERMINATE[i] = false   for i = 1, 2, .. n ( i.e. no process is terminated )

   3. look for an i such that
      a. TERMINATE[i] = false     ( consider one element of TERMINATE )
      b. NEED[i] ≤ AVAILABLE     ( consider one row of NEED )

      if no such i exists, ( i.e. either all terminated or may lead to deadlock ), go to step 5

   4. Set
      TERMINATE[i] = ture     ( i.e. we can run the process to the end )
      AVAILABLE = AVAILABLE + ALLOCATED[i]     ( the terminated process can return all the resources )
      go to step 3

   5. if TERMINATE[i] == true for all i, the system is safe, otherwise it is not safe

   In our example, is the state safe ?

   Now suppose P5 wants 2 c ( e.g. printers )

   Suppose we grant the 2 c to P5, will the state be safe? Let's check:

   ALLOCATED=

   3 0 1 1 0 1 0 0 1 1 1 0 1 1 0 1 0 0 2 0

   NEED =

   1 1 0 0 0 1 1 2 3 1 0 0 0 0 1 0 2 1 0 0

   Available = (

   1

   0

   0

   0

   )

   Then the remaining resources ( AVAILABLE ) are not sufficient to satisfy the max need of any process to run to the end. Thus the state is not safe. Therefore the request of P5 must not be granted at this moment.

   Note that an unsafe state does not necesarily lead to deadlock.

   Weaknesses of the Banker's Algorithm

   requires users to state their maximum needs in advance

   required fixed number of resources to allocate

   requires population of users fixed

   requires all tasks return all resources within a finite time