{"id":{"repo_id":"uiuc","oai_identifier":"oai:www.ideals.illinois.edu:2142/19091"},"canonical_url":"https://search.dev.ndltd.org/etd/uiuc/oai:www.ideals.illinois.edu:2142/19091","repository":{"repo_id":"uiuc","name":"University of Illinois - Urbana-Champaign","base_url":"https://www.ideals.illinois.edu/oai-pmh"},"display":{"title":"Scheduling hard real-time jobs that allow imprecise results","abstract":"One way to avoid timing faults in hard real-time systems is to use the imprecise computation approach. In this approach, an intermediate result of acceptable quality is used whenever a result of the desired quality cannot be produced before its deadline. This thesis discusses the problem of scheduling periodic jobs to meet deadlines on systems that support imprecise computations. In our workload models, each real-time task is logically decomposed into two parts: a mandatory part and an optional part. The mandatory part must be completed in order for the task to produce an acceptable result, and the optional part refines the result produced by the mandatory part to reduce the error in the result. The mandatory part has a hard deadline, and the optional part has a soft deadline. Our workload models differ from traditional models in that a task may be terminated due to time constraint at any time throughout its optional part. Depending on different kinds of undesirable effects of errors, jobs are classified as error-noncumulative or error-cumulative. For error-noncumulative jobs, the effects of errors in the results produced in different periods are not cumulative. The optional parts of the tasks never need to be completed. The result quality of each job is measured in terms of the average error in the results produced over several consecutive periods. A class of preemptive, priority-driven algorithms that lead to feasible schedules with small average error is described and evaluated. For error-cumulative jobs, the undesirable effects of errors produced in different periods are cumulative, making it necessary to complete the optional part at least once in several consecutive periods. A class of heuristic algorithms is designed to schedule the optimal parts. The performance of these algorithms is evaluated and the schedulability criteria are discussed.","abstract_html":"One way to avoid timing faults in hard real-time systems is to use the imprecise computation approach. In this approach, an intermediate result of acceptable quality is used whenever a result of the desired quality cannot be produced before its deadline. This thesis discusses the problem of scheduling periodic jobs to meet deadlines on systems that support imprecise computations. In our workload models, each real-time task is logically decomposed into two parts: a mandatory part and an optional part. The mandatory part must be completed in order for the task to produce an acceptable result, and the optional part refines the result produced by the mandatory part to reduce the error in the result. The mandatory part has a hard deadline, and the optional part has a soft deadline. Our workload models differ from traditional models in that a task may be terminated due to time constraint at any time throughout its optional part. Depending on different kinds of undesirable effects of errors, jobs are classified as error-noncumulative or error-cumulative. For error-noncumulative jobs, the effects of errors in the results produced in different periods are not cumulative. The optional parts of the tasks never need to be completed. The result quality of each job is measured in terms of the average error in the results produced over several consecutive periods. A class of preemptive, priority-driven algorithms that lead to feasible schedules with small average error is described and evaluated. For error-cumulative jobs, the undesirable effects of errors produced in different periods are cumulative, making it necessary to complete the optional part at least once in several consecutive periods. A class of heuristic algorithms is designed to schedule the optimal parts. The performance of these algorithms is evaluated and the schedulability criteria are discussed.","abstract_has_math":false,"creators":["Chung, Jen-Yao"],"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":2011,"date_issued":"2011-05-07T11:56:40Z","date_published":"2011-05-07T11:56:40Z","updated_at":"2026-07-22T22:25:12Z","subjects":["Operations Research","Computer Science"],"languages":["eng"],"rights":["Copyright 1989 Chung, Jen-Yao"],"rights_urls":[],"identifier_entries":[{"key":"dc:identifier","label":"Identifier","values":["AAI8924792","(UMI)AAI8924792"],"render_values":[{"text":"AAI8924792","href":null,"code":true},{"text":"(UMI)AAI8924792","href":null,"code":true}]}]},"links":{"outbound_url":"http://hdl.handle.net/2142/19091","outbound_label":"Handle","outbound_source":"dc:identifier"},"metadata_groups":[{"id":"people","label":"People","entries":[{"key":"dc:creator","label":"Author","values":["Chung, Jen-Yao"]}]},{"id":"academic_context","label":"Academic Context","entries":[{"key":"dc:date","label":"Dc Date","values":["2011-05-07T11:56:40Z","10000-01-01","1989"]},{"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":["Operations Research","Computer Science"]}]},{"id":"language_rights","label":"Language and Rights","entries":[{"key":"dc:language","label":"Dc Language","values":["eng"]},{"key":"dc:rights","label":"Dc Rights","values":["Copyright 1989 Chung, Jen-Yao"]}]},{"id":"identifiers","label":"Identifiers","entries":[{"key":"dc:identifier","label":"Identifier","values":["AAI8924792","(UMI)AAI8924792","http://hdl.handle.net/2142/19091"]}]},{"id":"additional","label":"Additional Metadata","entries":[{"key":"dc:description","label":"Description","values":["One way to avoid timing faults in hard real-time systems is to use the imprecise computation approach. In this approach, an intermediate result of acceptable quality is used whenever a result of the desired quality cannot be produced before its deadline. This thesis discusses the problem of scheduling periodic jobs to meet deadlines on systems that support imprecise computations. In our workload models, each real-time task is logically decomposed into two parts: a mandatory part and an optional part. The mandatory part must be completed in order for the task to produce an acceptable result, and the optional part refines the result produced by the mandatory part to reduce the error in the result. The mandatory part has a hard deadline, and the optional part has a soft deadline. Our workload models differ from traditional models in that a task may be terminated due to time constraint at any time throughout its optional part. Depending on different kinds of undesirable effects of errors, jobs are classified as error-noncumulative or error-cumulative. For error-noncumulative jobs, the effects of errors in the results produced in different periods are not cumulative. The optional parts of the tasks never need to be completed. The result quality of each job is measured in terms of the average error in the results produced over several consecutive periods. A class of preemptive, priority-driven algorithms that lead to feasible schedules with small average error is described and evaluated. For error-cumulative jobs, the undesirable effects of errors produced in different periods are cumulative, making it necessary to complete the optional part at least once in several consecutive periods. A class of heuristic algorithms is designed to schedule the optimal parts. The performance of these algorithms is evaluated and the schedulability criteria are discussed.","Made available in DSpace on 2011-05-07T11:56:40Z (GMT). No. of bitstreams: 2 license.txt: 4922 bytes, checksum: 910b249b4beec47e7ab768910c8f966f (MD5) 8924792.pdf: 3239747 bytes, checksum: 689447aff0723b91aa3ad9a433342a96 (MD5) Previous issue date: 1989","Item marked as restricted to the 'UIUC Users [automated]' Group (id=2) by Howard Ding (hding2@illinois.edu) on 2011-05-07T14:34:36Z Item is restricted indefinitely.","Restriction data tranferred 2014-07-01T11:13:18-05:00 Original Data Group with Access UIUC Users [automated] Release Date: none Reason: ETDs are only available to UIUC Users without author permission","ETDs are only available to UIUC Users without author permission","U of I Only"]},{"key":"dc:title","label":"Title","values":["Scheduling hard real-time jobs that allow imprecise results"]}]}],"canonical_facts":{"dc:creator":["Chung, Jen-Yao"],"dc:date":["2011-05-07T11:56:40Z","10000-01-01","1989"],"dc:description":["One way to avoid timing faults in hard real-time systems is to use the imprecise computation approach. In this approach, an intermediate result of acceptable quality is used whenever a result of the desired quality cannot be produced before its deadline. This thesis discusses the problem of scheduling periodic jobs to meet deadlines on systems that support imprecise computations. In our workload models, each real-time task is logically decomposed into two parts: a mandatory part and an optional part. The mandatory part must be completed in order for the task to produce an acceptable result, and the optional part refines the result produced by the mandatory part to reduce the error in the result. The mandatory part has a hard deadline, and the optional part has a soft deadline. Our workload models differ from traditional models in that a task may be terminated due to time constraint at any time throughout its optional part. Depending on different kinds of undesirable effects of errors, jobs are classified as error-noncumulative or error-cumulative. For error-noncumulative jobs, the effects of errors in the results produced in different periods are not cumulative. The optional parts of the tasks never need to be completed. The result quality of each job is measured in terms of the average error in the results produced over several consecutive periods. A class of preemptive, priority-driven algorithms that lead to feasible schedules with small average error is described and evaluated. For error-cumulative jobs, the undesirable effects of errors produced in different periods are cumulative, making it necessary to complete the optional part at least once in several consecutive periods. A class of heuristic algorithms is designed to schedule the optimal parts. The performance of these algorithms is evaluated and the schedulability criteria are discussed.","Made available in DSpace on 2011-05-07T11:56:40Z (GMT). No. of bitstreams: 2 license.txt: 4922 bytes, checksum: 910b249b4beec47e7ab768910c8f966f (MD5) 8924792.pdf: 3239747 bytes, checksum: 689447aff0723b91aa3ad9a433342a96 (MD5) Previous issue date: 1989","Item marked as restricted to the 'UIUC Users [automated]' Group (id=2) by Howard Ding (hding2@illinois.edu) on 2011-05-07T14:34:36Z Item is restricted indefinitely.","Restriction data tranferred 2014-07-01T11:13:18-05:00 Original Data Group with Access UIUC Users [automated] Release Date: none Reason: ETDs are only available to UIUC Users without author permission","ETDs are only available to UIUC Users without author permission","U of I Only"],"dc:identifier":["AAI8924792","(UMI)AAI8924792","http://hdl.handle.net/2142/19091"],"dc:language":["eng"],"dc:rights":["Copyright 1989 Chung, Jen-Yao"],"dc:subject":["Operations Research","Computer Science"],"dc:title":["Scheduling hard real-time jobs that allow imprecise results"],"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:25:12Z"}