الگوریتم برنامه ریزی غیر پیشگیرانه برای سیستم های نرم زمان واقعی

Real-time systems are often designed using preemptive scheduling and worst-case execution time estimates to guarantee the execution of high priority tasks. There is, however, an interest in exploring non-preemptive scheduling models for real-time systems, particularly for soft real-time multimedia applications. In this paper, we propose a new algorithm that uses multiple scheduling strategies for efficient non-preemptive scheduling of tasks. Our goal is to improve the success ratio of the well-known Earliest Deadline First (EDF) approach when the load on the system is very high and to improve the overall performance in both underloaded and overloaded conditions. Our approach, known as group-EDF (gEDF) is based on dynamic grouping of tasks with deadlines that are very close to each other, and using Shortest Job First (SJF) technique to schedule tasks within the group. We will present results comparing gEDF with other real-time algorithms including, EDF, Best-effort, and Guarantee, by using randomly generated tasks with varying execution times, release times, deadlines and tolerance to missing deadlines, under varying workloads. We believe that grouping tasks dynamically with similar deadlines and utilizing a secondary criteria, such as minimizing the total execution time (or other metrics such as power or resource availability) for scheduling tasks within a group, can lead to new and more efficient real-time scheduling algorithms.

The Earliest Deadline First (EDF) algorithm is the most widely studied scheduling algorithm for real-time systems [1]. For a set of preemptive tasks (be they periodic, aperiodic, or sporadic), EDF will find a schedule if a schedule is possible [2]. The application of EDF for non-preemptive tasks is not as widely investigated. It is our contention that non-preemptive scheduling is more efficient, particularly for soft real-time applications and applications designed for multithreaded systems, than the preemptive approach since the non-preemptive model reduces the overhead needed for switching among tasks (or threads) [3] and [4]. EDF is optimal for sporadic non-preemptive tasks, but EDF may not find an optimal schedule for periodic and aperiodic non-preemptive tasks. It has been shown that scheduling periodic and aperiodic non-preemptive tasks is NP-hard [5], [6] and [7]. However, non-preemptive EDF techniques have produced near optimal schedules for periodic and aperiodic tasks, particularly when the system is lightly loaded. When the system is overloaded, however, it has been shown that the EDF approach leads to very poor performance (low success rates) [8]. In this paper, a system load or utilization is used to refer to the sum of the execution times of pending tasks as related to the time available to complete the tasks. The poor performance of EDF is due to the fact that, as tasks that are scheduled based on their deadlines miss their deadlines, other tasks waiting for their turn are likely to miss their deadlines also – an outcome sometimes known as the domino effect. It should also be remembered that Worst-Case Execution Time (WCET) estimates for tasks are used in most real-time systems. We believe that, in practice, WCET estimates are very conservative, and more aggressive scheduling schemes based on average execution times for soft real-time systems using either EDF or hybrid algorithms can lead to higher performance. While investigating scheduling algorithms, we have analyzed a variation of EDF that can improve success ratios (that is, the number of tasks that have been successfully scheduled to meet their deadlines), particularly in overloaded conditions. The new algorithm can also decrease the average response time for tasks. We call our algorithm group-EDF, or gEDF, where the tasks with “similar” deadlines are grouped together (i.e., deadlines that are very close to one another), and the Shortest Job First (SJF) algorithm is used for scheduling tasks within a group. It should be noted that our approach is different from adaptive schemes that switch between different scheduling strategies based on system load; gEDF is used in overloaded as well as underloaded conditions. The computational complexity of gEDF is the same as that of EDF. In this paper, we will evaluate the performance of gEDF using randomly generated tasks with varying execution times, release times, deadlines and tolerance to missing deadlines, under varying loads. We believe that gEDF is particularly useful for soft real-time systems as well as applications known as “anytime algorithms” and “approximate algorithms,” where applications generate more accurate results or rewards with increased execution times [9] and [10]. Examples of such applications include search algorithms, neural-net based learning in AI, FFT and block-recursive filters used for audio and image processing. We model such applications using a tolerance parameter that describes by how much a task can miss its deadline, or by how much the task’s execution time can be truncated when the deadline is approaching. This paper is organized as follows. In Section 2, we present related work. In Section 3, we present our real-time system model. Numerical results are presented in Section 4. Conclusions are given in Section 5.

In this paper, we presented a new real-time scheduling algorithm that combines Shortest Job First scheduling with the Earliest Deadline First scheduling. We grouped tasks with deadlines that are very close to each other, and scheduled jobs within a group using SJF scheduling. We have shown that group-EDF results in higher success rates (that is, the number of jobs that have completed successfully before their deadline) as well as in faster response times. It has been known that while EDF produces an optimum schedule (if one is available) for systems using preemptive scheduling, EDF is not as widely used for non-preemptive systems. We believe that for soft real-time systems that utilize multithreaded processors, non-preemptive scheduling is more efficient. Although EDF produces practically acceptable performance even for non-preemptive systems when the system is underloaded, EDF performs very poorly when the system is heavily loaded. Our gEDF algorithm performs as well as EDF in terms of success ratio when a system is underloaded. Even on systems that are underloaded, gEDF shows higher success rates than EDF when dealing with soft real-time tasks (using higher deadline tolerances). And gEDF consistently outperforms EDF in overloaded situations. In this paper we also compared our gEDF with schemes that adapt EDF when the system is overloaded. Among the adaptive algorithms, we considered the Best-effort and Guarantee algorithms. In general, gEDF, which can be used in both overloaded and underloaded situations, performs as well as or better than EDF, Best-effort and Guarantee schemes. It should be remembered that the last two adaptive algorithms require the ability to accurately measure system loads so that the overloaded conditions can be detected. In most cases this is very difficult, particularly if the workload consists of periodic, aperiodic and sporadic jobs, or if the system consists of both real-time and non-real-time jobs. Moreover, estimating system load based on worst-case execution times, leads to under-utilizations, thus predicting overloaded conditions incorrectly. These problems are not encountered by gEDF, since there is no need to estimate system load or to switch between EDF and Best-effort on overloads. In future work, we plan to explore the impact of a variety of parameters on the performance gEDF, and evaluate gEDF for real workloads.