Das Problem der dinierenden Philosophen

1. Aufgabe

Das Beispiel der dinierenden Philosophen ist eines der populärsten Standardprobleme aus dem Bereich der Parallelprogrammierung. Es erlaubt, sowohl die Synchronisation wie auch die Kooperation der beteiligten Threads in einer lebendigen, grafischen Simulation darzustellen. Das Problem ist das folgende: In einem Kloster gibt es fünf Mönche, die sich der Philosophie widmen. Jeder Philosoph wäre glücklich, wenn er nur denken könnte, aber gelegentlich ist auch der menschliche Trieb des Essens zu beachten. Somit kennt jeder Philosoph drei Beschäftigungen:

  • denken

  • hungrig sein

  • essen

Die gemeinschaftliche Nahrungsaufnahme findet an einem großen Tisch statt, an dem die Philosophen im Kreis sitzen, siehe Abbildung 1. In der Mitte des Tisches steht eine Schüssel mit Reis, die immer wieder gefüllt wird. Auf dem Tisch gibt es ferner fünf Teller und fünf Gabeln. Solange ein Philosoph denkt, geschieht nichts. Bekommt er Hunger, versucht er zwei Gabeln, und zwar die zu seiner linken und rechten Seite, zu bekommen. Ist einer seiner benachbarten Glaubensbrüder gerade beim Essen, muss er warten. Sind beide Gabeln frei, kann er mit dem Essen beginnen. Nachdem er satt ist, legt er beide Gabeln zurück und denkt wieder. Die drei Zustände denken, hungrig sein und essen werden folglich ständig in dieser Reihenfolge durchlaufen.

Die dinierenden Philosophen.

Abbildung 1. Die dinierenden Philosophen.


Eine Lösung dieses Problems gestattet es, dass jederzeit so viele Philosophen wie möglich essen können und dass keiner der Philosophen verhungert. Man kann leicht erkennen, dass in der in Abbildung 1 betrachteten Konfiguration maximal zwei Philosophen gleichzeitig essen können und dass eine Gabel immer ungenutzt bleibt.

Um dieses Problem in einer WPF-Anwendung umzusetzen, gehen Sie bitte wie folgt vor: Neben dem Hauptfenster (Klasse MainWindow), das durch die Projektschablone automatisch angelegt wird, entwerfen Sie zwei weitere Steuerelemente (Projektschablonentyp User Control WPF):

  1. Steuerelement TableControl:

    Das Steuerelement TableControl abstrahiert einen realen Tisch. Er verwaltet die auf ihm liegenden Gabeln.

  2. Steuerelement PhilosopherControl:

    Das Steuerelement PhilosopherControl repräsentiert einen Philosophen. Ein Philosoph kennt den Tisch – Steuerelement TableControl–, an dem er sitzt.

Die Oberflächen der beiden Steuerelemente können Sie äußerst einfach gestalten. In Abbildung 2 finden Sie das TableControl-Steuerelement vor, die fünf kleinen Kreise sollen in sehr stilisierter Form die Gabeln darstellen:

Oberfläche des Steuerelements TableControl.

Abbildung 2. Oberfläche des Steuerelements TableControl.


Ein TableControl-Objekt verwaltet die auf dem Tisch liegenden Gabeln (Tabelle 1). Um zwei Gabeln aufnehmen bzw. wieder ablegen zu können, gibt es in dieser Klasse zwei Methoden DemandForks und ReleaseForks:

Methode

Beschreibung

DemandForks

public void DemandForks (int seat);

Der Wunsch, zwei Gabeln zum Essen zu verwenden, wird durch die Methode DemandForks übermittelt. Ein Aufruf von DemandForks blockiert solange, bis die zwei angeforderten Gabeln frei sind. Nach der Reservierung zweier Gabeln durch den Aufrufer ist die Farbe der Gabeln zu ändern. Der Parameter seat spezifiziert, auf welchem Platz der Philosoph sitzt.

ReleaseForks

public void ReleaseForks (int seat);

Nach dem Essen werden zwei Gabeln mit der Methode ReleaseForks wieder auf dem Tisch abgelegt. Mit den Hilfsmitteln der Threadkooperation gibt ein Aufruf der ReleaseForks-Methode kund, dass die zwei Gabeln wieder unbenutzt sind. Unbenutzte Gabeln besitzen eine andere Farbe als benutzte!

Tabelle 1. Wichtige Methoden des TableControl-Steuerelements.


Wir kommen auf die Philosophen zu sprechen. Visuell genügt es, einen Philosophen durch ein kreisförmiges Ellipse-Objekt zu repräsentieren (Abbildung 3):

Oberfläche des Steuerelements PhilosopherControl.

Abbildung 3. Oberfläche des Steuerelements PhilosopherControl.


Ein Philosoph kennt natürlich den Tisch, an dem er sitzt und kann folglich Gabeln nehmen und wieder ablegen. Die Realisierung der Lebenszyklusmethoden eines Philosophen ist in Tabelle 2 beschrieben:

Methode

Beschreibung

Thinking

private void Thinking();

Während eines Aufrufs der Thinking-Methode denkt der Philosoph. Die Zeitdauer dieser Phase sollte mit Hilfe eines Zufallszahlengenerators sinnvoll begrenzt werden.

Hungry

private void Hungry();

Mit einem Aufruf von Hungry ändert sich die farbliche Darstellung des PhilosopherControl-Objekts, um sein Hungergefühl zum Ausdruck zu bringen. Mit einem Aufruf von DemandForks am dazugehörigen TableControl-Steuerelement versucht er die für ihn erforderlichen Gabeln aufzunehmen.

Eating

private void Eating();

Ein Aufruf der Eating-Methode bedeutet, dass ein Philosoph seine linke und rechte Gabel belegt hat und für eine – wiederum zufällige Zeitdauer – isst.

EatingDone

private void EatingDone();

Durch diesen Aufruf beendet der Philosoph das Essen und er legt seine benutzten Gabeln mit einem Aufruf von ReleaseForks am dazugehörigen TableControl-Steuerelement wieder auf dem Tisch ab.

Tabelle 2. Wichtige Methoden des PhilosopherControl-Steuerelements.


Neben den in Tabelle 2 definierten Methoden besitzt ein Philosoph zusätzlich die beiden Methoden Start und Stop, um den Speiseraum zu betreten bzw. zu verlassen:

public void Start ();
public void Stop ();

Für das Leben eines Philosophen als endloser Zyklus aus denken, hungrig sein und essen bietet sich der Gebrauch eines Threads an. Mit der Füllfarbe eines Ellipse-Objekts lässt sich der Zustand eines Philosophen gut charakterisieren:

  • Farbe Color.DarkGray – Philosoph betritt oder verlässt den Speisesaal.

  • Farbe Color.Green – Philosoph denkt.

  • Farbe Color.Yellow – Philosoph ist hungrig.

  • Farbe Color.Red – Philosoph isst.

Das Anlegen eines TableControl-Objekts sowie der fünf PhilosopherControl-Objekte erfolgt im Konstruktor des Hauptfensters. Es fungiert als Container für den Tisch und fünf Philosophen. Zum Starten und Anhalten der Simulation bringen Sie im Hauptfenster noch zwei Schaltflächen mit entsprechender Beschriftung unter, siehe dazu Abbildung 4:

Anwendung zur Simulation des Problems der dinierenden Philosophen.

Abbildung 4. Anwendung zur Simulation des Problems der dinierenden Philosophen.


Beim Klicken auf die mit Start beschriftete Schaltfläche wenden sich die Philosophen ihrem Lebenszyklus zu. Zunächst gehen sie der Beschäftigung denken nach, die anderen Zustände schließen sich wie beschrieben an. Mit Stop beenden die Philosophen die Aktivitäten ihres Lebenszyklusses. Der Vorgang sollte in geordneten Bahnen erfolgen, sprich ein denkender oder essender Philosoph sollte nicht in seiner Tätigkeit unterbrochen werden.

2. Lösung

Eine einfache Lösung des Philosophen-Problems basiert auf dem Kooperationskonzept der Klasse Monitor mit ihren Methoden Wait und PulseAll. Aus der Sicht des Interimsraums eines Monitors können wir zwei Zustände erkennen, die für einen am Essenstisch sitzenden Philosophen in Betracht kommen:

  • Die zwei Gabeln, die der Philosoph zum Essen benötigt, sind frei.

  • Eine der zwei Gabeln oder beide ist bzw. sind belegt.

In Abhängigkeit vom Zustand der relevanten Gabeln betritt ein Philosoph den Interimsraum des Monitors, wenn er hungrig ist, aber keine Gabeln zum Essen zur Verfügung stehen. Legt ein Philosoph seine Gabeln nach dem Essen wieder auf den Tisch zurück, weckt er die schlafenden (hungrigen) Philosophen des Interimsraums auf. Wir erkennen nach diesen Überlegungen, dass das Monitorobjekt am sinnvollsten der Klasse TableControl zuzuordnen ist (Listing 1 und Listing 2):

01: <UserControl x:Class="WpfDiningPhilosophers.TableControl"
02:              xmlns="http://schemas.microsoft.com/winfx/2006/xaml/presentation"
03:              xmlns:x="http://schemas.microsoft.com/winfx/2006/xaml"
04:              xmlns:mc="http://schemas.openxmlformats.org/markup-compatibility/2006" 
05:              xmlns:d="http://schemas.microsoft.com/expression/blend/2008" 
06:              Width="Auto" Height="Auto">
07:     
08:     <Canvas Name="CanvasTable" >
09:         <Ellipse Width="150" Height="150" Stroke="Black" Fill="Black"
10:                  VerticalAlignment="Top" HorizontalAlignment="Left"/>
11: 
12:         <Ellipse Name="Fork1" Canvas.Left="15" Canvas.Top="55"
13:                  Fill="White" Height="16" HorizontalAlignment="Left"
14:                  Stroke="Black" VerticalAlignment="Top" Width="16" />
15:         <Ellipse Name="Fork2" Canvas.Left="65" Canvas.Top="20"
16:                  Fill="White" Height="16" HorizontalAlignment="Left"
17:                  Stroke="Black" VerticalAlignment="Top" Width="16" />
18:         <Ellipse Name="Fork3" Canvas.Left="120" Canvas.Top="55"
19:                  Fill="White" Height="16" HorizontalAlignment="Left"
20:                  Stroke="Black" VerticalAlignment="Top" Width="16" />
21:         <Ellipse Name="Fork4" Canvas.Left="100" Canvas.Top="110"
22:                  Fill="White" Height="16" HorizontalAlignment="Left"
23:                  Stroke="Black" VerticalAlignment="Top" Width="16" />
24:         <Ellipse Name="Fork5" Canvas.Left="35" Canvas.Top="110"
25:                  Fill="White" Height="16" HorizontalAlignment="Left"
26:                  Stroke="Black" VerticalAlignment="Top" Width="16" />
27:     </Canvas>
28: </UserControl>

Beispiel 1. Die Klasse TableControl: XAML.


Die Gabeln des Tisches werden ebenfalls in XAML deklariert - es handelt sich um stilisierte Ellipse-Objekte. In Listing 2 finden Sie den noch erforderlichen Code-Behind-Anteil vor, um zur Laufzeit des Programms dynamisch die Hintergrundfarbe der Gabeln ändern zu können:

01: namespace WpfDiningPhilosophers
02: {
03:     public partial class TableControl : UserControl
04:     {
05:         private Ellipse[] ellipses;
06:         private bool[] forks;
07: 
08:         // c'tor
09:         public TableControl()
10:         {
11:             this.InitializeComponent();
12: 
13:             // initialize forks
14:             this.forks = new bool[5];
15:             for (int i = 0; i < this.forks.Length; i++)
16:                 this.forks[i] = false;
17: 
18:             // store references of forks in an array
19:             this.ellipses = new Ellipse[5];
20:             this.ellipses[0] = this.Fork1;
21:             this.ellipses[1] = this.Fork2;
22:             this.ellipses[2] = this.Fork3;
23:             this.ellipses[3] = this.Fork4;
24:             this.ellipses[4] = this.Fork5;
25:         }
26: 
27:         // private indexer
28:         private bool this[int index]
29:         {
30:             get
31:             {
32:                 index %= 5;
33:                 return this.forks[index];
34:             }
35: 
36:             set
37:             {
38:                 index %= 5;
39:                 this.forks[index] = value;
40:             }
41:         }
42: 
43:         // public interface
44:         public void DemandForks(int seat)
45:         {
46:             Monitor.Enter(this);
47:             while (this[seat] == true || this[seat + 1] == true)
48:                 Monitor.Wait(this);
49:             this[seat] = true;
50:             this[seat + 1] = true;
51:             Monitor.Exit(this);
52: 
53:             this.UpdateControl();
54:         }
55: 
56:         public void ReleaseForks(int seat)
57:         {
58:             Monitor.Enter(this);
59:             this[seat] = false;
60:             this[seat + 1] = false;
61:             Monitor.PulseAll(this);
62:             Monitor.Exit(this);
63: 
64:             this.UpdateControl();
65:         }
66: 
67:         // private helper methods
68:         private delegate void UpdateControlHandler(bool[] states);
69: 
70:         private void UpdateControl()
71:         {
72:             if (!this.Dispatcher.CheckAccess())
73:             {
74:                 // execute 'UpdateControl' asynchronously on primary thread
75:                 UpdateControlHandler d = new UpdateControlHandler(this.UpdateControl);
76:                 bool[] states = (bool[])this.forks.Clone();
77:                 Object[] args = new Object[] { states };
78:                 this.Dispatcher.BeginInvoke(d, args);
79:             }
80:         }
81: 
82:         private void UpdateControl(bool[] states)
83:         {
84:             for (int i = 0; i < states.Length; i++)
85:             {
86:                 SolidColorBrush sb = (states[i]) ? Brushes.Red : Brushes.White;
87:                 this.ellipses[i].Fill = sb;
88:             }
89:         }
90:     }
91: }

Beispiel 2. Die Klasse TableControl: Code-Behind Anteile.


Zur Implementierung der Klasse PhilosopherControl definieren wir einen Aufzählungstyp PhilosopherState, um die möglichen Zustände im Leben eines Philosophen zu beschreiben:

enum PhilosopherState { None, Thinking, Eating, Hungry };

Das Leben eines Philosophen simulieren wir im Kontext eines Threads. In der Threadprozedur kommen alternierend vier Methoden Thinking, Hungry, Eating und EatingDone zum Aufruf. Die beiden Methoden Hungry und EatingDone stellen das Bindeglied zum TableControl-Objekt dar, mit Hilfe der zwei Methoden DemandForks und ReleaseForks versucht der Philosoph in den Besitz seiner notwendigen Gabeln zu gelangen bzw. legt diese wieder auf den Tisch zurück (Listing 3 und Listing 4):

01: <UserControl x:Class="WpfDiningPhilosophers.PhilosopherControl"
02:              xmlns="http://schemas.microsoft.com/winfx/2006/xaml/presentation"
03:              xmlns:x="http://schemas.microsoft.com/winfx/2006/xaml"
04:              xmlns:mc="http://schemas.openxmlformats.org/markup-compatibility/2006" 
05:              Width="100" Height="100">
06:     <DockPanel LastChildFill="True">
07:         <Ellipse Name="Circle" Fill="LightGray" Stroke="Black" StrokeThickness="7">
08:         </Ellipse>
09:     </DockPanel>
10: </UserControl>

Beispiel 3. Die Klasse PhilosopherControl: XAML.


Beachten Sie nachfolgend in Listing 4 die Zeilen 25 bis 36 sowie 96 und 107: Ein Philosoph muss den Tisch kennen, an dem er sitzt. Aus diesem Grund gibt es am Philosophensteuerelement eine Eigenschaft Table, die die Referenz eines TableControl-Steuerelements aufnehmen kann. In den Methoden Hungry und EatingDone hat der Philosoph dann die Möglichkeit, den Zugang zu den Gabeln zu erlangen:

001: namespace WpfDiningPhilosophers
002: {
003:     public enum PhilosopherState { None, Thinking, Eating, Hungry };
004: 
005:     public partial class PhilosopherControl : UserControl
006:     {
007:         private TableControl table;
008:         private int seat;
009: 
010:         // threading utils
011:         private Thread t;
012:         private bool running;
013:         private Random rand;
014: 
015:         private PhilosopherState state;
016: 
017:         public PhilosopherControl()
018:         {
019:             this.InitializeComponent();
020:             this.rand = new Random(DateTime.Now.Millisecond);
021:             this.State = PhilosopherState.None;
022:         }
023: 
024:         // properties
025:         public TableControl Table
026:         {
027:             get
028:             {
029:                 return this.table;
030:             }
031: 
032:             set
033:             {
034:                 this.table = value;
035:             }
036:         }
037: 
038:         public int Seat
039:         {
040:             get
041:             {
042:                 return this.seat;
043:             }
044: 
045:             set
046:             {
047:                 this.seat = value;
048:             }
049:         }
050: 
051:         private PhilosopherState State
052:         {
053:             get
054:             {
055:                 return this.state;
056:             }
057: 
058:             set
059:             {
060:                 this.state = value;
061:                 this.UpdateControl();
062:             }
063:         }
064: 
065:         // public interface
066:         public void Start()
067:         {
068:             if (this.t == null)
069:             {
070:                 ThreadStart ts = new ThreadStart(this.Run);
071:                 this.t = new Thread(ts);
072:                 this.running = true;
073:                 this.t.Start();
074:             }
075:         }
076: 
077:         public void Stop()
078:         {
079:             if (this.t != null)
080:             {
081:                 this.running = false;
082:                 this.t = null;
083:             }
084:         }
085: 
086:         // private helper methods
087:         private void Thinking()
088:         {
089:             this.State = PhilosopherState.Thinking;
090:             Thread.Sleep(this.rand.Next(3000));
091:         }
092: 
093:         private void Hungry()
094:         {
095:             this.State = PhilosopherState.Hungry;
096:             this.table.DemandForks(this.seat);
097:         }
098: 
099:         private void Eating()
100:         {
101:             this.State = PhilosopherState.Eating;
102:             Thread.Sleep(this.rand.Next(3000));
103:         }
104: 
105:         private void EatingDone()
106:         {
107:             this.table.ReleaseForks(this.seat);
108:         }
109: 
110:         private void Run()
111:         {
112:             while (this.running)
113:             {
114:                 this.Thinking();
115:                 this.Hungry();
116:                 this.Eating();
117:                 this.EatingDone();
118:             }
119: 
120:             this.State = PhilosopherState.None;
121:         }
122: 
123:         private delegate void UpdateControlHandler(PhilosopherState state);
124: 
125:         private void UpdateControl()
126:         {
127:             if (! this.Dispatcher.CheckAccess())
128:             {
129:                 // execute 'UpdateControl' asynchronously on primary thread
130:                 UpdateControlHandler d = new UpdateControlHandler(this.UpdateControl);
131:                 this.Dispatcher.BeginInvoke(d, this.State);
132:             }
133:         }
134: 
135:         private void UpdateControl(PhilosopherState state)
136:         {
137:             SolidColorBrush sb;
138:             switch (state)
139:             {
140:                 case PhilosopherState.Eating:
141:                     sb = Brushes.Red;
142:                     break;
143:                 case PhilosopherState.Hungry:
144:                     sb = Brushes.Yellow;
145:                     break;
146:                 case PhilosopherState.Thinking:
147:                     sb = Brushes.Green;
148:                     break;
149:                 default:
150:                     sb = Brushes.DarkGray;
151:                     break;
152:             }
153:             this.Circle.Fill = sb;
154:         }
155:     }
156: }

Beispiel 4. Die Klasse PhilosopherControl: Code-Behind.


Zur Platzierung und Verschaltung des TableControl- und der PhilosopherControl-Objekte kommen wir nun in Listing 5 und Listing 6 zu sprechen. Die Platzierung selbst ist in XAML nicht das Problem. Die fünf PhilosopherControl-Objekte müssen aber das eine TableControl-Objekt kennen, betrachten Sie dazu die Zeilen 20 und 21 von Listing 6: Die Referenz des TableControl-Objekts wird an alle Philosophen durchgeschleust:

01: <Window x:Class="WpfDiningPhilosophers.MainWindow"
02:         xmlns="http://schemas.microsoft.com/winfx/2006/xaml/presentation"
03:         xmlns:x="http://schemas.microsoft.com/winfx/2006/xaml"
04:         xmlns:local="clr-namespace:WpfDiningPhilosophers"
05:         Title="Dining Philosphers Problem" Height="500" Width="500">
06:     
07:     <DockPanel LastChildFill="True">
08:         <UniformGrid DockPanel.Dock="Top" Rows="1" Columns="2">
09:             <Button Height="30" Name="ButtonStart" Click="Button_Click">Start</Button>
10:             <Button Height="30" Name="ButtonStop" Click="Button_Click">Stop</Button>
11:         </UniformGrid>
12:         <Canvas>
13:             <local:TableControl x:Name="DiningTable" Canvas.Top="150" Canvas.Left="150">
14:             </local:TableControl>
15:             <local:PhilosopherControl
16:                 x:Name="DiningPhilosopher1"
17:                 Canvas.Top="20" Canvas.Left="70"></local:PhilosopherControl>
18:             <local:PhilosopherControl
19:                 x:Name="DiningPhilosopher2"
20:                 Canvas.Top="20" Canvas.Left="320"></local:PhilosopherControl>
21:             <local:PhilosopherControl
22:                 x:Name="DiningPhilosopher3"
23:                 Canvas.Top="190" Canvas.Left="380"></local:PhilosopherControl>
24:             <local:PhilosopherControl
25:                 x:Name="DiningPhilosopher4"
26:                 Canvas.Top="300" Canvas.Left="200"></local:PhilosopherControl>
27:             <local:PhilosopherControl
28:                 x:Name="DiningPhilosopher5"
29:                 Canvas.Top="190" Canvas.Left="20"></local:PhilosopherControl>
30:         </Canvas>
31:     </DockPanel>
32: </Window>

Beispiel 5. Hauptfenster der Anwendung: Klasse MainWindow: XAML.


01: namespace WpfDiningPhilosophers
02: {
03:     public partial class MainWindow : Window
04:     {
05:         private PhilosopherControl[] philosophers;
06: 
07:         public MainWindow()
08:         {
09:             this.InitializeComponent();
10: 
11:             // collect references of philosophers in an array
12:             this.philosophers = new PhilosopherControl[5];
13:             this.philosophers[0] = this.DiningPhilosopher1;
14:             this.philosophers[1] = this.DiningPhilosopher2;
15:             this.philosophers[2] = this.DiningPhilosopher3;
16:             this.philosophers[3] = this.DiningPhilosopher4;
17:             this.philosophers[4] = this.DiningPhilosopher5;
18: 
19:             // connect philosophers with table
20:             for (int i = 0; i < this.philosophers.Length; i++)
21:                 this.philosophers[i].Table = this.DiningTable;
22: 
23:             // assign seat number to each philosophers
24:             for (int i = 0; i < this.philosophers.Length; i++)
25:                 this.philosophers[i].Seat = i;
26:         }
27: 
28:         private void Button_Click(Object sender, RoutedEventArgs e)
29:         {
30:             if (sender == this.ButtonStart)
31:             {
32:                 for (int i = 0; i < this.philosophers.Length; i++)
33:                     this.philosophers[i].Start();
34:             }
35:             else if (sender == this.ButtonStop)
36:             {
37:                 for (int i = 0; i < this.philosophers.Length; i++)
38:                     this.philosophers[i].Stop();
39:             }
40:         }
41:     }
42: }

Beispiel 6. Hauptfenster der Anwendung: Klasse MainWindow: Code-Behind.


Hinweis: Bei der Realisierung der Klasse PhilosopherControl in Listing 4 kam für die Belange des Multithreading die Klasse Thread zum Einsatz. Alternativ hätte man auch mit der Klasse Task arbeiten können. Von einer Umstellung betroffen ist nur die Start-Methode betroffen:

public void Start()
{
    if (this.t == null)
    {
        this.t = new Task(this.Run);
        this.running = true;
        this.t.Start();
    }
}

Natürlich setzt dieses Codefragement im Instanzvariablenbereich die Deklaration einer Task-Referenz voraus:

private Task t;