First Come First Serve Mutual Exclusion Computer Science Essay

Published: Last Edited:


The paper is about closing the complexity gap between First Come First Serve mutual exclusion and mutual exclusion. Mutual exclusion is nothing but it allows the processes to acquire the shared resources in a safe manner. In other words Mutual exclusion means that if one process is using a shared resource then the other process is exempted from accessing that particular resource. First-Come-First-Served (FCFS) mutual exclusion (ME) make sure that processes trying to acquire a shared resource simultaneously acquire the resource in a fair order. The authors try to reduce the complexity gap between FCFS ME and ME by showing that the number of remote memory references a process use per passage lies in between O(min(k,logN)) and compares this algorithm to the previous algorithm proposed by many authors. K is nothing but the point contention.


The difference between Mutual exclusion (ME) and First come First serve Mutual exclusion (FCFS ME) is that in a mutual exclusion processes are allowed to access shared resource in a safe manner. ME is a way of making sure that processes that if one process is using a shared modifiable data, the other processes will be excluded from doing the same thing. It does not take care about the ordering of the processes. FCFS ME on the other hand make sure that processes are allowed to access shared resource in a fair order. In FCFS ME each and every process is given equal priority. Providing access to processes to acquire shared resources is the common problem which a raises during the programming of multiprocessors. ME is the approach used to address the problem of providing access to multiple processes to acquire shared resources safely. The processes are asynchronous that is they operate at different speeds. The gap which is present between First Come First Serve Mutual Exclusion and Mutual Exclusion in shared memory model is closed by assuming that processes communicate using read and write operations only. A mutual exclusion algorithm consists of trying protocol(TP) and exit protocol(EP) both of which surround the critical section(CS). If a process has completed the execution of trying protocol, critical section and exit protocol once is called as a passage. If a process is no more in one of the TP,CS,EP steps then the process is said to be in non critical section(NCS). The TP and EP make sure that at minimum one process is present in the CS. The TP and EP make sure that process requested a resource is allocated that resource. The properties of ME are:

Mutual Exclusion (ME) : No process is allowed to enter into the critical section simultaneously when a process is executing in a critical section.

Lockout Freedom (LF) : A process which entered into the trying protocol enters critical section in the course of time.

Bounded Exit (BE) : If a process has called the Exit protocol then it returns to the non critical section in a finite number of steps.

The processes should not simultaneously make calls to trying protocol and the exit protocol at the same time. The processes should make calls to trying protocol and exit protocol one after another. Processes should follow correct calling order that is the processes should begin with trying protocol and end with the exit protocol.

These properties could not prevent the situations where a processes has been in the trying protocol for a long time but could not able enter into the CS where the other processes are frequently entering into the CS this is not fair so ME algorithm which allows every process to enter into the CS is chosen. The fairness is provided by FCFS ME algorithm where every process in the system is allowed to enter into the CS the series the processes enter into the system at the beginning. In other words the processes are allowed to enter into the CS in the order they execute the trying protocol. The trying protocol is classified into two parts:

1) Doorway.

2) Waiting room.

The doorway has the code to arrange the processes which entered into the system according to FCFS order. The processes are executed in the same order. The time complexity is generally measured by the number of times a process makes access to memory resources during a passage in mutual exclusion. But in the case of asynchronous shared memory model a process makes access to memory resources unlimited number of times during busy-wait condition while waiting to leave the critical section by other process. So, the time complexity is calculated by the adding up the RMR performed during passage. The memory accesses are classified as local or remote. The two memory models used are distributed memory model(DSM) and cache coherent memory model(CC).

In case of distributed memory model each process is given a memory module which the process itself can access locally while the other processes are provided access to it remotely. In cache coherent model the other process can access the memory module locally as the contents in the cache coherent model are stored in a local cache which is updated regularly. Usually the complexity of a mutual exclusion algorithm by using RMR depends up on the processes waiting for entry into the critical section execution. This is quantity is defined by point contention. A mutual exclusion algorithm whose complexity increases with point contention is called adaptive mutual exclusion algorithm. Point contention is nothing but the number of processes waiting outside the non critical section during the execution of a fragment. In FCSFS ME the worst case complexity performed by atomic read and write is less than the normal mutual exclusion algorithm.

In case of the adaptive mutual exclusion algorithm the performance of the algorithm decreases as the point contention increases. The first FCFS ME algorithm was solved and given by lamport in his famous Bakery algorithm. The Remote Memory Reference(RMR) complexity given by Yang and Anderson is O(log N).


Common notations used in FCFS mutual exclusion algorithm are processes followed by step and then histories. Process defines execution path for accessing the shared variables in an order. The state of the process is nothing but the automation accord to that process which implies the process takes the local snapshot which represents its local state. The value read or written into the shared variable represents the step of a process. And a transition in a process Local state is depends on the value it has read and the step of encoding depends the value written into the shared variable and the variable accessed. The state of the process is given by the local states of all processes in the system and the values set into these shared variables. There is a program counter which determines the process next step. A execution history refers to periodic sequence steps and it refers to the states that start with opening state. The states in a system are numbered beginning from 0. This process is called indexing which used to identify each state in the execution history. This indexing does not occupy memory and are not executed by the process. The notation P@i denotes process p next step is the execution of the line i. The building blocks used in this algorithm have a familiar property for example consider two functions S1 and S2 these functions must be accessed by the processes in an alternating sequence a process p is said to be in building block if it calls to S1 first and then followed by the function S2.

FCFS algorithm and high-level description

When a process enters into the TP in the doorway phase it obtains a ticket from dispenser after obtaining a ticket from ticket dispenser the process enters into the waiting room. Dispenser is not atomic so every process is given identical ticket whenever it invokes ticket dispenser. In the waiting room the process gets add itself to the priority queue and waits till it becomes the top in the queue. When it becomes the head of the queue the process executes in Critical Section and after process is done with Critical Section it executes the exit protocol and informs the other process which is next to it to advance. To serialize the operations on the priority queue the algorithm has auxiliary lock. The priority queue has operations like Insert, Find Min, Remove. Remove operation has no effect if there are no items in the queue. The priority queue entries are usually in the form of (process_ID,ticket).

All processes uses head which is a Boolean Array which is used to let know other process when it eventually becomes the front of the queue. Dummy tickets are used in this algorithm to prevent or avoid race condition. For example let consider two processes 'a 'and 'b'. process 'a' has completed the execution of the doorway before process 'b' started the execution of the doorway. According to FCFS property process b should enter the CS after the process 'a' has done with the execution of the CS. But till process 'a' is added to priority queue process 'b' from the state of the priority queue cannot tell it should enter into the critical section before process 'b'. In order to stop process 'b' from entering CS before process 'a' dummy tickets and special set are used. In the doorway process 'b' add itself to the set.

After doorway process 'b' enters the doorway where it removes itself from the set and finds if there is another process in set. If there is any such process, process 'b' adds "a' with dummy ticket (a,-1). The insertion of process 'a' into the priority queue ensures that 'a' is at the head of the queue. After acquiring the auxiliary lock the dummy ticket is replaced by a proper ticket and the process enters into the critical section. And after the execution of CS, it clears itself from top of the queue and findmin() function is used to find the id of the processes whose ticket is minimum among all processes. Special set is used to store the ID's of all the processes in the system. Priority queue P stores the process in the form of a binary tree whose complexity is O(log N). In other mutual exclusion algorithms the RMR complexity increases as the number of processes increases in the system. In the case of FCFS Mutual Exclusion algorithm shown below the complexity always lies between or the algorithm takes minimum value between min(k,log N). The Remote Memory Refrence complexity of the algorithm is O(min(k,log N)).k refers point contention which describes the processes waiting for the Critical Section during the execution of a fragment. A special set is used to store the process id in a set which is at first is empty.

All the processes perform operations on the set by adding or removing their ID's by

INSERTSELF() and REMOVESELF(). The calls in the special set must be made by any processes in an follow sequence starting with INSERTSELF(). A process is said to be in the set if it has finished executing INSERTSELF() but not to REMOVESELF(). The operation REMOVESELF() is executed in a mutual exclusion manner. The ticket dispenser is used to issue tickets to the processes. Tickets are acquired by calling OBTAINTICKET() and when the process completed its execution it execute DONEWITHTICKET(). The algorithm is given by

First Come First Serve mutual exclusion algorithm for process a âˆˆ {1â€¦..N}


Shared Variables:

Set: Special set

P: priority queue

Head is a array [1â€¦â€¦â€¦..N] of type Boolean

Private variables:

ticket: integer

temp: integer








if temp!= âŠ¥ then

P.Insert ((temp,-1))

P.Remove (P,-1)





await Head[a]:=true






if temp!= âŠ¥ then



end loop

(AS mentioned in the paper)

Special set is implemented in the leaf acquisition problem. In this problem every process has admittance to Root of the tree T. whenever a process obtains a leaf it carry out some operations on the leaf which are related to it. After the completion of the computation it releases the leaf so the process which is in need of the leaf can easily attain it. The process of acquiring and releasing of the leaf are done by functions ACQLEAF(),RELELEAF() respectively. Every process access root T with a branching factor. The processes are allowed calls to ACQLEAF() and RELLEAF() in an varying sequence starting with ACQLEAF(). A Call made to ACQLEAF() by a process does nothing but it yields the id of the leaf correlated to. The complexity of the leaf acquisition problem is determined by step complexity and the depth complexity. The method RELLEAF() is executed in a ME manner. Kim and Anderson adaptive mutual exclusion algorithm has composing blocks that operates in same way as leaf acquisition problem. This algorithm uses a complete binary tree whose depth is given by M = [log N] which is denoted by T. As soon as a process exits the non critical section the starting step it do is find out a node in root T as described in algorithm. The process over and again executes the step direction=acquirenode(n).

The function passed to the acquirenode(n) is nothing but id of node which the process is attempting to acquire and the value returned is of the form left,right,stop. If the process gets the return value as stop, implies that the process has acquired the node which it has been trying. The process has control over the node till it executes the EP. For example If the process is unable to get the node which it is trying to acquire, the id which it got indicates the branch it has to follow in order to get another requested node which it is trying to obtain. Path[level]=(node,direction) is used to record the path followed by the process in the tree. During the exit protocol the process first cleans up the nodes which it has visited in the trying protocol in the tree.

The complexity of this algorithm is O(min(k,log N)). The complexity is obtained from the fact that ACQNODE(), RELNODE(), CLEARNODE() each of which has the step complexity given by O(1). If a process acquires a node in a tree then no other process can acquire the node till that node is released by the process which has obtained previously that is till it executes the exit protocol. The algorithm in case of mutual exclusion was proposed first by KIM and ANDERSON.



M= [log N]

Private variables:

n,l,i,j : integer // n=node, l=level ,p=path

direction: one of (left,right,stop)

p:array[0â€¦â€¦M] of record(n:integer;direction:one of (left,right,stop))








if dir=left then



else if direction=right then



until l > M V direction = stop

if l<=M then

for j:=l downto 0 do

ENT3(p[j].n,p[j].dir) //ENT=ENTRY






For j:=min(l,M) downto 0 do




If level<=L then


for j:=0 to l do






end loop


If a process tumble to the depth of the binary tree it executes the TP of non-adaptive ME algorithm. According to ME property, the ENT3 procedure can be completed successfully by maximum one process particular the root T. After finishing execution the process calls ENT2(0). In case if a process tumble to the bottom of the tree and if it has finished ENTN calls ENT2(1). The values that is passed to ENT2 which is either 0 or 1 is the ID the process accept during the process of execution of two process ME algorithm.

The implementation of ObtainTicket() and DoneWithTicket() is


Shared variables

Tkt:array[0â€¦â€¦.2N-1] of {INUSE,FREE}

Initially Tkt[0â€¦.N-1]=FREE and Tkt[Nâ€¦.2N-1}=INUSE

LastTicket:integer 0â€¦.2N-1,initially 2N-1


ticket:integer 0â€¦.2N-1, uninitialized

FUNCTION ObtainTicket()



while i<N and Tkt[(first+i) mod 2N] = INUSE do



last:=first +i


while first < last do


if Tkt[midpoint mod 2N]= INUSE then






ticket:=first mod 2N


return ticket

FUNCTION DoneWithTicket()

Tkt[(ticket+N mod 2N]:=FREE



The method DoneWithTicket () is executed in a ME manner. The method ObtainTicket() is used to find the next ticket which is free.If a free ticket has been found then the method ObtainTicket() searches for the least ticket. The ticket which is obtained is stored in a ticket which is declared as private.


The correctness of the First come First Serve Mutual Exclusion is divided into two main parts. The two parts of proof includes special set and other is the ticket dispenser.The first part is that the special set used in algorithm functions according to the conditions that the calls are made to the functions InsertSelf() and RemoveSelf() are executed in a correct order starting with InsertSelf().

The operation RemoveSelf() is accomplished in a mutual exclusion manner. The proof of first part is further classified into three parts. The first section is to prove that the algorithm follows first come first serve order. This is can be illustrated by a process which is first able to acquire ObtainTicket() before another process start to acquire the same function tells the first process which has obtained the ticket first enters into the critical section early than other the process which has obtained ticket late. This shows that the processes follow the first come first serve order. In other words, the process which has entered and finished the doorway enters the critical section than the process which is entering the doorway phase. The second section part of the proof is that the algorithm satisfies the lockout freedom property. This can be illustrated by proving that deadlock freedom holds and using the proof that the algorithm follows the First come first serve we can say that the property of lock out freedom also applies. The third section is that the algorithm satisfies the properties mutual exclusion and bounded exit.

The algorithm satisfies all the cases so the remote memory reference complexity is calculated. After all the calculations in mutual exclusion the Remote Memory Reference complexity is given by order of minimum of k,logN that is O(min(K,logN)