{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,1,1]],"date-time":"2026-01-01T10:06:24Z","timestamp":1767261984854,"version":"3.41.0"},"reference-count":23,"publisher":"Association for Computing Machinery (ACM)","issue":"2","license":[{"start":{"date-parts":[[2008,1,29]],"date-time":"2008-01-29T00:00:00Z","timestamp":1201564800000},"content-version":"vor","delay-in-days":0,"URL":"https:\/\/www.acm.org\/publications\/policies\/copyright_policy#Background"}],"funder":[{"DOI":"10.13039\/501100004966","name":"Fifth Framework Programme","doi-asserted-by":"publisher","award":["IST-2001-38117"],"award-info":[{"award-number":["IST-2001-38117"]}],"id":[{"id":"10.13039\/501100004966","id-type":"DOI","asserted-by":"publisher"}]},{"DOI":"10.13039\/501100004965","name":"Sixth Framework Programme","doi-asserted-by":"publisher","award":["IST-004527"],"award-info":[{"award-number":["IST-004527"]}],"id":[{"id":"10.13039\/501100004965","id-type":"DOI","asserted-by":"publisher"}]}],"content-domain":{"domain":["dl.acm.org"],"crossmark-restriction":true},"short-container-title":["ACM Trans. Embed. Comput. Syst."],"published-print":{"date-parts":[[2008,2]]},"abstract":"<jats:p>\n            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            <jats:italic>N<\/jats:italic>\n            + 2 buffers for each writer, where\n            <jats:italic>N<\/jats:italic>\n            is the number of readers for this writer.\n          <\/jats:p>","DOI":"10.1145\/1331331.1331339","type":"journal-article","created":{"date-parts":[[2008,2,28]],"date-time":"2008-02-28T14:02:33Z","timestamp":1204207353000},"page":"1-40","update-policy":"https:\/\/doi.org\/10.1145\/crossmark-policy","source":"Crossref","is-referenced-by-count":36,"title":["Semantics-preserving multitask implementation of synchronous programs"],"prefix":"10.1145","volume":"7","author":[{"given":"Paul","family":"Caspi","sequence":"first","affiliation":[{"name":"Verimag Laboratory Gi\u00e8res, France"}]},{"given":"Norman","family":"Scaife","sequence":"additional","affiliation":[{"name":"Verimag Laboratory, Gi\u00e8res, France"}]},{"given":"Christos","family":"Sofronis","sequence":"additional","affiliation":[{"name":"Verimag Laboratory"}]},{"given":"Stavros","family":"Tripakis","sequence":"additional","affiliation":[{"name":"Verimag and Cadence Research Laboratories, Berkeley, California"}]}],"member":"320","published-online":{"date-parts":[[2008,1,29]]},"reference":[{"key":"e_1_2_1_1_1","doi-asserted-by":"publisher","DOI":"10.1145\/1086228.1086263"},{"key":"e_1_2_1_2_1","doi-asserted-by":"publisher","DOI":"10.1109\/5.97297"},{"key":"e_1_2_1_3_1","volume-title":"LNCS","volume":"2491","author":"Benveniste A.","unstructured":"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. 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."},{"volume-title":"CAV'94","author":"Burch J.","key":"e_1_2_1_4_1","unstructured":"Burch , J. and Dill , D . 1994. Automatic verification of pipelined microprocessor control . In CAV'94 . Burch, J. and Dill, D. 1994. Automatic verification of pipelined microprocessor control. In CAV'94."},{"key":"e_1_2_1_5_1","doi-asserted-by":"publisher","DOI":"10.1145\/41625.41641"},{"key":"e_1_2_1_6_1","doi-asserted-by":"publisher","DOI":"10.1145\/780732.780754"},{"key":"e_1_2_1_7_1","volume-title":"Tech. Rep. YCS-286, Department of Computer Science","author":"Chen J.","year":"1997","unstructured":"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. 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."},{"key":"e_1_2_1_8_1","unstructured":"Clarke E. Grumberg O. and Peled D. 2000. Model Checking. MIT Press Cambridge MA.  Clarke E. Grumberg O. and Peled D. 2000. Model Checking. MIT Press Cambridge MA."},{"key":"e_1_2_1_9_1","first-page":"129","article-title":"A generic approach to schedulability analysis of real-time tasks","volume":"11","author":"Fersman E.","year":"2004","unstructured":"Fersman , E. and Yi , W. 2004 . A generic approach to schedulability analysis of real-time tasks . Nordic J. of Computing 11 , 2, 129 -- 147 . Fersman, E. and Yi, W. 2004. A generic approach to schedulability analysis of real-time tasks. Nordic J. of Computing 11, 2, 129--147.","journal-title":"Nordic J. of Computing"},{"volume-title":"Synchronous Programming of Reactive Systems","author":"Halbwachs N.","key":"e_1_2_1_10_1","unstructured":"Halbwachs , N. 1992. Synchronous Programming of Reactive Systems . Kluwer , Academic Publ ., Norwell, MA. Halbwachs, N. 1992. Synchronous Programming of Reactive Systems. Kluwer, Academic Publ., Norwell, MA."},{"key":"e_1_2_1_11_1","doi-asserted-by":"crossref","unstructured":"Halbwachs N. 1998. Synchronous programming of reactive systems---a tutorial and commented bibliography. In Computer Aided Verification. 1--16.   Halbwachs N. 1998. Synchronous programming of reactive systems---a tutorial and commented bibliography. In Computer Aided Verification. 1--16.","DOI":"10.1007\/BFb0028726"},{"key":"e_1_2_1_12_1","doi-asserted-by":"crossref","unstructured":"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.   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.","DOI":"10.1007\/978-1-4615-2796-1"},{"volume-title":"USENIX'02","author":"Huang H.","key":"e_1_2_1_13_1","unstructured":"Huang , H. , Pillai , P. , and Shin , K . 2002. Improving wait-free algorithms for interprocess communication in embedded real-time systems . In USENIX'02 . Huang, H., Pillai, P., and Shin, K. 2002. Improving wait-free algorithms for interprocess communication in embedded real-time systems. In USENIX'02."},{"key":"e_1_2_1_14_1","doi-asserted-by":"publisher","DOI":"10.1145\/321738.321743"},{"volume-title":"IEEE American Control Conference.","author":"Puri A.","key":"e_1_2_1_15_1","unstructured":"Puri , A. and Varaiya , P . 1995. Driving safely in smart cars . In IEEE American Control Conference. Puri, A. and Varaiya, P. 1995. Driving safely in smart cars. In IEEE American Control Conference."},{"key":"e_1_2_1_16_1","volume-title":"5th Intl. Sym. on Programming. LNCS","volume":"137","author":"Queille J.","unstructured":"Queille , J. and Sifakis , J . 1981. Specification and verification of concurrent systems in CESAR . In 5th Intl. Sym. on Programming. LNCS , vol. 137 . Queille, J. and Sifakis, J. 1981. Specification and verification of concurrent systems in CESAR. In 5th Intl. Sym. on Programming. LNCS, vol. 137."},{"key":"e_1_2_1_17_1","doi-asserted-by":"publisher","DOI":"10.1145\/125083.123062"},{"key":"e_1_2_1_18_1","doi-asserted-by":"publisher","DOI":"10.5555\/1009383.1009830"},{"key":"e_1_2_1_19_1","doi-asserted-by":"publisher","DOI":"10.1109\/12.57058"},{"key":"e_1_2_1_20_1","doi-asserted-by":"publisher","DOI":"10.1145\/1176887.1176892"},{"key":"e_1_2_1_21_1","doi-asserted-by":"crossref","unstructured":"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.   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.","DOI":"10.1007\/978-1-4615-5535-3"},{"volume-title":"Embedded Software (EMSOFT'02). LNCS","author":"Tripakis S.","key":"e_1_2_1_22_1","unstructured":"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 . 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."},{"key":"e_1_2_1_23_1","doi-asserted-by":"publisher","DOI":"10.1145\/1086228.1086292"}],"container-title":["ACM Transactions on Embedded Computing Systems"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/dl.acm.org\/doi\/10.1145\/1331331.1331339","content-type":"unspecified","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/dl.acm.org\/doi\/pdf\/10.1145\/1331331.1331339","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2025,6,18]],"date-time":"2025-06-18T20:22:27Z","timestamp":1750278147000},"score":1,"resource":{"primary":{"URL":"https:\/\/dl.acm.org\/doi\/10.1145\/1331331.1331339"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2008,1,29]]},"references-count":23,"journal-issue":{"issue":"2","published-print":{"date-parts":[[2008,2]]}},"alternative-id":["10.1145\/1331331.1331339"],"URL":"https:\/\/doi.org\/10.1145\/1331331.1331339","relation":{},"ISSN":["1539-9087","1558-3465"],"issn-type":[{"type":"print","value":"1539-9087"},{"type":"electronic","value":"1558-3465"}],"subject":[],"published":{"date-parts":[[2008,1,29]]},"assertion":[{"value":"2007-01-01","order":0,"name":"received","label":"Received","group":{"name":"publication_history","label":"Publication History"}},{"value":"2007-07-01","order":1,"name":"accepted","label":"Accepted","group":{"name":"publication_history","label":"Publication History"}},{"value":"2008-01-29","order":2,"name":"published","label":"Published","group":{"name":"publication_history","label":"Publication History"}}]}}