breeds
[
  philosophers
  forks
]

globals
[
  HUNGRY EATING THINKING  ;; these are constants for the states
  colors                  ;; this will be a list mapping states -> colors
  table-size turtle-size  ;; constant sizes for things in the gw
  fork-offset             ;; this is a heading offset used to place the forks
  fork-distance           ;; this is a distance used to place the forks
]

philosophers-own
[
  ;; how to draw the left fork when i'm holding it
  left-fork-xpos left-fork-ypos left-fork-heading
  ;; how to draw the right fork when i'm holding it
  right-fork-xpos right-fork-ypos right-fork-heading
  state                   ;; my current state
  left-fork right-fork    ;; the forks on my right and left
  total-eaten             ;; how much i've have to eat
]

forks-own
[
  xpos ypos save-heading  ;; where i belong when i'm on the table
  owner                   ;; the philosopher that currently owns me (if any)
  marked?                 ;; whether i'm currently marked
]

to setup
  ca
  
  ; constants
  set HUNGRY 0
  set EATING 1
  set THINKING 2
  set colors [ red green blue ]
  set table-size 0.6
  set turtle-size 0.1
  set fork-offset 10
  set fork-distance 0.1

  ; set up the model
  make-turtles
  recolor

  ; set up the plots
  setup-plots
  do-plots

end

;; create all the turtles, place them, and associate forks with philosophers
to make-turtles
  locals [ new-left previous-left current-turn ]
  set previous-left nobody
  set current-turn 0
  set-default-shape philosophers "person"
  set-default-shape forks "fork"

  ;; the tactic is to create one fork and one philosopher at a time,
  ;; associating each new philosopher with the new fork and with the fork
  ;; we created last time (stored in previous-left). the direction each new
  ;; turtle faces is incremented as we go, and they're moved to the edge of 
  ;; the table.
  repeat num-philosophers
  [
    create-custom-forks 1
    [
      set color 9
      set size turtle-size
      set marked? false
      set owner nobody
      rt current-turn
      rt 360 / (2 * num-philosophers)
      jump ((table-size - turtle-size) / 2)
      rt 180 ;; turn around so i look prettier.
      set new-left self

      ;; save my position and heading, so the philosophers can replace me later
      set xpos xcor
      set ypos ycor
      set save-heading heading
    ]
    create-custom-philosophers 1
    [
      set size turtle-size
      set state THINKING
      set right-fork previous-left
      set previous-left new-left
      set left-fork new-left
      rt current-turn
      jump ((table-size + turtle-size) / 2)
      calculate-fork-positions
    ]
    set current-turn (current-turn + 360 / num-philosophers)
  ]
  ; assuming that ids are assigned to turtles monotonically, this ties the
  ; knot.
  set right-fork-of (min-one-of philosophers [ who ]) previous-left
  ask random-one-of forks
  [
    set marked? true
  ]
end

to go
  ifelse take-turns? [ update-one ] [ update-all ]
  recolor
  do-plots
end

;; here we figure out where to place the forks when we pick them up. basically
;; they go above the philosophers head, the left on the left side and the 
;; right on the right side. fork-offset determines how far apart they are, and
;; fork-distance determines how far above the head.
to calculate-fork-positions ;; philosopher procedure
  rt fork-offset
  set left-fork-xpos (xcor + dx * fork-distance)
  set left-fork-ypos (ycor + dy * fork-distance)
  set left-fork-heading heading
  lt fork-offset * 2
  set right-fork-xpos (xcor + dx * fork-distance)
  set right-fork-ypos (ycor + dy * fork-distance)
  set right-fork-heading heading
  rt fork-offset
end

;; everybody gets a new color.
to recolor
  ask philosophers
  [
    ;; look up the color in the colors list indexed by our current state
    set color (item state colors)
  ]
  ask forks
  [
    ;; we'll indicate marked forks only if cooperation is on.
    ifelse cooperation? and marked?
    [
      set color magenta
    ]
    [
      set color 9
    ]
  ]
end

to update-one
  ask random-one-of philosophers
  [
    if state = THINKING
    [
      if random-float 1.0 < hungry-chance 
      [
        set state HUNGRY
      ]
      stop
    ] 
    if state = EATING
    [
      ;; keep track of how much we're eating.
      set total-eaten (total-eaten + 1)
      if random-float 1.0 < full-chance 
      [
        ;; put down forks
        ifelse cooperation?
        [
          release-forks-smart
        ]
        [
          release-forks-naive
        ]
        ;; continue thinking
        set state THINKING
      ]
      stop
    ]
    if state = HUNGRY
    [
      ; try to pick up the forks.
      ifelse cooperation?
      [
        acquire-forks-smart
      ]
      [
        acquire-forks-naive
      ]
      ; if we've got both forks, eat.
      if got? left-fork and got? right-fork
      [
        set state EATING
      ]
      stop
    ]
  ]
end

;; here's where philosophers actually do their thing. note that a philosopher
;; can go through several states in the same call to update.
to update-all
  ask philosophers
  [
    ;; some thinking philosophers may get hungry.
    if state = THINKING
    [
      if random-float 1.0 < hungry-chance 
      [
        set state HUNGRY
      ]
      stop
    ]
    ;; some eating philosophers may get full.
    if state = EATING
    [
      ;; keep track of how much we're eating.
      set total-eaten (total-eaten + 1)
      if random-float 1.0 < full-chance 
      [
        ;; put down forks
        ifelse cooperation?
        [
          release-forks-smart
        ]
        [
          release-forks-naive
        ]
        ;; continue thinking
        set state THINKING
      ]
      stop
    ]
    if state = HUNGRY 
    [
      ; try to pick up the forks.
      ifelse cooperation?
      [
        acquire-forks-smart
      ]
      [
        acquire-forks-naive
      ]
      ; if we've got both forks, eat.
      if got? left-fork and got? right-fork
      [
        set state EATING
      ]
      stop
    ]
  ]
end

;; a more sophisticated strategy for releasing the forks, which switches any 
;; marks to the other fork. see the info tab for details.
to release-forks-smart ;; philosopher procedure
  ;; check left fork
  ifelse marked?-of left-fork
  [
    set marked?-of left-fork false
    set marked?-of right-fork true
  ]
  [
    ;; otherwise, check right fork.
    if marked?-of right-fork
    [
      set marked?-of right-fork false
      set marked?-of left-fork true
    ]
  ]
  ;; release the forks.
  release left-fork
  release right-fork
end

;; just drop the forks.
to release-forks-naive ;; philosopher procedure
  release left-fork
  release right-fork
end

;; to release a fork, we set its owner to nobody and replace it on the table.
to release [ fork ] ;; philosopher procedure
  without-interruption
  [
    set owner-of fork nobody
    ask fork
    [
      setxy xpos ypos
      set heading save-heading
    ]
  ]
end

;; just try to pick each fork up. if i get only one, i'll just hold it
;; until i get the other one.
to acquire-forks-naive ;; philosopher procedure
  ;; try left fork
  if owner-of left-fork = nobody
  [
    acquire-left
  ]
  ;; try right fork 
  if owner-of right-fork = nobody
  [
    acquire-right
  ]
end

;; a more sophisticated strategy for acquiring the forks. see the info tab
;; for details.
to acquire-forks-smart ;; philosopher procedure
  ;; try left fork
  if owner-of left-fork = nobody
  [
    if (not marked?-of left-fork) or got? right-fork
    [
      acquire-left
    ]
  ]
  ;; try right fork
  if owner-of right-fork = nobody
  [
    if (not marked?-of right-fork) or got? left-fork
    [
      acquire-right
    ]
  ]
end

;; grab the left fork
to acquire-left ;; philosopher procedure
  acquire left-fork left-fork-xpos left-fork-ypos left-fork-heading
end

;; grab the right fork
to acquire-right ;; philosopher procedure
  acquire right-fork right-fork-xpos right-fork-ypos right-fork-heading
end

;; pick up a fork by setting its owner to me and moving it to a new 
;; location
to acquire [ fork new-x new-y new-heading ] ;; philosopher procedure
  without-interruption
  [
    set owner-of fork self
    ask fork 
    [
      setxy new-x new-y
      set heading new-heading
    ]
  ]
end

;; i've got a fork if it's owned by me.
to-report got? [ fork ] ;; philosopher procedure
  report (owner-of fork) = self
end

;; set up the plots. our ranges are dynamic, so we need this.
to setup-plots
  set-current-plot "Spaghetti consumed"
  set-plot-x-range 0 (count philosophers + 1)

  set-current-plot "Resource allocation"
  set-plot-y-range 0 (count philosophers)
end

;; do the plotting.
to do-plots
  every 0.4
  [
    set-current-plot "Spaghetti consumed"
    set-current-plot-pen "default"
    plot-pen-reset
    ask philosophers [ plotxy (who / 2) total-eaten ]
  ]

  set-current-plot "Resource allocation"
  set-current-plot-pen "Thinking"
  plot (count philosophers with [ state = THINKING ])
  set-current-plot-pen "Hungry"
  plot (count philosophers with [ state = HUNGRY ])
  set-current-plot-pen "Eating"
  plot (count philosophers with [ state = EATING ])
end


; *** NetLogo Model Copyright Notice ***
;
; This model was created as part of the projects:
; PARTICIPATORY SIMULATIONS: NETWORK-BASED DESIGN FOR SYSTEMS LEARNING IN
; CLASSROOMS and INTEGRATED SIMULATION AND MODELING ENVIRONMENT.
; The project gratefully acknowledges the support of the
; National Science Foundation (REPP & ROLE programs) -- grant numbers 
; REC #9814682 and REC-0126227.
;
; Copyright 2003 by Uri Wilensky.  Updated 2003.  All rights reserved.
;
; Permission to use, modify or redistribute this model is hereby granted,
; provided that both of the following requirements are followed:
; a) this copyright notice is included.
; b) this model will not be redistributed for profit without permission
;    from Uri Wilensky.
; Contact Uri Wilensky for appropriate licenses for redistribution for
; profit.
;
; To refer to this model in academic publications, please use:
; Wilensky, U. (2003).  NetLogo Dining Philosophers model.
; http://ccl.northwestern.edu/netlogo/models/DiningPhilosophers.
; Center for Connected Learning and Computer-Based Modeling,
; Northwestern University, Evanston, IL.
;
; In other publications, please use:
; Copyright 1998 by Uri Wilensky.  All rights reserved.  See
; http://ccl.northwestern.edu/netlogo/models/DiningPhilosophers
; for terms of use.
;
; *** End of NetLogo Model Copyright Notice ***
@#$#@#$#@
GRAPHICS-WINDOW
354
10
764
441
0
0
400.0
1
10
1
1
1

CC-WINDOW
354
442
764
562
Command Center

BUTTON
7
32
76
65
NIL
setup
NIL
1
T
OBSERVER
T

BUTTON
7
72
76
105
NIL
go
T
1
T
OBSERVER
T

SLIDER
172
45
345
78
num-philosophers
num-philosophers
2
40
20
1
1
NIL

SLIDER
172
85
345
118
hungry-chance
hungry-chance
0
1.0
0.5
0.01
1
NIL

SLIDER
172
125
345
158
full-chance
full-chance
0
1.0
0.5
0.01
1
NIL

PLOT
8
199
345
379
Spaghetti consumed
Philosopher ID
Spaghetti
0.0
100.0
0.0
25.0
true
false
PENS
"default" 1.0 1 -16776961 false

PLOT
8
382
345
562
Resource allocation
Time
No. of philosophers
0.0
100.0
0.0
100.0
true
true
PENS
"Thinking" 1.0 0 -16776961 true
"Hungry" 1.0 0 -65536 true
"Eating" 1.0 0 -11352576 true

SWITCH
8
112
159
145
cooperation?
cooperation?
1
1
-1000

BUTTON
83
72
159
105
go once
go
NIL
1
T
OBSERVER
T

SWITCH
8
152
159
185
take-turns?
take-turns?
0
1
-1000

@#$#@#$#@
WHAT IS IT?
-----------
The Dining Philosophers problem is a classic case study in the synchronization of concurrent processes.  It will be familiar to many students of Computer Science, but is applicable to many situations in which several independent processes must coordinate the use of shared resources.

The problem is fairly simple.  Suppose there is a group of philosophers sitting at a round table eating spaghetti.  These are boring philosophers: they do nothing but think, get hungry and eat.  In particular, they do not communicate with one another.

A fork sits on the table in between each pair of philosophers, so there are exactly as many forks as philosophers.  However, the spaghetti is quite messy, so in order to eat, each philosopher needs to be holding two forks, both the fork to her left and the fork to her right.  Clearly, if all the philosophers are to get some spaghetti, they'll have to share the forks.

There are many ways that this can go wrong.  A given philosopher can pick up both forks and begin eating, and never stop.  This guarantees that (at least) her immediate neighbors will never get to eat.  (Though at least SOMEONE gets to eat!)

What happens if every philosopher immediately picks up the fork to her right, then waits for the fork to her left to become available?  (To try it, set hungry-chance to 1.0, turn cooperation? and take-turns? off, then press setup and go.)  This situation is called "deadlock," and it is the bane of designers of concurrent systems.

The goal of the problem is to come up with a strategy that the philosophers can use to guarantee that:
1. At least one hungry philosopher can always eat.
2. On average, all the philosophers get the same amount to eat.

There is one other feature of the system that aids in finding a solution: while a philosopher is holding a fork, she has the ability to place a mark on it or to remove an existing mark.  These marks are visible to any philosopher who inspects the fork.  One random fork will always start out marked, but in order to avoid confusion, marked forks are not visually distinguished unless cooperation is enabled (in which case they are a different color).

Can you think of a way to feed the philosophers?

Remember that the philosophers shouldn't, in principle, communicate (apart from marking forks, though that arguably constitutes a communication channel).  This means that the assignment of global group properties (such as "even/odd-numbered philosophers" or "first philosopher") is not allowed.  The astute reader will note that the initial marking of a single fork violates this rule by assigning a globally unique property to a single philosopher.  In the absence of such an initially distinguished fork, can you think of a way to feed the philosophers?


HOW IT WORKS
------------
There are two types of agents: philosophers and forks.  Philosophers know which fork is on their left and which fork is on their right.  They also know what state they're in (thinking, hungry or eating) and how much they've eaten in total.  Forks know who they're currently being held by, if anyone, and whether or not they're marked.

To pick up a fork, a philosopher must first check that the fork isn't already being held by his associate, then set the fork's owner to himself.  It is possible in this model to steal a fork from another philosopher, therefore it is up to each philosopher not to do so.

To release a fork, a philosopher simply sets the fork's owner to nobody.

All the philosophers are initially thinking (blue).  At each time step, a thinking philosopher may become hungry (red) with probability hungry-chance.  A hungry philosopher will try to acquire both forks, and until she has done so will remain hungry.  A hungry philosopher with both forks immediately begins eating (green).  An eating philosopher may become full with probability full-chance, at which point she will release both forks and resume thinking (blue).

The value of the cooperation? switch determines which strategy is used to acquire and release the forks. With cooperation off, the following naive strategy is used to pick up the forks:
1. If the left fork is available, take it.
2. If the right fork is available, take it.
3. If you have both forks, begin eating. Otherwise, try again.
When full, the forks are simply released. Marks are completely ignored.

With cooperation on, a more sophisticated strategy using marks is used. To acquire the forks:
1. If the left fork is available, take it.
2. If you have the left fork and it is marked and you're not already holding the right fork, release the left fork.
3. If the right fork is available, take it.
4. If you have the right fork and it is marked and you're not already holding the left fork, release the right fork.
5. If you have both forks, begin eating. Otherwise, try again.
Once you are done eating, to release the forks:
1. If either fork is marked, unmark it and mark the other fork.
2. Release the forks.


HOW TO USE IT
-------------
Initial settings:
- num-philosophers: how many philosophers you'd like to feed.

The setup button will set the initial conditions. The go button will run the simulation, and the "go once" button will run the simulation for just one step, allowing you to watch what happens in more detail.

Other settings:
- hungry-chance: The probability of any thinking philosopher becoming hungry at any step.
- full-chance: The probability of any eating philosopher becoming full at any step.
- cooperation?: If off, the philosophers will use a naive strategy to acquire their forks; if on, they'll use a more sophisticated strategy. See HOW IT WORKS above.
- take-turns?: If on, only one philosopher will be allowed to move per time step (i.e., per press of "go once"); if off, every philosopher will be given a chance to move. Note that with take-turns? on, some philosophers may move twice before all the philosophers have moved. On average, however, the philosophers will each get the same number of turns.

Plots:
- Spaghetti consumed: plots the amount of spaghetti each philosopher has consumed (based on how many time steps she has spent in the eating state).
- Resource allocation: plots the number of philosophers in each state over time.


THINGS TO NOTICE
----------------
Play with take-turns? for different configurations of hungry-chance and full-chance and different numbers of philosophers.  Notice that take-turns? effects more than just the speed of the simulation, because not all the philosophers are guaranteed to get a chance to move once before any are allowed to move a second time.  Do you think that, in the long run, this will make a difference in the outcomes of simulations?  Why or why not? If so, under what circumstances?

Play with different configurations of hungry-chance and full-chance.  See how different combinations stress the system in different ways.  Notice how, although the system works well under certain circumstances, more stressful circumstances may expose a weakness.  This demonstrates the importance of "stress testing" when assessing the scalability of a system, particularly in the presence of concurrency.


THINGS TO TRY
-------------
Experiment with cooperation in combination with different settings for hungry-chance and full-chance.  See if you can find a situation where there is a striking contrast between the behaviors of the cooperating philosophers and the naive philosophers.

Try running the system for a long time in a variety of different configurations.  Does it ever seem to perform well at first, but eventually degrade (and maybe even deadlock)?  What about vice versa?  What do you think this shows about the value of "longevity testing" when assessing the stability and performance of a concurrent system?


EXTENDING THE MODEL
-------------------
Try to think of a different strategy for the philosophers, then implement it and see how well it works!  You will probably want to make use of marks, so remember that they are not visible unless cooperation is enabled; you may wish to change this.  Can you come up with a simpler strategy than the one we demonstrate?

Can you think of other configurations of processes and resources that might be interesting to experiment with?  For example, suppose there is one salt shaker on the table where all the philosophers can reach it, and suppose that each time a philosopher has acquired both forks, she must acquire the salt shaker and salt her spaghetti before she begins eating.  She can release the salt shaker after only one time step (i.e., before she finishes eating her pasta and releases the forks), so several philosophers can still eat at once.  Can this modification lead to deadlock? What if there are both salt and pepper?  Test your intuition!

There are many, many other such possibilities, and many are directly analogous to situations that frequently arise in practical resource allocation problems.


CREDITS AND REFERENCES
----------------------
Thanks to Matt Hellige for his work on this model.

To refer to this model in academic publications, please use: Wilensky, U. (2003). NetLogo Dining Philosophers model. http://ccl.northwestern.edu/netlogo/models/Dining Philsophers.  Center for Connected Learning and Computer-Based Modeling, Northwestern University, Evanston, IL.

In other publications, please use: Copyright 2003 by Uri Wilensky.  All rights reserved.  See http://ccl.northwestern.edu/netlogo/models/Dining Philsophers for terms of use.
@#$#@#$#@
default
true
0
Polygon -7566196 true true 150 5 40 250 150 205 260 250

box
true
0
Polygon -7566196 true true 45 255 255 255 255 45 45 45

circle
false
0
Circle -7566196 true true 0 0 300

fork
true
0
Polygon -7566196 true true 160 247 150 251 140 248 147 107 129 97 133 29 137 86 141 86 147 38 151 86 155 84 159 39 166 96 154 105

got-both
true
0
Circle -7566196 true true 116 27 68
Polygon -7566196 true true 140 95 141 115 97 125 63 222 57 232 57 248 67 250 75 245 77 237 111 174 120 257 182 257 192 175 225 241 227 248 235 251 239 251 248 242 243 231 239 232 206 126 163 114 161 92
Polygon -7566196 true true 240 237 253 192 249 188 257 168 256 187 263 173 260 189 268 179 262 198 258 196
Polygon -7566196 true true 61 238 39 197 35 198 25 179 38 194 33 175 41 192 39 173 49 194 44 196

got-left
true
0
Circle -7566196 true true 116 27 68
Polygon -7566196 true true 140 95 141 115 97 125 63 222 57 232 57 248 67 250 75 245 77 237 111 174 120 257 182 257 192 175 225 241 227 248 235 251 239 251 248 242 243 231 239 232 206 126 163 114 161 92
Polygon -7566196 true true 240 237 253 192 249 188 257 168 256 187 263 173 260 189 268 179 262 198 258 196

got-right
true
0
Circle -7566196 true true 116 27 68
Polygon -7566196 true true 140 95 141 115 97 125 63 222 57 232 57 248 67 250 75 245 77 237 111 174 120 257 182 257 192 175 225 241 227 248 235 251 239 251 248 242 243 231 239 232 206 126 163 114 161 92
Polygon -7566196 true true 61 239 32 195 29 200 23 175 32 193 29 172 37 192 35 173 44 191 40 198

person
true
0
Circle -7566196 true true 116 27 68
Polygon -7566196 true true 140 95 141 115 97 125 63 222 57 232 57 248 67 250 75 245 77 237 111 174 120 257 182 257 192 175 225 241 227 248 235 251 239 251 248 242 243 231 239 232 206 126 163 114 161 92

turtle
true
0
Polygon -7566196 true true 138 75 162 75 165 105 225 105 225 142 195 135 195 187 225 195 225 225 195 217 195 202 105 202 105 217 75 225 75 195 105 187 105 135 75 142 75 105 135 105

@#$#@#$#@
NetLogo 2.0beta5
@#$#@#$#@
@#$#@#$#@
@#$#@#$#@