Previous: Atomicity Up: Atomicity Next: Controlled Nondeterminism

Introduction

In this chapter we introduce the concept of atomicity. Because this construct is related to the notion of classes and member functions, some familiarity with the object-oriented aspects of C++ is assumed.

In Chapter the concept of threads of control executing in a parallel manner was introduced. A rule was presented for avoiding dangerous behavior by not sharing mutable variables between concurrent threads of execution. Sometimes, however, this sharing is necessary. Consider, for example, an implementation of a queue class. The following implementation is typical:

class Node  {
  public:
    int item;
    Node* next;
    Node (int i) { item = i; }
};

class Queue  {
  private:
    Node* head;
    Node* tail;
  public:
    Queue (void)  {
      head = NULL;
      tail = NULL;
    }

    void enqueue (int i)  {
      Node* add = new Node(i);
      if (head==NULL)  {
        head = add;
        tail = add;
      }
      else  {
        tail->next = add;
        tail = add;
      }
    }

    int dequeue (void)  {
      int ret_val = 0;
      if (head != NULL)  {
        ret_val = head->item;
        old_head = head;
        head = head->next;
        if (head == NULL)
          tail = NULL;
        delete old_head;
      }
      return ret_val;
    }
};

Now consider a Queue that can be used by an arbitrary and varying number of threads of control, all executing in parallel. Obviously this can lead to trouble if one thread of control accesses the queue by interrupting another thread that was already accessing the queue. We would like a mechanism to specify that once a particular member function has begun executing, no other member functions (from a particular set) of that object will begin executing. This mechanism is provided in CC++ by the keyword atomic. Atomicity is a mechanism for controlling the granularity of permitted interleavings of parallel threads of control.

Member functions (private, public, or protected) of an object can be declared atomic. This declaration specifies that the actions of such a function will not be interleaved with the actions of any other atomic function of the same object. In our queue example, both the enqueue() and the dequeue() operations would be declared atomic.

class Queue  {
  ...
  atomic void enqueue (int i) {...}
  atomic int dequeue (void) {...}
};

As a simpler example, consider the following program:

class Value  {
  private: 
    int x;
  public: 
    atomic void assign (int i) 
      { x = i; } 
};

void f(void)
{
  Value v; 
  par  { 
    v.assign(1); 
    v.assign(2); 
  } 
  //v.x is now either 1 or 2 
}

Two threads of control are created in the parallel block, each executing an atomic function of the object v. Because atomic functions that are members of the same object cannot execute concurrently, one atomic function executes first and is then sequentially followed by the execution of the second atomic function. The nondeterminism of the interleaving of actions within a parallel block is reflected in the fact that we do not know which atomic function will execute first. But once one atomic function begins execution, it will not be interrupted by the other atomic function. The two possibilities for the flow of control in this example are illustrated in Figure .

Atomic functions should always be used to access mutable variables that are shared between concurrent threads of control.