The Research Of Real-time Scheduling Algorithm Under Sigle Processor Environment

With the rapid development of networking, communications and multimedia computing, embedded systems are widely used, and the application of real-time systems have been expanded from its traditional domains, such as scientific researches, national defences, industrial control and so on, to many other areas of human society. The research of real-time systems focuses on two key issues:one is the scheduling algorithms of real-time tasks, and the other is deciding the schedulability of a set of real-time tasks. To address these two problems, this thesis proposes a schedulability decision algorithm for a set of hard real-time periodic tasks and sporadic tasks named IISS (Improved Idle Slack Stealing), as well as an improved Least Slack first (LSF) scheduling algorithm named DPTLSF (Dynamic Preemption Threshold LSF).IISS algorithm is designed to solve the hybrid scheduling schedulability decision problems of hard real-time periodic tasks and sporadic tasks and ensure the schedulability of sporadic tasks. Starting from the concept of EDF scheduling procedures and the reverse EDF scheduling procedures, the maximum time which can be diverted at any time of the EDF scheduling procedure is analyzed;IISS algorithm will schedule sporadic tasks to run either between the gaps of periodic tasks’ execution time, or the time diverted from periodic tasks. According to different characteristics of sporadic tasks, it will determine a dynamic time point named Tdynamic and output a sufficient condition for deciding the schedulability of sporadic tasks. Simulation results show that, IISS is more accurate and flexible than the existing algorithms.DPTLSF scheduling algorithm is designed to address the limitations of a classical scheduling algorithm named LSF which has high context switching frequency and high deadline missing rate. DPTLSF is based on the preemption threshold strategy and the analysis of the performance impacts that different idle time preemptions imposed on the LSF scheduling algorithm, and it uses a dynamic preemption threshold to avoid the "bumps" phenomenon resulted from switching tasks too frequently. Simulation results show that the proposed algorithm can reduce the number of context switches significantly and can also reduce the deadline missing rate of tasks under different processor load and the number of tasks in different cycles.