Execution time analysis of communicating tasks in distributed systems

Abstract

Task-execution times are one of the most important parameters in scheduling tasks. Most scheduling algorithms are based on the assumption that either worst-case task-execution times are known to the scheduler or no information on execution times is available at all. While scheduling tasks based on worst-case execution limes can guarantee to meet their timing requirements, it may lead to severe under-utilization of CPUs because worst-case execution times could be one or two orders of magnitude larger than the corresponding actual values. Scheduling tasks based on the execution time distribution (instead of worst-case execution times) is known to improve system utilization significantly. In this paper, we propose a model to predict task execution times in a distributed system. The model considers several factors which affect the execution time oi each task. These factors are classified into two groups: intrinsic and extrinsic. The intrinsic factors control the flow within a task, while the extrinsic factors include communication and synchronization delays between tasks. By simplifying the extrinsic factors. we represent a distributed system with a simple queuing model. The proposed queuing model consists of two stations. one for computation and the other for communication and synchronization. information on system utilization can be obtained by converting this queuing model to a Markov chain. The execution time of a task is then derived from the information on system utilization in the form of average and distribution. The model is extended to describe the effects of multiple tasks assigned to a single processing node. The utility of the model is demonstrated with an example.