Scheduling Predictable Applications
Scheduling Predictable Applications: An important property of all types of predictable applications is that such an application is schedulable according to the two-level scheme if the size of its server is equal to its required capability and its server is schedulable. In contrast, a nonpredictable application requires a server of a size larger than than its required capability, as we will explain below.
Nonpreemptively Scheduled Applications. Specifically, according to the two-level scheme, each nonpreemptively scheduled application Ti is executed by a constant utilization server whose size ˜ ui is equal to the required capacity si of the application. The server scheduler orders jobs in Ti according to the algorithm used by Ti. Let B denote the maximum execution time of nonpreemptable sections3 of all jobs in all applications in the system and Dmin denote the minimum of relative deadlines of all jobs in these applications. Corollary 7.8 says that all servers are schedulable if the total size of all servers is no greater than 1 − B/Dmin.
To show that every job in a nonpreemptively scheduled real-time application Ti completes in time when scheduled according to the two-level scheme, we consider a time instant at which the OS scheduler replenishes the server budget and sets the server deadline to execute a job in Ti . This time instant is the same as the scheduling decision time at which the job would be scheduled if Ti were executed alone on a slow processor whose speed is si times the speed of the physical processor. The job would complete on the slow processor at the deadline of the server. Since the server is schedulable, it surely will execute for as long as the execution time of the job (hence complete the job) by the server deadline according to the two-level scheme.4
Applications Scheduled according to a Cyclic Schedule. Each application Ti that is scheduled according to a cyclic schedule is also executed by a constant utilization server of size equal to si . The OS replenishes the budget of the server at the beginning of each frame. At each replenishment, the budget is set to si f , where f is the length of the frames, and the server deadline is the beginning of the next frame. The server scheduler schedules the application according to its precomputed cyclic schedule.
Preemptively Scheduled Predictable Applications. As with other predictable applications, the size ˜ ui of the server for a predictable application Ti that is scheduled in a preemptive, priority-driven manner is equal to its required capacity. However, the OS scheduler cannot maintain the server according to the constant utilization/total bandwidth server algorithms. Rather, it replenishes the server budget in the slightly different manner described below.
To motivate the modified replenishment rule, we consider two jobs, J1 and J2. The execution time of each is 0.25. Their feasible intervals are (0.5, 1.5] and (0, 2], respectively. The jobs are scheduled preemptively in a priority-driven manner: J1 has the higher priority and J2 the lower. These jobs would be schedulable if they were to execute by themselves on a slow processor of speed 0.25. Now, suppose that they are executed by a server of size 0.25 according to the two-level scheme on a processor of speed one. Moreover, suppose that the server is maintained according to the constant utilization server or total bandwidth server algorithm: At time 0, the server is given 0.25 unit of budget, and its deadline is set at 1. The server may execute for 0.25 unit of time and complete J2 by time 0.5 when J1 is released. When the server budget is replenished again, the deadline for consuming the budget is 2. J1 may complete as late as time 2 and, hence, may miss its deadline.
Deng, et al. [DeSL] showed that if the server for a preemptive, priority-driven application were maintained according to the constant utilization/total bandwidth server algorithms, we could guarantee the schedulability of the application only if the size of its server is 1, even when the required capacity of the application is much smaller than 1. This means that it cannot share the processor with any other application! A look at the above example tells us why. From time 0 to 0.5, the server is given (and is allowed to consume) 0.125 unit of budget more than what is required to complete the portion of J2 that could be completed before time 0.5 if J2 were executed on the slower processor. This 0.125 unit of budget should be saved to execute the higher-priority job J1 after 0.5. By giving the server a budget equal to the execution time or the remaining execution time of the job at the head of the server’s ready queue, the OS scheduler may introduce a form of priority inversion: A lower-priority job is able to make more progress according to the two-level schedule at the expense of some higher-priority job. We say that this priority inversion is due to the overreplenishment of the server budget.
A way to prevent this kind of priority inversion works as follows. At each replenishment time of the server for a preemptively scheduled application Ti, let t be the current server deadline or the current time, whichever is later. Let t be the next release-time of Ti , that is, t is the earliest release time after t of all jobs in Ti (in general, the occurrence time of the earliest possible context switch). t is computed by the server scheduler; this is possible when the release times of all jobs in Ti are known. Knowing that a preemption within Ti may occur at t , the OS scheduler sets the server budget to min(er, (t − t) ˜ ui ), where er is the execution time of the remaining portion of the job at the head of the server queue, and sets the deadline of the server at min(t er / ˜ ui , t ' ). Therefore, if Ti were to execute alone on a slower processor of speed ˜ ui , it would not have any context switch between any replenishment time and the corresponding server deadline. This condition, together with conditions that the server size is equal to the required capacity and the total size of all servers is no greater than 1 − B/Dmin, gives a sufficient condition for Ti to be schedulable when executed according to the two-level scheme.