Dining Philosopher Problem

diningphilosopher.clj

(ns algorithms.problems.diningphilosophers)

;  ----------------------------------------------
;  Dining Philosopher Problem
;
;  This implementation satisfies the following story
;  line:
;
;  Our waiters set several tables of various
;  sizes for dinner. One by one, the various hungry
;  philosophers trickle into the restaurant for dinner.
;  One of the waiters will seat them randomly at
;  various tables. As soon as a table is full,
;  the table is set, and the diners may start eating.
;  The philosophers may eat until there is no more food.
;
;  Implementation:

;  * each philosopher is an independent entity and is
;  expressed as a thread (future), as is each waiter
;
;  * each table maintains the following state:
;    * available servings
;    * chopsticks
;    * # seats
;    * diners at the table
;
;  * each philosopher maintains the following state:
;    * chopsticks to use, when available
;    * servings consumed
;
;  General thoughts on the problem:

;  * each chopstick may only be used by one philosopher
;  at a time
;  * each philosopher must acquire a left and right
;  chopstick in order to eat
;  * it takes a random amount of time to eat and a random
;  amount of time to think.
;  * a philosopher may only transition to EATING from
;  THINKING, and from THINKING to EATING
;  ----------------------------------------------

;; ----------------------------------------------
;; helper functions for table printing
;; ----------------------------------------------

(defn internal-print-table [table buf]
  (binding [clojure.core/*out* buf]
    (dosync
      (prn "-----------------------------------------------------------------------------------------------")
      (prn "Table: ")
      (prn "  state: " @(:tablestate table) " seats: " (:seats table))
      (pr "  chopsticks: ") (doseq [ch (:chopsticks table)] (pr (key ch) @(val ch) "  ")) (prn)
      (pr "  servings: ") (doseq [sv (:servings table)] (pr (key sv) ":" @(val sv) "  ")) (prn)
      (prn "-----------------------------------------------------------------------------------------------"))))

(defn print-table [table]
  (let [s (java.io.StringWriter.)
        p (internal-print-table table s)]
    (prn (.toString p))))

;; ----------------------------------------------
;; Records
;; ----------------------------------------------
(defrecord Philosopher [doing servings left-chopstick right-choptstick table]
  java.lang.Object
  (toString [this] (str "{:doing " :doing " :servings " :servings " :left " (hash :left-chopstick) " :right " (hash :right-chopstick) " :table " (hash :table) "}")))

(defrecord Chopstick [owner]
  java.lang.Object
  (toString [this] (str "{:owner " (hash :owner) "}")))

(defrecord Table [seats chopsticks philosophers tablestate]
  java.lang.Object
  (toString [this] (str "{:seats " :seats " :chopsticks " :chopsticks " :philosophers " :philosophers " :tablestate " :tablestate "}")))

;; ----------------------------------------------
;; Methods for
;; * creating tables
;; * eating, thinking
;; * starting, stopping table service
;; ----------------------------------------------
(defn create-table
  "Create and init a table with chopsticks, philosophers, and a serving count for each diner."
  [seats]
  (Table.
    seats
    (zipmap (range (inc seats)) (repeat (Chopstick. :table)))
    {}
    :notready))

(defn create-table-ref
  [seats]
  (ref (create-table seats)))

(defn create-philosopher
  "Create a philosopher."
  []
  (Philosopher. :thinking 0 nil nil nil))

(defn create-restaurant
  "creates a range of tables with seats from 0 to num-tables"
  [num-tables num-waiters]
  {:tables (map #(create-table-ref (inc %)) (range num-tables))
   :waiters (map #(agent %) (range num-waiters))})

(defn seat-philosopher-at-table
  "seat a philosopher at a table so that he/she may eat."
  [philosopher table]
  (let [seated-count (count (:philosophers @table))]
    (if (>= seated-count (:seats @table))
      ;; this table is full
      philosopher
      ;; table has room
      (let [left-chopstick ((:chopsticks @table) seated-count)
            right-chopstick ((:chopsticks @table) (mod (inc seated-count) (:seats @table)))
            hungry-philosopher (assoc philosopher :left-chopstick left-chopstick :right-chopstick right-chopstick :table table)]
        (dosync (ref-set table (assoc-in @table [:philosophers seated-count] hungry-philosopher)))
        hungry-philosopher))))


(defn seat-philosopher-in-restaurant
  "seat a philosopher at any available table"
  [philosopher restaurant]
  (loop [tables (:tables restaurant)
         ph philosopher]
    (if (nil? tables)
      false
      (if (not (nil? (:table ph)))
        true
        (recur (rest tables) (seat-philosopher-at-table philosopher (first tables)))))))

(defn try-eating
  "try to eat. the diner may not be able to, as they may already be eating, or they may not have
access to the chopsticks to their left and right."
  [philosopher]
  (do
    (dosync
      (if (and
        (= :dinnertime (:tablestate (:table philosopher)))
        (= :thinking (:doing philosopher))
        (= :table @(:left-chopstick philosopher))
        (= :table @(:right-chopstick philosopher)))
        (do
          (ref-set (:left-chopstick philosopher) philosopher)
          (ref-set (:right-chopstick philosopher) philosopher)
          (alter philosopher #(assoc philosopher :doing :eating :servings (inc (:servings philosopher)))))))
    (Thread/sleep (rand-int 100))))

(defn try-thinking
  "try to think. if the philosopher is currently eating, then this will cause him/her to surrender their
chopsticks and start thinking."
  [philosopher]
  (do
    (dosync
      (if (and
        (= :eating (:doing philosopher))
        (= philosopher @(:left-chopstick philosopher))
        (= philosopher @(:right-chopstick philosopher)))
        (do
          (ref-set (:left-chopstick philosopher) :table)
          (ref-set (:right-chopstick philosopher) :table)
          (alter philosopher #(assoc philosopher :doing :thinking)))))
    (Thread/sleep (rand-int 100))))

(defn philosopher-start-dining
  "start eating and thinking until the table is closed (e.g. it is closingtime)"
  [philsopher]
  (while (not (= :closingtime @(:tablestate (:table philsopher)))
    (try-eating philsopher)
    (try-thinking philsopher))))

(defn start-tableservice
  "the table has been served with food, it is dinnertime"
  [table]
  (do
    (dosync (alter table #(conj table :tablestate :dinnertime)))
    (doseq [philosopher (:philosophers table)] (future (philosopher-start-dining philosopher)))))

(defn stop-tableservice
  "food service is complete, and the diners must stop eating."
  [table]
  (dosync (alter table #(conj table (:tablestate table) :closingtime))))

(defn client-arrives [restaurant philosopher]
  (let [w (:waiters restaurant)]
    (send (w (rand-int (count w) (seat-philosopher-in-restaurant philosopher restaurant))))))

(defn serve-dinner [restaurant]
  (for [table (:tables restaurant)] (start-tableservice table)))

(defn close-restaurant [restaurant]
  (for [table (:tables restaurant)] (stop-tableservice table)))

;; ----------------------------------------------
;; references
;; ----------------------------------------------
;; The Art of Multiprocessor Programming, Herlihy & Shavit, page. 16
;; http://onclojure.com/2009/03/04/dorun-doseq-doall/
;; http://thinkrelevance.com/blog/2008/09/18/pcl-clojure-chapter-7.html
;; http://clojure.org/concurrent_programming