Information Technology Reference
In-Depth Information
utexas.edu/users/EWD/transcriptions/EWD01xx/EWD123.html
)
. The Sleep-
ing Barber problem is illustrative of a system where several threads need to ren-
dezvous with another thread that provides some service to them (e.g., several
document editor threads printing documents via a printer driver thread.)
In our version, there is a barbershop with one barber chair and a waiting
room with
NCHAIRS
chairs. The barber arrives every morning. When the shop is
open, while there are customers in the shop, the barber cuts one customer's hair
at a time. While the shop is empty of customers, the barber naps in the barber
chair. At closing time, a clock rings an alarm, the barber hangs a \closed" sign,
cuts the hair of anyone already in the shop, and then departs when the shop is
empty.
When a customer arrives at the shop, if the shop is closed, the customer
departs. Otherwise, the customer enters the shop. Then, if the barber is asleep,
the customer wakes the barber, if there is a free waiting room chair, the customer
sits down to wait, but if all waiting room chairs are full, the customer leaves.
Waiting customers are served in FIFO order.
Figures 5.16 and 5.17 show our solution.
We represent the barber shop as a shared object
BarberShop
and the bar-
ber, quitting-time clock, and each customer as a thread. The barber will
call
BarberShop::barberDay()
to open the shop. Each customer will call
BarberShop::getHairCut()
, which returns true if the customer succeeds in get-
ting a haircut or false if the customer fails because the shop is closed or full. Fi-
nally, at some point the clock thread will call
BarberShop::clockRingsClosingTime()
to tell the barber to close shop.
As you can see in Figure 5.17, a barber's day is not an atomic action. In
particular, customers can continue to arrive while the barber is cutting hair
(we're using the Sleeping Barber problem to model a system where we have
a worker thread doing work that arrives and lands in a queue.) So, rather
than holding the lock across
barberDay()
, we break
barberDay()
into three
pieces,
openStore()
,
waitForCustomer()
, and
doneCutting()
, each of which
(as per rule #2) holds the lock from start to nish. The barber \cuts hair"
by printing a message using
printf()
; this step represents IO or some CPU-
intensive calculation in a more realistic problem.
These
openStore()
,
waitForCustomer()
, and
doneCutting()
actions by
the barber and
getHairCut()
action by customers are straightforward manipu-
lations of shared state while holding the lock and waiting as appropriate. Notice
that in
waitForCustomer()
we use a variation of
wait()
that not only returns
when signalled but also if some specified wallclock time is reached; we use this
timeout to close the shop at the end of the day.
In
doneCutting()
we use
broadcast()
rather than
signal()
since several
customers can be waiting, but only the customer with
custId==cutCount
can proceed.