Étkező filozófusok
Feladat:
Általában n=5 filozófusra fogalmazzák meg, mint a jelenlegi példában is. n filozófus ül körbe egy kerek asztalt, amelyen n db (azaz ugyanannyi) villa, illetve középen egy tál főtt tészta, amiből a filozófusok szedhetnek a tányérjukba (két villa segítségével).
Az alábbi megszorításoknak teljesülnie kell:
- egy filozófus vagy eszik vagy gondolkodik (vagy jóllakott);
- ha egy filozófus jóllakott, nem eszik többet;
- egy filozófus a.cs.a. ehet, ha 2 villát tart a kezében;
- egy filozófus a.cs.a. gondolkodik, ha 0 villát tart a kezében;
- ha egy filozófus megéhezett, csak a bal-és jobbszomszédja felőli villákat próbálhatja meg felvenni;
- amíg egy filozófus eszik, bal-és jobbszomszédja csak gondolkodhat és megéhezhet(ha még nem lakott volna jól :) )
- előbb-utóbb mindegyik filozófus jóllakik, és utána hazamennek(együtt mennek haza).
- (+ lehetőség: bármelyik filozófusnak megmondható, ha jól lakott, ha nem, hogy többet nem ehet. Ilyenkor morcosan megvárja a többieket.)
{ Dining Philosphers J.R. Cordy (after C. Lewis) Dec 1981 }
var Diners : module
{ Random number generator }
include '%RANDOM'
pervasive type XCoord = 0 .. 79
pervasive type YCoord = 0 .. 23
pervasive const numberOfDiners := 5
{ Position of each philosopher at the table }
pervasive type Philosopher = 0 .. numberOfDiners - 1
pervasive const faceXPosition : array Philosopher of XCoord :=
(36, 56, 48, 24, 16)
pervasive const faceYPosition : array Philosopher of YCoord :=
(2, 9, 18, 18, 9)
{ Positions of forks to left and right of each philosopher }
pervasive type Fork = 0 .. numberOfDiners
pervasive const forkXPosition : array Fork of XCoord :=
(25, 49, 57, 37, 19, 25)
pervasive const forkYPosition : array Fork of YCoord:=
(5, 5, 14, 21, 14, 5)
{ Meals eaten by each philosopher }
pervasive const maxMeals := 50
var meals : array Philosopher of 0 .. maxMeals
{ Maximum eating and thinking times }
pervasive const maxEatingTime := 10
pervasive const maxThinkingTime := 10
{ Philospher's expressions }
pervasive const contemplating := 0
pervasive const smiling := 1
pervasive const chewing := 2
pervasive const frowning := 3
{ Philosopher's activities }
pervasive const thinking := 0
pervasive const eating := 1
{ Sides }
pervasive const left := 0
pervasive const right := 1
var Draw : module
exports (ChangeExpression, MoveFork, Finalize, Interrupt)
{ Terminal cursor handling library }
include '%CURSES'
procedure DrawFace (diner : Philosopher) =
imports (var Curses)
begin
const x : XCoord := faceXPosition (diner)
const y : YCoord := faceYPosition (diner)
Curses.Move (y, x)
Curses.AddStr ('MMMMMMM$E')
Curses.Move (y + 1, x)
Curses.AddStr ('| o,o |$E')
Curses.Move (y + 2, x)
Curses.AddStr ('| --- |$E')
Curses.Move (y + 3, x)
Curses.AddStr (' """""$E')
Curses.Refresh
end DrawFace
procedure ChangeExpression (diner : Philosopher, newExpression :
contemplating .. frowning) =
imports (var Curses)
begin
const x : XCoord := faceXPosition (diner)
const y : YCoord := faceYPosition (diner)
Curses.Move (y + 2, x)
if newExpression = contemplating then
Curses.AddStr ('| --- |$E')
elseif newExpression = smiling then
Curses.AddStr ('| \_/ |$E')
elseif newExpression = chewing then
Curses.AddStr ('| (_) |$E')
else
Curses.AddStr ('| /-\ |$E')
end if
Curses.Refresh
end ChangeExpression
procedure DrawFork (diner : Philosopher, side : left .. right, activity
: thinking .. eating) =
imports (var Curses)
begin
var x : XCoord
var y : YCoord
if activity = thinking then
x := forkXPosition (diner + side)
y := forkYPosition (diner + side)
else
if side = left then
x := faceXPosition (diner) - 7
else
x := faceXPosition (diner) + 9
end if
y := faceYPosition (diner) + 1
end if
Curses.Move (y, x)
Curses.AddStr ('|_|_|$E')
Curses.Move (y + 1, x + 2)
Curses.AddCh ($|)
Curses.Move (y + 2, x + 2)
Curses.AddCh ($|)
Curses.Refresh
end DrawFork
procedure EraseFork (diner : Philosopher, side : left .. right, activity
: thinking .. eating) =
imports (var Curses)
begin
var x : XCoord
var y : YCoord
if activity = thinking then
x := forkXPosition (diner + side)
y := forkYPosition (diner + side)
else
if side = left then
x := faceXPosition (diner) - 7
else
x := faceXPosition (diner) + 9
end if
y := faceYPosition (diner) + 1
end if
Curses.Move (y, x)
Curses.AddStr (' $E')
Curses.Move (y + 1, x + 2)
Curses.AddCh ($$S)
Curses.Move (Y + 2, x + 2)
Curses.AddCh ($$S)
Curses.Refresh
end EraseFork
procedure MoveFork (diner : Philosopher, side : left .. right,
newActivity : thinking .. eating) =
imports (DrawFork, EraseFork)
begin
if newActivity = thinking then
EraseFork (diner, side, eating)
else
EraseFork (diner, side, thinking)
end if
DrawFork (diner, side, newActivity)
end MoveFork
procedure Finalize =
imports (var Curses)
begin
var c : Char
Curses.Move (23, 0)
Curses.CursorOn
Curses.AddStr ('Hit return to continue.$E')
loop
exit when not Curses.HasCh
Curses.GetCh (c)
end loop
Curses.GetCh (c)
Curses.Clear
Curses.Refresh
Curses.Endwin
end Finalize
function Interrupt returns result : Boolean =
imports (Curses)
begin
return (Curses.HasCh)
end Interrupt
initially
imports (DrawFace, DrawFork, var Curses)
begin
var diner : Philosopher
Curses.Clear
Curses.Move (0, 3)
Curses.CursorOff
Curses.AddStr ('THE DINING PHILOSOPHERS$E')
Curses.Move (1, 0)
Curses.AddStr ('Processes in Concurrent Euclid$E')
diner := 0
loop
DrawFace (diner)
DrawFork (diner, left, thinking)
DrawFork (diner, right, thinking)
exit when diner = numberOfDiners - 1
diner := diner + 1
end loop
end
end module
var Forks :
monitor
imports (var meals, var Draw)
exports (PickUp, PutDown, AllDone)
function LeftDiner (diner : Philosopher) returns dinerToLeft :
Philosopher =
begin
return ((diner + 1) mod numberOfDiners)
end LeftDiner
function RightDiner (diner : Philosopher) returns dinerToRight :
Philosopher =
begin
return ((diner + numberOfDiners - 1) mod numberOfDiners)
end RightDiner
var forksAvail : array Philosopher of 0 .. 2
var okayToEat : array Philosopher of Condition
var done : condition
procedure PickUp (diner : Philosopher) =
imports (var forksAvail, var okayToEat, meals, LeftDiner, RightDiner
, var Draw)
begin
if forksAvail (diner) not= 2 then
wait (okayToEat (diner))
end if
forksAvail (LeftDiner (diner)) := forksAvail (LeftDiner (diner))
- 1
Draw.MoveFork (diner, left, eating)
forksAvail (RightDiner (diner)) := forksAvail (RightDiner (diner
)) - 1
Draw.MoveFork (diner, right, eating)
Draw.ChangeExpression (diner, chewing)
end PickUp
procedure PutDown (diner : Philosopher) =
imports (var forksAvail, var okayToEat, var meals, var done,
LeftDiner, RightDiner, var Draw)
begin
Draw.ChangeExpression (diner, contemplating)
Draw.MoveFork (diner, left, thinking)
forksAvail (LeftDiner (diner)) := forksAvail (LeftDiner (diner))
+ 1
Draw.MoveFork (diner, right, thinking)
forksAvail (RightDiner (diner)) := forksAvail (RightDiner (diner
)) + 1
if forksAvail (LeftDiner (diner)) = 2 then
signal (okayToEat (LeftDiner (diner)))
end if
if forksAvail (RightDiner (diner)) = 2 then
signal (okayToEat (RightDiner (diner)))
end if
meals (diner) := meals (diner) + 1
if meals (diner) = maxMeals then
Draw.ChangeExpression (diner, smiling)
signal (done)
elseif Draw.Interrupt then
meals (diner) := maxmeals
Draw.ChangeExpression (diner, frowning)
signal (done)
end if
end PutDown
procedure AllDone =
imports (var done)
begin
var numberDone : 0 .. numberOfDiners := 0
loop
wait (done)
numberDone := numberDone + 1
exit when numberDone = numberOfDiners
end loop
end AllDone
initially
imports (var forksAvail, var meals)
begin
var i : Philosopher
i := 0
loop
forksAvail (i) := 2
meals (i) := 0
i := i + 1
exit when i = numberOfDiners
end loop
end
end monitor
procedure Delay (time : SignedInt) =
begin
var i : SignedInt := time * 100
loop
exit when i <= 0
i := i - 1
end loop
end Delay
procedure CommonPhilosopher (diner : Philosopher) =
imports (var meals, var Forks, var Random, Delay)
begin
loop
Forks.PickUp (diner)
Random.Next
busy (Random.Number mod maxEatingTime)
Delay (Random.Number mod maxEatingTime)
Forks.PutDown (diner)
Random.Next
busy (Random.Number mod maxThinkingTime)
Delay (Random.Number mod maxThinkingTime)
exit when meals (diner) = maxMeals
end loop
end CommonPhilosopher
process Philosopher_0 (3000)
imports (CommonPhilosopher)
begin
CommonPhilosopher (0)
end Philosopher_0
process Philosopher_1 (3000)
imports (CommonPhilosopher)
begin
CommonPhilosopher (1)
end Philosopher_1
process Philosopher_2 (3000)
imports (CommonPhilosopher)
begin
CommonPhilosopher (2)
end Philosopher_2
process Philosopher_3 (3000)
imports (CommonPhilosopher)
begin
CommonPhilosopher (3)
end Philosopher_3
process Philosopher_4 (3000)
imports (CommonPhilosopher)
begin
CommonPhilosopher (4)
end Philosopher_4
process Cleanup (3000)
imports (var Forks, var Draw)
begin
Forks.AllDone
Draw.Finalize
end Cleanup
end Diners
Az implementációról
A filozófusokat, villákat koordinátáik tömbjén keresztül reprezentálják. A progi karaktergrafikával ki is rajzolja őket: ehhez kellenek a bal felső sarkok koordinátái. A többi változó jelentése a kódban eléggé dokumentálva van :)
A Diners modul egy Draw modult és egy Forks monitort tartalmaz. A Draw modul a filozófusok és villák kirajzolását, illetve a képernyő tisztítását, és az interaktivitás(a felhasználó és a program között) kontrollját végzi. Karaktergrafikát használó műveleteket tartalmaz, illetve lehetőséget ad arra, hogy tetszőleges billenytű lenyomására megzavarjunk egy (a max. adagját még el nem fogyasztott ) filozófust, és azt mondjuk neki, hogy "nem kapsz többet enni" - lásd 'Forks.PutDown'.
A Forks monitor pedig a villák használatát implementáló műveleteket felügyeli. Van egy inicializáló művelete: kezdetben V filozófus két villát érhet el, és még nem evett semmit. A PickUp - al egy filozófus villát vesz fel, egészen addig, amíg nem sikerül neki; A PutDown-al leteszi a villáit, és erre "udvariasan fehívja a többiek figyelmét"; az AllDone (és a Draw.Finalize) segítségével a CleanUp folyamat újra kiindulási helyzetbe hozza a programot.
Ezen kívül definiált benne a Delay (késleltető) és a CommonPhilosopher(a kajálást vezérlő fő eljárás) műveletek, valamint az ezt hívó filozófus-folyamatok,és egy "eltakarító" (a filozófusok hazamennek, az asztalt meg leszedik :) ) folyamat. A CommonPhilosopher-ben az éppen evő, illetve éppen gondolkodó filozófus tevékenyen várakozik (busy,Delay), de csak korlátozott ideig (maxEatingTime, maxThinkingTime).
A monitorbeli eljárások használta signal, wait és conditon-ok összefüggései:
- condition-ok.
- okayToEat: a filozófusokkal(!) (0..4) indexelt condition-tömb: okayToEat(i) "igaz" ==> i. filozófus ehet (mert fel tud venni 2 villát); ha pedig "hamis" ==> i. filozófus nem tud felvenni két villát(nem ehet).
- done: egyszerű condition változó. A done "igaz" ==> az egyik filozófus degeszre zabálta magát (vagy megzavarták evés közben és bosszús); ha pedig "hamis" ==> az a bizonyos filozófus még nem evett eleget.
- procedure PickUp
wait (okayToEat (diner))
: a hívó folyamat (lásd diner paraméter) az okayToEat tömbbeli saját helyének ("névtelen") várakozási listájára kerül; - procedure PutDown
- signal (okayToEat (LeftDiner (diner)))
: a hívó folyamat - filozófus - balszomszédját "feléleszti", és leszedi az okayToEat tömbbeli saját(balszomszédé) helyének ("névtelen") várakozási listájáról; - signal (okayToEat (RightDiner (diner)))
: a hívó folyamat - filozófus - jobbszomszédját "feléleszti", és leszedi az okayToEat tömbbeli saját helyének ("névtelen") várakozási listájáról; - signal (done)
: "felébreszti" az Alldone procedúrát hívogató Cleanup folyamatot (ő a done várakozási sorában van mindaddig, amíg az Alldone ciklusa le nem fut -- azaz amíg a filozófusok nem végeztek a kajálással. A kajálással végezni kétféleképpen lehet:a filozófus elégedetlen (Draw.Interrupt miatt), vagy elégedett, de a lekajált mennyisége így is, úgy is megkapja a maximális értéket.
- procedure AllDone
Az őt hívó folymatokat (mint pl. itt csak a Cleanup) felteszi a done várakozási sorába.
SCAN merevlemez-elérést irányító ütemező algoritmus
Feladat: a merevlemezhez érkező írási és olvasási kérelmek kiszolgálása, a fej mozgatásának írányításával. Az algoritmusról lentebb.
{SCAN Disc Scheduling Algorithm}
var Scan : module
include '%IO'
pervasive type cardinal = 0..32767
pervasive type tracknums=0..39
var disk:array tracknums of cardinal
var curtrack:0..39
var scheduler : monitor
imports (var curtrack, var IO, var disk)
exports (request,finish)
var tracks:array tracknums of condition
var numreq:cardinal
var prefdir:-1..1
procedure request(track:cardinal)=
imports (var tracks, var numreq)
begin
numreq := numreq+1
if numreq>1 then wait(tracks(track)) end if
end request
procedure finish =
imports(curtrack, var prefdir, var numreq, var tracks)
begin
var scanner:cardinal
numreq := numreq-1
if numreq>0 then
if not(empty(tracks(curtrack))) then signal(tracks(curtrack))
else
scanner := curtrack
loop
scanner := scanner+prefdir
if scanner=39 then prefdir := -1
else if scanner=0 then prefdir := 1
end if
end if
if not(empty(tracks(scanner))) then exit end if
end loop
signal(tracks(scanner))
end if
end if
end finish
initially
imports(var prefdir, var numreq, var curtrack, var disk)
begin
var i:cardinal
prefdir := 1
curtrack := 0
numreq := 0
i := 0
loop
disk(i) := 0
i := i+1
if i=40 then exit end if
end loop
end
end monitor
procedure positionhead(track:cardinal)=
imports (var curtrack)
begin
curtrack := track
end positionhead
procedure read(procnum:cardinal,track:cardinal, var c:cardinal)=
imports (curtrack, disk, var scheduler, positionhead, var IO)
begin
scheduler.request(track)
positionhead(track)
c := disk(curtrack)
IO.PutString('Process number ')
IO.PutInt(procnum,0)
IO.PutString(' read ')
IO.PutInt(c,0)
IO.PutString(' from track ')
IO.PutInt(track,0)
IO.PutString('.$N')
scheduler.finish()
end read
procedure write(procnum:cardinal,track:cardinal,c:cardinal)=
imports (curtrack, var scheduler, positionhead, var disk, var IO)
begin
scheduler.request(track)
positionhead(track)
disk(curtrack) := c
IO.PutString('Process number ')
IO.PutInt(procnum,0)
IO.PutString(' wrote ')
IO.PutInt(disk(curtrack),0)
IO.PutString(' on track ')
IO.PutInt(track,0)
IO.PutString('.$N')
scheduler.finish()
end write
process p1 (5000)
imports(read, write)
begin
var q:cardinal
write(1,25,1)
write(1,15,2)
write(1,35,3)
read (1,27,q)
read (1, 2,q)
write(1,34,4)
write(1, 3,5)
write(1,29,6)
write(1, 5,7)
write(1,39,8)
end p1
process p2 (5000)
imports(read, write)
begin
var q:cardinal
write(2,27,9)
write(2, 2,10)
read (2,25,q)
write(2,37,11)
write(2,10,12)
write(2,30,13)
write(2,20,14)
write(2,21,15)
read (2,29,q)
read (2,34,q)
end p2
process p3 (5000)
imports(read, write)
begin
var q:cardinal
write(3,17,16)
write(3, 8,17)
write(3,24,18)
read (3, 5,q)
write(3,36,19)
read (3,36,q)
write(3, 9,20)
write(3, 4,21)
write(3,28,22)
write(3,14,23)
write(3,13,24)
end p3
process p4 (5000)
imports(read, write)
begin
var q:cardinal
write(4,16,25)
read (4, 8,q)
read (4,17,q)
read (4,24,q)
write(4,11,26)
write(4,12,27)
write(4,18,28)
write(4,19,29)
read (4,16,q)
read (4,14,q)
end p4
process p5 (5000)
imports(read, write)
begin
var q:cardinal
write(5, 0,30)
write(5,31,31)
write(5,32,32)
write(5,33,33)
write(5,37,34)
read (5,15,q)
read (5,16,q)
read (5,17,q)
write(5,26,35)
write(5,23,36)
end p5
process p6 (5000)
imports(read, write)
begin
var q:cardinal
write(6, 1,37)
write(6, 6,38)
write(6, 7,39)
write(6,22,40)
write(6,38,41)
read (6, 8,q)
read (6,10,q)
read (6,12,q)
write(6,14,35)
write(6,16,36)
end p6
End Scan
Az implementációról
A SCAN modul tartalmazza a 'scheduler' nevű monitort, fejpozicionálást, olvasását, írást végző műveleteket, végül 6 folyamatot, azonosítószámukkal(1..6) és azzal hogy hova/honnan és mit írnak/olvasnak. Ezek a folyamtok a 0..39 -ig számozott cilindereken végeznek író-olvasó műveleteket. A scheduler nevű monitor műveletei az (írás/olvasás)kéréseket, illetve a következő kiszolgálandó kérés keresését(scan) koordinálják.
A monitorbeli eljárások használta signal, wait és conditon-ok összefüggései:
- condition-ok.
var tracks:array tracknums of condition : a cilinderek azonosítóival (0..39) indexelt őrfeltétel-változók tömbje (ami megadja, hogy éppen írható/olvasható -e az adott cilinder). - procedure request
if numreq>1 then wait(tracks(track)) end if
- ha a cilinderre érkező kérés már legalább a második, akkor felkerül a 'tracks' tömbnek a cilinder sorszámának megfelelő várakozólistájára. - procedure finish
- numreq := numreq-1 if numreq>0 then if not(empty(tracks(curtrack))) then signal(tracks(curtrack))
- ha az aktuális cilinder várakozási sora "nem üres", akkor felébreszt róla egy folyamatot. - if not(empty(tracks(scanner))) then exit end if
- a következő, nem üres várakozási sorú cilinder megtalálásakor kilép a ciklusból, majd - signal(tracks(scanner))
-felébreszt a várakozási sorából egy feladatot.
Ebben a feladatban már az 'empty' konstrukciónak is szerep jutott. Az algoritmus már ismerős (lehet) 'operációs rendszerek'-órákról : de azért röviden leírom, hogyan működik.
Kezdetben (lsd. a monitor initially műveletét) a mozgás iránya 1 (kifelé), az aktuális cilinder a legelső (a 0.), nincs kérés se írásra, se olvasásra, és a lemez(itt ebben a példában, az egyszerűség kedvéért) üres.
A folyamatok kéréseit (akár írás, akár olvasás), először belülről kifelé (a kiindulási pozícióból, ami most a 0. cilinder) folyamatosan haladva teljesíti, majd ha a legszélső (a 39.) cilinderhez ért, visszafordul, és kívülről befelé mozgatja a fejet, és ha talál kérést egy cilindernél, akkor azt teljesíti. Természetesen csak egyet egyszerre: ha egy cilinderre több kérés is befutott már, mire a fej odaért, akkor a cilinder várakozási sorából csak 1 folyamatot ébreszt fel. Ha ott van még további kérés, akkor ezek a kérések láncban, meg nem határozott sorrendben teljesülnek. Ezután továbbmegy befelé(a kéréseket az előbb látott módon szolgálva ki), és ha elérte az első (a 0.) cilindert,megint visszafordul.
A továbbiakban oda-vissza végigpásztázza a cilindereket, és ha egyiken kérés(eke)t talál, kiszolgálja az(oka)t. Az algoritmus holtpontmentes, és megelőzi a kiéheztetést.
"Concurrent Worms"
Feladat: 3 kukac mozog egy fix téglalap alakú területen, a határra érve ellenkező irányra váltanak, nem ütközhetnek magukba, sem egymásba.
{ Concurrent Worms V1.00 J.R. Cordy 29 April 1982 }
var Worms: module
include '%CURSES'
pervasive const nWorms := 3
var Its: monitor
exports (YourTurn, MyTurn, WormDone, AllDone)
{ Monitor to synchronize unit actions on the
terminal screen; Its.MyTurn insures that the
process may manipulate the screen until it
calls Its.YourTurn }
var mine: Boolean := false
var yours: condition { not mine }
var done : condition
procedure MyTurn =
imports (var mine, var yours)
begin
if mine then
{ Someone else already has it }
wait (yours)
end if
mine := true
end MyTurn
procedure YourTurn =
imports (var mine, var yours)
begin
mine := false
signal (yours)
end YourTurn
procedure WormDone =
imports (var done)
begin
signal (done)
end WormDone
procedure AllDone =
imports (var done)
begin
var numberDone : 0 .. nWorms := 0
loop
wait (done)
numberDone := numberDone + 1
exit when numberDone = nWorms
end loop
end AllDone
end monitor
{ Screen parameters }
pervasive const minX := 0
pervasive const maxX := 79
pervasive const minY := 0
pervasive const maxY := 23
{ Worm parameters }
pervasive const wormLength := 11
pervasive const wormX0: array 1..nWorms of minX..maxX-1 := (0,38,72)
pervasive const wormY0: array 1..nWorms of minY..maxY-1 := (0,11,22)
pervasive const wormString: array 0..nWorms*wormLength-1 of Char :=
($C,$o,$n,$c,$u,$r,$r,$e,$n,$t,$$S,
$E,$u,$c,$l,$i,$d,$$S,$$S,$$S,$$S,$$S,
$P,$r,$o,$c,$e,$s,$s,$e,$s,$$S,$$S)
pervasive const wormWiggle: array 0..wormLength-1 of -1..1 :=
(1,1,1,1,1,0,0,-1,-1,-1,0)
{ Worm algorithm }
procedure Worm (w: 1..nWorms) =
imports (var Its, var Curses)
begin
{ Segments of the worm }
var segment: array 0..wormLength-1 of
record
var x: minX..maxX
var y: minY..maxY
end record
{ Present direction of motion }
var xdir: -1..1 := 1
var ydir: -1..1 := 1
{ Turning parameters }
const maxCount := 1024
var count: 0..maxCount-1 := 0
const xturn: 0..maxCount := w * 117
const yturn: 0..maxCount := w * 37
{ Head and tail segments }
var head: 0..wormLength-1 := 0
var tail: 0..wormLength-1
var i: 0..wormLength
var j: 0..nWorms*wormLength-1
{ Initialize }
i := 0
loop
exit when i = wormLength
segment(i).x := wormX0(w)
segment(i).y := wormY0(w)
i := i + 1
end loop
loop
exit when Curses.HasCh
tail := (head + 1) mod wormLength
{ Compute new head position }
if segment(head).x >= maxX-1 then
xdir := -1
elseif segment(head).x <= minX+1 then
xdir := 1
end if
segment(tail).x :=
segment(head).x + xdir + xdir * wormWiggle(tail)
assert (segment(tail).x >= minX and segment(tail).x <= maxX)
if segment(head).y = maxY then
ydir := -1
elseif segment(head).y = minY then
ydir := 1
end if
segment(tail).y := segment(head).y + ydir
assert (segment(tail).y >= minY and segment(tail).y <= maxY)
head := tail
{ Redraw worm }
Its.MyTurn
i := head
j := (w-1) * wormLength
loop
Curses.Move (segment(i).y, segment(i).x)
Curses.AddCh (wormString(j))
exit when wormString(j) = $$S
i := (i + wormLength - 1) mod wormLength
j := j + 1
end loop
Curses.Refresh
Its.YourTurn
{ Decide if it's time to turn around }
if count mod xturn = 0 then
xdir := -xdir
end if
if count mod yturn = 0 then
ydir := -ydir
end if
count := (count + 1) mod maxCount
end loop
Its.WormDone
end Worm
procedure Finalize =
imports (var Curses)
begin
var c : Char
Curses.Move (23, 0)
Curses.CursorOn
loop
exit when not Curses.HasCh
Curses.GetCh (c)
end loop
Curses.Clear
Curses.Refresh
Curses.Endwin
end Finalize
initially
imports (var Curses)
begin
Curses.Clear
Curses.CursorOff
end
process Worm1
imports (Worm)
begin
Worm (1)
end Worm1
process Worm2
imports (Worm)
begin
Worm (2)
end Worm2
process Worm3
imports (Worm)
begin
Worm (3)
end Worm3
process Cleanup
imports (var Its, Finalize)
begin
Its.AllDone
Finalize
end Cleanup
end module
Az implementációról
Ez egy kedves kis program egymással párhuzamosan mozgó 3 kukaccal a képernyőn, amelyek a 'Concurrent','Euclid','Processes' feliratokból állnak. A program működése alatt a giliszták a 'képernyő' szélénél ellenkező irányba váltanak, és mielőtt egymásba ütköznének, el/megfordulnak.
A monitor MyTurn, YourTurn metódusai biztosítják a kölcsönös kizárást a képernyőre, mint kritikus erőforrásra vonatkozólag (lásd Worm - algoritmus 'Redraw worm' része.) A WormDone művelet segít "eltüntetni a gilisztákat" a képernyőről: billentyű-leütéskor sóbálvánnyá válik egy -egy giliszta. A program jólnevelt és az összes megmerevedett gilisztát eltakarítja a képernyőről, mielőtt befejeződne (Its.AllDone, Finalize).
Lineáris hashelés egy implementációja(Euclid nyelven)
Szerző : B. W. Lampson, J. Horning, R. L. London, J. G. Mitchell and G. L. Popek - Sigplan Notices, Vol.12, Nr. 2, February 1977
Feladat: valósítsuk meg számoknak tábláját, (pl. frissen nyitott bankszámláknak), mint egy asszociatív memóriát.
type NumberTable = module exports( Search, Delete, Insert )
{This modu1e implements a tab1e of numbers, e.g., currently open accounts, as an
associative memory}
pervasive const tableSize :=763; { Ez a tabla merete }
pervasive type TableIndex = 1..tableSize
pervasive type CyclicScan ( item : signedInt ) = {a generator for a for loop}
module exports ( Next, value, stop )
const start := (item mod tableSize)+1
var value : TableIndex := start
var stop : Boolean := False
procedure Next =
imports ( var value, start, var stop )
begin
if value = tableSize then value := 1
else value := value+1 end if
stop := (value not= start)
end Next
end CyclicScan
type State = (fresh, full, deleted)
type TableEntry( flag :State) =
record
case flag of
full => var key :signedInt end full
otherwise =>
end case
end TableEntry
var table :array TableIndex of TableEntry(any) {any: fresh,full,deleted}
function Search( key :signedInt) returns Boolean =
imports(table)
begin
{any tipusertekei itt az 1..tableSize intervallum-típus ertekei lehetnek :) }
for i in CyclicScan(any)
loop
with entry := table(i) case flag of
fresh => return False end fresh
full =>
return True when entry.key = key;
end full;
otherwise =>
end case;
end loop;
return False;
end Search;
procedure Delete( key :signedInt) =
imports(var table)
begin
const deletedEntry : TableEntry(deleted) := ();
for i in CyclicScan(key)
loop
with entry := table(i) case flag of
full =>
if entry.key = key then
table(i) := deletedEntry;
return
end if
end full
fresh => return end fresh
otherwise =>
end case
end loop
end Delete
procedure Insert( key :signedInt) =
imports(var table, Search)
begin
return when Search(key) {if already there};
for i in CyclicScan(key)
loop
case table(i).flag of
fresh, deleted =>
var t: TableEntry(full)
t.key := key
table(i) := t;
{az alabbi aprosagot veletlenul nem szedte a nyomdagep, pedig fontos :) }
return
end fresh
otherwise =>
end case
end loop
assert False {table never be full}
end Insert
const freshEntry : TableEntry(fresh) := ()
initially
begin
for i in table.IndexType loop
table(i) := freshEntry
end loop
end
end NumberTable
Segítség a kód olvasásához :
A CyclicScan a for-ciklus számára generálja a ciklusváltozó típusának lehetséges értékeit. Itt most épp előjeles egészeket, amik fix lépésközzel (most =1) követik egymást, növekvő sorrendben. Mindez a Next műveletből derül ki. A TableEntry típus megmondja, mi az aktuális kulcs állapota.
- fresh - az adott kulcshoz még nem tartozik érték
- full - az adott kulcshoz (pontosan 1) érték tartozik
- deleted - az adott kulcshoz már nem tartozik érték.