this information is specified in Galois for a class that implements sets. For each method, the implementor specifies the following:

 

• Commutes: This section specifies which other methods the current method commutes with, and under which conditions. For example, remove(x) commutes with add(y), as long as the elements are different.

• Inverse: This section specifies the inverse of the current method.

 

Note that add(x) does not commute with add(x) according to this specification. This is because rolling back add(x) requires invoking remove(x), which would conflict with other invocations of add(x). This choice simplifies the implementation.

3. 3. Runtime system

The Galois runtime system has two components: ( 1) a global structure called the commit pool that is responsible for creating, aborting, and committing iterations and ( 2) structures called conflict logs which detect when commutativity conditions are violated for catch-and-release objects.

The commit pool maintains an iteration record, shown in Figure 9, for each ongoing iteration in the system. The status of an iteration can be RUNNING, RTC ( ready-to-com-mit), or ABORTED. Threads go to the commit pool to obtain an iteration. The commit pool creates a new iteration record, obtains the next element from the iterator, assigns a priority to the iteration record based on the priority of the element (for a set iterator, all elements have the same priority), and sets the status field of the iteration record to RUNNING. When an iteration invokes a method of a shared object, ( 1) the conflict log of that object is updated, as described in more detail below and ( 2) a callback to the associated inverse method is pushed onto the undo log of the iteration record. If a commutativity conflict is detected, the commit pool arbitrates between the conflicting iterations, and aborts iterations to permit the highest priority iteration to continue execution. Callbacks in the undo logs of aborted iterations are executed to undo their effects on shared objects. Once a thread has completed an iteration, the status field of that iteration is changed to RTC, and the thread is allowed to begin a new iteration. When the completed iteration has the highest priority in the system, it is allowed to commit. It can be seen that the role of the commit pool is similar to that of a reorder buffer in out-of-order processors.

figure 9. iteration record maintained by runtime system.

IterationRecord {

Status status;

Priority p;

UndoLog ul;

Lock 1;

}

94 commuNicaTioNS of The acm | sEPTEMBER 2009 | VoL. 52 | no. 9

Conflict Logs: The conflict log is the mechanism for detecting commutativity conflicts. There is one conflict log associated with each catch-and-release object. A simple implementation for the conflict log of an object is a list containing the method signatures (including the values of the input and output parameters) of all invocations on that object made by currently executing iterations (called “outstanding invocations”). When iteration i attempts to call a method m1 on an object, the method signature is compared against all the outstanding invocations in the conflict log. If one of the entries in the log does not commute with m1, then a commutativity conflict is detected, and an arbitration process is begun to determine which iterations should be aborted, as described below. If m1 commutes with all the entries in the log, the signature of m1 is appended to the log. When i either aborts or commits, all the entries in the conflict log inserted by i are removed from the conflict log.

Consider the effects of calling contains(x) on a set implementing the interface shown in Figure 8. The conflict log contains all the outstanding invocations of methods on the set. Because contains can only conflict with add or remove, the runtime system will scan the log to ensure that no other iteration called add(x) or remove(x).

Note that for efficiency, a runtime system may use an optimized implementation of conflict logs which does not require a full scan of all outstanding method invocations to detect conflicts. The full version of this paper describes a number of these optimizations in more detail. 14

Commit pool: When an iteration attempts to commit, the commit pool checks two things: ( 1) that the iteration is at the head of the commit queue, and ( 2) that the priority of the iteration is higher than all the elements left in the set/Poset being iterated over. If both conditions are met, the iteration can successfully commit. If the conditions are not met, the iteration must wait until it has the highest priority in the system; its status is set to RTC, and the thread is allowed to begin another iteration.

When an iteration successfully commits, the thread that was running that iteration also checks the commit queue to see if more iterations in the RTC state can be committed. If so, it commits those iterations before beginning the execution of a new iteration. When an iteration has to be aborted, the status of its record is changed to ABORTED, but the commit pool takes no further action. Such iteration objects are lazily removed from the commit queue when they reach the head.

Conflict Arbitration: The other responsibility of the commit pool is to arbitrate conflicts between iterations. When iterating over an unordered set, the choice of which iteration to roll back in the event of a conflict is irrelevant. For simplicity, we always choose the iteration which detected the conflict. However, when iterating over an ordered set, the lower priority iteration must be rolled back while the higher priority iteration must continue. Without doing so, there exists the possibility of deadlock. Thus, when iteration i1 calls a method on a shared object and a conflict is detected with iteration i2, the commit pool arbitrates based on the priorities of the two iterations. If i1 has lower