A Randomized Rate-Based Scheduling Algorithm for Uncertain Environments

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). The EGPS algorithm, derived from the idea of Generalized Processor Sharing (GPS) 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.