1. Problem Definition

   while true do {
     NCS;  // non-critical section
     CS;   // critical section
   }

   while true do {
     NCS;  // non-critical section
     Entry(i);
     CS;   // critical section
     Exit(i);
   }

• Safety: At any time at most one process is in a CS.

• Progress: If a process is waiting to enter a CS. then the process eventually enters assuming that
  • No process stays in a CS indefinitely

  • Each process executes its Entry code, CS code, and Exit code with weak fairness.

• Read-Write Atomicity: Reads and writes of machine words are executed atomically

2. Comments

• Note that NCS is not (necessarily) executed with weak fairness. So the solution must handle the case where a process stays indefinitly in its NCS (which models, for example, an infinite loop or process termination in NCS).

• Note that constructs larger than reads and writes of machine words are not (necessarily) executed atomically. So the solution must not depend upon such constructs being atomic.

• Solving this problem actually gives us a very powerful synchronization primitive, namely, locks. Suppose S1, S2, S3, ..., are chunks of code that we want atomically executed with respect to each other; that is, at most one Si is executing at any time. This can be achieved by treating each Si as a CS. The Entry code corresponds to grabbing the lock and the Exit code corresponds to releasing the lock.

• Multiple instances of the solution gives us multiple locks. Suppose S1, S2, S3, ..., are chunks of code that are to be atomically executed with respect to each other, and T1, T2, T3, ..., are other chunks of code that are to be atomically executed with respect to each other (but Ti and Sj can be executing at the same time). This can be achieved by having two instances of the solution. That is, two sets of MEvars, say S.MEvars and T.MEvars, enclose each Si by Entry(i, S.MEvars) and Exit(i, S.MEvars), and enclose each Ti by Entry(i, T.MEvars) and Exit(i, T.MEvars).