Browse Prior Art Database

Optimal Thresholds for Scheduling Readers and Writers

IP.com Disclosure Number: IPCOM000037263D
Original Publication Date: 1989-Dec-01
Included in the Prior Art Database: 2005-Jan-29
Document File: 3 page(s) / 37K

Publishing Venue

IBM

Related People

Nicola, V: AUTHOR [+2]

Abstract

Threshold based scheduling has been shown to outperform a first-come, first-served (FCFS) scheduler from the viewpoint of the maximum throughput that can be sustained in processing readers and writers [1]. We describe a heuristic to determine the threshold number for writers such that the overall mean response time of the system is minimized.

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

Page 1 of 3

Optimal Thresholds for Scheduling Readers and Writers

Threshold based scheduling has been shown to outperform a first-come, first-served (FCFS) scheduler from the viewpoint of the maximum throughput that can be sustained in processing readers and writers [1]. We describe a heuristic to determine the threshold number for writers such that the overall mean response time of the system is minimized.

Reader and writer synchronization is a classical paradigm in operating system theory and practice, which is also applicable to transaction processing. Consider update transactions (resp. queries) requiring an exclusive (resp. a shared) lock on a database object. Queries (readers) can be processed in parallel, while updates (writers) are mutually exclusive with respect to each other and queries.

The FCFS scheduling of readers and writers results in the underutilization of the processing capacity of the system, especially when the reader processing times are much larger than those of writers. A more efficient scheduling policy is the Threshold Fastest Emptying (TFE) policy [2]. In a system with a saturated queue for readers and writers arriving according to a Poisson process (see the figure) TFE can be defined as follows: serve M readers until the queue for writers reaches some threshold number (K). Empty the system as quickly as possible, by finishing the processing of the M active readers. Then serve all writers including those which arrive while other writers are in progress. The cycle repeats.

This policy is generalized in [1] to a system with both reader and writer arrivals. As before when the number of writers exceeds a threshold then the system is emptied from readers and arriving readers are enqueued (see figure). The system then processes all writers before switching back to readers. If a writer (or reader) arrives at an empty system, it is processed immediately. Similarly the threshold has not been attained. An optimal threshold K (say Kopt) is the one which minimizes the mean overall response time in a corresponding reader saturated system at the point where the reader throughput equals that of the open system.

The arrival rates of readers and writers and the distribution of processing times (the exponential distribution is considered in 1). Given that the fraction of readers and writers is fr and fw and the mean response time for readers and writers as a function of K is denoted by Rr(M,K) and Rw(M,K), respectively, then the overall response time can be expressed as: R(M,K)=fr*Rr(M,K) + fw*Rw(M,K).

It is shown in 1, that under Markovian assumptions as K is increased (for a fixed M) the reader response time Rr(M,K) decreases at the cost of an increase in writer response times Rw(M,K). Thus, K can be chosen to minimize a weighted sum of Rr(M,K) and Rw(M,K). It is meaningful to choose the weights for Rr(M,K) and Rw(M,K) to correspond to fr and fw such that the overall response time R(M,K) is minimized. Since we are dealing with a re...