The Research On Real-Time Tasks Scheduling Algorithms In System-On-a-Chip(SOC)

With the quick development of large scale integrated circuit design technology and micro-electronics manufacturing technology, especially the present of deep sub micron semiconductor technology, hundreds of millions transistors can be integrated into a single chip now, which makes integrating CPU,memory and I/O devices into a single chip possible.Microcontroller, as the cen-tral part of various embedded real-time control systems (such as flight control system,antiaircraft defense system), has been designed and manufactured by SoC(System-On-a-Chip) technology completely, with the aims of reduced cost, energy saving, improved reusability and short time-to-market. Meanwhile, in the face of the dilemma of high performance and low cost, increased system complexity and decreased update cycling of products, behindhand design technologies and fast development of semiconductor technologies, SoC co-design method had been exploited to production-manufacturing of more and more microcontrollers. With the methodology of hard-ware/software co-design, there must be the software parts as well as the hardware parts on SoC. The RTOS can not only improve the performance and reliability of the system,but also simplify the development and debugging of SoC.There is a growing consensus that the real-time operating system(RTOS) has become an indispensable part of SoC.Differing from the classical real-time control systems, the physical resources of SoC real-time control system are very limited, its execution mode conforms to the event-driven reactive model,its targeting platforms are heterogeneous. These features make the real-time task schedul-ing policy, as the most essential part of RTOS of real-time control systems, face some new chal-lenges:its context switch cost of task preemption should be small as much as possible, its energy consumption of task set should be low as much as possible, its memory usage of task set should be saved as much as possible. However, current RTOSs usually exploit preemptive scheduling policies, which leads to the more task preemptions and higher resources requirements. Thus, in the embedded real-time computing environment, how to reduce the number of task switch and decrease the resource consumption under the condition of task's schedulability, would be a new interested problem.In this thesis, the research aim is the problem of real-time task scheduling in the miniature embedded real-time control systems, manufactured by SoC technologies. Given the remaining drawbacks and shortcomings of current research works on this problem,we propose a series of energy-efficient scheduling algorithms and memory-efficient scheduling algorithms, provide theo-retical proofs to the correctness and feasibility, at the same time a series of simulation experiments was evaluated for the performance and effect of our algorithms. Our research works are embodied into three following aspects:1.We propose a new FPPT scheduling paradigm on asynchronous task set, where a new schedu-lability test approach is firstly developed to calculate the worst case response time of every task under some preemption threshold assignment and determine its schedulability, Further-more, this paper presents algorithms to compute the feasible preemption threshold Assign-ment, and the proofs for the correctness of these algorithms are also presented.2.We address the problem of computing static and dynamic slowdown factors in the FPPT algorithm.Firstly, Sufficient constraints have been identified for the feasibility of the task set using slowdown factors. We formulate this problem of computing the static slowdown factors for tasks as an nonlinear optimization problem to minimize the total energy consumption of the system.Our simulation experiments show on an average 17%-53% energy gains over FPPT scheduling policy.3.We address the problem of variable execution time in tasks under the FPPT scheduling pol-icy, our approach exploit the stochastic data to develop the intra-task voltage scheduling, experiments show that more fluctuated task workload, more energy gains over usual DVS techniques.4.we address one of such side effects, an increase in task preemptions due to DVS.We present energy-efficient Fixed priority with preemption threshold(EE-FPPT) scheduling algorithm to solve this problem.First, we propose an appropriate schedulability analysis, based on response time analysis, for supporting energy-efficient FPPT scheduling in hard real-time systems. Second, we prove that a task set achieves the minimal energy consumptions under Maximal Preemption Threshold Assignment(MPTA).5.We propose a two-phase algorithm.In the first phase, the execution speed, i.e.,the supply voltage of each task are determined by applying off-line algorithms, and in the second phase, the procrastination length of each task is derived by applying on-line simulated work-demand time analysis, and thus the time moment to turn on/off the system is determined on the fly. A series of simulation experiments was evaluated for the performance of our algorithms. The results show that our proposed algorithms can derive energy-efficient schedules.6. We propose a new FPTS scheduling paradigm,which integrates FPPT with SRP, includ-ing the new Critical Instant, preemption threshold assignment and appropriate schedulability analysis, based on response time analysis. Furthermore, we present algorithm to compute the feasible preemption threshold assignment, and the proofs for the correctness of these algo-rithms are also presented.