Abstract
We study the implementation of a synchronous program as a set of multiple tasks running on the same computer, and scheduled by a real-time operating system using some preemptive scheduling policy, such as fixed priority or earliest-deadline first. Multitask implementations are necessary, for instance, in multiperiodic applications, when the worst-case execution time of the program is larger than its smallest period. In this case, a single-task implementation violates the schedulability assumption and, therefore, the synchrony hypothesis does not hold. We are aiming at semantics-preserving implementations, where, for a given input sequence, the output sequence produced by the implementation is the same as that produced by the original synchronous program, and this under all possible executions of the implementation. Straightforward implementation techniques are not semantics-preserving. We present an intertask communication protocol, called DBP, that is semantics-preserving and memory-optimal. DBP guarantees semantical preservation under all possible triggering patterns of the synchronous program: thus, it is applicable not only to time-, but also event-triggered applications. DBP works under both fixed priority and earliest-deadline first scheduling. DBP is a nonblocking protocol based on the use of intermediate buffers and manipulations of write-to/read-from pointers to these buffers: these manipulations happen upon arrivals, rather than executions of tasks, which is a distinguishing feature of DBP. DBP is memory-optimal in the sense that it uses as few buffers as needed, for any given triggering pattern. In the worst case, DBP requires, at most, N + 2 buffers for each writer, where N is the number of readers for this writer.
- Baleani, M., Ferrari, A., Mangeruca, L., and Sangiovanni-Vincentelli, A. 2005. Efficient embedded software design with synchronous models. In 5th ACM International Conference on Embedded Software (EMSOFT'05). 187--190. Google ScholarDigital Library
- Benveniste, A. and Berry, G. 1991. The synchronous approach to reactive and real-time systems. IEEE Proceedings 79, 1270--1282.Google ScholarCross Ref
- Benveniste, A., Caspi, P., Guernic, P. L., Marchand, H., Talpin, J., and Tripakis, S. 2002. A protocol for loosely time-triggered architectures. In Embedded Software (EMSOFT'02). LNCS, vol. 2491. Springer, New York. Google ScholarDigital Library
- Burch, J. and Dill, D. 1994. Automatic verification of pipelined microprocessor control. In CAV'94. Google ScholarDigital Library
- Caspi, P., Pilaud, D., Halbwachs, N., and Plaice, J. 1987. Lustre: A declarative language for programming synchronous systems. In 14th ACM Symp. POPL. Google ScholarDigital Library
- Caspi, P., Curic, A., Maignan, A., Sofronis, C., Tripakis, S., and Niebert, P. 2003. From Simulink to SCADE/Lustre to TTA: A layered approach for distributed embedded applications. In Languages, Compilers, and Tools for Embedded Systems (LCTES'03). ACM. Google ScholarDigital Library
- Chen, J. and Burns, A. 1997. A three-slot asynchronous reader-writer mechanism for multiprocessor real-time systems. Tech. Rep. YCS-286, Department of Computer Science, University of York. May.Google Scholar
- Clarke, E., Grumberg, O., and Peled, D. 2000. Model Checking. MIT Press, Cambridge, MA.Google Scholar
- Fersman, E. and Yi, W. 2004. A generic approach to schedulability analysis of real-time tasks. Nordic J. of Computing 11, 2, 129--147. Google ScholarDigital Library
- Halbwachs, N. 1992. Synchronous Programming of Reactive Systems. Kluwer, Academic Publ., Norwell, MA. Google ScholarDigital Library
- Halbwachs, N. 1998. Synchronous programming of reactive systems---a tutorial and commented bibliography. In Computer Aided Verification. 1--16. Google ScholarDigital Library
- Harbour, M., Klein, M., Obenza, R., Pollak, B., and Ralya, T. 1993. A Practitioner's Handbook for Real-Time Analysis: Guide to Rate-Monotonic Analysis for Real-Time Systems. Kluwer, Academic Publ., Norwell, MA. Google ScholarDigital Library
- Huang, H., Pillai, P., and Shin, K. 2002. Improving wait-free algorithms for interprocess communication in embedded real-time systems. In USENIX'02. Google ScholarDigital Library
- Liu, C. and Layland, J. 1973. Scheduling algorithms for multiprogramming in a hard real-time environment. Journal of the ACM 20, 1 (Jan.), 46--61. Google ScholarDigital Library
- Puri, A. and Varaiya, P. 1995. Driving safely in smart cars. In IEEE American Control Conference.Google Scholar
- Queille, J. and Sifakis, J. 1981. Specification and verification of concurrent systems in CESAR. In 5th Intl. Sym. on Programming. LNCS, vol. 137. Google ScholarDigital Library
- Ratel, C., Halbwachs, N., and Raymond, P. 1991. Programming and verifying critical systems by means of the synchronous data-flow programming language Lustre. In ACM-SIGSOFT Conference on Software for Critical Systems. Google ScholarDigital Library
- Scaife, N. and Caspi, P. 2004. Integrating model-based design and preemptive scheduling in mixed time- and event-triggered systems. In Euromicro conference on Real-Time Systems (ECRTS'04). Google ScholarDigital Library
- Sha, L., Rajkumar, R., and Lehoczky, J. 1990. Priority inheritance protocols: An approach to real-time synchronization. IEEE Trans. Computers. Google ScholarDigital Library
- Sofronis, C., Tripakis, S., and Caspi, P. 2006. A memory-optimal buffering protocol for preservation of synchronous semantics under preemptive scheduling. In 6th ACM International Conference on Embedded Software (EMSOFT'06). Google ScholarDigital Library
- Stankovic, J., Spuri, M., Ramamritham, K., and Buttazzo, G. 1998. Deadline Scheduling For Real-Time Systems: EDF and Related Algorithms. Kluwer Academic Publ., Norwell, MA. Google ScholarDigital Library
- Tripakis, S. 2002. Description and schedulability analysis of the software architecture of an automated vehicle control system. In Embedded Software (EMSOFT'02). LNCS, vol. 2491. Springer, New York. Google ScholarDigital Library
- Tripakis, S., Sofronis, C., Scaife, N., and Caspi, P. 2005. Semantics-preserving and memory-efficient implementation of inter-task communication on static-priority or EDF schedulers. In 5th ACM International Conference on Embedded Software (EMSOFT'05). 353--360. Google ScholarDigital Library
Index Terms
- Semantics-preserving multitask implementation of synchronous programs
Recommendations
A memory-optimal buffering protocol for preservation of synchronous semantics under preemptive scheduling
EMSOFT '06: Proceedings of the 6th ACM & IEEE International conference on Embedded softwareRecently, we have proposed a set of buffering schemes to preserve the semantics of a synchronous program when the latter is implemented as a set of multiple tasks running under preemptive scheduling. These schemes, however, are not optimal in terms of ...
Semantics-preserving and memory-efficient implementation of inter-task communication on static-priority or EDF schedulers
EMSOFT '05: Proceedings of the 5th ACM international conference on Embedded softwareIn previous work, we have proposed a method of preserving the functional semantics of model-based designs by the use of static checks and a double-buffer protocol [12]. However, this is restricted to static, fixed-priority scheduling and for high-...
Preemptive online scheduling with rejection of unit jobs on two uniformly related machines
We consider preemptive online and semi-online scheduling of unit jobs on two uniformly related machines. Jobs are presented one by one to an algorithm, and each job has a rejection penalty associated with it. A new job can either be rejected, in which ...
Comments