Barbershop Queue Demo
Posted: February 9, 2009 Filed under: concurrency 9 CommentsYet another classic concurrency problem.
This time, we have a barbershop. The shop employees one or more barbers. Customers come into the shop. If one of the barbers is free, he will give the customer a haircut. If all barbers are busy, the customer will wait in line until one of the barbers can take care of him. Barbers will handle customers on “first come first serve” basis. Of course, we don’t want to have two barbers working on the same customer at the same time, or giving haircuts to customers who no longer need them. We also don’t want barbers blocking each other, or blocking the entrance to the shop while working.
Its a nice problem, because you can check different queuing scenarios – fixed number of barbers while the number of customers grows, or how many barbers are needed to operate a shop with about 10 customers every second.
Normally, you would start one process running add_customers, with parameters telling it how many customers on average enter the shop every second, and how long should the demo run.
Then you add a process for each barber, with parameters for how long it takes to give a haircut, and how long the demo will run.
Something like:
(echo exec barber_shop.add_customers\(3,60\) | sqlplus -s scott/tiger)&
(echo exec barber_shop.add_barber\(0.3,60\) | sqlplus -s scott/tiger)&
(echo exec barber_shop.add_barber\(0.3,60\) | sqlplus -s scott/tiger)&
(echo exec barber_shop.add_barber\(0.3,60\) | sqlplus -s scott/tiger)&
Comments are welcome 🙂
Note: On rare occasions, the “add_customers” process waited over a minute between updating the customers and committing. “add_barber” did not run at all during that minute.
I suspect either my OS getting stuck somewhere or Oracle’s resource manager. However, when it happened I did not check v$sesstat or ASH to see what happened during that minute. Now it doesn’t reproduce, and I don’t have the session_id that had the issue to investigate.
If anyone tries running my code and runs into the same bug, please collect helpful events and timed statistics that may help debug it. I’ll buy a beer to anyone providing information that helps catch the bug (unless they are non-drinkers, in which case they can get orange juice 😉 ).
Just a simple Hadoop DBA 
Hi Chen,
Nice new coding style 😉
I ran the code three times and no bug to be found here. So much for the Hoegaarden.
Small detail: when you want an average of 3 customers per second, you’ll have to add one to your current expression. Now it’s effectively returning numbers between 0 and 5, leading to an average of 2.5 .
Regards,
Rob.
Hi Chen,
Another brilliant piece for concurrency. You really should write a book on Oracle! Anyways, I am a beta tester for 11gR2 so will be fun to see how any changes occur between 11gR1 and 11gR2 with your scripts and testing RAC for locking and latching processes. By the way, I am again on the hunt for new hidden Oracle parameters 🙂
Cheers,
Ben
@Rob
Well, you did find a bug with the customers number, so Hoegaarden on me, next time we happen to be at the same conference 🙂
And thanks again for the quick and useful code review.
@Ben
Did you read Alex Fatkulin’s posts about mutexes and latches in 11g? It’ll be interesting if you notice any changes/improvements in 11gR2.
Regarding the delayed add_customers() call.
I think that add_customers() waits for the add_barber() call to complete. This may happen as I believe that inbetween materializing the resultset for the subquery in add_customers() that identifies your ID list and carrying out the update, that it may be possible for some IDs in the ID list to have been updated by add_barber(). As a result add_barber() blocks add_customers().
You should be able to test this theory by making the subquery run slow enough for you to manually carry out an update in another session. Maybe a call to dbms_lock.sleep within the subquery?
I think both Tanel Poder and Jonathan Lewis have some examples of how to slow down queries sufficiently to allow you to do this – I can’t post a link at the moment.
I was sure that I’d read in the Oracle doco that this is how read consistency works for subqueries, but couldn’t find a link.
I’m interested to find out if you manage to reproduce this as I describe.
BTW – these concurrency posts are gold. Keep up the good work!
Best Regards,
Mathew Butler
Hey Mathew,
Currently my best suspicion for the cause of the bug is the fact that the fan on my CPU was dying at the time the tests ran.
The delay I’ve seen could not have been just add_barber() blocking add_customer(), since I’m talking about good 60 seconds delay.
It will be nice to try to slow everything down and verify that no blocking occur. I’ll try that one.
Chen,
doesn’t look like it would cause the bug you saw but I think this is not working as intended from the add_barber process:-
cursor c is select * from customers where needs_cut=1 order by entered_shop for update skip locked;
so when a barber becomes available he locks all the customers currently waiting then gives them a haircut in order if another baber becomes available he will not be able to get the lock on the customers queuing for the first barber. This would lock just the customer waiting the longest but is a more expensive query.
cursor c is select * from customers where needs_cut=1 and
entered_shop = (select min(entered_shop) from customers)
for update skip locked;
Also you could write the add customer procedure differently I did it as follows to give (if memory and the internet are not misleading me) a poisson distribution.
procedure add_customers(p_avg_customers_per_sec number,p_max_duration number) as
l_start_time date;
begin
wait_for_synchronisation; — to let all processes start at the exact same time
l_start_time := sysdate;
loop
dbms_lock.sleep(-ln(dbms_random.value)/ p_avg_customers_per_sec);
exit when sysdate > l_start_time + numtodsinterval(p_max_duration,’second’);
update customers set needs_cut=1,entered_shop=systimestamp
where id in (
select id from (select id from customers where needs_cut=0 order by dbms_random.random) where rownum<=1
);
commit;
log(‘customers entered shop at ‘ || systimestamp);
end loop;
end add_customers;
Chris
Further to my post above, re-reading the code I think for my change to the cursor you would need to add a new status for the customer record to indicate ‘hair being cut’ otherwise only one customer will get cut at a time.
Chris
[…] simple queuing PL/SQL calcuations.. A couple of posts by Chen Shapira, (this one barbershop-queue-demo and this one random-thoughts-about-queues) over at prodlife.wordpress.com regarding queuing in […]