SyncCharts in C: a proposal for light-weight, deterministic concurrency

ABSTRACT

SyncCharts in C (SC) extends C with control flow operators for deterministic, light-weight concurrency and preemption. SC is based on SyncCharts, a synchronous variant of Statecharts with a sound formal basis. SC implements concurrency via a simulation of multi-threading, inspired by reactive processing. This approach permits very fast context switches and allows to express SC operators with regular, sequential C code. Thus a concurrent SC program requires neither a special compiler nor OS support for concurrency.

A reference implementation of SC, based on C macros, is available as open source code. SC can be used in a number of scenarios: 1) as a regular programming language, requiring just a C compiler; 2) as an intermediate target language for synthesizing graphical SyncChart models into executable code, in a traceable manner; 3) as instruction set architecture for programming precision timed (PRET) or reactive architectures, abstracting functionality from physical timing; or 4) as a virtual machine instruction set, with a very dense encoding.

REFERENCES

• 1: J. Ali and J. Tanaka. Converting Statecharts into Java code. In Proceedings of the Fourth World Conference on Integrated Design and Process Technology (IDPT '99), Dallas, Texas, June 2000. Society for Design and Process Science (SDPS).
• 2: C. André. Semantics of SyncCharts. Technical Report ISRN I3S/RR-2003-24-FR, I3S Laboratory, Sophia-Antipolis, France, April 2003.
• 3: C. André. Computing SyncCharts reactions. In SLAP 2003: Synchronous Languages, Applications and Programming, A Satellite Workshop of ECRST 2003, volume 88, pages 3 -- 19, 2004.
• 4: A. W. Appel. Compiling with Continuations. Cambridge University Press, 2007.
• 5: F. Boussinot. Fairthreads: mixing cooperative and preemptive threads in C. Concurrency and Computation: Practice and Experience, 18(5):445--469, Apr. 2006.
• 6: T. Cucinotta, D. Faggioli, and A. Evangelista. Exception-based management of timing constraints violations for soft real-time applications. In Proceedings of the International Workshop on Operating Systems Platforms for Embedded Real-Time Applications (OSPERT'09), Dublin, Ireland, June 2009.
• 7: S. A. Edwards and J. Zeng. Code generation in the Columbia Esterel Compiler. EURASIP Journal on Embedded Systems, Article ID 52651, 31 pages, 2007.
• 8: Frederic Boussinot. Reactive C: An extension of C to program reactive systems. Software Practice and Experience, 21(4):401--428, 1991.
• 9: S. M. G. Berry and J.-P. Rigault. Esterel: Towards a synchronous and semantically sound high-level language for real-time applications. In IEEE Real-Time Systems Symposium, pages 30--40, 1983. IEEE Catalog 83CH1941-4.
• 10: D. Harel. Statecharts: A visual formalism for complex systems. Science of Computer Programming, 8(3):231--274, June 1987.
• 11: G. Kahn and D. B. MacQueen. Coroutines and networks of parallel processes. In IFIP Congress, pages 993--998, 1977.
• 12: L. Lavagno and E. Sentovich. ECL: a specification environment for system-level design. In DAC '99: Proceedings of the 36th ACM/IEEE conference on Design automation, pages 511--516, New York, NY, USA, 1999. ACM Press.
• 13: E. A. Lee. The problem with threads. IEEE Computer, 39(5):33--42, 2006.
• 14: X. Li, M. Boldt, and R. von Hanxleden. Mapping Esterel onto a multi-threaded embedded processor. In Proceedings of the 12th International Conference on Architectural Support for Programming Languages and Operating Systems (ASPLOS'06), San Jose, CA, October 21--25 2006.
• 15: B. Lickly, I. Liu, S. Kim, H. D. Patel, S. A. Edwards, and E. A. Lee. Predictable programming on a precision timed architecture. In Proceedings of Compilers, Architectures, and Synthesis of Embedded Systems (CASES'08), Atlanta, USA, Oct. 2008.
• 16: M. Mendler and M. Pouzet. Uniform and modular composition of data-flow & control-flow in the lazy B-calculus. Presentation at the International Open Workshop on Synchronous Programming (SYNCHRON'08), Aussois, France, Dec. 2008.
• 17: M. Mendler, R. von Hanxleden, and C. Traulsen. WCRT Algebra and Interfaces for Esterel-Style Synchronous Processing. In Proceedings of the Design, Automation and Test in Europe (DATE'09), Nice, France, Apr. 2009.
• 18: D. Potop-Butucaru, S. A. Edwards, and G. Berry. Compiling Esterel. Springer, May 2007.
• 19: S. Prochnow, C. Traulsen, and R. von Hanxleden. Synthesizing Safe State Machines from Esterel. In Proceedings of ACM SIGPLAN/SIGBED Conference on Languages, Compilers, and Tools for Embedded Systems (LCTES'06), Ottawa, Canada, June 2006.
• 20: S. Prochnow and R. von Hanxleden. Statechart development beyond WYSIWYG. In Proceedings of the ACM/IEEE 10th International Conference on Model Driven Engineering Languages and Systems (MoDELS'07), Nashville, TN, USA, Oct. 2007.
• 21: P. S. Roop, S. Andalam, R. von Hanxleden, S. Yuan, and C. Traulsen. Tight WCRT analysis for synchronous C programs. In Proceedings of the International Conference on Compilers, Architecture, and Synthesis for Embedded Systems (CASES'09), Grenoble, France, Oct. 2009.
• 22: P. S. Roop, S. Andalam, R. von Hanxleden, S. Yuan, and C. Traulsen. Tight WCRT analysis of synchronous C programs. Technical Report 0912, Christian-Albrechts-Universität Kiel, Department of Computer Science, May 2009.
• 23: P. S. Roop, Z. Salcic, and M. W. S. Dayaratne. Towards Direct Execution of Esterel Programs on Reactive Processors. In 4th ACM International Conference on Embedded Software (EMSOFT'04), Pisa, Italy, Sept. 2004.
• 24: M. Samek. Practical UML Statecharts in C/C++ Event-Driven Programming for Embedded Systems. Newnes, 2008.
• 25: F. Starke, C. Traulsen, and R. von Hanxleden. Executing Safe State Machines on a reactive processor. Technical Report 0907, Christian-Albrechts-Universität Kiel, Department of Computer Science, Kiel, Germany, Mar. 2009.
• 26: O. Tardieu and S. A. Edwards. Scheduling-independent threads and exceptions in SHIM. In Proceedings of the Proceedings of the International Conference on Embedded Software (EMSOFT'06), Seoul, Korea, Oct. 2006.
• 27: R. von Hanxleden. SyncCharts in C. Technical Report 0910, Christian-Albrechts-Universität Kiel, Department of Computer Science, May 2009. http://rtsys.informatik.uni-kiel.de/ biblio/downloads/papers/report-091%0.pdf.
• 28: R. von Hanxleden, X. Li, P. Roop, Z. Salcic, and L. H. Yoong. Reactive processing for reactive systems. ERCIM News, 66:28--29, Oct. 2006.
• 29: F. Wagner, R. Schmuki, P. Wolstenholme, and T. W. Thomas. Modeling Software with Finite State Machines: A Practical Approach. Auerbach Publications, 2006.
• 30: A. Wasowski. On efficient program synthesis from Statecharts. In Proceedings of the 2003 ACM SIGPLAN Conference on Language, Compilers, and Tools for Embedded Systems (LCTES'03), volume 38, issue 7, June 2003. ACM SIGPLAN Notices.
• 31: S. Yuan, S. Andalam, L. H. Yoong, P. S. Roop, and Z. Salcic. STARPro-a new multithreaded direct execution platform for Esterel. In Proceedings of Model Driven High-Level Programming of Embedded Systems (SLA++P'08), Budapest, Hungary, Apr. 2008.

INDEX TERMS

Primary Classification:
  D. Software
  D.3 PROGRAMMING LANGUAGES
      D.3.3 Language Constructs and Features
          Subjects: Concurrent programming structures

Additional Classification:
  D. Software
  D.3 PROGRAMMING LANGUAGES
      D.3.3 Language Constructs and Features
          Subjects: Coroutines

General Terms:
Design, Languages

Keywords:
SyncCharts, esterel, model-based design, multi-threading, reactive processing, statecharts, synchronous programming