Design and implementation of real-time scheduling schemes for genral purpose operating systems

Abstract

In recent years, we have seen proliferation of computation-intensive, time-critical applications like real-time video, audio, IP-based telecommunication and so on. These applications offer value-added, nice-to-have features in our everyday life but demand enhanced support from the computing environment in which they execute. The cheapest solution to this problem is to make these applications execute in the commonly available computing infrastructure. An example of such applications is a real-time, computation-intensive MPEG player that executes in an ordinary personal computer (PC) running a general purpose operating system (GPOS), such as UNIX, Macintosh or Windows. But none of these GPOSs provide definitive, real-time performance guarantees to the applications they execute. In this research work, we present a set of real-time scheduling schemes for a GPOS. These scheduling schemes are able to provide real-time performance guarantees to the applications on behalf of the underlying operating system. We have named these schemes as the Selective Periodic Scheduling (SPS) schemes. In this work, we have proposed the SPS schemes for periodic real-time tasks. The SPS schemes are based on the principles of classical cyclic scheduling with some important fundamental differences. Firstly, the invocation period of the SPS scheduler is independent of the periods of the applications. Secondly, the release instant of the first job of a task is controlled by the scheduler. This results in the reduction of the maximum load at any scheduling instant and makes it easier for the applications to meet their respective deadlines. In the earlier portion of this work, we present a detailed schedulability analysis for a set of real-time applications to be scheduled using the SPS schemes. This analysis forms the basis for the acceptance test for an application requiring real-time support from the system and also for the construction of a feasible schedule for a set of real-time applications. The schedule guarantees real-time performance for the applications. In the latter portion of this work, we present the design for the proposed scheduling schemes based on the analysis. It contains the algorithms and the data structures for the implementation of the SPS schemes. The SPS scheduler is to be integrated with the usual kernel scheduler of the GPOS and needs to be executed with the same period as the timer interrupt of the GPOS for its operations. The design is followed by the description of an experimental implementation of the SPS schemes to test the feasibility and effectiveness of our theory. The schemes are implemented as a user-level scheduler. The timer interrupt dependency of the scheduler is simulated using signals at the user level. Results obtained from even this user-level simulation show encouraging improvement in the performance of the applications needing real-time guarantees.