In Partial Fulfillment of the Requirements for the Degree of Doctor of Philosophy

Carlos Alberto Rincon Castro

will defend his dissertation proposal

Real-Time Systems Scheduling and Information Theory: From Uniprocessors to Multiprocessors

Abstract

Since Claude Shannon presented the definition of information and entropy in 1948, different science fields have used this theoretical background to represent the uncertainty of a system. For real-time systems, task scheduling is one of the most studied topics due to the constraint that all the tasks in the system have of meeting their deadlines. In this work, the foundation for using these definitions from information theory in real-time systems scheduling is presented as well as different scheduling solutions based on the proposed theory, for both uniprocessor and multiprocessor systems.

For uniprocessor systems, the Information Theory based Scheduling Solution for Real-time Systems (ITS-RT) and the Highest Task Density First scheduling algorithm (HTDF) are presented. The performance comparison of these solutions with the Earliest Deadline First scheduling algorithm (EDF) shows a minimal improvement of the proposed solutions over EDF in terms of the number of context switches and number of scheduler calls. For multiprocessor systems, the Information- Theoretic Scheduling Algorithm for Real-time systems (ITSA-RT) and its simplification based on the laxity of the task, the Simplified Information-Theoretic Scheduling Algorithm for Real-time system (SITSA-RT) are presented. When compared with other global, dynamic-priority, laxity-based algorithms, SITSA-RT performance analysis shows a reduction of up to 41.21% and 15.59% in the number of job migrations and the number of preemptions respectively, while producing a similar number of scheduler calls.

These results show the potential of using the definitions of information and entropy for real-time system scheduling, especially for the multiprocessor case where reducing the number of job migrations is the primary problem that researchers need to solve when designing global algorithms to schedule real-time tasks in multiprocessor systems.

As future work, a comparison between SITSA-RT and the state of the art real-time multiprocessor scheduling algorithms will be performed, measuring the number of job migrations, the number of preemptions, the number of scheduler calls, and the number of missed deadlines. Additionally, the execution time and memory usage of SITSA-RT will be analyzed to measure the computational cost of implementing the algorithm on a real-time system using WindRiver Workbench. Finally, a new technique based on entropy minimization will be introduced to reduce the number of task migrations in real-time systems implemented on multiprocessor platforms.

Date: Monday, November 27, 2017
Time: 10:30 AM
Place: PGH 550
Advisors: Dr. Albert M. K. Cheng

Faculty, students, and the general public are invited.