Következő példánk az absztrakt program fogalmát mutatja be. Az absztrakt program utasításait nem rendezzük szekvenciális folyamatokká, egyetlen utasításhalmaz formájában adjuk meg. Utasításhalmazok tulajdonságai könnyebben igazolhatóak, mint szekvenciális folyamatok halmazaként megadott párhuzamos programok helyessége. Az utasításhalmaz elemeit felváltva hajtjuk végre (ld. . fejezet), a program működése egy több ciklusmaggal rendelkező ciklushoz hasonlít. Ha egynél több processzor áll rendelkezésre, akkor egyszerre vagy időben átfedve több utasítást is végrehajthatunk Ebben az esetben csak olyan értékadások egyidejű vagy időben átfedő végrehajtása megengedett, amelyek nem tartalmaznak közös változót.. Az utasításhalmazt egy inicializáló értékadás előzi meg.
A buborékrendezés algoritmusa szerint két szomszédos megcserélünk, ha rossz sorrendben vannak. Az absztrakt program minden szomszédos elempárhoz tartalmaz egy olyan utasítást, amelyik szükség esetén a két elemet megcseréli. Ha az elemek sorrendje helyes, akkor további állapotváltozás már nem következik be, a program terminál.
Az absztrakt program egy lehetséges implementációja, ha minden
utasításhoz egy önálló folyamat tartozik és a folyamatokhoz egy-egy
saját processzort rendelünk hozzá. Egyidejűleg csak egy folyamat számára
engedélyezhetjük a vektor elemeihez való hozzáférést. Jelöljük
<lock a(i) and a(i+1)>-vel azt a műveletet, amellyel egy folyamat az i. és az
i+1. elem használatát igényli (a kritikus szakasz kezdetét), illetve
<unlock a(i) and a(i+1)>-vel azt a műveletet, amellyel lemond az elemek
kizárólagos használatáról (kritikus szakasz vége) . Ebben az esetben az
.
processzoron futó program pszeudokódja a következő lehet:
loop
< lock a(i) and a(i+1) >
x := a(i);
y := a(i+1);
if x > y then
a(i+1):=x;
a(i):= y;
end if;
< unlock a(i) and a(i+1) >
end loop;
folyamat.
Bemutatjuk azt is, hogy ugyenezen absztrakt programot hogyan valósíthatjuk meg egyetlen processzoron futó szekvenciális program formájában:
loop
for i=1 to n-1 do
x := a(i);
y := a(i+1);
if x > y then
a(i+1):=x;
a(i):= y;
end if;
end for
end loop