Sequentialization

from Wikipedia, the free encyclopedia

Under sequencing or sequencing refers to the creation of an order for a set of actions along the causal order , the z. B. is given by a function tree. The point is to find an order in which the actions can be carried out one after the other, so that any action that requires the result of another is not carried out until that result is available. The order in which concurrent (causally independent) actions are carried out is arbitrary. This often results in several possible sequencing, but all of them lead to the same result (otherwise it would not be correct sequencing).

Sequencing is the opposite of parallelization .

application

The sequencing of operations is particularly in resource planning ( scheduling ) important to a deadlock (deadlock) should be avoided. It is also crucial for the integrity of transaction systems . The Peterson algorithm or the Dekker algorithm are used here, for example . The philosopher problem provides an illustrative example of the problem of resource planning .

The subsequent sequencing of messages on the basis of time stamps , on the other hand, is important in distributed systems , both in operation and for analysis (see Logical Clock ) .

example

Example of a function tree for Spaghetti Bolognese

The illustration shows a greatly simplified function tree for the preparation of spaghetti bolognese . Now, if we had a cook who can only do one task at a time, we have to establish an order in which he has to do these things. There are several possible sequencing options (if we ignore the fact that the spaghetti could get cold, etc.):

  • Chop vegetables, fry minced meat, stir together, boil sauce, boil water, cook spaghetti, spaghetti Bolognese.
  • Fry minced meat, chop vegetables, stir together, boil sauce, boil water, boil spaghetti, spaghetti Bolognese.
  • Boil water, fry minced meat, chop vegetables, cook spaghetti, stir together, cook sauce, spaghetti Bolognese.
  • ... and a few other combinations.

In contrast, the following orders are not correct sequencing:

  • Chop vegetables, cook spaghetti (abort: cannot cook spaghetti because the water is not yet hot).
  • Chop the vegetables, stir together (abort: cannot stir together because the minced meat has not yet been fried).
  • Chop the vegetables, fry the minced meat, stir together, boil the sauce, boil water, spaghetti Bolognese (abort: spaghetti is missing).
  • ... and so on.

See also