Christos Sofronis
ABSTRACT
Recently, 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 memory (buffer usage). In this paper we propose a new protocol which generalizes the previous schemes. The new protocol is not only semantics-preserving but also memory-optimal in two senses: first, in terms of the number of buffers required to preserve semantics in the worst case (i.e.,for the "worst" possible arrival/execution pattern of the tasks); second, in terms of the number of buffers required to preserve semantics for any arrival/execution pattern and at any time, assuming no knowledge of future arrivals.
- Audsley, N., Burns, A., Davis, R., Tindell, K., and Wellings, A. Fixed priority pre-emptive scheduling: An historical perspective.Real Time Systems 8, 2--3 (1995). Google Scholar
Digital Library
- Baleani, M., Ferrari, A., Mangeruca, L., and Sangiovanni-Vincentelli, A. Efficient embedded software design with synchronous models. In 5th ACM International Conference on Embedded Software (EMSOFT'05) (2005), pp. 187--190. Google ScholarDigital Library
- Benveniste, A., and Berry, G. The synchronous approach to reactive and real-time systems. IEEE Proceedings 79 (Sept. 1991), 1270--1282.Google ScholarCross Ref
- Benveniste, A., Caspi, P., Guernic, P. L., Marchand, H., Talpin, J., and Tripakis, S. A protocol for loosely time-triggered architectures.In Embedded Software (EMSOFT'02) (2002), vol. 2491 of LNCS Springer. Google ScholarDigital Library
- Bhattacharyya, S. S., Murthy, P. K., and Lee, E. A. Software Synthesis from Dataflow Graphs Kluwer, 1996. Google ScholarDigital Library
- Caspi, P., Curic, A., Maignan, A., Sofronis, C., Tripakis, S., and Niebert, P. From Simulink to SCADE/Lustre to TTA: a layered approach for distributed embedded applications. In Languages, Compilers, and Tools for Embedded Systems (LCTES'03) (2003), ACM. Google ScholarDigital Library
- Chen, J., and Burns, A. A three-slot asynchronous reader-writer mechanism for multiprocessor real-time systems. Tech. Rep. YCS-286, Department of Computer Science, University of York,May 1997.Google Scholar
- Fersman, E., and Yi, W. A generic approach to schedulability analysis of real-time tasks. Nordic J. of Computing 11 2 (2004), 129--147. Google ScholarDigital Library
- Halbwachs, N. Synchronous Programming of Reactive Systems Kluwer, 1992. Google ScholarDigital Library
- Harbour, M., Klein, M., Obenza, R., Pollak, B., and Ralya, T. A Practitioner's Handbook for Real-Time Analysis: Guide to Rate-Monotonic Analysis for Real-Time Systems Kluwer, 1993. Google ScholarDigital Library
- Huang, H., Pillai, P., and Shin, K. Improving wait-free algorithms for interprocess communication in embedded real-time systems. In USENIX'02 (2002). Google ScholarDigital Library
- Lee, E., and Messerschmitt, D. Synchronous dataflow. Proceedings of the IEEE 75 9 (1987), 1235--1245.Google ScholarCross Ref
- Liu, C., and Layland, J. Scheduling algorithms for multiprogramming in a hard real-time environment. Journal of the ACM 20 1 (Jan.1973), 46--61. Google ScholarDigital Library
- Murthy, P. K., and Bhattacharyya, S. S. Buffer merging- a powerful technique for reducing memory requirements of synchronous dataflow specifications. ACM Transactions on Design Automation of Electronic Systems 9 2 (April 2004), 212--237. Google ScholarDigital Library
- Natale, M. D. the multitask implementation of multirate Simulink models. In 12th IEEE Real-Time and Embedded Technology and Applications Symposium (RTAS'06) (2006). To appear. Google ScholarDigital Library
- Scaife, N., and Caspi, P. Integrating model-based design and preemptive scheduling in mixed time-and event-triggered systems.In Euromicro conference on Real-Time Systems (ECRTS'04) (2004). Google ScholarDigital Library
- Sha, L., Rajkumar, R., and Lehoczky, J. Priority inheritance protocols: An approach to real-time synchronization. IEEE Trans. Computers (Sept. 1990). Google ScholarDigital Library
- Stankovic, J., Spuri, M., Ramamritham, K., and Buttazzo, G. Deadline Scheduling For Real-Time Systems: EDF and Related Algorithms Kluwer Academic Publishers, 1998. Google ScholarDigital Library
- Tripakis, S., Sofronis, C., Scaife, N., and Caspi, P. 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) (2005), pp.353--360. Google ScholarDigital Library
Index Terms
- A memory-optimal buffering protocol for preservation of synchronous semantics under preemptive scheduling
Recommendations
Semantics-preserving multitask implementation of synchronous programs
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. ...
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