Previous: Introduction Up: Atomicity Next: Deadlock

Controlled Nondeterminism

In Chapter it was stressed that arbitrary sharing of mutable variables between concurrent threads of control is a dangerous practice. This is because the manner in which the operations on these shared mutables are interleaved is unknown. Therefore nothing can be said about the outcome of such a program. Atomicity gives us a way to control this interleaving, and hence to control the nondeterminism of parallel composition. The example presented in Section , for instance, results in v.x having the value 1 or the value 2. Without an atomic access to v.x, however, this program would result in v.x having an arbitrary value.

Atomic functions can be used to write deterministic programs, despite the nondeterminism inherent in concurrent access to shared mutables. For example, consider finding the minimum element of an array:

class Min {
  private:
    int current_min; 
  public:
    Min(int i)  
      { current_min = i; } 
    atomic void check (int i)  
     { if (i<current_min) current_min = i; } 
};

int main()
{
  int A[N];
  ...
  Min m(A[0]);  
  parfor (int i=1; i<N; i++)  
    m.check(A[i]);  
  ...
}

Because of the nature of parfor, we do not know the order in which each of the N-1 parallel threads of control initiates execution of m.check(A[i]). However, once one thread begins execution of this m.check() function, no other thread is permitted to begin execution of any other atomic member functions of object m (including, of course, other instances of m.check()). Figure represents one possible sequence of execution for this program.

Thus, the order in which m.current_min is updated is nondeterministic. However, the nature of the application guarantees that at the end of the parfor statement, m.current_min will have been compared (and updated) to the minimum element of array A[]. Hence, given the input array A[], the intermediate values taken on by m.current_min are unknown, but the final value is fixed.

It is important to notice how this atomic function represents a significant bottleneck in the computation of this minimum element. Because only a single thread of control is allowed to be executing an atomic member function of m at any given time, the execution is essentially sequential. This suggests that atomic functions should be kept very small.