Process Synchronization – III – Using atomic instructions to solve Critical Section Problem

In the previous post, we discussed why atomic instructions like test_and_set() and compare_and_swap() were needed. We also discussed two algorithms which satisfied the mutual exclusion requirement, but did not satisfy the bounded waiting requirement.

In this post, we shall discuss an algorithm using test_and_set() which satisfies all the requirements listed in the critical section problem.

Let us first revisit the three requirements which have to be satisfies in a solution to the critical section problem. These are : 

  1. Mutual Exclusion –  only one process can execute its critical section at any time
  2. Progress – Selection of next process for executing in critical section cannot be postponed indefinitely.
  3. Bounded waiting – A process will not wait indefinitely to execute its critical section.

Let us first discuss the algorithm which satisfies the above three conditions, and then we shall look how are these conditions being satisfied.

The solution proposed requires two data items : 

We initialize both the data items to false.

Let us first discuss what the code above does. 

  • The do-while loop describes the execution sequence for a process Pi.
  • The data items lock and waiting array are initialized to false (for all i).
  • For process Pi :
    • Set waiting[i] and key to true.
    • Fact : A process can enter its critical section only if waiting[i] is false or key is false. Reason is :
      • Let us say that both waiting[i] and key are true.
      • Then, the control enters the while loop and calls test_and_set(&lock)
      • Here, if the lock is false, only then the key becomes false. Otherwise, key is set to true and the while loop continues. This loop will continue indefinitely for this Process Pi until the lock becomes available, i.e. lock is 0
    • So, let us say that Pi is the first process to execute test_and_set() function. Since the lock was initialized to false, value of key becomes 0.
    • In the next line, waiting[i] also becomes 0. This means that Process Pi is currently not waiting. It has set(acquired) the lock, and therefore can execute its critical section.
    • At this point, if any other process executes the test_and_set(&lock) function, the return value rv will always be true [since lock has been set to true by Pi]. Therefore, no other process will enter its critical section.
    • This satisfies the first requirement, i.e. Mutual Exclusion.
  • The process Pi now executes its critical section.
  • When a process leaves its critical section, it scans the waiting[] array in cyclic order, starting from i+1, ….. goes on till i-1.
  • It finds the first process j in this cyclic order with waiting[j] equal to true.
    • At this point, if no other process is waiting to enter critical section, i.e. it has reached i again, then it simply means that the lock becomes available again. So, its sets the value of lock to false.
    • Otherwise, it sets waiting[j] to false. Note that at this point in time, that particular process j would be executing the while loop with the condition : while (waiting[i] && key) 
    • This breaks its while loop, and Process j enters critical section.
    • Since process i, when exiting its critical section, either sets lock to false, or sets waiting[j] to false → both allow a waiting process to enter critical section → ensures Progress
  • Since, any process waiting to enter its critical section, will do so, in at most n-1 turns (since a process Pi which has just executed its critical section proceeds in a unidirectional cyclic manner to find a waiting process to execute the critical section next), therefore this ensures Bounded-waiting requirement is met.

We will start with mutexes and semaphores in the next post. Until then, keep reading and sharing!! 🙂