Verständnisprobleme bei einer Semaphoren-Implementierung

Harrison Bergeron

Hallo,

ich lese gerade das Buch The Little Book of Semaphores http://greenteapress.com/semaphores/. Es geht, wie der Titel schon sagt, um Semaphoren. Teil des Buches ist eine Semaphoren-Implementierung in C (s.u.).

Verständnisprobleme habe ich mit der Variablen wakeups. Im Buch heißt es dazu:

wakeups counts the number of pending signals; that is, the number of threads that have been woken but have not yet resumed execution. The reason for wakeups is to make sure that our semaphores have Property 3, described in Section 4.3.

Property 3 soll, soweit habe ich es hoffentlich verstanden, sicherstellen, dass einer der wartenden Threads den Mutex bekommt. Es soll verhindert werden, dass ein Thread immer wieder den Mutex bekommt und so die wartenden Threads verhungern.

Was ich nicht verstehe: Wie wird das mit wakeups gewährleistet? Könnte es nicht trotz der Variable passieren, dass ein nicht-wartender Thread den Mutex immer wieder bekommt?

Ich wäre über ein paar erklärende Sätze sehr dankbar.

typedef struct {
  int value, wakeups;
  Mutex *mutex;
  Cond *cond;
} Semaphore;

Semaphore *make_semaphore (int value)
{
  Semaphore *semaphore = check_malloc (sizeof(Semaphore));
  semaphore->value = value;
  semaphore->wakeups = 0;
  semaphore->mutex = make_mutex ();
  semaphore->cond = make_cond ();
  return semaphore;
}

void sem_wait (Semaphore *semaphore)
{
  mutex_lock (semaphore->mutex);
  semaphore->value--;

  if (semaphore->value < 0) {
    do {
      cond_wait (semaphore->cond, semaphore->mutex);
    } while (semaphore->wakeups < 1);
    semaphore->wakeups--;
  }
  mutex_unlock (semaphore->mutex);
}

void sem_signal (Semaphore *semaphore)
{
  mutex_lock (semaphore->mutex);
  semaphore->value++;

  if (semaphore->value <= 0) {
    semaphore->wakeups++;
    cond_signal (semaphore->cond);
  }
  mutex_unlock (semaphore->mutex);
}

Frohes Fest!

Wutz

Ich glaube, deine Frage ist wohl hier etwas zu speziell und ohne konkrete Erfahrung mit der erwähnten Implementierung nur was für Leute mit viel Zeit und Lust.

Harrison Bergeron

Ja, mag sein. Da das Buch kostenlos als PDF verfügbar ist, dachte ich jemand würde sich vielleicht dafür interessieren.

Ich habe mir die Frage mittlerweile selbst beantwortet. Der Autor ist an der Stelle etwas ungenau. Die Variable garantiert Property 3 gar nicht. wakeups sorgt nur dafür, dass nicht mehr Threads weiterlaufen als Signale gegeben wurden.

_--

http://de.wikipedia.org/wiki/Semaphor_(Informatik)#L.C3.B6sung_von_Dijkstra
evtl. ist die wiki erklärung besser? zaehler sollte dann wakeups sein, oder?

Harrison Bergeron

Ich glaube zaehler ist die Variable value im Code aus dem Buch. Dijkstra hatte wakeups nicht vorgesehen. Soweit ich es verstanden habe, ist wakeups ein Hilfsvariable um Semaphore mit POSIX zu implementieren.