{"id":{"repo_id":"uiuc","oai_identifier":"oai:www.ideals.illinois.edu:2142/23252"},"canonical_url":"https://search.dev.ndltd.org/etd/uiuc/oai:www.ideals.illinois.edu:2142/23252","repository":{"repo_id":"uiuc","name":"University of Illinois - Urbana-Champaign","base_url":"https://www.ideals.illinois.edu/oai-pmh"},"display":{"title":"Schedulability analysis of resource access control protocols in real-time systems","abstract":"To guarantee the timing requirements of real-time systems are satisfied, the timing behavior of the systems must be predictable. Priority driven scheduling algorithms, such as the earliest deadline first algorithm, are known to be effective and predictable in scheduling independent tasks. However, when concurrent tasks share resources in a mutually exclusive manner, the timing behavior of the system becomes less predictable. Due to the conflict in accessing shared resources, a high priority task may have to wait for the execution of a low priority task, a phenomenon called priority inversion, causing it to miss its deadline requirement. To minimize the occurrences of priority inversion in using the earliest deadline first algorithm, we proposed two resource access control protocols to coordinate the accesses to shared resources. The dynamic priority ceiling is used when every shared resource is unique and can be identified by the tasks using it. When two or more shared resources provide the same service and can be used interchangeably, the generalized priority ceiling protocol is used. We analyzed the properties of these two protocols, and showed that they are effective in making the timing behavior of tasks more predictable.","abstract_html":"To guarantee the timing requirements of real-time systems are satisfied, the timing behavior of the systems must be predictable. Priority driven scheduling algorithms, such as the earliest deadline first algorithm, are known to be effective and predictable in scheduling independent tasks. However, when concurrent tasks share resources in a mutually exclusive manner, the timing behavior of the system becomes less predictable. Due to the conflict in accessing shared resources, a high priority task may have to wait for the execution of a low priority task, a phenomenon called priority inversion, causing it to miss its deadline requirement. To minimize the occurrences of priority inversion in using the earliest deadline first algorithm, we proposed two resource access control protocols to coordinate the accesses to shared resources. The dynamic priority ceiling is used when every shared resource is unique and can be identified by the tasks using it. When two or more shared resources provide the same service and can be used interchangeably, the generalized priority ceiling protocol is used. We analyzed the properties of these two protocols, and showed that they are effective in making the timing behavior of tasks more predictable.","abstract_has_math":false,"creators":["Chen, Min-Ih"],"institution":"University of Illinois at Urbana-Champaign","degree_name":"Ph.D.","degree_level":"Dissertation","degree_discipline":"Computer Science","degree_department":null,"school":null,"contributors":["Lin, Kwei-Jay"],"advisors":[],"committee_chairs":[],"committee_members":[],"year":2011,"date_issued":"2011-05-07T14:07:33Z","date_published":"2011-05-07T14:07:33Z","updated_at":"2026-07-22T22:25:21Z","subjects":["Computer Science"],"languages":["eng"],"rights":["Copyright 1991 Chen, Min-Ih"],"rights_urls":[],"identifier_entries":[{"key":"dc:identifier","label":"Identifier","values":["AAI9210764","(UMI)AAI9210764"],"render_values":[{"text":"AAI9210764","href":null,"code":true},{"text":"(UMI)AAI9210764","href":null,"code":true}]}]},"links":{"outbound_url":"http://hdl.handle.net/2142/23252","outbound_label":"Handle","outbound_source":"dc:identifier"},"metadata_groups":[{"id":"people","label":"People","entries":[{"key":"dc:contributor","label":"Contributor","values":["Lin, Kwei-Jay"]},{"key":"dc:creator","label":"Author","values":["Chen, Min-Ih"]}]},{"id":"academic_context","label":"Academic Context","entries":[{"key":"dc:date","label":"Dc Date","values":["2011-05-07T14:07:33Z","10000-01-01","1991"]},{"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 1991 Chen, Min-Ih"]}]},{"id":"identifiers","label":"Identifiers","entries":[{"key":"dc:identifier","label":"Identifier","values":["AAI9210764","(UMI)AAI9210764","http://hdl.handle.net/2142/23252"]}]},{"id":"additional","label":"Additional Metadata","entries":[{"key":"dc:description","label":"Description","values":["To guarantee the timing requirements of real-time systems are satisfied, the timing behavior of the systems must be predictable. Priority driven scheduling algorithms, such as the earliest deadline first algorithm, are known to be effective and predictable in scheduling independent tasks. However, when concurrent tasks share resources in a mutually exclusive manner, the timing behavior of the system becomes less predictable. Due to the conflict in accessing shared resources, a high priority task may have to wait for the execution of a low priority task, a phenomenon called priority inversion, causing it to miss its deadline requirement. To minimize the occurrences of priority inversion in using the earliest deadline first algorithm, we proposed two resource access control protocols to coordinate the accesses to shared resources. The dynamic priority ceiling is used when every shared resource is unique and can be identified by the tasks using it. When two or more shared resources provide the same service and can be used interchangeably, the generalized priority ceiling protocol is used. We analyzed the properties of these two protocols, and showed that they are effective in making the timing behavior of tasks more predictable.","Schedulability conditions are conditions under which all tasks in a system are guaranteed to be schedulable. The availability of schedulability conditions allows system designers to verify if a given system can meet its timing requirement in a simple and straightforward way, without going through more expensive and time-consuming testing or simulation. We derived several schedulability conditions for a class of resource access control protocols based on the earliest deadline first algorithm, and showed that they are more general and more exact than the schedulability conditions currently reported in the literature. We also investigated the schedulability conditions of a particular real-time reader and writer problem and suggested two operation coalescence schemes to improve its performance.","Made available in DSpace on 2011-05-07T14:07:33Z (GMT). No. of bitstreams: 2 license.txt: 4922 bytes, checksum: 910b249b4beec47e7ab768910c8f966f (MD5) 9210764.pdf: 4599574 bytes, checksum: ca94df1656565e93f4b6f15cbff1722a (MD5) Previous issue date: 1991","Item marked as restricted to the 'UIUC Users [automated]' Group (id=2) by Howard Ding (hding2@illinois.edu) on 2011-05-07T15:03:13Z Item is restricted indefinitely.","Restriction data tranferred 2014-07-01T11:30:07-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":["Schedulability analysis of resource access control protocols in real-time systems"]}]}],"canonical_facts":{"dc:contributor":["Lin, Kwei-Jay"],"dc:creator":["Chen, Min-Ih"],"dc:date":["2011-05-07T14:07:33Z","10000-01-01","1991"],"dc:description":["To guarantee the timing requirements of real-time systems are satisfied, the timing behavior of the systems must be predictable. Priority driven scheduling algorithms, such as the earliest deadline first algorithm, are known to be effective and predictable in scheduling independent tasks. However, when concurrent tasks share resources in a mutually exclusive manner, the timing behavior of the system becomes less predictable. Due to the conflict in accessing shared resources, a high priority task may have to wait for the execution of a low priority task, a phenomenon called priority inversion, causing it to miss its deadline requirement. To minimize the occurrences of priority inversion in using the earliest deadline first algorithm, we proposed two resource access control protocols to coordinate the accesses to shared resources. The dynamic priority ceiling is used when every shared resource is unique and can be identified by the tasks using it. When two or more shared resources provide the same service and can be used interchangeably, the generalized priority ceiling protocol is used. We analyzed the properties of these two protocols, and showed that they are effective in making the timing behavior of tasks more predictable.","Schedulability conditions are conditions under which all tasks in a system are guaranteed to be schedulable. The availability of schedulability conditions allows system designers to verify if a given system can meet its timing requirement in a simple and straightforward way, without going through more expensive and time-consuming testing or simulation. We derived several schedulability conditions for a class of resource access control protocols based on the earliest deadline first algorithm, and showed that they are more general and more exact than the schedulability conditions currently reported in the literature. We also investigated the schedulability conditions of a particular real-time reader and writer problem and suggested two operation coalescence schemes to improve its performance.","Made available in DSpace on 2011-05-07T14:07:33Z (GMT). No. of bitstreams: 2 license.txt: 4922 bytes, checksum: 910b249b4beec47e7ab768910c8f966f (MD5) 9210764.pdf: 4599574 bytes, checksum: ca94df1656565e93f4b6f15cbff1722a (MD5) Previous issue date: 1991","Item marked as restricted to the 'UIUC Users [automated]' Group (id=2) by Howard Ding (hding2@illinois.edu) on 2011-05-07T15:03:13Z Item is restricted indefinitely.","Restriction data tranferred 2014-07-01T11:30:07-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":["AAI9210764","(UMI)AAI9210764","http://hdl.handle.net/2142/23252"],"dc:language":["eng"],"dc:rights":["Copyright 1991 Chen, Min-Ih"],"dc:subject":["Computer Science"],"dc:title":["Schedulability analysis of resource access control protocols in real-time 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:21Z"}