Saturday, September 27, 2014

Breaking the habit: Solving the Dining Philosopher's problem with Actors

Concurrent programming using Actors is different to traditional mutex based approaches, therefore I'd like to show how the solution of a classical concurrency problem can be done using Actors. It requires some time to get used to it as future/actor based concurrency looks different and uses different patterns.

Additionally I'll show how little effort is required to make this a distributed application, as asyncronous Actor based concurrency is much more resilient regarding network induced latency.

I'll use my Kontraktor Actor library version 2.0 beta to also illustrate how the "message == asynchronous method call" approach of Kontraktor works out in "practice".

Resources:

Kontraktor lib: https://github.com/RuedigerMoeller/kontraktor.
Full source of sample is here.

Description of the philosophers dining problem:
http://en.wikipedia.org/wiki/Dining_philosophers_problem
(I am using a non-fair solution to keeps things simple.)


The Table

One actor represents the table. For each fork, a list of philosophers waiting for "fork is free"-notification is kept.

Short explanation: In Kontraktor all public methods are translated into asynchronous messages put on to an actors queue ("mailbox") behind the scenes. The worker thread of an actor takes the messages of the mailbox and calls the "real" implementation. So its guaranteed an actor is executing single threaded. To identify asynchronous calls easily, I always put a $ in front of public actor methods.


Explanation: if a fork is taken and the queue of waiting philosophers is empty, a fulfilled promise is returned, else an unfulfilled promise is added to the queue. The caller code then looks like:


Once a fork is returned, the next Promise in the arraylist (if any) is notified. signal() is equivalent to receive("dummy",null).

Note that the "result" object is unused, I just need a signal from the future returned. That's why the fulfilled Promise gets a "void" as a dummy result object (which will then trigger immediate execution of the then-closure on caller side).

Note how I can use simple single threaded collections and data structures as the actor is guaranteed to be executed single threaded.

The Philosopher

A philosopher has a wonderful life which can be divided into 3 states:

10 think randomTime
20 be_hungry_and_try_to_grab_2_forks
30 eat randomTime
40 goto 10

[rumors are of lost lines 15 and 35 related to indecorous social activities introduced after Epicurus happened to join the table]


The meat is in the $live method:
After thinking, the philosopher tries to grab one fork, the closure given to the "then" method gets executed once the fork becomes available. Once both forks have been grabbed, another "delayed" call keeps the "eat" state for a while, then both forks are returned and a $live message is put onto the actors mailbox (=message queue) to start thinking again.

Remarks:

  • "delayed" just schedules the given closure onto the actors mailbox with a delay.
  • "self().$live()" puts a $live message onto the actors mailbox. If "this.$live()" would be called, the $live() message would be executed directly [synchronous] like a normal method. In this example this would not hurt, however in many cases this makes a difference.
  • Wait-Free. The executing thread is never blocked. One could easily simulate thousands of philosophers onto a single thread

Setup and run

The main method to start the life of 5 philosophers looks like this:

and

Note Hoarde is a utility to create and manage groups of Actors. "startReportingThread" just starts a thread dumping the state of all philosophers:


"Is this still Java?" .. probably weird looking stuff for the untrained eye ..
(note Philosopher.$getState is async and yield() is used to wait for all futures to complete before executing the then() closure printing the state)

BTW: spacing is somewhat inconsistent as I started to reformat code partially during edit .. but won't do screenshots again ..

Yay, done:



Let's make it a distributed application

The killer feature of Actor based asynchronous+lock/wait free programming is simple distributability. A solution using blocking mutexes would have to get a rewrite or rely on synchronous remote calls, so the bigger the network latency, the lower the throughput. Actors do not suffer from that.
We can just change the startup to make the table run remotely:


Is this cool or what ? I now can feed hoardes of philosophers with a single table server:





21 comments:

  1. Devops is not a Tool.Devops Is a Practice, Methodology, Culture or process used in an Organization or Company for fast collaboration, integration and communication between Development and Operational Teams. In order to increase, automate the speed of productivity and delivery with reliability.

    python training in bangalore
    aws training in bangalore
    artificial intelligence training in bangalore
    data science training in bangalore
    machine learning training in bangalore
    hadoop training in bangalore
    devops training in bangalore

    ReplyDelete
  2. Gaining Python certifications will validate your skills and advance your career.
    python certification

    ReplyDelete
  3. Great, I never thought learning java will be this much easier. Due to the extreme nature of academic programs, some people will argue that you cannot get your doctorate online. However, this is not the case with me. Just the way you are providing JAVA instructions. I used to acquire my research help from EssayKing. Who provides a research paper for a higher quality, lower rates, higher recognition, or higher mobility, as it is difficult to keep your current job at long intervals to get any of it.

    ReplyDelete
  4. I admire what you have done here. I love the part where you say you are doing this to give back but I would assume by all the comments that is working for you as well. Do you have any more info on this?
    organic basmati brown rice

    ReplyDelete
  5. Thanks, this is generally helpful.
    Still, I followed step-by-step your method in this Java online training
    Java online course

    ReplyDelete
  6. Why sit alone and get lonely while the world has had many dating sites for many years? I know one of these places personally and I would also like to recommend it to you. Literally in a week, I discovered my romanian brides for this service, the girls really are wonderful! The workers on this platform helped me to locate the right girl for me. I like the girls of Czech nationality but it's very difficult to find them in my town and particularly the place where I live, but I've been very happy with this location!

    ReplyDelete
  7. Thanks for the best share and it is very helpful.
    cinema hd for pc

    ReplyDelete
  8. Your blogs are authentic. I love them .Are you also searching for essay help? we are the best solution for you. We are best known for delivering quality essay help.

    ReplyDelete
  9. I love it here. Reading your blogs is therapeutic. Keep sharing. I love them Are you also searching for do assignment for me? we are the best solution for you. We are best known for delivering cheap assignments to students without having to break the bank

    ReplyDelete
  10. Hello Sir I saw your blog, It was very nice blog, and your blog content is awesome, i read it and i am impressed of your blog, i read your more blogs, thanks for share this summary.
    Learn to Recover Disabled Facebook Account

    ReplyDelete
  11. This type of message always inspiring and I prefer to read quality content, So happy to find good place to many here in the post, the writing is just great, thanks for the post.
    check here

    ReplyDelete
  12. Great article! I gonna try to check this code with my website.

    ReplyDelete
  13. Awesome blog. I enjoyed reading your articles. This is truly a great read for me. I have bookmarked it and I am looking forward to reading new articles. Keep up the good work!

    ReplyDelete
  14. Awesome blog. I enjoyed reading your articles. This is truly a great read for me. I have bookmarked it and I am looking forward to reading new articles. Keep up the good work!
    internship for web development | internship in electrical engineering | mini project topics for it 3rd year | online internship with certificate | final year project for cse

    ReplyDelete
  15. Students use paraphrasing tools, literature essay tool and multiple other ways to check their writing content. Yet, there is a particular general guideline which they fail to flow due to which they end up losing marks. So today, we are going to state some significant Do's which should be included in every essay to get the best grades.
    include transition
    including transition sentences at the end and beginning of each paragraph helps to connect the two. Often due to lack of proper outline, the matter becomes very confusing without the correct presentation. Hence, all mini sections should be appropriately titled with statements that interconnect them with the previous matter. Transition sentences are helpful to enhance readability and keep it relevant. Even essay writers provide economics assignment help to students in their papers.
    use present tense
    Most experts provide Dissertation help service to the present tense of writing. Writing in the current tense or active essay always shows higher engagement. Talking in the past tense while mentioning history is accepted, but try to keep it in present form for the rest of the essay. This feels like an interaction that keeps the readers hooked till the end.
    Advanced terms
    Using sophisticated terms help in showcasing knowledge. You can quickly lookup a thesaurus or online to find synonyms of similar words. Advanced terms can impress your teacher and show how professional you are with writing. Keep it readable by using simple sentences; however, make your knowledge by using high need terms here and there. When you hr assignment help, you will observe that experts use specific vocabulary, making their writing different from the basic ones.
    Answer what, when and how
    Content should be informational, which excites readers. Gear up your researching skills and provide information from credible sources. Gather exclusive data which makes your paper different from the rest. Provide insightful data in your article. An easy way to do it is by answering what, when and how in your paper. While proofreading, experts always lookout if their content is answering the essential questions that may arise.
    good presentation
    Apart from only taking care of the literature part, take care of the presentation too. Some generalized guidelines are followed for writing assignments. Like proper margin, readable font, not using too many bright colours and following instructions of teachers. A good presentation will always attract more eyeballs which aromatically class for more marks. Lookup for ideas or discuss innovative presentation ideas with known ones to get creative. Students always want to get good grades without any taking online exam help. But often, it seems unachievable. Correct knowledge and a little information about the proper tactics can help students write the best essay.

    We have a few more services below:
    NUR1201 Assessment Answers
    CHCDIS009 Task Answers
    CIA11217 Solutions
    HRM552 Task Answers
    FIT3152 Assessment Answers

    ReplyDelete