The proposed scheduling scheme minimizes the mean power consumption of real-time tasks with probabilistic computation amounts while meeting their deadlines. Our study formally solves the minimization problem under finitely discrete clock frequencies with irregular power consumptions, whereas state-of-the-arts studies did under infinitely continuous clock frequencies with regular power consumptions.

The proposed scheduling scheme minimizes the energy consumption of a real-time task on the multi-core processor with the dynamic voltage and frequency scaling capability. The scheme allocates a pertinent number of cores to the task execution, inactivates unused cores, and assigns the lowest frequency meeting the deadline. For a periodic real-time task with consecutive real-time instances, the scheme prepares the minimum-energy solutions for all input cases at off-line time, and applies one of the prepared solutions to each real-time instance at runtime.

The proposed scheduling scheme minimizes the mean energy consumption of a real-time parallel task, where the task has the probabilistic computation amount and can be executed concurrently on multiple cores. The scheme determines a pertinent number of cores allocated to the task execution and the instant frequency supplied to the allocated cores. Evaluation shows that the scheme saves manifest amount of the energy consumed by the previous method minimizing the mean energy consumption on a single core.

We propose a polynomial-time algorithm for the scheduling of real-time parallel tasks on multicore processors. The proposed algorithm always finds a feasible schedule using the minimum number of processing cores, where tasks have properties of linear speedup, flexible preemption, arbitrary deadlines and arrivals, and parallelism bound. The time complexity of the proposed algorithm is O(M3log N) for M tasks and N processors in the worst case.

Viable techniques such as dynamic voltage scaling (DVS) provide a new design technique to balance system performance and energy saving. In this paper, we extend previous works on task assignment problems for a set of linear-pipeline tasks over a set of processors. Different from previous works, we revisit the problems with two additional system factors: deadline and energy-consumption, which are key factors in real-time and power-aware computation. We propose an O(nm2) time complexity algorithm to determine optimal task-assignment and speed-setting schemes leading to minimal energy consumption, for a given set of m real-time tasks running on n identical processors (with or without DVS supports). The same result can be extended to a restricted form of heterogeneous processor model. Meanwhile, we show that on homogeneous processor model more efficient algorithms can be applied and result in time complexity of O(m2) when m ≤ n. For completeness, we also discuss cases without contiguity constraints. We show under such cases the problems become at least as hard as NP-hard.

In recent years, there has been a rapid and widespread proliferation of non-traditional embedded computing platforms such as digital camcorders, cellular phones, and portable medical devices. As applications become increasingly sophisticated and processing power increases, the application designer has to rely on the services provided by the real-time operating systems (RTOSs). These RTOSs must not only provide predictable services but must also be efficient and small in size. Kernel services should also be deterministic by specifying how long each service call will take to execute. Having this information allows the application designers to better plan their real-time application software so as not to miss the deadline of each task. In this paper, we propose a generalized deterministic scheduling algorithm that makes the task scheduling time constant irrespective of the number of tasks created in an application. The proposed algorithm eliminates the restriction on the maximum number of task priorities imposed on the existing ones, without additional memory overhead.

The problem of non-preemptive scheduling of real-time periodic tasks with specified release times on a uniprocessor system is known as NP-hard problem. In this paper we propose a new non-preemptive scheduling algorithm and a new static scheduling strategy which use the repetitiveness and the predictability of periodic tasks in order to improve schedulabilities of real-time periodic tasks with specified release times. The proposed scheduling algorithm schedules periodic tasks by using the heuristic that precalculates if the scheduling of the selected task leads to the case that a task misses a deadline when tasks are scheduled by the non-preemptive EDF algorithm. If so, it defers the scheduling of the selected task to avoid the precalculated deadline-missing. Otherwise, it schedules the selected task in the same way as the non-preemptive EDF algorithm. Our scheduling algorithm can always find a feasible schedule for the set of periodic tasks with specified release times which is schedulable by the non-preemptive EDF algorithm. Our static sheduling strategy transforms the problem of non-preemptive scheduling for periodic tasks with specified release times into one with same release times for all tasks. It suggests dividing the given problem into two subproblems, making a non-preemptive scheduling algorithm to find two feasible subschedules for the two subproblems in the forward or backward scheduling within specific time intervals, and then combining the two feasible subschedules into a complete feasible schedule for the given problem. We present the release times as a function of periods for the efficient problem division. Finally, we show improvements of schedulabilities of our scheduling algorithm and scheduling strategy by simulation results.