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

A METHOD FOR IMPLEMENTING PRIORITIZED WRITERS IN A READER-WRITER LOCK

IP.com Disclosure Number: IPCOM000008769D
Original Publication Date: 1998-Jun-01
Included in the Prior Art Database: 2002-Jul-11
Document File: 3 page(s) / 171K

Publishing Venue

Motorola

Related People

James Lacey: AUTHOR [+3]

Abstract

Software development often requires the synchronization of access to shared resources. Whereas access to most resources is limited at any given time to a single processing entity and can be guarded through the use of a conventional mutex (mutually exclusive lock), the nature of some resources allow for concurrent access under specific conditions. A reader-writer lock addresses access synchronization to one such category of resources. Resources that can be guarded by a reader-writer lock are typically characterized by many readers and only a few writers. Many reader.7 are allowed simultaneous access to such a resource due to the fact that they have no intent to modify the resource. However, a writer must have exclusive access to the resource since the intent is to alter it.

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 36% of the total text.

Page 1 of 3

M-LA Technical Developments

A METHOD FOR IMPLEMENTING PRIORITIZED WRITERS IN A READER-WRITER LOCK

by James Lacey, Mark Patton and Marc Peters

  Software development often requires the synchronization of access to shared resources. Whereas access to most resources is limited at any given time to a single processing entity and can be guarded through the use of a conventional mutex (mutually exclusive lock), the nature of some resources allow for concurrent access under specific conditions. A reader-writer lock addresses access synchronization to one such category of resources. Resources that can be guarded by a reader-writer lock are typically characterized by many readers

and only a few writers. Many reader.7 are allowed simultaneous access to such a resource due to the fact that they have no intent to modify the resource. However, a writer must have exclusive access to the resource since the intent is to alter it.

  The difficulty with reader-writer locks is the implementation of the lock itself. Two imple- mentations exist today that are widely accepted. One implementation is Pro-Reader and the other is Pro- Writer. The Pro-Reader variant assumes the writers are few and can wait for readers to dissipate without a consequence. A possible starvation of writers as a result of high reader activity is acceptable. The Pro-Writer variant assumes the writers are few but must complete as soon as possible. A possible starvation of readers could occur as a result of high writer activity (but discounted due to the assumption that there are only a few writers). Neither implementation is ideal as the assumptions are severe and most systems do not always adhere to the characteristics associated with either model.

  This paper introduces a new variant of the reader-writer lock that solves some of the inherent flaws in the previous implementations. This new variant categorizes writers as either "high" or "low" priority writers. High priority writers are typical of the Pro-Writer variant where the writer is given access to the resource as soon as possible (preventing any further reader accesses to the resource until it

has been satisfied). Low priority writers are typical of the Pro-Reader variant where writers are willing to wait until there are no readers accessing the resource (as well as no high priority writers). At first glance, the new variant seems like a simple merger of the two previous implementations. If this was true, the new variant would actually allow for both types of starvation (much worse than either previous implementation). Starvation of any type is not acceptable.

  To address the starvation problem, the new vari- ant of the reader-writer lock introduces the concept of upgrading writer locks. Whereas a high priority writer lock is acquired in much the same fashion as in the Pro-Writer implementation, the low priority writer lock is acquired with additional options. After a prescribed time period, which depends on the system behavior,...