Research On The Dynamic-Priority Scheduling Algorithms Of Tasks In Real-Time Systems

The accuracy of the computing results and the timeliness when the results come out in a real time system make it widely used in more and more areas, such as industry, defense, medical care and communications.However, with the higher demands of schedulability of real time systems, it is harder and harder for the traditional real-time scheduling algorithms to satisfy the demands of the applications.In this dissertation, we have researched on the scheduling on uniprocessor systems and multiprocessor systems, especially focused on the dynamic prioritiy scheduling algorithms.The main contributions and achievements of this dissertation are stated as follows:The least slack time first scheduling algorithm may frequently cause switching or serious thrashing among jobs.In this dissertation, an improved dynamic fuzzy threshold least slack time first scheduling algorithm for soft real-time sytems is proposed. The notion of fuzzy threshold coefficient is given. The slack time and the period of the running job are selected as the fuzzy inputs.The fuzzy threshold coefficient is generated by fuzzy theory.We regard the dynamic fuzzy threshold as the virtual slack time of the running job to avoid preemption. The simulation results show that, the dynamic fuzzy threshold makes the switching number of the improved algorithm smaller and the ratio of success not descreased.To avoid the frequenty switching and decrease the missed deadline percentage when the systems is overloaded in earliest deadline first scheduling algorithm, two improved earliest deadline first algorithms are presented in this dissertation. In the two algorithms, the slack time and the cruces coefficient of the running job are selected to be the fuzzy inputs in order to genenrate the fuzzy threshold coefficient. The absolute deadline of the running job is extended to save the resource in one algorithm and is shorten to increase the ratio of success in the other. The threshold is decided by several parameters of the running job, as a result, the ratio of success for important jobs is increased in both of two algorithms. The performance of the algorithms is experimentally examined and compared with the earliest deadline algorithm in detail.Results show that, the missed deadline percentage is decreased obviously while the deadline is extended and the switching number is reduced greatly while the deadline is shortened. The ratio of success for important jobs is increased efficiently by using these two algorithms. When the number of priority levels supported by the system is limited, it is hard to ensure the accuracy of grouping method in the scheduling algorithms.To solve this problem, an improved group priority earliest deadline first scheduling algorithm is proposed. We give the schedulability test. All the jobs satisfying the schedulability test are formed into a group and the earliest absolute deadline of the jobs in the group is chosen to be the priority of the group. The group and the other jobs in the system are scheduled under earliest deadline first. When the group gets the system resource, the jobs in the group are scheduled under shortest job first. Compared with earliest deadline first algorithm, best effort algorithm and other grouping algorithms, the simulation results show that the novel algorithm not only can decrease the priority levels effectively, but only can increase the ratio of success, shorten the average response time and reduce the switching number.In the scheduling of sporadic tasks on identical unit-capacity mulitiprocessors, the criterions used in density algorithm and the DBF* algorithm may cause the tasks which are feasible under the partitioned paradigm be flagged as "infeasible" sometimes.In this dissertation, a novel efficient demand bound function partitioned scheduling algorithm is proposed. A criterion which tracks the demand bound function exactly as needed is used on least-number processors and fixed-number processors respectively to avoid the incorrect judgment in determining whether a processor can accommodate an additional task in the novel algorithm. The experimental results demonstrate that the number of tasks schedulable in the novel algorithm is much higher than in density algorithm and DBF* algorithm.The partitioned scheduling on heterogeneous multiprocessors is complicated and hard to be optimal.To solve the problem, a novel integer linear programming partitioned scheduling algorithm is proposed. After describing the parameters of the tasks and the processors correctly,we regard the total utilization as the objective function and get the minimal value of the objective function by the constraints.The scheduling problem is changed to an integer linear programming problem.We use Lingo to get the solutions and assign the tasks according to it. The simulation results show the validity of the novel algorithm.