Keywords: real-time systems, soft-real time scheduling algorithm, uncertain systems, task overrun, overload handling, rate-based scheduling, randomization.

Recently real-time applications have evolved from closed, hard real-time systems to open, soft real-time environments featuring variable workload and resource requirements. Many applications are unpredictable, as their workloads are highly variable and very difficult to model. Due to this unpredictable behaviour, it is not possible to design systems in such a way to prevent all transient overloads which can occur (here we recall that an overload occurs when the overall system utilization exceeds 1), so in this context scheduling algorithms should be provided with overload handling capabilities. On the other hand, as tasks are subject to soft real-time constraints, scheduling algorithms should aim to meet as many deadlines as possible and to achieve high system utilizations, while avoiding pessimistic assumptions on load patterns. To address these requirements, new scheduling approaches have to be developed.

In this paper we present the Randomized Earliest-Completion-Time GPS (R-EGPS) algorithm, a rate-based scheduling algorithm with embedded overrun handling capabilities suitable for uncertain and overload-prone soft real-time systems. R-EGPS exploits randomization to bound the effect of overrunning jobs on the other jobs. R-EGPS is inspired by the Earliest-Completion-Time GPS (EGPS) algorithm proposed in [1]. The EGPS algorithm, derived from the idea of Generalized Processor Sharing (GPS) presented in [2], is a work-conserving, preemptive scheduling algorithm based on the concept of the reservation ratio of processor computation time. The EGPS algorithm assumes that worst case execution times are known, while in the scenario addressed in this paper such a knowledge is not available. The R-EGPS algorithm therefore assumes that each task Ti is assigned a reservation ratio, and thus a given CPU utilization, without any knowledge of the task's behaviour. Moreover, pessimistic assumptions are avoided in order to exploit system resources as much as possible.

The choice of avoiding pessimism in our execution scenario entails the problem of dealing with overrunning jobs. We define an overrunning job as one requiring a CPU utilization greater than its reserved one. Here a job's overrun does not necessarily imply a misbehaviour. As said before, tasks worst case utilizations are unknown and each task is assigned a reserved CPU utilization in such a way to make the overall task set exploit the CPU as much as possible. So, if a job requires more than the reserved CPU utilization, this does not imply that this job has to be necessarily penalized. However, as an overrunning job may affect jobs from other tasks which will be executed after it, some mechanism to bound overruns is needed to avoid a number of deadline misses.

To achieve this, a scheduler could let an overrunning job exploit the CPU time unused by underrunning jobs (i.e., those jobs which actually utilize less than the utilization reserved to the corresponding tasks) and thus complete its execution. Besides, the scheduler could decide to continue the execution of the overrunning job even if there is no extra CPU time due to past underruns, with the expectation that some jobs in the future will underrun. However, as the scheduler does not have any a priori knowledge about jobs behaviour, it cannot predict whether in the future some of them will overrun or underrun. To overcome the problems due to this uncertainty, the R-EGPS algorithm implements a simple mechanism, based on randomization, which enables the scheduler to decide whether and how much extra CPU time should be given to an overrunning job.

In the paper we evaluate the sensitivity of R-EGPS performance to the degree of uncertainty about task set characteristics and system utilization. The effect of dropping in both partially and totally uncertain environments is analyzed. In the first case, we assume that some knowledge of task set characteristics is given (e.g. execution time distribution and average), while in the second case such a knowledge is not available. In both environments, we assess the sensitivity of the performance of R-EGPS to the intensity of dropping, which depends on some parameters which are explained in the paper.

Simulation results show the effectiveness of the approach when applied to both partially and totally uncertain environments. Through a suitable choice of dropping intensity, depending on the system utilization and level of uncertainty, R-EGPS proves to be able to 'bound' the effect of overrunning jobs on the other ones, while avoiding blind penalization of jobs requiring longer execution times than the reserved ones. The results obtained provide the designer with useful guidelines while applying R-EGPS in uncertain environments.

1

T.W. Kuo, W.R. Yang, and K.J. Lin. "EGPS: A Class of Real-Time Scheduling Algorithms Based on Processor Sharing" in Proceedings of the 10th Euromicro Workshop on Real-Time Systems, pp. 27-34, Jun. 1998.

2

A.K. Parekh and R.G. Gallager. "A Generalized Processor Sharing Approach to Flow Control in Integrated Services Networks: The Single-Node Case" IEEE/ACM Transactions on Networking, Vol. 1, No. 3, pp 344-357, Jun. 1993. doi:10.1109/90.234856

purchase the full-text of this paper (price £20)

go to the previous paper
go to the next paper
return to the table of contents
return to the book description
purchase this book (price £95 +P&P)