SKEDSOFT

(a) Operation of the OS scheduler

Initialization
• Create a total bandwidth server S0 with size u0 < 1 for nonreal-time applications and a passive server for each service provider in the system.
• Set Ut to the total size of S0 and all passive servers.
Acceptance test and admission of a new real-time application Tk :
• Upon request from the application, do the acceptance test as described in Figure 12–11(c).
• If Tk passes the acceptance test, create server Sk of size uk , following the rules described in Figure 12–11(c).
Maintenance of each server Sk : Replenish the budget and set the deadline of server Sk according to Figure 12–11(b).
Interaction with server scheduler of each server Sk :
• When a thread in the application Tk becomes ready, invoke the server scheduler of Sk to insert the thread in Sk ’s ready queue.
• If Tk uses a preemptive scheduling algorithm, before replenishing the budget of Sk , invoke the server scheduler of Sk to update the next event time tk of Tk .
• When a thread in Tk enters its nonpreemptable section, mark the server Sk nonpreemptable until the thread exits the nonpreemptable section, and mark the server preemptable when the nonpreemptable section exceeds the declared maximum length.
• When a thread in Tk requests a global resource, grant the thread the resource and mark the server Sk nonpreemptable until the thread releases the global resource.
Scheduling of all servers: Schedule all ready servers on the EDF basis, except when a server is marked nonpreemptable; when a server is nonpreemptable, it has the highest priority among all servers.

Termination of a real-time application Tk :
• Destroy server Sk .
• Decrease Ut by uk .

the length of the time slices used by the time-sharing scheduler. The OS scheduler sets the budget of S0 to x when the first nonreal-time thread is ready to execute (say at time 0) and sets the deadline of the server at x/ ˜ u0. Hereafter, at each time t when the budget of S0 is exhausted and there are threads ready to be executed by S0, the OS scheduler sets the budget to x and the corresponding deadline to either t x/ ˜ u0 or the current deadline of the server plus x/ ˜ u0 whichever is later. Moreover, whenever a busy interval ends, the OS server gives the server x units of budget and sets the server deadline at the current time plus x/ ˜ u0.

As long as the server S0 is schedulable (meaning that its budget is always consumed before the current deadline), the open system offers nonreal-time applications a virtual slower processor with speed ˜ u0. As you will see later, the acceptance test of the open system is such processor utilization ˜ u0 committed to the server. Other than this, we will not be concerned with nonreal-time applications any further.

Passive Server. The server created by the OS scheduler for each service provider is a passive server. A passive server is a sporadic server. Its execution budget comes from two sources. The first is the server’s processor time allocation; the server has a very small size. (This is analogous to processor reservation of a system service provider.) The OS scheduler treats the passive server as a total bandwidth server of its size and replenishes its budget according to the rules described in Section 7.4.3. The only “aperiodic task” executed by the server using this budget is the daemon thread of the service provider. The daemon thread
is created during initialization (or when a service provider is admitted into the system). It is suspended immediately after it is created and wakes to run whenever the service provider receives a request for service. When the daemon thread runs, it creates a work thread to service the request and puts itself back to the suspended state again.

In addition, a passive server also gets execution budget from client applications of the SSP executed by the server. When a client application requests a service, it passes to the service provider its own budget and the associated deadline for consuming the budget.22 The work thread created by the daemon to service the client’s request executes with this budget and has this deadline. (Conceptually, we can think of the budget/deadline passed to the passive server as a CPU reservation. This reservation is not replenished periodically, however; rather it is under the control of the server scheduler of the client application.)We will return to provide more details on how the scheduler of a passive server works.

Admission, Termination, and Scheduler Interactions. To request admission, that is, to execute in the real-time mode, a new real-time application Tk provides in its request to the OS scheduler the information needed by the scheduler to do an acceptance test. If the application passes the test, the OS scheduler creates a server Sk of size ˜ uk to execute the new application. (The information the OS scheduler needs to do an acceptance test and the rules used by the scheduler to do the test and select the server type and size are described below.) Whenever a real-time application terminates, the OS scheduler destroys its server.

When a thread in a real-time application Tk becomes ready, the OS scheduler invokes the server scheduler of the server Sk to insert the thread into the server’s ready queue. The server scheduler orders the ready threads according to the scheduling algorithm of the real-time application Tk .