{"id":{"repo_id":"houston","oai_identifier":"oai:uh-ir.tdl.org:10657/3990"},"canonical_url":"https://search.dev.ndltd.org/etd/houston/oai:uh-ir.tdl.org:10657/3990","repository":{"repo_id":"houston","name":"University of Houston","base_url":"https://uh-ir.tdl.org/server/oai/request"},"display":{"title":"Real-time System 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, 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.","abstract_html":"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.","abstract_has_math":false,"creators":["Rincon, Carlos Alberto 1976-"],"institution":"University of Houston","degree_name":"Doctor of Philosophy","degree_level":"Doctoral","degree_discipline":"Computer Science","degree_department":null,"school":null,"contributors":[],"advisors":["Cheng, Albert M. K."],"committee_chairs":[],"committee_members":["Pâris, Jehan-François","Tsekos, Nikolaos V.","Chen, Ji"],"year":2018,"date_issued":"2018-08","date_published":"2018-08","updated_at":"2026-07-24T02:32:44Z","subjects":["Information Theory","Real-time systems","Scheduling","Uniprocessors","Multiprocessor systems"],"languages":["eng"],"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)."],"rights_urls":[],"identifier_entries":[]},"links":{"outbound_url":"https://hdl.handle.net/10657/3990","outbound_label":"Handle","outbound_source":"dc:identifier.uri"},"metadata_groups":[{"id":"people","label":"People","entries":[{"key":"dc:contributor.advisor","label":"Advisor","values":["Cheng, Albert M. K."]},{"key":"dc:contributor.committeemember","label":"Committee Member","values":["Pâris, Jehan-François","Tsekos, Nikolaos V.","Chen, Ji"]},{"key":"dc:creator","label":"Author","values":["Rincon, Carlos Alberto 1976-"]}]},{"id":"academic_context","label":"Academic Context","entries":[{"key":"dc:date.accessioned","label":"Dc Date Accessioned","values":["2019-05-23T14:17:27Z"]},{"key":"dc:date.issued","label":"Date","values":["2018-08"]},{"key":"thesis:degree_discipline","label":"Discipline","values":["Computer Science"]},{"key":"thesis:degree_level","label":"Degree Level","values":["Doctoral"]},{"key":"thesis:degree_name","label":"Degree Name","values":["Doctor of Philosophy"]},{"key":"thesis:institution_name","label":"Thesis Institution Name","values":["University of Houston"]}]},{"id":"subjects_keywords","label":"Subjects and Keywords","entries":[{"key":"dc:subject","label":"Dc Subject","values":["Information Theory","Real-time systems","Scheduling","Uniprocessors","Multiprocessor systems"]}]},{"id":"language_rights","label":"Language and Rights","entries":[{"key":"dc:language.iso","label":"Language (ISO)","values":["eng"]},{"key":"dc:rights","label":"Dc Rights","values":["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)."]}]},{"id":"identifiers","label":"Identifiers","entries":[{"key":"dc:identifier.uri","label":"Identifier URI","values":["https://hdl.handle.net/10657/3990"]}]},{"id":"additional","label":"Additional Metadata","entries":[{"key":"dc:description.abstract","label":"Abstract","values":["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."]},{"key":"dc:format.mimetype","label":"Dc Format Mimetype","values":["application/pdf"]},{"key":"dc:title","label":"Title","values":["Real-time System Scheduling and Information Theory: From Uniprocessors to Multiprocessors"]}]}],"canonical_facts":{"dc:contributor.advisor":["Cheng, Albert M. K."],"dc:contributor.committeemember":["Pâris, Jehan-François","Tsekos, Nikolaos V.","Chen, Ji"],"dc:creator":["Rincon, Carlos Alberto 1976-"],"dc:date.accessioned":["2019-05-23T14:17:27Z"],"dc:date.issued":["2018-08"],"dc:description.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, 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."],"dc:format.mimetype":["application/pdf"],"dc:identifier.uri":["https://hdl.handle.net/10657/3990"],"dc:language.iso":["eng"],"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)."],"dc:subject":["Information Theory","Real-time systems","Scheduling","Uniprocessors","Multiprocessor systems"],"dc:title":["Real-time System Scheduling and Information Theory: From Uniprocessors to Multiprocessors"],"thesis:degree_discipline":["Computer Science"],"thesis:degree_level":["Doctoral"],"thesis:degree_name":["Doctor of Philosophy"],"thesis:institution_name":["University of Houston"]},"updated_at":"2026-07-24T02:32:44Z"}