Research On The Task Of Bandwidth Transfer In EDF Algorithm

With the development of society and technology,real-time application have emerged continously,demand of the flexibility has became greater and greater.real-time sheduling algorithm,as a key point of ensuring real-time system ' s performance,is always a important topic in real-time systems area.EDF(Earliest Deadline First)is a classic dynamic sheduling algorithm in real-time systems.Buttazzo,a famous scholar in real-time systems area,put forward an elastic schedule model that based on EDF,made task sheduling more flexible,the problem of the earliest feasible time for the new task has came into view at the same time.Buttazzo had given a solution of this problem,a calculating formula of the earliest feasible time(hereafter referred to as B theorem),Qian improved the B theorem,put forward a better calculating formula(hereafter referred to as Q theorem).But in fact,the calculating result of using Q theorem for the new task of the earliest feasible time is not always the earliest,there is a better insertion time than the Q theorem In practice.In the other words,thecalculating of the earliest feasible time with a new task is still an open problem.This article is based on the above research background,focuses on the problem of bandwidth transfer caused by the new task insertion and the current task accelerationin EDF dynamic scheduling model.This article analyzes the scheduling results of different insertion time of new tasks accroding to the principles of the processor demand and put forward the principle of the task deadline.This principle gives 2conditions that make the new task ' s insertion time feasible.We can get a inference from the principle of the task deadline: the feasible time is the earliest feasible time when3 assumptions hold.these assumption always give the maximum badnwidth reservation to ? which means a task set of other task.Considerating that ? do not always require maximum bandwidth,it is a direction of researching the earliest feasible time that bringing ? into the scope of research and analysing the preemptive details of ? and task pair in the bandwidth transfer model.This article discuss some situations that ? particpating in task preemption,also do some Analysis of scheduling result in those situations.Scheduling results in those situations are better than B theorem and Q theorem.For a task set that needs to be shceduled,the earliest feasible time can be calculated by computer iteration,But this way consumes more time and its application value is lower at runtime.This article aims at the situation of a task pair(A compressed task transfers bandwidth to another task),,put forward an online algorithm that computing the earliest feasible time of new task insertion under 3 assumptions.A large number of simulation experiments show that the earliest feasible time of the online algorithm is earlier than that of B theorem and Q theorem.