Information Technology Reference
In-Depth Information
queue2
lock
item[0]
item[1]
...
nfull
firstFull
nextEmpty
queue1
lock
item[0]
item[1]
...
nfull
firstFull
nextEmpty
queue3
lock
item[0]
item[1]
...
nfull
firstFull
nextEmpty
Figure5.4: Three shared objects, each an instance of class
TSQueue
pointers) and synchronization variables (e.g., locks). Thus, every time we use a
class's constructor to produce another instance of a shared object, we allocate
both a new lock and new instances of the state protected by that lock.
Figure 5.3 defines a simple shared object, a thread-safe bounded queue. Our
implementation allows any number of threads to safely insert and remove items
from it. As Figure 5.4 illustrates, a program can allocate multiple such queues
(e.g.,
queue1
,
queue2
, and
queue3
), each of which includes its own lock and
state variables.
Notice that our queue stores only a bounded number of items. If the queue
is full, an insert request returns an error flag. Similarly, if the queue is empty,
a remove request returns an error flag. In the next section, we will show how
condition variables would allow us to instead wait until the queue has room on
insert or wait until an item is available on remove.
Also, to keep the example as simple as possible, we only allow items of type
int
to be stored in and removed from the queue, but the pattern can be used
for queuing anything.
The TSQueue implementation defines a circular queue that stores data in
an array,
items[]
. We maintain a number of simple invariants on the state.
nFull
indicates how many items are currently stored in the queue. If
nFull
is
nonzero, then
firstFull
is the index of the oldest item in the queue. If
nFull
is less than
MAX
, then
nextEmpty
is the index where the next item to be inserted
should be placed.
All of these variables are as they would be for a single-threaded version of
this object. The
lock
allows
tryInsert()
and
tryRemove()
to atomically read