View source for Dekker, Peterson e Test&Set in C

Tutti questi esempi hanno NPROC thread che svolgono un loop MAX volte sommando 1 ad ogni iterazione ad una variabile globale condivisa var;

Se tutto va bene il risultato finale deve essere NPROC*MAX.

== Senza sezioni critiche ==

Partiamo dall'esempio *SENZA* sezioni critiche e quindi errato perhc&eacute; ha una race condition:
<syntaxhighlight lang=C>
#include<stdio.h>
#include<stdint.h>
#include<pthread.h>
#include<unistd.h>

#define MAX 4000000
#define STEP 1000000
#define NPROC 4

volatile long val = 0;

void *codet(void *arg) {
        uintptr_t id = (uintptr_t) arg;
        int count;
        for (count=0; count  < MAX; count++) {
                /* enter */
                /* /enter */
                val = val + 1;
                if (count % STEP == 0)
                        printf("%d %ld\n",id,val);
                /* exit */
                /* /exit */
        }
}

int main(int argc, char *argv[]) {
        uintptr_t i;
        pthread_t t[NPROC];
        for (i=0; i<NPROC; i++)
                pthread_create(&t[i], NULL, codet, (void *) i);
        for (i=0; i<NPROC; i++)
                pthread_join(t[i], NULL);
        printf("%d %d\n",val,NPROC*MAX);
}
</syntaxhighlight>

== Test&Set ==

Ora proviamo con test&set (che viene fornito dal compilatore C)
<syntaxhighlight lang=C>
#include<stdio.h>
#include<stdint.h>
#include<pthread.h>
#include<unistd.h>
#include<sched.h>

#define MAX 4000000
#define STEP 1000000
#define NPROC 4

volatile long val = 0;
volatile long lock = 0;

void *codet(void *arg) {
  uintptr_t id = (uintptr_t) arg;
  int count;
  for (count=0; count  < MAX; count++) {
    /* enter */
    while (__sync_lock_test_and_set(&lock,1))
      /*sched_yield()*/;
    /* /enter */
    val = val + 1;
    if (count % STEP == 0)
      printf("%d %ld\n",id,val);
    /* exit */
    __sync_lock_release(&lock);
    /* /exit */
  }
}

int main(int argc, char *argv[]) {
  uintptr_t i;
  pthread_t t[NPROC];
  for (i=0; i<NPROC; i++)
    pthread_create(&t[i], NULL, codet, (void *) i);
  for (i=0; i<NPROC; i++)
    pthread_join(t[i], NULL);
  printf("%d %d\n",val,NPROC*MAX);
}
</syntaxhighlight>
questo funziona bene!
(se si decommenta la chiamata (di system call) sched_yield() l'esecuzione &egrave; molto pi&ugrave veloce, perch%eacute;?)

== Peterson ==
Proviamo con Peterson
<syntaxhighlight lang=C>
#include<stdio.h>
#include<stdint.h>
#include<pthread.h>
#include<unistd.h>

#define MAX 4000000
#define STEP 1000000
#define NPROC 2

volatile long val = 0;
volatile long need[NPROC];
volatile long turn;

void *codet(void *arg) {
  uintptr_t id = (uintptr_t) arg;
  int count;
  for (count=0; count  < MAX; count++) {
    /* enter */
    need[id] = 1;
    turn = 1 - id;
    __sync_synchronize();
    while (need[1 - id] && turn != id)
      ;
    /* /enter */
    val = val + 1;
    if (count % STEP == 0)
      printf("%d %ld\n",id,val);
    /* exit */
    need[id] = 0;
    /* /exit */
  }
}

int main(int argc, char *argv[]) {
  uintptr_t i;
  pthread_t t[NPROC];
  for (i=0; i<NPROC; i++)
    pthread_create(&t[i], NULL, codet, (void *) i);
  for (i=0; i<NPROC; i++)
    pthread_join(t[i], NULL);
  printf("%d %d\n",val,NPROC*MAX);
}
</syntaxhighlight>
La funzione del compilatore C "__sync_synchronize" (che nella macchine Intel genera l'istuzione assembler "__asm__ __volatile__("mfence");") &egrave; necessaria per x86 multicore perch&eacute; altrimenti le cache dei processori potrebbero non essere allineate.

== Dekker ==
E ora Dekker. 
<syntaxhighlight lang=C>
#include<stdio.h>
#include<stdint.h>
#include<pthread.h>
#include<unistd.h>

#define MAX 4000000
#define STEP 1000000
#define NPROC 2

volatile long val = 0;
volatile long need[NPROC];
volatile long turn;

void *codet(void *arg) {
  uintptr_t id = (uintptr_t) arg;
  int count;
  for (count=0; count  < MAX; count++) {
    /* enter */
    need[id] = 1;
    __sync_synchronize();
    while (need[1 - id]) {
      __sync_synchronize();
      need[id] = 0;
      while (need[1 - id] && turn != id)
        ;
      need[id] = 1;
      __sync_synchronize();
    }
    /* /enter */
    val = val + 1;
    if (count % STEP == 0)
      printf("%d %ld\n",id,val);
    /* exit */
    need[id] = 0;
    turn = 1 - id;
    /* /exit */
  }
}

int main(int argc, char *argv[]) {
  uintptr_t i;
  pthread_t t[NPROC];
  for (i=0; i<NPROC; i++)
    pthread_create(&t[i], NULL, codet, (void *) i);
  for (i=0; i<NPROC; i++)
    pthread_join(t[i], NULL);
  printf("%d %d\n",val,NPROC*MAX);
}
</syntaxhighlight>
(Qui sono state necessari epi&ugrave; istruzioni "siepe" fence)

== Peterson per N processi ==
<syntaxhighlight lang=C>
#include<stdio.h>
#include<stdint.h>
#include<pthread.h>
#include<unistd.h>

#define MAX 4000000
#define NPROC 4

volatile long val = 0;
volatile long turn;
volatile long stage[NPROC];
volatile long last[NPROC];

void *codet(void *arg) {
  uintptr_t id = (uintptr_t) arg;
  int count;
  int j, k;
  for (count=0; count  < MAX; count++) {
    /* enter */
    for (j=0; j<NPROC; j++) {
      stage[id] = j+1; last[j] = id;
      __sync_synchronize();
      for (k=0; k<NPROC; k++) {
        if (id != k)
          while (stage[k] >= stage[id] && last[j] == id)
            ;
      }
    }
    /* /enter */
    val = val + 1;
    if ((count & ((1<<20) - 1)) == 0)
      printf("%d %ld\n",id,val);
    /* exit */
    stage[id] = 0;
    /* /exit */
  }
}

int main(int argc, char *argv[]) {
  uintptr_t i;
  pthread_t t[NPROC];
  for (i=0; i<NPROC; i++)
    pthread_create(&t[i], NULL, codet, (void *) i);
  for (i=0; i<NPROC; i++)
    pthread_join(t[i], NULL);
  printf("%d %d\n",val,NPROC*MAX);
}
</syntaxhighlight>

= Thread o Processi? =

Gli esempi qui sopra sono stati costruiti con la libreria pthread che consente di creare thread (cio&eacute; strutture concorrenti all'interno del processo, che condividono tutte le risorse tranne quelle necessarie per avere una esecuzione indipendente, i.e. stato del processore e stack).
&Egrave; anche possibile ripetere gli esperimenti usando processi separati che condividano un'area di memoria. Pi&ugrave; avanti nel corso vedremo in dettaglio il significato delle funzioni e system call usate nell'esempio seguente.

== Test&Set fra processi ==

Ecco il T&S:
<syntaxhighlight lang=C>
#include<stdio.h>
#include<fcntl.h>
#include<stdlib.h>
#include<unistd.h>
#include<sched.h>
#include <sys/mman.h>

#define MAX 400000000
#define STEP 1000000

volatile int *shared;
#define val shared[0]
#define lock shared[1]

void *create_shmem(char *name, off_t length) {
  int shmfd = shm_open(name, O_CREAT|O_RDWR, 0600);
  ftruncate(shmfd,length);
  return mmap(NULL, length, PROT_READ|PROT_WRITE, MAP_SHARED, shmfd, 0);
}

int destroy_shmem(char *name) {
  return shm_unlink(name);
}

int main(int argc, char *argv[]) {
  shared = create_shmem("test", 3*sizeof(int));
  int count;
  for (count = 0; count < MAX; count ++) {
    /* enter */
    while (__sync_lock_test_and_set(&lock,1))
      sched_yield();
    /* /enter */
    val = val + 1;
    if (count % STEP == 0)
      printf("%ld\n",val);
    /* exit */
    __sync_lock_release(&lock);
    /* /exit */
  }
  printf("%d\n",val);

  destroy_shmem("test");
}
</syntaxhighlight>

* shm_create e shm_unlink sono definite nella libreria librt
* lanciate questo programma da piu' terminali virtuali
* se bloccate l'esecuzione puo' rimane definita l'area di memoria condivisa. se quando avete "ucciso" il processo lock valeva 1, il programma non funzionera' piu'. In GNU-Linux le aree di memoria condivisa sono visibili nel file system nella directory "/dev/shm", quindi occorre cancellare lo pseudo-file "/dev/shm/test".