Question

Is is possible to implement locks for a critical section in user-level code without the use of system calls or atomic instructions? Justify your answer

Answer 1

Yes it is possible to implement locks for a critical section in user-level code without use of system calls or atomic instructions. There are many examples like Peterson's algorithm and Dekker's algorithm.

I am discussing Peterson's algorithm as a justification of my answer. Although I will be discussing Peterson's algorithm which is a 2-process synchronization algorithm, it can be modified for more than 2-process. This answer is known as Filter algorithm.

Peterson's Algorithm:

There are two variables, flag and turn. A flag[n] value of true indicates that the process n wants to enter the critical section. Entrance to the critical section is granted for process P0 if P1 does not want to enter its critical section or if P1 has given priority to P0 by setting turn to 0.

                    bool flag[2] = {false, false};

                    int turn;

P0:              flag[0] = true;

                   P0_gate: turn = 1;

                   while (flag[1] == true && turn == 1)

                   {

                   // busy wait

                   }

                   // critical section

                   ...

                   // end of critical section

                   flag[0] = false;

P1:              flag[1] = true;

                 P1_gate: turn = 0;

                 while (flag[0] == true && turn == 0)

                 {

                 // busy wait

                 }

                 // critical section

                 ...

                 // end of critical section

                 flag[1] = false;

The algorithm satisfies the 4 essential criteria to solve the critical section problem, provided that changes to the variables turn, flag[0], and flag[1] propagate immediately and atomically. The 4 criteria are mutual exclusion, progress, bounded waiting and platform independent. The while condition works even with preemption.

Since turn can take on one of two values, it can be replaced by a single bit.

Mutual exclusion

P0 and P1 can never be in the critical section at the same time: If P0 is in its critical section, then flag[0] is true. In addition, either flag[1] is false (meaning P1 has left its critical section), or turn is 0 (meaning P1 is just now trying to enter the critical section, but graciously waiting), or P1 is at label P1_gate (trying to enter its critical section, after setting flag[1] to true but before setting turn to 0 and busy waiting). So if both processes are in their critical sections then we conclude that the state must satisfy flag[0] and flag[1] and turn = 0 and turn = 1. No state can satisfy both turn = 0 and turn = 1, so there can be no state where both processes are in their critical sections. (This recounts an argument that is made rigorous in.)

Bounded waiting

Bounded waiting, or bounded bypass means that the number of times a process is bypassed by another process after it has indicated its desire to enter the critical section is bounded by a function of the number of processes in the system. In Peterson's algorithm, a process will never wait longer than one turn for entrance to the critical section: After giving priority to the other process, this process will run to completion and set its flag to 1, thereby never allowing the other process to enter the critical section...

Progress

Progress is defined as the following: if no process is executing in its critical section and some processes wish to enter their critical sections, then only those processes that are not executing in their remainder sections can participate in making the decision as to which process will enter its critical section next. Note that for a process or thread, the remainder sections are parts of the code that are not related to the critical section. This selection cannot be postponed indefinitely. A process cannot immediately re-enter the critical section if the other process has set its flag to say that it would like to enter its critical section.

Platform Independent

It is platform independent because there is no kernel or hardware related mechanism used in this solution.