Das „Dining philosophers problem“ – yeah, Informatik!

Das „Dining-Phi­lo­phers-Pro­blem“ ist eine Par­al­le­li­sie­rungs­auf­ga­be aus der Infor­ma­tik. Fünf Phi­lo­so­phen sit­zen um einen Tisch mit für Tel­lern und fünf Gabeln dazwi­schen. Wenn einer von ihnen essen möch­te, benö­tigt er bei­de Gabeln neben sei­nem Teller.

By Ben­ja­min D. Esham / Wiki­me­dia Com­mons, CC BY-SA 3.0, https://commons.wikimedia.org/w/index.php?curid=56559

Damit kön­nen jeweils nur zwei Phi­lo­so­phen gleich­zei­tig essen und es muss jeweils ein Tel­ler zwi­schen ihnen sein, an dem nicht geges­sen wird. Eine his­to­ri­sche Lösung des Pro­blems kann man direkt in einer Publi­ka­ti­on von Dijks­tra nach­le­sen (S.29). Das hät­te man ein­fach for­ma­li­sie­ren kön­nen. Oder halt selbst nachdenken.

In der Infor­ma­tik­welt sind die Phi­lo­so­phen Pro­zes­se, die um die Betriebs­sys­tem­res­sour­cen auf dem Tisch kon­kur­rie­ren. Dabei muss man ver­mei­den, dass sich die Pro­zes­se gegen­sei­tig blo­ckie­ren: Wenn alle gleich­zei­tig wol­len, gibt es Streit und kei­ner kann die Res­sour­cen bele­gen, die er zum Essen braucht (infor­ma­tisch: Ver­klem­mung). Es darf aber auch kei­ne Situa­ti­on ein­tre­ten, in der alle so höf­lich sind, sich immer gegen­sei­tig den Vor­tritt zu las­sen (infor­ma­tisch: Aus­hun­ge­rung). Und natür­lich soll der Zugriff auf die Res­sour­cen fair und effi­zi­ent sein.

Die Her­aus­for­de­rung:

Man „denkt“ beim For­ma­li­sie­ren nicht nur für einen Pro­zess, son­dern für fünf, die mit­ein­an­der in einer defi­nier­ten Umge­bung interagieren.

Wer darf dann überhaupt miteinander essen?

Um das zu for­ma­li­sie­ren, neh­men wir mal eine simp­le mini­ma­le Daten­struk­tur – ein Feld mit einem boole­schen Ele­ment für jeden Pro­zess – d.h. jeder hat sein Flag, dass er auf „ich will essen“ set­zen kann. Dann gibt es fünf zuläs­si­ge Konstellationen:

10100
10010
01010
01001
00101

Das ist schon­mal hübsch, da es tat­säch­lich nur fünf zuläs­si­ge Fäl­le gibt. Boole­sche Wer­te zu scan­nen und zu mani­pu­lie­ren ist res­sour­cen­mä­ßig auch nicht so üppig aufwändig.

Eine Ent­schei­dung, ob man zwei Phi­lo­so­phen an den Tisch lässt, kann man ver­läss­lich fäl­len, wenn drei von ihnen ihr Inter­es­se bekun­det haben.

Damit nicht genug: Die Pro­zes­se müs­sen sich wei­ter­hin unter­ein­an­der steu­ern kön­nen, damit sie sich gegen­sei­tig an den Tisch las­sen können.

Ansatz

Man lässt immer drei Pro­zes­se in einen Emp­fangs­be­reich, die bei­den ande­ren blei­ben drau­ßen und stel­len sich an. Dann lässt man die mög­li­che Kon­stel­la­ti­on von zwei Phi­lo­so­phen an den Tisch. Der­je­ni­ge, der nicht zum Zuge kommt, bleibt in einem zwei­ten War­te­be­reich vor dem Tisch ste­hen (= sein Flag im Array bleibt gesetzt).

Wenn einer der am Tisch Essen­den auf­steht, kippt er sein Flag im Array, lässt einen aus der Schlan­ge im Emp­fangs­be­reich rein und stellt sich drau­ßen hin­ten wie­der an.

Ein beson­de­res Pro­blem ist die Konstellation:

10101

Bei sowas soll­te man die Rei­hen­fol­ge der Prü­fung mal vari­ie­ren, damit nicht immer die glei­chen zwei zum Zuge kom­men und der Drit­te „ver­hun­gert“ (das ist bei fünf Pro­zes­sen nicht sehr wahr­schein­lich, aber durch­aus mal möglich).

Wie macht man das mit dem Warten eigentlich?

Die ein­fachs­te Lösung besteht dar­in, die Pro­zes­se in End­los­schlei­fen mit einer Abbruch­be­din­gung (Prü­fung einer glo­ba­len Varia­ble) zu schi­cken, wenn sie im Emp­fangs­be­reich oder vor dem Tisch ste­hen. Dabei ver­bra­ten Sie bloß reich­lich Rechen­zeit – infor­ma­tisch heißt das „akti­ves War­ten“ (busy wait) – also dau­ernd her­um­quen­geln, ob man nicht end­lich dran ist. Moder­ne Betriebs­sys­te­me bekom­men das hin, mit sowas umzu­ge­hen, aber net­ter res­sour­cen­scho­nen­der Pro­gram­mier­stil ist das nicht.

Semaphoren als Lösung

Sema­pho­ren sind Daten­struk­tu­ren, die einen nega­ti­ven oder posi­ti­ven gan­zah­li­gen Wert anneh­men kön­nen und zusätz­lich einen Coun­ter besit­zen. Posi­ti­ve Wer­te geben die Anzahl der zur Ver­fü­gung ste­hen­den Res­sour­cen an, nega­ti­ve die Anzahl der Pro­zes­se, die bereits auf die Zutei­lung einer Res­sour­ce warten.

Der Coun­ter ist wie der Wert des Sema­phors für Anwen­dungs­pro­gram­me nicht ein­seh­bar. Inner­halb eines Pro­zes­ses kann ein Anwen­dungs­pro­gramm eine soge­nann­te P‑Operation auf einen Sema­phor aus­füh­ren. Wenn der Sema­phor einen posi­ti­ven Wert hat, wird die­ser um eins ernied­rigt (= eine Res­sour­ce ver­ge­ben) und der Pro­zess darf wei­ter­ma­chen. Wich­tig dabei: Das Betriebs­sys­tem ent­schei­det, wel­cher Pro­zess die Res­sour­ce erhält (meist FIFO, muss aber nicht).

Wenn der Wert nega­tiv oder null ist, wird auch um eins ernied­rigt und der Pro­zess muss war­ten (Auf Betriebs­sys­tem­ebe­ne wird dem Pro­zess der Pro­zes­sor ent­zo­gen, er bleibt im Spei­cher aktiv, ver­braucht aber außer Spei­cher kaum wei­te­re Res­sour­cen mehr).

Wenn der Pro­zess fer­tig ist, führt er eine V‑Operation auf den Sema­phor aus, der sich dadurch um Eins erhöht. Sema­pho­ren müs­sen, um die Inter­ak­ti­on von Pro­zes­sen steu­ern zu kön­nen, glo­ba­le Daten­struk­tu­ren sein.

Kritische Abschnitte

Da Pro­zes­se den Zustand bzw. Wert von Sema­pho­ren nicht abfra­gen, son­dern nur inkre­men­tie­ren oder dekre­men­tie­ren kön­nen, „erfah­ren“ sie von­ein­an­der nur über glo­ba­le Varia­blen oder sons­ti­ge Daten­struk­tu­ren, in unse­rem Fall z.B. das Array mit den boole­schen Elementen.

Wenn man auf glo­ba­len Daten­struk­tu­ren mit meh­re­ren Pro­zes­sen arbei­tet, muss man sicher­stel­len, dass das immer nur ein Pro­zess tun kann. Man sperrt sol­che Struk­tu­ren oder auch kri­ti­sche Abschnit­te durch einen extra Sema­phor (P‑Operation), macht sei­ne Arbeit und ent­sperrt die­sen Sema­phor wie­der (V‑Operation). Sol­che Sema­pho­ren haben nur 0 und 1 als Zustän­de und wer­den oft als „mutex“ bezeich­net. Damit wird ver­hin­dert, dass zwei Pro­zes­se sol­che Daten­struk­tu­ren gleich­zei­tig ver­än­dern (oder lesen) und damit Inkon­sis­ten­zen entstehen.

Meine Lösung (mittlerweile nach Rückmeldungen)

In der Vor­le­sung wird eine recht eigen­wil­li­ge Beschrei­bungs­spra­che ver­wen­det. Das hat damit zu tun, dass man nicht oft nur wenig über der Maschi­nen­spra­che bewegt, die dann deut­lich ein­ge­schränk­ter im Befehls­satz ist. Wenn man auf glo­ba­le Daten­struk­tu­ren lesend oder schrei­bend zugreift, muss man das „ato­mar“ machen (dafür sor­gen, dass man allei­ne ist).

TYPE philId = (0..4);
hungry_phils : SEMAPHORE == 3; // wir haben vorerst drei Plätze 
privsem : ARRAY (0...4) OF SEMAPHORE == [EACH == 0]; // persönlicher Warteplatz am Tisch
mutex_helper : SEMAPHORE == 1;
hungry_phils_array : ARRAY BOOLEAN OF slot == [EACH == FALSE];
swap_check : BOOLEAN == FALSE;

philosopher : PROCESS (id : IN philId)
BEGIN
  LOOP

    --denken

    P(hungry_phils);

    P(mutex_helper);
       hungry_phils_array[id] == true;

    IF swap_check
       IF hungry_phils_array[0] AND hungry_phils_array[2]
          let_eat[0,2];
       ELSEIF hungry_phils_array[0] AND hungry_phils_array[3]
          let_eat[0,3];
       ELSEIF hungry_phils_array[1] AND hungry_phils_array[3]
          let_eat[1,3];
       ELSEIF hungry_phils_array[1] AND hungry_phils_array[4]
          let_eat[1,4];
       ELSEIF hungry_phils_array[2] AND hungry_phils_array[4]
          let_eat[2,4];
       ENDIF
    ELSE
       IF hungry_phils_array[4] AND hungry_phils_array[2]
          let_eat[4,2];
       ELSEIF hungry_phils_array[4] AND hungry_phils_array[1]
          let_eat[4,1];
       ELSEIF hungry_phils_array[0] AND hungry_phils_array[3]
          let_eat[0,3];
       ELSEIF hungry_phils_array[1] AND hungry_phils_array[3]
          let_eat[1,3];
       ELSEIF hungry_phils_array[0] AND hungry_phils_array[2]
          let_eat[0,2];
       ENDIF
    ENDIF

    IF NOT swap_check
         swap_check == TRUE;
    ELSE
         swap_check == FALSE;
    ENDIF

    V(mutex_helper);

    P(privsem[id]);
      --essen
      P(mutex_helper);
          hungry_phils_array[id] == false; 
      P(mutex_helper);      
    V(hungry_phils); 

  REPEAT;

  let_eat : PROCEDURE (id1 : CARDINAL,id2 : CARDINAL)
     BEGIN
       V(privsem[id1]);
       V(privsem[id2]);
     END
 
END

Da steckt deut­lich mehr Gehirn­schmalz drin, als es den Anschein hat – z.B. war es gar nicht so ein­fach, immer dafür zu sor­gen, dass zwei Phi­lo­so­phen gleich­zei­tig essen. In alter­na­ti­ven Lösungs­vor­schlä­gen aus dem Tuto­ri­um wäre auch ein Ein­zel­es­sen mög­lich gewesen.

Wie geht in der Vorlesung weiter?

Sema­pho­ren sind bis­her Black­bo­xen. Jetzt wird geschaut, wie ein Betriebs­sys­tem Sema­pho­re rea­li­siert (das geht übri­gens manch­mal nicht ohne „busy wai­ting“). Letzt­lich geht es im Zutei­lung von Rechen­zeit an Pro­zes­se. Ich kann gedank­lich momen­tan nur leid­lich mit­hal­ten und brau­che letzt­lich zu viel Zeit für Lösun­gen. Das wird in der Klau­sur spä­ter spannend …