Browse Prior Art Database

Low Cost Low Contention Shared Exclusive Locks

IP.com Disclosure Number: IPCOM000051830D
Original Publication Date: 1981-Mar-01
Included in the Prior Art Database: 2005-Feb-11
Document File: 2 page(s) / 15K

Publishing Venue

IBM

Related People

Berstis, V: AUTHOR [+3]

Abstract

Systems need shared/exclusive lock mechanisms to control access to shared resources. The microinstruction set of the computer system provides Djikstra-style semaphores with built-in dispatching. However, the primitives provided do not in themselves provide a shared/exclusive lock mechanism. The contention properties of the present method are superior over the prior art described in Appendix A. The shared/ exchange lock mechanism used by storage management of the computer system satisfies the following design constraints: 1. The implementation, especially the shared path, must be efficient. Since it is used by page faults, excessive cost is intolerable. 2. The implementation must have low contention. Users desiring to obtain the lock shared must not wait for significant periods of time unless the lock is held exclusively.

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

Page 1 of 2

Low Cost Low Contention Shared Exclusive Locks

Systems need shared/exclusive lock mechanisms to control access to shared resources. The microinstruction set of the computer system provides Djikstra-style semaphores with built-in dispatching. However, the primitives provided do not in themselves provide a shared/exclusive lock mechanism. The contention properties of the present method are superior over the prior art described in Appendix A. The shared/ exchange lock mechanism used by storage management of the computer system satisfies the following design constraints: 1. The implementation, especially the shared path, must be efficient. Since it is used by page faults, excessive cost is intolerable. 2. The implementation must have low contention. Users desiring to obtain the lock shared must not wait for significant periods of time unless the lock is held exclusively. 3. Low priority tasks must have a reasonable chance to get the lock exclusive.

Djikstra-type semaphores called counters, for purposes here, are defined as follows:

Each counter has two fields: count and limit. Two atomic instructions, SEND COUNT (SENDC) and RECEIVE COUNT (RECC), are defined as follows:

SEND COUNT (SENDC): Add one to the count field of the specified counter. Dispatch all waiting processes.

RECEIVE COUNT (RECC): Compare the count to the limit. If the count is greater than or equal to the limit, set the count to count minus the limit. Otherwise, the count is unchanged, and the process waits.

The count and limit fields may go from 0 to N. Note that SENDC and RECC are microinstructions and execute atomically. When a process is redispatched from the wait state, it reexecutes the receive count instruction.

The lock is implemented as two counters named and initialized as follows: EXCLUSIVE COUNTER (ECOUNT) COUNT = 1, LIMIT = 1 SHARED COUNTER (SCOUNT) COUNT = N, LIMIT = 1

The following ""macro'' sequences get and free the lock in the indicated manner: GET SHARED GET EXCLUSIVE RECC ECOUNT RECC ECOUNT RECC SCOUNT SET LIMIT OF SCOUNT = N SENDC ECOUNT RECC SCOUNT FREE SHARED FREE EXCLUSIVE SENDC SCOUNT SET LIMIT OF SCOUNT = 1 SET COUNT OF SCOUNT = N SENDC ECOUNT This table shows a representative sample of transitions: ECOUNT SCOUNT Count Limit Count Limit INITIAL 1 1 N 1 Process A GETSHARED a) 0 1 N 1 b) 0 1 N-1 1 c) 1 1 N-1 1 Process B GETEXCLUSIVE a) 0 1 N-1 1 b) 0 1 N-1 N (Process B waits) Process C GETSHARED 0 1 N-1 N (Process C waits) Process A FREESHARED
a) 0 1 N N Process B c) 0 1 phi N Process B FREEEXCLUSIVE a) 0 1 phi 1 b) 0 1 N 1 c) 1 1 N 1 Process C GETSHARED a) 0 1 N 1 b) 0 1 N-1 1 c) 1 1 N-1 1 Process D GETSHARED a) 0 1 N-1 1 b) 0 1 N-2 1 c) 1 1 N-2 1 Where a), b), c) represent each alteration of a COUNT or LIMIT field by RECC/SENDC or by ordinary instruction. Observations (why the requirements are satisfied): 1. GET

1

Page 2 of 2

SHARED typically runs without significant interruption when no one holds the lock (or tries to hold the lock) exclusive....