Design of real-time virtual resource architecture for large-scale embedded systems

Embedded computers have become pervasive and complex. Every microwave oven has one. The Volvo S80 has more than fifty. A Boeing 777-300 has hundreds. Meanwhile, more and more embedded systems are inter-connected to perform so- phisticated functions on their hosts such as the air information management sys- tems on modern aircrafts. However, due to real-time and fault-tolerance concerns, embedded systems are traditionally implemented on dedicated hardware. This ap- proach entails at least three serious consequences: firstly, profligate and rigid usage of resources necessitated by the binding of subsystems to hardware platforms; sec- ondly, significantly more difficult system integration because individually developed and tested systems are not guaranteed to work in combination; thirdly, the lack of higher-level system control because conceptually indivisible functions are isolated on the hardware level. These problems have caused not only financial loss such as unusable systems due to the high cost of unjustified resource redundancy and integration failures, but also the loss of human lives as exemplified by a number of fatal accidents induced by the third problem. It is critical that system engineers have a solid basis for addressing these fundamental design problems in large-scale real-time embedded systems. An ideal solution should achieve a complete separa- tion of concerns so that: (1) each task group may be executed as if it had access to its own dedicated resource, (2) there is minimal interaction between the resource level scheduler and the task level scheduler, and (3) in case of hardware failure, task groups could easily migrate to other resources. Towards this end, in this dissertation we introduce the notion of a Real-Time Virtual Resource (RTVR) which operates at a fraction of the rate of the shared physical resource and whose rate of operation varies with time but is bounded. Tasks within the same task group are scheduled by a task level scheduler that is specialized to the real-time requirements of the tasks in the group. The scheduling problems on both task level and resource level are analyzed. We specifically investigate RTVRs on the integer domain. For the case of regular resource partitioning, we show that the utilization bounds of both fixed- priority scheduling and dynamic-priority scheduling remain unchanged from those for dedicated resources. We determine the utilization bounds for the more general case of irregular partitioning. In particular, both types of partitions can be effi- ciently constructed by exploiting compositionality properties vis-a-vis the regularity measure. We further extend the applicability of the RTVR in several directions. First, we propose a hierarchical real-time virtual resource model that permits resource partitioning to be extended to multiple levels. Through this model, partitions on each level are scheduled as if they had access to a dedicated resource. Interference between neighboring partition levels is also minimized. Second, we apply RTVR to gang scheduling which is a popular scheduling technique used in parallel systems. We show that the clean isolation between resource-level and task-level scheduling makes RTVR an ideal candidate for implementing the gang scheduling solution in the real-time systems environment. Third, RTVRs in distributed environments are also discussed and end-to-end delay of a series of RTVRs is calculated. Finally, we investigate the resource locking issues in RTVR and present a resource server solution which has a highly efficient admission test. We also present an optimization scheme called Partition Coalition which is based on the server solution and which can substantially reduce the blocking time due to resource locking. These results provide a foundation for implementing RTVR on small-scale multiprocessor or processor cluster systems that are increasingly available. Based on the previous theoretical framework, we implement RTVRs on the Linux 2.4 kernel. The first RTVR implementation uses a static resource level sched- uler which can be applied to systems with predefined application task sets. The second implementation has a novel dynamic resource level scheduler under which task groups can join and leave dynamically. We further virtualize network devices. Several experiments are conducted to measure system performance in various as- pects such as the effect of the scheduling quantum size, interrupt request response time and scheduling overhead. The experiments demonstrate that RTVRs can be efficiently implemented while satisfying their theoretical properties.