En pthreadimplementasjon av Donald Knuths vennlige troll med lamper i den ene neven

Her er en enda eldre utgave av Donald Knuths vennlige troll med lamper i den ene neven. Fila var opprinnelig datert 31. desember 2002.

Her er link til artikkelen: http://www-cs-faculty.stanford.edu/~knuth/papers/p160.ps.gz.

/*
 troll.c -- En pthreadimplementasjon av Donald Knuths
            vennlige troll med lamper i den ene neven.

 Se Donald E. Knuth og Frank Ruskeys artikkel som tidligere het
 "Deconstructing Coroutines", men som nå har fått tittelen
 "Efficient Coroutine Generation of Constrained Gray Sequences".
 Artikkelen er tilgjengelig på:
 http://www-cs-faculty.stanford.edu/~knuth/papers/p160.ps.gz.

 Copyright © 2002 Trond Endrestøl <Trond.Endrestol@ximalas.info>

 This program is free software; you can redistribute it and/or modify
 it under the terms of the GNU General Public License as published by
 the Free Software Foundation; either version 2 of the License, or
 (at your option) any later version.

 This program is distributed in the hope that it will be useful,
 but WITHOUT ANY WARRANTY; without even the implied warranty of
 MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the
 GNU General Public License for more details.

 You should have received a copy of the GNU General Public License
 along with this program; if not, write to the Free Software
 Foundation, Inc., 59 Temple Place - Suite 330, Boston,
 MA 02111-1307, USA.
*/
#include <sys/time.h>

#include <pthread.h>
#include <stdio.h>
#include <unistd.h>

#ifndef N
#define N 8
#endif

enum bool_t { false, true } Vaken[N], Lampe[N];
pthread_mutex_t MutEx = PTHREAD_MUTEX_INITIALIZER;
pthread_cond_t Cond[N], CondMain = PTHREAD_COND_INITIALIZER;

/* Ting og tang i forbindelse med tidsstempling. */
struct timeval Starttid;
pthread_once_t OnceInitTiming = PTHREAD_ONCE_INIT;

void InitTiming(void)
{
  gettimeofday(&Starttid, NULL);
} /* InitTiming */

double Timing(void)
{
  struct timeval MinTid;
  double Tidsstempel;

  pthread_once(&OnceInitTiming, InitTiming);

  gettimeofday(&MinTid, NULL);

  Tidsstempel = MinTid.tv_sec + (MinTid.tv_usec / 1.0E6);
  Tidsstempel -= Starttid.tv_sec + (Starttid.tv_usec / 1.0E6);

  /* Bruk formatet %.6f eller %.6g
     siden presisjonen bare er i hele mikrosekunder. */

  return Tidsstempel;
} /* Timing */

void SkrivStatus(void)
{
  size_t i;
  double Tidsstempel = Timing();

  /* Skrive ut status for hvert troll. */
#if 0 /* Skrive ut trollene forlengs. */
  for (i = 0; i < N; i++) {
    printf("Troll(%lu):%.6f: %s, lampa er %s\n",
           i,
           Tidsstempel,
           (Vaken[i]) ? "våken" : "sover",
           (Lampe[i]) ? "på"    : "av");
    } /* for */
#else /* Skrive ut trollene baklengs. */
  i = N - 1;
  do {
    printf("Troll(%lu):%.6f: %s, lampa er %s\n",
           i,
           Tidsstempel,
           (Vaken[i]) ? "våken" : "sover",
           (Lampe[i]) ? "på"    : "av");
    } while (i--); /* do-while */
#endif

  /* Skrive ut en vakker skillelinje. */
  puts("----");

  /* Tvinge buffret output på stdout ut på skjermen. */
  fflush(stdout);
} /* SkrivStatus */

void *Troll(void *Argument)
{
  size_t i = (size_t)Argument; /* Jeg er Troll(i). */

  pthread_mutex_lock(&MutEx); /* Låse mutexen. */

  pthread_cond_signal(&CondMain); /* Signalere main(). */

  while (1) {
    /* Vente på signal fra Troll(i + 1) eller fra main(). */
    pthread_cond_wait(&Cond[i], &MutEx);

    if (Vaken[i]) { /* Jeg er våken. */
      Lampe[i] = !Lampe[i]; /* Skru på eller av lampa. */
      Vaken[i] = false; /* Sovne på grunn av overanstrengelse. */

      /* Mirakuløst klarer likevel dette trollet å fortelle
         omverdenen om tilstanden til alle trollene. */
      SkrivStatus();

      /* Signalere main(). */
      pthread_cond_signal(&CondMain);
      } /* if */
    else { /* Jeg sover. */
      Vaken[i] = true; /* Våkne opp. */

      if (i != 0) { /* Signalere naboen med mindre jeg er Troll(0). */
        pthread_cond_signal(&Cond[i - 1]);
        } /* if */
      else { /* Skrive status og signalere main() siden jeg er Troll(0). */
        SkrivStatus();
        pthread_cond_signal(&CondMain);
        } /* else */
      } /* else */
    } /* while */

  /* NOTREACHED */
  return NULL;
} /* Troll */

int main(void)
{
  size_t i;
  pthread_t tID;

  /* Låse mutexen. */
  pthread_mutex_lock(&MutEx);

  /* Initialisere arrayene og opprette trollene.
     I utgangspunktet er hvert troll våken og lampene er slått av. */
  for (i = 0; i < N; i++) {
    Vaken[i] = true;
    Lampe[i] = false;
    Cond[i] = PTHREAD_COND_INITIALIZER;

    pthread_create(&tID, NULL, Troll, (void *)i);
    pthread_cond_wait(&CondMain, &MutEx);
    } /* for */

  /* Skrive ut den innledende tilstanden til trollene. */
  SkrivStatus();

  /* Holde simuleringen i gang. */
  while (1) {
    /* Signalere Troll(N - 1). */
    pthread_cond_signal(&Cond[N - 1]);

    /* Vente på signal fra det siste trollet i hver omgang. */
    pthread_cond_wait(&CondMain, &MutEx);

    /* Sove litt, ellers rekker vi ikke å følge med på skjermen. */
    sleep(1);
    } /* while */

  /* NOTREACHED */
  return 0;
} /* main */

/* troll.c */