Introduction to Petri Nets (4IS)
Course material (french)
TP 3
Token-ring
Context : A token ring protocol is used to solve the mutual exclusion problem.
Each site consists of a station and a client. The station takes care of the
token circulation and offers a mutual exclusion service to its client.
The behaviour of client i consists in three states:
- idle_i : Client i idle
- wait_i : Client i waiting for the Critical section (CS)
- work_i : Client i in Critical Section
The state of the token is described by two indexed sets of propositions:
- token_i : the token is available on station i
- after_i : the token is in transit between station i and
station i+1
A) Simulation et correction du modèle proposé
The net tk4.ndr
proposes a Petri model for a ring composed by 4 sites.
- Edit the net tk4.ndr and simulate it with the stepper.
- Does its behavior seem to you a priori correct?
You should have observed that the proposed solution does not guarantee the absence of starvation. Indeed, a client can stay indefinitely waiting to work.
The service provided by the station should ensure that it will work after a finite time and it is not the case. This is not case since the proposed solution present two errors:
(E1) : a station may be too selfish (thinking only about its customer) and prevent other customers from working.
(E2) : stations can also be too altruistic and always give priority to other stations.
Find these two behaviors by simulation.
Propose some modifications to the net in order to prohibit the pathological behaviors of selfishness and altruism.
To develop your corrections, you will work directly on the graphical form of the net. You will use the simulation to validate your corrections.
You will first process to correct selfishness (E1)
and then altruism (E2).
For E1, you will make the same correction on each station.
For E2, you will make a specific correction on each station.
Indication For this several choices are available:
- Use of an inhibitor arc that allows to forbid the enabling of a tra
nsition if its entry place is marked. Under the editor nd
to obtain an inhibitor
arc, draw an arc between a place and a transition and choose the inhibitor option)
- Use of priorities between transitions. In nd, you just have to draw an arc
between two transitions. This arc will appear in orange.
- Use of a complementary place.
- Use of a read arc
B) Petri Puzzle net with inhibitory arcs and priorities
-
Analyze and simulate the solution proposed in puzzle.ndr
- Give an interpretation to the t3 and t4 transitions as well as to the "nbMax" and "frozen" places.
What problem of the previous model can be solved in this way?
- Propose an "equivalent" version without inhibiting arc.
- Propose an "equivalent" version without inhibitor arc and without priority.
II Automatic generation of the Token Ring Petri Net
To be done at the end of the Tps series if you have time left.
Do the exercise III of TP1 before.
To allow parametrized modeling of the problem, an auxiliary program can be used to generate the corresponding Petri net. The ctk0 file is a TCL script used to generate the network associated with a configuration with k sites.
- The
compo.net file gives the result of this script for k =3. The script uses the possibility of working in a compositional way: we use the fact that in textual two transitions with the same name will be merged. There are client specific transitions, station transitions and transitions common to a client and his station.
- To generate a network with 8 sites: load the ctk0 script and execute the following command: ./ctk0 8 > ctk0_8.net (don't forget to make the script executable with the chmod +x ckt0 command).
III Modeling a parameterized system: the dinner of the philosophers
Standard version: N philosophers are seated around a round table. They are in three states (think, wait, dine). Every philosopher needs two forks to eat, but there is only one fork per plate. So to eat a philosopher must take the fork on his left and the fork on his right in two distinct stages. Thus at any time two philosophers who are next to each other cannot eat simultaneously.
Variants of the standard problem:
Using the script provided, model the philosophers' dinner; of course, you have to make the ring disappear, but you'll keep a compositional spirit by distinguishing between the behavior of the philosopher (who won't change throughout the exercise) and his disciple in charge of picking up and returning the forks.
- You will simplify the problem by assuming that the N disciples have an indistinguishable set of N forks from which can draw both forks simultaneously (V0),
- they draw the forks one after the other (V1),
- the forks are individualized and are taken sequentially (V2).
Note: For versions V0 and V1, we will allow 2 neighboring philosophers to eat at the same time.
Work to be provided:
Note: You will not seek to guarantee freedom from starvation or prevent interblocking)
- For versions V0 and V1:
- Propose a compositional modeling of the disciples and the heap of forks
- Write the associated script.
Propose a solution for version V2 Standard (Optional)