Coordination

 

Introduction to AOP

Aspect-oriented programming is a partial solution to code tangling. In an aspect-oriented programming system, related details of a program are extracted and syntactically encapsulated. For example, details about thread synchronization, remote method calls, and exception handling may be separated from the body of the program.

The Coordination Language (Method Synchronization)

Method synchronization is achieved by defining exclusion sets and method managers. Exclusion sets define which methods should not be executed synchronously. Method managers provide additional, more flexible control.

Exclusion Sets

There are two types of exclusion sets - mutex (mutual exclusion) and selfex (self exclusion) sets.
A method f() in a mutex set may not be executed by a thread if any other method in the set excluding f() is being executed by a different thread. In other words, only one method in a mutex set may be executed at any given time. For example:

mutex { f,g }

If thread 1 begins execution of f(), thread 2 may not execute g(). Thread 2 is not prohibited from executing f(), nor is thread 1 prohibited from executing g().

A method f() in a selfex set may not be executed by more than one thread at a time. For example:

selfex { f }

If thread 1 begins execution of f(), thread 2 may not enter f() until thread 1 has returned. Thread 1 is not prohibited from re-entering f() recursively.
The synchronized keyword in java has the same effect as including the synchronized functions in both selfex and mutex sets. For example:

synchronized void f() { ... }
synchronized void g() { ... }

becomes

selfex { f,g }
mutex  { f,g }

Mutex/selfex example:

BankAccount {
  (@
  private int _balance = 0;
  @)
  public void deposit(int n) (@ _balance+=n; @)
  public void withdraw(int n) (@
    if(n>_balance) error();
    else _balance-=n;
  @)
  public int balance() (@ return _balance; @)
}

coordinator BankAccount {
  selfex { deposit,withdraw }
  mutex  { deposit,withdraw,balance }
}

In this example, if a thread is executing either deposit() or withdraw(), we don't want any other threads executing any other methods. If a thread is executing balance(), we don't want any other threads executing withdraw() or deposit(), but other threads are permitted to execute balance().

When specifying exclusion sets, you may also specify method arguments. For example, selfex { f } will match all methods of name f. Selfex { f(int) } will match only methods named f taking one int as an argument. For example:

SomeClass {
  int f() (@ ... @)
  int f(int) (@ ... @)
}

coordinator SomeClass {
  mutex { f, g() }
}

is the same as

coordinator SomeClass {
  mutex { f(), g() }
  mutex { f(int), g() }
}

That is, entry into any method named f is considered entry into ALL methods named f by the coordinator. If selfex { f } is declared, entry of one thread into f(int) will prohibit other threads from entering f(), f(char), etc.

Method Managers

In addition to exclusion sets, method managers help synchronize methods. The three types of method managers are requires expressions, on entry clauses, and on exit clauses.

Requires Expressions

A method's requires expression is a boolean expression of condition variables that must evaluate to true for a thread to be able to execute the method. Condition variables are types of booleans which may be declared in coordinators. Only condition variables may be seen in requires expressions.

On Entry/On Exit Clauses

On entry and on exit clauses are blocks of code to be executed just before or just after a thread executes a method. A method's on entry block will be executed if and only if a thread is given permission to execute that method. A method's on exit block is executed after the return statement (if one exists), but before control returns to the calling method. It is also possible to define additional data fields for these code fragments to communicate with each other. Condition variables are usually set in these blocks.

An example of this is a bounded stack which is shared by multiple threads:

BoundedStack {
  (@
  private Object[] array = new Object[20];
  private int used_slots = 0;
  @)

  public void put(Object x) (@ array[used_slots++] = x; @)
  public Object take() (@
    Object temp = array[--used_slots];
    array[used_slots] = null;
    return temp;
  @)
  public Object peek() (@
    return array[used_slots-1];
  @)
}

coordinator BoundedStack {
  selfex { put,take }
  mutex  { put,take,peek }

  condition empty = true, full = false;

  put requires(!full) {
    on exit {
      empty = false;
      if(used_slots == array.length) full = true;
    }
  }
  take requires(!empty) {
    on exit {
      full = false;
      if(used_slots == 0) empty = true;
    }
  }
  peek requires(!empty) {}
}

Coordinators are free to inspect the objects/classes which they coordinate, but should not make any changes.

Coordinated Visitors

Per-Class and Multi-Class Coordination

By default, coordination is done on a per-object basis (ie. a thread executing f() on one instance of a class will not interfere with a different thread executing f() on a different instance of the same class). There are times when this behavior is not appropriate (eg. the coordinated method tweaks some static variables).

Define a per-class coordinator as follows:

per class coordinator A {
  selfex { f }
}

Now, given that a1 and a2 are instances of A, if thread 1 begins execution of a1.f(), thread 2 is prohibited from entering not only a1.f() but also a2.f().

In order to specify that a coordinator operates on more than one class, simply list all the classnames, separated by commas:

coordinator A,B {
  ...
}

Note that a multi-class coordinator is implicitly static. Declaring a  object multi-class coordinator is an error.

Grammar

Cool                    ::= List(CoordinatorDeclaration) .
CoordinatorDeclaration  ::= [Granularity]
                            "coordinator"
                            CoordClassNames
                            CoordinatorBody .
Granularity             ::= "per class" | "per object" .
CoordClassNames         ::= CommaList(ClassName) .
CoordinatorBody         ::= "{" List(CoordinationSpec) "}" .
CoordinationSpec        ::= VarDeclaration
                          | SelfexMethodSet
                          | MutexMethodSet
                          | MethodManager .

VarDeclaration          ::= VarType VarDeclarators ";" .
VarDeclarators          ::= CommaList(VarDeclarator) .
VarDeclarator           ::= VariableName ["=" VarInitializer] .
VarInitializer          ::= JavaExpression .

SelfexMethodSet         ::= "selfex" QualifiedMethodNames ";" .
QualifiedMethodNames    ::= CommaList(QualifiedMethodName) .
QualifiedMethodName     ::= [GeneralClassName "."] MethodName .
GeneralClassName        ::= ClassName | "*" .

MutexMethodSet          ::= "mutex" "{" QualifiedMethodNames "}" .

MethodManager           ::= QualifiedMethodNames
                            [Requires]
                            "{" [EntryExitClauses] "}" .
Requires                ::= "requires"
                            "(" BooleanExpression ")" .
EntryExitClauses        ::= List(OnEntry | OnExit) .
OnEntry                 ::= "on entry" "{" JavaCode "}" .
OnExit                  ::= "on exit" "{" JavaCode "}" .

Outline of Implementation