Information Technology Reference
In-Depth Information
//Naive,polling-basedimplementationof
//removethatwaitssoitcanalwaysreturn
//anitem.
int
TSQueue::remove()
{
intret;
boolempty;
do{
empty=tryRemove(&ret);
}until(!empty);
returnret;
}
Figure5.6: A naive, polling-based implementation of
remove()
from a
bounded queue that retries in a loop until it succeeds in removing an item.
The method
tryRemove()
is defined in Figure 5.3.
in each region to finish, or in our Earth Visualizer example, a thread in charge
of rendering part of the screen might wait either for a user input that shifts the
scene or for new data to update the view.
Broadly speaking, what we want to do in all of these cases is have a thread
wait for something else to change the state of the system so that it can make
progress.
One way to have a thread wait for another thread to act would be to poll -
|repeatedly check the state of interest.
For example,
TSQueue
could wrap
Denition: poll
tryRemove()
in a polling loop to provide a
remove()
method that always re-
turns an item as shown in Figure 5.6. Unfortunately, such an approach can
be inecient because waiting threads continually loop, consuming CPU cycles
without making useful progress. Worse, it might delay the scheduling of the
other threads|perhaps exactly the ones for which the looping threads are wait-
ing.
A \x" to the polling-based approach is to add a delay. For example, in Fig-
ure 5.6, we might sleep, yielding the processor, for 100ms after each unsuccessful
tryRemove()
call so that there is a 100ms delay after a failed attempt.
This approach has two problems. First, although it reduces the ineciency
of polling, it does not eliminate it. Suspending and scheduling a thread imposes
nontrivial overheads, and if a program has a large collection of threads polling
every few tens or hundreds of milliseconds, they may still consume significant
resources. Second, periodic polling adds latency. In our hypothetical Google
Earth example, if the thread waiting for keyboard input waited 100ms between
each check, the application might become noticeably more sluggish.
As an extreme example, one of the authors once had an employee implement
a network server that provided several layers of processing, where each layer had
a thread that received work from the layer above and sent the work to the layer
below.
Measurements of the server showed surprisingly bad performance; we
