12.2 Implementing Timed Systems

Timed concurrent systems can be implemented in Java by a set of threads which use sleep() and timed wait() to synchronize with time. We can characterize this as a thread-based approach since active entities in the model are translated into threads in an implementation. This approach to translating models into programs was used in the preceding chapters for non-timed systems. In this chapter, we exploit the time-driven nature of the models and use an event-based approach in which active entities are translated into objects that respond to timing events. Essentially, the tick action in the model becomes a set of events broadcast by a time manager to all the program entities that need to be aware of the passage of time. The organization of a timed system implementation conforms to the Announcer – Listener architecture described in Chapter 11, with the time manager acting as the announcer and timed objects as the listeners. We have chosen this event-based approach for two reasons. First, the translation from timed model to timed implementation is reasonably direct; and secondly, for timed systems with many activities the resulting implementation is more efficient than the thread-based approach since it avoids context-switching overheads. However, as discussed in the following, the approach also has some limitations when compared with a thread-based approach.

12.2.1 Timed Objects

Each process in a timed model that has tick in its alphabet becomes a timed object in an implementation. A timed object is created from a class that implements the Timed interface listed in Program 12.1.

Program 12.1: Timed interface.

 public interface Timed {   void pretick() throws TimeStop;   void tick(); }

Each timed object is registered with the time manager, which implements a two-phase event broadcast. In phase 1, the pretick() method of each timed object is invoked and, in phase 2, the tick() method is invoked. The behavior of a timed object is provided by the implementation of these two methods. In the pre-tick phase, the object performs all output actions that are enabled in its current state. These may modify the state of other timed objects. In the tick phase, the object updates its state with respect to inputs and the passage of time. Two phases are needed to ensure that communication between timed objects completes within a single clock cycle. We clarify the translation from model processes into timed objects, with pretick() and tick() methods and the use of the TimeStop exception, in the examples that follow.

CountDown Timer

A version of the countdown timer model introduced in Chapter 2 is given below.

 COUNTDOWN (N=3)   = COUNTDOWN[N], COUNTDOWN[i:0..N] =   (when(i>0)  tick -> COUNTDOWN[i-1]   |when(i==0) beep -> STOP   ).

The COUNTDOWN process outputs a beep action after N ticks and then stops. The implementation is given in Program 12.2. The translation from the model is straightforward. Each invocation of the tick() method decrements the integer variable i. When i reaches zero, the next invocation of pretick() performs the beep action and the timer stops by removing itself from the time manager. The operation of TimeManager is described in the next section.

Program 12.2: TimedCountDown class.

 class TimedCountDown implements Timed {   int i; TimeManager clock;   TimedCountDown(int N, TimeManager clock) {     i = N; this.clock = clock;     clock.addTimed(this); // register with time manager   }   public void pretick() throws TimeStop {     if (i==0) {         // do beep action        clock.removeTimed(this); // unregister = STOP     }   }   public void tick(){ --i; } }

Timed Producer – Consumer

The next example implements the producer – consumer model of section 12.1.1. To keep the code succinct, the timed class definitions are nested inside the ProducerConsumer class of Program 12.3. The class creates the required instances of the Producer, Consumer and TimeManager classes.

Program 12.3: ProducerConsumer class.

 class ProducerConsumer {   TimeManager clock = new TimeManager(1000);   Producer producer = new Producer(2);   Consumer consumer = new Consumer(2);   ProducerConsumer() {clock.start();}   class Consumer implements Timed {...}   class Producer implements Timed {...} }

For convenience, the PRODUCER process is listed below:

 PRODUCER(Tp=3) =   (item -> DELAY[1]), DELAY[t:1..Tp] =   (when(t==Tp) tick -> PRODUCER   |when(t<Tp) tick -> DELAY[t+1]   ).

Initially, the producer outputs an item and then waits for Tp clock ticks before outputting another item. The timed class that implements this behavior is listed in Program 12.4.

Program 12.4: Producer class.

 class Producer implements Timed {   int Tp,t;   Producer(int Tp) {     this.Tp = Tp; t = 1;     clock.addTimed(this);   }   public void pretick() throws TimeStop {     if (t==1) consumer.item(new Object());   }   public void tick() {     if (t<Tp) { ++t; return;}     if (t==Tp) { t = 1;}   } }

An instance of the Producer class is created with t = 1 and the consumer.item() method is invoked on the first pre-tick clock phase after creation. Each subsequent tick increments t until a state is reached when another item is output. The behavior corresponds directly with PRODUCER.

Now let us examine how the item() method is handled by the consumer. The timed model for the consumer is shown below. The consumer waits for an item and then delays Tc ticks before offering to accept another item.

 CONSUMER(Tc=3) =   (item -> DELAY[1] | tick -> CONSUMER), DELAY[t:1..Tc] =   (when(t==Tc) tick -> CONSUMER   |when(t<Tc) tick -> DELAY[t+1]   ).

The implementation of CONSUMER is listed in Program 12.5.

Program 12.5: Consumer class.

 class Consumer implements Timed {   int Tc,t; Object consuming = null;   Consumer(int Tc) {     this.Tc = Tc; t = 1;     clock.addTimed(this);   }   void item(Object x) throws TimeStop {     if (consuming!=null) throw new TimeStop();     consuming = x;   }   public void pretick() {}   public void tick() {     if (consuming==null) return;     if (t<Tc) { ++t; return;}     if (t==Tc) {consuming = null; t = 1;}   } }

In the Consumer class, the tick() method returns immediately if the consuming field has the value null, implementing the behavior of waiting for an item. The item() method sets this field when invoked by the producer. When consuming is not null, the tick() method increments t until Tc is reached and then resets consuming to null indicating that the item has been consumed and that another item can be accepted. Effectively, consuming represents the DELAY states in the model. If the producer tries to set consuming when it is not null then a TimeStop exception is thrown. This signals a timing inconsistency in exactly the same way that a time-stop deadlock in the model is the result of a timing inconsistency. TimeStop is thrown if the producer tries to output an item when the previous item has not yet been consumed. As we see in the next section, a TimeStop exception stops the time manager and consequently, no further actions are executed.The implementation of producer – consumer has exactly the same property as the model. For correct execution, Tc must be less than or equal to Tp. Note that, in the Consumer class, the method pretick() has no implementation because the class has no outputs.

The Two-Phase Clock

The operation of the two-phase clock cycle should now be clear. Methods on other objects are invoked during the pre-tick phase and the changes in state caused by these invocations are recognized in the tick phase. This ensures that actions complete in a single clock cycle. However, this scheme only approximates the maximal progress property of timed models. Maximal progress ensures that all actions that can occur happen before the next tick. Our implementation scheme only gives each timed object one opportunity to perform an action, when its pretick() method is executed. A multi-way interaction between timed objects thus requires multiple clock cycles. An example of a multi-way interaction would be a request action followed by a reply followed by an acknowledgment (three-way). Maximal progress in the model ensures that such a multi-way interaction would occur within a single clock cycle if no intervening tick events were specified. We could implement a multi-phase clock scheme to allow multi-way interaction in a single clock cycle, however this complexity might be better dealt with by reverting to a thread-based implementation scheme. In fact, the examples later in the chapter show that the two-phase scheme is sufficiently powerful to implement quite complex systems that exhibit the same behavior as their models. We take care that multi-way interaction within a single clock cycle is not required. This usually means that we introduce an intervening tick in the model, for example between a request and a reply.

In addition to the ease with which models can be translated into implementations, the event-based implementation scheme has the advantage, when compared to the thread-based scheme, that we do not have to synchronize access to shared objects. The activations of the tick() and pretick() methods of a timed object are indivisible with respect to other a ctivations of these methods. This is because the methods are dispatched sequentially by the time manager. Method dispatch incurs much less overhead than context switching between threads. Consequently, the event-based scheme is more efficient in systems with large numbers of time-driven concurrent activities. An example of such a system is presented in the final section of the chapter.

12.2.2 Time Manager

The TimeManager class (Program 12.6) maintains a list of all those timed objects which have registered with it using addTimed(). The pretick() and tick() methods are invoked on all Timed objects in this list by the TimeManager thread every delay milliseconds. The value of delay can be adjusted by an external control, such as a slider through the AdjustmentListener interface that the class implements.

Program 12.6: TimeManager class.

 public class TimeManager extends Thread                       implements AdjustmentListener{   volatile int delay;   volatile ImmutableList<Timed> clocked = null;   public TimeManager(int d) {delay = d;}   public void addTimed(Timed el) {     clocked = ImmutableList.add(clocked,el);   }   public void removeTimed(Timed el) {     clocked = ImmutableList.remove(clocked,el);   }   public void     adjustmentValueChanged(AdjustmentEvent e) {     delay = e.getValue();   }   public void run () {     try {       while(true) {         try {           for (Timed e: clocked) e.pretick();  //pretick broadcast                for (Timed e :clocked) e.tick();   //tick broadcast         } catch (TimeStop s) {             System.out.println("*** TimeStop");             return;         }         Thread.sleep(delay);       }     } catch (InterruptedException e){}   } }

The data structure used to hold the list of timed objects must be designed with some care. A pretick() or tick() method may cause a timed object to remove itself from the list. To ensure that such a removal does not destroy the integrity of the list data structure, we use an immutable list that does not change during an enumeration off it. If a removal occurs during a broadcast, this removal generates a new list which is used for the next broadcast. The class implementing the immutable list is given in Program 12.7.

Program 12.7: ImmutableList class.

 public class ImmutableList<T> implements Iterable<T> {   ImmutableList<T> next;   T item;   private ImmutableList          (ImmutableList<T> next, T item) {     this.next = next; this.item=item;   }   public static<T> ImmutableList<T> add            (ImmutableList<T> list, T item) {     return new ImmutableList<T>(list, item);   }   public static<T> ImmutableList<T> remove            (ImmutableList<T> list, T target) {     if (list == null) return null;     return list.remove(target);   }   private ImmutableList<T> remove(T target) {     if (item == target) {       return next;     } else {       ImmutableList<T> new_next = remove(next,target);       if (new_next == next ) return this;       return new ImmutableList<T>(new_next,item);     }   } }

The delay and clocked TimeManager fields (Program 12.6) are declared to be volatile since they can be changed by external threads. The keyword volatile ensures that the run() method reads the actual value of these fields before every broadcast. It prevents a compiler optimizing access by storing the fields in local variables or machine registers. If such an optimization occurred, the values would be read only once, when the run() method started, and it would not see subsequent updates.

The pretick() method allows a timed object to throw a TimeStop exception if it detects a timing inconsistency. This exception terminates the TimeManager thread. Consequently, a timing inconsistency in an implementation has the same behavior as a model with timing inconsistency – no further actions can be executed.