ピーターソンのアルゴリズム

/*  * ANSI C89 source, KNF style implementation of Peterson's Algorithm.  *  * Copyright (c) 2005, Matthew Mondor  * Released in the public domain (may be licensed under the GFDL).  *  * Please fix any bugs as needed, preserving the KNF style and this comment,  * unless considered inconvenient in which case you can do whatever you want  * with the code.  */  #include <assert.h> #include <stdio.h> #include <stdlib.h> #include <pthread.h>  struct pa_desc {         int     *f0, *f1;         int     last; };  void    pa_init(void); void    pa_desc_init(struct pa_desc *, int); void    pa_desc_lock(struct pa_desc *); void    pa_desc_unlock(struct pa_desc *);  void    *thread0_main(void *); void    *thread1_main(void *); void    threadx_critical(void);  int     main(int, char **);  static int      pa_f0, pa_f1, pa_last;  /* Shared */ #define BUCKETS 100 int             gi, g[BUCKETS];  /*  * Initializes the pa system.  To be called by the process once before  * initializing pa descriptors.  */ void pa_init(void) {          pa_f0 = pa_f1 = pa_last = 0; }  /*  * Initializes a pa descriptor for use by a thread.  * One thread should use id 0 and the other one id 1.  */ void pa_desc_init(struct pa_desc *d, int id) {          assert(id == 0 || id == 1);          if (id == 0) {                 d->f0 = &pa_f0;                 d->f1 = &pa_f1;                 d->last = 1;         } else if (id == 1) {                 d->f0 = &pa_f1;                 d->f1 = &pa_f0;                 d->last = 0;         } }  void pa_desc_lock(struct pa_desc *d) {          for (*d->f0 = 1, pa_last = d->last;             *d->f1 == 1 && pa_last == d->last; ) ; }  void pa_desc_unlock(struct pa_desc *d) {          *d->f0 = 0; }  /*  * Main loop of the first concurrent thread  */ /* ARGSUSED */ void * thread0_main(void *args) {         struct pa_desc  d;          pa_desc_init(&d, 0);          for (;;) {                 pa_desc_lock(&d);                 threadx_critical();                 pa_desc_unlock(&d);         }          /* NOTREACHED */         return NULL; }  /*  * Main loop of the second concurrent thread  */ /* ARGSUSED */ void * thread1_main(void *args) {         struct pa_desc  d;          pa_desc_init(&d, 1);          for (;;) {                 pa_desc_lock(&d);                 threadx_critical();                 pa_desc_unlock(&d);         }          /* NOTREACHED */         return NULL; }  /*  * Critical function which would normally have concurrency issues if two  * threads executed it without locking.  */ void threadx_critical(void) {         int     i;          /* Do something which would normally have dual concurrency issues */         for (i = 0; i < BUCKETS; i++)                 g[i] = gi++;         for (i = 0; i < BUCKETS; i++)                 (void) printf("g[%d] = %d\n", i, g[i]); }  /*  * Test program which demonstrates that dual concurrency can be achieved  * without locking using Peterson's algorithm.  We run two concurrent threads  * which voluntarily perform concurrency sensitive operations on a shared  * memory region (gi, g[BUCKETS]).  */ /* ARGSUSED */ int main(int argc, char **argv) {         pthread_t       tid1, tid2;         pthread_attr_t  tattr;          gi = 0;         pa_init();          pthread_attr_init(&tattr);         pthread_attr_setdetachstate(&tattr, 0);          /* Note: a real application would perform error checking */         pthread_create(&tid1, &tattr, thread0_main, NULL);         pthread_create(&tid2, &tattr, thread1_main, NULL);          pthread_join(tid1, NULL);         pthread_join(tid2, NULL);         /* NOTREACHED */          return EXIT_SUCCESS; }