An efficient deadlock avoidance algorithm

Raphael Finkel; Hari H. Madduri

doi:10.1016/0020-0190(87)90195-5

An efficient deadlock avoidance algorithm

Raphael Finkel, Hari H. Madduri

Computer Science

Research output: Contribution to journal › Article › peer-review

4 Scopus citations

Abstract

The Banker's algorithm avoids deadlocks by requiring the existence of a safe sequence of job completions before granting any request. We generalize this safety test and calculate the minimum number of resources needed to assure that an allocation state is safe. We also introduce a data structure that remembers safe sequences across calls to the resource allocator. We derive an O(log n) safety test for n processes.

Original language	English
Pages (from-to)	25-30
Number of pages	6
Journal	Information Processing Letters
Volume	24
Issue number	1
DOIs	https://doi.org/10.1016/0020-0190(87)90195-5
State	Published - Jan 15 1987

Keywords

Banker's algorithm
deadlock avoidance
resource allocation

ASJC Scopus subject areas

Theoretical Computer Science
Signal Processing
Information Systems
Computer Science Applications

Access to Document

10.1016/0020-0190(87)90195-5

Cite this

@article{b1a07808e93941baa8d64b0dd4f5b4c9,

title = "An efficient deadlock avoidance algorithm",

abstract = "The Banker's algorithm avoids deadlocks by requiring the existence of a safe sequence of job completions before granting any request. We generalize this safety test and calculate the minimum number of resources needed to assure that an allocation state is safe. We also introduce a data structure that remembers safe sequences across calls to the resource allocator. We derive an O(log n) safety test for n processes.",

keywords = "Banker's algorithm, deadlock avoidance, resource allocation",

author = "Raphael Finkel and Madduri, {Hari H.}",

year = "1987",

month = jan,

day = "15",

doi = "10.1016/0020-0190(87)90195-5",

language = "English",

volume = "24",

pages = "25--30",

number = "1",

}

TY - JOUR

T1 - An efficient deadlock avoidance algorithm

AU - Finkel, Raphael

AU - Madduri, Hari H.

PY - 1987/1/15

Y1 - 1987/1/15

N2 - The Banker's algorithm avoids deadlocks by requiring the existence of a safe sequence of job completions before granting any request. We generalize this safety test and calculate the minimum number of resources needed to assure that an allocation state is safe. We also introduce a data structure that remembers safe sequences across calls to the resource allocator. We derive an O(log n) safety test for n processes.

AB - The Banker's algorithm avoids deadlocks by requiring the existence of a safe sequence of job completions before granting any request. We generalize this safety test and calculate the minimum number of resources needed to assure that an allocation state is safe. We also introduce a data structure that remembers safe sequences across calls to the resource allocator. We derive an O(log n) safety test for n processes.

KW - Banker's algorithm

KW - deadlock avoidance

KW - resource allocation

UR - http://www.scopus.com/inward/record.url?scp=0023157013&partnerID=8YFLogxK

UR - http://www.scopus.com/inward/citedby.url?scp=0023157013&partnerID=8YFLogxK

U2 - 10.1016/0020-0190(87)90195-5

DO - 10.1016/0020-0190(87)90195-5

M3 - Article

AN - SCOPUS:0023157013

SN - 0020-0190

VL - 24

SP - 25

EP - 30

JO - Information Processing Letters

JF - Information Processing Letters

IS - 1

ER -

An efficient deadlock avoidance algorithm

Abstract

Keywords

ASJC Scopus subject areas

Access to Document

Other files and links

Fingerprint

Cite this