Search

Mobile real-time systems with limited system resources and a limited power source need to fully utilize the system resources when the workload is heavy and reduce energy consumption when the workload is light. EDZL (Earliest Deadline until Zero Laxity), a multiprocessor real-time scheduling algorithm, can provide high system utilization, but little work has been done aimed at reducing its energy consumption. This paper tackles the problem of DVFS (Dynamic Voltage/Frequency Scaling) in EDZL scheduling. It proposes a technique to compute a uniform speed on full-chip DVFS platforms and individual speeds of tasks on per-core DVFS platforms. This technique, which is based on the EDZL schedulability test, is a simple but effective one for determining the speeds of tasks offline. We also show through simulation that the proposed technique is useful in reducing energy consumption.

This paper proposes an off-line dynamic voltage scaling (DVS) scheme that can be integrated with EDF$$^{(k)}$$(k), which is a global real-time scheduling algorithm for symmetric multiprocessor systems. The scheme computes the static execution speed for each individual task assuming the task's worst-case execution. Based on the individual speed, it determines static dual speeds off-line for each task to make use of the gap between actual execution demand and the worst-case execution demand. The simulation results show that the proposed scheme combined with an existing online DVS technique can reduce energy consumption by up to 37 % compared with a uniform speed technique when the number of processors is 32.

This letter proves the finish time predictability of EDZL (Earliest Deadline Zero Laxity) scheduling algorithm for multiprocessor real-time systems, which is a variant of EDF. Based on the results, it also shows that EDZL can successfully schedule any periodic task set if its total utilization is not greater than (m + 1)/2, where m is the number of processors.

Multiprocessor architecture becomes common on real-time systems as the workload of real-time systems increases. Recently new deadline-based (EDF-based) multiprocessor scheduling algorithms are devised, and comparative studies on the performance of these algorithms are necessary. In this paper, we compare EDZL, a hybrid of EDF and LLF, with other deadline-based scheduling algorithms such as EDF, EDF-US[m(2m-1)], and fpEDF. We show EDZL schedules all task sets schedulable by EDF. The experimental results show that the number of preemptions of EDZL is comparable to that of EDF and the schedulable utilization bound of EDZL is higher than those of other algorithms we consider.

Upon multiprocessor platforms, global EDZL is known to be at least as effective as global EDF in scheduling task sets to meet deadlines, but there has been no research on power-aware EDZL scheduling. In this paper, we firstly address the problem of reducing energy consumption of real-time tasks on EDZL scheduling by lowering processor speed. An off-line algorithm and an on-line algorithm are proposed to reduce energy consumption while guaranteeing a hard real-time constraint. Then we show the effectiveness of our algorithms through extensive simulation.

Rate Monotonic scheduling algorithm is widely used in real-time systems and embedded systems for its implementation simplicity and optimality in fixed priority scheduling. Since determining the schedulability of a task set in Rate Monotonic scheduling is an important step in designing a real-time system, schedulability analysis has been extensively studied. Although there is an exact schedulability test method for Rate Monotonic scheduling, the exact test is too complex to be executed on-line for large number of tasks because it is based on the response time calculation which is NP-hard. Thus many researchers studied on polynomial time sufficient conditions on Rate Monotonic schedulability. The existing polynomial time sufficient conditions are in the form of a utilization bound; that is, if a task set's total utilization is not larger than a utilization bound, the task set is accepted as schedulable one. Though the utilization bound tests are simple, they suffer from poor processor utilization. In this paper, we propose a new sufficient schedulability condition based on the response time test, different from the previous approaches. The new test provides a condition that is both necessary and sufficient for task sets with period ratio less than 2, while the previous tests provide only sufficient conditions. Extensive simulations show that our test significantly outperforms the existing tests with utilization bound.

Minimizing energy consumption with guaranteeing real-time constraints in low-power embedded systems is gaining more importance as real-time applications become more widely used in embedded systems. Dynamic voltage scaling is a technique to reduce energy consumption by lowering supply voltage. However, lowering supply voltage may interfere with scheduling algorithms, so that tasks may not be successfully scheduled. In this paper, we formulate the problem of minimizing energy consumption for Pre-scheduling as an optimization problem, and show that the problem is a nonlinear convex optimization with linear constraints which can be solved by sequential quadratic programming. By solving the problem, we can obtain the optimal supply voltage and successful scheduling of all tasks is guaranteed.

A priority-driven scheduling algorithm is said to be start time (finish time) predictable if the start time (finish time) of jobs in the schedule where each job executes for its actual execution time is bounded by the start times (finish times) of jobs in the schedules where each job executes for its maximum/minimum execution time. In this paper, we study the predictability of a job-level dynamic priority algorithm, LLF (Least Laxity First), on multiprocessor real-time systems. We present a necessary and sufficient condition for a priority-driven algorithm to be start time (finish time) predictable. Then, in LLF scheduling, we show that both the start time and the finish time are predictable if the actual execution times cannot be known. However, solely the finish time is predictable if the actual execution times can be known.

The Stack Resource Policy (SRP) is a real-time synchronization protocol suitable for embedded systems for its simplicity. However, if SRP is applied to dynamic priority scheduling, the runtime overhead of job selection algorithms could affect the performance of the system seriously. To solve the problem, a job selection algorithm was proposed that uses a selection tree as a scheduling queue structure. The proposed algorithm selects a job in O(⌈log2n⌉) time, resulting in significant reduction in the run-time overhead of scheduler. In this paper, the correctness of the job selection algorithm is presented. Also, the job selection algorithm was implemented in GSM/GPRS handset with ARM7 processor to see its effectiveness on embedded systems. The experiments performed on the system show that the proposed algorithm can further utilize the processor by reducing the scheduling overhead.

The stack resource policy (SRP) is a real-time synchronization protocol with some distinct properties. One of such properties is early blocking; the execution of a job is delayed instead of being blocked while requesting shared resources. If SRP is used in dynamic priority scheduling such as in the earliest deadline first (EDF), the early blocking requires that a scheduler should select the highest-priority job among the jobs that will not be blocked, incurring a runtime overhead. In this paper, we analyze the runtime overhead of EDF scheduling when SRP is used. We find out that if jobs share resources using SRP the overhead of selecting a job when using the conventional implementations of a ready queue becomes serious as the number of jobs increases. To solve this problem, we propose an alternative data structure for the ready queue and an algorithm that can significantly reduce the overhead. This paper also describes the design and implementation of a real-time layer that employs the proposed scheme in Linux.

Real-time scheduling on multiprocessor involves many complex issues. One of them is tie-breaking: the way how ties are broken among tasks with same priority. Unlike on uniprocessor, the feasibility of a task set on multiprocessor depends on a tie-breaking policy as well as on a scheduling algorithm. In this paper, we suggest and compare several tie-breaking policies for deadline-based schedule algorithms on multiprocessor. An effective tie-breaking policy for different scheduling algorithm is identified by simulation.