Introducing Time Driven Programming using CSP/occam and WCET Estimates

• Main Author: Korsgaard, Martin
• Format: Dissertation
• Language: English
• Subjects: ntnudaim; Reguleringsteknikk; SIE3 teknisk kybernetikk

This thesis describes an experimental programming language called TIME/occam. TIME/occam, like occam, is based on Communicating Sequential Processes (CSP), a branch of process algebra that allows computer programs to be modelled and verified mathematically and mechanically. TIME/occam uses synchronous channel communication as the only legal communication between parallel threads, and prohibits shared variables. Simple statements allow programs to specify parallelism directly. The main innovation in TIME/occam is the TIME statement, which allows the deadline and timing requirements of a task to be specified directly in the language. The TIME statement takes a block and a deadline, and tells the scheduler that the block must be completed within the deadline. It also states that the statement following the TIME block is not allowed to start until the timer expires. This can be used with a loop to create periodic tasks. Statements that have no timing requirements will never be executed. Because channel communication is synchronous, channels allow timing requirements to pass on from one task to another dependent task. The use of channels and timing requirements allow execution of a program to be planned some time in advance. It is assumed that execution time estimates can be found on line, although no viable solution for this exists at this time. Planning execution opens up new possibilities for dealing with missed deadlines. A compiler and scheduler have been implemented for the language. The scheduler is not complete; in particular it lacks the re-planning and execution algorithm. The thesis also contains an introduction to real-time and concurrent programming, and describes some of the difficulties that arise from pre-emptive scheduling of dependent threads. There is also a discussion on worst-case execution time analysis and related hardware issues. An example implementation of dining philosophers is presented, and it is explained how such a program is scheduled and executed in TIME/occam. Finally, the limitations of such a concept are discussed. In particular, there is a question whether or not a very heavy scheduler like the TIME/occam scheduler can be used in practice.