Difference between revisions of "Zibaldone"

From Sistemi Operativi
Jump to navigation Jump to search
(Aggiunta possibile soluzione)
 
(35 intermediate revisions by 5 users not shown)
Line 1: Line 1:
 +
== Monitor: Ponte a senso Unico ==
 +
Proposta di soluzione: esercizio 1 esame 22/01/2014
 +
<syntaxhighlight lang=C>
 +
//
 +
//  20140122_bridge
 +
//
 +
/*  Esercizio c.1:
 +
*
 +
*  Per colpa delle frane un ponte veicolare e' rimasto danneggiato.
 +
*  I veicoli possono ora percorrerlo solo in senso unico alternato e, per non eccedere la portata,
 +
*  al piu' ci possono essere sul ponte N veicoli contemporaneamente.
 +
*  Scrivere il monitor bridge sapendo che i veicoli chiameranno il monitor prima di entrare nel
 +
*  ponte e dopo averlo attraversato.
 +
*  I veicoli che entrano dal lato est escono dal lato ovest e viceversa.
 +
*  Quindi i (numerosi) veicoli eseguiranno uno dei due frammenti di codice seguenti:
 +
*
 +
*
 +
*  bridge.enter(E)                      bridge.enter(W)
 +
*  //cross the bridge                  //cross the bridge
 +
*  bridge.exit(W)                      bridge.exit(E)
 +
*
 +
*
 +
*  La soluzione proposta deve evitare deadlock e deve essere efficiente.
 +
*  (controesempio: una soluzione che prevedesse l'attraversamento del ponte da parte di un solo veicolo alla volta
 +
*  sebbene rispetti tutti i vincoli sarebbe considerata errata poiche' inefficiente).
 +
*  Oltre al codice si richiede una descrizione degli accorgimenti adottati per rendere la soluzione efficiente.
 +
*/
 +
 +
#include <stdio.h>
 +
#include "monitor.h"
 +
 +
#define CAPACITY 7 //capacità del bridge
 +
#define BALANCE 9 
 +
#define NCAR 15
 +
 +
enum dest{
 +
    E = 0,
 +
    W = 1
 +
};
 +
 +
int ncrossing_we = 0; //n car che stanno attraversando il bridge da W->E
 +
int ncrossing_ew = 0; //n car che stanno attraversando il bridge da E->W
 +
 +
int nwaiting_we = 0; //n car che aspettano di attraversare da W->E
 +
int nwaiting_ew = 0;  //n car che aspettano di attraversare da E->W
 +
 +
int priority = BALANCE;
 +
 +
int crossed_we = 0; //n volte che il ponte è stato attraversato da W->E
 +
int crossed_ew = 0; //n volte che il ponte è stato attraversato da E->W
 +
 +
condition ok2goW; // capacity > 0 && (ncrossing_ew == 0 || priority > 0)
 +
condition ok2goE; // capacity > 0 && (ncrossing_we == 0 || prioriti > 0 )
 +
monitor bridge;
 +
 +
void bridge_create(void){
 +
    bridge = monitor_create();
 +
    ok2goW = condition_create(bridge);
 +
    ok2goE = condition_create(bridge);
 +
}
 +
 +
void bridge_enter(enum dest d){
 +
    monitor_enter(bridge);
 +
    if (d == W) {
 +
        nwaiting_we++;
 +
        if (ncrossing_we >= CAPACITY || ncrossing_ew > 0 || (nwaiting_ew > 0 && priority <= 0)) {
 +
            condition_wait(ok2goW);
 +
        }
 +
        priority--;
 +
        nwaiting_we--;
 +
        ncrossing_we++;
 +
        if (ncrossing_we < CAPACITY && priority > 0) {
 +
            condition_signal(ok2goW);
 +
        }
 +
    }else if(d == E){
 +
        nwaiting_ew++;
 +
        if (ncrossing_ew >= CAPACITY || ncrossing_we > 0 || (nwaiting_we > 0 && priority <= 0)){
 +
            condition_wait(ok2goE);
 +
        }
 +
        priority--;
 +
        nwaiting_ew--;
 +
        ncrossing_ew++;
 +
        if (ncrossing_ew < CAPACITY && priority > 0) {
 +
            condition_signal(ok2goE);
 +
        }
 +
    }
 +
    monitor_exit(bridge);
 +
}
 +
 +
void bridge_exit(enum dest d){
 +
    monitor_enter(bridge);
 +
    if (d == E) {
 +
        ncrossing_we--;
 +
        crossed_we++;
 +
        if (ncrossing_we < CAPACITY && nwaiting_we > 0 && (nwaiting_ew == 0 || priority > 0)) {
 +
            condition_signal(ok2goW);
 +
        }else if (ncrossing_we == 0 && nwaiting_ew > 0 ) {
 +
            priority = BALANCE;
 +
            condition_signal(ok2goE);
 +
        }
 +
    } else if (d == W){
 +
        ncrossing_ew--;
 +
        crossed_ew++;
 +
        if (ncrossing_ew < CAPACITY && nwaiting_ew > 0 && (nwaiting_we == 0 || priority > 0)) {
 +
            condition_signal(ok2goE);
 +
        }else if (ncrossing_ew == 0 && nwaiting_we > 0) {
 +
            priority = BALANCE;
 +
            condition_signal(ok2goW);
 +
        }
 +
    }
 +
    monitor_exit(bridge);
 +
}
 +
 +
void *crossEW(void* arg){
 +
    while (1) {
 +
        printf("waitW: %d |-|%d|->  <-|%d|-| waitE: %d  || crossed W->E: %d crossed E->W: %d||\n", nwaiting_we, ncrossing_we, ncrossing_ew, nwaiting_ew, crossed_we, crossed_ew);
 +
        usleep(random() % 200000);
 +
        bridge_enter(E);
 +
        usleep(random() % 20000);
 +
        bridge_exit(W);
 +
    }
 +
}
 +
 +
void *crossWE(void* arg){
 +
    while (1) {
 +
        printf("waitW: %d |-|%d|->  <-|%d|-| waitE: %d  || crossed W->E: %d crossed E->W: %d||\n", nwaiting_we, ncrossing_we, ncrossing_ew, nwaiting_ew, crossed_we, crossed_ew);
 +
        usleep(random() % 200000);
 +
        bridge_enter(W);
 +
        usleep(random() % 20000);
 +
        bridge_exit(E);
 +
    }
 +
}
 +
 +
int main(int argc, const char * argv[]) {
 +
    pthread_t e_w_t[NCAR];
 +
    pthread_t w_e_t[NCAR];
 +
    bridge_create();
 +
 +
    srandom(time(NULL));
 +
    for (int i = 0; i < NCAR; i++) {
 +
        pthread_create(&e_w_t[i], NULL, crossEW, NULL);
 +
        pthread_create(&w_e_t[i], NULL, crossWE, NULL);
 +
 +
    }
 +
    for (int i = 0; i < NCAR; i++) {
 +
        pthread_join(w_e_t[i], NULL);
 +
        pthread_join(e_w_t[i], NULL);
 +
    }
 +
    return 0;
 +
}
 +
</syntaxhighlight>
 +
 +
 +
Dal testo dell'esercizio si evincono le seguenti condizioni basilari per poter attraversare il ponte:
 +
<syntaxhighlight lang=C>
 +
  (capacità>0 && ncrossing_OppositeDirection == 0)
 +
</syntaxhighlight>
 +
 +
Per rendere la soluzione efficiente ho introdotto, così, la variabile priority settata al valore BALANCE ottenendo la seguente condizione:
 +
<syntaxhighlight lang=C>
 +
priority > 0 || nwaitingOppositeDirection == 0;
 +
</syntaxhighlight>
 +
 +
e.i. fin quando il mio senso (e.g. W->E) ha ancora priorità di attraversare  O non ci sono macchine nella
 +
direzione opposta che attendono, continuo a dare il via alle macchine che vanno nella mia stessa direzione.
 +
Priority viene decrementata ad ogni macchina che attraversa il ponte.
 +
 +
Non appena tale condizione viene interrotta, priority viene restaurata al valore BALANCE e la sua gestione viene ceduta al senso opposto.
 +
Notare che anche questa soluzione non gestisce il caso in cui "il mio senso ha priorità ma non c'è nessuno che vuole attraversare",
 +
sarebbe inutile far attendere e maccchine della direzione opposta.
 +
Allora il tutto viene gestito come segue:
 +
 +
<syntaxhighlight lang=C>
 +
  bridge.enter()
 +
    if (ncrossing_MyDirection <= CAPACITY && ncrossing_OppositeDirection == 0 && (mypriority > 0 || nwaitingOppositeDirection == 0)){
 +
attraverso il ponte;
 +
    }
 +
</syntaxhighlight>
 +
 +
<syntaxhighlight lang=C>
 +
    bridge.exit()
 +
if (ncrossing_MyDirection < CAPACITY && nwaiting_MyDirection > 0 && (nwaiting_OppositeDirection == 0 || mypriority > 0)) {
 +
            do il via a chi attende di attraversare nella mia stessa direzione;
 +
        }else if (ncrossing_MyDirection == 0 && nwaiting_OppositeDirection > 0 ) {
 +
            restauro priority e lascio il comando alle macchine nella direzione opposta;
 +
</syntaxhighlight>
 +
 +
 +
L’ultima possibilità è che nessuno vuole attraversare il bridge, in questo caso nn faccio nulla.
 +
Il comando resta alla direzione che per ultima ha attraversato il bridge
 +
 +
 +
== Ponte a senso unico (2) ==
 +
<syntaxhighlight lang=C>
 +
#include <stdio.h>
 +
#include <monitor.h>
 +
#include <pthread.h>
 +
#include <string.h>
 +
 +
const int NCAR_E=8;
 +
const int NCAR_W=8;
 +
const int MAX_CAR = 7;
 +
 +
 +
enum dir{E,W,N};
 +
int n_carcross = 0;
 +
int waiting[2] = {0,0}; //[0] = [E] ; [1] = [W]
 +
enum dir curr_dir = N;
 +
 +
 +
monitor bridge;
 +
condition ok2go[2];
 +
 +
void bridge_create(){
 +
bridge = monitor_create();
 +
ok2go[0] = condition_create(bridge);
 +
ok2go[1] = condition_create(bridge);
 +
}
 +
 +
void print_bridge(){
 +
if (curr_dir == E)
 +
printf("%d W <<<<<%d<<<<< E %d\n",waiting[1],n_carcross,waiting[0]);
 +
else
 +
printf("%d W >>>>>%d>>>>> E %d\n",waiting[1],n_carcross,waiting[0]);
 +
}
 +
 +
void bridge_enter(enum dir d){
 +
monitor_enter(bridge);
 +
int i = (int) d;
 +
if (curr_dir == N){
 +
curr_dir = d;
 +
}
 +
if ((curr_dir != d) || (n_carcross >= MAX_CAR) || (waiting[1-i]>0)){
 +
waiting[i]++;
 +
condition_wait(ok2go[i]);
 +
waiting[i]--;
 +
}
 +
n_carcross++;
 +
print_bridge();
 +
if (n_carcross < MAX_CAR){
 +
if (waiting[i]>0)
 +
condition_signal(ok2go[i]);
 +
}
 +
monitor_exit(bridge);
 +
}
 +
 +
void bridge_exit(enum dir d){
 +
monitor_enter(bridge);
 +
int i = (int) d;
 +
n_carcross--;
 +
print_bridge();
 +
if (waiting[i]>0){
 +
if (n_carcross == 0){
 +
curr_dir = (enum dir) (1 - curr_dir);
 +
condition_signal(ok2go[i]);
 +
}
 +
}
 +
else
 +
      If (waiting [1-i]>0)
 +
  condition_signal(ok2go[1-i]);
 +
      Else
 +
          curr_dir = N;
 +
monitor_exit(bridge);
 +
}
 +
 +
void *cross(void* arg){
 +
enum dir d = (enum dir) arg;
 +
while (1) {
 +
        usleep(random() % 2000000);
 +
        bridge_enter(d);
 +
        usleep(random() % 2000000);
 +
        bridge_exit((enum dir)(1-d));
 +
}
 +
}
 +
 +
int main(int argc, const char * argv[]) {
 +
    pthread_t e_t[NCAR_E];
 +
    pthread_t w_t[NCAR_W];
 +
   
 +
    bridge_create();
 +
 +
    srandom(time(NULL));
 +
 +
    for (int i = 0; i < NCAR_E; i++) {
 +
        pthread_create(&e_t[i], NULL, cross,(void*) E);
 +
    }
 +
    for (int i = 0; i < NCAR_W; i++) {
 +
        pthread_create(&w_t[i], NULL, cross, (void*) W);
 +
    }
 +
    for (int i = 0; i < NCAR_E; i++) {
 +
        pthread_join(e_t[i], NULL);
 +
    }
 +
    for (int i = 0; i < NCAR_W; i++) {
 +
        pthread_join(w_t[i], NULL);
 +
    }
 +
    return 0;
 +
}
 +
</syntaxhighlight>
 +
 +
Questa è la prima soluzione che mi è venuta in mente cercando di rimanere sul più semplice possibile ... ho adottato alcuni accorgimenti per evitare di avere un programma lungo ma con "doppioni" --[[User:GabrieleCalarota|GabrieleCalarota]] ([[User talk:GabrieleCalarota|talk]]) 18:35, 14 December 2016 (CET)
 +
 +
== Monitor: Cospirazione dei filosofi ==
 +
 +
<syntaxhighlight lang=C>
 +
#include <stdio.h>
 +
#include <monitor.h>
 +
#include <pthread.h>
 +
#include <stdint.h>
 +
 +
monitor dp;
 +
condition philo_wait[5]; /* status[np(i,1)] == 'T' && status[np(i,-1)] == 'T' */
 +
char status[] = "TTTTT";
 +
 +
int np(int i, int off) {
 +
        return (i+5+off) % 5;
 +
}
 +
 +
 +
void dp_create(void) {
 +
        int i;
 +
        dp = monitor_create();
 +
        for (i=0; i<5; i++)
 +
                philo_wait[i] = condition_create(dp);
 +
}
 +
 +
void dp_starteat(int i) {
 +
        monitor_enter(dp);
 +
        if (status[np(i,1)] != 'T' || status[np(i,-1)] != 'T')
 +
                condition_wait(philo_wait[i]);
 +
        status[i] = 'E';
 +
        printf("%s\n",status);
 +
        monitor_exit(dp);
 +
}
 +
 +
void dp_endeat(int i) {
 +
        monitor_enter(dp);
 +
        status[i] = 'T';
 +
        printf("%s\n",status);
 +
        if (status[np(i,2)] == 'T')
 +
                condition_signal(philo_wait[np(i,1)]);
 +
        if (status[np(i,-2)] == 'T')
 +
                condition_signal(philo_wait[np(i,-1)]);
 +
        monitor_exit(dp);
 +
}
 +
 +
monitor cospy;
 +
condition wait2eat;
 +
int cospy_count;
 +
 +
void cospy_create(void) {
 +
        cospy = monitor_create();
 +
        wait2eat = condition_create(cospy);
 +
}
 +
 +
void cospy_starteat(void) {
 +
        monitor_enter(cospy);
 +
        cospy_count++;
 +
        condition_signal(wait2eat);
 +
        monitor_exit(cospy);
 +
}
 +
 +
void cospy_endeat(void) {
 +
        monitor_enter(cospy);
 +
        cospy_count--;
 +
        if (cospy_count == 0)
 +
                condition_wait(wait2eat);
 +
        monitor_exit(cospy);
 +
}
 +
 +
void *philo(void *arg) {
 +
        int i = (uintptr_t) arg;
 +
        while (1) {
 +
                usleep(random() % 2000000);
 +
                dp_starteat(i);
 +
                if (i == 1 || i == 3)
 +
                        cospy_starteat();
 +
                usleep(random() % 2000000);
 +
                if (i == 1 || i == 3)
 +
                        cospy_endeat();
 +
                dp_endeat(i);
 +
        }
 +
}
 +
 +
int main(int argc, char *argv[]) {
 +
        pthread_t philo_t[5];
 +
        uintptr_t i;
 +
        dp_create();
 +
        cospy_create();
 +
        srandom(time(NULL));
 +
        for (i=0; i<5; i++)
 +
                pthread_create(&philo_t[i], NULL, philo, (void *) i );
 +
        while(1)
 +
                pause();
 +
}
 +
</syntaxhighlight>
 +
--[[User:FedericoB|FedericoB]] ([[User talk:FedericoB|talk]]) 11:27, 25 November 2016 (CET)Veniva creata la condizione di cospirazione collegata al monitor dp invece che cospy. Quindi con il signal il processo veniva messo nell'urgent stack sbagliato e chiamando monitor_exit su cospy non si risvegliava il processo nell' urgent stack di dp.
 +
 +
== RW errato ==
 
Codice '''ERRATO''' dei lettori scrittori che dovrebbe non soffrire di problemi di starvation...
 
Codice '''ERRATO''' dei lettori scrittori che dovrebbe non soffrire di problemi di starvation...
 
Esercizio: trovare gli errori.
 
Esercizio: trovare gli errori.
Line 138: Line 536:
 
</syntaxhighlight>
 
</syntaxhighlight>
  
 +
== RW di FedericoB ==
 
Propongo la seguente soluzione. Mi sembra che funzioni ma devo ancora capire perchè e documentarla bene. Ho provato prima a cercare il bug ma non ci sono riuscito. Ho quindi modificato il codice secondo ciò che mi sembrava sensato in base alle condizioni del problema. Ne possiamo parlare in aula oggi. --[[User:FedericoB|FedericoB]] ([[User talk:FedericoB|talk]]) 12:48, 11 November 2016 (CET)
 
Propongo la seguente soluzione. Mi sembra che funzioni ma devo ancora capire perchè e documentarla bene. Ho provato prima a cercare il bug ma non ci sono riuscito. Ho quindi modificato il codice secondo ciò che mi sembrava sensato in base alle condizioni del problema. Ne possiamo parlare in aula oggi. --[[User:FedericoB|FedericoB]] ([[User talk:FedericoB|talk]]) 12:48, 11 November 2016 (CET)
 +
Ho notato che l'errore non si manifesta più eliminando il controllo che ci siano scrittori in attesa quando un lettore vuole iniziare a scrivere. Non capisco come questo possa essere collegato al bug. --[[User:FedericoB|FedericoB]] ([[User talk:FedericoB|talk]]) 15:10, 11 November 2016 (CET)
 +
 +
FedericoB, questa soluzione &egrave; quella con priorit&agrave; ai lettori, no? Se continuano ad arrivare lettori numberOfReaders non sar&agrave; mai zero e quindi gli scrittori non scriveranno mai. [[User:Renzo|Renzo]] ([[User talk:Renzo|talk]]) 10:34, 12 November 2016 (CET)
 +
 +
SFIDA: ho trovato il modo di togliere la starvation aggiungendo 4 token (parole chiave, nomi di variabili, operatori, costanti) a questa soluzione di FedericoB. Chi trova la soluzione? [[User:Renzo|Renzo]] ([[User talk:Renzo|talk]]) 10:43, 12 November 2016 (CET) Ah! ho appena trovato una soluzione che prevede 2 soli token in pi&ugrave;! [[User:Renzo|Renzo]] ([[User talk:Renzo|talk]]) 10:47, 12 November 2016 (CET)
  
 
<syntaxhighlight lang=C>
 
<syntaxhighlight lang=C>
Line 148: Line 552:
 
#define NUMBER_OF_READERS 3
 
#define NUMBER_OF_READERS 3
 
#define NUMBER_OF_WRITERS 3
 
#define NUMBER_OF_WRITERS 3
−
#define READER 0
 
−
#define WRITER 1
 
 
semaphore mutex;
 
semaphore mutex;
 
semaphore ok2read;
 
semaphore ok2read;
Line 155: Line 557:
  
 
int numberOfReaders=0;
 
int numberOfReaders=0;
−
int numberOfWriter=0;
+
int numberOfWriters=0;
 
int waitingReaders=0;
 
int waitingReaders=0;
 
int waitingWriters=0;
 
int waitingWriters=0;
Line 165: Line 567:
 
// <await nw == 0 -> nr++>
 
// <await nw == 0 -> nr++>
 
     semaphore_P(mutex);
 
     semaphore_P(mutex);
−
     if (numberOfWriter > 0) {
+
     if (numberOfWriters > 0) {
 
         waitingReaders++;
 
         waitingReaders++;
 
         semaphore_V(mutex);
 
         semaphore_V(mutex);
Line 172: Line 574:
 
     }
 
     }
 
     numberOfReaders++;
 
     numberOfReaders++;
−
     printf("NR %d - NW %d - WR %d - WW %d \n", numberOfReaders, numberOfWriter, waitingReaders, waitingWriters);
+
     printf("NR %d - NW %d - WR %d - WW %d \n", numberOfReaders, numberOfWriters, waitingReaders, waitingWriters);
 
     if (waitingReaders > 0 )
 
     if (waitingReaders > 0 )
 
         semaphore_V(ok2read);
 
         semaphore_V(ok2read);
Line 183: Line 585:
 
     semaphore_P(mutex);
 
     semaphore_P(mutex);
 
     numberOfReaders--;
 
     numberOfReaders--;
−
     printf("NR %d - NW %d - WR %d - WW %d \n", numberOfReaders, numberOfWriter, waitingReaders, waitingWriters);
+
     printf("NR %d - NW %d - WR %d - WW %d \n", numberOfReaders, numberOfWriters, waitingReaders, waitingWriters);
 
     if (numberOfReaders == 0 && waitingWriters > 0)
 
     if (numberOfReaders == 0 && waitingWriters > 0)
 
         semaphore_V(ok2write);
 
         semaphore_V(ok2write);
Line 193: Line 595:
 
// <await nw == 0 && nr == 0 -> nw++>
 
// <await nw == 0 && nr == 0 -> nw++>
 
     semaphore_P(mutex);
 
     semaphore_P(mutex);
−
     if (numberOfWriter > 0 || numberOfReaders > 0) {
+
     if (numberOfWriters > 0 || numberOfReaders > 0) {
 
         waitingWriters++;
 
         waitingWriters++;
 
         semaphore_V(mutex);
 
         semaphore_V(mutex);
Line 199: Line 601:
 
         waitingWriters--;
 
         waitingWriters--;
 
     }
 
     }
−
     numberOfWriter++;
+
     numberOfWriters++;
−
     printf("NR %d - NW %d - WR %d - WW %d \n", numberOfReaders, numberOfWriter, waitingReaders, waitingWriters);
+
     printf("NR %d - NW %d - WR %d - WW %d \n", numberOfReaders, numberOfWriters, waitingReaders, waitingWriters);
 
     semaphore_V(mutex);
 
     semaphore_V(mutex);
 
}
 
}
Line 207: Line 609:
 
// <nw-->
 
// <nw-->
 
     semaphore_P(mutex);
 
     semaphore_P(mutex);
−
     numberOfWriter--;
+
     numberOfWriters--;
−
     printf("NR %d - NW %d - WR %d - WW %d \n", numberOfReaders, numberOfWriter, waitingReaders, waitingWriters);
+
     printf("NR %d - NW %d - WR %d - WW %d \n", numberOfReaders, numberOfWriters, waitingReaders, waitingWriters);
 
     if (waitingReaders > 0)
 
     if (waitingReaders > 0)
 
         semaphore_V(ok2read);
 
         semaphore_V(ok2read);
Line 260: Line 662:
 
}
 
}
  
 +
</syntaxhighlight>
 +
 +
== RW2 ==
 +
Buongiorno, guardando il codice visto a lezione mi sembra che cambiando la condizione del primo if nella startread() da "if (nw > 0 && ww == 0)" a "if (nw > 0 || ww > 0)" la situazione migliori. In particolare con l'and tra quelle due condizioni si aveva che non veniva fatta la P sull'ok2read anche quando si aveva nw>0 (con ww!=0), cosa che invece dovrebbe fare. Lasciando il resto del codice uguale mi sembra che faccia quello che deve fare.. .
 +
 +
Matteo.pincherle: Perch&eacute; non modifichi in programma di FedericoB, lo provi e pubblichi qui la patch? [[User:Renzo|Renzo]] ([[User talk:Renzo|talk]]) 10:42, 13 November 2016 (CET)
 +
 +
'''Perchè quel AND permetteva di avere 2 scrittori?''' <br>
 +
Permetteva in primis di avere dei lettori in contemporanea a uno scrittore. In quanto se succedeva che un lettore volesse entrare mentre non c'erano degli scrittori in attesa ma scrittori in scrittura, veniva saltato il blocco che mandava il lettore in attesa e risultava un lettore in contemporanea a uno scrittore. <br>
 +
Questo lettore poi poteva finire di leggere prima che lo scrittore in contemporanea a lui finisse di scrivere. <br>
 +
Il lettore in uscita se non c'erano altri lettori con lui e non c'erano scrittori in attesa dava il permesso per far accedere un altro scrittore. <br>
 +
A questo punto un altro scrittore che avesse voluto entrare poteva entrare, con il risultato di avere 2 scrittori in contemporanea.
 +
--[[User:FedericoB|FedericoB]] ([[User talk:FedericoB|talk]]) 19:25, 13 November 2016 (CET)
 +
 +
== Patch ==
 +
Così, se non sbaglio, quando c'è almeno uno scrittore in attesa non lascia entrare altri lettori. Fa esaurire la lettura dei presenti e poi lascia scrivere lo scrittore.
 +
 +
<syntaxhighlight lang=C>
 +
 +
#include<stdio.h>
 +
#include<stdint.h>
 +
#include<pthread.h>
 +
#include<semaphore.h>
 +
 +
#define NUMBER_OF_READERS 3
 +
#define NUMBER_OF_WRITERS 3
 +
semaphore mutex;
 +
semaphore ok2read;
 +
semaphore ok2write;
 +
 +
int numberOfReaders=0;
 +
int numberOfWriters=0;
 +
int waitingReaders=0;
 +
int waitingWriters=0;
 +
int w_last;
 +
 +
// (nw == 0 && nr == 0) || (nr > 0 && nw == 0) || nw == 1
 +
// (nw == 0 && nr >= 0) || nw == 1
 +
 +
void startread(void) {
 +
    // <await nw == 0 -> nr++>
 +
    semaphore_P(mutex);
 +
    if (numberOfWriters > 0 || waitingWriters>0) {
 +
        waitingReaders++;
 +
        semaphore_V(mutex);
 +
        semaphore_P(ok2read);
 +
        waitingReaders--;
 +
    }
 +
    numberOfReaders++;
 +
    w_last=0;
 +
    printf("NR %d - NW %d - WR %d - WW %d \n", numberOfReaders, numberOfWriters, waitingReaders, waitingWriters);
 +
    if (waitingReaders > 0 )
 +
        semaphore_V(ok2read);
 +
    else
 +
        semaphore_V(mutex);
 +
}
 +
 +
void endread(void) {
 +
    // <nr-->
 +
    semaphore_P(mutex);
 +
    numberOfReaders--;
 +
    printf("NR %d - NW %d - WR %d - WW %d \n", numberOfReaders, numberOfWriters, waitingReaders, waitingWriters);
 +
    if (numberOfReaders == 0 && waitingWriters > 0)
 +
        semaphore_V(ok2write);
 +
    else
 +
        semaphore_V(mutex);
 +
}
 +
 +
void startwrite(void) {
 +
    // <await nw == 0 && nr == 0 -> nw++>
 +
    semaphore_P(mutex);
 +
    if (numberOfWriters > 0 || numberOfReaders > 0) {
 +
        waitingWriters++;
 +
        semaphore_V(mutex);
 +
        semaphore_P(ok2write);
 +
        waitingWriters--;
 +
    }
 +
    numberOfWriters++;
 +
    w_last=1;
 +
    printf("NR %d - NW %d - WR %d - WW %d \n", numberOfReaders, numberOfWriters, waitingReaders, waitingWriters);
 +
    semaphore_V(mutex);
 +
}
 +
 +
void endwrite(void) {
 +
    // <nw-->
 +
    semaphore_P(mutex);
 +
    numberOfWriters--;
 +
    printf("NR %d - NW %d - WR %d - WW %d \n", numberOfReaders, numberOfWriters, waitingReaders, waitingWriters);
 +
    if (waitingReaders > 0 && (waitingWriters==0 || w_last))
 +
        semaphore_V(ok2read);
 +
    else if (waitingWriters > 0 && (waitingReaders==0 || !w_last))
 +
        semaphore_V(ok2write);
 +
    else
 +
        semaphore_V(mutex);
 +
}
 +
 +
void *reader(void *arg) {
 +
    int i = (uintptr_t)arg;
 +
    while (1) {
 +
        //other code
 +
        usleep(random() % 200000);
 +
        startread();
 +
        //read
 +
        usleep(random() % 200000);
 +
        endread();
 +
    }
 +
}
 +
 +
void *writer(void *arg) {
 +
    int i = (uintptr_t)arg;
 +
    while (1) {
 +
        //other code
 +
        usleep(random() % 200000);
 +
        startwrite();
 +
        //write
 +
        usleep(random() % 200000);
 +
        endwrite();
 +
    }
 +
}
 +
 +
int main(int argc, char *argv[]) {
 +
    int i;
 +
    pthread_t t;
 +
    srandom(time(NULL));
 +
    mutex=semaphore_create(1);
 +
    ok2read=semaphore_create(0);
 +
    ok2write=semaphore_create(0);
 +
    for (i=0; i<NUMBER_OF_READERS; i++)
 +
        pthread_create(&t, NULL, reader, (void *)(uintptr_t) i);
 +
    for (i=0; i<NUMBER_OF_WRITERS; i++)
 +
        pthread_create(&t, NULL, writer, (void *)(uintptr_t) i);
 +
    while(1)
 +
        pause();
 +
}
 +
 +
</syntaxhighlight>
 +
 +
wlast non serve pi&ugrave;... [[User:Renzo|Renzo]] ([[User talk:Renzo|talk]]) 17:52, 13 November 2016 (CET)
 +
 +
== RW2bis ==
 +
Nella tua soluzione se i lettori sono "molto veloci" e non vanno mai a 0, lo scrittore non inizierà mai a scrivere.
 +
 +
Cioè: Uno scrittore viene svegliato da ok2write solo se passa la condizione
 +
<syntaxhighlight lang=C>
 +
[..]
 +
if (numberofReaders == 0 && waitingWriters >0)
 +
    semaphore_V(ok2write);
 +
[..]
 +
</syntaxhighlight> --[[User:GabrieleCalarota|GabrieleCalarota]] ([[User talk:GabrieleCalarota|talk]]) 17:46, 13 November 2016 (CET)
 +
 +
Non direi perche' nella startread se:
 +
<syntaxhighlight lang=C>
 +
    if (numberOfWriters > 0 || waitingWriters>0)
 +
</syntaxhighlight>
 +
i lettori si bloccano. Quindi se c'e' almeno uno scrittore in attesa i lettori non entrano (e quindi prima o poi terminano e lasciano il posto ad uno scrittore).
 +
[[User:Renzo|Renzo]] ([[User talk:Renzo|talk]]) 17:57, 13 November 2016 (CET)
 +
 +
 +
Ho pensato al caso limite seguente:
 +
Supponiamo che ci siano dei lettori che stanno leggendo e ad un certo punto uno scrittore chiede di scrivere.
 +
 +
<syntaxhighlight lang=C>       
 +
      void startread(void) {
 +
    // <await nw == 0 -> nr++>
 +
    semaphore_P(mutex);
 +
    if (numberOfWriters > 0 || waitingWriters>0) {
 +
        waitingReaders++;  //Nuovo scrittore (t1)
 +
        semaphore_V(mutex);
 +
        semaphore_P(ok2read);
 +
        waitingReaders--;
 +
    }
 +
    numberOfReaders++;
 +
    w_last=0;
 +
    printf("NR %d - NW %d - WR %d - WW %d \n", numberOfReaders, numberOfWriters, waitingReaders, waitingWriters);
 +
  if (waitingReaders > 0 )  //Vecchio scrittore(t1)
 +
        semaphore_V(ok2read);
 +
    else
 +
        semaphore_V(mutex);
 +
}
 +
</syntaxhighlight>
 +
 +
Non appena lo scrittore rilascia il mutex, un nuovo lettore chiede di leggere (e si addormenterà). Un lettore (lento) che era riuscito a entrare nel segmento startofread prima che lo scrittore entrasse in startofwrite, continua a leggere e risveglia uno dei nuovi lettori. Se i lettori continuano a richiedere di leggere continuamente, verranno addormentati e subito risvegliati.
 +
 +
E' da considerarsi possibile? --[[User:GabrieleCalarota|GabrieleCalarota]] ([[User talk:GabrieleCalarota|talk]]) 19:11, 13 November 2016 (CET)
 +
 +
Suppongo che "un nuovo scrittore chiede di leggere" si aun refuso e sia da intendere "un nuovo lettore chiede di leggere" (altrimenti ci sono crisi di identit&agrave;) e che "startofread" significhi "startread" e "startofwrite"  sia "startwrite".
 +
La "startread" viene eseguita in mutua esclusione, quindi non ci puo' essere "un lettore lento che sia riuscito ad entrare" nella funione startread. Se ha superato la P(mutex) iniziale o e' bloccato sulla ok2read o e' entrato. [[User:Renzo|Renzo]] ([[User talk:Renzo|talk]]) 19:37, 13 November 2016 (CET)
 +
 +
=== pali ===
 +
<syntaxhighlight lang=python>
 +
#!/usr/bin/env python3
 +
 +
import threading
 +
import time
 +
import logging
 +
import random
 +
from monitor import monitor, condition, entry
 +
 +
class safeprint(monitor):
 +
def __init__(self):
 +
super().__init__()
 +
 +
@entry
 +
def print(self, *args,**kwargs):
 +
print(*args,**kwargs)
 +
 +
safeprint = safeprint().print
 +
 +
class polimon(monitor):
 +
vsig = [0,0,0,0,-1,4,3,2,1,0]
 +
vwait = [0,1,2,3,4,-1,0,0,0,0]
 +
def __init__(self):
 +
super().__init__()
 +
self.started=set()
 +
self.state = 0
 +
self.vcond = [condition(self) for _ in range(5)]
 +
self.printing = False
 +
 +
@entry
 +
def sync(self, i):
 +
if i not in self.started:
 +
self.started.add(i)
 +
if self.printing:
 +
self.vcond[0].wait()
 +
else:
 +
self.printing = False
 +
nextsig = polimon.vsig[self.state]
 +
if nextsig >= 0:
 +
self.vcond[nextsig].signal()
 +
self.state = (self.state + 1) % 10
 +
nextwait = polimon.vwait[self.state]
 +
if nextwait >= 0:
 +
self.vcond[nextwait].wait()
 +
self.printing = True
 +
 +
def client(poli,i):
 +
for _ in range(10):
 +
time.sleep(random.random() * 0.5)
 +
poli.sync(i)
 +
safeprint(i)
 +
 +
if __name__ == "__main__":
 +
cli=[]
 +
poli = polimon()
 +
for i in range(10):
 +
p=threading.Thread(name='cli'+str(i), target=client, args=(poli,i))
 +
p.deamon=True
 +
p=cli.append(p)
 +
for i in range(10):
 +
cli[i].start()
 +
for i in range(10):
 +
cli[i].join()
 
</syntaxhighlight>
 
</syntaxhighlight>

Latest revision as of 13:32, 16 May 2017

Monitor: Ponte a senso Unico

Proposta di soluzione: esercizio 1 esame 22/01/2014 

//
//  20140122_bridge
//
/*   Esercizio c.1:
 *
 *   Per colpa delle frane un ponte veicolare e' rimasto danneggiato.
 *   I veicoli possono ora percorrerlo solo in senso unico alternato e, per non eccedere la portata,
 *   al piu' ci possono essere sul ponte N veicoli contemporaneamente.
 *   Scrivere il monitor bridge sapendo che i veicoli chiameranno il monitor prima di entrare nel
 *   ponte e dopo averlo attraversato.
 *   I veicoli che entrano dal lato est escono dal lato ovest e viceversa.
 *   Quindi i (numerosi) veicoli eseguiranno uno dei due frammenti di codice seguenti:
 *
 *
 *   bridge.enter(E)                      bridge.enter(W)
 *   //cross the bridge                   //cross the bridge
 *   bridge.exit(W)                       bridge.exit(E)
 *
 *
 *   La soluzione proposta deve evitare deadlock e deve essere efficiente.
 *   (controesempio: una soluzione che prevedesse l'attraversamento del ponte da parte di un solo veicolo alla volta
 *   sebbene rispetti tutti i vincoli sarebbe considerata errata poiche' inefficiente).
 *   Oltre al codice si richiede una descrizione degli accorgimenti adottati per rendere la soluzione efficiente.
*/

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

#define CAPACITY 7 //capacità del bridge
#define BALANCE 9  
#define NCAR 15

enum dest{
    E = 0,
    W = 1
};

int ncrossing_we = 0; //n car che stanno attraversando il bridge da W->E
int ncrossing_ew = 0; //n car che stanno attraversando il bridge da E->W

int nwaiting_we = 0; //n car che aspettano di attraversare da W->E
int nwaiting_ew = 0;  //n car che aspettano di attraversare da E->W

int priority = BALANCE;

int crossed_we = 0; //n volte che il ponte è stato attraversato da W->E
int crossed_ew = 0; //n volte che il ponte è stato attraversato da E->W

condition ok2goW; // capacity > 0 && (ncrossing_ew == 0 || priority > 0)
condition ok2goE; // capacity > 0 && (ncrossing_we == 0 || prioriti > 0 )
monitor bridge;

void bridge_create(void){
    bridge = monitor_create();
    ok2goW = condition_create(bridge);
    ok2goE = condition_create(bridge);
}

void bridge_enter(enum dest d){
    monitor_enter(bridge);
    if (d == W) {
        nwaiting_we++;
        if (ncrossing_we >= CAPACITY || ncrossing_ew > 0 || (nwaiting_ew > 0 && priority <= 0)) {
            condition_wait(ok2goW);
        }
        priority--;
        nwaiting_we--;
        ncrossing_we++;
        if (ncrossing_we < CAPACITY && priority > 0) {
            condition_signal(ok2goW);
        }
    }else if(d == E){
        nwaiting_ew++;
        if (ncrossing_ew >= CAPACITY || ncrossing_we > 0 || (nwaiting_we > 0 && priority <= 0)){
            condition_wait(ok2goE);
        }
        priority--;
        nwaiting_ew--;
        ncrossing_ew++;
        if (ncrossing_ew < CAPACITY && priority > 0) {
            condition_signal(ok2goE);
        }
    }
    monitor_exit(bridge);
}

void bridge_exit(enum dest d){
    monitor_enter(bridge);
    if (d == E) {
        ncrossing_we--;
        crossed_we++;
        if (ncrossing_we < CAPACITY && nwaiting_we > 0 && (nwaiting_ew == 0 || priority > 0)) {
            condition_signal(ok2goW);
        }else if (ncrossing_we == 0 && nwaiting_ew > 0 ) {
            priority = BALANCE;
            condition_signal(ok2goE);
        }
    } else if (d == W){
        ncrossing_ew--;
        crossed_ew++;
        if (ncrossing_ew < CAPACITY && nwaiting_ew > 0 && (nwaiting_we == 0 || priority > 0)) {
            condition_signal(ok2goE);
        }else if (ncrossing_ew == 0 && nwaiting_we > 0) {
            priority = BALANCE;
            condition_signal(ok2goW);
        }
    }
    monitor_exit(bridge);
}

void *crossEW(void* arg){
    while (1) {
        printf("waitW: %d |-|%d|->  <-|%d|-| waitE: %d  || crossed W->E: %d crossed E->W: %d||\n", nwaiting_we, ncrossing_we, ncrossing_ew, nwaiting_ew, crossed_we, crossed_ew);
        usleep(random() % 200000);
        bridge_enter(E);
        usleep(random() % 20000);
        bridge_exit(W);
    }
}

void *crossWE(void* arg){
    while (1) {
        printf("waitW: %d |-|%d|->  <-|%d|-| waitE: %d  || crossed W->E: %d crossed E->W: %d||\n", nwaiting_we, ncrossing_we, ncrossing_ew, nwaiting_ew, crossed_we, crossed_ew);
        usleep(random() % 200000);
        bridge_enter(W);
        usleep(random() % 20000);
        bridge_exit(E);
    }
}

int main(int argc, const char * argv[]) {
    pthread_t e_w_t[NCAR];
    pthread_t w_e_t[NCAR];
    bridge_create();

    srandom(time(NULL));
    for (int i = 0; i < NCAR; i++) {
        pthread_create(&e_w_t[i], NULL, crossEW, NULL);
        pthread_create(&w_e_t[i], NULL, crossWE, NULL);

    }
    for (int i = 0; i < NCAR; i++) {
        pthread_join(w_e_t[i], NULL);
        pthread_join(e_w_t[i], NULL);
    }
    return 0;
}


Dal testo dell'esercizio si evincono le seguenti condizioni basilari per poter attraversare il ponte: 

   (capacità>0 && ncrossing_OppositeDirection == 0)

Per rendere la soluzione efficiente ho introdotto, così, la variabile priority settata al valore BALANCE ottenendo la seguente condizione: 

priority > 0 || nwaitingOppositeDirection == 0;

e.i. fin quando il mio senso (e.g. W->E) ha ancora priorità di attraversare O non ci sono macchine nella direzione opposta che attendono, continuo a dare il via alle macchine che vanno nella mia stessa direzione. Priority viene decrementata ad ogni macchina che attraversa il ponte.

Non appena tale condizione viene interrotta, priority viene restaurata al valore BALANCE e la sua gestione viene ceduta al senso opposto. Notare che anche questa soluzione non gestisce il caso in cui "il mio senso ha priorità ma non c'è nessuno che vuole attraversare", sarebbe inutile far attendere e maccchine della direzione opposta. Allora il tutto viene gestito come segue: 

   bridge.enter()
    if (ncrossing_MyDirection <= CAPACITY && ncrossing_OppositeDirection == 0 && (mypriority > 0 || nwaitingOppositeDirection == 0)){
					 attraverso il ponte;
    }

    bridge.exit()
	if (ncrossing_MyDirection < CAPACITY && nwaiting_MyDirection > 0 && (nwaiting_OppositeDirection == 0 || mypriority > 0)) {
            		do il via a chi attende di attraversare nella mia stessa direzione;
        }else if (ncrossing_MyDirection == 0 && nwaiting_OppositeDirection > 0 ) {
            		restauro priority e lascio il comando alle macchine nella direzione opposta;


L’ultima possibilità è che nessuno vuole attraversare il bridge, in questo caso nn faccio nulla. Il comando resta alla direzione che per ultima ha attraversato il bridge


Ponte a senso unico (2)

#include <stdio.h>
#include <monitor.h>
#include <pthread.h>
#include <string.h>

const int NCAR_E=8;
const int NCAR_W=8;
const int MAX_CAR = 7;


enum dir{E,W,N};
int n_carcross = 0;
int waiting[2] = {0,0}; //[0] = [E] ; [1] = [W]
enum dir curr_dir = N; 


monitor bridge;
condition ok2go[2];

void bridge_create(){
	bridge = monitor_create();
	ok2go[0] = condition_create(bridge);
	ok2go[1] = condition_create(bridge);
}

void print_bridge(){
	if (curr_dir == E)
		printf("%d W <<<<<%d<<<<< E %d\n",waiting[1],n_carcross,waiting[0]);
	else
		printf("%d W >>>>>%d>>>>> E %d\n",waiting[1],n_carcross,waiting[0]);
}

void bridge_enter(enum dir d){
	monitor_enter(bridge);
	int i = (int) d;
	if (curr_dir == N){
		curr_dir = d;
	}
	if ((curr_dir != d) || (n_carcross >= MAX_CAR) || (waiting[1-i]>0)){
			waiting[i]++;
			condition_wait(ok2go[i]);
			waiting[i]--;
	}
	n_carcross++;
	print_bridge();
	if (n_carcross < MAX_CAR){
		if (waiting[i]>0)
			condition_signal(ok2go[i]);
	}
	monitor_exit(bridge);
}

void bridge_exit(enum dir d){
 monitor_enter(bridge);
 int i = (int) d;
 n_carcross--;
 print_bridge();
 if (waiting[i]>0){
 	if (n_carcross == 0){
 		curr_dir = (enum dir) (1 - curr_dir);
 		condition_signal(ok2go[i]);
 	}
 }
 else
       If (waiting [1-i]>0)
 	   condition_signal(ok2go[1-i]);
       Else 
           curr_dir = N; 
 monitor_exit(bridge);
}

void *cross(void* arg){
	enum dir d = (enum dir) arg;
	while (1) {
	        usleep(random() % 2000000);
	        bridge_enter(d);
	        usleep(random() % 2000000);
	        bridge_exit((enum dir)(1-d));
	}
}

int main(int argc, const char * argv[]) {
    pthread_t e_t[NCAR_E];
    pthread_t w_t[NCAR_W];
    
    bridge_create();
 
    srandom(time(NULL));

    for (int i = 0; i < NCAR_E; i++) {
        pthread_create(&e_t[i], NULL, cross,(void*) E); 
    }
    for (int i = 0; i < NCAR_W; i++) {
        pthread_create(&w_t[i], NULL, cross, (void*) W);
    }
    for (int i = 0; i < NCAR_E; i++) {
        pthread_join(e_t[i], NULL);
    }
    for (int i = 0; i < NCAR_W; i++) {
        pthread_join(w_t[i], NULL);
    }
    return 0;
}

Questa è la prima soluzione che mi è venuta in mente cercando di rimanere sul più semplice possibile ... ho adottato alcuni accorgimenti per evitare di avere un programma lungo ma con "doppioni" --GabrieleCalarota (talk) 18:35, 14 December 2016 (CET)

Monitor: Cospirazione dei filosofi

#include <stdio.h>
#include <monitor.h>
#include <pthread.h>
#include <stdint.h>

monitor dp;
condition philo_wait[5]; /* status[np(i,1)] == 'T' && status[np(i,-1)] == 'T' */
char status[] = "TTTTT";

int np(int i, int off) {
        return (i+5+off) % 5;
}


void dp_create(void) {
        int i;
        dp = monitor_create();
        for (i=0; i<5; i++)
                philo_wait[i] = condition_create(dp);
}

void dp_starteat(int i) {
        monitor_enter(dp);
        if (status[np(i,1)] != 'T' || status[np(i,-1)] != 'T')
                condition_wait(philo_wait[i]);
        status[i] = 'E';
        printf("%s\n",status);
        monitor_exit(dp);
}

void dp_endeat(int i) {
        monitor_enter(dp);
        status[i] = 'T';
        printf("%s\n",status);
        if (status[np(i,2)] == 'T')
                condition_signal(philo_wait[np(i,1)]);
        if (status[np(i,-2)] == 'T')
                condition_signal(philo_wait[np(i,-1)]);
        monitor_exit(dp);
}

monitor cospy;
condition wait2eat;
int cospy_count;

void cospy_create(void) {
        cospy = monitor_create();
        wait2eat = condition_create(cospy);
}

void cospy_starteat(void) {
        monitor_enter(cospy);
        cospy_count++;
        condition_signal(wait2eat);
        monitor_exit(cospy);
}

void cospy_endeat(void) {
        monitor_enter(cospy);
        cospy_count--;
        if (cospy_count == 0)
                condition_wait(wait2eat);
        monitor_exit(cospy);
}

void *philo(void *arg) {
        int i = (uintptr_t) arg;
        while (1) {
                usleep(random() % 2000000);
                dp_starteat(i);
                if (i == 1 || i == 3)
                        cospy_starteat();
                usleep(random() % 2000000);
                if (i == 1 || i == 3)
                        cospy_endeat();
                dp_endeat(i);
        }
}

int main(int argc, char *argv[]) {
        pthread_t philo_t[5];
        uintptr_t i;
        dp_create();
        cospy_create();
        srandom(time(NULL));
        for (i=0; i<5; i++)
                pthread_create(&philo_t[i], NULL, philo, (void *) i );
        while(1)
                pause();
}

--FedericoB (talk) 11:27, 25 November 2016 (CET)Veniva creata la condizione di cospirazione collegata al monitor dp invece che cospy. Quindi con il signal il processo veniva messo nell'urgent stack sbagliato e chiamando monitor_exit su cospy non si risvegliava il processo nell' urgent stack di dp.

RW errato

Codice ERRATO dei lettori scrittori che dovrebbe non soffrire di problemi di starvation... Esercizio: trovare gli errori. 

#include<stdio.h>
#include<stdint.h>
#include<pthread.h>
#include<semaphore.h>

#define NREADER 3
#define NWRITER 3
semaphore mutex;
semaphore ok2read;
semaphore ok2write;

int nr=0;
int nw=0;
int wr=0;
int ww=0;
int w_last;

// (nw == 0 && nr == 0) || (nr > 0 && nw == 0) || nw == 1
// (nw == 0 && nr >= 0) || nw == 1

// this "baton" function has been left for reference only.
// code to implement "passing the baton" has been copied at the end of
// each ({start}|{end})({read}|{write}) function and reduced.
void baton(void) {
        if (nw == 0 && nr == 0 && ww > 0)
                semaphore_V(ok2write);
        else if (nw == 0 && wr > 0 )
                semaphore_V(ok2read);
        else
                semaphore_V(mutex);
}

void startread(void) {
// <await nw == 0 -> nr++>
        semaphore_P(mutex);
        if (nw > 0 && ww == 0) {
                wr++;
                semaphore_V(mutex);
                semaphore_P(ok2read);
                wr--;
        }
        nr++;
        w_last=0;
        printf("NR %d - NW %d - WR %d - WW %d \n", nr, nw, wr, ww);
        if (wr > 0 )
                semaphore_V(ok2read);
        else
                semaphore_V(mutex);
}

void endread(void) {
// <nr-->
        semaphore_P(mutex);
        nr--;
        printf("NR %d - NW %d - WR %d - WW %d \n", nr, nw, wr, ww);
        if (nr == 0 && ww > 0)
                semaphore_V(ok2write);
        else
                semaphore_V(mutex);
}

void startwrite(void) {
// <await nw == 0 && nr == 0 -> nw++>
        semaphore_P(mutex);
        if (nw > 0 || nr > 0) {
                ww++;
                semaphore_V(mutex);
                semaphore_P(ok2write);
                ww--;
        }
        nw++;
        w_last=1;
        printf("NR %d - NW %d - WR %d - WW %d \n", nr, nw, wr, ww);
        semaphore_V(mutex);
}

void endwrite(void) {
// <nw-->
        semaphore_P(mutex);
        nw--;
        printf("NR %d - NW %d - WR %d - WW %d \n", nr, nw, wr, ww);
        if (wr > 0 && (ww == 0 || w_last))
                semaphore_V(ok2read);
        else if (ww > 0 && (wr == 0 || !w_last))
                semaphore_V(ok2write);
        else
                semaphore_V(mutex);
}

void *reader(void *arg) {
        int i = (uintptr_t)arg;
        while (1) {
                //other code
                usleep(random() % 200000);
                startread();
                //read
                usleep(random() % 200000);
                endread();
        }
}

void *writer(void *arg) {
        int i = (uintptr_t)arg;
        while (1) {
                //other code
                usleep(random() % 200000);
                startwrite();
                //write
                usleep(random() % 200000);
                endwrite();
        }
}


//printf("philo thinking: %d\n",i);
/*while*/

int main(int argc, char *argv[]) {
        int i;
        pthread_t t;
        srandom(time(NULL));
        mutex=semaphore_create(1);
        ok2read=semaphore_create(0);
        ok2write=semaphore_create(0);
        for (i=0; i<NREADER; i++)
                pthread_create(&t, NULL, reader, (void *)(uintptr_t) i);
        for (i=0; i<NWRITER; i++)
                pthread_create(&t, NULL, writer, (void *)(uintptr_t) i);
        while(1)
                pause();
}

RW di FedericoB

Propongo la seguente soluzione. Mi sembra che funzioni ma devo ancora capire perchè e documentarla bene. Ho provato prima a cercare il bug ma non ci sono riuscito. Ho quindi modificato il codice secondo ciò che mi sembrava sensato in base alle condizioni del problema. Ne possiamo parlare in aula oggi. --FedericoB (talk) 12:48, 11 November 2016 (CET) Ho notato che l'errore non si manifesta più eliminando il controllo che ci siano scrittori in attesa quando un lettore vuole iniziare a scrivere. Non capisco come questo possa essere collegato al bug. --FedericoB (talk) 15:10, 11 November 2016 (CET)

FedericoB, questa soluzione è quella con priorità ai lettori, no? Se continuano ad arrivare lettori numberOfReaders non sarà mai zero e quindi gli scrittori non scriveranno mai. Renzo (talk) 10:34, 12 November 2016 (CET)

SFIDA: ho trovato il modo di togliere la starvation aggiungendo 4 token (parole chiave, nomi di variabili, operatori, costanti) a questa soluzione di FedericoB. Chi trova la soluzione? Renzo (talk) 10:43, 12 November 2016 (CET) Ah! ho appena trovato una soluzione che prevede 2 soli token in più! Renzo (talk) 10:47, 12 November 2016 (CET) 

#include<stdio.h>
#include<stdint.h>
#include<pthread.h>
#include<semaphore.h>

#define NUMBER_OF_READERS 3
#define NUMBER_OF_WRITERS 3
semaphore mutex;
semaphore ok2read;
semaphore ok2write;

int numberOfReaders=0;
int numberOfWriters=0;
int waitingReaders=0;
int waitingWriters=0;

// (nw == 0 && nr == 0) || (nr > 0 && nw == 0) || nw == 1
// (nw == 0 && nr >= 0) || nw == 1

void startread(void) {
// <await nw == 0 -> nr++>
    semaphore_P(mutex);
    if (numberOfWriters > 0) {
        waitingReaders++;
        semaphore_V(mutex);
        semaphore_P(ok2read);
        waitingReaders--;
    }
    numberOfReaders++;
    printf("NR %d - NW %d - WR %d - WW %d \n", numberOfReaders, numberOfWriters, waitingReaders, waitingWriters);
    if (waitingReaders > 0 )
        semaphore_V(ok2read);
    else
        semaphore_V(mutex);
}

void endread(void) {
// <nr-->
    semaphore_P(mutex);
    numberOfReaders--;
    printf("NR %d - NW %d - WR %d - WW %d \n", numberOfReaders, numberOfWriters, waitingReaders, waitingWriters);
    if (numberOfReaders == 0 && waitingWriters > 0)
        semaphore_V(ok2write);
    else
        semaphore_V(mutex);
}

void startwrite(void) {
// <await nw == 0 && nr == 0 -> nw++>
    semaphore_P(mutex);
    if (numberOfWriters > 0 || numberOfReaders > 0) {
        waitingWriters++;
        semaphore_V(mutex);
        semaphore_P(ok2write);
        waitingWriters--;
    }
    numberOfWriters++;
    printf("NR %d - NW %d - WR %d - WW %d \n", numberOfReaders, numberOfWriters, waitingReaders, waitingWriters);
    semaphore_V(mutex);
}

void endwrite(void) {
// <nw-->
    semaphore_P(mutex);
    numberOfWriters--;
    printf("NR %d - NW %d - WR %d - WW %d \n", numberOfReaders, numberOfWriters, waitingReaders, waitingWriters);
    if (waitingReaders > 0)
        semaphore_V(ok2read);
    else if (waitingWriters > 0)
        semaphore_V(ok2write);
    else
        semaphore_V(mutex);
}

void *reader(void *arg) {
    int i = (uintptr_t)arg;
    while (1) {
        //other code
        usleep(random() % 200000);
        startread();
        //read
        usleep(random() % 200000);
        endread();
    }
}

void *writer(void *arg) {
    int i = (uintptr_t)arg;
    while (1) {
        //other code
        usleep(random() % 200000);
        startwrite();
        //write
        usleep(random() % 200000);
        endwrite();
    }
}


//printf("philo thinking: %d\n",i);
/*while*/

int main(int argc, char *argv[]) {
    int i;
    pthread_t t;
    srandom(time(NULL));
    mutex=semaphore_create(1);
    ok2read=semaphore_create(0);
    ok2write=semaphore_create(0);
    for (i=0; i<NUMBER_OF_READERS; i++)
        pthread_create(&t, NULL, reader, (void *)(uintptr_t) i);
    for (i=0; i<NUMBER_OF_WRITERS; i++)
        pthread_create(&t, NULL, writer, (void *)(uintptr_t) i);
    while(1)
        pause();
}

RW2

Buongiorno, guardando il codice visto a lezione mi sembra che cambiando la condizione del primo if nella startread() da "if (nw > 0 && ww == 0)" a "if (nw > 0 || ww > 0)" la situazione migliori. In particolare con l'and tra quelle due condizioni si aveva che non veniva fatta la P sull'ok2read anche quando si aveva nw>0 (con ww!=0), cosa che invece dovrebbe fare. Lasciando il resto del codice uguale mi sembra che faccia quello che deve fare.. .

Matteo.pincherle: Perché non modifichi in programma di FedericoB, lo provi e pubblichi qui la patch? Renzo (talk) 10:42, 13 November 2016 (CET)

Perchè quel AND permetteva di avere 2 scrittori?
Permetteva in primis di avere dei lettori in contemporanea a uno scrittore. In quanto se succedeva che un lettore volesse entrare mentre non c'erano degli scrittori in attesa ma scrittori in scrittura, veniva saltato il blocco che mandava il lettore in attesa e risultava un lettore in contemporanea a uno scrittore.
Questo lettore poi poteva finire di leggere prima che lo scrittore in contemporanea a lui finisse di scrivere.
Il lettore in uscita se non c'erano altri lettori con lui e non c'erano scrittori in attesa dava il permesso per far accedere un altro scrittore.
A questo punto un altro scrittore che avesse voluto entrare poteva entrare, con il risultato di avere 2 scrittori in contemporanea. --FedericoB (talk) 19:25, 13 November 2016 (CET)

Patch

Così, se non sbaglio, quando c'è almeno uno scrittore in attesa non lascia entrare altri lettori. Fa esaurire la lettura dei presenti e poi lascia scrivere lo scrittore. 

#include<stdio.h>
#include<stdint.h>
#include<pthread.h>
#include<semaphore.h>

#define NUMBER_OF_READERS 3
#define NUMBER_OF_WRITERS 3
semaphore mutex;
semaphore ok2read;
semaphore ok2write;

int numberOfReaders=0;
int numberOfWriters=0;
int waitingReaders=0;
int waitingWriters=0;
int w_last;

// (nw == 0 && nr == 0) || (nr > 0 && nw == 0) || nw == 1
// (nw == 0 && nr >= 0) || nw == 1

void startread(void) {
    // <await nw == 0 -> nr++>
    semaphore_P(mutex);
    if (numberOfWriters > 0 || waitingWriters>0) {
        waitingReaders++;
        semaphore_V(mutex);
        semaphore_P(ok2read);
        waitingReaders--;
    }
    numberOfReaders++;
    w_last=0;
    printf("NR %d - NW %d - WR %d - WW %d \n", numberOfReaders, numberOfWriters, waitingReaders, waitingWriters);
    if (waitingReaders > 0 )
        semaphore_V(ok2read);
    else
        semaphore_V(mutex);
}

void endread(void) {
    // <nr-->
    semaphore_P(mutex);
    numberOfReaders--;
    printf("NR %d - NW %d - WR %d - WW %d \n", numberOfReaders, numberOfWriters, waitingReaders, waitingWriters);
    if (numberOfReaders == 0 && waitingWriters > 0)
        semaphore_V(ok2write);
    else
        semaphore_V(mutex);
}

void startwrite(void) {
    // <await nw == 0 && nr == 0 -> nw++>
    semaphore_P(mutex);
    if (numberOfWriters > 0 || numberOfReaders > 0) {
        waitingWriters++;
        semaphore_V(mutex);
        semaphore_P(ok2write);
        waitingWriters--;
    }
    numberOfWriters++;
    w_last=1;
    printf("NR %d - NW %d - WR %d - WW %d \n", numberOfReaders, numberOfWriters, waitingReaders, waitingWriters);
    semaphore_V(mutex);
}

void endwrite(void) {
    // <nw-->
    semaphore_P(mutex);
    numberOfWriters--;
    printf("NR %d - NW %d - WR %d - WW %d \n", numberOfReaders, numberOfWriters, waitingReaders, waitingWriters);
    if (waitingReaders > 0 && (waitingWriters==0 || w_last))
        semaphore_V(ok2read);
    else if (waitingWriters > 0 && (waitingReaders==0 || !w_last))
        semaphore_V(ok2write);
    else
        semaphore_V(mutex);
}

void *reader(void *arg) {
    int i = (uintptr_t)arg;
    while (1) {
        //other code
        usleep(random() % 200000);
        startread();
        //read
        usleep(random() % 200000);
        endread();
    }
}

void *writer(void *arg) {
    int i = (uintptr_t)arg;
    while (1) {
        //other code
        usleep(random() % 200000);
        startwrite();
        //write
        usleep(random() % 200000);
        endwrite();
    }
}

int main(int argc, char *argv[]) {
    int i;
    pthread_t t;
    srandom(time(NULL));
    mutex=semaphore_create(1);
    ok2read=semaphore_create(0);
    ok2write=semaphore_create(0);
    for (i=0; i<NUMBER_OF_READERS; i++)
        pthread_create(&t, NULL, reader, (void *)(uintptr_t) i);
    for (i=0; i<NUMBER_OF_WRITERS; i++)
        pthread_create(&t, NULL, writer, (void *)(uintptr_t) i);
    while(1)
        pause();
}

wlast non serve più... Renzo (talk) 17:52, 13 November 2016 (CET)

RW2bis

Nella tua soluzione se i lettori sono "molto veloci" e non vanno mai a 0, lo scrittore non inizierà mai a scrivere.

Cioè: Uno scrittore viene svegliato da ok2write solo se passa la condizione 

[..] 
if (numberofReaders == 0 && waitingWriters >0) 
     semaphore_V(ok2write);
[..]

--GabrieleCalarota (talk) 17:46, 13 November 2016 (CET)

Non direi perche' nella startread se: 

    if (numberOfWriters > 0 || waitingWriters>0)

i lettori si bloccano. Quindi se c'e' almeno uno scrittore in attesa i lettori non entrano (e quindi prima o poi terminano e lasciano il posto ad uno scrittore). Renzo (talk) 17:57, 13 November 2016 (CET)


Ho pensato al caso limite seguente: Supponiamo che ci siano dei lettori che stanno leggendo e ad un certo punto uno scrittore chiede di scrivere. 

         
       void startread(void) {
    // <await nw == 0 -> nr++>
    semaphore_P(mutex);
    if (numberOfWriters > 0 || waitingWriters>0) {
        waitingReaders++;   //Nuovo scrittore (t1)
        semaphore_V(mutex);
        semaphore_P(ok2read);
        waitingReaders--;
    }
    numberOfReaders++;
    w_last=0;
    printf("NR %d - NW %d - WR %d - WW %d \n", numberOfReaders, numberOfWriters, waitingReaders, waitingWriters);
   if (waitingReaders > 0 )   //Vecchio scrittore(t1)
        semaphore_V(ok2read);
    else
        semaphore_V(mutex);
}

Non appena lo scrittore rilascia il mutex, un nuovo lettore chiede di leggere (e si addormenterà). Un lettore (lento) che era riuscito a entrare nel segmento startofread prima che lo scrittore entrasse in startofwrite, continua a leggere e risveglia uno dei nuovi lettori. Se i lettori continuano a richiedere di leggere continuamente, verranno addormentati e subito risvegliati.

E' da considerarsi possibile? --GabrieleCalarota (talk) 19:11, 13 November 2016 (CET)

Suppongo che "un nuovo scrittore chiede di leggere" si aun refuso e sia da intendere "un nuovo lettore chiede di leggere" (altrimenti ci sono crisi di identità) e che "startofread" significhi "startread" e "startofwrite" sia "startwrite". La "startread" viene eseguita in mutua esclusione, quindi non ci puo' essere "un lettore lento che sia riuscito ad entrare" nella funione startread. Se ha superato la P(mutex) iniziale o e' bloccato sulla ok2read o e' entrato. Renzo (talk) 19:37, 13 November 2016 (CET)

pali

#!/usr/bin/env python3

import threading
import time
import logging
import random
from monitor import monitor, condition, entry

class safeprint(monitor):
	def __init__(self):
		super().__init__()

	@entry
	def print(self, *args,**kwargs):
		print(*args,**kwargs)

safeprint = safeprint().print

class polimon(monitor):
	vsig = [0,0,0,0,-1,4,3,2,1,0]
	vwait = [0,1,2,3,4,-1,0,0,0,0]
	def __init__(self):
		super().__init__()
		self.started=set()
		self.state = 0
		self.vcond = [condition(self) for _ in range(5)]
		self.printing = False

	@entry
	def sync(self, i):
		if i not in self.started:
			self.started.add(i)
			if self.printing:
				self.vcond[0].wait()
		else:
			self.printing = False
			nextsig = polimon.vsig[self.state]
			if nextsig >= 0:
				self.vcond[nextsig].signal()
			self.state = (self.state + 1) % 10
			nextwait = polimon.vwait[self.state]
			if nextwait >= 0:
				self.vcond[nextwait].wait()
		self.printing = True

def client(poli,i):
	for _ in range(10):
		time.sleep(random.random() * 0.5)
		poli.sync(i)
		safeprint(i)

if __name__ == "__main__":
	cli=[]
	poli = polimon()
	for i in range(10):
		p=threading.Thread(name='cli'+str(i), target=client, args=(poli,i))
		p.deamon=True
		p=cli.append(p)
	for i in range(10):
		cli[i].start()
	for i in range(10):
		cli[i].join()
Retrieved from "https://so.v2.cs.unibo.it/wiki/index.php?title=Zibaldone&oldid=1881"