CIS 307: Mutual Exclusion and Critical Regions

These topics are treated very nicely in Tanenbaum section 2.2. Here we examine the kind of reasoning involved in achieving mutual exclusion by software means in a tightly-coupled computer system. Most of the code appears in Silberschatz et al: Operating Systems Concepts.

[Introduction], [Solution 1], [Solution 2], [Solution 3], [Petersen Solution], [Bakery Algorithm]

Introduction

We are examining the question of how to implement Critical Regions by software means using shared variables. We will assume that the code of a process has the form: ..... loop ....... CRITICAL_REGION ....... forever .... [Remember that a Critical Region is a code segment that, with respect to similar CRs, is executed atomically. We assume that processes DO NOT die within CRs. Of course this is an unwarranted assumption. What it means is that the issue of dead processes within a CR is dealt by separate mechanisms that have nothing to do with concurrency, for instance, by timed checks. We also assume, and this is reasonable, that if there are no explicit reasons for a process not to execute, it will eventually execute for at least a while. ]
[We use above the word "process" in an informal way. Technically, processes usually have distinct address spaces, while in the algorithms discussed in this section we have shared variables. Perhaps instead we should say "threads", but for historical reasons we continue to use "process".]
We want to define some global variables, local variables, and PROLOGUE and EPILOGUE procedures to be invoked respectively before and after the CRITICAL_REGION so that the behavior intended for CRs is achieved.
Until we say otherwise, we assume that we have two processes P0 and P1 that execute as follows: cobegin P0: loop .... PROLOGUE CRITICAL_REGION EPILOGUE ... forever P1: loop .... PROLOGUE CRITICAL_REGION EPILOGUE ... forever coend;

Solution 1

Global integer variable turn initialized to 0; Process Pi, where i is 0 or 1, has local integer variable i with value 0 for P0 and 1 for P1; PROLOGUE: while turn <> i do null; EPILOGUE: turn := 1-i; Solution 1 is a bad solution because it is possible to have a process indefinitely waiting for another process that has no desire to enter the critical region. This is a case of lack of progress since we have a process waiting while no one is in the critical region.

Solution 2

Global boolean array variable flag with two components both initialized to false; Process Pi, where i is 0 or 1, has local integer variable i with value 0 for P0 and 1 for P1; PROLOGUE: while flag[1-i] do null; flag[i] := true; EPILOGUE: flag[i] := false; Solution 2 is a bad solution because it does not guaranty mutual exclusion. Why?

Solution 3

Global boolean array variable flag with two components both initialized to false; Process Pi, where i is 0 or 1, has local integer variable i with value 0 for P0 and 1 for P1; PROLOGUE: flag[i] := true; while flag[1-i] do null; EPILOGUE: flag[i] := false; Solution 3 is a bad solution because it may result in deadlock. Why?

Petersen Solution

Global integer variable turn initialized to 0; Global boolean array variable flag with two components both initialized to false; Process Pi, where i is 0 or 1, has local integer variable i with value 0 for P0 and 1 for P1; PROLOGUE: flag[i] := true; turn := 1-i; while flag[1-i] and (turn = (1-i)) do null; EPILOGUE: flag[i] := false; In order for this to be a good solution you need to worry about the following issues:

Mutual Exclusion. You should be able to show that the assumption that two processes are simultaneously in critical regions leads to a contradiction.
Progress: if two processes try to enter the critical region, one will enter the region. You should be able to argue that if two processes are trying to enter the critical region, there will be no explicit reason for one of them not to enter.
Bounded Waiting: No process that is trying to enter the critical region should have to wait indefinitely while other processes enter more than once. Here you should be able to analyze the scenario: P0 and P1 try to enter the critical region; P0 enters, exits, tries to enter again. Who enters at this point?

There is no obvious way of generalizing the Petersen solution to the case of more than 2 processes.

Bakery Algorithm

This algorithm, due to Leslie Lamport, implements CRs for any number of concurrent processes, say, P0, P1, .. Pn-1

GLOBAL VARIABLES: choosing: a boolean array with n positions initialized to false; its ith position is true when the ith process wants to select a new number. number: an integer array with n positions initialized to 0; its ith position contains the bakery number for the ith process. We assume a function MAX that returns the largest value found in number by looking in succession to positions 0, 1, .., n-1; This function can be invoked concurrently by any process. LOCAL VARIABLES of process Pi: i : an integer that identifies this process; j : a loop control variable PROLOGUE: 1. choosing[i] := true; 2. number[i] := MAX(number) + 1; 3. choosing[i] := false; 4. for j from 0 to n-1 do 5. begin 6. while choosing[j] do null; 7. while number[j] <> 0 and 8. ((number[j] < mumber[i]) or 9. (number[j] = number[i] and j < i)) do 10. null; 11. end; EPILOGUE: number[i] := 0;

Notes:

Choosing[i] is true only while process Pi is trying to select a number in statement 2.
Number[i] is non zero only after process Pi has selected a number and is either waiting to enter the critical region or in it.
If process Pi and Pj are executing the prologue concurrently and are after statement 2. and we have number[j] < number[i] then process Pj will enter the critical region before Pi. However it is possible for number[j] to be equal to number[i]. This may happen because the evaluation of MAX(number) in Pi and Pj occurs before the assignment to number[i]. In this case where number[i] is equal to number[j] the tie between Pi and Pj is broken by giving precedence to the process with smaller subscript.

Could you state the reason why statement 6. is required?

ingargiola.cis.temple.edu