Efficient Synchronization for Real-Time Systems with Nested Resource Access
Catherine E. Nemitz · Carolina Digital Repository (University of North Carolina at Chapel Hill) · 2021
Real-time systems are comprised of tasks, each of which must be guaranteed to meet its timing requirements. These tasks may request access to shared system components, called resources. Each such request may experience delays before being granted resource access. These delays can be separated into two categories: (i) those caused by the order in which tasks are granted resource access, and (ii) those caused by the time it takes to coordinate this ordering. If these delays are too large, a task may be unable to meet its timing requirements. Tasks can require access to multiple resources concurrently, acquiring these resources in a nested fashion. This nested resource access can cause significant delays to tasks; these delays can far exceed those when only a single resource is required at a time, as certain request orderings cause delays between tasks that do not share any resources. This dissertation presents locking protocols and a protocol-independent approach to mitigate resource access delays. Nested resource access can increase delays for all requests, including non-nested requests. The first protocol eliminates these additional delays by separating requests by type and creating a fast-path mechanism for non-nested requests. The next two protocols both reduce delays by reordering requests. One protocol reorders requests as they are issued, and the other uses an offline process to determine which requests may execute concurrently. These three protocols were compared to prior approaches in an evaluation across a range of task systems; all three protocols resulted in more task systems guaranteed to meet their timing requirements. Finally, a protocol-independent approach reduces delays by using a designated task to execute the locking protocol on behalf of other tasks. When applied to two protocol variants, this approach significantly reduced delays.