Browse Prior Art Database

The Deadlock Problem: An Overview

IP.com Disclosure Number: IPCOM000131458D
Original Publication Date: 1980-Sep-01
Included in the Prior Art Database: 2005-Nov-11
Document File: 27 page(s) / 84K

Publishing Venue

Software Patent Institute

Related People

Sreeknanth S. Isloor: AUTHOR [+4]

Abstract

*Now at Bell Northern Research, Ottawa. Deadlock is a constant threat in terminal-oriented systems. This comprehensive study of deadlock-handling techniques introduces a method for on-line detection in distributed data bases. Modern multiprogramming systems are designed to support a high degree of parallelism by ensuring that as many system components as possible are operating concurrently. The increasing trend among commercial firms for on-line operations, especially those involving integrated data bases, and the consequent need by active users for responsive systems have placed heavy demands on operating systems. Compounding these difficulties, distributed processing has arrived as the solution to incremental system growth. Such contemporary systems exhibit a high degree of resource and data sharing, a situation in which deadlock is a constant threat. Deadlocks arise when members of a group of processes which hold resources are blocked indefinitely from access to resources held by other processes within the group. When no member of the group will relinquish control over its resources until after it has completed its current resource acquisition, deadlock is inevitable and can be broken only by the involvement of some external agency.

This text was extracted from a PDF file.
This is the abbreviated version, containing approximately 5% of the total text.

Page 1 of 27

THIS DOCUMENT IS AN APPROXIMATE REPRESENTATION OF THE ORIGINAL.

This record contains textual material that is copyright ©; 1980 by the Institute of Electrical and Electronics Engineers, Inc. All rights reserved. Contact the IEEE Computer Society http://www.computer.org/ (714-821-8380) for copies of the complete work that was the source of this textual material and for all use beyond that as a record from the SPI Database.

The Deadlock Problem: An Overview

Sreeknanth S. Isloor* T. Anthony Marsland

University of Alberta

*Now at Bell Northern Research, Ottawa. Deadlock is a constant threat in terminal-oriented systems.

This comprehensive study of deadlock-handling techniques introduces a method for on-line detection in distributed data bases.

Modern multiprogramming systems are designed to support a high degree of parallelism by ensuring that as many system components as possible are operating concurrently. The increasing trend among commercial firms for on-line operations, especially those involving integrated data bases, and the consequent need by active users for responsive systems have placed heavy demands on operating systems. Compounding these difficulties, distributed processing has arrived as the solution to incremental system growth. Such contemporary systems exhibit a high degree of resource and data sharing, a situation in which deadlock is a constant threat. Deadlocks arise when members of a group of processes which hold resources are blocked indefinitely from access to resources held by other processes within the group. When no member of the group will relinquish control over its resources until after it has completed its current resource acquisition, deadlock is inevitable and can be broken only by the involvement of some external agency.

A set of processes becomes deadlocked as a consequence of exclusive access and circular wait. The simplest illustration of these conditions involves only two processes, each holding, for exclusive access, a different resource and each requesting access to the resource held by the other. The result is a circular wait which cannot be broken until one of the processes releases its resource or cancels its request.

In this article, we survey the resource management problem in computer systems by reviewing the principles, techniques, and tools involved in handling and avoiding deadlocks; we also propose a new method for handling deadlock in distributed data bases, closing with some case studies on the resource management problem in large computer systems. Annotated references to works cited and a comprehensive bibliography of supplementary materials are provided.

Examples of deadlock

The deadlock problem occurs in many different contexts, and analogies can be made to real-life situations, provided one interprets the processes and resources involved appropriately. For instance, one often hears about "deadlocked" peace talks between two warring nations. In that context, the peace-negotiating...