Server Maintenance: The OS scheduler maintains (i.e., replenishes its budget and sets its deadline) the server Sk for each real-time application Tk with the help of the scheduler of Sk . Figure 12–11(b) summarizes the rules the OS scheduler uses. In the figure, ˜ u denotes the size of the server being maintained. For simplicity, we take as the time origin the time instant immediately after the server is created; this is the instant when the application executed by the server begins to execute in real-time mode.
(b) Server maintenance rules
Inputs: Server size= ˜u, scheduling quantum= q, start time of the application= 0.
• If the application is cyclically scheduled with frame size f ,
– server type: Constant utilization
– replenishment rule: At time 0, f , 2 f , . . ., set budget to ˜u f and deadline to f , 2 f , 3 f , . . . , respectively.
• If the application is nonpreemptively scheduled:
– server type: Constant utilization.
– replenishment rule: The constant utilization server algorithm.
• If the application is unpredictable,
– server type: Total bandwidth server-like.
– replenishment rule:
∗ replenishment time t:
(1) when the ready queue is empty and a thread is released, or
(2) when the ready queue is nonempty,
(i) t is the current server deadline d, or
(ii) the budget is exhausted at t and the next event time is not the release time of a thread with priority higher than the thread at the head of the server ready queue.
∗ budget replenished: ˜ u(tn q − max(t, d)), where tn is a lower bound to the next event time and q is the scheduling quantum of the open system.
∗ server deadline: tn q
• If the application is preemptively scheduled but predictable,
– server type: Total bandwidth server
– replenishment rule: Same as the rule for unpredictable applications except q is equal to 0 and tn is the next event time.
Predictable Applications. You recall that there are three types of predictable applications: cyclically scheduled applications, nonpreemptively scheduled applications, and priority-driven, preemptively scheduled applications that have known next event times. The server used to execute a cyclically scheduled application is a constant utilization server. For the purpose of server maintenance, the workload presented to the server appears to be a single thread. The thread is ready for execution at the beginning of each frame (i.e., at times 0, f , 2 f , and so on). The execution time of this thread is ˜u f . Hence, the OS scheduler replenishes
the server budget at the beginning of the frames. Each time, the OS scheduler gives the server ˜u f units of budget and sets the deadline of the server accordingly. When the application becomes idle, the OS reclaims the remaining budget. (This emulates the case where the virtual slow processor idles during parts of some frames.)
Similarly, each nonpreemptively scheduled real-time application is executed by a constant utilization server. The OS treats the application as a single aperiodic task and replenishes the budget of the Server. If the server is schedulable, it emulates a slow processor of speed ˜ u in the following sense for both types of applications. If we compare the schedule of the application in the open system with its schedule on a slow processor of speed ˜ u, (1) scheduling decisions are made at the same time and (2) every thread completes at the same time or sooner in the open system.
Each preemptively scheduled application is executed by a server that is similar to a total bandwidth server.23 The rules for maintaining the server of a predictable preemptive application are motived by the example on priority inversion due to budget over replenishment that was described in Section 7.9.2. Whenever the OS scheduler gets ready to replenish the server budget, say at time t , it queries the server scheduler for the next event time t. It gives the server ˜ u(t − t) units of budget; the new deadline of the server is t . This way, if a new thread with a higher priority is released at the next event time t, the OS scheduler will be able to give a new chunk of budget to the server for the execution of the new thread. Unpredictable Applications. When periodic tasks in a preemptively scheduled application have release-time jitters or sporadic tasks, it is impossible for the server scheduler to compute an accurate estimate of the next event time. In the extreme when nothing is known about the release times of some threads, the OS scheduler simply maintains the server in the same way as the server S0 for nonreal-time applications. In other words, it replenishes the server budget periodically, q units of time apart, giving the server ˜ uq units of budget each time. We call this design parameter of the open system the scheduling quantum.
When it is possible for the server scheduler to provide the OS scheduler with a lower bound ˆt to the next event time, the OS scheduler sets the server deadline at ˆt q and sets the server budget to ˜ u(ˆt q − t) where t is the current time. Since the actual next event time t (i.e., the next context switch) is never more than q time units earlier than the current server deadline, should a higher-priority thread be released at t , it is delayed by at most q units of time. In other words, the duration of a priority inversion due to overreplenishment of server budget is never more than q units of time.
