Browse Prior Art Database

New Threshold Policy for Scheduling Readers And Writers

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

Publishing Venue

IBM

Related People

Thomasian, A: AUTHOR

Abstract

A queueing system can process writers one at a time, while readers can be processed with a degree of concurrency up to M (the number of servers in the queueing system). This is because writers are mutually exclusive with respect to each other and readers, while readers are compatible with each other. The FCFS (first come, first served) scheduling of readers and writers is inefficient because of the lost opportunities to process the readers concurrently. This effect is especially significant when the readers are much longer than writers. The performance of this system can be improved by adopting a threshold policy (*). Readers are processed until the number of writers in the system attains a certain threshold (K).

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

New Threshold Policy for Scheduling Readers And Writers

       A queueing system can process writers one at a time,
while readers can be processed with a degree of concurrency up to M
(the number of servers in the queueing system).  This is because
writers are mutually exclusive with respect to each other and
readers, while readers are compatible with each other.  The FCFS
(first come, first served) scheduling of readers and writers is
inefficient because of the lost opportunities to process the readers
concurrently.  This effect is especially significant when the readers
are much longer than writers.  The performance of this system can be
improved by adopting a threshold policy (*).  Readers are processed
until the number of writers in the system attains a certain threshold
(K).  The readers in progress in the system are then processed to
completion, but no new readers (enqueued or arriving) are activated.
After all in-progress readers are completed, the system processes all
writers including those which arrive after the threshold was
attained.

      This threshold policy has the advantage that by deferring the
processing of readers (until all writers are processed) there will be
an accumulation of readers in the system such that they can be
processed more efficiently.  On the other hand, this policy has the
disadvantage of (potentially) deferring the processing of multiple
readers while writers are in progress.  This effect is more
significant when writers are not necessarily shorter than readers and
an accumulation of readers in the system during the processing of
writers is not unlikely.

      The new (non-preemptive) threshold scheduling policy utilizes a
threshold K for the number of writers and a threshold J for the
number of readers.  The effect of the new threshold J for readers is
to give priority to readers (with respect to writers) when their
number has exceeded J. This has the advantage of reducing the overall
response time (a weighted sum of the reader and writer response times
with the weights equalling the fraction of readers and writers in the
arrival stream, respectively).  The threshold J should be set high
enough such that readers are processed efficiently.  This is due to
the inefficiency in processing readers at lower degrees of
concurrency, including the time the system is being emptied from
readers.  There is a secondary threshold associated with readers
(J'), which is set to M in the following discussion (experimentation
showed that this setting is acceptable).  This threshold assures the
continuation of reader processing, unless it cannot be continued
efficiently anymore.  Even when the threshold for writers has been
achieved, the emptying of the system from readers is not started
unless the number of readers in the system is less than J'.  Once the
processing cycle for writers begins, even though the thresho...