LTS: Linear task scheduling on multiprocessor through equation of the line

Real-time task scheduling in embedded multiprocessor systems, as the name implies, is known as a problem because of two major difficulties: identifying tasks´ priority and task assignment issue. The former, has especially a significant importance in the case of global real-time scheduling on symmetric multiprocessor environment. The great importance of priority assignment becomes even clearer when we observe that only by using dynamic priority assignment for decision making it will be possible to reach an optimal global scheduling algorithm. In this paper, too, a novel approach (called LTS) for dynamic priority assignment of periodic real-time tasks with implicit deadline on multiprocessor is portrayed which is based on the equation of the line. In order to attain this objective, task computation time coupled with deadline time is used to generate an equation of the line to represent the priority of each task at every time unit. Then, such equation is employed so as to assign priorities to the tasks and thus, at every time unit, those tasks which hold higher priorities are selected for processors to be assigned to execute. We also introduce an essential rule for task assignment to prevent potential deadline misses. Experiments were performed on 4500 randomly generated tasksets indicating that not only can LTS schedule periodic tasksets on single processor, but it also schedules tasksets with total utilization ≤ m on multiprocessor environment with m processors safely.