Prove scritte 2017

Esame 11/09/2017

2017.09.11.tot.pdf

Esercizio c.1

monitor crossing

ok2dir[4];     //NESW
bool busy = false;

pe entra(int dir)
   if (busy)
      ok2dir[dir].wait();
   busy = true;


pe esci(int dir)
   busy = false;
   ok2dir[(dir + 1) % 4].signal();
   if (!busy)
      ok2dir[(dir + 2) % 4].signal();
   if (!busy)
      ok2dir[(dir + 3) % 4].signal();
   if (!busy)
      ok2dir[(dir + 4) % 4].signal();  //dir

//alternativa più compatta
pe esci(int dir)
   busy = false;
   for (i = 0; i < 4; i++)
   if (!busy)
      ok2dir[(dir + i + 1) % 4].signal();

Soluzione proposta 2

Soluzione proposta da LLibera e corretta da Flecart

const int N_DIRECTION = 4;

// assumo N = 0, E = 1, S = 2, W = 3, oppure shiftati ciclicamente, è equivalente

monitor crossing {
	bool free;										//l'incrocio è libero?
	int num_waiting[N_DIRECTION];
	condition okToCross[N_DIRECTION];				//free == True
	
	crossing() {
		free = True;								//parto con l'incrocio libero
		for (int i = 0; i < N_DIRECTION; i++) {
			num_waiting[i] = 0;
		}
	}

	procedure entry enter(int direction) {
		if(!free) {									//se l'incrocio non è libero
			num_waiting[direction]++;
			okToCross[direction].wait();			//aspetto nella mia direzione
			num_waiting[direction]--;
		}
													//ora sono sicurə che sia libero
		free = False;								//quindi lo dichiaro occupato
	}

	procedure entry exit(int direction) {
													//non devo aspettare niente per liberare l'incrocio
		free = True;								//lo dichiaro libero
		
		for (int i = 0; i < N_DIRECTION; i++) {
			int curr_dir = (direction + i + 1) % N_DIRECTION;
			if (num_waiting[curr_dir] > 0) {
				okToCross[curr_dir].signal();
				break;	// l'onere di risvegliare gli altri è stato passato al nuovo processo risvegliato, quindi esco.
			}
		}
	}
}

Esercizio c.2 (da controllare)

// server[] = array contenente il PID di tutti i server

#define BROADCAST server[0]

server[0]
{
    while(true)
    {
        <msg, sender> = arecv(*); // ricevo il messaggio
        if (sender == BROADCAST)
            print(msg); // se il messaggio l'ho ricevuto da me stesso allora lo stampo
        else
            asend(*, <msg, getpid()>); // se il messaggio l'ho ricevuto da un client o da un altro server lo inoltro a tutti i server (compreso me stesso)
    }
}

server[x] // x = 1...N-1
{
    while(true)
    {
        <msg, sender> = arecv(*); // ricevo il messaggio
        if (sender == BROADCAST)
            print(msg); // se il messaggio l'ho ricevuto dal server[0] allora lo stampo
        else
            asend(BROADCAST, <msg, getpid()>) // se il messaggio l'ho ricevuto da un client lo inoltro al server[0]
    }
}

Soluzione proposta 2

Soluzione proposta da Flecart Soluzione corretta da Flecart friend

process server_0 {

        while (true) {
                <msg, sender> = arecv(ANY);
                for (int i = 1 ; i < N; i++) {
                        asend(<msg, 0>, server[i]);
                        while(true){
                          msg = arecv(server[i]); // così so che tutti abbiano stampato.
                          if(msg==ACK)
                            break
                          asend(msg,server[0]);
                        }
                }
                print(msg);
        }
}

process server_[i=1 to N - 1] {
        while (true) {
                <msg, sender> = arecv(ANY);
                if (sender == 0) {
                        print(msg);
                        asend(ACK, server[0]);
                } else {
                        asend(<msg, i>, server[0]);
                }
        }
}

Esame 17/07/2017

2017.07.17.tot.pdf

Esercizio c.1

monitor conf {
        condition finished;
        condition ready2present[max];
        bool arrived[max] = false;
        bool giachiamato[max] = false;

        entry chiama(chiamato){
        if(arrived[chiamato] == true)
                ready2present[chiamato].signal;
                finished.wait;
                return true;
        else
                giachiamato[chiamato]= true
                return false;
        }

        entry arrivato(nome){
                if(giachiamato[nome] == true)
                        return  false;

                arrived[nome] = true;
                ok2present[nome].wait;
                return true;
        }

        entry finepresentazione(nome){
                finished.signal;
        }
}

Esercizio c.2 (da controllare)

controllata da LiberaL 14:26, 26 May 2023 (CEST) l'implementazione fornita gestisce solo il caso di arecv(ANY) e non arecv(mittente)

si, è possibile: 

Implementare asend e arecv date bsend e brecv

asend(pid_t dst, msg_type msg){
    bsend (<dst, msg>);
}

arecv(*){
  do {
    <dst, msg> = brecv(*);
  } while (dst != getpid())
  return msg;
}

propongo (LiberaL 13:11, 27 May 2023 (CEST)) quindi questa implementazione con gestione arecv da mittente specificato (sempre da controllare)

//il messaggio mandato è la tripla <destinatario, mittente, messaggio>

asend(pid_t dst, msg_type msg){
    bsend (<dst, getpid(), msg>);
}

Queue of <pid_t, msg_type> db; //nota: salvo qui solo se il messaggio è per me, quindi dest non mi serve
arecv(pid_t sender) {

  //devo controllare se nella coda ho già ricevuto il messaggio da quel mittente, ovvero mentre aspettavo un messaggio da qualcun'altro
  //db.get(sender) cerca una tripla il cui mittente è sender
  //se trova il messaggio lo rimuove anche dal db.
  //db.get(ANY) ritorna (ed elimina da db) il primo che trova (FIFO), e if(db.isEmpty()) return NULL;

  if( ( <mit, msg> = db.get(sender) ) != NULL ) //se lo trova
    return msg;
  bool message_for_me;
  do {
    <dst, mit, msg> = brecv(*);                 //ricevo
    message_for_me = (dst == getpid());         //il messaggio è per me?
    if( message_for_me ) {
      if ( mit == sender || sender == ANY )     //se devo ritornare il messaggio
        break;     //esci dal while
      else                                      //se devo salvarlo (sender specificato e messaggio per me)
        //devo mettere in db i messaggi di altri mittenti, ricevuti quando ne aspettavo uno da un mittente specificato
        db.add(<mit, msg>);
    }
  } while (!message_for_me)
  return msg;
}

Esame 19/06/2017

2017.06.19.tot.pdf

Esercizio c.1 (da controllare)

• Mi sembra che ci sia un errore per il giodice, potrebbe succedere in un caso che il wait non si risvegli mai Flecart (talk) 15:38, 19 January 2023 (CET)

#define NATLETI n

condition ok2lancia[NATLETI];
condition ok2giudice;

int counter[NATLETI];
int ultimo_tiro;
float registro[NATLETI][3];

Procedure entry: boolean pronto(int i)
{
    if(!(i == 0 && counter[i] == 0)) // se è il primo lancio non devo metterlo in wait
        ok2lancia[i].wait()
    if(counter[i] < 3)
        return true;
    else
        return false;
}

Procedure entry: void lanciato (int i)
{
    counter[i]++;
    ultimo_tiro = i;
    ok2giudice.signal();
}

Procedure entry: int lanciofatto()
{
    ok2giudice.wait()
    if(ultimo_tiro == NATLETI-1 && counter[0] == 3)
        return -1;  // devo invalidare la condizione per uscire dal while, quindi se nessuno deve più lanciare ritorno -1
    else
        return ultimo_tiro;
}

Procedure entry: void registraechiama(int i, float m)
{
    registro[i][counter[i]-1] = m; // il secondo indice indica l'iesimo lancio -1 (perchè iniziamo a contare da zero)
    if(i == NATLETI-1) // se ha appena tirato l'ultimo atleta non posso dare il via a NATLETI (perchè non esiste), quindi faccio ricominciare il giro
        ok2lancia[0].signal();
    else
        ok2lancia[i+1].signal();
}

Procedure entry: int classifica()
{
    int best[NATLETI];
    for(int i = 0; i < NATLETI; i++)
    {
        for(int j = 0; j < 3; j++)
        {
            if(registro[i][j] > best[i])
                best[i] = registro[i][j];
        }
    }
    best.sort_in_descending_order(); // supponiamo nel nostro pseudolinguaggio esista una funzione di ordinamento qualunque
    return best;
}

Esame 29/05/2017

2017.05.29.tot.pdf

Esercizio c.1

condition okpartita
condition ok2chiama
condition ok2punteggio
condition ok2run[2][MAX]
int numpronti
int punteggio[2]
boolean partita=false
boolean partitafinita=false
chiamati = []
contabandiera[2]
int winner

entry nuovapartita():
{
    punteggio[A] = punteggio[B] = 0;
    numpronti = 0;
    partita=true;
    okpartita.signal()
    chiamati = [];
}
entry chiama(l):
{
    if (numpronti<2*MAX)
    {
        ok2chiama.wait();
    }
    chiamati = l;
    contabandiera[A] = contabandiera[B] = 0
    winner = -1;
    for (s in n)
    {
        ok2run[A][s].signal();
        ok2run[B][s].signal()
    }
    ok2punteggio.wait();
    punteggio[winner++]
    if (max(punteggio) == 10)
    {
        partitafinita = true;
        for (s in A,B)
        {
            for (n in range(MAX))
            {
                ok2run[s][n].signal();
            }
        }
    }
    return punteggio;
}
entry pronto(s, n):
{
    if (partitafinita) return 1;
    if (!partita)
    {
        okpartita.wait();
    }
    numpronti++;
    if (numpronti>=2*MAX)
    {
        ok2chiama.signal();
    }
    if (!(n in chiamati))
    {
        ok2run[s][n].wait();
    }
    numpronti--;
    return 0 if partita else 1;
}
allabandiera(s, n):
{
    contabandiera[s]++;
    if (winner == -1 && contabandiera[s] == len(chiamati))
    {
        winner = s;
    }
    if (contabandiera[A] == len(chiamati) && contabandiera[B] == len(chiamati))
    {
        ok2punteggio.signal();
    }
}

casi da discutere:    
se arrivano studenti a pronto prima che il prof dichiara nuovapartita succedono guai.