Deadlock Avoidance Algorithms for Recursion-Tree Modeled Requests in Parallel Executions

Yang Wang

doi:10.1109/TC.2021.3122843

Deadlock Avoidance Algorithms for Recursion-Tree Modeled Requests in Parallel Executions

2021-01-01

2

OA

AI

DOI：10.1109/TC.2021.3122843

Original

Original request for help

Save

Abstract

En 中文

We present an extension of the banker's algorithm to resolve deadlock for programs whose resource-request graph can be modeled as a recursion tree for parallel execution. Our algorithm implements the banker's logic, with the key difference being that some properties of the tree are fully exploited to improve the resource utilization and safety check in deadlock avoidance. For an n-node tree modeled program making requests to m types of resources, our recursion-tree based algorithm can obtain a time complexity of O(mnlog log n) on average in safety check while reducing the conservativeness in resource utilization. We reap these benefits by proposing a concept of the resource critical tree and leverage it to localize the maximum claim associated with each node in the tree. To tackle the case when the tree model is not statically known, we relax the definition of a local maximum claim by sacrificing some resource utilization. With this trade-off, the algorithm can resolve the deadlock and achieve more efficient safety checks within time of O(mlog log n). Our empirical studies on a two-dimensional integration problem on sparse grids show that the proposed algorithms can reduce resource utilization conservativeness and improve avoidance performance by minimizing the number of safety checks.

Keywords:

Deadlock avoidance

recursion-tree model

resource constraint

resource-request graph

safety check

task scheduling

Deadlock Avoidance Algorithms for Recursion-Tree Modeled Requests in Parallel Executions

Abstract

Journal

Organization