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 to execute, it will eventually execute for at least a while. ]
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 indefinite postponement. Why?

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 successions
		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