Study On Timely Scheduling Of Embedded Distributed Real-Time System

With the development of technology, the complexity of Real-Time system has reached a new level. Because Embedded Distributed Real-Time system combines the advantages of Distributed system and Embedded Real-Time system, it will be more and more widely applied. In Real-Time system tasks must be finished in given deadlines, so tasks waiting for execution should be scheduled reasonably. In order to guarantee the predictability of Real-Time system, the Worst-Case-Execution-Time (WCET) is often used in scheduling analysis which determines whether a task should be executed or not. This is essential for those critical tasks. However, the Embedded Distributed Real-Time system often exists in very complex and dynamic surroundings, it is impossible to predict the task's upper bound of execution time. Even if the upper bound can be predicted, there are only a few occasions when tasks run to the upper bound of execution time. If we still use the present scheduling algorithms in Embedded Distributed Real-Time system, the cost of constructing a Embedded Real-Time system will be very high and system resource will not be fully applied.After analyzing the features and deficiencies of the distributed system architecture standards such as CORBA, RTCORBA, minimum CORBA and Jini., A new system model of Embedded Distributed Real-Time system has been proposed. Based on this model and imprecise computation, timely scheduling is studied. The main contents of this thesis are presented as follow.(1) Model of Embedded Distributed Real-Time system. All services in model are transparent and extensible, and simple developing platform of Embedded Distributed Real-Time system is presented. Programmers can develop embedded distributed in a single image programming system model, which saves a lot of time in developing complex embedded distributed real-time applications.(2) Timely scheduling based on presented model and imprecise computation. According to the concept of imprecise computation, tasks are divided into two portions: Mandatory Portion and Optional Portion. Mandatory Portion must be finished within deadline and acceptable results can be gained. After finishing Mandatory Portion, Optional portion can execute to refine the results if processor is idle. In our presented system model there is central node used to implement timely scheduling and called service management and scheduling node. Its major work is to register all services and corresponding request messages which are all saved into an optional execution path task graph. The service management and scheduling node can receive request messages from clients. Then, according to optional task execution path graph, it tries to calculate a highest reward execution path through the Time-Constrained Execution Path Selecting Algorithm and produces a scheduling control message including execution time of all tasks in the calculated execution path. The Scheduling Control Message guides related processors to distribute enough time to tasks in all nodes belonging to the calculated execution path. Because the Time-Constrained Execution Path Selecting Problem is NP-complete, a heuristic algorithm is presented in this thesis. Timely scheduling mechanism overcomes the drawbacks of traditional scheduling algorithms in many real-time systems, so it can reduce the cost of constructing the Embedded Distributed Real-Time system.