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

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

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

ingargiola.cis.temple.edu