Summary

This chapter has presented a discrete approach to modeling and implementing timed systems. The passage of time is signaled by regular successive ticks of a clock. In models, this tick appears as an action that is shared by the processes for which behavior depends on the passage of time. In implementations, the tick is an event broadcast by a time manager.

In discrete time models, we saw that the composition of processes with inconsistent timing resulted in a deadlock. This sort of deadlock is termed a time-stop. The order in which actions can occur in a timed model is restricted by making a maximal progress assumption. This ensures that an action occurs as soon as all participants are ready to perform it. Maximal progress is true for a model when we make the tick action low priority. This ensures that all ready actions occur within a clock cycle. Maximal progress thus reflects the implementation assumption that actions take negligible time to execute.

We described an implementation approach for timed systems that is event-based rather than thread-based. In this approach, each model process that has tick in its alphabet is translated into a timed object. Timed objects are invoked regularly by a time manager that dispatches timing events. We use a two-phase scheme that requires a pre-tick and tick event dispatch. Timed objects produce outputs during the pre-tick phase and compute the next state based on received inputs during the tick phase. This scheme permits one-way communication interactions to occur atomically within a single clock cycle. It was pointed out that multi-way interactions within a single clock cycle are not supported by this scheme. However, this did not cause problems in the example programs. The advantage of using timed objects rather than threads to implement timed processes is concerned with runtime efficiency. Timed objects are activated by method invocation, which has a lower overhead than context-switching threads. Further, since the pre-tick and tick methods run sequentially, there is no synchronization overhead to ensure mutual exclusion. Lastly, for programs largely concerned with display, the approach naturally synchronizes screen updates from multiple activities.

We should also point out some of the disadvantages of the event-based approach or the reader might wonder why we have devoted the main part of the book to a thread-based approach. Threads abstract from the detail of how activities should be scheduled to organize interaction. We saw that the timed approach was limited to uni-directional interactions in a single clock cycle. More complex interaction needs to be explicitly scheduled with either a multi-phase clock or, alternatively, over multiple clock cycles. This rapidly becomes unmanageable for complex interactions. Further, the event-based scheme required a timed object to examine its state every clock cycle to determine whether an event has occurred. A thread-based implementation may incur lower overhead for systems in which activities do not perform some action every clock cycle. The thread scheduler dispatches a thread only when there is some work for it to do.

Finally, we note that the model-based approach to concurrent programming permits a designer the flexibility to use either an event-based or thread-based implementation scheme or indeed a hybrid. We use the same modeling and analysis techniques for both implementation approaches.