{"id":{"repo_id":"uiuc","oai_identifier":"oai:www.ideals.illinois.edu:2142/72088"},"canonical_url":"https://search.dev.ndltd.org/etd/uiuc/oai:www.ideals.illinois.edu:2142/72088","repository":{"repo_id":"uiuc","name":"University of Illinois - Urbana-Champaign","base_url":"https://www.ideals.illinois.edu/oai-pmh"},"display":{"title":"Scheduling in Real-Time Systems to Ensure Graceful Degradation: The Imprecise-Computation and the Deferred-Deadline Approaches","abstract":"When a real-time system becomes overloaded, we want the system to degrade in a graceful, predictable manner. Imprecise computations and deferred deadlines are two approaches to provide this graceful, predictable degradation.","abstract_html":"When a real-time system becomes overloaded, we want the system to degrade in a graceful, predictable manner. Imprecise computations and deferred deadlines are two approaches to provide this graceful, predictable degradation.","abstract_has_math":false,"creators":["Shih, Wei-Kuan"],"institution":"University of Illinois at Urbana-Champaign","degree_name":"Ph.D.","degree_level":"Dissertation","degree_discipline":"Computer Science","degree_department":null,"school":null,"contributors":[],"advisors":[],"committee_chairs":[],"committee_members":[],"year":2014,"date_issued":"2014-12-17T20:00:41Z","date_published":"2014-12-17T20:00:41Z","updated_at":"2026-07-22T22:26:06Z","subjects":["Computer Science"],"languages":[],"rights":[],"rights_urls":[],"identifier_entries":[{"key":"dc:identifier","label":"Identifier","values":["(UMI)AAI9329162"],"render_values":[{"text":"(UMI)AAI9329162","href":null,"code":true}]}]},"links":{"outbound_url":"http://hdl.handle.net/2142/72088","outbound_label":"Handle","outbound_source":"dc:identifier"},"metadata_groups":[{"id":"people","label":"People","entries":[{"key":"dc:creator","label":"Author","values":["Shih, Wei-Kuan"]}]},{"id":"academic_context","label":"Academic Context","entries":[{"key":"dc:date","label":"Dc Date","values":["2014-12-17T20:00:41Z","10000-01-01","1993"]},{"key":"dc:type","label":"Dc Type","values":["text"]},{"key":"thesis:degree_discipline","label":"Discipline","values":["Computer Science"]},{"key":"thesis:degree_level","label":"Degree Level","values":["Dissertation"]},{"key":"thesis:degree_name","label":"Degree Name","values":["Ph.D."]},{"key":"thesis:institution_name","label":"Thesis Institution Name","values":["University of Illinois at Urbana-Champaign"]}]},{"id":"subjects_keywords","label":"Subjects and Keywords","entries":[{"key":"dc:subject","label":"Dc Subject","values":["Computer Science"]}]},{"id":"identifiers","label":"Identifiers","entries":[{"key":"dc:identifier","label":"Identifier","values":["http://hdl.handle.net/2142/72088","(UMI)AAI9329162"]}]},{"id":"additional","label":"Additional Metadata","entries":[{"key":"dc:description","label":"Description","values":["When a real-time system becomes overloaded, we want the system to degrade in a graceful, predictable manner. Imprecise computations and deferred deadlines are two approaches to provide this graceful, predictable degradation.","This thesis describes efficient algorithms for scheduling tasks in systems based on these two approaches. The first part is concerned with problems of scheduling imprecise computations. In the imprecise computation model, each task is logically decomposed into a mandatory subtask and an optional subtask. The mandatory subtask must be executed to completion in order to produce an acceptable result. The optional subtask begins after the mandatory subtask is completed and can be left incompleted. The error in the result of a task is equal to the processing time of the unexecuted portion of the optional subtask. We want to schedule these tasks to meet two objectives: (1) the mandatory subtasks of all tasks complete by their deadlines whenever it is feasible to do so; (2) the optional subtasks are completed as much as possible so that overall result quality is optimized. The algorithms described in the first part are for the preemptive scheduling, on a uniprocessor system, of dependent tasks with rational ready times, deadlines and processing times. Some can handle tasks with different weights. Among the algorithms are the optimal ones for different performance measures used to quantify the overall result quality.","The second part of this thesis is concerned with the problems of scheduling periodic tasks with deferred deadlines. The deferred-deadline approach to graceful degradation is to ensure that the lateness of all tasks is acceptably small during an overload. We describe a semi-static, priority-driven algorithm, called the modified rate-monotone algorithm, for scheduling periodic tasks with deferred deadlines. When some periodic tasks are considered to be urgent because their deadlines cannot be deferred, we can schedule the urgent tasks by the well-known rate-monotone algorithm and the tasks with deferred deadlines by the modified rate-monotone algorithm. The performance of this hybrid strategy for scheduling mixed task sets of urgent tasks and tasks with deferred deadlines is discussed. (Abstract shortened by UMI.)","Made available in DSpace on 2014-12-17T20:00:41Z (GMT). No. of bitstreams: 1 9329162.pdf: 5398564 bytes, checksum: 9552a8c59a13479cf4f72f62d754ee56 (MD5) Previous issue date: 1993","Embargo set by: Seth Robbins for item 72256 Lift date: Forever Reason: Restricted to the U of I community idenfinitely during batch ingest of legacy ETDs","Restricted to the U of I community idenfinitely during batch ingest of legacy ETDs","U of I Only","140 p.","Thesis (Ph.D.)--University of Illinois at Urbana-Champaign, 1993."]},{"key":"dc:title","label":"Title","values":["Scheduling in Real-Time Systems to Ensure Graceful Degradation: The Imprecise-Computation and the Deferred-Deadline Approaches"]}]}],"canonical_facts":{"dc:creator":["Shih, Wei-Kuan"],"dc:date":["2014-12-17T20:00:41Z","10000-01-01","1993"],"dc:description":["When a real-time system becomes overloaded, we want the system to degrade in a graceful, predictable manner. Imprecise computations and deferred deadlines are two approaches to provide this graceful, predictable degradation.","This thesis describes efficient algorithms for scheduling tasks in systems based on these two approaches. The first part is concerned with problems of scheduling imprecise computations. In the imprecise computation model, each task is logically decomposed into a mandatory subtask and an optional subtask. The mandatory subtask must be executed to completion in order to produce an acceptable result. The optional subtask begins after the mandatory subtask is completed and can be left incompleted. The error in the result of a task is equal to the processing time of the unexecuted portion of the optional subtask. We want to schedule these tasks to meet two objectives: (1) the mandatory subtasks of all tasks complete by their deadlines whenever it is feasible to do so; (2) the optional subtasks are completed as much as possible so that overall result quality is optimized. The algorithms described in the first part are for the preemptive scheduling, on a uniprocessor system, of dependent tasks with rational ready times, deadlines and processing times. Some can handle tasks with different weights. Among the algorithms are the optimal ones for different performance measures used to quantify the overall result quality.","The second part of this thesis is concerned with the problems of scheduling periodic tasks with deferred deadlines. The deferred-deadline approach to graceful degradation is to ensure that the lateness of all tasks is acceptably small during an overload. We describe a semi-static, priority-driven algorithm, called the modified rate-monotone algorithm, for scheduling periodic tasks with deferred deadlines. When some periodic tasks are considered to be urgent because their deadlines cannot be deferred, we can schedule the urgent tasks by the well-known rate-monotone algorithm and the tasks with deferred deadlines by the modified rate-monotone algorithm. The performance of this hybrid strategy for scheduling mixed task sets of urgent tasks and tasks with deferred deadlines is discussed. (Abstract shortened by UMI.)","Made available in DSpace on 2014-12-17T20:00:41Z (GMT). No. of bitstreams: 1 9329162.pdf: 5398564 bytes, checksum: 9552a8c59a13479cf4f72f62d754ee56 (MD5) Previous issue date: 1993","Embargo set by: Seth Robbins for item 72256 Lift date: Forever Reason: Restricted to the U of I community idenfinitely during batch ingest of legacy ETDs","Restricted to the U of I community idenfinitely during batch ingest of legacy ETDs","U of I Only","140 p.","Thesis (Ph.D.)--University of Illinois at Urbana-Champaign, 1993."],"dc:identifier":["http://hdl.handle.net/2142/72088","(UMI)AAI9329162"],"dc:subject":["Computer Science"],"dc:title":["Scheduling in Real-Time Systems to Ensure Graceful Degradation: The Imprecise-Computation and the Deferred-Deadline Approaches"],"dc:type":["text"],"thesis:degree_discipline":["Computer Science"],"thesis:degree_level":["Dissertation"],"thesis:degree_name":["Ph.D."],"thesis:institution_name":["University of Illinois at Urbana-Champaign"]},"updated_at":"2026-07-22T22:26:06Z"}