Peterson’s n-Process Protocol
Peterson's Solution is a classic software based solution to the critical-section problem. Peterson's original formulations works for 2 processes. However, it is possible to implement it for more than 2 processes.
The following code works for 2 processes and it can be found easily on the Internet.
#define TRUE 1
int turn;
int interested[2];
void enterRegion(int process)
{
int other = 1 - process;
interested[process] = TRUE;
turn = process;
while (interested[other] == TRUE && turn == process)
;
}
void leaveRegion(int process)
{
interested[process] = FALSE;
}
Unfortunately, there aren't many resources about n-Process Peterson solution. I think one of the good explanation can be found in "Operating Systems Review, January 1990 ('Proof of a Mutual Exclusion Algorithm', M Hofri)".
I just like to show the following implementation of Peterson's n-Process Protocol.
#define N 10 /* First process is indicated with 1, not 0 */
int turn[N];
int stage[N + 1];
void enterRegion(int process)
{
int i, j;
for (i = 1; i <= N - 1; i++) {
stage[process] = i;
turn[i] = process;
for (j = 1; j <= N; j++) {
if (j == process)
continue;
while (stage[j] >= i && turn[i] == process)
;
}
}
}
void leaveRegion(int process)
{
stage[process] = FALSE;
}
Note: There are N processes from 1 to N. Therefore we need a turn array with size N - 1 and we need a stage array with size N. However, I declared the turn and the stage arrays with sizes N and N + 1 respectively. It is just because I like to keep the code clean. I don't want to subtract 1 like turn[i - 1]. I ignore the first elements -turn[0] and stage[0]- and never access them.
March 26th, 2010 - 15:21
Hi,
in my humble opinion, there are two significant errors in the code of the n-process solution.
Firstly, in the while cycle, there should be turn[i] instead of turn[j]. That’s because turn is a value associated to a stage, not to a process.
Secondly, I am not very sure if a solution with N-1 stages works. When a process leaves a critical region, it’s stage is being set to FALSE, which is 0. But, when a process tries to enter a critical region, it’s stage is set to 0, as a first try. This implies that processes which aren’t interested to enter a critical region can block processes that are interested (in the first condition of the while cycle). In my opinion, there should be stages 0 to N, and the i-cycle should run from 1 to N. This would avoid such not so good situations.
Sincerely,
Peter.
March 26th, 2010 - 15:23
Sorry, I wanted to write, that the i-cycle should run from 1 to N-1 and a stages should be 0 to N-1.
March 27th, 2010 - 18:57
Hi Peter,
Thank you so much for your comment.
You are absolutely right on both;
- The turn[j] should be turn[i], there was a typo.
- For the second problem, I had missed the case FALSE and the first stage 0. I had been thinking to assign -1 as a not-interested but forgot somehow. Anyway updating the loops is much clear and readable.
I have corrected the code as you suggested.
Best Regards,
Alper
May 25th, 2011 - 17:34
Hi
good work done by Mr.Alper…