SKEDSOFT

Scheduling Nonpredictable Applications
In general, the actual release-times of some jobs in a nonpredictable application Ti may be unknown. It is impossible for its server scheduler to determine the next release-time t of Ti precisely. Therefore, some priority inversion due to overreplenishment of the server budget is unavoidable. Fortunately, the bad effect on the schedulability of Ti can be compensated by making the size ˜ ui of the server larger than the required capacity si of the application.

Budget Replenishment. Let t'_e denote an estimate of the next release time t  of Ti . The server scheduler computes this estimate at each replenishment time t of the server as follows. If the earliest possible release time of every job in Ti is known, the server scheduler uses as t'e the minimum of the future earliest release times plus an error factor ε > 0. When the earliest release times of some jobs in Ti are unknown, t'e is equal to the t ε, where t is the current time. After obtaining the value t'e from the server scheduler, the OS scheduler sets the server budget to min(er, (t'e − t) ˜ ui ) and the server deadline at min(t er / ˜ ui , t'e).

ε is a design parameter. It is called the quantum size of the two-level scheduler. In the absence of any knowledge on the release-times of jobs in an application, the OS scheduler replenishes the budget of its server every ε units of time. Hence, the smaller the quantum size, the more frequent the server replenishments, and the higher the server maintenance overhead. However, the size of the server required to execute the application grows with the quantum size, as it will become evident below.

Required Server Size. It is easy to see that if Ti were to execute alone on a slower processor, it would not have any context switch from the current replenishment time to ε time units before the new server deadline. The extra budget that the OS schedulermay inadvertently give to the server is no greater than ε ˜ ui . Hence, the length of priority inversion due to the overreplenishment of the server budget is at most ε ˜ ui . We can treat this time as the blocking time of any higher-priority job that may be released between the current replenishment time and server deadline.

Let D_i,min be the minimum relative deadline of all jobs in Ti . Section 6.8 tells us that if the size of the server for Ti satisfies the inequality si ε ˜ ui /D_i,min ≤ ˜ui , any higher-priority job that may suffer this amount of blocking can still complete in time. Rewriting this inequality and keeping the equality sign, we get

In conclusion, a nonpredictable application Ti with required capacity si and minimum relative deadline D_i,min is schedulable according to the two-level scheme if the size of its server is given by the expression above and the total size of all servers in the system is no greater than 1 − B/D_min.