Dining Philosophers

Dining Philosophers preview image

2 collaborators

Uri_dolphin3 Uri Wilensky (Author)
Matt Hellige (Author)

Tags

computer science 

Tagged by Reuven M. Lerner about 5 years ago

Model group CCL | Visible to everyone | Changeable by group members (CCL)
Model was written in NetLogo 5.0.4 • Viewed 474 times • Downloaded 21 times • Run 0 times
Download the 'Dining Philosophers' modelDownload this modelEmbed this model

Do you have questions or comments about this model? Ask them here! (You'll first need to log in.)


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 would happen if every philosopher immediately picked up the fork to her right, then waited for the fork to her left to become available? 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

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.

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.

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 different configurations of hungry-chance and full-chance and different numbers of philosophers. See how different combinations stress the system in different ways.

What settings produce deadlock more often? (You may want to use the speed slider to fast forward the graphics so you can do longer runs more quickly.)

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.

HOW TO CITE

If you mention this model in a publication, we ask that you include these citations for the model itself and for the NetLogo software:

COPYRIGHT AND LICENSE

Copyright 2003 Uri Wilensky.

CC BY-NC-SA 3.0

This work is licensed under the Creative Commons Attribution-NonCommercial-ShareAlike 3.0 License. To view a copy of this license, visit http://creativecommons.org/licenses/by-nc-sa/3.0/ or send a letter to Creative Commons, 559 Nathan Abbott Way, Stanford, California 94305, USA.

Commercial licenses are also available. To inquire about commercial licenses, please contact Uri Wilensky at uri@northwestern.edu.

This model was created as part of the projects: PARTICIPATORY SIMULATIONS: NETWORK-BASED DESIGN FOR SYSTEMS LEARNING IN CLASSROOMS and/or 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.

Comments and Questions

Click to Run Model

breed [philosophers philosopher]
philosophers-own [
  state                   ;; my current state: "HUNGRY", "EATING", or "THINKING"
  left-fork right-fork    ;; the forks on my right and left
  total-eaten             ;; how much I've had to eat
]

breed [forks fork]
forks-own [
  home-xpos home-ypos home-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
  clear-all
  ;; set up the model
  make-turtles
  recolor
  reset-ticks
end 

;; create all the turtles, place them, and associate forks with philosophers

to make-turtles
  set-default-shape philosophers "person torso"
  set-default-shape forks "fork"
  ;; create-ordered- equally spaces the headings of the turtles,
  ;; in who number order
  create-ordered-philosophers num-philosophers [
    set size 0.1
    jump 0.35
    set state "THINKING"
  ]
  create-ordered-forks num-philosophers [
    rt 180 / num-philosophers
    jump 0.25
    rt 180
    set size 0.1
    set marked? false
    set owner nobody
    ;; save my position and heading, so the philosophers can replace me later
    set home-xpos xcor
    set home-ypos ycor
    set home-heading heading
  ]
  ask philosophers [
    set left-fork fork (who + num-philosophers)
    ifelse who = 0
      [ set right-fork fork (2 * num-philosophers - 1) ]
      [ set right-fork fork (who + num-philosophers - 1) ]
  ]
  ask one-of forks [ set marked? true ]
end 

to go
  ask one-of philosophers [ update ]
  recolor
  tick
end 

;; everybody gets a new color.

to recolor
  ask philosophers [
    ;; look up the color in the colors list indexed by our current state
    ifelse state = "THINKING"
      [ set color blue ]
      [ ifelse state = "HUNGRY"
        [ set color red ]
        [ set color green ] ]
  ]
  ask forks [
    ;; we'll indicate marked forks only if cooperation is on.
    ifelse cooperation? and marked?
      [ set color magenta ]
      [ set color white ]
  ]
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  ;; philosopher procedure
  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 

;; just drop the forks.

to release-forks-naive  ;; philosopher procedure
  release left-fork
  release right-fork
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 [
    ask left-fork [ set marked? false ]
    ask right-fork [ set marked? true ]
  ]
  [
    ;; otherwise, check right fork.
    if [marked?] of right-fork [
      ask right-fork [ set marked? false ]
      ask left-fork [ set marked? true ]
    ]
  ]
  ;; release the forks.
  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
  ask fork [
    if owner != nobody [
      set owner nobody
      setxy home-xpos home-ypos
      set heading home-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
  if [owner] of left-fork = nobody
    [ acquire-left ]
  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
  if [owner] of left-fork = nobody [
    if ([not marked?] of left-fork) or got? right-fork
      [ acquire-left ]
  ]
  if [owner] of right-fork = nobody [
    if ([not marked?] of right-fork) or got? left-fork
      [ acquire-right ]
  ]
end 

;; grab the left fork. set its owner to me and move it

to acquire-left  ;; philosopher procedure
  ask left-fork [
    set owner myself
    move-to owner
    set heading [heading] of owner
    rt 8  fd 0.1
  ]
end 

;; grab the right fork. set its owner to me and move it

to acquire-right  ;; philosopher procedure
  ask right-fork [
    set owner myself
    move-to owner
    set heading [heading] of owner
    lt 8  fd 0.1
  ]
end 

;; I've got a fork if it's owned by me.

to-report got? [fork]  ;; philosopher procedure
  report self = [owner] of fork
end 


; Copyright 2003 Uri Wilensky.
; See Info tab for full copyright and license.

There are 10 versions of this model.

Uploaded by When Description Download
Uri Wilensky over 5 years ago Updated to NetLogo 5.0.4 Download this version
Uri Wilensky almost 6 years ago Updated version tag Download this version
Uri Wilensky almost 6 years ago Updated to version from NetLogo 5.0.3 distribution Download this version
Uri Wilensky over 6 years ago Updated to NetLogo 5.0 Download this version
Uri Wilensky about 8 years ago Updated from NetLogo 4.1 Download this version
Uri Wilensky about 8 years ago Updated from NetLogo 4.1 Download this version
Uri Wilensky about 8 years ago Updated from NetLogo 4.1 Download this version
Uri Wilensky about 8 years ago Updated from NetLogo 4.1 Download this version
Uri Wilensky over 8 years ago Model from NetLogo distribution Download this version
Uri Wilensky over 8 years ago Dining Philosophers Download this version

Attached files

File Type Description Last updated
Dining Philosophers.png preview Preview for 'Dining Philosophers' over 5 years ago, by Uri Wilensky Download

This model does not have any ancestors.

This model does not have any descendants.