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