Dismiss
InnovationQ will be updated on Sunday, Oct. 22, from 10am ET - noon. You may experience brief service interruptions during that time.
Browse Prior Art Database

Improved Solution to the MUTUAL EXCLUSION Problem

IP.com Disclosure Number: IPCOM000043102D
Original Publication Date: 1984-Jul-01
Included in the Prior Art Database: 2005-Feb-04
Document File: 2 page(s) / 48K

Publishing Venue

IBM

Related People

Downs, T: AUTHOR

Abstract

The mutual exclusion problem is the problem of ensuring that, at most, one of N independent processes is engaged in its CRITICAL_SECTION at any one time. Any method addressing this problem must deal with two issues: Ensuring mutual exclusion. Preventing deadlocks. The problem presented here only addresses the case where N equals 2; it does not deal with the generalized mutual exclusion problem. Dijkstra [*] discusses a number of unsatisfactory solutions to this problem before quoting the correct solution discovered by T. J. Decker. The method presented here is an improvement to this solution. Two versions are quoted: one in Dijkstra's formalism and one in a more modern formalism. They are shown respectively in Table 1 and Table 2.

This text was extracted from a PDF file.
At least one non-text object (such as an image or picture) has been suppressed.
This is the abbreviated version, containing approximately 73% of the total text.

Page 1 of 2

Improved Solution to the MUTUAL EXCLUSION Problem

The mutual exclusion problem is the problem of ensuring that, at most, one of N independent processes is engaged in its CRITICAL_SECTION at any one time. Any method addressing this problem must deal with two issues: Ensuring mutual exclusion. Preventing deadlocks. The problem presented here only addresses the case where N equals 2; it does not deal with the generalized mutual exclusion problem. Dijkstra [*] discusses a number of unsatisfactory solutions to this problem before quoting the correct solution discovered by T. J. Decker. The method presented here is an improvement to this solution. Two versions are quoted: one in Dijkstra's formalism and one in a more modern formalism. They are shown respectively in Table 1 and Table 2.

(Image Omitted)

Inherent in the method described is that one process has a higher priority in a possible deadlock situation, and is 'granted' the critical resources by the other process. In the versions presented below process LOCK_A has the higher priority.

PROOF OF CORRECTNESS ENSURING MUTUAL EXCLUSION In case A is attempting to get the resource: If A is trying to get the resource, then A_GRANT>1. If B had it, then B_GRANT=1 and A_GRANT will not be set to 2, so A is held in its loop. If B tries to get it, then it cannot get out of its loop because A_GRANT=1. In case B is attempting to get the resource: If B is trying to get the resource, then B_GRANT=1. If A had it, then A_GRANT>1, so...