Real-time System Scheduling and Information Theory: From Uniprocessors to Multiprocessors

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, we present the foundation for using these definitions from information theory in real-time system scheduling as well as different scheduling solutions based on the proposed theory, for both uniprocessor and multiprocessor systems. For uniprocessor systems, we proposed the Information Theory based Scheduling Solution for Real-time Systems (ITS-RT) and the Highest Task Density First scheduling algorithm (HTDF). 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 the number of scheduler calls. For multiprocessor systems, we presented 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 systems (SITSA-RT). When compared with other global, dynamic-priority algorithms, SITSA-RT significantly reduces the number of job migrations (up to 41.65% when compared against the selected EDF-based algorithms, and up to 93.22% when compared against the selected PFair-based algorithms). We also introduced the theoretical analysis and the implementation aspects of the Entropy-based scheduling mechanism to reduce task migrations in real-time systems. The performance analysis of this additional scheduling layer combined with global EDF shows a reduction in the number of task migrations by up to 49.66% while generating a similar number of job migrations when compared against global EDF. 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.

Name thesis:degree_name

Doctor of Philosophy

Level thesis:degree_level

Doctoral

Discipline thesis:degree_discipline

Computer Science

Grantor

University of Houston

Year dc:date.issued

2018

Author dc:creator

• Rincon, Carlos Alberto 1976-

Advisor dc:contributor.advisor

• Cheng, Albert M. K.

Committee members dc:contributor.committeemember

• Pâris, Jehan-François
• Tsekos, Nikolaos V.
• Chen, Ji

• Information Theory
• Real-time systems
• Scheduling
• Uniprocessors
• Multiprocessor systems

Statement dc:rights

• The author of this work is the copyright owner. UH Libraries and the Texas Digital Library have their permission to store and provide access to this work. Further transmission, reproduction, or presentation of this work is prohibited except with permission of the author(s).

Language dc:language.iso

eng

Handle dc:identifier.uri

https://hdl.handle.net/10657/3990

OAI identifier oai:identifier

oai:uh-ir.tdl.org:10657/3990