Difference between revisions of "Prove svolte e soluzioni proposte"

Latest revision as of 16:49, 17 May 2023

Questa pagina raccoglie prove d'esame svolte (che possono essere utili alla preparazione) e soluzioni proposte a tali prove da sottoporre a peer-review. Chiunque prenda visione di un esercizio è pregato (per il bene collettivo) a lasciare una propria firma con nome utente e data di visualizzazione indicando se lo svolgimento è ritenuto corretto; in caso di svolgimento scorretto è invece invitato ad apportare una correzione o a spiegare il perché dell'errore commesso, lasciando come nel caso precedente il proprio nome utente e data di correzione.

Al fine di verificare la correttezza degli esercizi di concorrenza, segnaliamo la presenza di strumenti di programmazione concorrente per i linguaggi C e Python.

Difference between revisions of "Prove svolte e soluzioni proposte"

Latest revision as of 16:49, 17 May 2023

Prove scritte

Prove pratiche

Navigation menu

Search

@@ Line 1: / Line 1: @@
-Questa pagina serve a raccogliere prove d'esame svolte (che possono essere utili alla preparazione) e soluzioni proposte a tali prove da sottoporre a peer-review.
+Questa pagina raccoglie prove d'esame svolte (che possono essere utili alla preparazione) e soluzioni proposte a tali prove da sottoporre a peer-review. Chiunque prenda visione di un esercizio è pregato (per il bene collettivo) a lasciare una [https://www.mediawiki.org/wiki/Help:Signatures propria firma] con nome utente e data di visualizzazione indicando se lo svolgimento è ritenuto corretto; in caso di svolgimento scorretto è invece invitato ad apportare una correzione o a '''spiegare il perché dell'errore commesso''', lasciando come nel caso precedente il proprio nome utente e data di correzione.
-== Esame 19/09/2018 ==
+Al fine di verificare la correttezza degli esercizi di concorrenza, segnaliamo la presenza di [[Tool_per_semafori_e_monitor|strumenti di programmazione concorrente]] per i linguaggi C e Python.
-=== Esercizio c.1 (sbagliato) ===
-<source lang="c">
-// Condition: MAX
-// Condition: ok2load
-// Condition: ok2unload
-// Condition: ok2move
-int airport_codes = [BLQ, CDG, BRX, LGW, FCO, ...]
+== Prove scritte ==
-struct luggage {
+* [[Prove scritte 2023]]
-    int dstcode;
+* [[Prove scritte 2022]]
-    int owner;
+* [[Prove scritte 2021]]
-};
+* [[Prove scritte 2020]]
-luggage cart[MAX];
+* [[Prove scritte 2019]]
-int loaded = 0;
+* [[Prove scritte 2018]]
+* [[Prove scritte 2017]]
+* [[Prove scritte 2015]]
+* [[Prove scritte 2014]]
+* [[Prove scritte 2013]]
+* [[Prove scritte 2011]]
+* [[Prove scritte 2005]]
-Procedure entry: void cartat(int code)
+== Prove pratiche ==
-{
+* [[Prove pratiche 2022]]
-    if(code == 0)
+* [[Prove pratiche 2019]]
-    {
+* [[Prove pratiche 2018]]
-        ok2unload.wait();
+* [[Prove pratiche 2017]]
-        ok2load.signal();
+* [[Prove pratiche 2016]]
-    }
-    else
-    {
-        ok2load.wait();
-        ok2unload.signal();
-    }
-}
-Procedure entry: void load(int dstcode, int owner)
-{
-    ok2move.wait();
-    if(loaded < MAX)
-    {
-        luggage l;
-        l.dstcode = dstcode;
-        l.owner = owner;
-        cart.push(l);
-        loaded++;
-    }
-    else ok2move.signal();
-}
-Procedure entry: int unload(int dstcode)
-{
-    ok2move.wait();
-    int i;
-    for(i=0; i<loaded; i++)
-    {
-        if(cart[i].dstcode == dstcode)
-        {
-            int owner = cart[i].owner;
-            cart[i].remove();
-            loaded--;
-            return owner;
-        }
-    }
-    else ok2move.signal();
-}
-</source>
-<br>
-=== Esercizio c.1 ===
-<source lang="c">
-monitor dispatch
-condition go_cart;
-condition ok2station; // quando la stazione può caricare
-current_station = None
-// dizionario con chiave destinazione
-luggages = {}
-def countl(luggages):
-    n=0
-    for d in luggages:
-        n += len(luggages[d]);
-p.e. cartat(code):
-    current_station = code // carrello arriva alla stazione
-    if (code == BLQ || len(luggages[code]) > 0):
-        ok2station[code].signal()
-        go_cart.wait()
-    current_station = None // il carrello sta viaggiando tra le stazioni
-p.e. load(dst, owner):
-    if (current_station != BLQ || countl(luggages) >= MAX):
-        ok2station(BLQ).wait()
-    luggages[dst].append(owner)
-    if (countl(luggages) >= MAX)
-        go_cart.signal()
-p.e. unload(dst):
-    if (current_station != dst || len(luggages[dst]) == 0)
-    // lunghezza lista dei bagagli con questa destinazione
-        ok2station(dst).wait()
-    owner = luggages[dst].pop()
-    if len(luggages[dst]) == 0)
-        go_cart.signal()
-    return owner
-</source>
-<br>
-=== Esercizio c.2 ===
-<source lang="c">
-/* MP sincrono dato quello asincrono */
-void ssend(obj msg, process q)
-{
-    asend(msg, q);
-    ack = areceive(q);
-}
-obj sreceive(process p)
-{
-    obj msg = areceive(p);
-    asend(ack, p);
-    return msg;
-}
-</source>
-<br>
-Soluzione:
-<source lang="c">
-dati asend/arecv devo implementare lssend lsrecv
-lssend(dst, msg):
-    asend(dst, (MSG, myid(), msg))
-    arecv(dst)
-lsrecv(snd):
-    asend(myid(), (TAG, myid(), NULL))    // mi mando un messaggio che riesco a riconoscere
-    while True:
-        (T, s, m) =  arecv(ANY)           // continua a ricevere finchè non ricevi il mio messaggio
-        if (T != TAG) data.push(s, m)
-        else break
-    while (((s,m) = data.pop(snd) == NULL):   // c'è il messaggio di src definito?
-        (T, s, m) =  arecv(ANY)
-        data.push(s, m)
-    asend(s, (ACK, myid(), NULL)
-    return m
-</source>
-<br>
-=== Esercizio g.1 (sbagliato) ===
- <nowiki>
-x = long_compute()/short_compute()
-X = io()
-0 0 0 0 0 0 0 0 0 1 1 1 1 1 1 1 1 1 1 2 2 2 2 2 2 2 2 2 2 3 3 3 3 3 3 3 3 3 3 4 4 4 4 4 4 4 4 4 4 5 5 5 5 5 5 5 5 5 5 6 6 6 6 6 6 6 6 6 6 7 7 7 7 7 7 7 7 7 7 8 8 8
-1 2 3 4 5 6 7 8 9 0 1 2 3 4 5 6 7 8 9 0 1 2 3 4 5 6 7 8 9 0 1 2 3 4 5 6 7 8 9 0 1 2 3 4 5 6 7 8 9 0 1 2 3 4 5 6 7 8 9 0 1 2 3 4 5 6 7 8 9 0 1 2 3 4 5 6 7 8 9 0 1 2
-P1 |x|x|x|x|x|X|-|-|-|-|-|-|X|X|X|-|-|-|-|-|-|X|x|x|-|-|-|-|-|-|x|x|x|-|-|-|-|-|-|-|-|-|-|-|-|-|-|-|X|X|X|-|-|-|-|-|-|X|X|x|-|-|-|-|-|-|x|-|-|
-P2         |-|-|x|x|x|-|-|-|-|-|-|x|x|-|-|-|-|-|-|-|X|X|X|-|-|-|-|-|-|X|X|x|-|-|-|-|-|-|x|x|x|-|-|-|-|-|-|x|-|-|-|-|-|-|-|-|X|X|X|-|-|-|-|-|-|X|X|x|-|-|-|x|-|-|
-P3               |-|-|x|x|x|-|-|-|-|-|-|x|x|-|-|-|-|-|-|-|-|-|-|-|-|-|-|-|-|X|X|X|-|-|-|-|-|-|X|X|x|-|-|-|-|-|-|x|x|x|-|-|-|-|-|-|x|-|-|-|-|-|-|-|-|X|X|X|-|-|-|X|X|x|x|
- </nowiki>
-<br>
-=== Esercizio g.1 ===
- <nowiki>
-P1(start=0): 5ms CPU, 5ms IO, 5ms CPU, 5ms IO, 2ms CPU
-P2(start=4): 5ms CPU, 5ms IO, 5ms CPU, 5ms IO, 2ms CPU
-P3(start=7): 5ms CPU, 5ms IO, 5ms CPU, 5ms IO, 2ms CPU
-0 0 0 0 0 0 0 0 0 1 1 1 1 1 1 1 1 1 1 2 2 2 2 2 2 2 2 2 2 3 3 3 3 3 3 3 3 3 3 4 4 4 4 4 4 4 4 4 4 5
-1 2 3 4 5 6 7 8 9 0 1 2 3 4 5 6 7 8 9 0 1 2 3 4 5 6 7 8 9 0 1 2 3 4 5 6 7 8 9 0 1 2 3 4 5 6 7 8 9 0
-P|1 1 1|1 1|2 2 2|3 3 3|2 2|1 1 1|3 3|1 1|2 2 2*3 3 3|2 2|3 3|1 1|-|2 2|- - -|3 3|
-I          |1 1 1 1 1|     |2 2 2 2 2|3 3 3 3 3|1 1 1 1 1|2 2 2 2 2|3 3 3 3 3|
-r - - - - 2 - - 3 2 2 2 1 1 3 3 3 1 1 2 2 - - - 2 2 2 3 3 1 1
-3 3
-* 3 ha finito input output e 2 è ancora in esecuzione quindi c'è da scegliere
- </nowiki>
-<br>
-=== Esercizio g.2 (da controllare) ===
-a) Può richiedere supporto hardware. Se implementato con contatori o stack questi devono essere aggiornati ad ogni riferimento alla memoria. L'intero sistema viene appesantito e rallentato.<br>
-b) Il journaling si assicura che i dati sul filesystem siano consistenti, ma non aggiornati. Assicura la coerenza dei dati, ma non la perdita dei file se il filesystem si danneggia.<br>
-c) Si dice che un programma A ha lo stesso potere espressivo di un programma B quando è possibile esprimere ogni programma scritto con B mediante A. Per implementare MP sincrono dato quello asincrono basta aggiungere una libreria. Per implementare MP asincrono dato quello sincrono bisogna aggiungere un processo server.<br>
-d) In questi casi tutte le istruzioni vengono eseguite con la massima autorità, con problemi di sicurezza nel caso un utente estraneo prenda il controllo del sistema o rischio di commettere gravi errori semplicemente sbagliando a digitare un comando.
-== Esame 17/07/2018 ==
-=== Esercizio c.1 ===
-<source lang="c">
-/* Monitor Delirum: */
-// Condition: Ok2Load;
-// Condition: Ok2Pour[]; // Un elemento per Type
-int availableBeer[]; // Un elemento per Type
-Queue requests[]; // Un elemento per Type
-Queue pendingRequests;
-Procedure entry: void Pour(Type t, Quantity c)
-{
-    if (c > availableBeer[t]) // Richiesta maggiore della birra disponibile
-    {
-        c -= availableBeer[t];
-        availableBeer[t] = 0;
-        requests[t].Enqueue(c);
-        if (requests[t].Length == 1) // Risveglio un magazziniere solo se è la prima richiesta di questo tipo di birra
-        {
-            pendingRequests.Enqueue(t);
-            Ok2Load().Signal();
-        }
-        Ok2Pour[t].Wait();
-        requests[t].Dequeue(); // Quando ho ottenuto la birra che voglio, elimino la mia richiesta
-    }
-    availableBeer[t] -= c;
-}
-Procedure entry: Type isEmpty()
-{
-    if (pendingRequests.Length == 0)
-    {
-        Ok2Load.Wait();
-    }
-    return pendingRequests.Dequeue();
-}
-Procedure entry: Loaded(Type t, Capacity c)
-{
-    availableBeer[t] += c;
-    while (requests[t].Length > 0 && availableBeer[t] > requests[t].head())
-    {
-        Ok2Pour[t].Signal();
-    }
-    if (requests[t].Length > 0) // serve per evitare che a causa di un magazziniere lento si accodino cosi tante richieste che mentre si sta caricando si svuota subito il fusto
-    {
-        pendingRequests.Enqueue(t);
-        Ok2Load.Signal();
-    }
-}
-</source>
-<br>
-=== Esercizio c.2 (da controllare) ===
-<source lang="c">
-stack s;
-semaphore mutex(1); // mutua esclusione
-semaphore ok2consume(0);
-Procedure entry: void push(int value)
-{
-    mutex.P();
-    s.push(value)
-    mutex.V()
-    ok2consume.V()
-}
-Procedure entry: int pop()
-{
-    int value;
-    ok2consume.P();
-    mutex.P();
-    value = s.pop();
-    mutex.V();
-    return value;
-}
-</source>
-<br>
-=== Esercizio g.1 (da controllare) ===
-Possiamo notare subito che il sistema ha due processori ed un dispositivo di I/O.
-'''A''' e '''B''' partono insieme al tempo 0.<br>
-'''C''' parte tra il tempo 0 ed il tempo 2 (non possiamo sapere di preciso quando perchè entrambe le CPU sono occupate).<br>
-'''D''' parte tra il tempo 0 ed il tempo 3.<br>
-A questo punto possiamo supporre che tutti e 4 i processi partano in sequenza ('''A''', '''B''', '''C''', '''D''') nello stesso momento, e ognuno prende la prima CPU libera che trova.<br>
-'''A''' lavora per 3ms, poi scade il time slice.<br>
-Nel frattempo '''B''' lavora per 2ms, poi richiede I/O per 4ms.<br>
-La CPU su cui lavora '''B''' quindi si libera, e si manda in esecuzione il processo '''C'''.<br>
-Scaduto il time slice per '''A''', si da il controllo ad un nuovo processo. '''B''' è occupato con I/O, '''C''' sta già lavorando, quindi è il turno di '''D'''.<br>
-'''C''' lavora per 3ms, poi richiede I/O per 3ms, che però è occupato da '''B''', quindi si mette in coda per utilizzarlo.<br>
-La CPU su cui lavorava '''C''' si libera ed il controllo torna ad '''A''', che doveva lavorare ancora per 2ms prima di chiedere il controllo di I/O, quindi lavora e si mette in coda dietro a '''C'''.<br>
-Tornando a '''D''', questo lavora per 3ms prima che scada il time slice. Anche '''B''' ha finito il lavoro e ha bisogno di una CPU.<br>
-In questo momento sia '''D''' che '''B''' sono nella coda dei processi in stato ready, ma dal diagramma possiamo notare che il controllo torna a '''D'''.<br>
-La CPU ha scelto a caso un processo tra i due, perchè arrivati a questo punto possiamo supporre che lo scheduler sia Round-Robin.<br>
-'''B''' prende possesso della prima CPU che si libera, ovvero quella occupata da '''A''', poi lavora per 2ms e termina il suo lavoro.<br>
-Nel momento in cui '''B''' termina il lavoro, scade anche il time slice per '''D''', e '''C''' termina di usare I/O.<br>
-Abbiamo due processi ('''C''' e '''D''') in coda ready. Ma abbiamo anche due CPU libere, perchè '''A''' è in coda per I/O e ci entra appena '''C''' finisce di usarlo.<br>
-Lo scheduler sceglie di mandare '''C''' sul primo processore e '''D''' sul secondo.<br>
-'''A''' nel frattempo, lavora per 4ms con I/O.<br>
-'''C''' lavora per 3ms, poi termina il suo lavoro.<br>
-'''D''' lavora per 3ms, poi scade il time slice. Ci sono due processori liberi, quindi '''D''' riparte subito in esecuzione.<br>
-'''D''' doveva lavorare ancora per 1ms prima di aver bisogno di I/O, quindi finisce e si mette in coda.<br>
-Ma nello stesso momento '''A''' termina di usare I/O, si prende un processore libero e lavora per i suoi ultimi 2ms.<br>
-'''D''' lavora per 1ms con I/O, poi prende il secondo processore libero e lavora per 1ms prima di terminare il suo lavoro.<br>
-Il time slice è di 3ms, lo scheduler è di tipo Round-Robin.<br>
-Il dispositivo di I/O è FIFO. L'ordine con cui partono i processi è quello alfabetico.
-<source lang="c">
-A(){
-    compute_a1(); // 5ms
-    io_a(); // 4ms
-    compute_a2(); // 2ms
-}
-B(){
-    compute_b(); // 2ms
-    io_b(); // 4ms
-    compute_b(); // 2ms
-}
-C(){
-    compute_c(); // 3ms
-    io_c(); // 3ms
-    compute_c(); // 3ms
-}
-D(){
-    compute_d1(); // 10ms
-    io_d(); // 1ms
-    compute_d2(); // 1ms
-}
-</source>
-Lo scheduler potrebbe anche essere a priorità:<br>
-Priorità '''B''' < priorità '''D''' < priorità '''C'''<br>
-Priorità '''A''' = ?<br>
-'''B''' fatto partire prima di '''C''' e '''D'''.
-<br>
-== Esame 29/05/2017 ==
-=== Esercizio c.1 ===
-<source lang="c">
-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
-p.e. nuovapartita():
-{
-    punteggio[A] = punteggio[B] = 0;
-    numpronti = 0;
-    partita=true;
-    okpartita.signal()
-    chiamati = [];
-}
-p.e. 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;
-}
-p.e. 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();
-    }
-}
-</source>
-<br>
-== Esame 16/07/2014 ==
-=== Esercizio c.1 ===
-<source lang="c">
-/* Monitor Bounded Buffer: (non richiesto dall'esercizio) */
-queue q;
-condition oktoread; // q.length() > 0
-condition oktowrite; // q.length() < MAX
-procedure entry type read():
-    if (q.length() == 0) oktoread.wait(); // controllo
-    retval = q.dequeue(); // cambio lo stato
-    // abilito coloro che possono essere abilitati dal cambiamento di stato
-    oktowrite.signal()
-    return retval;
-procedure entry void write(type elem):
-    if (q.length() >= MAX) oktowrite.wait(); //controllo
-    q.enqueue(elem); // cambio lo stato
-    oktoread.signal(); // abilito chi può essere abilitato
-/* NOTE:
- * procedure entry ==> dichiarazione di funzioni (senza vedere l'implementazione
- * dall'esterno)
- */
-</source>
-<br>
-<source lang="c">
-/* Min-Max Monitor Bounded Buffer: */
-Queue Q;
-// Condition: OKTOREAD: Q.Length > MIN
-// Condition: OKTOWRITE: Q.Length < MAX
-procedure entry: Type Read():
-{
-    if (Q.Length <= MIN) OKTOREAD.Wait(); // Controllo
-    retval = Q.Dequeue(); // Cambio di stato
-    OKTOWRITE.Signal(); // Abilito chi vuole scrivere
-    return retval; // Qui sono sicuro perchè ne ho eliminato uno prima
-}
-procedure entry: void Write(Type elem):
-{
-    if (Q.Length >= MAX) OKTOWRITE.Wait() // Controllo
-    Q.Enqueue(elem); // Cambio di stato
-    if (Q.Length > MIN) OKTOREAD.Signal(); // Abilito chi vuole leggere
-}
-</source>
-<br>
-=== Esercizio c.2 ===
-<source lang="c">
-Semaphore mutex = 1;
-struct Elem
-{
-    Semaphore s;
-    int counter;
-}
-struct Elem V[]; // Vettore a dimensione variabile. I nuovi elementi sono initializzati a s = 0, counter = 0.
-void RendezVouz(int n)
-{
-    mutex.P(); // Blocco, decremento di 1 (il processo si blocca se il semaforo vale 0)
-    V[n].counter++;
-    if (V[n].counter < n)
-    {
-        mutex.V(); // Rilascia, incrementa di 1
-        V[n].s.P();
-    }
-    V[n].counter--;
-    if (V[n].counter > 0)
-        V[n].s.V();
-    else
-        mutex.V();
-}
-</source>
-<br>
-=== Esercizio g.1 ===
- <nowiki>
-    0241302 ==> soluzione corretta
-(0)2   2200
-(1)3   1111
-(2)4   4442
-(3)0   0333
-3 4 0 1 2 3 4  0  1  2  3 ==> soluzione proposta, non corretta perchè non è la stringa più corta
-           1 1 1 1  0  0  0  0
-           3 2 2 2  2  1  1  1
-           4 4 3 3  3  3  2  2
-           0 0 0 4  4  4  4  3
- </nowiki>