Introduction. Scheduling Iheory has a rich and long hislOry. In add ilion. process algebras have been S1udied as a formal Iheory of syslem design and verificalion since Ihe early 19805. However, these two separate worlds have not been connected until recent years and Ihe conneclion is nol yel complele. In olher words, using Ihe models and algorithms of scheduling Iheory in a process algebraic design is S1ill involved wilh many theoretical and praclical complicalions. In this chapter. building upon previous attempts in Ihis direction, we propose a process algebra. called PARS for Process Algebra with Resources and Schedulers, for the design of scheduled realtime systems. Previous attempts to incorporate scheduling algorithms in process algebra either did not have an explicit notion of schedulers [5 , 15 ,16) (thus, coding the scheduling policy in the process specification) or scheduling is treated for restricled cases thai only support single-processor scheduling [6,12). Our approach to modeling scheduled sYSIems is depicled in Figure 10. 1. In this approach, process specificalion (including aspeclS such as causal relalions of actions, Iheir liming and resource requiremenlS) is separated from Ihe specificalion of schedulers. Then one can apply schedulers to processes to oblain scheduled systems and further compose scheduled systems together. A distinguishing feature of our process algebra is the possibility of specifying schedulers as process terms (similar to resource-consuming processes). Another advantage of the proposed approach is the separation between process specification and scheduler specification that provides a separation of concerns. allows for specifying generic scheduling strategies and makes it possible to apply schedulers to systems at different levels of abstraction. Common to most process algebraic frameworks for resources, the proposed framework provides the possibility of extending standard schedulability analysis to the formal verification process.
|Title of host publication||Process Algebra for Parallel and Distributed Processing|
|Editors||M. Alexander, W. Gardner|
|Publisher||Chapman & Hall|
|Publication status||Published - 2008|
|Name||CRC Computational Science Series|
Mousavi, M. R., Reniers, M. A., Basten, T., & Chaudron, M. R. V. (2008). PARS : a process algebraic approach to resources and schedulers. In M. Alexander, & W. Gardner (Eds.), Process Algebra for Parallel and Distributed Processing (pp. 331-358). (CRC Computational Science Series; Vol. 2). Chapman & Hall.