{"id":{"repo_id":"uiuc","oai_identifier":"oai:www.ideals.illinois.edu:2142/72063"},"canonical_url":"https://search.dev.ndltd.org/etd/uiuc/oai:www.ideals.illinois.edu:2142/72063","repository":{"repo_id":"uiuc","name":"University of Illinois - Urbana-Champaign","base_url":"https://www.ideals.illinois.edu/oai-pmh"},"display":{"title":"Scheduling Imprecise Hard Real-Time Jobs With Cumulative Error","abstract":"The imprecise computation approach is a way to satisfy all timing constraints and provide graceful degradation more easily during transient overloads in hard real-time systems. The basic idea of this approach is to trade precision for timeliness. In this approach, each task is divided logically into two subtasks: a mandatory subtask that produces a rough but acceptable result and an optional subtask that refines the rough result. The mandatory subtask must be completed by the deadline of the task for the task to produce an acceptable and usable result. The optional subtask can be left unfinished if necessary. When a transient overload occurs, the scheduler can discard the optional subtasks if they are not completed by their deadlines. Errors result from the early terminations of tasks. For some applications, the error in the result generated by an unfinished optional subtask has a cumulative effect on the results generated by the later tasks of the same periodic job. For each job of this type, there is a maximum threshold of cumulated error. When the cumulated error of the results produced in a number of periods exceeds the maximum threshold, the result is no longer considered to be correct. The focus of this thesis is on the problem of scheduling imprecise hard real-time jobs with cumulative error. A class of heuristic algorithms is proposed to schedule jobs such that the cumulated error of the results produced by each job will not exceed the maximum threshold. The proposed algorithms are evaluated using different transient overload workload models for a number of job sets with different characteristics. The results of this evaluation are presented and discussed in this thesis.","abstract_html":"The imprecise computation approach is a way to satisfy all timing constraints and provide graceful degradation more easily during transient overloads in hard real-time systems. The basic idea of this approach is to trade precision for timeliness. In this approach, each task is divided logically into two subtasks: a mandatory subtask that produces a rough but acceptable result and an optional subtask that refines the rough result. The mandatory subtask must be completed by the deadline of the task for the task to produce an acceptable and usable result. The optional subtask can be left unfinished if necessary. When a transient overload occurs, the scheduler can discard the optional subtasks if they are not completed by their deadlines. Errors result from the early terminations of tasks. For some applications, the error in the result generated by an unfinished optional subtask has a cumulative effect on the results generated by the later tasks of the same periodic job. For each job of this type, there is a maximum threshold of cumulated error. When the cumulated error of the results produced in a number of periods exceeds the maximum threshold, the result is no longer considered to be correct. The focus of this thesis is on the problem of scheduling imprecise hard real-time jobs with cumulative error. A class of heuristic algorithms is proposed to schedule jobs such that the cumulated error of the results produced by each job will not exceed the maximum threshold. The proposed algorithms are evaluated using different transient overload workload models for a number of job sets with different characteristics. The results of this evaluation are presented and discussed in this thesis.","abstract_has_math":false,"creators":["Cheong, Infan Kuok"],"institution":"University of Illinois at Urbana-Champaign","degree_name":"Ph.D.","degree_level":"Dissertation","degree_discipline":"Computer Science","degree_department":null,"school":null,"contributors":["Liu, Jane W.S."],"advisors":[],"committee_chairs":[],"committee_members":[],"year":2014,"date_issued":"2014-12-17T20:00:22Z","date_published":"2014-12-17T20:00:22Z","updated_at":"2026-07-22T22:26:06Z","subjects":["Computer Science"],"languages":[],"rights":[],"rights_urls":[],"identifier_entries":[{"key":"dc:identifier","label":"Identifier","values":["(UMI)AAI9305490"],"render_values":[{"text":"(UMI)AAI9305490","href":null,"code":true}]}]},"links":{"outbound_url":"http://hdl.handle.net/2142/72063","outbound_label":"Handle","outbound_source":"dc:identifier"},"metadata_groups":[{"id":"people","label":"People","entries":[{"key":"dc:contributor","label":"Contributor","values":["Liu, Jane W.S."]},{"key":"dc:creator","label":"Author","values":["Cheong, Infan Kuok"]}]},{"id":"academic_context","label":"Academic Context","entries":[{"key":"dc:date","label":"Dc Date","values":["2014-12-17T20:00:22Z","10000-01-01","1992"]},{"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/72063","(UMI)AAI9305490"]}]},{"id":"additional","label":"Additional Metadata","entries":[{"key":"dc:description","label":"Description","values":["The imprecise computation approach is a way to satisfy all timing constraints and provide graceful degradation more easily during transient overloads in hard real-time systems. The basic idea of this approach is to trade precision for timeliness. In this approach, each task is divided logically into two subtasks: a mandatory subtask that produces a rough but acceptable result and an optional subtask that refines the rough result. The mandatory subtask must be completed by the deadline of the task for the task to produce an acceptable and usable result. The optional subtask can be left unfinished if necessary. When a transient overload occurs, the scheduler can discard the optional subtasks if they are not completed by their deadlines. Errors result from the early terminations of tasks. For some applications, the error in the result generated by an unfinished optional subtask has a cumulative effect on the results generated by the later tasks of the same periodic job. For each job of this type, there is a maximum threshold of cumulated error. When the cumulated error of the results produced in a number of periods exceeds the maximum threshold, the result is no longer considered to be correct. The focus of this thesis is on the problem of scheduling imprecise hard real-time jobs with cumulative error. A class of heuristic algorithms is proposed to schedule jobs such that the cumulated error of the results produced by each job will not exceed the maximum threshold. The proposed algorithms are evaluated using different transient overload workload models for a number of job sets with different characteristics. The results of this evaluation are presented and discussed in this thesis.","Made available in DSpace on 2014-12-17T20:00:22Z (GMT). No. of bitstreams: 1 9305490.pdf: 6170941 bytes, checksum: 6c21295407396e9197fcaab800fc787b (MD5) Previous issue date: 1992","Embargo set by: Seth Robbins for item 72231 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","169 p.","Thesis (Ph.D.)--University of Illinois at Urbana-Champaign, 1992."]},{"key":"dc:title","label":"Title","values":["Scheduling Imprecise Hard Real-Time Jobs With Cumulative Error"]}]}],"canonical_facts":{"dc:contributor":["Liu, Jane W.S."],"dc:creator":["Cheong, Infan Kuok"],"dc:date":["2014-12-17T20:00:22Z","10000-01-01","1992"],"dc:description":["The imprecise computation approach is a way to satisfy all timing constraints and provide graceful degradation more easily during transient overloads in hard real-time systems. The basic idea of this approach is to trade precision for timeliness. In this approach, each task is divided logically into two subtasks: a mandatory subtask that produces a rough but acceptable result and an optional subtask that refines the rough result. The mandatory subtask must be completed by the deadline of the task for the task to produce an acceptable and usable result. The optional subtask can be left unfinished if necessary. When a transient overload occurs, the scheduler can discard the optional subtasks if they are not completed by their deadlines. Errors result from the early terminations of tasks. For some applications, the error in the result generated by an unfinished optional subtask has a cumulative effect on the results generated by the later tasks of the same periodic job. For each job of this type, there is a maximum threshold of cumulated error. When the cumulated error of the results produced in a number of periods exceeds the maximum threshold, the result is no longer considered to be correct. The focus of this thesis is on the problem of scheduling imprecise hard real-time jobs with cumulative error. A class of heuristic algorithms is proposed to schedule jobs such that the cumulated error of the results produced by each job will not exceed the maximum threshold. The proposed algorithms are evaluated using different transient overload workload models for a number of job sets with different characteristics. The results of this evaluation are presented and discussed in this thesis.","Made available in DSpace on 2014-12-17T20:00:22Z (GMT). No. of bitstreams: 1 9305490.pdf: 6170941 bytes, checksum: 6c21295407396e9197fcaab800fc787b (MD5) Previous issue date: 1992","Embargo set by: Seth Robbins for item 72231 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","169 p.","Thesis (Ph.D.)--University of Illinois at Urbana-Champaign, 1992."],"dc:identifier":["http://hdl.handle.net/2142/72063","(UMI)AAI9305490"],"dc:subject":["Computer Science"],"dc:title":["Scheduling Imprecise Hard Real-Time Jobs With Cumulative Error"],"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"}