Expert to Expert: Erik Meijer and Bertrand Meyer - Objects, Contracts, Concurrency, Sleeping Barbers

HOLY CRAP! I have to watch this!

“I don’t use the internet any more because they can steel every thing” in context that was a very funny comment.

Regarding the Sleeping Barber Algorithm and with out breaking the demonstration. Wouldn’t you want to have as many barbers as you have chairs?

jason818_253.33 wrote:



Regarding the Sleeping Barber Algorithm and with out breaking the demonstration. Wouldn’t you want to have as many barbers as you have chairs?

This does inspire some thought.

Basically, a chair will contain a customer, and a barber is required to do the work. This pretty much means that the number of chairs is the number of slots in the queue. The number of barbers will be determined by how many processor cores you have.

So pretty much, the more processor cores you have, the more barbers you can have. You ideally want one barber for each processor core. So, the more processor cores you have and therefore the more barbers you have, the faster you'll be able to cut the hair of all the customers in the chairs.

This analogy does make the problem sound simple.

jason818_253.33 wrote:  Regarding the Sleeping Barber Algorithm and with out breaking the demonstration. Wouldn’t you want to have as many barbers as you have chairs?

CRPietschmann wrote:

This analogy does make the problem sound simple.

You've both misunderstood the crux of the Sleeping Barber problem. The problem is a problem not of speed or efficiency, but one of concurrency. The point is to serve the customers without experiencing process- (customer-) starvation or deadlock and the Sleeping Barber problem is a double-rendevous problem requring a more careful use of locks to achieve the correct result than you might think at first.

Wow. 2008 is shaping up to be the best year to date for video interviews on Channel 9! How are you guys going to top this?

dot_tom wrote:

Wow. 2008 is shaping up to be the best year to date for video interviews on Channel 9! How are you guys going to top this?

There have been both hits and misses. 2007 was not the best year for channel9 videos. But you are right 2008 looks very promising: more videos on language, tools and process (development methods like Agile). A video about the new work item types in Rosario would be great...

I enjoyed this. Thanks

Here is a CCR implementation of the Sleeping Barber(s).
Optionally, we can add barbers (threads).
As shown, this is actually a pretty clean pattern using Ports and lamdas and hides the locks and such in the runtime. User level locks on shared state could still be needed in the lambda.  So it is not something that has to be "baked" into a language itself as this works pretty clean as a library.

I really like a few of ideas in this video in general:
1) I like the ccr Port abstraction. For some reason I like endpoints and messages.
2) I like the idea of Pre and Post conditions. This could be added to c#. Think spec# has.
3) I like the idea explicit handling of Query and Command on shared state.  It allows tooling and static and runtime checks.
4) I like the idea un-named types like Tuples. c# has anonymous types, but you can't pass them around.
5) I love the idea of Transactions for object state and have them work with normal DB transactions for rollback.  That seems to be a winning pattern for handling shared state and something like CCR below for handling concurrency and coordination.

private void button20_Click(object sender, EventArgs e)
{
    // Have 1 Barber and N chairs. You can add Barbers (i.e. Threads in the pool) by changing the Dispatcher ctor.
    Port<string> chairsPort = new Port<string>();
    DispatcherQueue dq = new DispatcherQueue("Barber", new Dispatcher(1, "BarberPool"));
    Arbiter.Activate(dq, Arbiter.Receive(true, chairsPort, (string name) =>
        {
            Thread.Sleep(100); // Time to cut hair.
            Console.WriteLine("Customer {0} thanks the barber for the cut on thread {1}.", name, Thread.CurrentThread.ManagedThreadId);
        }));
    for (int i = 0; i < 15; i++)
        chairsPort.Post("Customer" + i);
}

Very interesting video - as all of these Going Deep's have been.

RE the Sleeping Barber: Why not just temporarily impart the knowledge and know-how of how to cut one's own hair to each customer that comes along with instructions to come back and report how it went? 

staceyw wrote:

Here is a CCR implementation of the Sleeping Barber(s).
Optionally, we can add barbers (threads).
As shown, this is actually a pretty clean pattern using Ports and lamdas and hides the locks and such in the runtime. User level locks on shared state could still be needed in the lambda.  So it is not something that has to be "baked" into a language itself as this works pretty clean as a library.

I really like a few of ideas in this video in general:
1) I like the ccr Port abstraction. For some reason I like endpoints and messages.
2) I like the idea of Pre and Post conditions. This could be added to c#. Think spec# has.
3) I like the idea explicit handling of Query and Command on shared state.  It allows tooling and static and runtime checks.
4) I like the idea un-named types like Tuples. c# has anonymous types, but you can't pass them around.
5) I love the idea of Transactions for object state and have them work with normal DB transactions for rollback.  That seems to be a winning pattern for handling shared state and something like CCR below for handling concurrency and coordination.

private void button20_Click(object sender, EventArgs e)
{
    // Have 1 Barber and N chairs. You can add Barbers (i.e. Threads in the pool) by changing the Dispatcher ctor.
    Port<string> chairsPort = new Port<string>();
    DispatcherQueue dq = new DispatcherQueue("Barber", new Dispatcher(1, "BarberPool"));
    Arbiter.Activate(dq, Arbiter.Receive(true, chairsPort, (string name) =>
        {
            Thread.Sleep(100); // Time to cut hair.
            Console.WriteLine("Customer {0} thanks the barber for the cut on thread {1}.", name, Thread.CurrentThread.ManagedThreadId);
        }));
    for (int i = 0; i < 15; i++)
        chairsPort.Post("Customer" + i);
}

Well, it looks to me that support for Queries and Commands would (almost) automatically require transactional support.
No one would like to read partial state, would they?
And in a way, it proves the point of functional programmers are trying to make - when you need to change the world, you have to create a new copy of it.
Whoever was reading the world at the moment you decided to modify it, would continue to use the "old" consistent version of it.
After you are done changing the world and committed your changes, all the new readers would see the new updated version. The old version will hang around long enough for all active readers conclude their activities and be "garbage collected" as soon as its no longer required.
Which is sort of what databases already do to implement non-blocking consistent reads.
So, it seems that eventually runtime environment will be a database with a common VM on top of it.
But that approach has its own issues, namely a requirement to have universal change sequence number to mark world versions.

Hmmm, is it a coincidence that Eric Meijer is said to be working on SQL Server these days?

Truely old school, he wrote his algorithm on paper! how many programmers do that today? 

Once again this video made me think of a really cool addition I'd love to see Channel 9 add to such video interviews. Charles, is there any chance you could ask your interviewees to state the last comp.sci book they read and enjoyed? I'm thinking the 'tradition' would be that it wouldn't even directly have to have anything to do with the subject of the video in question. You could then include the book details in addition to the usual interviewee home page link. Often times when watching or listening to the folks you interview I'm left thinking: 'Wow, I'd love the scan the titles on their technical bookshelf!'. Am I alone in this?

Hi DCharles. I'm guilty of frequently resorting paper based coding! I keep meaning to get myself a cheap A4 scanner so I can archive these things. I often make myself walk away from my computer and go think somewhere else. Which usually results in algorthims being sketched on any available bit of paper. I often find it much easier to do 'think refactors' on paper than on the screen.

dcharles wrote:

Truely old school, he wrote his algorithm on paper! how many programmers do that today? 

I used to write all my Cobol programs on paper first and work them out and debug them on paper.  This was mainly because we had time limit on input and Run time for CPU.  It actually worked out pretty well, because you could sit down and type the whole program in an hour or so and it was mostly debugged already.  I would not do that today.  As Erik has said before, today the IDE is so good, it is like "smart paper" that serves the same function as paper, but with other benefits.

sokhaty wrote:



staceyw wrote: Here is a CCR implementation of the Sleeping Barber(s). Optionally, we can add barbers (threads). As shown, this is actually a pretty clean pattern using Ports and lamdas and hides the locks and such in the runtime. User level locks on shared state could still be needed in the lambda.  So it is not something that has to be "baked" into a language itself as this works pretty clean as a library. I really like a few of ideas in this video in general: 1) I like the ccr Port abstraction. For some reason I like endpoints and messages. 2) I like the idea of Pre and Post conditions. This could be added to c#. Think spec# has. 3) I like the idea explicit handling of Query and Command on shared state.  It allows tooling and static and runtime checks. 4) I like the idea un-named types like Tuples. c# has anonymous types, but you can't pass them around. 5) I love the idea of Transactions for object state and have them work with normal DB transactions for rollback.  That seems to be a winning pattern for handling shared state and something like CCR below for handling concurrency and coordination. private void button20_Click(object sender, EventArgs e) {     // Have 1 Barber and N chairs. You can add Barbers (i.e. Threads in the pool) by changing the Dispatcher ctor.     Port<string> chairsPort = new Port<string>();     DispatcherQueue dq = new DispatcherQueue("Barber", new Dispatcher(1, "BarberPool"));     Arbiter.Activate(dq, Arbiter.Receive(true, chairsPort, (string name) =>         {             Thread.Sleep(100); // Time to cut hair.             Console.WriteLine("Customer {0} thanks the barber for the cut on thread {1}.", name, Thread.CurrentThread.ManagedThreadId);         }));     for (int i = 0; i < 15; i++)         chairsPort.Post("Customer" + i); }

Well, it looks to me that support for Queries and Commands would (almost) automatically require transactional support.
No one would like to read partial state, would they?
And in a way, it proves the point of functional programmers are trying to make - when you need to change the world, you have to create a new copy of it.
Whoever was reading the world at the moment you decided to modify it, would continue to use the "old" consistent version of it.
After you are done changing the world and committed your changes, all the new readers would see the new updated version. The old version will hang around long enough for all active readers conclude their activities and be "garbage collected" as soon as its no longer required.
Which is sort of what databases already do to implement non-blocking consistent reads.
So, it seems that eventually runtime environment will be a database with a common VM on top of it.
But that approach has its own issues, namely a requirement to have universal change sequence number to mark world versions.

Hmmm, is it a coincidence that Eric Meijer is said to be working on SQL Server these days?

yes.  That is essentially what we came up with in another thread on object transactions.  Transactions would atomically make a copy of the invariants.  A writer could make updates to its' version and "try" update.  I think it would a ~simple matter to extent object meta data to include a seq number.

dcharles wrote:

Truely old school, he wrote his algorithm on paper! how many programmers do that today? 

Me for one. Excepting trivial functions, most of what I do requires me to think, and I can't do that without a bit of paper and a pencil.

The participants seem surprisingly ignorant of the state of the art in concurrent programming. Message passing architectures are old hat, and have been shown to be scalable; a lot of work is going into transactionactional memory and other non-blocking strategies, and so on, but I don't hear these being mentioned even in passing.

The Eiffel SCOOP mechanism was proposed over a decade ago, making the idea generations old in the software world, yet a functioning product still hasn't shipped. Why is that?

I'm not convinced that SCOOP can work. The problem I see with it is that it allows for arbitrary sharing of state among concurrently executing objects. If it can be made to work then the compiler will probably have to make such conservative decisions wrto synchronization that performance will be a tiny fraction of the theoretical optimum.

Its one of those ideas that have a seductive elegance at first glance but ultimately turns into a dead end.

foostar wrote:

I'm not convinced that SCOOP can work. The problem I see with it is that it allows for arbitrary sharing of state among concurrently executing objects. If it can be made to work then the compiler will probably have to make such conservative decisions wrto synchronization that performance will be a tiny fraction of the theoretical optimum.

Is this really true? My understanding is that SCOOP is very high level and there are a number of different ways it could be implemented internally. For example, it could be implemented on top of message passing?

I like the SCOOP concepts. Being a fan of design by contract for many years now, I like especially the way it works neatly with contracts. I would like to think foostar is incorrect in these assumptions.

Very good video. This was very nice to see Bertrand Meyer speaking about his work. Thanks for bringing this.

BTW, does he have to take into account the customers who do not see a barber and walk away? That was very funny!!

Anyone who want to convert Mod video files to mpg, mpeg, avi, wmv video formats you can use Aiseesoft Mod Video Converter. You can free download it and have a try.
http://www.aiseesoft.com/mod-video-converter.html