Scheduling Overhead And Processor Utilization
Scheduling Overhead and Processor Utilization
Deng et al. [DLZS] simulated systems with different workloads for the purpose of determining the scheduling overhead of the two-level priority-driven scheme. Specifically, they compare the numbers of context switches and queue insertion/deletion operations incurred in systems using the two-level scheme with the corresponding numbers in a closed system using a onelevel priority-driven scheduler.
Their simulation results show that scheduling overhead of the open system depends critically on the scheduling quantum. This design parameter can be set to 0 when all realtime applications are predictable. In this case, the scheduling overhead of the open system is essentially the same as that of a closed system. (The number of context switches are the same. There are more queues to maintain but all the queues are shorter.) When some realtime applications are nonpredictable, we must choose a nonzero scheduling quantum. The scheduling overhead of the open system is significantly higher than that of the closed system only when the scheduling quantum is small.
We note that the smaller the minimum relative deadline, the smaller the scheduling quantum must be. Even when the minimum relative deadlines of all applications are large, we may still want to use a small scheduling quantum. The reason is that the size of the server for each nonpredictable application required to meet the schedulability condition 1 grows with the scheduling quantum. A larger server than the required capacity of the applications means a lower processor utilization for real-time applications. In short, in order to accommodate nonpredictable applications with large release-times jitters and small relative deadlines, some processor bandwidth (on the order of 30 percent) is not available for real-time applications. This bandwidth is either wasted as scheduling overhead, when the scheduling quantum is small, or set aside for the sake of compensating blocking time in nonpredictable applications, when the scheduling quantum is large. The latter is better because the extra processor bandwidth over the required capacity of the real-time application will be used by server S0 for nonreal-time applications.
Service Provider Structure and Real-Time API Functions
In the open system, services such as network and file access are implemented as specialpurpose user-level server applications. As stated earlier, the OS scheduler creates a passive server to execute each service provider. Each SSP has a daemon thread, which is created when the service provider is admitted into the system. Its responsibilities are (1) to create work threads in the address space of the service provider in response to requests for service from clients, and (2) to process incoming data to identify the receiving thread and to notify that thread. The daemon thread is suspended immediately after it is created.When the daemon thread wakes up to run, the passive server executes it using the server’s own budget.
Scheduling of Work Threads When a client application Tk requests service from an SSP, it sends a budget and a deadline for consuming the budget along with its request to the service provider. The parameters of the work thread created to service the client include its budget and deadline, which are equal to the respective values given by the request. The scheduler of the passive server schedules its daemon thread and all the work threads on the EDF basis, and the OS scheduler schedules the passive server according to the deadline of the thread at the head of the server’s ready queue.
The passive server also has a suspend queue.Whenever the budget of the passive server
is exhausted but the executing thread remains incomplete, it is removed from the server’s
ready queue and inserted in the suspend queue. When the requesting application sends more
budget, the scheduler of the passive server reactivates the work thread, setting its budget and
deadline accordingly and moving it back to the ready queue. When the thread completes, any
unused budget is returned to the requesting application.
API Functions for Invocation of System Services. A real-time client application requests service by sending the service provider one of two Real-Time Application Programming Interface (RTAPI) calls: send data( ) and recv data( ). The former is called when a client application requests the service provider to accepts its data (e.g., to send a message or write a file.) When called at time t by an application Tk , the function send data( ) first invokes the server scheduler of server Sk to transfer its budget and deadline to the passive server of the service provider. The call wakes up the daemon thread of the service provider. When this thread executes, it creates a work thread, as described in the previous paragraphs. In the meantime, the calling thread within the client application is blocked until the work thread completes.
A client application calls recv data( ) to request a service provider to process incoming data on its behalf. Similar to send data( ), recv data( ) also causes a transfer of budget to the passive server of the system service provider. If the data to be received are not available at the time, the call effectively freezes the client application, since the server of the application has no budget to execute and the service provider cannot execute on behalf of the application as the
data are not available. To circumvent this problem, the client application first calls wait data( ) to wait for the data. If the data are available, wait data( ) returns immediately. Otherwise, the thread calling wait data( ) is blocked. Unlike send data( ) and recv data( ), wait data( ) does not transfer budget to service provider. Hence, when the calling thread is blocked, the server of the application can still execute other threads in the client application. When incoming data arrive, the daemon thread processes the data just to identify the receiver of the incoming data and, after the receiver is identified, wakes up the thread that called wait data( ) if the thread exists, and wait data( ) returns. The client application then calls recv data( ) to transfer to the service provider the budget needed by the SSP process and receive the incoming data.
In effect, a call of the send data( ) or recv data( ) function causes a transfer of budget from the server of the client application to the passive server of service provider. Because this transfer does not violate any of the schedulability conditions stated above, the client remains schedulable. The schedulability of other applications is not affected by the execution of the service provider.
Other Real-Time API Functions. In addition to the real-time API functions for communication between real-time applications and system service providers, the open system also needs to provide API functions for the creation, admission, and termination of real-time applications. As an example, the prototype system described in [DLZS] provides a function called register application( ). A real-time application calls this function to specify for the operating system its required capacity, as well as its choice of real-time scheduling algorithm and resource-access protocol among the ones supported by the system.
The prototype supports periodic and aperiodic tasks. A real-time application calls a create periodic task function to create a periodic task of the specified phase, period, and relative deadline, as well as informing the operating system of the resources the periodic task will require and the maximum length of time the task will hold these resources. Similarly, it calls a create aperiodic task function to create an aperiodic task that will execute in response to a specified list of events. After creating and initializing all its tasks, an application then calls start application( ) to request admission into the open system.
The prototype also provides API functions for use by SSPs in their interaction with client applications. Examples of these functions are add thread budget( ), which replenishes the budget of the specified thread in response to the add budget( ) request.