Algorithms for Checking Applicability of Resource Access Protocols in Real-Time Systems
Abstract
Introduction: Developing multi-task applications often requires that access to their common resources is shared between multiple tasks. For this purpose, synchronizing elements like mutexes are often used. However, using mutexes can lead to deadlocks. To avoid them, you can use special access protocols with additional steps on top of mutex operations («request»/»free resource»). In real-time systems, these steps could lead to a significant increase in response time for high priority tasks. Previously, a solution based on static analysis of real-time application models was proposed. The applications are modeled using graphical formalism of route nets. This solution relies on building a special multipartite oriented graph (a graph of bundles of critical intervals). Purpose: The goal is to develop algorithms which would implement the static analysis proposed earlier, and to evaluate their complexity. Results: The algorithms developed in this study can determine whether the necessary and sufficient conditions for deadlocks are found in a given application. The analysis is performed in three steps. The first algorithm builds a graph of bundles of critical intervals. This algorithm is linear with respect to number of bundles and their dependencies. The second algorithm enumerates the interparty circuits. This algorithm takes O((n+e)(c+1)), where c is the number of the circuits, n is number of the vertices, and e is the number of the edges. Finally, the third algorithm searches for intersections between the interparty circuits. The third algorithm takes linear time with respect to the total length of all the interparty circuits. These algorithms allow developers to modify an application early in its development to prevent deadlocks or chose an access protocol providing the best performance.Published
2017-08-21
How to Cite
Nikiforov, V., & Podkorytov, S. (2017). Algorithms for Checking Applicability of Resource Access Protocols in Real-Time Systems. Information and Control Systems, (4), 59-66. https://doi.org/10.15217/issn1684-8853.2017.4.59
Issue
Section
Hardware and software resources