NetLogo User Community Models

(back to the NetLogo User Community Models)

Download If clicking does not initiate a download, try right clicking or control clicking and choosing "Save" or "Download".(The run link is disabled for this model because it was made in a version prior to NetLogo 6.0, which NetLogo Web requires.)

## BACKGROUND

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 [Wilensky, 2003]

## PROBLEM STATEMENT

Consider the famous synchronization problem consisting of a group of N hungry philosophers who spend some time thinking between copious meals of spaghetti. There are only N forks on a circular table and there is a fork between two philosophers.

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 (SYSTEM MODEL)

The layout is split in two areas.

The upper area, labelled as 'canvas' is where the observer can see the problem-world.

The lower area, called 'Petri' contains the Petri net that rules the system.

Philosopher agents know which fork is on their left and which fork is on their right. An arc connects a philosopher to her left fork. Another arc to her right fork.

They also know what state they're in (thinking, hungry or eating) and how much they've eaten in total.

Fork agents know they are busy when tehy leave from their home position. When a fork is at its home position, it can be seized by a philosopher in its neighbor. (arc-connected to)

All the philosophers are initially thinking (blue). A thinking philosopher is always hungry. She 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).

This logic is supported by the Petri net (lower area in the layout).

See the model section.

## 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:

- bu-prob-still-hungry: The probability of any eating philosopher to continue eating next period of time.

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

In the command center (console) the observer can see what the system is doing (trace). More detailed trace is shown when bu-debug-mode? is 'on'.

## THINGS TO TRY

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.

## MODEL

In the model, there are three places; places contain two types of tokens, the first type is associated with the philosophers and the second is associated with forks. The arcs are labeled by the token variables. A token has a number of attributes. The tokens residing in both the places “think” and “free forks” have two attributes: the first attribute being its type and the second attribute being its identity, id. The tokens residing in the place “eat”, have four attributes: the first two ones are the same as in place “think”, and the last two ones are the ids of the forks currently used by the philosopher. The transition “take forks” is associated with the predicate which specifies the correct relation between a philosopher and the two forks used by him. The predicate inscribed on transition “take forks” as i = j is a concise form of expressing that the second attribute of a <p, i> token should match the second attribute of the two tokens representing the forks. This means that a philosopher can eat only when the two adjacent forks are free. For example, the forks <f, 3> and <f, 4> must be free in order to allow the philosopher <p, 3> to move to the eating place. Note that a predicate expresses an imperative condition which must be met in order for a transition to fire. A predicate should not be used to express the result associated with transition “put down forks”, although there is a well-defined relationship between the attributes of the tokens released when “put down forks” fires.

## EXTENDING THE MODEL - MANAGING VERSIONS

The current version (1.03) has 468 LOC (lines of code).

Try to think of a different strategy for the philosophers, then implement it and see how well it works!

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.

## REFERENCES

* 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.

* Wilensky, U. (1999). NetLogo. http://ccl.northwestern.edu/netlogo/. Center for Connected Learning and Computer-Based Modeling, Northwestern University, Evanston, IL.

* Wang, Jiacun. "Petri nets for dynamic event-driven system modeling." Handbook of Dynamic System Modeling (2007): 1-17.
http://bluehawk.monmouth.edu/~jwang/Ch024.pdf

* Zurawski, Richard, and MengChu Zhou. "Petri nets and industrial applications: A tutorial." Industrial Electronics, IEEE Transactions on 41.6 (1994): 567-583.
http://www.stevens-tech.edu/wireless/research/petrinet/reading-petri-net-tutorial-zurawski-zhou.pdf

* http://cpntools.org/_media/book/cpn.pdf

## CREDITS

josegual@esce.ipvc.pt
June 2015