Approximate Analysis of Reader/Writer Queues.
We analyze the performance of queues that serve readers and writers. Readers are served concurrently, while writers require exclusive service. We approximately analyze a first-come-first-serve (FCFS) reader/writer queue, and derive simple formulae for computing waiting times and capacity under the assumption of Poisson arrivals and exponential service. We extend the analysis to handle a one-writer queue, and a queue that includes write-intention locks. The simple analyses that we present can be used as rules-of-thumb for designing concurrent systems.
Introduction
Most analyses of database or operating system concurrency control algorithms handle only the case
of exclusive access. In practice, however, many concurrency control algorithms use both shared and
exclusive locks. Shared locks are important for increasing concurrency and reducing serialization delays.
This paper describes queues that model reader and writer access to a shared resource. Readers place
R (read) locks and writers place W (write) locks. Any number of R locks may be held simultaneously,
but only one W lock may be placed at a given time. In addition, R and W locks are incompatible and
cannot be held simultaneously. A queuing discipline that manages the lock access should be fair, so that
readers should not starve writers, and vice versa. A common fairness criterion is FCFS. That is, if lock
ff arrives before lock fi, grant ff before granting fi.
The FCFS lock queuing mechanism obeys the following protocol: when the job in service finishes, if
the first job in the queue is a reader, grant access to all readers up to the first writer. If the first job is
a writer, grant the lock to the writer. In addition, if the queue is empty, or only readers are in service
and a reader arrives, grant a lock to the reader (see figure 1). We call this type of lock queue a FCFS
reader/writer queue or a FCFS r/w queue, for short.
We also analyze a variation on the FCFS R/W queue. In the variation, which we call the one-writer
queue, there is at most one writer in the queue at a time, and the reader arrival rate is much larger than
the writer arrival rate. The one-writer queue has many applications (for example, in the analysis of a
communications driver [15]). We use the one-writer queue to model queues with write-intention locks,
or R/U/W queues. In a R/U/W queue, the incoming stream consists of R and U locks. R locks are
compatible both with each other and with U locks, but U locks are not compatible with each other. U
locks occasionally upgrade to W locks, which are exclusive. The R/U/W queue can model write-intention
locks, which are often used for concurrent data structures [3] and for multigranularity locking [4].
The model that we develop predicts the expected waiting time for R, W and U locks. In addition,
the model can predict the probability that a W lock is in the queue, and determine whether the resource
can serve the offered load.
Several analyses of read and write access to a shared resource have been in the context of database
performance [23, 17, 6]. For example, Tay [23] handles read-only requests by modifying the formulae for
the probability of a lock conflict and assumes that queuing for shared data is rare.
The problem of queuing for shared data has been modeled in the context of replicated databases. It
is assumed that there are k copies of a file, and two different copies of a file may be read simultaneously.
Coffman et al. [7] analyze a saturated queue in which a write request preempts all current readers. In
[8], Coffman, Gelenbe, and Plateau analyze the same queue, except that readers may begin reading a
copy of the file as soon as it has been written. Baccelli and Coffman [2] analyze a preemptive queue
that has Poisson arrivals. Nelson and Iyer [18] analyze a non-preemptive queue in which the job arrivals
are Poisson and are processed in FCFS order. Read operations receive exponentially distributed service,
and write operations receive phase distributed service (the exponential distribution is an example of a
phase distribution.) Nelson and Iyer's analysis can be thought of as an exact analysis of an approximate
FCFS R/W queue, as readers and writers receive FCFS service, but at most k readers may be served
simultaneously. This analysis requires an iteration step that involves multiplication of k by k matrices.
Courcoubetis et al. [10, 1] analyze queuing systems of k queues in which ordinary customers require
service from only one queue, while locking customers require service from all queues simultaneously.
Thomasian and Nicola [24, 26, 25] use the vacationing server model to study the optimal control of a
reader/writer queue. Courcoubetis and Reiman [9] use a system of k queues with ordinary and locking
customers to study the optimal control of a reader/writer queue.
Reiman and Wright [20, 19] provide an exact analysis of the stability of the first queueing system
described in this paper, permit arbitrary reader and writer service times, and permit the writer arrival
process to be an arbitrary renewal process. These authors also provide lower and upper bounds on the
lock waiting times, and a heavy traffic approximation.
This paper has two main contributions. The first contribution is the simple formulae for predicting
the capacity and the waiting times of the FCFS R/W queuing system. These formulae can provide simple
rules of thumb for designing concurrent systems [12, 11]. The second contribution of this paper is the
analysis of the one-writer queue and the R/U/W queue. To the best of our knowledge, these queuing
systems have not been treated before.
An Approximation to the FCFS R/W Queue
The difficulty in analyzing the reader/writer queue is that the two different classes of customers receive
different types of service. The writers are the more tractable of the two classes because they receive
exclusive FCFS service. Therefore, we approximate the reader/writer queue as an FCFS queue with an
aggregate customer, which is a writer together with all readers immediately ahead of it in the queue. The
aggregate customer has an arrival rate of w and a service time equal to the service time for a writer
plus the service time for all of the readers immediately ahead of it. We need to calculate the service
time for the readers that entered the queue before the entering writer and after the previous writer.
There are two cases: either the entering writer finds another writer in the queue, or no writers are in
the queue. If another writer is in the queue, the entering writer must wait for all readers that entered in
between writer arrivals. Otherwise, the writer must wait for only those readers that survived (have not
yet finished service) until the writer entered.
We will use the following symbols and definitions in the analysis:
reader arrival rate.
reader service rate.
probability that a writer is in the queue (or writer utilization).
expected time to serve an aggregate customer (a writer and all readers that arrived after the previous
writer for which the current writer must wait).
expected time that a writer must wait for readers that arrived after the previous writer, if the
previous writer is still in the queue upon the arrival of the current writer.
expected time that a writer must wait for readers that arrived after the previous writer, if the previous
writer finished before the current writer arrived.
expected waiting time for a writer.
expected waiting time for a reader.
time to serve n readers.
A r (t): number of readers that arrive in t seconds.
time of a writer that finds another writer in the queue.
number of surviving readers.
service time: time that a customer spends receiving service.
service period: total time that a customer spends in the queue (=service time+waiting time).
The main result of this section is:
Theorem 1 The probability that a writer is in the queue, ae w , satisfies:
r
r
Some results that we will need to perform the analysis are:
be the time for n concurrent readers to be served, where each reader is served
concurrently at rate  r . Then
d
dt
Pr[S r (n)
Proof: We model this situation by a pure-death process. Let state k be the condition that there are k
readers left, and let P k (t) be the probability that the system is in state k at time t,
the system is in state k at time t, then a reader will die at rate k r . In this model P 0
The description of the system leads to the following system of differential equations:
dPn (t)
dt
\Gamman r Pn (t)
dt
dt
For our initial conditions, we have Pn From this, the solution to the
differential equations is:
R 1P k+1 (x)e krx dx
The solution to this recurrence is:
The last of the differential equations tells us that dP0 (t)
or that
dt
Corollary 1
1=i (3)
Proof:
dt
r
r
where the last step is just the application of the combinatorial identity found in [21], page 4. ffl
With these tools, we can calculate the expected time needed to serve all readers in front of a writer,
W, if another writer is in the queue when W enters. We need to calculate the number of readers that
entered the queue before the entering writer and after the previous writer. Suppose the time between
writer arrivals is t. Let the random variable A r (t) be the number of readers that arrive in t seconds. The
readers have a Poisson arrival rate, so A r (t) has the distribution:
To calculate the distribution of the number of readers that arrive between the arrival of two writers,
we find the unconditional distribution of A r . For this, we need to know the distribution of t. The
probability that the inter-arrival period lasts at least t seconds, given that the arriving writer finds at
least one other writer in the queue, is the probability that the inter-arrival period lasts at least t seconds
and the service period (waiting time plus service time) of the previous writer lasts at least t seconds. Let
Tw be the random variable that represents the interarrival time of writers that find the queue utilized.
Then:
d
dt Pr[Tw
dt
Pr[interarrival time  t] \Delta Pr[previous writer still in queue]
where K is a normalizing constant.
Suppose that we already know the expected service time of an aggregate customer, 1= a , and the
probability that a writer is in the queue, ae a . If we model the aggregate queue as an M/M/1
queue, then we know that the service period distribution (waiting time and service time) is [13]:
The probability that the previous writer has not been served in t seconds is so we have:
d
dt
Using this distribution for Tw , we get:
dt Pr[T w  t]dt
R 1(r
r a
r a
a
r+a
r+a
This leads to
Lemma 2 The expected time to serve all readers in front of a writer arriving in a queue that already
contains a writer is:
r
Proof: We randomize S r using A r and calculate the unconditional expectation.
r (a +r )
a+r
In order to solve this sum, we apply Abel's transformation ([16] page 36),
\DeltaX k
Y r
Let
a k
a n+1
a k =k
using the well-known expansion ln(1
a
We substitute in the value of a, substitute w =ae w for  a , and multiply by the leading constants to
get:
r
r
a
r
Next, we must calculate the expected waiting time for serving the readers in the case in which the
writer enters the queue and finds only readers in the queue. We cannot use the expected value already
calculated because some of the readers may have left the queue before the writer enters the queue. The
calculation of the distribution of the number of readers in the queue when the writer arrives is intractable.
Instead of the distribution, we will calculate the expected number of readers still in the queue.
Consider three points in time, A respect to a particular writer, W, who enters the
queue and finds no other writers in the queue. Occasion A is the point when the previous writer entered
the queue, occasion B is the point when the previous writer left the queue and occasion C is the point
when W enters the queue (see Figure 2). Because reader arrivals and departures are independent, we
will consider the expected number of surviving readers from (A,B) and from (B,C) separately.
We need to know the lengths of the intervals (A,B) and (B,C). The arrival distribution is memoryless,
so the length of (B,C) has an exponential distribution with parameter w . We find the approximation
to the distribution of the length of (A,B) the same way we found the approximation to the distribution
of Tw . The probability that (A,B) lasts at least t seconds is the probability that the previous writer's
service period lasts at least t seconds and the writer interarrival time is at least t seconds.
d
dt
Consider the survivors from (B,C) first. The probability that a reader enters the queue during time
. A reader that entered the queue  seconds before C will survive with probability
. Therefore, the expected number of surviving readers if (B,C) is t seconds long is
The unconditional distribution of N BC
r becomes:
R 1r
w+r
Next, consider the survivors from (A,B). The expected number of survivors from (A,B) is the expected
number of readers that arrived in (A,B), then survived through (B,C). Suppose that the probability of
surviving (B,C) is p. Then if k readers arrived in (A,B), the expected number of survivors, N AB
r (k; p)
equals kp. To remove the dependence of N AB
r (k; p), on k, we need to know the distribution of the number
of arrivals in (A,B). Since the distribution of j(A; B)j has the same distribution as T u
w , the number of
readers that arrive in (A,B) has the same distribution as A r .
k=0 kp a
r+a
r+a
a
If the interval (B,C) is t seconds long, the probability of surviving is . Using this to get the
unconditional distribution of N AB
r , we get:
R 1r
a
The expected number of survivors when W arrives is
In order to calculate the expected waiting time, we assume that the number of surviving readers has
a geometric distribution with mean (1
r is then number of surviving readers,
We can calculate the mean in the same manner as in Lemma 2, to get:
Lemma 3 The expected time to serve all readers in front of a writer that finds no other writers in the
queue when it arrives is:
r
Now, we know that the expected service time for the aggregate customer is:
a
If we use the fact that ae and the values of r e and r u , we get:
r
r
Proving Theorem 1ffl
To find ae w , we find the root of ae w in the above equation. This can be done iteratively or with a
nonlinear equation solving package. The queue will be stable if ae w ! 1.
Once the correct ae w has been found, we can try solving the queue as an M/M/1 queue with arrival
rate w and service rate 1=Aw . In this system, the expected waiting time is (ae wAw
waiting time of an aggregate customer is the waiting time of a reader, but a writer must also wait for all
readers ahead of it to finish, so:
Corollary 2 If the aggregate queue is modeled as an M/M/1 queue, the expected waiting times for the
reader and writer customers are:
2.0.1 M/G/1 Model
We can also consider the server as a network of exponential stages. With probability ae w , service is for
an expected 1=w seconds, then for an expected r u seconds. With probability service is for an
expected 1=w seconds, then for an expected r e seconds. The Laplace transform of the service time of
this server is given by:
ae w
r
The expected waiting time for a M/G/1 queue is given by ([13] pg.190):
where x is the service time at the server.
The value of x 2 can be found by differentiating the Laplace transform twice and evaluating at zero.
This gives:
Corollary 3 If the aggregate queue is modeled as an M/G/1 queue, the expected waiting times for the
reader and writer customers are:
re
e
2.1 Maximum Throughput
Theorem 1 can be used to predict the maximum throughput.
Corollary 4 At the maximum throughput, w ,  r , w and  r satisfy
e r (1=w \Gamma1= w
Proof: Theorem 1 and solve for  r ffl We note that this stability condition is the same as
that derived in [20, 19].
As an application, we can find the maximum throughput of the queue when the proportion of readers
to writers is constant.
Corollary 5 If  r then the maximum writer arrival rate is:
Corollary 5 implies that if a increasing the reader service rate is better than increasing the
writer service rate. If a the opposite is true.
Theorem 1 can also be used to find the arrival rates such that ae
2.2 Comparison and Experiments
A R/W queue simulator was built and experiments run. Six hundred thousand samples were taken. The
results of the simulator were then compared to analytical results.

Table

1 shows a comparison between the M/M/1 model and the simulation. The analytical calculation
of ae w (and therefore of r u and r e ) is usually close to the results of the simulator. The match is best when
r  w and becomes worse when  r is much larger than w . This can be seen in Figure 4. The M/M/1
model gives good predictions of the expected lock waiting times when  r  w . As  r increases, the
waiting times predicted by the M/M/1 model tend to become pessimistic, as can be seen in Figure 3.

Table

2 shows a comparison between the M/G/1 model and the simulation. If  r AE w , then the
M/G/1 model is a better approximation than the M/M/1 model.
When the rate of reader arrivals is close to the rate of writer arrivals, the aggregate customer has
a service distribution that can be approximated well by an exponential distribution. When the rate of
reader arrivals becomes large, the contribution of the readers to the service time becomes greater and the
service time distribution is better approximated by the hyperexponential distribution. A rule of thumb
for choosing the best model to use is the following:
Rule of thumb: If  r =w  5, use the M/G/1 model, otherwise use the M/M/1 model.

Figures

5 and 6 show how the maximum writer and reader arrival rate decreases with an increasing
reader and writer arrival rate, respectively. The graphs show a cutoff point in the writer arrival rate after
which the reader arrival rate may be increased almost arbitrarily as the writer arrival rate decreases.
This is largely due to the fact that r e and r u depend logarithmically on  r , so that further increases in
the aggregate customer's service time require exponential increases in the reader arrival rate.
3 The One-Writer Queue
In this section, we analyze a reader/writer queue in which at most one writer is ever in the queue. The
protocol of the one-writer queue is the same as for the FCFS R/W queue: FCFS and readers are served
concurrently. Further, we assume that writers arrive rarely, compared to readers.
Let us calculate E[Ww ], the expected waiting time for a W lock. We need to know the distribution
of the number of R locks in front of the W lock when the W lock enters the queue. If W locks arrive
rarely, the distribution of the number of R locks in the queue will approach a steady-state M=M=1
distribution. If N r is the number of R locks in the queue when a W lock arrives, then, from [13]:
Let Ww (n) be the waiting time for a W lock if n R locks are in the queue when the W lock enters.
Then, from Corollary 1,
r
Combining (17) and Corollary 1, the unconditional distribution of Ww is:
r
In [5], we find the formula:X
The exponential integral can be algebraically obtained from G 1 (x), so we can't expect to simplify
into a closed form. Combining (18) and (19), we get:
Theorem 2 The expected waiting time for a W lock in a one-writer queue is:
Let us next calculate the expected waiting time for a R lock. An R lock waits only if there is a W
lock in the queue ahead of it. If the R lock arrives when the W lock is in service, the R lock will have to
wait for the renewal time of the W lock service. Since we are assuming exponentially distributed service
times, the expected renewal time is 1=w . The probability that the R lock will arrive when a W lock is
in service is W =W .
An R lock will arrive while the W lock is waiting with probability E[Ww (as there is at most one
W lock in the queue at a time). The R lock will have to wait for the service time of the W lock (1=W )
plus the remaining time to serve the readers ahead of the W lock. This is the renewal time of the W
waiting time distribution. From [13], this is given by
is the first moment of the waiting time distribution and m 2 is the second moment. We have
already calculated the first moment (E[Ww ]), so all we need to do is calculate the second moment.
From Lemma 1, the distribution of the time for n readers to finish service is:
d
dt
Pr[S r (n)
Using the distribution of the number of readers (17), the distribution of Ww is:
d
dt
Next, we find the second moment:
ijo
dt
io
(ir
io
In order to simplify the sum, let us express
as a recursive relation:
Since
the first sum is simply g n\Gamma1 . From [21], the second sum is just
Therefore:
Our problem reduces to finding a simpler form of
The gn function has a simple difference. This suggests that we consider V (x) to be the exponential
generating function of gn , and try to find a relationship that leads to a solution for
The derivative operator will let us calculate a difference in an exponential generating function. Assuming
that
dV
dx
x
linear differential equation, so we can apply the formula for the solution
of first order linear differential equations [22],
dV
dx
R P dx
'Z
Qe
R P
\GammaR e x
x
In order to find the value of the constant c, evaluate V (0) and find that
The function G 2 (x) is also a transcendental function, so we cannot hope to simplify V (x) further. By
using the formula for V (x) (24) and the formula for the renewal time (21), we get:
Lemma 4 The expected residual time of Ww is
Now that we have calculated r 1 [Ww ], we can calculate E[W r ] by:
which gives:
Theorem 3 The expected wait for a reader in the one-writer queue is:
The throughput of the one-writer queue is limited by the arrival rate at which there always is a
writer in the queue. The expected length of time that a W lock is in the queue is 1=w +E[Ww ]. Using
Theorem 2, we get:
Corollary 6 The throughput of the one-writer queue is limited by
Proof: When the arrival rate over the service rate equals one, there will always be a W lock in the
queue. Therefore, the arrival rate must be less than or equal to the service rate ffl
3.1 Asymptotics
The functions G 1 (x) and G 2 (x) are transcendental functions, so they cannot be simplified into familiar
functions. Their power series forms aren't completely satisfactory for calculations either. While both G 1
and G 2 grow slowly, the maximum terms in their power series grow rapidly, so that for even relatively
small values of x (about 35), limited precision algorithms cannot calculate the functions. Fortunately,
both G 1 and G 2 have simple asymptotic representations.
The function G 1 (x) is related to the exponential integral by
is the exponential integral [14],
x
e \Gammat
dt
has the following asymptotic expansion [14]:
x
where
If we use the first asymptotic expansion (use R 0 (x)), we can bound E 1 (x) by
Therefore we can approximate G 1 (x) by
with an error of less than e \Gammax =x.
We can use the asymptotic form of G 1 (x) to get an asymptotic formula for G 2 (x) by integrating.
has a zero at has a removable singularity at
as Therefore, break the interval of
integration [0; x] into two parts, [0; a) and [a; x]. On the first interval, we integrate the power series
representation of G 1 (x) and get the value G 2 (a). On the second interval, we integrate the asymptotic
form of
R x
a
The constant c 2  :9891 can be evaluated by using the power series of G 2 to evaluate G 2 (a). The error
is bounded by
a
x dx
a e \Gammax =x 2 dx
4 The Reader/Write-Upgrade/Writer Queue
In this section, we use the results of section 3 to analyze the reader/write-upgrade/writer queue. The
R/U/W queue uses three types of locks: read, write-upgrade, and write locks, which we abbreviate sa R,
U and W locks, respectively. W denote the arrival rates of the R and U locks by R and U , respectively.
We assume that some proportion of the U locks upgrade to W locks. We denote the service rates of the
R and W locks by R and W , respectively. The service time of a U lock depends on the waiting time of
a W lock. We assume that the  r AE u , and that U locks are rarely upgraded to W locks. The result is
that  r AE w , and that writer arrivals are rare. Because of the assumptions, the results of the previous
section apply. (The assumptions are safe when the queue is applied to concurrent B-tree algorithms, for
example [3, 11]).
The R locks will be blocked only by a W lock. A U lock may be blocked by a W lock or by another
U lock. A W lock comes from a conversion request from the current U lock only, and is blocked by all
of the R locks currently in service. Thus, R locks block U locks only by blocking a W lock conversion.
This leads us to consider strategy of modeling the R/U/W queue as two queues, one for the R and W
locks, and one for the U locks.
In the R/W queue, R locks are served simultaneously. If a W lock enters the queue, the W lock must
wait for the preceding R locks to finish service before obtaining control of the queue. All R locks that
enter the queue after the W lock must wait until the W lock finishes service. In the U queue, U locks
receive FCFS service. The U lock in service might be upgraded to a W lock. The W lock blocks all U
locks. Therefore, the R/W queue and the U queue are coupled by increasing the service time for a U
lock by the expected service period (waiting time and service time) of a W lock.
We can now list the waiting times for the three types of locks.
W: the waiting time for a W lock is the time for all preceding R locks to finish.
R: the waiting time for an R lock is:
Pr[W lock is waiting]*[(W service)+(time for surviving R's to finish)]+ Pr[W lock in service]*(time
for W to finish service).
U: the waiting time for a U lock is the the waiting time for a customer in a FCFS queue. The arrival
rate is U and the service time is:
service period)).
c be the probability that a U lock converts to a W lock. Then
U be the expected time to service a U lock if the lock does not upgrade to a W lock.
U be the expected time to service a U lock if it upgrades to a W lock.
Therefore, the input parameters for the queue are R , U , R ,
U and T u
U .
Theorem 2 gives the expected wait for a W lock. Theorem 3 gives the expected
wait for a R lock.
All that needs to be done is to calculate the expected wait for a U lock. The expected service time
for a single U lock is:
Therefore, the utilization of the U lock queue is:
ae
If we model the U lock queue as a M/M/1 queue then, from [13],
Theorem 4 The expected waiting time for a U lock in the R/U/W queue is
Since W locks are generated from U locks, the throughput of the R/U/W queue is limited by the
service of the U locks.
Corollary 7 The throughput of the R/U/W queue is limited by
U +G1 (r=r )=r
4.1 Comparison and Experiments
A R/U/W queue was built and experiments run. Six hundred thousand samples were taken. Table 3
shows a comparison between analytical and simulator results. Since the one-writer queue and the R/U/W
queue are so similar, the comparison applies to the one-writer queue also. The comparison shows that
the analytical model predicts waiting times well. The accuracy of the analytical model improves as the
reader arrival rate increases.
Conclusions
We have developed a simple yet accurate model of FCFS reader/writer queue performance. We present
formulae to predict the shared resource capacity, waiting times for read and write locks, and the arrival
rates that produce a desired system loading. The formulae are simple enough to be used in a rule of
thumb by a system designer.
We extend the analyses to handle one-writer queues, and write-upgrade locks. We present formulae
to predict lock waiting times, and an estimate of the capacity of the shared resource. The locking queues
analyzed in this paper are used in many areas, such as concurrent data structures [11] and communications
channels [15].



--R

Construction of the stationary regime of queues with locking.

Concurrency of operations on B-trees
Concurrency Control and Recovery in Database Systems.
An Introduction to the Theory of Infinite Series.
On the modeling of parallel access to shared data.

Optimization of the number of copies in a distributed database.
Optimal control of a queuing system with simultaneous service requirements.
Stability of a queuing system with concurrent service and locking.
The Performance of Concurrent Data Structure Algorithms.
A framework for the performance analysis of concurrent B-tree algo- rithms
Queueing Systems
Calculation of Special Functions: The Gamma Function
Spider Systems Ltd.
Difference Equations.
Probabilistic models of database locking: Solutions
Analysis of a replicated database.
The stability and latency of concurrent-x exclusive-y
Performance analysis of concurrent-read exclusive-write
Combinatorial Identities.
Differential Equations with Applications and Historical Notes.
Locking performance in centralized databases.
Analysis of a threshold policy for scheduling readers and writers.
Analysis of a threshold policy for scheduling readers and writers.
Performance evaluation of a threshold policy for scheduling readers and writers.
--TR
performance analysis;lock queue;queuing system;concurrent system;reader/writer