Esperimenti con semafori e monitor in C

Ho messo a vostra disposizione alcuni sorgenti che implementano in C le astrazioni di semaforo e monitor come le abbiamo viste (o vedremo presto) a lezione.

Ho messo il materiale in questo file.

La directory comprende:

• un Makefile
• tlist.[ch] un modulo di implementazione di liste circolari di thread_id (usate per gestire i processi bloccati). Le liste possono essere usate come code o stack.
• suspend.[ch] è il modulo che implementa la sospensione e riattivazione dei pthread (usando il segnale SIGUSR1).
• semaphore.[ch] implementazione dei semafori fair
• monitor.[ch] implementazione dei monitor (con semantica signal urgent per le variabili di condizione).
• prod_cons.c esempio: produttore consumatore con i semafori
• bounded_buf.c esempio: bounded_buffer con i semafori
• bounded_buf_mon.c esempio: bounded buffer con i monitor
• philo.c: cena dei filosofi (la soluzione è volutamente errata e può generare deadlock)

---

--FedericoB (talk) 11:14, 22 November 2016 (CET)
Ho aggiunto in questo file.

• binsemaphore.[ch] semafori binari implementati senza semafori normali
• dirtybinsemaphore.c semafori binari implementati con semafori normali
• prod_consBin.c problema del produttore-consumatore risolto con solo un semaforo(binario). (warning contiene useless wait)
• dirtysemaphore.c semafori ordinari implementati con semafori binari
• readerWriters.c soluzione del problema lettori-scrittori che abbiamo discusso qui
• semaphoreWithMonitors.c semafori ordinari implementati utilizzando i monitor

Nel makefile ho aggiunto:

• il target prod_consBin e dirtyprod_consBin in cui cambia solo il tipo di semaforo binario linkato.
• il target readerWriters e dirtyreaders_writers in cui cambia solo il tipo di semaforo ordinario linkato.
• il target dirtyPhilo che linka al problema dei filosofi i semafori che utilizzano al loro interno i monitor.

---

Renzo (talk) 09:01, 15 November 2016 (CET)
attenzione: l'implementazione di FedericoB e' un ottimo punto di partenza per la discussione ma non e' corretta, Infatti non rispetta l'invariante dei semafori binari 0 <= nV + Init - nP <= 1. Poniamo infatti Init = 0, e sottoponiamo l'implementazione di Federico alla sequenza V V P V. La prima V porta il semaforo al valore 1, la seconda blocca il chiamante, la P successiva trova il semaforo a 1 quindi non e' bloccante e quindi (codice alla mano) decrementa il semaforo (s->value--) e risveglia il processo bloccato per la seconda V. Il semaforo ora vale zero. L'ultima V non e' quindi bloccante. quindi Init=0, nV=3, nP=1. (Nv + Init - Np) vale quindi 0 + 3 - 1 cioe' 2. Ahi! Dov'e' l'errore?

---

--FedericoB (talk) 10:54, 15 November 2016 (CET)
Ho sistemato creando prima i semafori binari implementati con i semafori normali.
Dopo sono riuscito a sistemare anche i semafori binari senza semafori normali. L'unico difetto è che usano 2 value invece che 1.

---

Renzo (talk) 12:03, 15 November 2016 (CET)
Ancora ottimi spunti di discussione, ma non ancora perfetti.... Prendiamo l'implementazione dei semafori binari con i semafori ordinari e il caso Init 1, V V P P. Per effetto dell'Init sem0 vale 1 e sem 1 vale 0. Il primo V porta sem0 a 2 e il chiamante si ferma su sem1. Il secondo V porta sem0 a 3 e ferma anch'esso il chiamante su sem1. La prima P supera la P su sem0 (che viene portato a 2) fa la V su sem1 (che ora vale 1) ed esce. La seconda P porta sem0 a 1, sem1 a 2 ed esce. Abbiamo lasciato I due processi fermi sulla P(sem1). Prima o poi si sbloccheranno.... ma in questo momento nP (il numero di processi che hanno superato la P) vale 2, nV (il numero di processi che hanno superato la V) e' zero, Init era 1. quindi nV + Init - nP = 0 + 1 - 2 = -1. Ahime'! Come si risolve?

---

--FedericoB (talk) 10:52, 18 November 2016 (CET)
Ho sistemato i semafori binari e ho aggiunto i semafori ordinari implementati con i binari.
Ho tenuto il problema del produttore consumatore con il solo semaforo binario. Funziona ma abbiamo visto che può far aspettare inutilmente il consumatore.

---

S.G (talk) 10:36, 18 November 2016 (CET)
Ho dei dubbi riguardo la seguente parte "La prima P supera la P su sem0 (che viene portato a 2) fa la V su sem1 (che ora vale 1) ed esce". La prima P viene superata, mentre la V su sem1 (verifica che la coda sia vuota, se lo è incrementa di uno il semaforo, altrimenti risveglia un processo) ha in coda alcuni processi, e quindi non dovrebbe incrementare sem1.

---

#include<stdio.h>
#include<pthread.h>
#include "binsemaphore.h"

binsemaphore binSemaphore;
volatile int buffer;

void *producer(void *arg) {
    short int firstTime = 1;
	while (1) {
		int value;
		usleep(random() % 200000);
		value = random() % 32768;
		printf("produced: %d\n",value);
		if (!firstTime) binsemaphore_V(binSemaphore);
        buffer = value;
		printf("sent: %d\n",value);
        binsemaphore_V(binSemaphore);
        firstTime=0;
	}
}

void *consumer(void *arg) {
	while (1) {
		int value;
		printf("\t\tconsumer ready\n");
        binsemaphore_P(binSemaphore);
		value = buffer;
		printf("\t\tconsume %d\n", value);
        binsemaphore_P(binSemaphore);
		usleep(random() % 200000);
	}
}

int main(int argc, char *argv[]) {
	pthread_t prod_t;
	pthread_t cons_t;
    binSemaphore=binsemaphore_create(0);
	srandom(time(NULL));
	pthread_create(&prod_t, NULL, producer, NULL);
	pthread_create(&cons_t, NULL, consumer, NULL);
	pthread_join(prod_t, NULL);
	pthread_join(cons_t, NULL);
}

In questa soluzione del prod_cons con un solo semaforo binario è presente race condition su buffer in quanto non c'è alcuna sicurezza di mutua esclusione nel producer e quindi sia producer che consumer possono accedere al buffer contemporaneamente... Si riesce a patchare oppure non è possibile risolverlo con un solo semaforo 0/1?

uso dei semafori

Se volete fare altri esperimenti con i semafori dovete includere il file semaphore.h nei vostri sorgenti C.

Un semaforo ha tipo semaphore e viene creato in questo modo

semaphore mutex;
mutex = mutex_create(1);

(ovviamente le variabili semaphore devono essere condivise e 1 è solo l'esempio di valore iniziale per un semaforo mutex)

Le operazioni P e V su mutex si scrivono così:

semaphore_P(mutex);
semaphore_V(mutex);

produttore e consumatore

Il file prod_cons.c implementa una soluzione del problema del produttore/consumatore.

Il buffer e i semafori sono definiti come variabili condivise.

semaphore full;
semaphore empty;
volatile int buffer;

Il main inizializza i semafori e crea i thread.

int main(int argc, char *argv[]) {
  pthread_t prod_t;
  pthread_t cons_t;
  full=semaphore_create(0);
  empty=semaphore_create(1);

  pthread_create(&prod_t, NULL, producer, NULL);
  pthread_create(&cons_t, NULL, consumer, NULL);
  pthread_join(prod_t, NULL);
  pthread_join(cons_t, NULL);
}

La sincronizzazione fra produttore e il consumatore viene realizzata come segue:

void *producer(void *arg) {
  while (1) {
    int value;
    // produce value
    semaphore_P(empty);
    buffer = value;
    semaphore_V(full);
  }
}

void *consumer(void *arg) {
  while (1) {
    int value;
    semaphore_P(full);
    value = buffer;
    semaphore_V(empty);
    // consume value
  }
}

Uso dei monitor

Un monitor viene creato con la funzione:

monitor mymon;
mymon = monitor_create()

Le variabili di condizione vengono create nel seguente modo:

condition oktoproceed;
oktoproceed = condition_create(mymon);

(NB: le variabili di condizione sono sempre riferite ad uno specifico monitor).

Le procedure entry sono normali funzioni C ma occorre mettere all'entrata e all'uscita le chiamate monitor_{enter,exit}':

int mymon_dosomething(/* params */) {
  rval int;
  monitor_enter(mymon);
  ....
  monitor_exit(mymon);
  return rval;
}

Le operazioni wait e signal sulle variabili di condizione si scrivono così:

condition_wait(oktoproceed);
condition_signal(oktoproceed);

Bounded buffer con i monitor

Vengono definite come variabili condivise il monitor e le variabili di condizione

monitor bb;
condition ok2write;
condition ok2read;

oltre al buffer e alle variabili per la gestione delle strutture dati, fra le quali il contatore buflen.

Il monitor viene creato da questa funzione:

void bb_create(void) {
  bb = monitor_create();
  ok2write = condition_create(bb);
  ok2read = condition_create(bb);
}

che viene richiamata dal main prima di far partire i thread:

int main(int argc, char *argv[]) {
  pthread_t prod_t;
  pthread_t cons_t;
  bb_create();

  pthread_create(&prod_t, NULL, producer, NULL);
  pthread_create(&cons_t, NULL, consumer, NULL);
  pthread_join(prod_t, NULL);
  pthread_join(cons_t, NULL);
}

Il monitor implementa due procedure entry put e get:

void bb_put(int value) {
  monitor_enter(bb);
  if (buflen >= SIZE)
    condition_wait(ok2write);
  // enqueue value in the buffer
  buflen++;
  condition_signal(ok2read);
  monitor_exit(bb);
}

int bb_get(void) {
  int rval;
  monitor_enter(bb);
  if (buflen <= 0)
    condition_wait(ok2read);
  // dequeue rval from the buffer
  buflen--;
  condition_signal(ok2write);
  monitor_exit(bb);
  return rval;
}

Il codice dei processi produttore e del consumatore usa le procedure entry del monitor bb in questo modo:

void *producer(void *arg) {
  while (1) {
    int value;
    // produce value
    bb_put(value);
  }
}

void *consumer(void *arg) {
  while (1) {
    int value;
    value = bb_get();
    // consume value
  }
}

Semafori implementati con monitor

#include "semaphore.h"
#include "monitor.h"

struct semaphore {
    volatile long value;
    monitor monit;
    condition okToP;
};

semaphore semaphore_create(long initval) {
    struct semaphore* s=malloc(sizeof(semaphore));
    if (s) {
        s->value = initval;
        s->monit = monitor_create();
        s->okToP = condition_create(s->monit);
    }
    return s;
}

void semaphore_destroy(semaphore s) {
    condition_destroy(s->okToP);
    monitor_destroy(s->monit);
    free(s);
}

void semaphore_P(semaphore s) {
    monitor_enter(s->monit);
    if (s->value <=0) condition_wait(s->okToP);
    s->value--;
    monitor_exit(s->monit);
}

void semaphore_V(semaphore s) {
    monitor_enter(s->monit);
    s->value++;
    condition_signal(s->okToP);
    monitor_exit(s->monit);
}

Monitor implementati con semafori

--FedericoB (talk) 10:57, 29 November 2016 (CET) Ho provato a farlo nel seguente modo, ma non funziona. Qualche idea?

#include<stdio.h>
#include "semaphore.h"

#define mutex_in(X) pthread_mutex_lock(X)
#define mutex_out(X) pthread_mutex_unlock(X)

struct urgentStack {
    struct urgentStack *next;
    semaphore sem;
};

struct monitor {
    pthread_mutex_t lock;
    struct urgentStack *urgent;
};

typedef struct monitor *monitor;

struct condition {
    monitor mon;
    int processCount;
    semaphore sem;
};

typedef struct condition *condition;

monitor monitor_create(void) {
    monitor m = malloc(sizeof(*m));
    if (m) {
        pthread_mutex_init(&m->lock, NULL);
        m->urgent = NULL;
    }
    return m;
}

void monitor_destroy(monitor m) {
    pthread_mutex_destroy(&m->lock);
    free(m);
}

void monitor_enter(monitor m) {
    mutex_in(&m->lock);
}

void monitor_exit(monitor m) {
    //if there is a process in the urgent stack
    if (m->urgent != NULL) {
        //remove it from the stack and wake him up before leaving the monitor
        semaphore_V(m->urgent->sem);
        semaphore_destroy(m->urgent->sem);
        struct urgentStack *next = m->urgent->next;
        free(m->urgent);
        m->urgent = next;
        //passing le baton
    } else
        mutex_out(&m->lock);
}

condition condition_create(monitor m) {
    condition c = malloc(sizeof(*c));
    if (c) {
        c->mon = m;
        c->sem = semaphore_create(1);
        c->processCount = 0;
    }
    return c;
}

void condition_destroy(condition c) {
    semaphore_destroy(c->sem);
    free(c);
}

void condition_wait(condition c) {
    c->processCount++;
    monitor_exit(c->mon);
    semaphore_P(c->sem);
}

void condition_signal(condition c) {
    if (c->processCount > 0) {
        monitor monitor = c->mon;
        struct urgentStack *top = monitor->urgent;
        struct urgentStack *new = malloc(sizeof(struct urgentStack));
        new->sem = semaphore_create(1);
        new->next = top;
        monitor->urgent = new;
        semaphore_V(c->sem);
        semaphore_P(new->sem);
    }
}