Research On The Earliest Deadline First Real-Time Scheduling Algorithm

The real-time system has some characters such as responsing in time, high dependability, dedication and less artificial interference, so it is widely applied in the industrial control, military defense, signal processing, and aerospace technology. In the real-time systems research and applications in various fields, real-time scheduling algorithms are one of the basic problems, For a variety solution of real-time problem, it need on the basis adopt some kind of real-time scheduling algorithm, testifying whose feasibility combining with owing real time scheduling algorithmic character ability more well. Therefore, real-time scheduling algorithm is important for the real-time systems research and popularization. The EDF (earliest deadline first) scheduling algorithm as the optimal dynamic priority scheduling algorithm, the scheduling strategy is simple and periodic task sets can reach 100% of the total load, so there are a very attractive prospect.The maximum stealing time of the EDF algorithm for scheduling periodic task has important application in many fields such as the non-periodic tasks scheduling, soft real-time tasks scheduling and multi-processor fault-tolerant scheduling, etc. Analysing of the nature of the maximum stealing time, giving the result that the maximum stealing time is equal to the minimum delayed time appears in the first busy time interval of the hyperperiod, presents the DTA (delay time approximation) algorithm. Using the optimal nature of EDF scheduling algorithm, and apporathing gradually by the delayed time of the task with the minimum period time, DTA algorithm can rapidly and accurate calculate the maximum stealing time. The algorithm's time complexity is only related to the total load of the periodic task set and the number of periodic tasks.The existing hard real-time periodic tasks and non-periodic task scheduling algorithm aims to shorten the response time of aperiodic tasks and can not determine whether the task can meet the deadline tiem. So they are only suitable for soft real-time task scheduling, does not apply to sporadic task scheduling. Because EDF algorithm is based on the deadling time of each real-time task, so can use EDF scheduling algorithm to unified schedule real-time periodic tasks and sporadic tasks, and has the best schedulability. By calculating the idle time and the stealing time in the scheduling procedure with EDF algorithm, propose the ISS (idle slack stealing) algorithm to determine the schedulability of sporadic tasks.When there are mutual exclusion resources sharing between some real-time tasks, using resource access control protocol can prevent real-time task has been indefinitely blocked, but can not prevent the direct blocking caused by priority inversion. In blocking time, the low-priority task seizes the high-priority task to run, disrupting the normal EDF scheduling procedure. By proving that blocking time does not change the distribution of idle time, and in a busy time interval, all periodic tasks will only be postponed once due to the same mutual exclusion resource. Then the blocking time as steal time and according to the definition and nature of maximum steal time, put forward the BTS (blocking translate stealing time) algorithm, witch can determine the conditions for schedulability. As long as the sum of the most critical areas of resources is more than the length of the maximum steal time, the real-time periodic task set is to be scheduled with EDF algorithm.