Esperimenti con message passing in C
Ho messo a vostra disposizione alcuni sorgenti che implementano in C le astrazioni di message passing sincrono, asincrono e completamente asincrono come le abbiamo viste (o vedremo presto) a lezione.
Ho messo il materiale in questo file.
La directory comprende:
- un Makefile
- suspend.[ch] è il modulo che implementa la sospensione e riattivazione dei pthread (usando il segnale SIGUSR1).
- msg.[ch] modulo di implementazione dei paradigmi di message passing.
- sender.c receiver.c: esempi di processi che si scambiano un messaggio (sender manda a receiver che risponde).
IL file msg.h spiega come usare i servizi forniti da questi sorgenti.
Per iniziare occorre dare il nome al processo durante l'inizializzazione del servizio:
void async_msg_init(char *procname);
void sync_msg_init(char *procname);
void nb_msg_init(char *procname);
IL tipo di servizio (sincrono, asincrono o completamente asincrono) viene deciso al momento della inizializzazione e non puo' piu' essere cambiato.
Per spedire un messaggio basta indicare il nome del destinatario, il buffer contenente il messaggio e la lunghezza in byte del messaggio.
ssize_t msg_send(char *dest, const void *buf, size_t len);
L'interfaccia e' simile alla system call "write" ma al posto del file descriptor c'e' il nome del destinatario. E' possibile inviare messaggi vuoti (di solito servono per indicare un acknowledgement. Al momento della spedizione il processo destinatario deve esistere, altrimenti la funzione ritorna errore. In caso di successo la funzione restituisce ilnumero di byte inviati, -1 un caso di errore.
Per ricevere un messaggio si usa la funzione msg_receive:
ssize_t msg_recv(char *sender, void *buf, size_t len);
Il campo sender può essere:
- una stringa: in questo caso viene ricevuto il primo messaggio spedito dal mittente indicato
- NULL: viene consegnato il primo messaggio ricevuto qualsiasi ne sia stato il mittente
- una variabile di tipo msg_procname con il primo byte zero (una stringa vuota di dimensione adeguata): viene consegnato il primo messaggio ricevuto qualsiasi ne sia stato il mittente e il nome del mittente viene salvato nella variabile sender.
aggiornamento Dec. 6 2016
E' stata aggiunta una funzione per ottenere il proprio nome.
void msg_myname(char *myname);
(il parametro deve essere di tipo msg_procname per essere certi che il nome non sia più lungo del buffer).
La costante MAXLEN indica la massima lunghezza dei messaggi che la libreria gestisce.
Il makefile ha ora un parametro opzionale per la compilazione dei test/tutorial "receiver" e "sender".
make clean; make MPTYPE=async make clean; make MPTYPE=sync make clean; make MPTYPE=nb
generano gli eseguibili di esempio per i vari paradigmi di message passing. Lanciando da due shell diverse (e.g. due finestre terminale) prima receiver in una e poi sender nell'altra si potranno osservare le stampe dei due programmi.
aggiornamento Dec. 9 2016
Ho aggiunto questo file che contiene gli esempi di implementazione di message passing asincrono dato quello sincrono (con server) e message passing completamente asincrono dato quello sincrono.
Dining philosophers con message passing
Soluzione senza gestore delle bacchette
In questa soluzione non c'è un gestore delle bacchette a cui richiederne l'uso ma i filosofi si scambiano direttamente messaggi per accordarsi.
Essendo la libreria del message passing non attualmente thread safe ho implementato la soluzione utilizzando un processo per ogni filoso.
C'è un programma chiamato startPhilos che tramite fork() e exec() esegue i filosofi. StartPhilos assegna anche le bacchette iniziali tramite parametri, io ho seguito la regola che viene assegnata la bacchetta sempre al filosofo con id minore tra i 2 filosofi che potrebbero avere quella bacchetta. In realtà qualsiasi ordine è accettabile, a parte quello in cui si impone una situazione di deadlock.
Ogni stick ha 3 stati: without(il filosofo ha bisogno della bacchetta), clean e dirty. Se a un filosofo manca una bacchetta la richiede al vicino.
Quando a un filosofo viene chiesta una bacchetta la cede solo è sporca, ma la pulisce prima di consegnarla.
Un filosofo mangia solo se ha 2 bacchette pulite, dopo aver mangiato le bacchette sono sporche.
A seguito il ciclo principale della vita di un filosofo:
while (1) {
//think
usleep(random() % 2000000);
//request right stick if the philosopher doesn't have it
if (rightStick == without) {
msg_send(rightPhilo, "request", 8);
}
//request left stick if the philosopher doesn't have it
if (leftStick == without) {
msg_send(leftPhilo, "request", 8);
}
//read messages from everyone
msg_procname philo = "";
while (msg_recv(philo, buffer, 8) > 0) {
if (strcmp(buffer, "ok") == 0) {
if (strcmp(philo, rightPhilo) == 0) {
//a received stick is always clean
rightStick = clean;
} else if (strcmp(philo, leftPhilo) == 0) {
//a received stick is always clean
leftStick = clean;
}
} else if (strcmp(buffer, "request") == 0) {
//philosophers give up sticks only if they are dirty
if ((strcmp(philo, rightPhilo) == 0) && (rightStick == dirty)) {
rightStick = without;
msg_send(rightPhilo, "ok", 3);
}
if ((strcmp(philo, leftPhilo) == 0) && (leftStick == dirty)) {
leftStick = without;
msg_send(leftPhilo, "ok", 3);
}
}
}
//if a philosopher have 2 clean stick he can start eating
if (leftStick == clean && rightStick == clean) {
//eating
usleep(random() % 2000000);
//endeat
//the sticks are dirty after eating.
leftStick = dirty;
rightStick = dirty;
}
}
Potete trovare un archivio con i sorgenti completi e commentati e makefile qui.
Questa soluzione oltre al deadlock risolve anche il problema della starvation in quanto il meccanismo bacchetta sporca/pulita obbliga un filosofo a cedere la bacchetta dopo aver mangiato e perciò consentire ai vicini di mangiare.
Ho utilizzato il modello completamente asincrono ma senza busy wait in quanto i filosofi tra un tentativo e l'altro di ottenere la bacchetta si mettono a pensare.
Questa soluzione è stata ideata in origine da K. Mani Chandy and J. Misra nel 1984.
--FedericoB (talk) 22:06, 10 December 2016 (CET)