Difference between revisions of "Prove scritte 2022"

From Sistemi Operativi
Jump to navigation Jump to search
 
(17 intermediate revisions by 4 users not shown)
Line 163: Line 163:
 
         waiting.signal();
 
         waiting.signal();
 
     }
 
     }
 +
}
 +
</syntaxhighlight>
 +
 +
 +
== Esercizio c2 ==
 +
 +
[[ 20220906c2 ]]  proposte di soluzione
 +
 +
= Prova 2022/07/20 =
 +
 +
== Esercizio c1 ==
 +
 +
in un porto con una sola banchina utilizzabile occorre caricare cereali sulle navi. I camion portano i cereali al porto. Una sola nave alla volta può essere attraccata al molo, un solo camion alla volta scarica i cereali nella nave.
 +
Il codice eseguito da ogni nave è:
 +
  nave[i] process:
 +
    porto.attracca(capacità)
 +
    porto.salpa()
 +
    ...naviga verso la destinazione
 +
 +
Il codice di ogni camion è:
 +
  camion[j] process:
 +
    while (1):
 +
      quantità = carica_cereali()
 +
      porto.scarica(quantità)
 +
 +
I camion fanno la spola dai depositi alla nave. La nave arriva vuota e può salpare solo se è stata completamente riempita (la somma delle quantità scaricate dai camion raggiunge la capacità indicata come parametro della funzione attracca). Se un camion può scaricare solo parzialmente il suo carico rimane in porto e aspetta di completare l'operazione con la prossima nave che attraccherà al molo.
 +
Scrivere il monitor porto.
 +
 +
=== Soluzione proposta 1 (da controllare) ===
 +
Proposta da [[User: SpookyWiki |SpookyWiki]] ([[User talk:SpookyWiki|talk]]) 14:56, 13 May 2023 (CEST)
 +
 +
<syntaxhighlight lang=C>
 +
 +
// in questa versione, se il remainingSpace è -1 vuol dire che nessuna
 +
//barca è attraccata
 +
monitor porto{
 +
 +
int remainingSpace; // -1 -> non ci sono barche attraccate
 +
bool camionSlotBusy;
 +
condition waiting4slot; //il camion attende di essere preso in carico
 +
condition waiting4dock; //la barca attende il molo
 +
condition waiting4load; //il la barca attende i camion
 +
condition waiting4boat; //i camion attendono una barca
 +
 +
porto {
 +
remainingSpace = -1;
 +
camionSlotBusy = false;
 +
}
 +
 +
procedure entry void attracca(int capacità){
 +
if( remainingSpace >=0 )
 +
wait4dock.wait();
 +
remainingSpace = capacità;
 +
waiting4slot.signal();
 +
}
 +
 +
procedure entry void salpa(){
 +
if( remainingSpace > 0 )
 +
wait4load.wait();
 +
waiting4dock.signal();
 +
}
 +
 +
procedure entry void scarica(quantità){
 +
if( camionSlotBusy )
 +
waiting4slot.wait()
 +
//se non posso scaricare il carico
 +
if( remainingSpace <= 0)
 +
waiting4boat.wait()
 +
 +
int remainingLoad = quantità;
 +
 +
while (remainingLoad > 0){
 +
//il camion si svuota e se ne deve andare
 +
if( remainingSpace >= remainingLoad ) {
 +
remainingSpace -= remainingLoad;
 +
remainingLoad = 0;
 +
if ( remainingSpace == 0)
 +
wait4load.signal();
 +
//il camion non si svuota del tutto e deve rimanere
 +
} else {
 +
remainingLoad -= remainingSpace;
 +
remainingSpace = 0;
 +
waiting4load.signal();
 +
waiting4boat.wait();
 +
}
 +
}
 +
waiting4slot.singal();
 +
 +
}
 +
 
}
 
}
 
</syntaxhighlight>
 
</syntaxhighlight>
Line 440: Line 530:
 
         }
 
         }
 
     }
 
     }
 +
}
 +
</syntaxhighlight>
 +
 +
=== Soluzione proposta 2 (da controllare) ===
 +
Proposta da [[User: SpookyWiki |SpookyWiki]] ([[User talk:SpookyWiki|talk]]) 18:06, 22 May 2023 (CEST)
 +
 +
<syntaxhighlight lang=C>
 +
monitor delay {
 +
Map<pid_t, int tickleft> tickmap;
 +
pid_t last;
 +
int blocked;
 +
int quit;
 +
condition wait4ticks;
 +
 +
delay() {
 +
last = null;
 +
blocked = 0;
 +
quit = 0;
 +
}
 +
 +
procedure entry int wait_tick(int nticks) {
 +
blocked++;
 +
if( nticks > 0 ) { // se un proc entra con nticks = 0 esce direttamente
 +
pid_t mypid = getpid();
 +
tickmap.add(mypid, nticks);
 +
last = mypid
 +
while ( tickmap[mypid].tickleft > 0) {
 +
waiting4ticks.wait()
 +
tickmap[mypid].tickleft --
 +
if( last != mypid )
 +
waiting4ticks.signal();
 +
}
 +
map.remove(mypid);
 +
if( last == mypid )
 +
last = tickleft.getLast(); //se la map è vuota, assumo ritorni null
 +
}
 +
quit++;
 +
return blocked;
 +
}
 +
 +
procedure entry void tick() {
 +
waiting4ticks.signal();
 +
blocked -= quitted;
 +
quit = 0;
 +
}
 
}
 
}
 
</syntaxhighlight>
 
</syntaxhighlight>
Line 508: Line 643:
 
</syntaxhighlight>
 
</syntaxhighlight>
  
 +
=== Soluzione proposta 2 (da controllare) ===
 +
Proposta da [[User: SpookyWiki |SpookyWiki]] ([[User talk:SpookyWiki|talk]]) 18:42, 22 May 2023 (CEST)
 +
 +
<syntaxhighlight lang=C>
 +
Map<<pid_t dest, pid_t mitt>, List<int> msgs> db;
 +
 +
void asend(msg_t msg, pid_t dest) { //dobbiamo salvarci l'ordine
 +
pid_t mypid = getpid();
 +
int progressivo;
 +
if (db[<dest, mypid>] == null) {
 +
db.add(<dest, mypid>);
 +
db[<dest, mypid>].msgs.add(0)
 +
progressivo = 0;
 +
} else {
 +
progressivo = db[<dest, mypid>].msgs.getLast() +1;
 +
db[<dest, mypid>].msgs.add(progressivo);
 +
}
 +
nfasend(<msg, progressivo>, dest);
 +
}
 +
 +
msg_t arecv(pid_t sender) {
 +
pid_t mypid = getpid();
 +
int progressivo = db[<mypid, sender>].msgs[0];
 +
msg, prog = nfarecv(sender);
 +
while ( prog != progressivo) {
 +
nfasend(<msg, progressivo>, mypid);
 +
msg, prog = nfarecv(sender);
 +
}
 +
db[<mypid, sender>].msgs.remove(0);
 +
return msg;
 +
}
 +
</syntaxhighlight>
  
 
= Prova 2022/02/14 =
 
= Prova 2022/02/14 =
Line 553: Line 720:
 
</syntaxhighlight>
 
</syntaxhighlight>
  
 +
== Esercizio c2 ==
 +
 +
Dato un servizio di message passing asincrono implementare un servizio di message passing sincrono
 +
con selezione ordinata che ha la seguente interfaccia:
 +
 +
void snsend(msgtype msg, pid_t dest);
 +
msgtype snrecv(pid_t sender, int n);
 +
 +
La funzione snrecv deve restituire l'n-mo messaggio proveniente dal mittente specificato (che può essere any). Se n ==
 +
0 restituisce l'ultimo messaggio. Esempi:
 +
m = snrecv(tizio, 1): restituisce il primo messaggio da tizio (attende se non ve ne sono)
 +
m = snrecv(ANY, 42): restituisce il 42-mo messaggio da chiunque (attende se ci sono meno di 42 messaggi in attesa di
 +
essere ricevuti)
 +
m = snrecv(caio, 0): restituisce l'ultimo messaggio ricevuto da Caio (attende se non ci sono messaggi pendenti da Caio)
 +
m = snrecv(ANY, 0): restituisce l'ultimo messaggio ricevuto, indipendentemente dal mittente.
 +
 +
=== Proposta di soluzione 1 (da controllare)===
 +
* Proposta da [[User:Barba|zBarba]] ([[User talk:Barba|talk]]) 10:54, 21 January 2024 (CET)
 +
 +
<syntaxhighlight lang="C">
 +
// int db.count(pid_t sender): conta quanti messaggi inviati da sender sono presenti nel db. Se sender == ANY allora li conta tutti
 +
// msg_t db.extract(pid_t sender,int  n): ritorna l'n-mo mesaggio del db inviato da sender. Se sender == ANY allora ritorna l'n-mo elemento
 +
 +
void snsend(msgtype msg, pid_t dest){
 +
    asend(<msg, getpid()>, dest)
 +
    do{
 +
        <m, snd> = arecv(dest)
 +
        db.add(<m, snd>)
 +
    }while(m != ACK)
 +
    db.extract(dest, db.count(dest))
 +
}
 +
 +
msgtype snrecv(pid_t sender, int n){
 +
    if(n == 0){
 +
        n = db.count(sender)
 +
    }
 +
 +
    while(db.count(sender) < n){
 +
        <m, snd> = arecv(sender)
 +
        db.add(<m, snd>)
 +
    }
 +
    <m, snd> = db.extract(sender, n)
 +
    asend(<ACK, getpid()>, snd)
 +
    return m
 +
}
 +
</syntaxhighlight>
  
 
= Prova 2022/01/17 =
 
= Prova 2022/01/17 =
Line 558: Line 771:
 
== Esercizio c1 ==
 
== Esercizio c1 ==
  
−
Scrivere il monitor multibuf che implementi un buffer limitato (MAX elementi) di oggetti di tipo T che
+
Scrivere il monitor multibuf che implementi un buffer limitato (MAX elementi) di oggetti di tipo T che
 
implementi le seguenti procedure entry:
 
implementi le seguenti procedure entry:
−
void add(int n, T objexts[]);
+
  void add(int n, T objexts[]);
−
void get(int n, T objects[]);
+
  void get(int n, T objects[]);
 
La funzione add deve aggiungere al buffer gli n oggetti passati col parametro objects. La funzione get deve predere
 
La funzione add deve aggiungere al buffer gli n oggetti passati col parametro objects. La funzione get deve predere
 
dal buffer in modalità FIFO i primi n elementi presenti nel buffer e copiarli negli elementi del vettore objects.
 
dal buffer in modalità FIFO i primi n elementi presenti nel buffer e copiarli negli elementi del vettore objects.
Line 582: Line 795:
 
int i, j;
 
int i, j;
 
int free;
 
int free;
 +
queue<int,cond> add_queue;
 +
 +
queue<int,cond> get_queue;
  
 
multibuf {
 
multibuf {
Line 632: Line 848:
  
 
} // multibuf
 
} // multibuf
 +
</syntaxhighlight>
 +
 +
== Esercizio c2 ==
 +
Un servizio di message passing sincrono senza selezione del mittente prevede una API con due funzioni:
 +
  sasend(msg_t msg, pid dest);
 +
  msg_t sarecv(void);
 +
La funzione sarecv restituisce il primo messaggio ricevuto da qualsiasi mittente ed è bloccante se non ci sono
 +
messaggi pendenti. la funzione sasend si blocca fino a quando il messaggio msg non viene ricevuto dal processo dest.
 +
Dato quindi un servizio di message passing sincrono senza selezione del mittente implementare un servizio di
 +
message passing sincrono (standard, quello definito nel corso) senza fare uso di processi server.
 +
 +
=== Soluzione proposta 1 (da controllare) ===
 +
* proposta da [[User:Flecart|Flecart]] ([[User talk:Flecart|talk]]) 18:25, 16 January 2023 (CET)
 +
* Errore, ssend in questo caso non è sincrono, bisognerebbe uscire con l'ack dal receiver [[User:Flecart|Flecart]] ([[User talk:Flecart|talk]]) 22:56, 16 January 2023 (CET)
 +
<syntaxhighlight lang="C">
 +
 +
ssend(msg_t msg, pid dest) {
 +
sasend(<msg, getpid()>, dest);
 +
}
 +
 +
 +
// variabili interne di srecv
 +
queue<msg_t> msgs[MAX_PROC];
 +
 +
// suppongo non ci sia il caso in cui sender = ANY.
 +
// nel caso ci fosse la necessità, si dovrebbe creare una altra struttura di dati
 +
// che ordini globalmente il messaggio che sia arrivato prima.
 +
msg_t srecv(pid sender) {
 +
if (msgs[sender].len() > 0) {
 +
return msgs[sender].dequeue();
 +
}
 +
 +
while (true) {
 +
<msg, pid> = sarecv();
 +
if (pid == sender) {
 +
return msgs[pid].dequeue();
 +
} else {
 +
msgs[pid].enqueue(msg);
 +
}
 +
}
 +
}
 +
 +
</syntaxhighlight>
 +
 +
=== Soluzione proposta 2 (da controllare) ===
 +
 +
proposta da [[User:gio|Flecart Friend]] cedo la proprità intellettuale di questa soluzione a flecart
 +
 +
<syntaxhighlight lang="C">
 +
// mem è condivisa tra ssend e srecv di ogni processo
 +
// essendo che un processo può solo mandare o ricevere alla volta
 +
// non abbiamo bisogno di cs
 +
 +
// inizializzati tutti a NULL
 +
msg_t mem[MAXPID];
 +
// in mem ci basta un messaggio per PID perchè un pid può aver mandato al
 +
// massimo un messaggio essendo che sono bloccanti la send e la recive
 +
 +
void ssend(msg_t msg, pid dest) {
 +
  sasend(<getpid(),msg>,dest);
 +
  while(true){
 +
    <form_c,msg>=sarecv();
 +
    // dovrebbe essere ovvio che se è from c allora il msg dovrebbe essere un
 +
    // ack perchè se c avesse mandato un messaggio diverso vorrebbe dire che
 +
    // sta facendo una send e se i due processi si fanno una send allora c'è
 +
    // deadhlock
 +
    if(from_c == dest && msg == ACK){
 +
      break;
 +
    }else{
 +
      mem[from_c]=msg;
 +
    }
 +
  }
 +
}
 +
 +
msg_t srecv(pid from) {
 +
  if(mem[from]!=NULL){
 +
    t=mem[from];
 +
    mem[from]=NULL;
 +
    ssend(ACK,from);
 +
    return t;
 +
  }
 +
  while(true){
 +
    <form_c,msg>=sarecv();
 +
    if(from_c==from){
 +
      ssend(ACK,from);
 +
      return msg;
 +
    }else{
 +
      mem[from_c].push(msg);
 +
    }
 +
  }
 +
}
 +
 
</syntaxhighlight>
 
</syntaxhighlight>

Latest revision as of 10:55, 21 January 2024

Prova 2022/09/06

Esercizio c1

Esercizio c.1: I bit di un numero intero rappresentano condizioni di un sistema. Se lo stato attuale è 6 (0110) vuole dire che attualmente sono vere le condizioni 2 (0010) e 4 (0100). Scrivere un monitor bitcond che fornisca le seguenti procedure entry: void set(int bit2set); accende nello stato attuale i bit di bit2set void unset(int bit2unset) spegne nello stato attuale i bit di bit2unset void statuswait(int bit2wait) attende che lo stato attuale soddisfi tutti le condizioni indicate in bit2wait (cioè che tutti i bit in bit2wait siano accesi nello stato attuale). Le richieste statuswait devono essere servite in ordine FIFO (cioè un processo anche se sono presenti tutte le condizioni necessarie deve attendere se un processo che ha chiamato statuswait prima è in attesa). Lo stato iniziale è zero (nessuna risorsa disponibile)

Soluzione proposta 1

class bitcond{
  int bitmap;
  int lastBitmask;
  int has=0;
  
  condition waiting;
  condition c;

  void set(int i){
    bitmap|=i; 
      if(bitmap&lastBitmask == bitmap) c.signal();
  }
  void unset(int i){
    bitmap&=~i; 
  }
  void statuswait(int i){
    has++; 
    if(has>1){
      waiting.wait();
    }

    if(!(bitmap&i==i)){
      lastBitmask=i;
      c.wait();
    }

    waiting.signal();
    has--;
  }
  bitcond(){
    bitmap = 0;
  }
}

Soluzione proposta 2

Proposta da Flecart (talk) 12:06, 14 January 2023 (CET) 

const int int_size = 32;

class monitor {
    int value;
    condition bitset[int_size];

    int numstatuswaiting;
    condition waiting;
    
    monitor() {
        value = 0;
    }
    
    /// guarda se il bit n-significativo è settato in from
    bool nbit(int from, int n) {
        return (from & (1 << n)) != 0
    }

    void entry set(int bit2set) {
        value |= bit2set;

        for (int i = 0; i < 32; i++) {
            if (nbit(value, i))
                bitset[i].signal();
        }
    }

    void entry statuswait(int bit2wait) {
        // in questo modo solamente un singolo processo è dentro ad aspettare
        // che tutte le condizioni siano rispettate
        if (numstatuswaiting > 0)
            waiting.wait();
        
        numstatuswaiting++;
        int i = 0;
        while(i < 32) {
            if (nbit(bit2wait, i) && !nbit(value, i)) {
                bitset[i].wait();

                // ricomincia a guardare tutti i bit da zero, perché
                // nel frattempo potrebbero essere cambiati.
                // -1 così con l'istruzione successiva diventa 0
                i = -1; 
            }
            i++;
        }
        
        numstatuswaiting--;
        waiting.signal();
    }
}

Soluzione proposta 3

Proposta da Flecart (talk) 12:07, 14 January 2023 (CET) questa è la soluzione più brutta, ma dovrebbe andare. 

const int int_size = 32;

class monitor {
    int value;
    condition status;

    int numstatuswaiting;
    condition waiting;
    
    monitor() {
        value = 0;
    }
    
    /// guarda se il bit n-significativo è settato in from
    bool nbit(int from, int n) {
        return (from & (1 << n)) != 0
    }

    void entry set(int bit2set) {
        value |= bit2set;
        status.signal();
    }


    void entry unset(int bit2unset) {
        value = (value & ~bit2unset);
    }

    void entry statuswait(int bit2wait) {
        // in questo modo solamente un singolo processo è dentro ad aspettare
        // che tutte le condizioni siano rispettate
        if (numstatuswaiting > 0)
            waiting.wait();
        
        numstatuswaiting++;
        while(true) {
            if ((value & bit2wait) == bit2wait) 
                break;
            else 
                status.wait();
        }
        numstatuswaiting--;
        waiting.signal();
    }
}


Esercizio c2

20220906c2 proposte di soluzione

Prova 2022/07/20

Esercizio c1

in un porto con una sola banchina utilizzabile occorre caricare cereali sulle navi. I camion portano i cereali al porto. Una sola nave alla volta può essere attraccata al molo, un solo camion alla volta scarica i cereali nella nave. Il codice eseguito da ogni nave è: 

  nave[i] process:
    porto.attracca(capacità) 
    porto.salpa()
    ...naviga verso la destinazione

Il codice di ogni camion è: 

 camion[j] process: 
   while (1):
     quantità = carica_cereali()
     porto.scarica(quantità)

I camion fanno la spola dai depositi alla nave. La nave arriva vuota e può salpare solo se è stata completamente riempita (la somma delle quantità scaricate dai camion raggiunge la capacità indicata come parametro della funzione attracca). Se un camion può scaricare solo parzialmente il suo carico rimane in porto e aspetta di completare l'operazione con la prossima nave che attraccherà al molo. Scrivere il monitor porto.

Soluzione proposta 1 (da controllare)

Proposta da SpookyWiki (talk) 14:56, 13 May 2023 (CEST) 

// in questa versione, se il remainingSpace è -1 vuol dire che nessuna 
	//barca è attraccata
monitor porto{

	int remainingSpace; // -1 -> non ci sono barche attraccate
	bool camionSlotBusy;
	condition waiting4slot; //il camion attende di essere preso in carico
	condition waiting4dock; //la barca attende il molo
	condition waiting4load; //il la barca attende i camion
	condition waiting4boat; //i camion attendono una barca

	porto {
		remainingSpace = -1;
		camionSlotBusy = false;
	}

	procedure entry void attracca(int capacità){
		if( remainingSpace >=0 )
			wait4dock.wait();
		remainingSpace = capacità;
		waiting4slot.signal();
	}

	procedure entry void salpa(){
		if( remainingSpace > 0 )
			wait4load.wait();
		waiting4dock.signal();
	}

	procedure entry void scarica(quantità){
		if( camionSlotBusy ) 
			waiting4slot.wait()
		//se non posso scaricare il carico
		if( remainingSpace <= 0)
			waiting4boat.wait()

		int remainingLoad = quantità;

		while (remainingLoad > 0){
			//il camion si svuota e se ne deve andare
			if( remainingSpace >= remainingLoad ) {
				remainingSpace -= remainingLoad;
				remainingLoad = 0;
				if ( remainingSpace == 0)
					wait4load.signal();
			//il camion non si svuota del tutto e deve rimanere
			} else {
				remainingLoad -= remainingSpace;
				remainingSpace = 0;
				waiting4load.signal();
				waiting4boat.wait();
			}
		}
		waiting4slot.singal();
		
	}

}

Prova 2022/06/21

Esercizio c1

Scrivere il monitor collocamento: 

 void cercolavoro(char *nome, char *skill)
 void char *assumo(char * skill)

Quando un processo chiama la cercolavoro si mette in attesa di una richiesta di lavoro e rimane bloccato nel monitor fino a che non è stato assunto. Nella cercolavoro viene indicato il nome dell'aspirante lavoratore la sua capacità (skill). Un datore di lavoro con necessità di personale chiama la assumo specificando la capacità richiesta. Se c'è in attesa almeno un aspirante lavoratore con quella specifica capacità (uguale valore di skill), il datore di lavoro riceve il nome del nuovo dipendente ed entrambi i processi escono dal monitor. Nel caso non ci siano richieste compatibili il datore di lavoro si blocca nel monitor attendendo un lavoratore con la capacità cercata. Quando arriva il lavoratore che soddisfa le richieste si sbloccano entrambi i processi lavoratore e datore di lavoro. La assumo restituisce in ogni caso il nome del dipendente da assumere.


Soluzione proposta

Soluzione proposta da Flecart (talk) 12:08, 14 January 2023 (CET)

ci potrebbe essere un errore in quanto non è specificato il comportamento della struttura dati in alcune situazioni 

class collocamento{

set<char *, condition> richieste;  // chi assume cerca questa skill
set<char *, char *, condition> ricerche; // nome e skill di chi cerca

char *last_nome;

collocamento {
	last_nome = NULL;
	richieste = set();
	ricerche = set();	
}

void cercolavoro(char *nome, char *skill) {
	datore = richieste.find(skill);  // cerca valutando la prima come chiave
	if (datore != NULL) {
		<skill, cond> = datore;
		richieste.remove(datore);
		last_nome = nome;
		cond.signal();		
	} else {
		condition c = new condition();
		ricerche.insert(nome, skill, c);
		c.wait();
		free(c);
	}
}

void char *assumo(char * skill){
	lavoratore = ricerche.find2(skill); // cerca valutando la seconda come chiave.
	if (lavoratore != NULL) {
		<nome, skill, cond> = lavoratore;
		ricerche.remove(lavoratore);
		cond.signal();
		last_nome = nome;
	} else {
		condition c = new condition();
		richieste.insert(skill, c);
		c.wait();
		free(c);
	}

	return last_nome;
}

}// class collocamento

Soluzione proposta

Soluzione proposta da Flecart Frend, regalo la proprietà intellettuale di questa soluzione a flecart. 

class workdisptcher{

  // la multi map può storare più di un valore per una chiave
  // quando viene richiesta una particolare chiave da in maniera LIFO
  // il risultato
  // es:
  // multi_map<char *,int> lavoratori;
  // lavoratori.insert("prova",2);
  // lavoratori.insert("prova",1);
  // lavoratori.get("prova") == 2
  // lavoratori.remove("prova")
  // lavoratori.get("prova") == 1
  multi_map<char *,(char*,cond)> lavoratori;
  multi_map<char *,cond> posti_aperti;
  char* buffer_name;
  void cercolavoro(char *nome, char *skill){
    if(posti_aperti.find(skill)){
      auto entry =posti_aperti.get(skill);
      posti_aperti.remove(entry);
      buffer_name=name;
      entry.1.signal();
    }else{
      cond c= new cond();
      lavoratori.insert(skill,(nome,c)) ;
      c.wait();
      free(c);
    }
  }
  void char *assumo(char * skill){
    if(lavoratori.find(skill)){
      auto entry =lavoratori.get(skill);
      posti_aperti.remove(entry);
      auto [nome,cnd] = entry.1;
      cond.signal();
      return nome;
    }else{
      cond c= new cond();
      posti_aperti.insert(skill,c) ;
      c.wait();
      free(c);
      return buffer_name;
    }

  }

}

Esercizio c2

Un servizio viene fornito in modalità client-server usando message passing asincrono. Al fine di aumentare l'efficienza si decide di usare molti server e un processo dispatcher in grado di distribuire le richieste agli N server. Quando un processo server è libero riceve dal dispatcher la prossima richiesta da elaborare: codice di ogni client (tanti!): ..... 

 asend(<getpid(), request>, dispatcher)
 result = arecv(dispatcher)

server process[i], i = 0, ..., N-1: 

request = arecv(dispatcher)
result = compute(request)
asend(<getpid(), result>, dispatcher)

Scrivere il processo dispatcher. (il dispatcher conosce i pid di tutti i server).

Soluzione proposta (sbagliata)

Soluzione proposta da Flecart

Questo esercizio è stato corretto tempo fa in classe dal professore, **non è completamente corretto** se si vuole provare a correggerlo alla fine dell'esercizio c'è scritto cos'è sbagliato. 


extern int N;
process dispatcher() {
    // indice che tiene conto a quale server dover mandare
    // per semplicità supponiamo che i server abbiano PID
    // da 0 a N - 1
    int i = 0; 

    // mappa server a pid del processo che lo ha richiesto.
    // chiave: pid del server
    // value: queue richiesta dispatchata al server in chiave
    map<int, queue<int>> mapper; 
    while (true) {
        res = arecv(ANY);
        
        // in questa parte l'importante è sapere
        // se la richiesta proviene dal  server o da un altro
        // processo, ho assunto che la disambiguazione 
        // fosse immediata, un altro modo per checkare questo
        // è vedere se il PID del messaggio rientri fra quelli
        // noti al dispatcher.
        if (<pid, request> = res) {
            mapper[i].enqueue(pid);
            asend(request, i /*il i-esimo server*/);
            i++;
            i %= N;
        } else if (<pid, response> = res) {
            requester_pid = mapper[pid].dequeue();
            asend(response, requester_pid);
        }
    }
}


l'es è sbagliato perchè dovrei mandare ai server liberi, non a round-robin Flecart (talk) 15:52, 14 January 2023 (CET)

Soluzione proposta 2

Soluzione proposta da Giovanni Spadaccini 

dispatcher{
  queue<<pid,request>> work;
  queue<pid> freeserver;
  map<pid,pid> map_server_to_client;
  while(true){
    <pid,message>=arecv(ANY);
    if pid in servers{
      client=map_server_to_client.get(pid);
      map_client_to_server.remove(pid);
      freeserver.push(pid);
      asend(<message>,client);
    }else{
      work.push(<pid,message>);
    }
    while !freeserver.empty() and !work.emtpy(){
      server_pid = freeserver.pop();
      <client,msg> = work.pop();
      map_server_to_client.insert(server,client);
      asend(msg,server_pid);
    }
  }
}

Prova 2022/06/01

Esercizio c1

Scrivere il monitor delay che fornisce due procedure entry: 

 int wait_tick(int nticks)
 void tick(void)

La procedure entry tick è pensata per essere richiamata periodicamente (es. ogni secondo o ora o giorno) da un processo. Quando un processo chiama la wait_tick deve attendere un numero di chiamate della tick pari al parametro nticks. Per esempio se un processo chiama wait_tick(2) deve fermarsi e verrà riattivato alla seconda successiva chiamata di tick. La funzione wait_tick ha come valore di ritorno il numero di processi che erano bloccati al momento della tick che ha sbloccato il chiamante. Esempio: P chiama wait_tick(2) e si blocca. Q chiama wait_tick(3) e si blocca. T chiama tick() non succede nulla. R chiama wait_tick(2) e si blocca. T chiama tick(), viene sbloccata la wait_tick di P e il valore ritornato è 3. T chiama tick(), vengono sbloccate le wait_tick di Q e R e il valore ritornato per entrambi i processi è 2

Soluzione proprosta 1 (da controllare)

Soluzione proposta da Flecart 

class MonitorDelay {
    int curr_time;
    int waiting_num;

    // min heap con il tempo di sblocco dei processi e la condizione su cui è fermato
    // il tempo di sblocco minore è messo in cima alla heap
    // la sintassi con pair è ispirata alla std::pair di c++
    heap<pair<int, condition>> waiting; 

    void init() {
        curr_time = 0;
        waiting = heap<pair<int, condition>>();
    }

    int entry wait_tick(int nticks) {
        if (nticks <= 0) {
            return waiting.size();
        } else {
            condition c = new condition();
            waiting.insert(make_pair(nticks + curr_time, c));
            c.wait();
            free(c);
        }
        return waiting_num;
    }


    void entry tick(void) {
        waiting_num = waiting.size();
        curr_time++;

        while (waiting.head().first <= curr_time) {
            condition c = waiting.head().second;
            waiting.deleteHead();
            c.signal();
        }
    }
}

Soluzione proposta 2 (da controllare)

Proposta da SpookyWiki (talk) 18:06, 22 May 2023 (CEST) 

monitor delay {
	Map<pid_t, int tickleft> tickmap;
	pid_t last;
	int blocked;
	int quit;
	condition wait4ticks;
	
	delay() {
		last = null;
		blocked = 0;
		quit = 0;
	}

	procedure entry int wait_tick(int nticks) {
		blocked++;
		if( nticks > 0 ) { // se un proc entra con nticks = 0 esce direttamente
			pid_t mypid = getpid();
			tickmap.add(mypid, nticks);
			last = mypid
			while ( tickmap[mypid].tickleft > 0) {
				waiting4ticks.wait()
				tickmap[mypid].tickleft --
				if( last != mypid )
					waiting4ticks.signal();
			}
			map.remove(mypid);
			if( last == mypid )
				last = tickleft.getLast(); //se la map è vuota, assumo ritorni null
		}
		quit++;
		return blocked;
	} 

	procedure entry void tick() {
		waiting4ticks.signal();
		blocked -= quitted;
		quit = 0;
	}
}

Esercizio c2

Consegna

Esercizio c.2: Un servizio di message passing asincrono non fifo (nfasend/nfarecv) consegna in tempo finito tutti i messaggi spediti ma non è garantito che i messaggi vengano ricevuti nell'ordine nel quale sono stati spediti. 

 void nfasend(msg_t msg, pid_t dest)
 msg_t nfarecv(pid_t sender)

Dato un servizio di message passing asincrono non fifo scrivere una libreria che implementi il servizio di message passing asincrono fifo: 

 void asend(msg_t msg, pid_t dest)
 msg_t arecv(pid_t sender)

Nota: sia il servizio dato (non fifo) sia quello da implementare (fifo) consentono la ricezione solo da mittente specificato (non supportano ANY/*).

Soluzione proposta 1

void nfasend(msg_t msg, pid_t dest);
msg_t nfarecv(pid_t sender);


// array di grandezza di massimi numero di processi, inizializzato a 0
// utilizzato per contare il numero di messaggi inviati a un certo processo.
int num_sender[MAX_PROC];

//RICORDA che ogni sender ha il suo num_sender[...]

void asend(msg_t msg, pid_t dest) {
	src = getpid();
	nfasend(<msg, num_send[dest]>, dest);
	num_sender[dest]++;
}

// molto simile a num_sender, ma è utilizzato per contare il numero di messaggi ricevuti, in ordine.
int num_receiver[MAX_PROC];
// array heap ordinato sul int (per ogni heap in cima c'è il messaggio col minimo int).
min_heap<msg, int> messages[MAX_PROC];

//RICORDA che ogni receiver ha il suo proprio num_receiver[...] e messages[...]

msg_t arecv(pid_t sender) {
	p = getpid();
	
	if (messages[sender].size() > 0 && messages[sender].top() == num_receiver[sender]) {
		(msg, num_mess) = messages[sender].removeTop();
		num_receiver[sender]++;
		return msg;
	}

	(msg, num_mess) = nfarecv(sender);

	while (num_mess != num_receiver[sender]) {
		messages[sender].insert(msg, num_mess);
		(msg, num_mess) = nfarecv(sender);
	}

	num_receiver[sender]++;
	return msg;	
}

Soluzione proposta 2 (da controllare)

Proposta da SpookyWiki (talk) 18:42, 22 May 2023 (CEST) 

Map<<pid_t dest, pid_t mitt>, List<int> msgs> db;

void asend(msg_t msg, pid_t dest) { //dobbiamo salvarci l'ordine
	pid_t mypid = getpid();
	int progressivo;
	if (db[<dest, mypid>] == null) {
		db.add(<dest, mypid>);
		db[<dest, mypid>].msgs.add(0)
		progressivo = 0;
	} else {
		progressivo = db[<dest, mypid>].msgs.getLast() +1;
		db[<dest, mypid>].msgs.add(progressivo);
	}
	nfasend(<msg, progressivo>, dest);
}

msg_t arecv(pid_t sender) {
	pid_t mypid = getpid();
	int progressivo = db[<mypid, sender>].msgs[0];
	msg, prog = nfarecv(sender);
	while ( prog != progressivo) {
		nfasend(<msg, progressivo>, mypid);
		msg, prog = nfarecv(sender);
	}
	db[<mypid, sender>].msgs.remove(0);
	return msg;
}

Prova 2022/02/14

Esercizio c1

Scrivere il monitor semdata che implementi un semaforo con dato. Questa astrazione prevede due operazioni: 

datatype dP(void);
void dV(datatype data);

Non è previsto assegmento di valore iniziale nel costruttore, l'invariante è lo stesso dei semafori (con init = 0): ndP <= ndV (dove ndP e ndV rappresentano rispettivamente il numero di operazioni dP e dV completate. I dati passati come parametro alla dV devono essere memorizzati in ordine LIFO. L'operazione nP restituisce il valore più recente fra quelli memorizzati (e lo cancella dalla struttura dati).

Proposta di soluzione 1

  • Proposta da Flecart (talk) 12:06, 16 January 2023 (CET)
class semdata {

stack<datatype> pila;
condition p_waiting;


semdata() {
	pila = stack();
}

datatype dp(void) {
	if (pila.len() <= 0) {
		p_waiting.wait();
	}	

	return pila.pop();
}

void dV(datatype data) {
	pila.push(data);
	p_waiting.signal();
}

}

Esercizio c2

Dato un servizio di message passing asincrono implementare un servizio di message passing sincrono con selezione ordinata che ha la seguente interfaccia: 

void snsend(msgtype msg, pid_t dest);
msgtype snrecv(pid_t sender, int n);

La funzione snrecv deve restituire l'n-mo messaggio proveniente dal mittente specificato (che può essere any). Se n == 0 restituisce l'ultimo messaggio. Esempi: m = snrecv(tizio, 1): restituisce il primo messaggio da tizio (attende se non ve ne sono) m = snrecv(ANY, 42): restituisce il 42-mo messaggio da chiunque (attende se ci sono meno di 42 messaggi in attesa di essere ricevuti) m = snrecv(caio, 0): restituisce l'ultimo messaggio ricevuto da Caio (attende se non ci sono messaggi pendenti da Caio) m = snrecv(ANY, 0): restituisce l'ultimo messaggio ricevuto, indipendentemente dal mittente.

Proposta di soluzione 1 (da controllare)

  • Proposta da zBarba (talk) 10:54, 21 January 2024 (CET)
// int db.count(pid_t sender): conta quanti messaggi inviati da sender sono presenti nel db. Se sender == ANY allora li conta tutti
// msg_t db.extract(pid_t sender,int  n): ritorna l'n-mo mesaggio del db inviato da sender. Se sender == ANY allora ritorna l'n-mo elemento

void snsend(msgtype msg, pid_t dest){
    asend(<msg, getpid()>, dest)
    do{
        <m, snd> = arecv(dest)
        db.add(<m, snd>)
    }while(m != ACK)
    db.extract(dest, db.count(dest))
}

msgtype snrecv(pid_t sender, int n){
    if(n == 0){
        n = db.count(sender)
    }

    while(db.count(sender) < n){
        <m, snd> = arecv(sender)
        db.add(<m, snd>)
    }
    <m, snd> = db.extract(sender, n)
    asend(<ACK, getpid()>, snd)
    return m
}

Prova 2022/01/17

Esercizio c1

Scrivere il monitor multibuf che implementi un buffer limitato (MAX elementi) di oggetti di tipo T che implementi le seguenti procedure entry: 

 void add(int n, T objexts[]);
 void get(int n, T objects[]);

La funzione add deve aggiungere al buffer gli n oggetti passati col parametro objects. La funzione get deve predere dal buffer in modalità FIFO i primi n elementi presenti nel buffer e copiarli negli elementi del vettore objects. Entrambe le funzioni devono attendere che vi siano le condizioni per poter essere completate: che ci siano n elementi liberi per la add, che ci siano n elementi nel buffer per la get. Non sono ammesse esecuzioni parziali: mentre attendono le rispettive condizioni nessun elemento può essere aggiunto o rimosso dal buffer. La definizione del problema C.1 presenta casi di possibile deadlock?

Soluzione proposta 1

Una situazione di deadlock è quando un add non ha abbastanza per inserire, e get non ha abbastanza da prendere. Se non utilizzo la coda come ho fatto così rischio starvation. 

class multibuf {
	
T buffer[MAX];
int i, j;
int free;
queue<int,cond> add_queue;

queue<int,cond> get_queue;

multibuf {
	i = j = 0;
	free = MAX;
}


void add(int n, T objects[]) {
	if (add_queue.size() > 0 || free < n) {
		condition c = new condition();
		add_queue.enqueue(n, c);
		c.wait();
		free(c);
	}

	for (int k = j; k != (j + n) % MAX; k = (k + 1) % MAX) {
		int other_idx = (k - i) < 0 ? k + MAX - i : k - i;
		buffer[k] = objects[other_idx];
	}
	free -= n;
	j = (j + n) % MAX;
		
	while (get_queue.size() > 0 && get_queue.front() <= MAX - free) {
		n, cond = get_queue.dequeue();
		cond.signal();
	}
}

void get(int n, T objects[]) {
	if (get_queue.size() > 0 || MAX - free < n) {
		condition c = new condition();
		get_queue.enqueue(n, c);
		c.wait();
		free(c);
	}
	
	for (int k = i; k != (i + n) % MAX; k = (k + 1) % MAX) {
		int other_idx = (k - i) < 0 ? k + MAX - i : k - i;
		objects[other_idx] = buffer[k];
	}
	free += n;
	i = (i + n) % MAX;

	while (add_queue.size() > 0 && add_queue.front() <= free) {
		n, cond = add_queue.dequeue();
		cond.signal();
	}
}

} // multibuf

Esercizio c2

Un servizio di message passing sincrono senza selezione del mittente prevede una API con due funzioni: 

 sasend(msg_t msg, pid dest);
 msg_t sarecv(void);

La funzione sarecv restituisce il primo messaggio ricevuto da qualsiasi mittente ed è bloccante se non ci sono messaggi pendenti. la funzione sasend si blocca fino a quando il messaggio msg non viene ricevuto dal processo dest. Dato quindi un servizio di message passing sincrono senza selezione del mittente implementare un servizio di message passing sincrono (standard, quello definito nel corso) senza fare uso di processi server.

Soluzione proposta 1 (da controllare)

  • proposta da Flecart (talk) 18:25, 16 January 2023 (CET)
  • Errore, ssend in questo caso non è sincrono, bisognerebbe uscire con l'ack dal receiver Flecart (talk) 22:56, 16 January 2023 (CET)
ssend(msg_t msg, pid dest) {
	sasend(<msg, getpid()>, dest);
}


// variabili interne di srecv
queue<msg_t> msgs[MAX_PROC];

// suppongo non ci sia il caso in cui sender = ANY.
// nel caso ci fosse la necessità, si dovrebbe creare una altra struttura di dati
// che ordini globalmente il messaggio che sia arrivato prima.
msg_t srecv(pid sender) {
	if (msgs[sender].len() > 0) {
		return msgs[sender].dequeue();
	}
	
	while (true) {
		<msg, pid> = sarecv();
		if (pid == sender) {
			return msgs[pid].dequeue();
		} else {
			msgs[pid].enqueue(msg);
		}
	}
}

Soluzione proposta 2 (da controllare)

proposta da Flecart Friend cedo la proprità intellettuale di questa soluzione a flecart 

// mem è condivisa tra ssend e srecv di ogni processo
// essendo che un processo può solo mandare o ricevere alla volta
// non abbiamo bisogno di cs

// inizializzati tutti a NULL
msg_t mem[MAXPID];
// in mem ci basta un messaggio per PID perchè un pid può aver mandato al
// massimo un messaggio essendo che sono bloccanti la send e la recive

void ssend(msg_t msg, pid dest) {
  sasend(<getpid(),msg>,dest);
  while(true){
    <form_c,msg>=sarecv();
    // dovrebbe essere ovvio che se è from c allora il msg dovrebbe essere un
    // ack perchè se c avesse mandato un messaggio diverso vorrebbe dire che
    // sta facendo una send e se i due processi si fanno una send allora c'è
    // deadhlock
    if(from_c == dest && msg == ACK){
      break;
    }else{
      mem[from_c]=msg;
    }
  }
}

msg_t srecv(pid from) {
  if(mem[from]!=NULL){
    t=mem[from];
    mem[from]=NULL;
    ssend(ACK,from);
    return t;
  }
  while(true){
    <form_c,msg>=sarecv();
    if(from_c==from){
      ssend(ACK,from);
      return msg;
    }else{
      mem[from_c].push(msg);
    }
  }
}
Retrieved from "https://so.v2.cs.unibo.it/wiki/index.php?title=Prove_scritte_2022&oldid=3067"