Queues and stacks

It is often nice to be able to simulate a queue or stack discipline for places, e.g. for communication over a TCP channel.

Alas, CPN Tools does not currently support this, but this is easy done by the modeler.

Example

image_unordered.jpg

This is a very simple model of a sender and a receiver.

The sender, sends packages onto a network.

The receiver receives packages from the network.

Stack

We want the network to have a LIFO (last in, first out), or stack behavior. (Yes, this is not realistic, but then I only need to introduce one example).

We change the type of the place from “T” to “list T”, and make all ingoing arcs preprend to the list, and all outgoing arcs should then remove the head from the list.

When I do this to the above example, I get:

image_stack.jpg

Changes to declarations

  • I have added a new type “PACKAGEs” of type “list PACKAGE”
  • I have added a new variable of the new type “PACKAGEs”

Changes to the network place

  • I change the type from “PACKAGE” to “PACKAGEs”
  • I add/change the initial marking to be a list. In this case the original initial marking was the empty marking, and I add the empty list ”[]”. If the original marking had been, e.g., “1`1++2`4”, I could have changed it to, e.g., ”[1, 4, 1]” (the ordering DOES matter now).

Changes to (ingoing and outgoing) arcs

  • I change the inscription of the arc from “p” to “p::ps”, where “ps” i the new variable of the new type “PACKAGEs”
  • I add a new arc in the opposite direction with the inscription “ps”

Queues

We want the network to have a FIFO (first in, first out), or queue behavior. This is like the behavior of TCP streams.

We change the type of the place from “T” to “list T”, and make all ingoing arcs append to the list, and all outgoing arcs should then remove the head from the list.

The only difference from stacks is that instead of prepending to the list, we append to it. When I do this to the example, I obtain:

image_queue.jpg

Changes to declarations

  • I have added a new type “PACKAGEs” of type “list PACKAGE”
  • I have added a new variable of the new type “PACKAGEs”

Changes to the network place

  • I change the type from “PACKAGE” to “PACKAGEs”
  • I add/change the initial marking to be a list. In this case the original initial marking was the empty marking, and I add the empty list ”[]”. If the original marking had been, e.g., “1`1++2`4”, I could have changed it to, e.g., ”[1, 4, 1]” (the ordering DOES matter now).

Changes to outgoing arcs

  • I change the inscription of the arc from “p” to “p::ps”, where “ps” i the new variable of the new type “PACKAGEs”
  • I add a new arc in the opposite direction with the inscription “ps”

Changes to incoming arcs

  • I change the inscription of the arc from “p” to “ps^^[p]”, where “ps” i the new variable of the new type “PACKAGEs”
  • I add a new arc in the opposite direction with the inscription “ps”

Priority queues

We want the network to have a priority-queue behavior, i.e. the priority of a packet determines the order in which it is handled. This is similar to IP quality-of-service options which allow datagrams to be identified (and possibly handled) with eight levels of precedence.

We change the type of the place from “T” to “list T”, and make all ingoing arcs insert elements into the list according to precedence/priority, and all outgoing arcs should then remove the head from the list.

The difference from FIFO queues is that instead of appending to the list, elements are added according to their priority. When I do this to the example, I obtain:

Priority queue

Changes to declarations

  • I have added a new type “PACKAGEs” of type “list PACKAGE”
  • I have added a new variable of the new type “PACKAGEs”
  • I add a function “higherPriority” to determine whether one package has higher priority than another
  • I add a function “pinsert” for inserting packages into a list according to their priority

Changes to the network place

  • I change the type from “PACKAGE” to “PACKAGEs”
  • I add/change the initial marking to be a list. In this case the original initial marking was the empty marking, and I add the empty list ”[]”. If the original marking had been, e.g., “1`1++2`4”, I could have changed it to, e.g., ”[4, 1, 1]” (the ordering DOES matter now).

Changes to outgoing arcs

  • I change the inscription of the arc from “p” to “p::ps”, where “ps” i the new variable of the new type “PACKAGEs”
  • I add a new arc in the opposite direction with the inscription “ps”

Changes to ingoing arcs

  • I change the inscription of the arc from “p” to “pinsert p ps”, where “ps” i the new variable of the new type “PACKAGEs”
  • I add a new arc in the opposite direction with the inscription “ps”

Examples