{"id":{"repo_id":"uiuc","oai_identifier":"oai:www.ideals.illinois.edu:2142/23695"},"canonical_url":"https://search.dev.ndltd.org/etd/uiuc/oai:www.ideals.illinois.edu:2142/23695","repository":{"repo_id":"uiuc","name":"University of Illinois - Urbana-Champaign","base_url":"https://www.ideals.illinois.edu/oai-pmh"},"display":{"title":"Validating timing constraints in multiprocessor and distributed systems","abstract":"In multiprocessor and distributed real-time systems, scheduling jobs dynamically on processors is likely to achieve better performance. However, analytical and efficient validation methods for determining whether all the timing constraints are met do not yet exist for systems using modern dynamic scheduling strategies, and exhaustive methods are often infeasible or unreliable since the execution time and release time of each job may vary. In this thesis, we present solutions to the problem of how to validate systems in which jobs have arbitrary timing constraints and variable execution times and are scheduled on processors dynamically in a priority-driven manner. We begin by considering the simplest case of this problem where jobs are independent and processors are identical. We then generalize the validation problem to deal with the case where the processors are heterogeneous and the jobs are dependent. For each case we present conditions under which the jobs execute in a predictable manner, i.e., the completion times of jobs are no later when the execution times of some jobs decrease. We also present algorithms and bounds with which the latest completion times of all jobs can be bounded.","abstract_html":"In multiprocessor and distributed real-time systems, scheduling jobs dynamically on processors is likely to achieve better performance. However, analytical and efficient validation methods for determining whether all the timing constraints are met do not yet exist for systems using modern dynamic scheduling strategies, and exhaustive methods are often infeasible or unreliable since the execution time and release time of each job may vary. In this thesis, we present solutions to the problem of how to validate systems in which jobs have arbitrary timing constraints and variable execution times and are scheduled on processors dynamically in a priority-driven manner. We begin by considering the simplest case of this problem where jobs are independent and processors are identical. We then generalize the validation problem to deal with the case where the processors are heterogeneous and the jobs are dependent. For each case we present conditions under which the jobs execute in a predictable manner, i.e., the completion times of jobs are no later when the execution times of some jobs decrease. We also present algorithms and bounds with which the latest completion times of all jobs can be bounded.","abstract_has_math":false,"creators":["Ha, Rhan"],"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":2011,"date_issued":"2011-05-07T14:23:37Z","date_published":"2011-05-07T14:23:37Z","updated_at":"2026-07-22T22:25:22Z","subjects":["Computer Science"],"languages":["eng"],"rights":["Copyright 1995 Ha, Rhan"],"rights_urls":[],"identifier_entries":[{"key":"dc:identifier","label":"Identifier","values":["AAI9543600","(UMI)AAI9543600"],"render_values":[{"text":"AAI9543600","href":null,"code":true},{"text":"(UMI)AAI9543600","href":null,"code":true}]}]},"links":{"outbound_url":"http://hdl.handle.net/2142/23695","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":["Ha, Rhan"]}]},{"id":"academic_context","label":"Academic Context","entries":[{"key":"dc:date","label":"Dc Date","values":["2011-05-07T14:23:37Z","10000-01-01","1995"]},{"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":"language_rights","label":"Language and Rights","entries":[{"key":"dc:language","label":"Dc Language","values":["eng"]},{"key":"dc:rights","label":"Dc Rights","values":["Copyright 1995 Ha, Rhan"]}]},{"id":"identifiers","label":"Identifiers","entries":[{"key":"dc:identifier","label":"Identifier","values":["AAI9543600","(UMI)AAI9543600","http://hdl.handle.net/2142/23695"]}]},{"id":"additional","label":"Additional Metadata","entries":[{"key":"dc:description","label":"Description","values":["In multiprocessor and distributed real-time systems, scheduling jobs dynamically on processors is likely to achieve better performance. However, analytical and efficient validation methods for determining whether all the timing constraints are met do not yet exist for systems using modern dynamic scheduling strategies, and exhaustive methods are often infeasible or unreliable since the execution time and release time of each job may vary. In this thesis, we present solutions to the problem of how to validate systems in which jobs have arbitrary timing constraints and variable execution times and are scheduled on processors dynamically in a priority-driven manner. We begin by considering the simplest case of this problem where jobs are independent and processors are identical. We then generalize the validation problem to deal with the case where the processors are heterogeneous and the jobs are dependent. For each case we present conditions under which the jobs execute in a predictable manner, i.e., the completion times of jobs are no later when the execution times of some jobs decrease. We also present algorithms and bounds with which the latest completion times of all jobs can be bounded.","Made available in DSpace on 2011-05-07T14:23:37Z (GMT). No. of bitstreams: 2 license.txt: 4922 bytes, checksum: 910b249b4beec47e7ab768910c8f966f (MD5) 9543600.pdf: 5209490 bytes, checksum: 15c75233252be713dfef960865b2abba (MD5) Previous issue date: 1995","Item marked as restricted to the 'UIUC Users [automated]' Group (id=2) by Howard Ding (hding2@illinois.edu) on 2011-05-07T15:06:13Z Item is restricted indefinitely.","Restriction data tranferred 2014-07-01T11:31:46-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":["Validating timing constraints in multiprocessor and distributed systems"]}]}],"canonical_facts":{"dc:contributor":["Liu, Jane W.S."],"dc:creator":["Ha, Rhan"],"dc:date":["2011-05-07T14:23:37Z","10000-01-01","1995"],"dc:description":["In multiprocessor and distributed real-time systems, scheduling jobs dynamically on processors is likely to achieve better performance. However, analytical and efficient validation methods for determining whether all the timing constraints are met do not yet exist for systems using modern dynamic scheduling strategies, and exhaustive methods are often infeasible or unreliable since the execution time and release time of each job may vary. In this thesis, we present solutions to the problem of how to validate systems in which jobs have arbitrary timing constraints and variable execution times and are scheduled on processors dynamically in a priority-driven manner. We begin by considering the simplest case of this problem where jobs are independent and processors are identical. We then generalize the validation problem to deal with the case where the processors are heterogeneous and the jobs are dependent. For each case we present conditions under which the jobs execute in a predictable manner, i.e., the completion times of jobs are no later when the execution times of some jobs decrease. We also present algorithms and bounds with which the latest completion times of all jobs can be bounded.","Made available in DSpace on 2011-05-07T14:23:37Z (GMT). No. of bitstreams: 2 license.txt: 4922 bytes, checksum: 910b249b4beec47e7ab768910c8f966f (MD5) 9543600.pdf: 5209490 bytes, checksum: 15c75233252be713dfef960865b2abba (MD5) Previous issue date: 1995","Item marked as restricted to the 'UIUC Users [automated]' Group (id=2) by Howard Ding (hding2@illinois.edu) on 2011-05-07T15:06:13Z Item is restricted indefinitely.","Restriction data tranferred 2014-07-01T11:31:46-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":["AAI9543600","(UMI)AAI9543600","http://hdl.handle.net/2142/23695"],"dc:language":["eng"],"dc:rights":["Copyright 1995 Ha, Rhan"],"dc:subject":["Computer Science"],"dc:title":["Validating timing constraints in multiprocessor and distributed systems"],"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:22Z"}