home
> study
>> dissim

translate to English (by SYSTRAN)

Diskrete Simulation - C++SIM, Teil 3

Teil 1, Teil 2, Teil 3

1 Beispiel Tokenbus

Das Tokenbus-System besitzt n = 60 Teilnehmer, die durch je eine (unbegrenzte) Warteschlange repräsentiert sind. Die Warteschlangen werden sämtlich nach dem Silo-(Fifo-)Prinzip abgearbeitet. Die Zwischenankunftszeit für die Nachrichten sind für jede der Warteschlangen exponentialverteilt. Für jeden der Teilnehmer ist die mittlere Zwischenankunftszeit der Nachrichten gleich a. Die Übertragungsdauer der Nachrichten verteilt sich so: 90 % der Nachrichten beanspruchen 100 µs und die restlichen 10 % beanspruchen 600 µs. Die Übertragung des Tokens dauert c = 100 µs. Die Grenze für die Sendeberechtigung ist so festgelegt: Jeder Teilnehmer darf nach Erhalt des Staffelholzes höchstens eine Nachricht senden.

Welcher Prozentsatz von Nachrichten hat eine Wartezeit von mehr als 100 ms, wenn die mittlere Zwischenankunftszeit a = 18 ms ist? Auf welchen Prozentsatz kommt man für a = 16 ms?

1.1 Klassendiagramm

1.2 Source Code

Hier gibt's den Source code des Beispiels.

1.4 Ergebnisse der Simulation

2 Statistische Funktionen

Neben den eigentlich für die Simulation notwendigen Funktionen, bietet C++SIM auch noch einige statistische Funktionen zur Auswertung der Simulationsergebnisse an.

So stellt C++SIM mit den Klassen Mean, Variance und SimpleHistogram einfache Möglichkeiten zur Verfügung, um Mittelwert, Varianz und Histogramme auszugeben, wobei die Klassen jeweils aufeinander aufbauen:

Mean --> Variance --> PrecisionHistogram --> Histogram

Die Verwendung eines Mittelwertes ist gut in die C++-Umgebung eingebunden:

Mean myMean;

myMean.setValue(value1);
myMean += value1;

cout << myMean;

Beim Tokenbus-Beispiel wird folgende Ausgabe für die mittlere Wartezeit bei einer mittleren Zwischenankunftszeit von 16 ms erzeugt:

Number of samples : 50000
Minimum           : 0
Maximum           : 423.813
Sum               : 2.63466e+06
Mean              : 52.6932

Die Berechnung der Varianz zusätzlich zum Mittelwert geschieht ähnlich einfach, indem statt der Klasse Mean die Klasse Variance verwendet wird:

Variance myVariance;

myVariance.setValue(value1);
myVariance += value1;

cout << myVariance;

Histogramme lassen sich ebenfalls ähnlich erstellen, wobei es allerdings verschiedene Klassen gibt, um die Aufteilung beim Histogramm vorzunehmen. SimpleHistogram unterteilt den Bereich in Bereiche fester Länge. Als Beispiel wurde wieder der Tokenbus bei einer mittleren Zwischenankunftszeit von 16 ms verwendet:

// SimpleHistogram (double min, double max, double w);
// SimpleHistogram (double min, double max, long nbuckets);
SimpleHistogram mySimpleHist(0, 200, (long) 10);

myVariance.setValue(value1);
myVariance += value1;

cout << myVariance;

Die Ausgabe ist zwar nicht sehr ansprechend gestaltet, enthält aber alle notwendigen Informationen. Um eine ansprechender oder eventuell sogar graphische Ausgabe zu erhalten, kann eine eigene Klasse abgeleitet werden, in der die Ausgabefunktion ersetzt wird.

Maximum index range  : 440
Minimum index range  : 0
Number of buckets    : 11
width of each bucket : 40
Bucket : < 0, 26923 >
Bucket : < 40, 12523 >
Bucket : < 80, 5772 >
Bucket : < 120, 2453 >
Bucket : < 160, 1041 >
Bucket : < 200, 579 >
Bucket : < 240, 332 >
Bucket : < 280, 201 >
Bucket : < 320, 131 >
Bucket : < 360, 38 >
Bucket : < 400, 7 >

Variance          : 2726.71
Standard Deviation: 52.2179
Number of samples : 50000
Minimum           : 0
Maximum           : 400
Sum               : 1.73376e+06
Mean              : 34.6752

Auffallend bei diesen Werten ist, dass der Mittelwert nicht mit dem obigen übereinstimmt - offenbar verwendet C++SIM bei einem Histogramm zur Berechnung des Mittelwertes die Werte nur mehr aus dem Histogramm und nicht die echten Werte.

Neben diesen elementaren statistischen Funktionen existieren noch zwei weitere Funktionen zur Ausgabe von Histogrammen, die allerdings hier nicht mehr besprochen werden. Leider schweigt die Dokumentation ebenfalls zu den statistischen Funktionen, sodass nur mehr das Studium des Quelltextes bleibt, um an eine Beschreibung der Funktionen zu kommen.

3 Besonderheiten beim Starten der Simulation

Um eine Simulation in C++SIM zu starten sind einige Detail zu beachten, die auf den ersten Blick nicht ganz einsichtig erscheinen. Das Hauptmodul eines typischen Simulationsprogramm muß immer ungefähr so aussehen: (als Beispiel dient hier wieder das Tokenbus-Beispiel)

// Initialisierung des Thread-Pakets
Thread::Initialize();

Node n[nrNodes];      // Netzwerk-Knoten
Token t(n, nrNodes);  // Token, das den Ablauf steuert

t.Await();
t.Exit();

Der erste aktive Simulationsprozess muß dann noch folgende Methoden definieren, um die Simulation in Gang zu bringen:

void Token::Body()
{
  Scheduler::scheduler().Resume();

  // ...
  // hier startet die eigentliche Simulation
  // ...

  Scheduler::scheduler().reset();
  Scheduler::scheduler().Suspend();

  /*
   * Must reactivate main thread before this thread "dies" or there
   * will be nothing waiting to "catch" us.
   */
  Thread::mainResume();
}

void Token::Await()
{
  Resume();
  Thread::Self()->Suspend();
}

void Token::Exit()
{
  Thread::Exit();
}

4 Fehler beim Thread-Handling

Siehe dazu auch Anhang A Zusatz.

Bei ausführlichen Tests unter Linux (POSIX-Threads) traten merkwürdige Effekte auf. Nach einiger Zeit stellte sich heraus, dass es irgendetwas mit dem Beenden von Threads zu tun haben müsse. Schließlich konnte ein Fehler im C++SIM-Code (zumindest beim POSIX-Thread-Support) entdeckt werden.

Wird ein Thread beendet, so aktiviert C++SIM den nächsten lauffähigen Thread und ruft im sich beendenden Thread die Methode terminateThread auf, damit sich dieser selbst beendet. Wird allerdings im gerade aktivierten Thread das Thread-Object des alten Threads sofort gelöscht, ohne dass dieser eine Gelegenheit hat, sich zuvor selbst zu beenden, ist das Chaos vorprogrammiert - da hilft auch der Aufruf von terminateThread im Destruktors des Thread-Objekts nichts mehr, da dieser nicht wartet, bis sich der Thread beendet hat.

Eine Möglichkeit, das Problem zu beheben wäre, in der Methode terminateThread auf den Thread mit pthread_join zu warten. Nachteil dabei ist allerdings, dass das Programm wirklich solange wartet, bis sich der Thread beendet hat - ein Abbruch der Simulation durch das Hauptprogramm ist dann auch nur mit Unterstützung jedes Simulationsprozesses möglich.

// tidy things up before we terminate thread

Thread::~Thread ()
{
  Remove(this);

  terminateThread();

  delete _data;
}

void Thread::terminateThread ()
{
  /*
   * If one thread terminates another then we must switch contexts
   * to the terminating thread for it to tidy itself up. Then that
   * thread must switch back to us.
   */

  _data->dead = TRUE;
  _data->waitThread = pthread_self();
  if (pthread_equal(_data->waitThread, _data->_thread) == 0)
  {
    Thread::Resume();
    pthread_mutex_lock(&_data->_lock);  // hier evtl pthread_join
    pthread_mutex_destroy(&_data->_lock);
    pthread_attr_destroy(&_data->_attr);
  }
  else
  {
    pthread_mutex_destroy(&_data->_lock);
    pthread_attr_destroy(&_data->_attr);
    pthread_exit(0);
  }
}

5 Gesamteindruck

Jemand, der bereits einige Grundkenntnisse bei der Simulation mit SIMULA hat, sollte keine größeren Probleme haben, sich in kürzester Zeit in C++SIM einarbeiten zu können.

Gegenüber Simulationspaketen, die ihre eigene Programmiersprache mitbringen (wie zB ModSim), hat C++SIM sicher den Vorteil, dass es auf einer der bekanntesten Programmiersprachen aufsetzt. Dadurch läßt sich sicher wieder einiges an Einarbeitsungszeit sparen, wenn man vorher bereits mit C++ gearbeitet hat.

Das Zurückgreifen auf OS-Threads für die Simulationsprozesse kann bei großer Anzahl von Simulationsprozessen zu Problemen führen, da übliche PC-Betriebssysteme meist nur für eine überschaubare Anzahl von Threads ausgelegt sind. Auch scheint die Synchronisation zwischen den Threads durch den Umweg über das Betriebssystem unnötig zeitaufwendig zu sein. Dies ist natürlich vor allem vor dem Hintergrund zu sehen, dass sowieso immer nur ein einzelner Simulationsprozess zur gleichen Zeit aktiv ist.

Teilweise ist die vorhandene Dokumentation etwas mager - die Statistikklassen sind zum Beispiel überhaupt nicht in der Dokumentation erwähnt.

A Zusatz

Auf eine Mail an die Autoren des Pakets mit dem Hinweis, dass beim (POSIX)-Thread-Handling beim Beenden eines Threads Race-Conditions auftreten können, erhielt ich innerhalb weniger Stunden die Antwort, dass die Fehler bereits bekannt seien und in einer nächsten Version behoben sein werden.