An Efficient Dynamic Scheduling of Tasks for Multicore Real-Time Systems

What is it about?

Embedded real-time systems are increasing day by day to execute high-performance-oriented applications on multicore architecture. Efficient task scheduling in these systems are very necessary so that majority of the tasks can be scheduled within their deadline and thus providing the needed throughput. This paper presents a scheduling algorithm where random tasks generated at different time intervals with different periodicity and execution time can be accommodated into a system, which is already running a set of tasks, meeting the deadline criteria of the tasks. The idle time of the cores has been found based on the execution time of the existing tasks. Using the concept of Pfair scheduling, random new tasks have been divided to fit into the idle times of the different cores of the system. We verify the proposed algorithm using generated task sets, and the results show that our algorithm performs excellently in all the cases.

Featured Image

Why is it important?

This paper proposes a simulation model to find the best possible way to schedule the given set of tasks efficiently to the available processing cores so that all the task deadlines are met and also the throughput of the system is optimum for the set of tasks. The model maintains two-level queues—global and local. It also uses the concept of two algorithms, namely EDF and Pfair as per follows: (a) EDF at the global queue of new tasks and (b) Pfair for context switching and forwarding the job to local queue. Time complexity of both EDF and Pfair algorithm is O (logn); therefore, time complexity of the proposed model is also O (logn), but the model has some novelties in respect to efficient utilization of the processors as well as fitting almost all the tasks efficiently meeting the deadline condition, which is given below: The model is better than EDF scheme because EDF works well in underloaded condition and when there is only one processor. But our proposed model is in overloaded condition and has multiple processors. The same model can also be used in underloaded condition having a single processor. Further we can allocate almost all the new tasks into the cores if 1. Periodicity is big for the new task 2. Execution time of new task is small 3. Task is divided into huge number of jobs thus decreasing their execution time so that jobs can be fitted before next instance of the existing task starts. In RM scheduling, all the deadlines of randomly generated periodic task can be met if CPU utilization is less than or equal to 85 %. With scheduling periodic task containing same deadlines and periods, utilization bound of EDF is 100 %, but this is an ideal situation where the system is not in overloaded condition. The CPU utilization of our proposed model varies from 95 % to 100 %, meeting all the task deadlines and all the system conditions. Hence, CPU utilization of our model is very high comparable to RM scheduling and EDF scheduling.