Modeling The Hygienic Dining Philosophers Algorithm Inward Tla+
This postal service on hygienic dining philosophers algorithm is the continuation of the postal service on dining philosophers. If you lot haven't seen that one, it is improve to read that origin before you lot croak on with this one.
The hygienic dining philosophers algorithm (due to Chandy & Misra 1984) generalizes the telephone topology of the dining philosophers algorithm to an arbitrary undirected graph. The most of import contribution of the hygienic philosophers algorithm is that it introduces a priority concept that ensures "No Starvation" fifty-fifty nether weak fairness. (NoStarvation == \A p \in Procs: state[p]="Hungry" > state[p]="Eating") The scheme deprioritizes a procedure that has eaten so the procedure cannot greedily trounce its neighbors to eating again. This is achieved past times flagging the forks of a procedure that has eaten every bit "dirty". Dirty forks announce that the procedure has merely eaten, hence that procedure needs to furnish the fork to whatever of its neighbors that asked for the muddy fork.
I modeled "forks" in addition to "request tokens" every bit sets every bit well. The modeling of forks in addition to requests are directional, in addition to the definitions of "Forkat" in addition to "Reqat" reflects this point. I also modeled "clean forks" every bit a set: if a fork is clean, the fork is listed inward the laid "Clean". (I mightiness lead hold gone wild with using sets for modeling all the information structures of the algorithm. But inward my defense, sets are i of the simplest information structures, in addition to are flexible in addition to useful.)
Now let's utter close the initialization of the forks, request-tokens, in addition to build clean forks set. The initial placement of forks in addition to their marker every bit build clean or muddy determines the initial priority relation with the processes. So, when nosotros initialize, nosotros must live on careful non to innovate a cycle, since that would lawsuit inward a deadlock. Therefore, a construction should live on imposed on the graph such that it is a directed acyclic graph (DAG).
The recommended initialization is that initially all the forks are muddy (i.e., Clean={}) in addition to each procedure is "Thinking". If a procedure becomes hungry, it tin in addition to so acquire the forks it requests (since they are already dirty) without waiting on other procedure (which may non lead hold the inclination) to consume first. For simplicity, I decided to assign the muddy forks to the lower id procedure of an edge, so I initialized the fork laid to live on equal to the Topology set. (Of course of didactics inward the fork laid the edges are directional: the procedure that comes before inward the border tuple denotes that fork resides at that side of the edge.) Since I had to brand certain that the asking token is non on the side of the muddy fork (because that would live on misinterpreted every bit the other node asking for the fork inward the initial state) I initialized the request-token laid to live on equal to the contrary of the Topology set.
But origin the procedure checks if it needs to respond to whatever requests ship to it for forks in addition to does so if its nation is non "Eating". The requests for the muddy forks are answered within a piece loop iteration. That a fork is muddy indicates the procedure has a lower priority in addition to must defer. It does so past times sending the fork to the other side, in addition to "cleaning" the fork piece it is existence passed to the neighbor.
Else if the procedure is hungry in addition to has unopen to forks to request, the procedure starts requesting its missing forks. For this, the procedure needs to iterate through its neighbors via a piece loop. It sets Q to live on the laid of neighbors for which a fork needs to live on requested. Then, inward each iteration of the loop, a vecino is picked out from this set, in addition to the asking is sent to that neighbor's side. The piece loop is completed when all neighbors are covered ---set Q becomes an empty set.
Otherwise, if the procedure is "Hungry", in addition to satisfies all the atmospheric condition to eat, it transitions to the "Eating" state. The atmospheric condition are: the procedure has all the forks inward following edges on its side, in addition to each fork is either clean, or the muddy forks lead hold non received requests yet. In other words, a procedure tin consume with unopen to of the forks existence dirty, provided that the corresponding neighbors for those muddy forks are non hungry in addition to lead hold non ship requests for those forks. Since a procedure eats exclusively when it has all the forks on its side, nosotros are guaranteed that when a procedure is eating none of its neighbors tin live on eating. (Otherwise a fork would live on inward both sides of the edge, which would violate TypeOkFork predicate.)
If a procedure is Eating, it tin transition to Thinking. For this, the procedure marks all its forks every bit dirty, iterating over a piece loop.
Finally if a procedure is Thinking, it tin transition to Hungry anytime.
I flora that this corresponds reasonably good to the atomicity distributed shared retention model, where a procedure tin write to i vecino inward i step, but cannot write to multiple neighbors at once.
The 2nd põrnikas was much to a greater extent than subtle. When a hungry procedure was requesting tokens, I had written the asking token subtraction exterior the if clause. (There was an if clause checking vecino should live on sent the request. And I had the asking add-on (req:= req \union {<<q,self>>};) within the if, asking subtraction exterior the if (Hii: req:= req \ {<<self,q>>};). So the model checker was maliciously timing the other procedure to ship the fork, in addition to and so ship a asking for that fork back. Then when the occupation "Hii: req:= req \ {<<self,q>>}" is executed the removal of the asking token would live on removing the genuine asking ship dorsum from that other process, non the ghost of the asking token that the procedure had sent inward the origin place. At that dot I hadn't written the TypeOK predicates inward my model, so I didn't grab this quickly. Instead, I had to figure this subtle põrnikas past times inspecting a line of 61 steps (the smallest publish of steps needed to exercise this bug). The lesson I learned is non to procrastinate close checking for the TypeOK predicates for ensuring audio updating of the information structures.
Finally, the tertiary põrnikas was also real subtle. I had a "doneReq" flag to avoid unnecessary requesting of forks, if the forks were requested before. Again the model checker was existence a jerk in addition to finding a rare sequencing of events to surface a rare bug. The line was 55 steps, repeating later mensuration 43. The procedure 3 kept eating, piece 0, 1, in addition to two starved. Processes 0, 1, in addition to two are hungry, in addition to since their doneReq flag was true, they didn't ship additional requests. They didn't genuinely ship asking to procedure 3 because they already had the muddy token on their side. But in addition to so procedure 3 ship them the asking in addition to got those tokens. And procedure 0,1,2 are non sending the asking again, because they cry back they are done with requests. I fixed the occupation past times removing the doneReq flag but instead checking for the demand for requesting. This also sped upwardly model checking, every bit less nation is maintained.
My initial attempts had took close 4GB of infinite in addition to progressed slowly, which led me stopping them. To speed upwardly the model checking, I improved the answering of requests for forks past times making the GetReqNbrs business office to a greater extent than selective past times adding the 2nd occupation to that check. Seeing that it helped speed upwardly model checking, I also wrote a to a greater extent than selective GetForkNbrs function. These reduced the nation space, in addition to the execution time. But I nonetheless can't essay checking with to a greater extent than than four processes every bit that takes a long time.
Here is the terminal right version of the model
Here is the version that has põrnikas 3
My sense with using TLA+ inward 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 postal service you lot tin compass all my posts close TLA+
The hygienic dining philosophers algorithm (due to Chandy & Misra 1984) generalizes the telephone topology of the dining philosophers algorithm to an arbitrary undirected graph. The most of import contribution of the hygienic philosophers algorithm is that it introduces a priority concept that ensures "No Starvation" fifty-fifty nether weak fairness. (NoStarvation == \A p \in Procs: state[p]="Hungry" > state[p]="Eating") The scheme deprioritizes a procedure that has eaten so the procedure cannot greedily trounce its neighbors to eating again. This is achieved past times flagging the forks of a procedure that has eaten every bit "dirty". Dirty forks announce that the procedure has merely eaten, hence that procedure needs to furnish the fork to whatever of its neighbors that asked for the muddy fork.
PlusCal modeling of the algorithm
Here is my PlusCal algorithm modeling of the hygienic dining philosophers problem.Initialization in addition to Modeling
I model the Topology every bit a set. Since nosotros are looking at a undirected graph, the edges are bidirectional. Our Definition of "Edge" predicate, in addition to consequentially that of "GetNbrs", reverberate the bidirectionality of the edges.
I modeled "forks" in addition to "request tokens" every bit sets every bit well. The modeling of forks in addition to requests are directional, in addition to the definitions of "Forkat" in addition to "Reqat" reflects this point. I also modeled "clean forks" every bit a set: if a fork is clean, the fork is listed inward the laid "Clean". (I mightiness lead hold gone wild with using sets for modeling all the information structures of the algorithm. But inward my defense, sets are i of the simplest information structures, in addition to are flexible in addition to useful.)
Now let's utter close the initialization of the forks, request-tokens, in addition to build clean forks set. The initial placement of forks in addition to their marker every bit build clean or muddy determines the initial priority relation with the processes. So, when nosotros initialize, nosotros must live on careful non to innovate a cycle, since that would lawsuit inward a deadlock. Therefore, a construction should live on imposed on the graph such that it is a directed acyclic graph (DAG).
The recommended initialization is that initially all the forks are muddy (i.e., Clean={}) in addition to each procedure is "Thinking". If a procedure becomes hungry, it tin in addition to so acquire the forks it requests (since they are already dirty) without waiting on other procedure (which may non lead hold the inclination) to consume first. For simplicity, I decided to assign the muddy forks to the lower id procedure of an edge, so I initialized the fork laid to live on equal to the Topology set. (Of course of didactics inward the fork laid the edges are directional: the procedure that comes before inward the border tuple denotes that fork resides at that side of the edge.) Since I had to brand certain that the asking token is non on the side of the muddy fork (because that would live on misinterpreted every bit the other node asking for the fork inward the initial state) I initialized the request-token laid to live on equal to the contrary of the Topology set.
Process actions
Each procedure is initialized to start inward Thinking state. The procedure in addition to so loops through checking appropriate actions for its electrical flow state, in addition to perform nation transitions when atmospheric condition are met.
But origin the procedure checks if it needs to respond to whatever requests ship to it for forks in addition to does so if its nation is non "Eating". The requests for the muddy forks are answered within a piece loop iteration. That a fork is muddy indicates the procedure has a lower priority in addition to must defer. It does so past times sending the fork to the other side, in addition to "cleaning" the fork piece it is existence passed to the neighbor.
Else if the procedure is hungry in addition to has unopen to forks to request, the procedure starts requesting its missing forks. For this, the procedure needs to iterate through its neighbors via a piece loop. It sets Q to live on the laid of neighbors for which a fork needs to live on requested. Then, inward each iteration of the loop, a vecino is picked out from this set, in addition to the asking is sent to that neighbor's side. The piece loop is completed when all neighbors are covered ---set Q becomes an empty set.
Otherwise, if the procedure is "Hungry", in addition to satisfies all the atmospheric condition to eat, it transitions to the "Eating" state. The atmospheric condition are: the procedure has all the forks inward following edges on its side, in addition to each fork is either clean, or the muddy forks lead hold non received requests yet. In other words, a procedure tin consume with unopen to of the forks existence dirty, provided that the corresponding neighbors for those muddy forks are non hungry in addition to lead hold non ship requests for those forks. Since a procedure eats exclusively when it has all the forks on its side, nosotros are guaranteed that when a procedure is eating none of its neighbors tin live on eating. (Otherwise a fork would live on inward both sides of the edge, which would violate TypeOkFork predicate.)
If a procedure is Eating, it tin transition to Thinking. For this, the procedure marks all its forks every bit dirty, iterating over a piece loop.
Finally if a procedure is Thinking, it tin transition to Hungry anytime.
A greenback close the usage of labels
As I alluded to inward the previous posts, the labels are non in that location for cosmetic reasons. They determine the granularity of steps. The TLA+ conversion of the PlusCal code uses the labels. So if you lot forget to position a label where it is needed, TLA+ volition warn you lot close it. For example, TLA+ dictates that a piece loop has a label. This agency that each iteration of the piece loop tin live on atomic, but the entire piece loop cannot live on executed every bit i atomic step. TLA+ does non allow for updating the same variable twice inward i step. So TLA+ complained in addition to required me to add together "Hii:" in addition to "Aii" labels.I flora that this corresponds reasonably good to the atomicity distributed shared retention model, where a procedure tin write to i vecino inward i step, but cannot write to multiple neighbors at once.
Bugs
I flora 3 bugs inward my before versions of the code through model checking. The origin was on the guard of the "Hungry" to "Eating" transition. I had wrote "Edge(self,k)" every bit a conjunction. After TLA toolkit line showed me my mistake, I corrected that to "Edge(self,k)=>".The 2nd põrnikas was much to a greater extent than subtle. When a hungry procedure was requesting tokens, I had written the asking token subtraction exterior the if clause. (There was an if clause checking vecino should live on sent the request. And I had the asking add-on (req:= req \union {<<q,self>>};) within the if, asking subtraction exterior the if (Hii: req:= req \ {<<self,q>>};). So the model checker was maliciously timing the other procedure to ship the fork, in addition to and so ship a asking for that fork back. Then when the occupation "Hii: req:= req \ {<<self,q>>}" is executed the removal of the asking token would live on removing the genuine asking ship dorsum from that other process, non the ghost of the asking token that the procedure had sent inward the origin place. At that dot I hadn't written the TypeOK predicates inward my model, so I didn't grab this quickly. Instead, I had to figure this subtle põrnikas past times inspecting a line of 61 steps (the smallest publish of steps needed to exercise this bug). The lesson I learned is non to procrastinate close checking for the TypeOK predicates for ensuring audio updating of the information structures.
Finally, the tertiary põrnikas was also real subtle. I had a "doneReq" flag to avoid unnecessary requesting of forks, if the forks were requested before. Again the model checker was existence a jerk in addition to finding a rare sequencing of events to surface a rare bug. The line was 55 steps, repeating later mensuration 43. The procedure 3 kept eating, piece 0, 1, in addition to two starved. Processes 0, 1, in addition to two are hungry, in addition to since their doneReq flag was true, they didn't ship additional requests. They didn't genuinely ship asking to procedure 3 because they already had the muddy token on their side. But in addition to so procedure 3 ship them the asking in addition to got those tokens. And procedure 0,1,2 are non sending the asking again, because they cry back they are done with requests. I fixed the occupation past times removing the doneReq flag but instead checking for the demand for requesting. This also sped upwardly model checking, every bit less nation is maintained.
Improving the model checking complexity
This was a modest model with four processes, but the model checking took close 50 minutes in addition to used close 2GB of storage to exhaustively search the entire plausible execution nation space. To acquire that infinite back, brand certain you lot manually delete the model checking folder, folder ending with ".toolbox". You don't demand to worry close infinite besides much though: if you lot start a novel model cheque it writes over the previous one.My initial attempts had took close 4GB of infinite in addition to progressed slowly, which led me stopping them. To speed upwardly the model checking, I improved the answering of requests for forks past times making the GetReqNbrs business office to a greater extent than selective past times adding the 2nd occupation to that check. Seeing that it helped speed upwardly model checking, I also wrote a to a greater extent than selective GetForkNbrs function. These reduced the nation space, in addition to the execution time. But I nonetheless can't essay checking with to a greater extent than than four processes every bit that takes a long time.
Concluding remarks
So in that location nosotros go. Hygienic philosophers algorithm extend the topology of dining philosophers solution to an arbitrary graph, in addition to to a greater extent than importantly, provides "NoStarvation" guarantee fifty-fifty nether a weakly-fair scheduler. The algorithm ensures that exclusively i node executes critical department inward a neighborhood, in addition to this is useful for coordinating critical activity executions inward a distributed system. If all nodes execute without coordination, nosotros lead hold maximum parallel semantics which cannot furnish serializability (sequential consistency) guarantees. Using dining philosophers for coordination provides serializability guarantees. So, hygienic dining philosophers algorithm uncovering applications inward transforming programs written at a shared retention model with serializability assumptions to execute correctly with the serializability guarantees at the message passing model.Logistics
The PlusCal code for the programs are accessible through the below links. When you lot desire to model cheque the program, start a novel model, in addition to come inward four for N, so the model checker is ready to start. In the model checker tab, click on Invariant pane in addition to come inward ME in addition to so TypeOkFork in addition to so TypeOkReq, so that these 3 predicates are checked against whatever violation, in addition to inward the Properties pane come inward NoStarvation so that the progress belongings is checked for satisfaction. If you lot brand a alteration 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 in addition to so used for the model-checking. See the TLA+ posts below close how this works.Here is the terminal right version of the model
Here is the version that has põrnikas 3
Related Links
Using TLA+ for teaching distributed systemsMy sense with using TLA+ inward 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 postal service you lot tin compass all my posts close TLA+
0 Response to "Modeling The Hygienic Dining Philosophers Algorithm Inward Tla+"
Post a Comment