Sezioni Critiche in C

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

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

Dekker

#include<stdio.h>
#include<stdint.h>
#include<stdlib.h>
#include<sched.h>
#include<pthread.h>
#include<unistd.h>

#define MAX 400
#define STEP 10
#define NPROC 2

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

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

int main(int argc, char *argv[]) {
  uintptr_t i;
  pthread_t t[NPROC];
  srand(time(NULL));
  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("%ld %d\n",val,NPROC*MAX);
}

Peterson

Proviamo con Peterson

#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);
}

La funzione del compilatore C "__sync_synchronize" (che nella macchine Intel genera l'istuzione assembler "__asm__ __volatile__("mfence");") è necessaria per x86 multicore perché altrimenti le cache dei processori potrebbero non essere allineate.

Peterson per N processi

#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);
}

Test&Set

Ora proviamo con test&set (che viene fornito dal compilatore 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);
}

questo funziona bene! (se si decommenta la chiamata (di system call) sched_yield() l'esecuzione è molto pi&ugrave veloce, perché?)

Test&Set fra processi

Ecco il T&S:

#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");
}

• 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".