27 Solution Criteria to Critical-Section Problem

Solution to protect against concurrent modification of data in the critical section with the following criteria :

• Mutual Exclusion : If process $P_i$ is in its critical section (i.e., where shared variables could be altered inconsistently), then no process can be in this critical section.
• Progress : no process outside of the critical section (i.e., in the remainder section) should block a process waiting to enter.
• Bounded Waiting : A bound must exist on the number of times that the other processes are allowed to enter the critical section after a process has made a request to enter its critical section and before that request is granted (i.e., it must be fair, so no one poor process is not always waiting behind the others).
  Assumes that each process executes at a non-zero speed.
  No assumption concerning relative speed of the $N$ processes.

Peterson’s Solution

• Two process solution.
• Assume that the CPU’s register LOAD and STORE instructions are atomic (not realistic on modern CPUs, educational example).
• The two processes share two variables:
  • int turn;
  • Boolean wants_in[2];
• The variable turn indicates whose turn it is to enter the critical section
• The wants_in array is used to indicate if a process is ready to enter the critical section. wants_in[i] = true implies that process $P_i$ is ready.

do {
	wants_in[i] = TRUE; // I want access...
	turn = j; // but, please, you go first
	while (wants_in[j] && turn == j); // if you are waiting and it is
		// your turn, I will wait.
		[critical section]
	wants_in[i] = FALSE; // I no longer want access.
		[remainder section]
} while (TRUE);

When both processes are interested, they achieve fairness through the turn variable, which causes their access to alternate.