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:





20 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. 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
  3. 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
  4. Thanks for the best share and it is very helpful.
    cinema hd for pc

    ReplyDelete
  5. 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
  6. 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
  7. Great article! I gonna try to check this code with my website.

    ReplyDelete
  8. 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
  9. 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

  10. Fin indisk mad. Meget venlig betjening. Vi fik vores egen "buffet" på bordet med fire take away frederiksberg forskellige varme retter samt forretter. Ekstra plus: de har indisk vin 👍🏼
    We use certain strategies and techniques to assist our customers. dissertation writers We have an entire plan that is followed for the better accommodation of ideas provided by our customers.

    ReplyDelete
  11. This is really interesting, you are such a great blogger. Visit media foster for creative and professional website design and Digital Marketing Company in Mohali and Also get Digital Marketing Course in Mohali
    TOP IT Company in Mohali
    best SEO Company in Mohali

    ReplyDelete
  12. Such great and nice information about software.
    This site gonna help me a lot in finding and using a lot of software.
    Kindly make this like content and출장샵
    출장샵
    출장샵
    출장샵
    출장샵
    출장샵
    출장샵 update us. Thanks for sharing us Sublime Text Crack.
    Kindly click on here and visit our website and read more.

    ReplyDelete
  13. Quartz Luxury Windows has a comprehensive selection of Single hung windows
    , allowing them to cater to the preferences of each homeowner.

    ReplyDelete