Prove scritte 2022

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();
    }
}

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 (da controllare)

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

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

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 (da controllare)

Soluzione proposta da Flecart

Questo esercizio è stato corretto tempo fa in classe dal professore, <bold>non è completamente corretto</bold> perché dovrei mandare ai server liberi, non a round-robin Flecart (talk) 15:52, 14 January 2023 (CET)

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);
        }
    }
}

Soluzione proposta 2

Soluzione proposta da Flecart frend che cede a flecart la proprietà intellettuale di questa soluzione

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();
        }
    }
}

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;	
}