The Computation Time Process Model

Abstract

In traditional real-time multiprocessor schedulability analysis it is required that all tasks are entirely serial. This implies that if a task is written in a parallel language such as occam, all parallelism in the task must be suppressed to enable schedulability analysis. Part of the reason for this restriction is the difficulty in analysing execution times of programs with a complex parallel structure. In this paper we introduce an abstract model for reasoning about the temporal properties of such programs. Within this model, we define what it means for a process to be easier to schedule than another, and the notion of upper bounds on execution times. Counterintuitive temporal behaviour is demonstrated to be inherent in all systems where processes are allowed an arbitrary parallel structure. For example, there exist processes that are guaranteed to complete on some schedule, that may not complete if executing less than the expected amount of computation. Not all processes exhibit such counterintuitive behaviour, and we identify a subset of processes that are well-behaved in this respect. The results from this paper is a necessary prerequisite for a complete schedulability analysis of systems with an arbitrary parallel structure.