logo of the SSW institute ;)
Computer Science
System Software

Home

General
Staff
Contact
Partners
Alumni

Research
Areas
Projects
Papers
Books
Reports
Awards

Teaching
Lectures
Exams
B.Projects
M.Theses
PhD Theses
Go Abroad

Misc
Talks
Library
Gallery
Links
Search

Webmaster


Back to index

6 Applications

In this chapter we present two applications of the composable message semantics framework described in Chapter 4. The framework is not meant to be used directly by an application, but favours the introduction of an additional layer in order to ease its usage. The applications presented in this chapter are strictly local, i.e. they stay within one address space. For simplicity we use the layer DecObjects as described in Section 4.8.
The first example presented in Section 6.1 tracks and prints dynamic traces of method invocations. The user interface is kept primitive in order to demonstrate how easily one can gain information on method invocations by using our composable message semantics. The second example in Section 6.2 uses message semantics to synchronise invocations of different methods, objects and/or even classes.

6.1 Dynamic Traces

The module Recorder records method invocations. Every invocation made on a registered object is recorded and, depending on the installed viewer, the appropriate action is initiated. On purpose, we kept the interface as simple as possible. The invocation filter that records the invocations is not exported. Therefore, it cannot be combined with other filters and abstractions.
Interface Description
DEFINITION Recorder;

  IMPORT SYS := SYSTEM, Linearizers;

  TYPE
    Container = RECORD
      class: INTEGER;
      b: BOOLEAN;
      i: LONGINT;
      x: REAL;
      y: LONGREAL;
      c: CHAR;
      s: SET;
      str: ARRAY 1024 OF CHAR;
    END ;
    Viewer = POINTER TO ViewerDesc;
    ViewerDesc = RECORD
      PROCEDURE (v: Viewer) After (obj: SYS.PTR; id: LONGINT; s: Linearizers.Stream);
      PROCEDURE (v: Viewer) Before (obj: SYS.PTR; id: LONGINT; s: Linearizers.Stream);
      PROCEDURE (v: Viewer) Method (obj: SYS.PTR; id: LONGINT;
                                          VAR name: ARRAY OF CHAR);
      PROCEDURE (v: Viewer) Name (obj: SYS.PTR; VAR name: ARRAY OF CHAR);
      PROCEDURE (v: Viewer) NextParameter (VAR vals: Container);
      PROCEDURE (v: Viewer) OpenParameters (VAR vals: Container; obj: SYS.PTR;
                                                   id: LONGINT; s: Linearizers.Stream);
    END ;

  VAR
    stdViewer: Viewer;

  PROCEDURE Register (VAR res: SYS.PTR; obj: SYS.PTR; v: Viewer; name: ARRAY OF CHAR);

END Recorder.

Registering Objects
Register (res, original, v, name)
registers the object original for the recording of later method invocations. After it has been registered, every method invoked on res is intercepted and recorded as defined by the viewer v. Invocations on original are handled as before. The identifier name is assigned to the decorated object res and is passed along whenever an invocation is passed to the viewer. If no viewer is passed in v (v = NIL), the default viewer is taken as defined by the global variable stdViewer. Defining individual viewers allows different facilities/visualisations for different objects.
Access to Parameters
A Container describes one parameter at a time and can be used to iterate over the actual parameters of an intercepted invocation. Our implementation of Recorder supports only parameters of primitive types or arrays of characters (open and fixed size). A container has a field for all possible parameter types. The type identifier stored in the field class determines the field that actually holds the value. class uses the same constants as defined and used in module Ref.
Visualisation of Invocations
A Viewer object is responsible for one or several recorded objects. The recording semantic calls the methods Before and After right before and right after every intercepted invocation. Actual implementations of Viewer must implement these methods as required by their specification:
  • viewer.Before(obj, id, s) is called right before a recorded method is invoked. obj refers to the receiver of the invocation, id denotes the called method and s contains the streamed parameters.
  • viewer.After(obj, id, s) is called after a recorded method has been invoked. obj refers to the receiver of the invocation, id denotes the called method and s contains the streamed result.
  • viewer.Method(obj, id, name) returns the name of the method denoted by obj and the method selector id. This method is used to convert the selector used within the composable message semantics framework into a human readable form.
  • viewer.Name(obj, name) returns the name of the object obj, as assigned when the object was registered for recording.
  • viewer.OpenParameters(vals, obj, id, s) opens the parameter stream s after the invocation of method id on object obj. vals will contain the value of the first actual parameter.
  • viewer.NextParameter(vals) advances to the next parameter of the examined invocation. A value of Ref.End in vals.class indicates that there are no more parameters.
Recorder.Viewer offers default implementations for Before and After. Before prints the name of the receiver and the name of the invoked method. It uses indentation in order to show the call chain. After inverses the indentation done by Before (see the example output below).
Examples
MODULE TestRec;

IMPORT Recorder, SYS := SYSTEM, Linearizers;

TYPE
  Object = POINTER TO ObjectDesc;
  ObjectDesc = RECORD
  END;

VAR a, b: Object; i: INTEGER;

PROCEDURE (o: Object) N;
BEGIN
END N;

PROCEDURE (o: Object) M (val: INTEGER);
BEGIN
  IF val>4 THEN b.M(0) END;
  b.N
END M;

BEGIN
  NEW(a); NEW(b); i:=17;
  Recorder.Register(a, a, NIL, "Object a");
  Recorder.Register(b, b, NIL, "Object b");
  a.M(3);
  b.M(i)
END TestRec.

The above example registers two objects for recording and invokes some methods that again invoke other methods recursively. We use the same variables to hold the decorated objects as were used for the real objects. This way, we automatically adapt all clients to use the decorated version of our objects a and b. The actual invocation trace, which is generated by the execution of this test program, is as follows:
Object a.M
  Object b.N
Object b.M
  Object b.M
    Object b.N
  Object b.N
The above trace was generated by registering the objects a and b. There were no other necessary modifications to the program. However, sometimes, one would like to have another view of the invocation trace. To achieve this, one has to implement a sub-type of Viewer, which overrides the methods Before, After or both of them.
TYPE
  Viewer = POINTER TO ViewerDesc;
  ViewerDesc = RECORD (Recorder.ViewerDesc)
  END;

VAR
  v: Viewer;

PROCEDURE (v: Viewer) Before (obj: SYS.PTR; id: LONGINT; s: Linearizers.Stream);
VAR methName, objName: ARRAY 32 OF CHAR; c: Recorder.Container;
BEGIN
  v.Method(obj, id, methName);
  v.Name(obj, objName);
  Out.String(objName); Out.Char('.'); Out.String(methName);
  IF methName = "M" THEN
    v.OpenParameters(c, obj, id, s);
    Out.Char(' '); Out.Int(c.i, 0)
  END;
  Out.Ln
END Before;

BEGIN
  NEW(v);
  É
  Recorder.Register(a, a, v, "Object a");
  Recorder.Register(b, b, v, "Object b");

Instead of NIL, we have to pass an instance of our viewer type while registering our objects. We override the method Before. We make no super-call, i.e. there is no indentation. Additionally, we check whether the called method is M. If this is the case, we know that we currently look at the parameter val and print its value. The invocation trace will look like this:
Object a.M 3
Object b.N
Object b.M 17
Object b.M 0
Object b.N
Object b.N
Implementation of the Module Recorder
Most of the code of Recorder is responsible for the generated visualisation and for the access to the streamed parameters. The code necessary for the recording semantic is implemented in two procedures and uses the layer DecObjects.
TYPE
  Invocation = POINTER TO InvocationDesc;
  InvocationDesc = RECORD (Invocations.InvocationFilterDesc)
  END;

PROCEDURE (inv: Invocation) Invoke (obj: SYS.PTR; id: LONGINT; s: Linearizers.Stream) :
                                        Linearizers.Stream;
VAR o :Object;
BEGIN
  o := FindObject(obj);
  o.viewer.Before(obj, id, s);
  s := inv.Invoke^ (obj, id, s);
  o.viewer.After(obj, id, s);
  RETURN s
END Invoke;

Method Invocation implements the actual recording invocation filter, which activates the associated viewer before and after it forwards intercepted invocations to the next filter. FindObject searches the descriptor object for the receiver obj. The module Recorder maintains these descriptors o, which maintain a relation from the invoked object obj to the associated viewer o.viewer. They contain the name of the object and the assigned viewer. Before and after the filter forwards the invocation to the next filter/abstraction, it calls the corresponding viewer methods Before and After.
The second part where Recorder accesses the semantics framework is where it registers objects for recording.
VAR
  inv: Invocation;

PROCEDURE Register* (VAR res: SYS.PTR; obj: SYS.PTR; v: Viewer; name: ARRAY OF CHAR);
VAR c: Invocations.Class; m: Invocations.Method; ret: INTEGER; o: Object;
BEGIN
  IF v = NIL THEN v := stdViewer END;
  c := Invocations.GetClass(obj);
  Linearizers.Register(c.module, c.name, Marshaller);
  m := c.methods;
  WHILE m# NIL DO
    m.SetCallerInvocation(inv);
    m := m.next
  END;
  DecObjects.SetSemantics(obj, c, res, ret);
  ASSERT(ret = DecObjects.ok);
  NEW(o);
  o.viewer := v;
  o.dec := SYS.VAL(LONGINT, res);
  ... register o for look-up in invocation filter
END Register;

É
NEW(inv); inv.next := DecObjects.Invocation();

Register prepares obj for decoration, decorates it by calling DecObjects.SetSemantics and updates the list of decorated objects. To prepare obj for decoration, we first have to assign a marshaller to the type of obj. We use a simple marshaller that marshals nothing. Second, we have to assign the invocation semantic inv that includes our filter. We build this semantic in the module body and assign it to every method of obj.

6.2 Synchronisation

The second example demonstrates the implementation and usage of a new invocation filter, which allows us to decorate any messages with the semaphore operations Up and Down. Using such a filter we can solve many classic synchronisation problems in an elegant way. To reduce the size of the example we again use DecObjects. However, the application of the new filter is the same for DObjects (see Section 9.1). Our new filter is implemented in the module Locks.
MODULE Locks;

IMPORT Invocations, Linearizers, Threads, SYS := SYSTEM;

TYPE
  Semaphore* = POINTER TO Threads.Semaphore;
  Lock* = POINTER TO InvocationDesc;
  InvocationDesc = RECORD (Invocations.InvocationFilterDesc)
    sem: Semaphore
  END;

PROCEDURE (lock: Lock) Invoke* (obj: SYS.PTR; id: LONGINT; s: Linearizers.Stream) :
                                    Linearizers.Stream;
BEGIN
  lock.sem.Down;
  s := lock.Invoke^(obj, id, s);
  lock.sem.Up;
  RETURN s
END Invoke;

PROCEDURE New* (sem: Semaphore) : Lock;
VAR lock: Lock;
BEGIN
  NEW(lock);
  lock.sem := sem;
  RETURN lock
END New;

END Locks.

We implement the new invocation filter Lock that forwards an invocation only after it owns the semaphore sem. It uses the semaphores offered by the module Threads. The procedure New returns a new instance of the filter. As we can see, the implementation is extremely simple. A more complex implementation could maintain a set of semaphores instead of only one. However, the above implementation is sufficient for our example. In the remaining section we show its usefulness with the help of an extended example.
Extended Example: The Dining Philosophers
The problem of the dining philosophers [Dij71] is well known in the field of concurrent programming. It is sufficiently simple to be understandable, yet subtle enough to be challenging (see [Ben90] for more details).
The problem sees five philosophers around a round table (see Figure 6.1). Each philosopher thinks and eats alternatively. In order to eat, he has to have both the fork on his left and the fork on his right side. However, these forks are also used by the two adjacent philosophers. Our solution must guarantee that a philosopher eats only if he has both forks, that no philosopher starves and that there are no deadlocks. In our first implementation version we show an Oberon implementation that ignores all necessary synchronisation aspects. Of course, the implementation is not correct, as it does not guarantee that philosophers eat only while they own both of their forks.
MODULE Philosophers;

IMPORT Threads;

TYPE
  Eater* = POINTER TO EaterDesc;
  EaterDesc* = RECORD (Threads.ThreadDesc)
  END;

VAR
  phils: ARRAY 5 OF Eater;

PROCEDURE (me: Eater) Think*;
END Think;

PROCEDURE (me: Eater) Eat*;
END Eat;

PROCEDURE Start;
VAR t: Threads.Thread; self: Eater;
BEGIN
  t := Threads.ActiveThread();
  self := t(Eater);
  LOOP
    self.Think;
    self.Eat
  END
END Start;

PROCEDURE Dinner*;
VAR i: INTEGER;
BEGIN
  FOR i := 0 TO 4 DO
    NEW(phils[i]);
    Threads.Start(phils[i], Start, 10000)
  END
END Dinner;

END Philosophers.

We start the program in procedure Dinner by creating a thread for every philosopher. These threads start their execution in procedure Start. Start casts the the current thread t to our philosopher type Eater. It now has access to the philosopher self, which is associated to this thread. Finally, we start an endless loop, in which we repeatedly call the methods Think and Eat.
Our next version tries to ensure the correctness of the algorithm by using semaphores to synchronise the different threads.
MODULE Philosophers;

IMPORT Threads;

TYPE
  Eater* = POINTER TO EaterDesc;
  EaterDesc* = RECORD (Threads.ThreadDesc)
    left, right: INTEGER;
  END;

VAR
  phils: ARRAY 5 OF Eater;
  forks: ARRAY 5 OF Threads.Semaphore;
  room: Threads.Semaphore;

PROCEDURE (me: Eater) Think*;
END Think;

PROCEDURE (me: Eater) Eat*;
END Eat;

PROCEDURE Start;
VAR t: Threads.Thread; self: Eater;
BEGIN
  t := Threads.ActiveThread();
  self := t(Eater);
  LOOP
    self.Think;
    room.Down;
    forks[self.left].Down; forks[self.right].Down;

    self.Eat;
    forks[self.left].Up; forks[self.right].Up;
    room.Up

  END
END Start;

PROCEDURE Dinner*;
VAR i: INTEGER;
BEGIN
  room.Init(4);
  FOR i := 0 TO 4 DO

    NEW(phils[i]);
    forks[i].Init(1);
    phils[i].left := i;
    phils[i].right := (i+1) MOD 5
  END;

  FOR i := 0 TO 4 DO
    Threads.Start(phils[i], Start, 10000)
  END
END Dinner;

END Philosophers.

As one can see, quite a few additions are necessary (bold lines). And, even worse, they are spread all over the complete source code. We have to add some global variables, initialise them and add additional code before and after a philosopher starts to eat. Additionally, we even have to change the existing type EaterDesc, as a philosopher has to identify his forks and has to know the order in which to take them. This leads to changes to the type EaterDesc, which again leads to a changed module interface, i.e. all clients have to be recompiled.
In our next version we try to get rid of the above disadvantages, i.e. to concentrate the changes in a few places and not to modify the module interface. We use the interception framework to achieve this, by applying a lock filter to the invocations of method Eat.
MODULE Philosophers;

IMPORT Threads, Locks, Invocations, DecObjects;

TYPE
  Eater* = POINTER TO EaterDesc;
  EaterDesc* = RECORD (Threads.ThreadDesc)
  END;

VAR
  phils: ARRAY 5 OF Eater;

PROCEDURE (me: Eater) Think*;
END Think;

PROCEDURE (me: Eater) Eat*;
END Eat;

PROCEDURE Start;
VAR t: Threads.Thread; self: Eater;
BEGIN
  t := Threads.ActiveThread();
  self := t(Eater);
  LOOP
    self.Think;
    self.Eat;
  END
END Start;

PROCEDURE Dinner*;
VAR
  i, res: INTEGER; t: Eater; l, r, first: Locks.Lock; c: Invocations.Class; m: Invocations.Method;
  forks: ARRAY 5 OF Locks.Semaphore;
  room: Locks.Semaphore;

BEGIN
  FOR i := 0 TO 4 DO
    NEW(forks[i]); forks[i].Init(1)
  END;
  NEW(room); room.Init(4);

  FOR i := 0 TO 4 DO
    NEW(t);
    c := Invocations.GetClass(t);
    m := c.GetMethod("Eat");
    first := Locks.New(room); l := Locks.New(forks[i]); r := Locks.New(forks[(i+1) MOD 5]);
    first.next := l; l.next := r; r.next := DecObjects.Invocation();
    m.SetCallerInvocation(first);
    DecObjects.SetSemantics(t, c, phils[i], res);

  END;

  FOR i := 0 TO 4 DO
    Threads.Start(phils[i], Start, 10000)
  END
END Dinner;

END Philosophers.

We can see (bold lines), that the necessary changes are concentrated in the initialisation part. The actual algorithm does not change and the module interface is stable. We first allocate and initialise the necessary semaphores. We use them to initialise three locking invocation filters for the invocation of Eat on every philosopher. Depending on the philosopher's number, we assign the filters to the appropriate semaphores. We concatenate the filters and assign the composed semantic to the method Eat. We finally decorate the philosopher with the new semantics and assign the decorator to phils[i] (see Figure 6.2). As one can see in this version, there are many useful applications for our composable message semantics. The ability to add arbitrary semantics allows us to write cleaner programs that are more legible and understandable. Arbitrary semantics allow the design to stand out more clearly and help the programmer to separate different concerns.
Another advantage of using synchronisation filters is, that they are much more flexible than fixed semantics are, e.g. synchronised methods in Java [GoJS96]. Synchronised Java methods allow only one lock for synchronisation, i.e. the lock of the receiver. More complex requirements have to be solved using the 'synchronized' statement. This again spreads the changes over different parts of the source code and does not prevent the programmer from making subtle errors by forgetting/omitting the synchronisation code in some places.

Back to index