MCS-041 Solved Assignment (Question 4)

Study and implement the Lamport’s Bakery Algorithm for Interprocess synchronization using C/C++ programming language.

In Detail: 

One decentralized algorithm in common use, for example, in bakeries, is to issue numbers to each customer. When the customers want to access the scarce resource (the clerk behind the counter), they compare the numbers on their slips and the user with the lowest numbered slip wins.

The problem with this is that there must be some way to distribute numbers, but this has been solved. In bakeries, we use a very small server to distribute numbers, in the form of a roll of tickets where conflicts between two customers are solved by the fact that human hands naturally exclude each other from the critical volume of space that must be occupied to take a ticket. We cannot use this approach for solving the problem on a computer.

Before going on to more interesting implementations for distributing numbers, note that clients of such a protocol may make extensive use of their numbers! For example, if the bakery contains multiple clerks, the clients could use their number to select a clerk (number modulo number of clerks). Similarly, in a FIFO queue implemented with a bounded buffer, the number modulo the queue size could indicate the slot in the  buffer to be used, allowing multiple processes to simultaneously place values in the queue.

Lamport’s Bakery Algorithm provides a decentralized implementation of the “take a number” idea. As originally formulated, this requires that each competing process share access to an array, but later distributed algorithms have eliminated this shared data structure. Here is the original formulation:


For each process, i, there are two values, C[i] and N[i], giving the status of process I and the number it has picked. In more detail:

N[i] = 0 --> Process i is not in the bakery. 

N[i] > 0 --> Process i has picked a number and is in the bakery. 

C[i] = 0 --> Process i is not trying to pick a number. 

C[i] = 1 --> Process i is trying to pick a number. 

when 

N[i] = min( for all j, N[j] where N[j] > 0 ) 

Process i is allowed into the critical section. 

Here is the basic algorithm used to pick a number: 

C[i] := 1; 

N[i] := max( for all j, N[j] ) + 1; 

C[i] := 0; 

In effect, the customer walks into the bakery, checks the numbers of all the waiting
customers, and then picks a number one larger than the number of any waiting
customer.

If two customers each walk in at the same time, they are each likely to pick the same
number. Lamport’s solution allows this but then makes sure that customers notice that
this has happened and break the tie in a sensible way.

To help the customers detect ties, each customer who is currently in the process of
picking a number holds his hand up (by setting C[i] to 1. s/he pulls down his hand
when s/he is done selecting a number -- note that selecting a number may take time,
since it involves inspecting the numbers of everyone else in the waiting room.

 Solution

A process does the following to wait for the baker: 

Step 1: 

while (for some j, C(j) = 1) do nothing; 

First, wait until any process which might have tied with you has finished selecting 

their numbers. Since we require customers to raise their hands while they pick 

numbers, each customer waits until all handsare down after picking a number in order 

to guarantee that all ties will be cleanly recognised in the next step. 

Step 2: 

repeat 

W := (the set of j such that N[j] > 0) 

(where W is the set of indeces of waiting processes) 

M := (the set of j in W 

such that N[j] <= N[k] 

for all k in W) 

(where M is the set of process indices with minimum numbers) 

j := min(M) 

(where is in M and the tie is broken) 

until i = j;

C implementation 

#include "pthread.h"
	#include "stdio.h"
	#include "unistd.h"
	#include "string.h"
	#define MEMBAR __sync_synchronize()
	#define THREAD_COUNT 8
	volatile int tickets[THREAD_COUNT];
	volatile int choosing[THREAD_COUNT];
	volatile int resource;
	void lock(int thread) {
	choosing[thread] = 1;
	MEMBAR;
	int max_ticket = 0;
	for (int i = 0; i < THREAD_COUNT; ++i) {
	int ticket = tickets[i];
	max_ticket = ticket > max_ticket ? ticket : max_ticket;
	}
	tickets[thread] = max_ticket + 1;
	MEMBAR;
	choosing[thread] = 0;
	MEMBAR;
	for (int other = 0; other < THREAD_COUNT; ++other) {
	while (choosing[other]) { }
	MEMBAR;
	while (tickets[other] != 0 &&
	(tickets[other] < tickets[thread] ||
	(tickets[other] == tickets[thread] && other < thread))) { }
	}
	}
	void unlock(int thread) {
	MEMBAR;
	tickets[thread] = 0;
	}
	void use_resource(int thread) {
	if (resource != 0) {
	printf("Resource was acquired by %d, but is still in-use by %d!\n",
	thread, resource);
	}
	resource = thread;
	printf("%d using resource...\n", thread);
	MEMBAR;
	sleep(2);
	resource = 0;
	}
	void *thread_body(void *arg) {
	long thread = (long)arg;
	lock(thread);
	use_resource(thread);
	unlock(thread);
	return NULL;
	}
	int main(int argc, char **argv) {
	memset((void*)tickets, 0, sizeof(tickets));
	memset((void*)choosing, 0, sizeof(choosing));
	resource = 0;
	pthread_t threads[THREAD_COUNT];
	for (int i = 0; i < THREAD_COUNT; ++i) {
	pthread_create(&threads[i], NULL, &thread_body, (void*)((long)i));
	}
	for (int i = 0; i < THREAD_COUNT; ++i) {
	pthread_join(threads[i], NULL);
	}
	return 0;
	}

Second, wait until your ticket number is the minimum of all tickets in the room. There
may be others with this minimum number, butin inspecting all the tickets in the room, you found them! If you find a tie, see if your customer ID number is less than the ID numbers of those with whom you’ve tied, and only then enter the critical section and meet with the baker.

Conclusion

The solution shown above is simple. Instead of computing the value of the smallest
number, compute the minimum process ID among the processes that hold the smallest
value. In fact, we need not seek the minimum process ID, all we need to do is use any
deterministic algorithm that all participants can agree on for breaking the tie. As long
as all participants apply the same deterministic algorithms to the same information,
they will arrive at the same conclusion.