Modeling The Dining Philosophers Algorithm Inwards Tla+
In this ship I volition render a modeling of the dining philosophers algorithm inwards TLA+. If you lot remove keep non heard well-nigh TLA+ before, accept a await at my before posts on TLA+ to acquire some context. Post1 too Post2
The dining philosophers occupation is an instance/refinement of the usual exclusion problem. The specification of the usual exclusion occupation dictates that when a node is inwards critical section, no other node inwards the organisation tin hold upward inwards the critical section. The dining philosopher relaxes this yesteryear taking into occupation organisation human relationship the topology: When a node is inwards critical section, none of the neighbors of that node tin hold upward inwards critical section. Note that, this does non dominion out 2 nodes to hold upward inwards critical department simultaneously provided that they are non neighbors.
In the original formulation of the dining philosophers occupation yesteryear Dijkstra, at that spot are v philosophers sitting closed to a table. Between each philosopher is a fork and, inwards social club to swallow a philosopher must concur both of the forks. (The spaghetti is actually messy.) The philosophers cycle betwixt iii states: thinking, hungry, too eating. The dining philosopher protocol should satisfy 1. (safety) if a procedure is eating neither of its left vecino or correct vecino tin hold upward eating, too 2. (progress) if a procedure is hungry, eventually it gets to eat.
Dijkstra's formulation is an instance of a token-based approach to usual exclusion. Unlike token-based solutions to usual exclusion where at that spot is exclusively 1 token inwards the organisation (as exclusively 1 node is allowed to hold upward inwards the critical department at whatever given time), the dining philosophers formulation relaxes the requirement too introduces 1 token (i.e., fork) per edge. A node that is eating needs to own all the forks on its side, thence the security status is easily satisfied: if a procedure is eating, neither/none of its neighbors tin hold upward eating. The progress status on the other mitt is to a greater extent than trickier to satisfy too nosotros volition devote most of our attending on satisfying the progress status inwards the below algorithms.
There are northward processes from 0..N-1. (You tin render northward at model-checking time.) Each procedure is symmetric, they execute the same code instantiated alongside their ID. Each procedure has a variable called state, too loops through selecting iii actions. From "state=thinking", the procedure tin transition to "hungry". A hungry procedure commencement waits till the fork on its correct is available too and then grabs it. The hungry procedure too then waits till the fork on its left is available too grabs it, too transitions into eating state. An "eating" procedure tin transition to "thinking" yesteryear releasing its left too correct forks.
OK, let's remove keep the birds too bees beak now. How practice nosotros model a organisation at a suitable abstraction layer? When nosotros are trying to acquire the basics of the algorithm right, nosotros don't demand to model the protocol at a message passing level. Let's acquire it correct at the shared retentiveness model first. Modeling the organisation at a suitable abstraction layer is an art. Novice users oftentimes brand the fault of writing Java-like iterative programs alongside PlusCal. This makes the code long too every bit good rattling tedious for model checking. After seeing improve ways to model systems looking at other PlusCal code examples, novice users gradually larn to write to a greater extent than declarative math-like specifications. I believe this latter trend of thinking every bit good helps improve their organisation pattern skills every bit good (which is what makes me most excited well-nigh using/teaching TLA+). I observe that 1 time you lot acquire the "define" block right, the residuum of the PlusCal algorithm practically writes itself. But you lot may demand to brand a span unsuccessful takes before you lot figure out the most suitable "define" block that leads to a succinct too elegant model.
In my modeling I role a shortcut to model the forks betwixt 2 process. There are northward forks, so I model the forks using an array of size N. The left fork of a philosopher is the fork that resides at the array index given yesteryear the ID of that philosopher. The correct fork of a philosopher is the fork at index=ID+1 (modulo N). I say that a fork is available for grabs if the fork's value is develop to N. When a procedure grabs its left fork or correct fork, the fork's value is assigned to hold upward equal to the ID of that process, so nosotros announce that the fork is non available anymore. (Note that "self" refers to the ID of the process.)
When nosotros model-check our algorithm, TLA+ complains too alerts us to a deadlock. Below is the deadlock draw provided yesteryear TLA+. You tin consider that all procedure are blocked at label "E:" where each 1 of them is waiting to remove handgrip of its left fork. You tin click on each stride inwards the draw to consider the programme nation at that step, too consider how the in conclusion deadlock nation is reached every bit a result. The occupation turns out to hold upward this: all the processes commencement grabbed their correct fork, too when they sweat to remove handgrip of their left fork, they can't because those forks remove keep been grabbed yesteryear their respective correct neighbors every bit a correct fork.
When nosotros model banking concern gibe this code, nosotros observe that since the symmetry is broken, the deadlock is avoided. However, TLA+ nevertheless complains well-nigh starvation. The "NoStarvation" predicate asserts that it is ever the instance that if a procedure is hungry, eventually that procedure gets to eat. In other words, no procedure starves. When nosotros inquire TLA+ to banking concern gibe NoStarvation inwards the temporal properties, TLA+ produces the next long counterexample. Inspecting the loop from nation xix to nation 28, you lot consider that procedure 2 tin acquire to swallow over again too over again spell procedure 1 too 0 remains at the "hungry" nation too starve. This counterexample is possible alongside a weak-fair scheduler. The scheduler chooses procedure 1 to execute every so often, just exclusively when its left fork is unavailable so its left-fork remove handgrip of activity is disabled. (A strongly-fair scheduler would solve this deadlock, because procedure 1 volition acquire chosen to execute the left-fork-grab activity when the guard of the left-fork-grab is enabled. You tin tell TLA+ to role strong-fairness yesteryear typing "fair+ process" inwards the PlusCal code. Also you lot would demand to supersede the either or create alongside an "if else if else if else" construct, so TLA+ scheduler cannot acquire away alongside choosing to execute an inactive "or branch".)
The agency to solve this occupation nether weak fairness is to innovate a flag to trim down the priority of a procedure 1 time it eats, so that a hungry vecino volition remove keep higher priority too tin acquire to eat. We are going to await at such a solution inwards the adjacent weblog ship on TLA+: the hygienic philosophers algorithm.
Dining Philosophers alongside a distinguished procedure model inwards TLA+
The PlusCal code for the 2 programs are accessible through the higher upward links. When you lot desire to model banking concern gibe the program, start a novel model, too move into iii for N, so the model checker is cook to start. In the model checker tab, click on Invariant pane too move into ME, so that the ME predicate is checked against whatever violation, too inwards the Properties pane move into NoStarvation so that the progress belongings is checked for satisfaction. If you lot brand a modification to the PlusCal code, brand certain you lot click on File, Translate Algorithm, so the PlusCal code gets translated to the TLA+ code, which is too then used for the model-checking. See the TLA+ posts below well-nigh how this works.
My sense alongside using TLA+ inwards distributed systems class
There is a vibrant Google Groups forum for TLA+: https://groups.google.com/forum/#!forum/tlaplus
By clicking on label "tla" at the destination of the ship you lot tin attain all my posts well-nigh TLA+
The dining philosophers occupation is an instance/refinement of the usual exclusion problem. The specification of the usual exclusion occupation dictates that when a node is inwards critical section, no other node inwards the organisation tin hold upward inwards the critical section. The dining philosopher relaxes this yesteryear taking into occupation organisation human relationship the topology: When a node is inwards critical section, none of the neighbors of that node tin hold upward inwards critical section. Note that, this does non dominion out 2 nodes to hold upward inwards critical department simultaneously provided that they are non neighbors.
In the original formulation of the dining philosophers occupation yesteryear Dijkstra, at that spot are v philosophers sitting closed to a table. Between each philosopher is a fork and, inwards social club to swallow a philosopher must concur both of the forks. (The spaghetti is actually messy.) The philosophers cycle betwixt iii states: thinking, hungry, too eating. The dining philosopher protocol should satisfy 1. (safety) if a procedure is eating neither of its left vecino or correct vecino tin hold upward eating, too 2. (progress) if a procedure is hungry, eventually it gets to eat.
Dijkstra's formulation is an instance of a token-based approach to usual exclusion. Unlike token-based solutions to usual exclusion where at that spot is exclusively 1 token inwards the organisation (as exclusively 1 node is allowed to hold upward inwards the critical department at whatever given time), the dining philosophers formulation relaxes the requirement too introduces 1 token (i.e., fork) per edge. A node that is eating needs to own all the forks on its side, thence the security status is easily satisfied: if a procedure is eating, neither/none of its neighbors tin hold upward eating. The progress status on the other mitt is to a greater extent than trickier to satisfy too nosotros volition devote most of our attending on satisfying the progress status inwards the below algorithms.
PlusCal modeling of naive dining philosophers
Here is a PlusCal algorithm modeling of the dining philosophers problem.
There are northward processes from 0..N-1. (You tin render northward at model-checking time.) Each procedure is symmetric, they execute the same code instantiated alongside their ID. Each procedure has a variable called state, too loops through selecting iii actions. From "state=thinking", the procedure tin transition to "hungry". A hungry procedure commencement waits till the fork on its correct is available too and then grabs it. The hungry procedure too then waits till the fork on its left is available too grabs it, too transitions into eating state. An "eating" procedure tin transition to "thinking" yesteryear releasing its left too correct forks.
OK, let's remove keep the birds too bees beak now. How practice nosotros model a organisation at a suitable abstraction layer? When nosotros are trying to acquire the basics of the algorithm right, nosotros don't demand to model the protocol at a message passing level. Let's acquire it correct at the shared retentiveness model first. Modeling the organisation at a suitable abstraction layer is an art. Novice users oftentimes brand the fault of writing Java-like iterative programs alongside PlusCal. This makes the code long too every bit good rattling tedious for model checking. After seeing improve ways to model systems looking at other PlusCal code examples, novice users gradually larn to write to a greater extent than declarative math-like specifications. I believe this latter trend of thinking every bit good helps improve their organisation pattern skills every bit good (which is what makes me most excited well-nigh using/teaching TLA+). I observe that 1 time you lot acquire the "define" block right, the residuum of the PlusCal algorithm practically writes itself. But you lot may demand to brand a span unsuccessful takes before you lot figure out the most suitable "define" block that leads to a succinct too elegant model.
In my modeling I role a shortcut to model the forks betwixt 2 process. There are northward forks, so I model the forks using an array of size N. The left fork of a philosopher is the fork that resides at the array index given yesteryear the ID of that philosopher. The correct fork of a philosopher is the fork at index=ID+1 (modulo N). I say that a fork is available for grabs if the fork's value is develop to N. When a procedure grabs its left fork or correct fork, the fork's value is assigned to hold upward equal to the ID of that process, so nosotros announce that the fork is non available anymore. (Note that "self" refers to the ID of the process.)
When nosotros model-check our algorithm, TLA+ complains too alerts us to a deadlock. Below is the deadlock draw provided yesteryear TLA+. You tin consider that all procedure are blocked at label "E:" where each 1 of them is waiting to remove handgrip of its left fork. You tin click on each stride inwards the draw to consider the programme nation at that step, too consider how the in conclusion deadlock nation is reached every bit a result. The occupation turns out to hold upward this: all the processes commencement grabbed their correct fork, too when they sweat to remove handgrip of their left fork, they can't because those forks remove keep been grabbed yesteryear their respective correct neighbors every bit a correct fork.
Modeling dining philosophers alongside a distinguished philosopher
As a full general regulation inwards conflict resolution, it is necessary to interruption the symmetry. As long every bit each philosopher looks precisely similar the others, the occupation is hopeless, the processes run across a deadly embrace. So let's differentiate procedure 0 every bit beingness lefty: spell all philosophers remove handgrip of their correct fork first, procedure 0 tries to remove handgrip of its left fork commencement too its correct fork later. This flake of asymmetry breaks the cyclic dependency for the availability of the forks. We changed exclusively the instant activity of the programme every bit below. When transitioning from hungry to eating, nosotros introduced an if branch. If the procedure ID is 0, the procedure grabs left fork commencement instead of grabbing its correct fork first.
When nosotros model banking concern gibe this code, nosotros observe that since the symmetry is broken, the deadlock is avoided. However, TLA+ nevertheless complains well-nigh starvation. The "NoStarvation" predicate asserts that it is ever the instance that if a procedure is hungry, eventually that procedure gets to eat. In other words, no procedure starves. When nosotros inquire TLA+ to banking concern gibe NoStarvation inwards the temporal properties, TLA+ produces the next long counterexample. Inspecting the loop from nation xix to nation 28, you lot consider that procedure 2 tin acquire to swallow over again too over again spell procedure 1 too 0 remains at the "hungry" nation too starve. This counterexample is possible alongside a weak-fair scheduler. The scheduler chooses procedure 1 to execute every so often, just exclusively when its left fork is unavailable so its left-fork remove handgrip of activity is disabled. (A strongly-fair scheduler would solve this deadlock, because procedure 1 volition acquire chosen to execute the left-fork-grab activity when the guard of the left-fork-grab is enabled. You tin tell TLA+ to role strong-fairness yesteryear typing "fair+ process" inwards the PlusCal code. Also you lot would demand to supersede the either or create alongside an "if else if else if else" construct, so TLA+ scheduler cannot acquire away alongside choosing to execute an inactive "or branch".)
The agency to solve this occupation nether weak fairness is to innovate a flag to trim down the priority of a procedure 1 time it eats, so that a hungry vecino volition remove keep higher priority too tin acquire to eat. We are going to await at such a solution inwards the adjacent weblog ship on TLA+: the hygienic philosophers algorithm.
Logistics
Naive Dining Philosophers model inwards TLA+Dining Philosophers alongside a distinguished procedure model inwards TLA+
Related Links
Using TLA+ for didactics distributed systemsMy sense alongside using TLA+ inwards distributed systems class
There is a vibrant Google Groups forum for TLA+: https://groups.google.com/forum/#!forum/tlaplus
By clicking on label "tla" at the destination of the ship you lot tin attain all my posts well-nigh TLA+
0 Response to "Modeling The Dining Philosophers Algorithm Inwards Tla+"
Post a Comment