On Hierarchical Scheduling in VxWorks

Theoretically, hierarchical scheduling has many advantages when it comes to integrating real-time applications on a single CPU. Even though each subsystem (real-time application) will get less resource in the form of CPU (as they are required to share the CPU), they will not be forced to have their properties changed (periods, priorities, etc.) during the integration and their scheduling policy is allowed to remain the same. Each subsystem will still be isolated as if it would be executing in isolation and the error of one subsystem can not propagate and affect other subsystems. A subsystem can be viewed as a virtual task which in turn have it's own properties. Virtual tasks will be scheduled by a global scheduler and virtual tasks execution includes the scheduling of it's local tasks (by the virtual tasks local scheduler) as well as the local task execution. The cost of all the explained advantages is the overhead of the global scheduler. In facilitating the above mentioned benefits a more complex scheduler has been developed. A hierarchical scheduling framework (HSF) will only be of use and interest if it is time efficient (low overhead) and if it is possible to implement it on top of already existing industrial systems. This thesis address these issues and specifically exploit the possibilities of designing and implementing a HSF on top of one of the most commonly used commercial industry real-time operating system, namely Vxworks. The focus during the development of the HSF has been to find, evaluate and choose the most time efficient design solutions in order to impose as little system overhead as possible. The work can be separated into two sections. First we designed and implemented two extensions to the native vxworks fixed priority preemptive scheduler. The first extension was to implement a module that had support to schedule tasks periodically. This module has an absolute time based multiplexed software timer event queue (TEQ). The second extension was an Earliest Deadline First (EDF) implementation. These two extensions together with the native vxworks scheduler form two new local schedulers, a Fixed Priority (FPS) periodic task scheduler and an EDF periodic task scheduler. When the local schedulers were implemented, we moved on and designed and implemented two global schedulers (FPS and EDF). The HSF uses these two global schedulers (one of them) and schedules servers according to the periodic server model. Each subsystem is then internally scheduled by either our local FPS or EDF scheduler. Server execution time (budget) and period, as well as tasks periods and deadlines, are handled by the TEQ. Each local system will each have their own TEQ and the servers will have one common TEQ. Detailed scheduling overhead analysis for the local and global FPS scheduler was derived using the Response Time Analysis (RTA). Moreover, we did extensive time measurements of the local schedulers, the global schedulers and the HSF itself. Execution traces from tests are graphically shown using execution recording of tasks.