Research On Task Scheduling For Open Real-time Systems

With the rapid development of the hardware in computer science, it is possible that several complex hard and soft real-time applications developed and deployed independently run on a fast and general-purpose workstation or personal computer system concurrently with some non-real-time applications. Further, the real-time and non-real-time applications are allowed to join and leave the system dynamically. The system is called"Open real-time system", which is one of the hottest topics in real-time computing area. Real-time scheduling is one of the critical technologies in real-time systems. The traditional real-time scheduling theories and mothods are very mature, but they are used in traditional real-time systems which process some special real-time applications. How to schedule the tasks in open real-time system is a new challenge.Two-dimensional priority scheduling sheme not only sets task priority, but also specifies scheduling policy priority. The priorities of scheduling policies are set first. For example, the priority of EDF is set to the highest. That of RM is set to the second highest. That of SD is assigned to the second lowest priority. That of non-real-time scheduling policy is assigned to the lowest one. Secondly, the priorities of the tasks with the same scheduling policy are set according to their policy. In the scheme, the execution order of a task is determined by both its priority and its scheduling policy priority. This scheme not only resolves the problem of scheduling policy dependent on scheduling mechanism in tradisional priority-driven scheduling methods, but also overcomes the shortcoming not suitable for the parallel and distributed real-time applications in the existing open real-time scheduling schemes. It is suitable the situations with privilege and rank.Howerver, in two-dimensional priority scheduling scheme, the tasks in the ready queue of the scheduling policy with lower priority will not be scheduled for ever, which is called dead-waiting, in the case that the ready queue of the scheduling policy with the highest priority is always nonempty, and it is not suitable for the fair situations. In the CUS(Constant Utilization Server)-based hybrid scheduling scheme, a CUS is assigned to each real-time scheduling policy. At the bottom level, the top-level servers are maintained and scheduled by the global EDF scheduler. The framework not only resolves the problems in the existing schemes, but also makes up the insufficiency in the two-dimensional priority scheduling scheme and suit for the fair situations. Its performance can be improved by introducing spare bandwidth reclaiming mechanism and overrun control into CUS.The size of CUS is fixed, however the workload of open system is dynamically variable, so the overall system's performance becomes quite dependent on a correct CUS size allocation. For example, if the CPU bandwidth allocated to a CUS is much less than its requested value, many tasks will be rejected by the system because they can't pass the schedulability test, degrading the system's performance. On the other hand, if the allocated bandwidth is much greater than the actual needs, the system will run with low efficiency, wasting the available resources. The size of VUS (Vaviable Utilization Server) can be adjusted to meet the requirements according to the change of the system's workload. Futher, the maintenance algorithm of VUS is better than that of CUS. The experimental results also show that the VUS-based two-level hierarchical scheduling scheme has better performance and is more suitable for the task scheduling of open real-time system than others.With the application spread, there is an increasing demand that several complex real-time applications developed and deployed independently and then run on the distributed systems concurrently with some non-real-time applications. The open distributed real-time systems come up with new requirements for task scheduling. The real-time scheduling framework based on CPNA (Classified-Processing-Node-Allocation) algorithm with an EDF-driven heuristic algorithm and FCF (First-Committed-First) algorithm is more suitable for homogeneous systems and also has good performance, but when the number of processing nodes in distributed system is less than 3, or when the classification number of processing nodes is too small, it does not separate the scheduling mechanism from the scheduling policy well, which will limit the open degreere of open systems and also restrict its performance. The real-time scheduling scheme based on most-demand-first and most-idlest-fit allocation algorithm with VUS algorithm overcomes the shortcomings in the existing schemes, which is applicable to many task models and separates the scheduling mechanism from the scheduling policy and is suitable for the complex parallel/distributed applications and heterogeneous system environments. Furthermore, the most-demand-first and most-idlest-fit allocation algorithm can balance the workload in distributed system. The new method has high open degree and high performance, which is a good choice for task scheduling in open distributed real-time systems.Based on the theory research, a Linux-based open distributed real-time system has been implemented. The test results showed that the system had good real-time performance. Both event latency and periodic jitter are below 25μs. It can be used in many fields, such as real-time control systems, numerical control systems, manufacturing, and so on.