nix

7.     Process Synchronization

7.1    Background

• Cooperating processes may either directly share a logical address space (that is, both code and data), or be allowed to share data only through files. The former case is achieved through the use of lightweight processes or threads.

         
         
         
         

• A Race Condition occurs, if
  • two or more processes/ threads access and manipulate the same data concurrently, and
  • the outcome of the execution depends on the particular order in which the access takes place.
• Synchronization is needed to prevent race conditions from happening.
• Statically detecting race conditions in a program using multiple semaphores is NP-hard.
• It is virtually impossible to catch race conditions dynamically because hardware must examine every memory access.
• Two groups, A and B, of processes exchange messages.
• Each process in A runs a function T_A (), and each process in B runs a function T_B ().
• Both T_A () and T_B () have an infinite loop and never stop.

         

• When a process in A makes a message available, it can continue only if it receives a message from a process in B who has successfully retrieves A’s message.
• Similarly, when a process in B makes a message available, it can continue only if it receives a message from a process in A who has successfully retrieves B’s message.
• Suppose process A1 presents its message for B to retrieve. If A2 comes for message exchange before B retrieves A1's, will A2's message overwrites A1's?
• Suppose B has already retrieved A1's message. Is it possible that when B presents its message, A2 picks it up rather than A1?
• Thus, the messages between A and B must be well-protected to avoid race conditions.

         
         
         

• If there are shared data items, always protect them properly. Without a proper mutual exclusion, race conditions are likely to occur.
• In this first attempt, both global variables Buf_A and Buf_B are shared and should be protected.

         
         

• Improper protection is no better than no protection, because it gives us an illusion that data have been well-protected.
• We frequently forgot that protection is done by a critical section, which cannot be divided.
• Thus, protecting “here is my card” followed by “may I have yours” separately is not good enough.

         
         

• Mutual exclusion for one group may not prevent processes in other groups from interacting with a process in this group.
• It is common that we protect a shared item for one group and forget other possible, unintended accesses.
• Protection must be applied uniformly to all processes rather than within groups.

         
         

• We use locks for mutual exclusion.
• The owner, the one who locked the lock, should unlock the lock.
• In the above “solution”, already is acquired by a process A but released by a process B. This is risky!
• In this case, a pure lock is more natural than a binary semaphore.
• Check the ThreadMentor tutorial pages for more details and correct solutions.

• A critical section is a section of code in which a process access shared resources.
• Thus, the execution of critical sections must be mutually exclusive (e.g., at most one process can be in its critical section at any time).
• The critical-section problem is to design a protocol that processes can use to cooperate.

           

• A critical section protocol consists of two parts: an entry section and an exit section. The remaining code is the remainder section.
• Between them is the critical section that must run in a mutually exclusive way.

                    

• Any solution to the critical section problem must satisfy the following three conditions:
  • Mutual Exclusion
    • If a process P is executing in its critical section, then no other processes can be executing in their critical sections.
    • The entry protocol should be capable of blocking processes that wish to enter but cannot.
    • Moreover, when the process that is executing in its critical section exits, the entry protocol must be able to know this face and allows a waiting process to enter.
  • Progress
    • If no process is executing in its critical section and some processes wish to enter their critical sections, then
      • Only those processes that are waiting to enter can participate in the competition (to enter their critical sections).
      • No other process can influence this decision.
      • This decision cannot be postponed indefinitely.
  • Bounded Waiting
  • After a process made a request to enter its critical section and before it is granted the permission to enter, there exists a bound on the number of times that other processes are allowed to enter.
  • Hence, even though a process may be blocked by other waiting processes, it will not be waiting forever.
  • Moreover, the solution cannot depend on CPU’s relative speed and scheduling policy.

• Suppose we have two processes, P₀ and P₁.
• Let one process be P_i and the other be Pj, where j = 1-i. Thus, if i=0 (resp., i=1), then j=1 (resp., j=0).

• Global variable turn controls who can enter the critical section.
• Since turn is either 0 or 1, only one can enter.
• However, processes are forced to run in an alternating way.
• This solution does not fulfill the progress condition.
• If Pj exits by setting turn to i and terminates, P_i can enter but cannot enter again.
• Thus, an irrelevant process can block other processes from entering a critical section.

                                 

• Variable flag[i] is the “state” of process P_i: interested or not-interested.
• P_i expresses its intention to enter, waits for P_j to exit, enters its section, and finally changes to “I am out” upon exit.
• The correctness of this algorithm is timing dependent!
• If both processes set flag[i] and flag[j] to TRUE at the same time, then both will be looping at the while forever and no one can enter.
• Bounded waiting does not hold.

                                 

• If both processes are in their critical sections, then
  • flag[j] && turn == j (P_i) and flag[i] && turn == i (P_j) are both FALSE
  • flag[i] and flag[j] are both TRUE
  • Thus, turn == i and turn == j are FALSE
  • Since turn can hold on value, only one of turn == i or turn == j is FALSE, but not both.
  • We have a contradiction and P_i and P_j cannot be in their critical sections at the same time.
• If P_i is waiting to enter, it must be executing its while loop.
• Suppose P_j is not in its critical section:
  • If P_j is not interested in entering, flag[j] was set to FALSE when P_j exits. Thus, P_i may enter.
  • If P_j wishes to enter and sets flag[j] to TRUE, it will set turn to i and may P_i enter.
• In both cases, processes that are not waiting do not block the waiting processes from entering.
• When P_i wishes to enter:
  • If P_j is outside of its critical section, then flag[j] is FALSE and P_i may enter.
  • If P_j is in its critical section, eventually it will set flag[j] to FALSE and P_i may enter.
  • If P_i is in the entry section, P_i may enter if it reaches while first. Otherwise, P_j enters and P_i may enter after P_j set flag[j] to FALSE and exits.
• Thus, P_i waits at most one round!

• Bakery algorithm, based on the scheduling algorithm commonly used in bakeries.                     

/*****************************************************************************************/

boolean choosing[n] = {FALSE};

int number[n] = {0};        /* Process who gets the smallest number can enter the critical section first */

do {              

                                critical section

                                remainder section

} while (1);

/*****************************************************************************************/

7.3    Synchronization Hardware

• The critical-section problem could be solved simply in a uniprocessor environment if we could forbid interrupts to occur while a shared variable is being modified.
• Disabling/Enabling interrupts:
  • This is slow and difficult to implement on multiprocessor systems.
  • Because interrupts are disabled, no context switch will occur in a critical section.
  • Infeasible in a multiprocessor system because all CPUs must be informed.
  • Some features that depend on interrupts (e.g., clock) may not work properly.

                     

• Special privileged machine instructions:
  • Atomic: Many machines provide special hardware instructions that allow us either to test and modify the content of a word, or to swap the contents of two words as one uninterruptible unit. More precisely, when such an instruction runs, all other instructions being executed in various stages by the CPUs will be stopped (and perhaps re-issued later) until this instruction finishes.
  • Thus, if two such instructions are issued at he same time, even though on different CPUs, they will be executed sequentially.
  • Privileged: These instructions are, in general, privileged, meaning they can only execute in supervisor or kernel mode.
  • Mutual exclusion is obvious as only on TS instruction can run at a time.
  • However, progress and bounded waiting may not be satisfied.
  • Test and Set (TS)

                     
                     

• Bounded-waiting mutual exclusion with TestAndSet             

/*****************************************************************************************/

boolean waiting[n] = {false};

boolean lock;

do {

                     critical section

                     Remainder section

} while (1);

• Swap                     

/*****************************************************************************************/

Void Swap (boolean &a, boolean &b) {

                                boolean temp = a;

                                a = b;

                                b = temp;

}

do {

           critical section

           remainder section

} while (1);

/*****************************************************************************************/

• Compare and Swap (CS)
• Problems with software and hardware solutions
  • All of these solutions use busy waiting.
  • Busy waiting means a process waits by executing a tight loop to check the status/value of a variable.
  • Busy waiting may be needed on a multiprocessor system; however, it wastes CPU cycles that some other processes may use productively.
  • Even though some personal/lower-end systems may allow users to use some atomic instructions, unless the system is lightly loaded, CPU and system performance can be low, although a programmer may “think” his/her program looks more efficient.