Introduction
The Concurrency Explorer (ConcX) provides the tools and features to explore and solve a variety of parallel or asynchronous problems, including the Sleeping Barber problem, described by Wikipedia as follows:
“In computer science, the sleeping barber problem is a classic inter-process communication and synchronization problem between multiple operating system processes. The problem is analogous to that of keeping a barber working when there are customers, resting when there are none, and doing so in an orderly manner.
The analogy is based upon a hypothetical barber shop with one barber. The barber has one barber's chair in a cutting room and a waiting room containing a number of chairs in it. When the barber finishes cutting a customer's hair, he dismisses the customer and goes to the waiting room to see if there are others waiting. If there are, he brings one of them back to the chairs and cut their hair. If there are none, he returns to the chair and sleeps in it.
Each customer, when they arrive, looks to see what the barber is doing. If the barber is sleeping, the customer wakes him up and sits in the cutting room chair. If the barber is cutting hair, the customer stays in the waiting room. If there is a free chair in the waiting room, the customer sits in it and waits their turn. If there is no free chair, the customer leaves.”
The Wikipedia article then discusses a variety of concurrency problems, such as:
-
the barber and the newly-arrived customer check each other’s status at the same time so they deadlock because at that moment:
-
The barber sees no one sitting in a chair and thinks the waiting room is empty so goes to sleep
-
The customer thinks the barber is busy so doesn’t try to wake up the barber and just patiently waits for the barber
-
two customers arrive at the same time, see the barber is already busy, and then both try to sit in the same chair, causing either:
Other concurrency problems can also occur depending on how well inter-process communications have been defined. But before you get that far away look in your eyes and start mapping out your code solution in your head, consider using the ConcX to solve the Sleeping Barber problem.
Solving the Sleeping Barber Problem
The Concurrency Explorer (ConcX) is a free, open source tool available from the Avian Computing Project. ConcX is an interactive GUI tool designed to help us think about parallel problems. ConcX encourages us to imagine a parallel problem/program as resembling a flock of birds where each bird behaves (eats, sleeps, etc) and operates independently but also competes and cooperates with the other birds in the flock.
The Customer, Barber, ShopManager and Chair objects are all provided as part of the ConcX download. You could add one or more of each of these objects one by one or you can just load the barbershop20cust.bird file, included in the standard ConcX download. This file will load and configure one barber, one shop manager, and twenty customers.
When the objects are done loading, ConcX will look like the following screenshot:
The numbered tabs on the left represent the birds that were loaded and configured to perform the roles of the barber and customers. You can click on the individual tabs to see configuration details of each bird. In the center of the screen is a list of the names and types of the birds next to their individual progress bars. Each time a bird (Barber, Customer, or ShopManager) successfully “eats”, its progress bar will grow. The progress bars are updated in real time so there is no need to wait until a run is completed to see if every thread is working as desired.
Click the Start All button at the bottom left of the screen. The activity progress bars on the right side of the ConcX screen will start to grow in relation to how many times each bird successfully eats (see the following screenshot).
Each Customer’s progress bar will only grow while they are actually waiting. Each Customer’s arrival time was pre-configured so they don’t all arrive at the same time. When Customers can’t find a chair, they give up and leave. If a customer waits too long (individually configured), they give up and leave. Customers who successfully get a haircut (or give up) will terminate their thread and their progress bar will stop growing.
Each time the barber gives a haircut, his progress bar will grow; if there is only one customer, the barber’s progress bar will only grow once. Only the shop manager’s progress bar will keep growing throughout the run because he is constantly checking for updates to make to the haircuts reports. When his line stops growing, click on the TupleTree tab (upper right of the screen) to see the results of the run. More about the TupleTree later in this document.
Sleeping Barber Results
The following screenshot shows the contents of the TupleTree after running the standard Sleeping Barber solution. The DailyTransactionPod contains the reports that were generated and continuously updated by the ShopManager.
The reports include:
-
the names of customers who received haircuts and the barber(s) who gave those haircuts
-
The names of customers who couldn’t find chairs or ran out of patience and left. Both represent lost opportunities.
-
A list of haircuts by barber
-
A list of when each customer was called but was absent
Note that the Customers are all listed in alphabetical order. That’s because Customer #1 thru Customer #20 were all given names in alphabetical order and arrive in that order. That makes it easy to figure out if the customers do in fact get their haircuts in order of their arrival.
Here’s the full report, copied from the TupleTree screen
Customers Completed Report
CustName Arrvd At Start At FinishAt $Paid BarberName
Adambb9 17:001 17:060 18:060 $10.00 Zeb
Bertc4a 17:919 18:075 20:075 $20.00 Zeb
Chada24 18:937 20:098 23:099 $30.00 Zeb
Dave9e1 20:954 23:133 24:633 $15.00 Zeb
Evanb05 22:972 24:662 27:163 $25.00 Zeb
Greg14f 27:007 27:549 29:550 $20.00 Zeb
Hanka66 27:026 29:605 32:606 $30.00 Zeb
Ivan42a 27:045 32:631 34:132 $15.00 Zeb
Jake3da 31:060 34:167 36:668 $25.00 Zeb
Kentbd3 33:077 36:679 37:680 $10.00 Zeb
Lukebe8 34:096 37:746 39:747 $20.00 Zeb
Mark2f9 36:113 39:756 42:756 $30.00 Zeb
Natef97 37:131 42:764 44:265 $15.00 Zeb
Otto7d3 39:149 44:302 46:803 $25.00 Zeb
Todde18 42:233 48:249 50:750 $25.00 Zeb
-----------------------------------------------
Customers Who Gave Up or Couldn't Find a Chair
CustName Arrvd At Gave Up At
Fredc86 23:089 26:100
Petec74 39:170 39:170
Quin77b 39:189 39:189
Rami325 39:207 39:207
Stan621 39:226 39:226
-----------------------------------------------
Barber Productivity Report
Barber Name Haircut Amt Haircut Time
Zeb $10.0 10 minutes
Zeb $20.0 20 minutes
Zeb $30.0 30 minutes
Zeb $15.0 15 minutes
Zeb $25.0 25 minutes
Zeb $20.0 20 minutes
Zeb $30.0 30 minutes
Zeb $15.0 15 minutes
Zeb $25.0 25 minutes
Zeb $10.0 10 minutes
Zeb $20.0 20 minutes
Zeb $30.0 30 minutes
Zeb $15.0 15 minutes
Zeb $25.0 25 minutes
Zeb $25.0 25 minutes
-----------------------------------------------
Barber Called Absent Customer Report
Barber Name Cust Name Called At
Zeb Fredc86 27:534
Zeb Petec74 47:166
Zeb Quin77b 47:482
Zeb Rami325 47:841
Zeb Stan621 48:202
-----------------------------------------------
Note that there were 5 customers who gave up waiting (1 waited too long and 4 couldn’t find a chair). The report shows that Fred waited for about 3 seconds before giving up, which matches his patience setting of 3 seconds. The other 4 customers have arrival times and departure times that are nearly identical, which indicates that they all left because they couldn’t find a chair. Since the Arrival Time for Otto, Pete, Quin, Rami, and Stan are within 80 milliseconds of each other, it shows that they all came in as a group but only Otto found a chair and got a haircut.
Let’s see how making a few changes affects the results.
Exploring Sleeping Barber Possibilities
The following screenshot shows that tab #1 (Mr Smith, the Shop Manager) has been selected and that his Externally Managed Variable (XMV) tab has also been selected. The “Chairs in Waiting Room” field was blank, meaning that the ShopManager put out the default number of chairs (3). By updating the XMV field to 5 we can rerun the simulation to see if adding more chairs fixes the problem. No re-compiling required.
Click the “Clear All Activities” button in the bottom right corner and then click the Start All button in the bottom left corner of the screen.
The following report excerpt shows just the customers who gave up:
Customers Who Gave Up or Couldn't Find a Chair
CustName Arrvd At Gave Up At
Fredbd3 39:798 42:904
Rami226 55:812 55:812
Stan7f5 55:819 55:819
-----------------------------------------------
<meta charset="utf-8" />
Now only three customers gave up: Impatient Fred and the last two in the group of five who came in together. If we add a couple more chairs, clear the results and then rerun the simulation, the Customer Gave Up portion of the report will contain only Impatient Fred.
But what if the barbershop is small and doesn’t have room for 7 chairs? It would be pretty expensive to expand the shop for just those rare occasions when 5 or more customers arrive all at once. Let’s see what happens if we add a second barber instead of adding more chairs.
First, click on tab #1 and blank out/zero out Mr Smith’s Chairs in Waiting Room value.
Next, click the Add New Bird button (bottom center of the screen) and add a new Barber bird as follows:
Click on Add New Bird button and then
-
(Bird) Type: type “bar” in the Type field and press Tab. ConcX will find multiple bird types that begin with “bar” and will pop up a ComboBox populated with all matching items. If not already highlighted, select the Barber.class and click on the OK button.
-
Food Eaten: type “bar” in the Food Type field and press Tab. ConcX will find multiple food pods that begin with “bar” and will pop up a ComboBox populated with all matching items. If not already highlighted, select the BarberBacklogPod and click on the OK button.
-
Food Stored: type “null” in the Food Type field and press Tab. ConcX will find only one matching food pod and fill in the full name of NullPod
-
Give the Barber an appropriately casual name, such as Yank or Willy
-
Click on the Barber’s Vitality tab and change his Stamina to a negative number, such as -5000. Negative numbers prevent a bird from dying if it goes too long without eating.
Click the Clear All Activities button and then Click the Start All button.
When the run is finished, the Shop Manager’s results will be similar to the following:
Customers Completed Report
CustName Arrvd At Start At FinishAt $Paid BarberName
Adam81e 57:134 57:136 58:136 $10.00 Zeb
Bertfaa 58:050 58:084 00:085 $20.00 Yank
Chad422 59:067 59:079 02:079 $30.00 Zeb
Dave5a8 01:085 01:121 02:620 $15.00 Yank
Evan447 03:102 03:108 05:608 $25.00 Zeb
Freda5f 05:118 05:137 06:137 $10.00 Yank
Greg4a4 07:135 07:142 09:142 $20.00 Zeb
Hankac2 07:153 07:191 10:191 $30.00 Yank
Ivan8fe 07:171 09:171 10:672 $15.00 Zeb
Jake753 11:185 11:240 13:740 $25.00 Yank
Kent3a6 13:203 13:235 14:235 $10.00 Zeb
Luke0cb 14:219 14:233 16:233 $20.00 Yank
Nate4cf 17:253 17:275 18:775 $15.00 Zeb
Mark0b8 16:236 16:252 19:253 $30.00 Yank
Petedb7 19:290 19:321 20:321 $10.00 Yank
Otto736 19:272 19:299 21:798 $25.00 Zeb
Quin94d 19:309 20:330 22:330 $20.00 Yank
Toddee5 22:354 22:371 24:870 $25.00 Yank
-----------------------------------------------
Customers Who Gave Up or Couldn't Find a Chair
CustName Arrvd At Gave Up At
Ramif1e 19:327 19:327
Standec 19:346 19:346
-----------------------------------------------
Barber Productivity Report
Barber Name Haircut Amt Haircut Time
Zeb $10.0 10 minutes
Yank $20.0 20 minutes
Zeb $30.0 30 minutes
Yank $15.0 15 minutes
Zeb $25.0 25 minutes
Yank $10.0 10 minutes
Zeb $20.0 20 minutes
Yank $30.0 30 minutes
Zeb $15.0 15 minutes
Yank $25.0 25 minutes
Zeb $10.0 10 minutes
Yank $20.0 20 minutes
Zeb $15.0 15 minutes
Yank $30.0 30 minutes
Yank $10.0 10 minutes
Zeb $25.0 25 minutes
Yank $20.0 20 minutes
Yank $25.0 25 minutes
-----------------------------------------------
Barber Called Absent Customer
Barber Name Cust Name Called At
Zeb Ramif1e 22:124
Zeb Standec 22:457
-----------------------------------------------
<meta charset="utf-8" />
A couple of things to note in these results:
-
With two barbers, Impatient Fred got his haircut because he didn’t have to wait too long
-
Just two customers gave up because they couldn’t find a chair
-
The Completed Customers Report lists customers in order of their haircut's completion and not in the order of arrival. This demonstrates that the barbers are working together but asynchronously; one barber never has to wait for the other barber to finish but always goes on to the customer who has been waiting longest.
-
The Shop Manager knows which barber performed which haircuts without having to reprogram anything.
Let’s add a third barber and see what happens. Click the Add New Bird button and add another barber bird as described above. Now click the Clear All Activities button and then the Start All button.
After re-running the simulation, we get the following results:
Customers Who Gave Up or Couldn't Find a Chair
CustName Arrvd At Gave Up At
Ramibea 11:000 11:000
Stanf61 11:018 11:018
-----------------------------------------------
<meta charset="utf-8" />This result shows that adding a third barber didn’t help; the same two customers still could not find a chair. So let’s fire the third barber (disable his thread by changing his Type to Not Found) and changing the number of chairs in the waiting room to 4. Now when we Clear All Activities and Start All, every one of the 20 customers is able to get a haircut.
Which means that we've been able to identify two different ways that every customer could be served:
- by increasing the number of waiting room chairs to 7
- by adding a second barber and also increasing the number of waiting room chairs to 4
<meta charset="utf-8" />
ConcX Concepts
Let's take a look at the foundational concepts of ConcX. Using the ideas in Avian Computing, ConcX maps the various thread states into the natural behaviors of a bird, such as hatching (thread.start), napping (thread.sleep), death (thread.stop) and so on to make it easier to think about and describe each thread’s actions. Each bird follows a standard life cycle; once they are hatched, they look for food, digest it if they find their type of food, store any resulting foods (the way some birds will hide leftover food), and then take a nap. When the birds get too old or can’t get enough to eat, they die. Expressing the threads’ actions in natural terms is done to make it easier and more natural to think about the threads.
<meta charset="utf-8" />
Each “bird” (thread) in ConcX eats one type of food pod and stores one type of food pod in the “TupleTree”. The TupleTree in ConcX is a simplified version of a tuplespace, a concept originally developed for the Linda coordination language. A tuplespace is shared associative memory used as a repository for tuples of data. Linda was originated in 1986 by Sudhir Ahuja, David Gelernter, Nicholas Carriero and others. Linda was the foundation for several major products, including Sun’s JavaSpaces, IBM’s TSpaces, and many more in a variety of languages.
In ConcX, the TupleTree is a singleton that shares data with all the birds using synchronized methods. Any object in the TupleTree can be retrieved by any bird that knows to ask for that type of object. Because the TupleTree manages its objects using synchronized methods, there is never a need for users to create or code mutexes or locks or any other mechanisms for concurrent objects to sharing objects. Instead, the TupleTree manages all sharing of data so you can concentrate on what needs to be done with the data.
The traditional concurrency tools of wait and notify are like a traditional phone system; if the person on the other end of the phone is available when you call them, it works great. Unfortunately if both parties aren’t available at the same time, nothing can happen.
Linda is more like an email system, where the senders and receivers check for and respond to emails at their convenience instead of interrupting each other. In ConcX, the TupleTree is like an email server except it holds food pods that function as shared resources. In this way, Linda provides a safe, simple and robust mechanism for data sharing between multiple asynchronous threads.
Runtime Information in ConcX
One of the original goals of ConcX was to provide ready access to its runtime context, of what was happening to each thread while each one was running. To do this, ConcX provides more information than real-time updating of progress bars. ConcX automatically documents each run several ways, including:
-
Each food pod in the TupleTree has a complete time-stamped history of all events that occured to that individual food pod and which bird caused the event
-
Each bird maintains its own time-stamped history of its events, such as when it looked for food, what food it found, when it digested and stored its food, and so on.
The following excerpts will help to illustrate how the recorded information can be used. First, from the Chair-2 food pod left in the TupleTree at the end of the run, we can see when Bert sat in the chair (every customer who sat in Chair-2 on that run are also documented):
11:14:23:853,WaitingRoomChairPod,Bert78b found a chair in waiting room
11:14:24:127,WaitingRoomChairPod,Bert78b gave up chair to get haircut
<meta charset="utf-8" />
Next, here’s an excerpt from the personal history of Customer #2, Bert, available on his History tab:
11:14:23:853,Bert,Bert78b found a chair in waiting room
11:14:23:853,Bert,Created CustInfoFindByNamePod,Bert78b
11:14:23:853,Bert,Created BarberBacklogPod,Bert78b
11:14:23:853,Bert,Looking for food,
11:14:23:853,Bert,eating foodType,Bert78b
11:14:23:853,Bert,Napping,107ms
11:14:23:961,Bert,Looking for food,
11:14:23:961,Bert,eating foodType,Bert78b
11:14:23:961,Bert,Napping,166ms
11:14:24:127,Bert,Looking for food,
11:14:24:127,Bert,eating foodType,Bert78b
11:14:24:127,Bert,bird lifetime was set to 40300 millis
11:14:24:127,Bert,haircut in process
<meta charset="utf-8" />
Bert’s History shows that he found an empty chair (Chair #2) at 23:853. After waiting (Looking for food and napping) for about 250 milliseconds, Bert recorded that his haircut was in process at 24:127.
And to cross-check the information, the barber’s (Zeb) History shows that he was sleeping at 23:963, then got the next name from the waiting list (BarberBacklogPod) and then called him (Bert). There’s a short time lag (from 23:995 until 24:127) while Bert takes a 166ms nap but then the desired haircut (2000ms) is given (from 23:995 until 25:996).
11:14:23:963,Zeb,Napping,32ms
11:14:23:995,Zeb,Looking for food,
11:14:23:995,Zeb,Got 1 pods from TupleTree
11:14:23:995,Zeb,eating foodType,barbershop\BarberBacklogPod,Zeb
11:14:23:995,Zeb,Called Bert78b for haircut
11:14:23:995,Zeb,BEFORE Haircut retrieved Bert78b info on attempt 0
11:14:25:996,Zeb,AFTER Haircut retrieved Bert78b info on attempt 0
11:14:25:996,Zeb,ATE_FOOD1-->strFood1 NullPod,STORE_ONE by,barbershop\Barber
11:14:25:996,Zeb,Napping,49ms
While the excerpts shown above only confirm that the barbershop ran as expected, the combined histories of food pods and birds is most useful when things don't go as planned. The time-stamped history entries make it possible to reconstruct the runtime context, down to the state of each thread, when errors were encountered.
<meta charset="utf-8" />
Sleeping Barber Conclusions
The ConcX solution to the Sleeping Barber problem is significantly more complicated than the original problem described in Wikipedia, allowing multiple barbers, shop managers maintaining near real-time reports, impatient customers and more. It is also easier to run and to modify than most other solutions while providing better assurance that it did what it was supposed to do. The ConcX solution is also robust when it is scaled up; the screenshot below shows what happens when the barbershop flock file is loaded five times and then run. All 5 barbers and all 5 shop managers and all 100 customers just work as expected.
This article demonstrated some of the strengths of ConcX at exploring concurrent program solutions, including:
-
GUI environment for configuring and running multiple concurrent threads
-
Adding new threads as needed
-
Starting and stopping of individual threads or all threads at any time during a run
-
Simple modification of individual thread settings to help identify which settings are critical and which are unimportant
-
Real-time updating of the progress of every thread on GUI screen for immediate visual feedback for users
-
Timestamped event history of shared data objects, including which bird (thread) possessed the data object
-
Timestamped event history for every bird (thread) for every run with selectable levels of detail for each bird
ConcX was designed to support quick and easy modifications in a robust high-feedback environment to promote the exploration of concurrent programs. ConcX is a free open-source tool designed to promote higher level thinking about concurrent programs; ConcX lets us think about what we want the threads to do instead of thinking about how to code what we want them to do.
History
July 27, 2018: Initial publication of document
