A Two Level Scheme For Integrated Scheduling

A TWO-LEVEL SCHEME FOR INTEGRATED SCHEDULING
This section describes a two-level scheduling scheme [DeLS] that provides timing isolation to individual applications executed on one processor. Each application contains an arbitrary number and types of tasks. By design, the two-level scheme allows different applications to use different scheduling algorithms (e.g., some may be scheduled in a clock-driven manner while the others in a priority-driven manner). Hence, each application can be scheduled in a way best for the application. More importantly, the schedulability and real-time performance of each application can be determined independently of other applications executed on the same processor. By emulating an infinitesmally fine-grain time slicing scheme, the two-level scheme creates a slower virtual processor for each applications in the system.

Overview and Terminology
According to the two-level scheme, each application is executed by a server. The scheduler at the lower level is called the OS scheduler. It replenishes the budget and sets the deadline of each server in the manners described below and schedules the ready servers on the EDF basis. At the higher level, each server has a server scheduler; this scheduler schedules the jobs in the application executed by the server according to the algorithm chosen for the application.

Required Capability. In the description below, we use Ti for i = 1, 2, . . . , n to denote n real-time applications on a processor; each of these applications is executed by a server. To determine the schedulability and performance of each application Ti , we examine the tasks in it as if the application executes alone on a slower processor whose speed is a fraction s of the speed of the physical processor. In other words, we multiple the execution time of every job in the application by a factor 1/s > 1 and use the product in place of the execution time in the schedulability test on the application. The minimum fraction of speed at which the application is schedulable is called its required capacity si . The required capacity of every application must be less than 1.

For example, the required capacity of an application that contains two periodic tasks (2, 0.5) and (5, 1) is 0.5 if it is scheduled rate-monotonically. The reason is that we can multiple the execution time of each task by 2 and the resultant tasks (2, 1.0) and (5, 2) are schedulable, but if the multiplication factor were bigger, the resultant tasks would not be schedulable. If these tasks are scheduled on the EDF basis, its required capacity is 0.45. The system may also have one or more nonreal-time applications. All nonreal-time applications are executed by a total bandwidth or WFQ server of size 0 < ˜ u0 < 1. The jobs in these applications are scheduled by the server scheduler in a time-shared manner; so the budget of the server is replenished periodically. In essence, the two-level scheduler creates for all the nonreal-time applications a virtual time-shared processor of speed ˜ u0.

Predictable versus Nonpredictable Applications. As we will see shortly, in order to correctly maintain the server of an application that is scheduled according to a preemptive priority-driven algorithm, the OS scheduler needs an estimate of the occurrence time of every event of the application that may trigger a context switch within the application. Such events include the releases and completions of jobs and their requests and releases of resources. At any time t , the next event of application Ti is the one that would have the earliest occurrence time after t among all events of Ti if the application were to execute alone on a slow processor with speed si equal to its required capacity.We call an application that is scheduled according to a preemptive, priority-driven algorithm and contains aperiodic and sporadic tasks and/or periodic tasks with release-time jitters an unpredictable application. The reason for this name is that the OS scheduler needs an estimate of its next event (occurrence) time at each replenishment time of its server, but its server scheduler cannot compute an accurate estimate.

All other types of applications are predictable. An application that contains only periodic tasks with fixed release times and known resource request times is predictable because its server scheduler can compute accurately the occurrence times of its future events. (In fact, for such an application, the event occurrence times can be computed a priori before the application requests to execute in the real-time mode and stored for use at run time.) All time-driven applications are predictable because scheduling decisions are triggered by clock interrupts which occur at known time instants. As we will see shortly, the OS scheduler does not need to know the event occurrence times of a nonpreemptively scheduled application. We say that nonpreemptively scheduled applications are predictable.