Parallel Programming WS 2014/2015 - Assignment 1

Kastens, Pfahler
Institut für Informatik, Fakultät für Elektrotechnik, Informatik und Mathematik, Universität Paderborn

Oct 24, 2014

Exercise 1 (Hoare Logic)

Consider the following process p1:

   { P1: moneyBag = x }

      b1 = 10;
      t1 = moneyBag;
      t1 = t1 + b1;
      moneyBag = t1;
   
   { Q1: moneyBag = x + 10 }

Show that the postcondition Q1 holds for the sequential execution of the process if the execution starts in a state characterized by P1.

Consider the following two statements

   S1: x = x + y;
   S2: y = x - y;

Assume that x is initially 2 and that y is 5. What are the possible final values of x and y for each of the following programs?

a)

   S1; S2;

b)

   co <S1> //
      <S2>
   oc

c)

   co S1 //
      S2
   oc

a)

Consider 2 scenarios:

Which scenario results in more interleaved execution orders?

b)

Find a formula for the number of interleaved execution orders for n processes executing m atomic actions each.

Two processes p1 and p2 operate on a common variable x and local variables t and v:

   x = 0;
   
   p1: t = x; t = t + 2; x = t;
   
   p2: v = x + 1; x = v + 1;

Find a decomposition of the two processes into constructs that are atomic by AMO. Choose this decomposition as coarse as possible.

The Java program Atomic.java is a simulation of the process structure in Assignment 2c. Compile and execute it to compare the results.

Generiert mit Camelot | Probleme mit Camelot? | Geändert am: 06.11.2014