ATL Use Case - From Hoare's Monitors to Dijkstra's Semaphores
Keywords
Hoare's Monitor Dijkstra's Semaphore, Programming |
Overview
This is a classic in synchronization. We propose an automatic translation from Hoare's monitors as defined in [1] into Dijkstra's semaphores as initially introduced in [2]. The ATL transformation code follows the rules given in [1]. A complete reprint of this paper is available at: http://www.acm.org/classics/feb96/. The overall approach is summarized in the following figure:
As a classical example, we can take the readers and writers problem:
Another example is the bounded buffer presented at: http://www.acm.org/classics/feb96/bounded_buffer.html. In [1] a set of rules for translating from monitors to semaphores is given to prove that monitors can be implemented by semaphores. We reproduce below these rules that may be found at: http://www.acm.org/classics/feb96/interpretation.html. "Obviously, we shall require for each monitor a Boolean semaphore "mutex" to ensure that the bodies of the local procedures exclude each other. The semaphore is initialized to 1; a P(mutex) must be executed on entry to each local procedure, and a V(mutex) must usually be executed on exit from it. When a process signals a condition on which another process is waiting, the signaling process must wait until the resumed process permits it to proceed. We therefore introduce for each monitor a second semaphore "urgent" (initialized to 0), on which signaling processes suspend themselves by the operation P(urgent). Before releasing exclusion, each process must test whether any other process is waiting on urgent, and if so, must release it instead by a V(urgent) instruction We therefore need to count the number of processes waiting on urgent, in an integer "urgentcount" (initially zero). Thus each exit from a procedure of a monitor should be coded:
Finally, for each condition local to the monitor, we introduce a semaphore "condsem" (initialized to 0), on which a process desiring to wait suspends itself by a P(condsem) operation. Since a process signaling this condition needs to know whether anybody is waiting, we also need a count of the number of waiting processes held in an integer variable "condcount" (initially 0). The operation "cond.wait" may now be implemented as follows (recall that a waiting program must release exclusion before suspending itself):
The signal operation may be coded:
In this implementation, possession of the monitor is regarded as a privilege which is explicitly passed from one process to another. Only when no one further wants the privilege is mutex finally released. This solution is not intended to correspond to recommended "style" in the use of semaphores. The concept of a condition-variable is intended as a substitute for semaphores, and has its own style of usage, in the same way that while loops or coroutines are intended as a substitute for jumps. In many cases, the generality of this solution is unnecessary, and a significant improvement in efficiency is possible.
Significant improvements in efficiency may also be obtained by avoiding the use of semaphores, and by implementing conditions directly in hardware, or at the lowest and most uninterruptible level of software (e.g. supervisor mode). In this case, the following optimizations are possible.
In summary we take into consideration the following rules from above:
Why is this ATL transformation interesting?For several reasons:To conclude, we provide below a set of screenshots showing the different input/output files provided/created with this use case:
|
Related Use Cases
None at the current time. |
References
[1] | Hoare, C.A.R Monitors: An Operating System Structuring Concept Communications of the ACM, Vol. 17, No. 10. October 1974, pp. 549-557 |
[2] | Dijkstra, E. W. Cooperating Sequential Processes. In programming Languages (Ed. F. Genuys), Academic Press, New York. |
Download
Complete scenario |
Scenario available in the ATL transformation zoo (with source files). |
Program Metamodel |
Program metamodel is expressed in the KM3 textual format. |
Acknowledgement
The present work is being supported by the Usine Logicielle project of the System@tic Paris Region Cluster. This work has also been supported by the Atlantic federation of labs. |
General Information
- March 2007
- By Freddy Allilaire (INRIA)
Please, ask your questions on the M2M newsgroup