Modify Peterson\'s algorithm (shown below) to achieve mutual exclusion for n>2 p
ID: 3568331 • Letter: M
Question
Modify Peterson's algorithm (shown below) to
achieve mutual exclusion for n>2 processes/threads.
#define FALSE 0
#define TRUE 1
#define N 2 /* number of processes */
int turn; /* whose turn is it? */
int interested[N]; /* all values initially 0 (FALSE) */
void enter_region( int process ) /* process is 0 or 1 */
{
int other; /* number of the other process */
other = 1 - process; /* the opposite process */
interested[process] = TRUE; /* show that you are interested */
turn = process; /* set flag */
while ( turn == process && interested[other] == TRUE )
/* null statement */ ;
}
void leave_region( int process ) /* process that is leaving */
{
interested[process] = FALSE; /* indicate departure from critical region */
}
Explanation / Answer
Let N be the number of running processes. The algorithm uses two arrays
of integers:
Q[1..N] indicates the current level of each process. Elements of Q belong to
the range [0..N ? 1].
Turn[1..N ? 1] stores the last process that has reach a level. Elements of
Turn belong to the range [1..N].
const N
shared variables
Q : array[1..N] of [0..N?1];
turn : array[1..N?1] of [1..N];
In this algorithm, processes climb a ladder with N ? 1 steps. When several
processes try to pass the same step, at least one of them do not move. The
algorithm for the i-th process is the following:
begin
while true do
begin
for j from 1 to N?1 do
begin
Q[i] = j;
Turn[j] = i;
wait until ((for all k 6= i, (Q[k] < j)) ou (Turn[j]6=i))
end
execute critical code
Q[i] := 0;
execute non critical code
end
end
Related Questions
drjack9650@gmail.com
Navigate
Integrity-first tutoring: explanations and feedback only — we do not complete graded work. Learn more.