Objects, Abstractions and Concurrency

 

The core of object-oriented programming is building data abstractions which can be modified with a well-defined set of operations [27, 41, 41]. These operations (i.e. member functions in C++) transform the data abstraction from one consistent state to another. In a concurrent program, such member functions might be interleaved, exposing inconsistent states, and thereby destroying the encapsulation (and perhaps also the correctness) of the data abstraction. To avoid such problems, concurrent object models generally must prevent the interleaving of members which can violate encapsulation [2, 42, 13, 12, 3, 6, 23, 20]. Concurrent object models must also be designed with programmability and single source maintenance in mind.

For instance, a simple model which provides a single monitor for each object might prohibit recursive calls, breaking many sequential programs, and requiring programmers to program around the language. Our extensive experience with Concurrent Aggregates explored such a model, but programmers generally found this model burdensome and a fruitful source of program deadlock. In addition, because of the complex lock dependence structures that could be built with such a model, it prevented numerous optimizing code transformations.

The ICC++ object concurrency model constrains concurrency enough to maintain the logical atomicity of operations, but it permits much more concurrency than models based on a single monitor. The model has three elements: an object consistency model, a mechanism for extending that model to multiple objects, and a model for constructing atomic operations over multiple abstractions.

Object Data Abstractions

  ICC++ defines an object consistency model and object concurrency guarantees to allow a programmer to reason about program correctness and progress. The consistency model ensures local serializability of operations by ensuring that method calls do not disrupt each other. Concurrency guarantees define which member calls must run concurrently, allowing programmers to reason about program progress.

Object Consistency Model

  In ICC++, concurrent method invocations on an object are constrained so that intermediate object states created within a member function are not visible. In essence, this means that the operations are locally serializable; the effect on member variables is as if the member functions operated one after another. This preserves the same notion of consistency provided in a sequential object model: each member call leaves the object in a consistent state for subsequent calls. For concurrency control purposes, a member function call is considered to include nested calls on this.

Thus object state modifications during the execution of such nested calls are not visible. Finally, direct access to object state from outside member functions (e.g. a->field_name) are subject to the same consistency model by requiring use of implicitly-defined accessor members.

Object Concurrency Guarantees

  Concurrency guarantees enable a programmer to reason about progress in a concurrent program. For each object locally, ICC++ guarantees that member function calls whose effect on object state is explicitly independent will execute concurrently. Explicit independence is determined by forming may-read and may-write sets as a conservative approximation of member effects. For example, concurrency is guaranteed for two methods which share no member variables and those that employ read-only sharing of member variables. The notion of explicit independence is transitive: the may-read and may-write sets include accesses within nested calls on this. This simple concurrency guarantee allows many programs that partition object state into independent read and write sets to be written without additional synchronization, and without fear of deadlock.

As an example, consider a semaphore object:

class Semaphore{
 private :
  int i;	
 public :
  Semaphore(int ii = 0){
    i = ii;
  }

  int p(void){ 
    if (i==0) return ++i;
    return 0;
  }

  int v(void){
    if (i==1) return i-;
    return 0;
  }
};

Because the semaphore's p() and v() operations both potentially read and write the instance variable i, no concurrency is allowed--much less guaranteed--between them.

A similar example is the following simple barrier object:

class barrier{
 private :
  int countto;
  int arrived;
  int flag;		
 public :
  barrier(void){
    countto = arrived = flag = 0;
  }

  void begin_barrier(int expected){
    arrived = flag = 0;
    countto = expected;
  }

  int enter_barrier(void){ 
    arrived++;
    if (arrived == countto) return 1;
    return 0;
  }

  void post_flag(void){ flag = 1; }

  int test_barrier(void){ return flag; }
};

The barrier class is called once with begin_barrier() to initialize its consensus count. Threads then call enter_barrier() to signal their arrival, and check test_barrier() to see when the barrier has completed. If the value returned by test_barrier() is 1, the barrier is complete, so the thread calls post_flag. A distinct flag variable allows calls to enter_barrier() and test_barrier() to execute concurrently, ensuring that the barrier can complete. Without the concurrency guarantees, a programmer might be forced to split the flag state into another object in order to ensure concurrent progress of both test_barrier() and enter_barrier().

Concurrency Control Across Multiple Objects

  Data abstractions are often conveniently implemented as ensembles of objects, shallow hierarchies, trees, networks, and other pointer-based structures. For example, C++ objects sometimes have fields that point to arrays, allowing the arrays to vary is size. The ICC++ concurrency control model allows consistency guarantees to be extended over several objects by using the integral declaration specifier.

integral is a new type specifier that can be applied only to member variables and extends object consistency to include all references to that member variable. That is, all references to an integral member variable are considered read/write operations on it, providing local serialization. Note that this does not ensure global serialization, since the object whose reference is declared integral could be shared. However, this model handles the common case where the integral variable points to private state, and can be implemented efficiently with only local operations.

The code example below illustrates the use of integral.

class Bucket;
class HashTable{
  integral Bucket buckets[];   // collection of buckets
  int n_buckets;               // number of buckets

  // locate the bucket in which a given key would be found
  Bucket& find_bucket(Key k) { 
    return buckets[k.hash }

 public :

  Element find(Key k) {
    // Bucket::find returns an element based upon a given key
    return find_bucket(k).find(k);
  }

  Element add(Element e) {
    Bucket& b = find_bucket(e.key);
    // Bucket::has returns TRUE if the bucket has the key
    // Bucket::add puts a given element in the bucket
    if (! b.has(e.key)) b.add(e); 
    return e;
  }

friend bool operator >=(HashTable&, HashTable&);
};

Extending Concurrency Control to Contained Objects Using integral  For example, the buckets member in Program 1.1 is declared integral to incorporate it into the hash table's concurrency control.The integral specifier is needed to ensure that calls to HashTable::add and HashTable::find are mutually exclusive; HashTable::add does not affect the immediate state of the HashTable itself, so multiple calls to it could otherwise interleave. Such interleaved calls would, in turn, interleave calls to Bucket::has and Bucket::add. This could cause the same element to be inserted multiple times. However, since HashTable::add reads the state of buckets, declaring buckets to be integral prevents this interleaving.

While integral supports coherence for a single abstraction, some operations require consistency across multiple abstractions. For instance, a set difference operation on mathematcial sets could need to prevent changes to both set arguments so as to remain consistent. And in general, coordinating concurrent activities requires coordinated updates across several distinct abstractions [19, 28]. friend functions may be part of the interfaces of multiple classes, making them a natural basis for coordinating updates across multiple objects. They provide the same guarantees as members for all their friendly arguments; that is, friends ensure that intermediate states of all friendly arguments are invisible. This means the execution of a friend function is locally serializable with respect to each friendly argument.

bool operator >=(HashTable &left, HashTable &right) {
  for(int i = 0; i < right.n_buckets; i++) {
    Bucket &b = right.buckets[i];
    for(int j = 0; j < b.n_elements; b++) {
      if (!left.find(b[j]))
        return false;
    }
  }

  return true;
}

Above is the code for operator >=, which was declared friend in HashTable; it checks whether left is a superset of right. There is a potential for wrong answers if either left or right are modified. Declaring this function a friend prevents this from happening, as friend assures that it will be consistent with respect to both left and right.

Discussion

  Our experience with monitor-based concurrency control models in Concurrent Aggregates highlight the problems of their use (e.g. a penchant for deadlock) and optimization (e.g. limited code transformations), and thus motivate ICC++'s concurrent object model.

A language's concurrency control model can affect execution efficiency. Our concurrency control model is defined in terms of visible state changes, rather than locking or exclusivity, to allow the compiler to optimize concurrency control. Declaring intermediate states to be invisible gives objects thread-safe semantics, and also allow object state to be safely cached in registers under compiler control. Concurrency control also interacts with derivation, and our concurrency model has been designed with this inheritance anomaly in mind, as discussed in Section 1.8.

While transactions and nested transactions provide an elegant, flexible model for composing objects into larger abstractions, they are far too expensive for object-level concurrency. To exploit concurrency at this level, overheads of at most a few instructions can be tolerated. The integral mechanism meets this cost constraint because its local definition of consistency allows it to be implemented with local bit-mask operations. The friend mechanism provides a truly consistent view of two objects, and thus is more expensive, potentially requiring remote locking. ICC++ includes friend as a building block when such expensive structures are really essential.