September 12, 2013

Eating Pez With Ada

Back in May I wrote an article called Concurrent Ada Programming. It was meant as an introduction to the wonderful world of Ada tasking and protected objects, and while the code presented in the article most certainly did not muck about with complex constructions and mind-bending designs, it did however expose the reader to my rather feeble attempts at naming identifiers, as Georg Bauhaus was kind enough to point out to me:

Can I make some comments about the choice of identifiers? That’s from the perspective of a reader, totally subjective, of course. It reflects what had me a little confused at first, looking at the source (not the explanation). For example, there are: Jobs (Positive), Job (Natural), Jobs (protected), A_Job (Natural), Job as an immutable loop variable. And none of these is, well, if I may, a job (task). They are jobs’ numbers, though, as the output indicates.

This might all appear nitpicky, I guess. I always found good names helpful for understanding source from source, which is why…

Of course Georg is completely right, and because it did not appear nit-picky to me at all, I decided to code a completely new example, this time focusing on the beloved Pez dispenser. One Pez dispenser + several children = perfect situation to flex a bit of Ada tasking muscle. I've tried my best to name the identifiers properly, and I do believe I've done a marginally better job of it than in my previous article.

So without further ado, lets get on with the Ada programming, and check out a basic sequential Pez dispenser example (one child, one dispenser). Note that the example make use of an Ada 2012 feature, so you must have an Ada 2012 compiler to make it work. I've used the GNAT GPL 2012 compiler.

Before you read on, please clone the Pez_Dispenser project from my github account, so you have all the files available.



Looks nice eh? I am hopeful that it reads better than the example from my previous article, and if it doesn't, well then I think I'll just give up on this subject.

But for now lets assume that the example code is good, and do a quick rundown of what is going on.

First we with the two packages Ada.Task_Identification and Ada.Text_IO. What this does is make the subprograms and types from those packages visible and available to our program, somewhat analogous to the #include directive used in C. After that we setup our "main" procedure and name it Sequential. In Ada you can call your main procedure whatever you like.

The Ada.Task_Identification package makes it possible for us to figure out the id of a task and Ada.Text_IO makes the Put_Line procedure available to Sequential.

The use clauses we encounter next lets us access the tools of the Ada.Text_IO and Ada.Task_Identification packages without having to prefix every type and subprogram with the package name. This is equivalent to the using namespace statement in C++. Note that it is fairly easy to abuse use clauses to a point where your code becomes almost unreadable. Another option is using renames instead, for example like this:



But I digress. Lets get back on track!

Next up we declare and initialize the Task_Id constant. This is basically just a string representation of the internal id for the main environment task. Both Image and Current_Task are methods found in the Ada.Task_Identification package. We use the Task_Id constant to identify the task that is currently chewing on a snack.

After the Task_Id declaration, we define the new type Reward as an enumeration type with the possible values Candy and No_Candy. The Dispenser type is a record with a single component, Available_Candies, which is initialized with the value 20, meaning that all new dispensers comes loaded with 20 delicious candies. Not too shabby!

The Pop function takes a Dispenser and returns a Reward. If there are still candies in the dispenser, then it decreases the number of available candies by 1. Note that it is the D : in out Dispenser parameter in this function that requires an Ada 2012 compiler. Older versions of Ada only allow in parameters when using functions.

Finally we declare the Result variable as a Reward and the Pez_Dispenser variable as a Dispenser.

And that my friends was all the declaration stuff (the part between is and begin). Next up: The body of the program (the part between begin and end).

The meat of the body is the A_Child_Popping_Pez loop, in which the first thing we do is call the Pop function with our Pez_Dispenser and put the reward in the Result variable. After that we exit the loop if the reward given in Result is No_Candy. If the given reward is Candy we proceed with some chewing in the form of the delay 1.0 statement. This proceeds until all the candies are gone and the dispenser is empty.

When the loop exits we cheerfully let the world know that because there are no more candies, we might as well run out to play.

Let us compile and run the program:



You should now see something like this flow by:

thomas@t420:~/Ada/Pez_Dispenser/sequential$ time sequential
main_task_000000000064C010 pops a candy from the dispenser.
19 left in the dispenser
main_task_000000000064C010 is chewing on a candy.
main_task_000000000064C010 pops a candy from the dispenser.
18 left in the dispenser
main_task_000000000064C010 is chewing on a candy.
main_task_000000000064C010 pops a candy from the dispenser.
17 left in the dispenser
main_task_000000000064C010 is chewing on a candy.
main_task_000000000064C010 pops a candy from the dispenser.
16 left in the dispenser
main_task_000000000064C010 is chewing on a candy.
main_task_000000000064C010 pops a candy from the dispenser.
15 left in the dispenser
main_task_000000000064C010 is chewing on a candy.
main_task_000000000064C010 pops a candy from the dispenser.
14 left in the dispenser
main_task_000000000064C010 is chewing on a candy.
main_task_000000000064C010 pops a candy from the dispenser.
13 left in the dispenser
main_task_000000000064C010 is chewing on a candy.
main_task_000000000064C010 pops a candy from the dispenser.
12 left in the dispenser
main_task_000000000064C010 is chewing on a candy.
main_task_000000000064C010 pops a candy from the dispenser.
11 left in the dispenser
main_task_000000000064C010 is chewing on a candy.
main_task_000000000064C010 pops a candy from the dispenser.
10 left in the dispenser
main_task_000000000064C010 is chewing on a candy.
main_task_000000000064C010 pops a candy from the dispenser.
9 left in the dispenser
main_task_000000000064C010 is chewing on a candy.
main_task_000000000064C010 pops a candy from the dispenser.
8 left in the dispenser
main_task_000000000064C010 is chewing on a candy.
main_task_000000000064C010 pops a candy from the dispenser.
7 left in the dispenser
main_task_000000000064C010 is chewing on a candy.
main_task_000000000064C010 pops a candy from the dispenser.
6 left in the dispenser
main_task_000000000064C010 is chewing on a candy.
main_task_000000000064C010 pops a candy from the dispenser.
5 left in the dispenser
main_task_000000000064C010 is chewing on a candy.
main_task_000000000064C010 pops a candy from the dispenser.
4 left in the dispenser
main_task_000000000064C010 is chewing on a candy.
main_task_000000000064C010 pops a candy from the dispenser.
3 left in the dispenser
main_task_000000000064C010 is chewing on a candy.
main_task_000000000064C010 pops a candy from the dispenser.
2 left in the dispenser
main_task_000000000064C010 is chewing on a candy.
main_task_000000000064C010 pops a candy from the dispenser.
1 left in the dispenser
main_task_000000000064C010 is chewing on a candy.
main_task_000000000064C010 pops a candy from the dispenser.
0 left in the dispenser
main_task_000000000064C010 is chewing on a candy.
No more candy! main_task_000000000064C010 runs out to play.

real 0m20.004s
user 0m0.000s
sys 0m0.002s

As you can see it takes the main_task_000000000064C010 (you might get a different name on your system) child 20 seconds to chew its way through all the candies in the Pez dispenser.

We can make this go "faster" by adding some more children and have them share the dispenser. Lets see how we can do that using tasks and a protected object.



Not too complicated I should say. We with and use the same packages as before, but after that there are a few new things, first of which is a protected object. In Ada these are objects that export procedures, functions and entries that enables us to interact with the encapsulated data structure. In our case we’ve set up a protected object called Pez_Dispenser (effectively a singleton), but we could just as well have created a protected type and then declared one of more objects to be of that type, as we did with the Dispenser type in the sequential example.

We can only operate on the data structure of a protected object via the exported subprograms and this is done under automatic mutual exclusion. A protected object will allow many concurrent readers (via exported functions), but only one writer (via exported procedures and entries).

A protected object is just what we need to protect our Pez dispenser from race conditions (raging kids all grabbing for the same candy!), now that we have several tasks (children) querying and updating it.

Lets take a closer look at the code:



First we declare our Pez_Dispenser protected object where we export the sole Pop procedure, which is the only way for us to interact with the very simple data structure consisting only of the variable Available_Candies.

In the body of Pez_Dispenser we find the actual implementation of the Pop procedure. If Available_Candies is greater than 0 then Result is set to Candy, Available_Candies is reduced by 1 and a short message about who did the popping and how many candies are left in the dispenser is written to STDOUT. If Available_Candies is 0 then Result is set to No_Candy.

With this simple system in place we’re ensured that access to Available_Candies is only ever granted to one single task (child) at a time. As soon as one task is done popping a Pez, access is opened up to the next task.

With a secure Pez_Dispenser in place we move on to creating the tasks that will be doing the actual eating:



First we declare a task type called Child. We could’ve setup a task object, just as we did with the Pez_Dispenser protected object, but since we want more than one Child a type is the way to go. The body of the task looks a lot like the body from the Sequential program.

Inside the Child task we declare the Task_Id constant so we can identify each of the running Child tasks, and then we declare the Result variable to be of the type Reward.

In the body of the Child task we’ve got a plain named loop in which the first thing we do is try and pop a candy from the Pez_Dispenser. If Result equals No_Candy after having called Pop we immediately exit the loop and output the sad "No more candy!" message. If Result is Candy we Chew to our hearts content, again signified by the delay 1.0 statement.

Last we have this:



Here we declare the children Alice, Bob, Clair and Dwayne. As soon as the program reaches this spot, four Child tasks are created and when we pass begin they spring to life. Since we already have 4 children trying to get to the candy like there’s no tomorrow, we don’t really need to add any code to the main environment task, so we simply provide a null statement. The main environment task is the master of the 4 Child tasks, so it wont complete until all 4 Child tasks have completed.

Lets compile and see how the program performs now:



thomas@t420:~/Ada/Pez_Dispenser/concurrent$ time concurrent
bob_000000000065D2C0 pops a candy from the dispenser.
19 left in the dispenser
bob_000000000065D2C0 is chewing on a candy.
dwayne_0000000000663D80 pops a candy from the dispenser.
18 left in the dispenser
dwayne_0000000000663D80 is chewing on a candy.
alice_0000000000659D60 pops a candy from the dispenser.
17 left in the dispenser
alice_0000000000659D60 is chewing on a candy.
clair_0000000000660820 pops a candy from the dispenser.
16 left in the dispenser
clair_0000000000660820 is chewing on a candy.
bob_000000000065D2C0 pops a candy from the dispenser.
15 left in the dispenser
bob_000000000065D2C0 is chewing on a candy.
alice_0000000000659D60 pops a candy from the dispenser.
14 left in the dispenser
alice_0000000000659D60 is chewing on a candy.
dwayne_0000000000663D80 pops a candy from the dispenser.
13 left in the dispenser
dwayne_0000000000663D80 is chewing on a candy.
clair_0000000000660820 pops a candy from the dispenser.
12 left in the dispenser
clair_0000000000660820 is chewing on a candy.
bob_000000000065D2C0 pops a candy from the dispenser.
11 left in the dispenser
bob_000000000065D2C0 is chewing on a candy.
alice_0000000000659D60 pops a candy from the dispenser.
10 left in the dispenser
alice_0000000000659D60 is chewing on a candy.
dwayne_0000000000663D80 pops a candy from the dispenser.
9 left in the dispenser
dwayne_0000000000663D80 is chewing on a candy.
clair_0000000000660820 pops a candy from the dispenser.
8 left in the dispenser
clair_0000000000660820 is chewing on a candy.
bob_000000000065D2C0 pops a candy from the dispenser.
7 left in the dispenser
bob_000000000065D2C0 is chewing on a candy.
alice_0000000000659D60 pops a candy from the dispenser.
6 left in the dispenser
alice_0000000000659D60 is chewing on a candy.
dwayne_0000000000663D80 pops a candy from the dispenser.
5 left in the dispenser
dwayne_0000000000663D80 is chewing on a candy.
clair_0000000000660820 pops a candy from the dispenser.
4 left in the dispenser
clair_0000000000660820 is chewing on a candy.
bob_000000000065D2C0 pops a candy from the dispenser.
3 left in the dispenser
bob_000000000065D2C0 is chewing on a candy.
alice_0000000000659D60 pops a candy from the dispenser.
2 left in the dispenser
alice_0000000000659D60 is chewing on a candy.
dwayne_0000000000663D80 pops a candy from the dispenser.
1 left in the dispenser
dwayne_0000000000663D80 is chewing on a candy.
clair_0000000000660820 pops a candy from the dispenser.
0 left in the dispenser
clair_0000000000660820 is chewing on a candy.
No more candy! bob_000000000065D2C0 runs out to play.
No more candy! alice_0000000000659D60 runs out to play.
No more candy! dwayne_0000000000663D80 runs out to play.
No more candy! clair_0000000000660820 runs out to play.

real 0m5.012s
user 0m0.002s
sys 0m0.001s

There you have it. With 4 children attacking our Pez dispenser it takes a mere 5 seconds to empty it. Obviously the performance gains are normally not as linear as in this simple example where chewing each candy amounts to no more than a simple delay 1.0 statement. The performance gained from adding concurrency to a program depends on a lot of different factors.

The important point to get across is that adding concurrency to a program doesn't have to be complicated. Adding concurrency to an Ada program is very simple, and the model for doing it is easy, both to understand and to work with. When you're using Ada there's simply no excuse for not adding concurrency to your program where it will benefit from it.

There is of course a whole lot more to Ada and concurrent programming than shown here. This little example has barely scratched the surface. A good place to start is the Ada Programming Wikibook.

You can grab the code for these examples at github.com/ThomasLocke/Pez_Dispenser.

Finally a big thank you goes out to my good friend Dwight Scott Miller for helping me weed out the worst parts of my Danish-ified English. I really appreciate it.