Design Of Real-Time Virtual Resource Architecture For Embedded System

Embedded computers have become pervasive and complex. In our daily life, many electric equipment and other equipments, from microwave to plane, almost all have one or more embedded systems. Meanwhile, more and more embedded systems are inter-connected to perform sophisticated functions on their hosts such as the air information management systems on modern aircrafts. However, due to real-time and fault-tolerance concerns, embedded systems are traditionally implemented on dedicated hardware. This approach entails at least three serious consequences:firstly, profligate and rigid usage of resources necessitated by the binding of subsystems to hardware platforms; secondly, 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. An ideal solution should achieve a complete separation 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 RTVR 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 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. Then 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 RTVR on the Linux 2.4 kernel. The first RTVR implementation uses a static resource level scheduler 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. Several experiments are conducted to measure system performance in various aspects such as interrupt request response time. The experiments demonstrate that RTVR can be efficiently implemented while satisfying their theoretical properties.