Collaboration

If two domains are collaborating and running concurrently there are likely to be times when one must wait until the other has come to some point in its work. I assume shared RAM here for that is often where much of their mutual state lives. One scheme is for each domain to own a cell in shared RAM where it can leave a note to the other when it is blocked. It thereupon becomes ready.

Each domain examines the other’s cell after it has taken any action that might unblock the other. When a domain sees that the other has left a note, it zaps the note and forks the other domain. To reveal bugs it is probably wise to note when the other domain is waiting before beginning to wait yourself. The following sequence in collaborating domains X and Y is to be avoided:

X observes obstacle.
Y removes that obstacle.
Y notes that there is no note from X.
X makes note for Y.
X becomes available.

To shift gears I will talk of exclusive locks. The two domains share a wait object for lock conflicts. An exclusive lock is a cell in RAM. The values in the lock are codes for:

0: No one holds the lock.
1: X holds the lock.
2: Y holds the lock.
3: X holds the lock and Y wants it.
4: Y holds the lock and X wants it.

Compare and swap is used to access the lock. The following is a magic definition of compare-and-swap which is good enough for this note. If lock holds v then CS(int v, b, int * lock) puts b in the lock and returns -1. Otherwise cs returns the value in the lock.

int CS(int v, b, int * lock){ // This block is magically atomic.
  if(v == *lock) {*lock = b; return -1;}
  return *lock;}

When X wants the lock it does:

z: if(CS(0, 1, &lock) != -1){ // conflict
     if(CS(2, 4, &lock) != -1) goto z;
     y: Wait on wait object.
     Set wait object’s time value to next year.
     if(lock == 4) {log("its probably been a year"); goto y;}
     go to z;}

When X is done with the lock it does:

z: if(CS(1, 0, &lock) != -1){ // Y wants this lock.
     if(CS(4, 0, &lock) != -1) crash;
     Set wait object’s time value to 0 (long past).
     }

Mutatis mutandis for Y. The somewhat costly invocation of the wait object happens only on lock conflict, not on typical lock usage. A correctness proof might note that

After X notices that Y holds the lock (lock=2) it does not access the lock again until the wait object returns.
Until X succeeds at setting the lock, it can only have the values 0 and 2.
After it succeeds the only agent with access to the lock is Y and its only act will be to set the lock first to 0 but soon possible to 2 again.

This code is admittedly delicate. It needs a version with many sharers.