next up previous contents index
Next: Aufgaben Up: 2.3.2 Programmeigenschaften Previous: Sicherheit

Lebendigkeit

  Bei den Scheduling  Strategien werden folgende Begriffe unterschieden

  1. unconditionally fair  for atomic actions.
  2. weak fair,  unconditionally fair und bei await werden die Bedingungen auch einmal wahr.
  3. strong fair,  unconditionally fair und bei await werden die Bedingungen unendlich oft wahr.

Zur Verdeutlichung der Strategien betrachten wir einige Beispiele.

 VAR cout: boolean; cont:=true;

con

while cont do (* nothing *) end;

cont:=false;

end;

Bei `unconditional fair scheduling' wird auch das Statement cont:=false einmal ausgeführt, wodurch dann die while Schleife beendet wird und das con Statement terminiert. Ein unconditional fair scheduling ist z.B. durch round robin Verfahren einfach realisierbar.

 VAR cont, try: boolean; cont:=true; try:=false;

con

while cont do try:=true; try:=false end;

await try then cont:=false end;

end

Bei `weak fair scheduling' folgt u.U. keine Terminierung, denn das await Statement wird zwar unendlich oft ausgeführt, aber es ist nicht sichergestellt, daß in diesem Moment try den Wert true hat. In diesem Fall wird cont nie auf false gesetzt und das while Statement terminiert nicht.

Nur bei `strong fair scheduling' folgt die Terminierung, da dann garantiert wird, daß das await Statement unendlich oft ausgeführt wird und die Bedingung auch unendlich oft den Wert true annimmt. Wie man sieht, kann das nur der Fall sein, wenn das await Statement genau zwichen den Statements try:=true und try:=false ausgeführt wird. Die Bestimmung dieses Zeitpunkts ist aber nur nach eingehender Analyse des Programmtextes möglich und kann praktisch nicht vom Betriebssystem und dem Laufzeitsystem durchgeführt werden. (Ist z.B. nur mit FIFO Queues in Spezialfällen realisierbar.)

Eine letzte Lebendigkeitseigenschaft ist der sogenannte live lock.  Dabei tut jeder nicht terminierte Prozeß etwas, aber ohne die Arbeit voranzubringen.



parallel@rz.uni-mannheim.de
Mon Okt 28 14:38:25 PST 1996