Created
August 22, 2015 21:41
-
-
Save glts/0bb56d89e7d4597cd4ec to your computer and use it in GitHub Desktop.
My Clojure solution for Dijkstra's 'dining philosophers' problem
This file contains hidden or bidirectional Unicode text that may be interpreted or compiled differently than what appears below. To review, open the file in an editor that reveals hidden Unicode characters.
Learn more about bidirectional Unicode characters
;; Philosophers sitting around a table, one chopstick per person. | |
;; Dijkstra's "dining philosophers" problem. | |
(let [logger (agent nil)] | |
(defn log [& args] | |
(send-off logger #(apply println %2) args))) | |
(defn philosophers | |
"Returns a vector of philosophers with the given names, each having a | |
chopstick on their left and right. A chopstick contains a reference to the | |
philosopher who is currently using it, or nil if it is not being used." | |
[names] | |
(let [chopsticks (repeatedly (count names) #(ref nil)) | |
pairs (map vec (partition 2 1 (cycle chopsticks)))] | |
(mapv #(hash-map :name %1 :chopsticks %2) | |
names | |
pairs))) | |
(defn can-eat? [philo] | |
(every? nil? (map deref (:chopsticks philo)))) | |
(defn eating? [philo] | |
(every? #(= philo %) (map deref (:chopsticks philo)))) | |
(defn eat [philo] | |
(dosync | |
(when (can-eat? philo) | |
(doseq [user (:chopsticks philo)] (ref-set user philo)) | |
(log (:name philo) "is now eating")))) | |
(defn think [philo] | |
(dosync | |
(when (eating? philo) | |
(doseq [user (:chopsticks philo)] (ref-set user nil)) | |
(log (:name philo) "stops eating and thinks some more")))) | |
(defn begin-feast | |
"Begins a feast for a table of philosophers with the given names. Starts | |
futures that run indefinitely; returns these futures to make it possible | |
to cancel the feast." | |
[names] | |
(doall (for [p (philosophers names)] | |
(future | |
(while true | |
(if (eating? p) | |
(think p) | |
(eat p)) | |
(Thread/sleep (+ 1000 (rand-int 2000)))))))) | |
(defn end-feast | |
"Takes a collection of philosopher-futures and cancels them all." | |
[futures] | |
(doseq [f futures] (future-cancel f))) | |
;; Luxemburg | |
;; | |
;; Wittgenstein Leibniz | |
;; | |
;; Shelley Chomsky | |
(def fs (begin-feast ["Luxemburg" "Wittgenstein" "Shelley" "Chomsky" "Leibniz"])) | |
; to cancel: | |
; (end-feast fs) |
Sign up for free
to join this conversation on GitHub.
Already have an account?
Sign in to comment