Table of contents

Petri networks (Labwork)

Petri networks (Labwork)

Presentation

What is it for?

Petri nets are a mathematical formalism that allows to specify programs where several tasks run in parallel, these tasks sometimes having to access resources each in turn. It is used to specify communication protocols… but the idea here is simply to play with this formalism, on school cases, as a programming exercise.

Definition

A Petri net is a set of elements linked together. These elements are of two kinds. First, the network contains pools of tokens. These are simple boxes in which tokens can be added or removed. Second, the network contains transitions. The transitions put the pools in relation via connections. More precisely, a transition is meant to take tokens from some pools (the input pools) and to add tokens to others (the output pools). For each input pool of a transition, the number of tokens to be taken, for this transition, is fixed at the time of the network design. Similarly, for the output pools, the number of tokens deposited by the transition is fixed at the time of the network design as well. A transition is activable if, for all its input pools, there are more tokens than the number to be taken by the transition. Activating an activatable transition means taking the required number of tokens from each input pool (so there are enough, since the transition is activatable), and adding the number of tokens defined for this transition to each output pool.

A petri network execution is then the following:

Repeat
- take an activable transition t randomly among all activable transitions.
- activate t (it updates the number of tokens in the pools).
until none of the transitions are available (i.e. we have reached a dead-lock situation).

The example of red lights

A red light can be modeled by a Petri net. The transitions are the color changes, and the pools allow to make these changes in the right order (red never follows green for example). The following figure shows this modeling.

Where the interest of Petri nets becomes more obvious is when you have to manage two traffic lights on a crossroads… they must not turn green at the same time. You have to wait until one is red to authorize the other one to turn green. To do this, you just have to create two copies of the previous network (one copy per traffic light), and to express the exclusivity constraint by a new pool.

We will work on this example to start with.

Materials

Get the archive petri.tar.gz, and uncompress it somewhere.

mylogin@mymachine:~$ tar zxvf petri.tar.gz
mylogin@mymachine:~$ rm petri.tar.gz
mylogin@mymachine:~$ cd petri

Here, you will find petri*.hpp and petri*.cpp files. You will have to write their content when you will be instructed to do so. Note that petri.hpp includes all the petri*.hpp, for the sake of simplicity when you want to use the Petri tools we will define.

Instructions are given by test-*.cpp files, that you will have to compile and run. They are numbered, so the questions in this labwork as formulated as "write something in some petri*.* file, and run test-*.cpp to check that is works as expected.

Running a test is straightforward, it consists of compiling all the petri*.cpp file as well as the test and gather the whole binaries into a test executable that you can run.

For example, running the first test is:

mylogin@mymachine:~$ g++ -o test -I. -std=c++17 -pedantic -Wall petri*.cpp test-001-pools.cpp
mylogin@mymachine:~$ ./test

You will have compiling issues since it is supposed to work once you answer the first question.

The solution can be found in petri-solution.tar.gz, but you are really encouraged not to use it. Making errors, and understanding why, is the way to learn C++. Ask the teachers if you get stucked.

Red lights

Here, we well progressively set up the petri library on the example of the red lights.

Pools

The idea is to make test-001-pools.cpp work fine. To do so, you have to read petriPool.hpp and implement the methods in petriPool.cpp.

The test file shows you how we intend to handle pools in the following. Pools will not need to be modified from now.

Transitions

A transition is linked to several pools, for input as well as for output. The link to a pool comes with an integer, telling how many token will be taken for input pools and telling how many tokens will be produced for output pools.

The relation to a pool, for inputs as for outputs, are thus a pair containing a pool and an integer. Let us call this “slots”.

Look at the petriTransition.* files.

Make test-002-001-transitions-basics.cpp work. Remember that a single transition activation takes tokens from inut pools (according to the integer in the slots) an adds new token in the output pools ((according to the integer in the slots).

Now, for having a better interface, we add the possibility to invoke activate and is_activable thanks to the respective operator() method and the operator bool () method. Add this in order to have test-002-002-transitions-operators.cpp working.

Network

The network stores a set of transitions, and performs the simulation step by step. Try to make test-003-network-redlight.cpp work. It simulated the single redlight network. Here, rather than implementing a method bool next_step(), that returns true if some transition has been activated, we rather use the operator()() function name.

The transition to be activated at each simulation step has to be chosen randomly from the activable ones. This is why the Network structure own a gen attribute, that is initialized from a random seed. The seed itself can be chosen according to system time, so that two executions do not take the same random decisions.

Selecting randomly an activable transition can be done as follows. Make a loop on the transitions, and store their address into a vector (i.e. a std::vector<Transition*>) if they are activable. Then, toss a number between 0 and N-1, if N is the number of activable transitions. Use std::uniform_int_distribution to make this random choice. Then, from the selected address, get the transition and activate it.

Write a network-redlights.cpp file that implements the full crossroad petri network.

Convert into graphviz

The purpose of this section is to work on streams, in order to serialize a network in a .dot file that graphviz can render as a graph.

Download the text file example.dot, read it, and convert it into a graph like this with the dot command (install graphviz):

mylogin@mymachine:~$ dot -Tpdf example.dot -o example-dot.pdf

You can also use neato from the same .dot file:

mylogin@mymachine:~$ neato -Tpdf example.dot -o example-neato.pdf

Compare the two results.

After the simulation, in the previous network-redlights.cpp, add the following lines:

std::ofstream file("redlight.dot");
file << redlight; // redlight is a petri::Network

Do not forget to include <fstream>. Check the result. You should get something like this.

Hint: The transitions and pools are names transition<i> and pool<i> in the .dot file. The value <i> can be the index of the transition in the vector of the network where it is stored. For the pools, it is not that easy since they are not gathered somewhere… You can use, a std::map<pool_ref, unsigned int> idf_of_pool local variable, that you first fill by exploring all the pools referenced by the transitions. Look at the documentation of std::map (and ask the teachers).

The philosophers

Let us model a famous problem called The dining philosophers problem, illustrated by the following picture.

The dining philosophers (from Wikipedia.org)

At a banquet, n philosophers are around a table to eat a dish of spaghetti, located in the center of the table. The philosophers have a fork on their left and a fork on their right. The right fork of a philosopher is the left fork of his right neighbor. Each philosopher thinks, but decides from time to time to eat. To do so, s/he first takes his/her left fork, then his/her right fork. Only then does he take a portion of pasta from the dish and eat it, then s/he puts both forks back down simultaneously, making them available.

Generate a simulation

Write new c++ files to solve this problem (do not alter the petri* files we have made so far, they form a library that we now use). First, write a function that takes the number of philisophers as an argument, and produces a petri net as a result, modeling the problem.

Display the graph (neato is recommended) for 2, 3, 4 philosophers, and check the models.

Average deadlock time

The simulation will lead to a deadlock (no more fork available for any transition). Indeed, the probability that it does not lead to a dead-lock is 0. We would like to know, for a given number of philosopher, the average number of timesteps before the dead-lock. Plot this average according to the number of philisophers (e.g. generate a python file that plots the values).

Hervé Frezza-Buet,