Dining Philosophers Problem in Clojure

Question

I have implemented the Dining Philosophers Problem in Clojure with refs, trying to emphasize readability. Please point out if parts of it are inefficient, not idiomatic, or improvable in any way. Full code on GitHub.

;;;;;;;;;;;;;;;;;;;;
;; DINING ;;
;; PHILOSOPHERS ;;
;; PROBLEM ;;
;;;;;;;;;;;;;;;;;;;;
(ns concurrency.dining-philosophers
 (:gen-class)
 (:require [clojure.core.async :refer [go chan >!! <!!]]))
(def n-philosophers 5)
(def max-eating-time 3000)
(def max-thinking-time 2000)
(def retry-time 5)
(def forks (for [_ (range 0 n-philosophers)]
 (ref false)))
;; We use a core async channel to implement a logger that writes
;; to the terminal. It will run on the main thread
(def logger-chan (chan))
(defn log [& xs]
 (>!! logger-chan (apply str xs)))
(defn logger [channel]
 (println "Ready to log...")
 (while true
 (let [msg (<!! channel)]
 (println msg))))
;; The philosopher function contains the main logic of the application
(declare get-forks eat think wait-retry-time)
(defn philosopher
 "Given a philosopher's location n at the table, tries to pick up both
 forks simultaneously and eat. When he is finished eating he thinks
 for a while. If he cannot pick up both forks, he retries after a while.
 This function runs in a thread"
 [n]
 (log "Philosopher " n " just sat down")
 (while true
 (if (get-forks n)
 (do (log "Philosopher " n " picked up forks")
 (eat n)
 (think n))
 (wait-retry-time))))
(declare get-fork left-fork right-fork release-fork)
(defn get-forks
 "We try to get the left fork first, and then the right fork. If we succeed
 in getting the left fork but not the right, we drop the left fork.
 Returns true if we succeed in getting both forks and false otherwise."
 [n]
 (dosync
 (if (get-fork (left-fork n))
 (if (get-fork (right-fork n))
 true
 (release-fork (left-fork n)))
 false)))
(defn get-fork [fork]
 (if @fork
 nil
 (ref-set fork true)))
(defn left-fork [n]
 (nth forks (mod (dec n) n-philosophers)))
(defn right-fork [n]
 (nth forks n))
(defn release-fork [fork]
 (ref-set fork false))
(declare release-forks)
(defn eat [n]
 (log "Philosopher " n " is dining")
 (Thread/sleep (rand-int max-eating-time))
 (release-forks n)
 (log "Philosopher " n " dropped forks"))
(defn release-forks [n]
 (dosync
 (release-fork (left-fork n))
 (release-fork (right-fork n))))
(defn think [n]
 (log "Philosopher " n " is thinking")
 (Thread/sleep (rand-int max-thinking-time)))
(defn wait-retry-time []
 (Thread/sleep retry-time))
(defn -main []
 (println "Starting main")
 (dotimes [i n-philosophers]
 (.start (Thread. #(philosopher i))))
 (logger logger-chan))
(-main)

Answer 1

Idiosyncrasies

declareing your fns

It's pretty unusual to declare all of your functions before defining them.

It appears that you did it so that you could define your functions in the order you thought most appropriate. That's common for newcomers, and it's certainly something many people are used to. To be clear, there's nothing wrong with wanting that.

However, most clojure programs work within this constraint and just define things in the order they are needed. After a while you become accustomed to seeing things in that order, and you start to look at the bottom of the file for the program overview. This has the minor benefit of calling out the places where circular references are actually needed.

Manually calling -main

This is a toy program, so calling -main in your namespace probably does what you want 100% of the time. However, in a real codebase, doing that can pretty much make your namespace unusable for other namespaces. If you're using lein you can call:

lein run -m concurrency.dining-philosophers

If you're running raw clojure use:

java -cp "clojure.jar:$OTHER_JAR_PATHS" clojure.main -m concurrency.dining-philosophers

Program Structure

Decouple Philosophers

Your philosophers are aware of a lot of implementation details. Really all they care about is their name, their left fork, and their right fork. You transmit all of that information in a single number, which is convenient, but it means you have to be concerned with how forks are retrieved in the philosopher code as opposed to just using the forks you're assigned.

The consequence of this is it binds your functions together in an undesirable way.

Leverage Sequences

Your solution uses a lot of indices and math to manipulate those indices. It could be made dramatically simpler by manipulating sequences instead. (Hint: Use the above advice and the partition function.)

Microfunctions

This is a really common thing for newcomers to clojure, myself included.

When I did a lot of Java, I tended to like very small functions, and I would create arbitrary functions (e.g. get-fork, release-fork and wait-retry-time) for no other reason than to cut down on my line count. After working with clojure for a while, function length became less important than overall comprehensibility. So what I try and do now is look for fundamental concepts in my program as opposed to places where I can inject a random function.

For example, for this problem, I see get-forks, release-forks, eat, and think as primitives. They are things that are inherent to the problem. You may or may not name them, but they are definitely there.

You never really want to get a single fork at one time, so get-fork seems too small to be a standalone concept. The same for release-fork. wait-retry-time is just a pseudonym for (Thread/sleep retry-time). The latter is going to be more obvious to any newcomer to the codebase.

General Comments

Use of core.async

Just to let you know, since you pulled in core.async, it's possible to do a lot of the mechanics around starting/stopping threads with core.async. This has a couple of advantages:

• Removes the need to use Java constructs like Thread/sleep, .start, .wait. (As far as I know, this is really just an aesthetic advantage)
• Allows you to easily interact with processes (i.e. start them and stop them) (Another potential option here is Java's Executor infrastructure.)

So it's not a massive gain, but the option is there if you choose.

No cleanup mechanism

While we're on the topic of interacting with the processes, the current structure doesn't leave any hooks for cleaning up your threads. This works fine for a toy program where you'll let it run then ctrl-c, but any real-world system will need to handle that cleanly. So it might be nice for you to use the opportunity to think about how to structure the program so you can clean up on demand.

Unbuffered logger-chan

Since your logger-chan is an unbuffered chan you've introduced synchrony around your logging when you probably want some asynchrony there. I can't see any harm in setting a buffer of ~100 or ~1000 on that channel. It'll almost certainly be way ahead of its workload, and in the event it gets behind, it'll still give some backpressure so you won't lose any events.

Closing Thoughts

I really like that you chose clojure's STM system for this problem. It's not often used, but by far the best fit. Also, despite my nitpicking, the big picture flow of philosopher is straightforward in the best kind of way.

Please let me know if you have any questions about my comments. I'm more than happy to give further feedback!

Edit in response to OPs comments

go-block lockup

You only get lock up if you occupy the thread (e.g. with Thread/sleep, or by doing IO or doing a CPU-intensive process). If you "park" it with (<! (a/timeout msecs)) it doesn't block the state machine.

core.async vs future

I was referring to the thread macro. I don't think there's any substantial benefit to core.async over the futures with and Executor. I actually did a version with ExecutorService and Future, and it has the same feature set. FWIW I think it's also more concise than the version I did with core.async.

However, it is very beneficial to use one of those two over Thread/start and Thread/wait. Those are pretty rudimentary constructs. And they suck for most use cases.

Function Size

You pose a really good point regarding get-fork. You do indeed want to eliminate repetition where possible (though not at the expense of simplicity). I would agree that in the current implementation, get-fork needs to be its own function. However, I don't think getting a single fork is necessary for a solution to this problem.

• user3146897: Thanks for the answer, I appreciate your feedback. I have some questions though. With core async are you referring to the "thread" function/macro? I think go wouldn't be appropriate since there is a lot of waiting in the program. And since I wouldn't be using the channels that thread returns, is there any advantage in using it vs using future.
• user3146897: Also, I get what you are dying about micro functions, but get-fork is not a one-liner and eliminating it would create quite a bit of repetition in the code. Aren't we supposed to eliminate repetition when possible? And if get-fork should be a function, then wouldn't release-fork also be one, even if it's only for consistency. I do agree with wait-retry-time though, it shouldn't be a separate function.
• Tim Pote: @user3146897 see my edits. Please let me know if you have any more questions!