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