Consistency of the Memory Sub-System

6.895 Theory of Parallel Systems Lecture 5 Consistency of the Memory Sub-System Lecturer: Bradley C. Kuszmaul Lecture Summary 1. Mutual Ezclusion Introduction to the problems of shared-memory parallel systems and definition of mutual exclusion. 2. Mutual Exclusion Algorithms Description of the mutual exclusion algorithms of Dekker and Dijkstra. 3. Memory Consistency Definition of memory consistency in terms of atomic operations. 4. Memory Subsystem of Hardware Architectures Description of various memory operation primitives such as Load-Link-Store-Conditional and Trans- actional Memory. 1 Mutual Exclusion The underlying problem of shared memory parallel systems is that we have more than one thread and shared memory locations, accessed by all concurrent executing threads. The question is how do the threads interact? Example 1 One example Cilk code which contains a simple determinacy race, already discussed in the previous lectures, is the following: cilk int foo (void) {x++; } cilk int main (int argc, char *argv[]) { spawn foo(); spawn foo(); } Once we detect the determinacy race, e.g. by using the Nondeterminator, our goal is to eliminate it. In order to avoid the determinacy race we have to make sure that only one thread at a time can perform the operation x++. As a start we could consider the following idea. Simply prevent context switching, for example by turning off the interrupts as in the following MIPS assembler code: DI turn off interrupts LW R1, (0)R2 ADD R1, R1,1 SW R1, (0)R2 ΕΙ However, there are a number of downfalls with using interrupts for mutual exclusion: It only works on a uniprocessor machine. On a multiprocessor machine the other processors are not affected by the DI instruction. It only works in kernel (not user) mode. On most architectures there is no user-level call that can disable interrupts. And it also prevents other threads from doing non-critical work, which is extremely dangerous, since the operating system time slice interrupt will never take place, and the operating system would fail gaining control Definition 1 In a more general conceptual setting, mutnal exclusion can be described in the following algo rithmic setup: while (1) { trying(); critical section() releaning(); noncrit; In an infinite loop each thread tries to execute critical section(), that is the sequence of operations which need to be executed atomically. In order to be allowed to execute the critical section the thread first needs to get permission. In the above example the task of allocating the right to enter the critical section is given by the part trying(). Moreover the thread needs to be cooperative and release hold of its right to enter the critical section in releasing(). Consequently it performs the rest of its non-critical task noncrit(). Now the problem is to write the functions trying() and releasing() so that at most one thread is in critical section at a time. One extremely trivial solution would be: Example 2 trying(void) { halt(); } The trivial solution is not good since it simply stops the currently executing thread. This illustrates a problem with our specification of mutual exchision. In addition to the algorithmir description of mutual exclusion from Definition I we now introduce some additional definitions. Definition 2 Mutual exclusion requires that there is Progress. // no thread is execating critical section and there are some threads which are trying to enter critical section (in our example by executing trying()) then some thread will do critical section. Apart from the definition of mutual exclusion with guaranteed progress there are other aspects which are desirable, however not strictly required for Mutual Exclusion, such as: Definition 3 No Starvation. Every executing thread gets a fair chance of executing in the critical section. Example 3 An alternate idea for the mutual exclusion problem in the case of two threads would be: int turn 1; int run(int i) { // i is the thread nunber for the currently executing thread, // for one thread and 1 for the other crit(); while (turnli); turn-1-1; // it is the other thread's turn noncrit(); } However, the problem with the previous approach is that it does not guarantee progress. If, for example, noncrit() is an infinite loop in thread 1, then thread 0 would get stuck. 2 Mutual Exclusion Algorithms This section presents two algorithms that solve the mutual exclusion problem. The first one is due to Dekker and it solves the mutual exclusion problem for two threads. The second is Dijkstra's algorithm for mutual exclusion, which is a generalization applicable to any number of threads. 2.1 Dekker's Algorithm A solution which works for two threads and uses turns was described by Dekker. The following C code presents his algorithm: int turn; int wants [2]; // i is the current thread, j-1-i is the other thread while(1) ( wants[i] = TRUE; while (wants[j]) ( if (turnej) ( } // trying wants [1] FALSE; while (turnj); // empty loop wants[i] = TRUE; critical_section(); turn=j; wants [1] FALSE; // release noncrit(); As a visualization of Dekker's algorithm consider the following railroad from Figure 1. Each thread has its own railroad system which intersects with the railroad of the other thread only on the critical section. There are a number of switches which the threads activate as they traverse the railroad. Whenever a thread encounters a semaphore it can change its course according to the indication of the semaphore. The threads "move" in the direction shown by the arrows. As an illustration, assume that thread 0 starts at the top of its railway system and wants to do critical section. It will first set turn-1, and then wants [0] TRUE Next it will encounter a semaphore which tells it whether thread I wants to enter the critical section. Suppose that thread I also wants to enter, then thread 0 will switch tracks, and "move" downwards. On this new track it will set wants[0]=FALSE and go and check the next semaphore. Assume that now turn=0, then thread 0 will remain on this track, and set wants [0] TRUE. Also assume that now thread 1 does not want to enter the critical section. Then thread 0 can go and execute critical section. 2.2 Dijkstra's Algorithm Dijkstra devised a mutual exclusion algorithm for any number of threads. The following are the conditions for Dijkstra's mutual exclusion problemt Only 1 thread may execute critical section() at a time. The threads execute in an infinite loop trying to enter critical section. Atomic read and atomic write are available, but no other instructions (no locking instructions).