Search

Reducing job migrations is essential for any global multiprocessor scheduling algorithm. In this letter, we present a global, dynamic-priority, laxity-based algorithm that reduces the number of migrations on multiprocessor embedded systems by leveraging information theory principles. A simplification of the proposed scheduling theory is presented to reduce the overhead caused by using information theory. Our results show that the proposed algorithm is able to reduce the number of migrations by up to 41.21% when compared with other global, dynamic-priority, laxity-based algorithms. As the utilization per task set and the number of processors increase, simplified information-theoretic scheduling algorithm is able to improve its performance in terms of the number of migrations.

In this paper, we describe how Shannon's information theory is used to develop the Simplified Information-Theoretic Scheduling algorithm for Real-time Systems (SITSA-RT), and we explain the mechanism used by this algorithm to reduce the number of job migrations in real-time systems implemented in a multiprocessor platform. We present a performance comparison of the proposed algorithm with different multiprocessor scheduling algorithms for synthetic and real-case task sets. The results of the performance comparison for the synthetic task sets case show that outperforms all the studied EDF-based (up to 41.65%) and P-Fair based algorithms (up to 93.22%) in terms of the reduction of the number of job migrations while offering a similar performance in terms of the number of preemptions, the number of tasks migrations, and deadline miss ratio. These results show that as the utilization per task set and the number of processors increase, SITSA-RT is able to improve its performance in terms of the number of migrations. The results from the real-case task set based on NASA's X-38 avionics architecture show that for the scheduler execution time, MLLF improves the performance of SITSA-RT by 5.96% and SITSA-RT improves the performance of LLF by 19%, and from the memory requirements we found that MLLF usage is 13.48% lower than SITSA-RT, and SITSA-RT usage is 52.97% lower than LLF.

The purpose of this paper is to present a scheduling solution based on information theory principles to schedule real-time tasks. We propose the mathematical background for using information as a parameter in real-time systems as well as the relationship between information and utilization. We present a new dynamic priority scheduling solution that selects the task with the highest amount of information per studied interval. We propose the feasibility analysis of the scheduling solution and we compare its performance against the Earliest Deadline First (EDF) scheduling algorithm using as dependent variables the number of context switches and the number of preemptions. We generated 16 test files (with 100 synthetic task sets per file) using as independent variables: (a) Utilization (from 70% to 100%), (b) Number of tasks per Task set (from 2 to 5) and (c) Hyper-period (fixed at 40). The results showed that: (a) Our scheduling solution improves the performance of EDF by 1.1384% in terms of the number of context switches and 2.0428% in terms of the number of preemptions for the studied task sets; (b) The similarity ratio (number of similar schedules) between the two algorithms was 42.68%.

The purpose of this paper is to present the mathematical background for using entropy in real-time scheduling as well as the relationship between entropy and utilization. We present a new scheduling algorithm based on entropy to schedule tasks in real-time systems. The goal is to minimize the uncertainty of the scheduling problem by executing the task with the highest entropy first without missing any deadline. The uncertainty measurement is based on the probability of the execution of a task during the hyper-period. This study aims to present entropy as a new parameter that can be used by researchers in different real-time systems fields.