Difference between revisions of "Prove svolte e soluzioni proposte"

From Sistemi Operativi
Jump to navigation Jump to search
(Spezzettata la pagina "Prove svolte e soluzioni proposte" in più sottopagine)
Line 3: Line 3:
 
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.
 
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.
  
−
== Esame 13/09/2019 ==
+
== Prove scritte ==
−
Testo: [https://www.cs.unibo.it/~renzo/so/compiti/2019.09.13.tot.pdf 2019.09.13.tot.pdf]
+
* [[Prove scritte 2019]]
−
=== Esercizio c.1 ===
+
* [[Prove scritte 2018]]
−
Controllato dal professor Davoli durante la lezione del 19/05/2020.
+
* [[Prove scritte 2017]]
 +
* [[Prove scritte 2015]]
 +
* [[Prove scritte 2014]]
 +
* [[Prove scritte 2011]]
 +
* [[Prove scritte 2005]]
  
−
<source lang="python">
+
== Prove pratiche ==
−
# Original author: Andrea R.
+
* [[Prove pratiche 2018]]
−
 
+
* [[Prove pratiche 2016]]
−
monitor mbuf:
 
−
    waiting = 0
 
−
    queue<pair<T, int>> q    # (dato, molteplicità)
 
−
    condition ok2add        # q.length() < MAXELEM
 
−
    condition ok2get        # q.length() > 0
 
−
   
 
−
 
 
−
    entry void add(T data, int n):
 
−
        if q.length() >= MAXELEM:
 
−
            ok2add.wait()
 
−
 
 
−
        q.enqueue({data, n})
 
−
 
 
−
        if waiting >= q.front().second:
 
−
            ok2get.signal()
 
−
 
 
−
 
 
−
    entry T get():
 
−
        waiting++                                        # vuole ricevere
 
−
        if q.empty() or waiting < q.front().second:      # cortocircuitato
 
−
            ok2get.wait()
 
−
 
 
−
        x = q.front().first
 
−
        q.front().second--
 
−
        waiting--                    # riceve
 
−
 
 
−
        if q.front().second > 0:    # cascata
 
−
            ok2get.signal()
 
−
        else:                        # ultimo che riceve
 
−
            q.dequeue()
 
−
            ok2add.signal()
 
−
        return x
 
−
</source>
 
−
 
 
−
== Esame 15/07/2019 ==
 
−
[http://www.cs.unibo.it/~renzo/so/compiti/2019.07.15.tot.pdf 2019.07.15.tot.pdf]
 
−
=== Esercizio c.1 ===
 
−
 
 
−
# Verifica del 18/05/2020 dell'utente [[User:Acsor|Acsor]]. Ritengo sia: corretto
 
−
# Verifica del ... dell'utente ... . Ritengo sia: ...
 
−
# ...
 
−
 
 
−
Una semplice realizzazione in Python dello pseudocodice seguente è disponibile [https://github.com/pollomarzo/rdso1920/tree/master/2019exams/samepc qui].
 
−
 
 
−
<source lang="python">
 
−
# Original authors: Mattia Guazzaloca, Paolo Marzolo
 
−
#
 
−
# Contributors: utente Acsor
 
−
 
 
−
monitor pair_buffer:
 
−
    int nw, nr;
 
−
    queue buffer;
 
−
    condition same_number;
 
−
 
 
−
    pair_buffer():
 
−
        nw = nr = 0
 
−
        buffer = queue()
 
−
        same_number = condition()
 
−
   
 
−
    @entry
 
−
    put(T x):
 
−
        nw++;
 
−
        buffer.enqueue(x);
 
−
       
 
−
        if nw != nr:
 
−
            same_number.wait();
 
−
           
 
−
        same_number.signal();
 
−
        nw--;
 
−
       
 
−
    @entry
 
−
    T get(void):
 
−
        nr++;
 
−
 
 
−
        if nw != nr:
 
−
            same_number.wait();
 
−
        else:
 
−
            same_number.signal();
 
−
       
 
−
        T val = buffer.dequeue();
 
−
        same_number.signal();
 
−
        nr--;
 
−
 
 
−
        return val;
 
−
</source>
 
−
 
 
−
<br>
 
−
 
 
−
== Esame 18/06/2019 ==
 
−
[http://www.cs.unibo.it/~renzo/so/compiti/2019.06.18.tot.pdf 2019.06.18.tot.pdf]
 
−
=== Esercizio c.1 (da controllare) ===
 
−
<source lang="c">
 
−
monitor pg{
 
−
 
 
−
  int waitingReader = 0;
 
−
  int waitingWriter = 0;
 
−
 
 
−
  condition ok2write;
 
−
  condition ok2read;
 
−
 
 
−
  T datobuf;
 
−
 
 
−
  entry put (T dato) {
 
−
 
 
−
    if (waitingReader > 0)
 
−
      datobuf = dato;
 
−
      while (waitingReader > 0)
 
−
        ok2read.signal();
 
−
    else if (waitingWriter >= 0)
 
−
      waitingWriter++;
 
−
      ok2write.wait();
 
−
      waitingWriter--;
 
−
      datobuf = dato;
 
−
 
 
−
  }
 
−
 
 
−
  entry T get (void) {
 
−
 
 
−
    if (waitingReader > 0 || waitingWriter == 0)
 
−
      waitingReader++;
 
−
      ok2read.wait();
 
−
      waitingReader--;
 
−
    else if (waitingWriter > 0)
 
−
      ok2write.signal();
 
−
      return datobuf;
 
−
   
 
−
  }
 
−
 
 
−
}
 
−
</source>
 
−
<br>
 
−
 
 
−
=== Esercizio c.1 (da controllare) ===
 
−
<source lang="c">
 
−
monitor taon {
 
−
condition ok2w, ok2r;
 
−
int nw, nr = 0;
 
−
T buf;
 
−
 
 
−
entry  void put (T dato){
 
−
nw++;
 
−
if( nw != 1 || nr == 0)
 
−
            ok2w.wait();
 
−
buf = dato;
 
−
for (i=0, i++, i < nr)
 
−
    ok2r.signal();
 
−
nw--;
 
−
}
 
−
 
 
−
entry T get(){
 
−
nr++;
 
−
if(nw==0)
 
−
    ok2r.wait();
 
−
ok2w.signal();
 
−
T dato = buf;
 
−
nr --;
 
−
return dato;
 
−
}
 
−
</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 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
 
−
  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 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 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
 
−
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
 
−
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
 
−
                      1 3 3
 
−
 
 
−
* 3 ha finito input output e 2 è ancora in esecuzione quindi c'è da scegliere
 
−
</nowiki>
 
−
<br>
 
−
 
 
−
 
 
−
=== Esercizio g.2 (da controllare) ===
 
−
# 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.
 
−
# 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.
 
−
# 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.
 
−
# 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 18/05/2019 ==
 
−
[http://www.cs.unibo.it/~renzo/so/compiti/2019.05.18.tot.pdf 2019.05.18.tot.pdf]
 
−
 
 
−
=== Esercizio c.1 (da controllare) ===
 
−
 
 
−
* Controllato dall'utente Lusvelt in data 26/08/2020 (sbagliato, dal testo si evince che se manca anche solo un componente bisogna mettersi in attesa finchè non arrivi, per poi prendere anche gli altri).
 
−
:: E non è quel che già accade nel ramo else di get()? C'è una wait() ed essa è invocata proprio quando components[i] > self._v[i]. (La chat in Wiki è scomoda, sentiamoci su Telegram.) -- [[User:Acsor|Acsor]] ([[User talk:Acsor|talk]]) 17:32, 26 August 2020 (CEST)
 
−
* ...
 
−
 
 
−
Il sorgente seguente può essere eseguito scaricando in una stessa directory il package [[Tool per semafori e monitor|pysm]] del prof. Davoli.
 
−
 
 
−
<source lang="python">
 
−
#!/usr/bin/env python3
 
−
 
 
−
import threading
 
−
 
 
−
from array import array
 
−
from pysm.monitor import condition, entry, monitor
 
−
 
 
−
 
 
−
class storage(monitor):
 
−
    ELEMS = 16
 
−
 
 
−
    """
 
−
    Implementazione che permette l'avanzamento degli operai in presenza di
 
−
    altri operai in attesa.
 
−
    """
 
−
    def __init__(self):
 
−
        monitor.__init__(self)
 
−
        self._v = array('L', self.ELEMS * [0])
 
−
        self._c = tuple(condition(self) for i in self._v)
 
−
        # self._requests[i] = [l1, l2, ..., ln] se per l'attrezzo i ci sono in
 
−
        # attesa n processi che richiedono ciascuno l1, l2, ..., ln unita'
 
−
        self._requests = {i: list() for i in range(self.ELEMS)}
 
−
 
 
−
    @entry
 
−
    def add(self, components):
 
−
        if len(components) != self.ELEMS:
 
−
            raise ValueError("components must contain exactly ELEMS elements")
 
−
 
 
−
        for i, c in enumerate(components):
 
−
            self._v[i] += c
 
−
 
 
−
            # Finche' per il componente i ci sono richieste in sospeso che
 
−
            # possono essere soddisfatte, svegliamo il processo in attesa, che
 
−
            # proseguira' col richiedere i componenti successivi
 
−
            while self._requests[i] and self._requests[i][0] <= self._v[i]:
 
−
                self._c[i].signal()
 
−
 
 
−
    @entry
 
−
    def get(self, components):
 
−
        if len(components) != self.ELEMS:
 
−
            raise ValueError("components must contain exactly ELEMS elements")
 
−
 
 
−
        for i in range(len(components)):
 
−
            if components[i] <= self._v[i]:
 
−
                self._v[i] -= components[i]
 
−
            else:
 
−
                components[i] -= self._v[i]
 
−
                self._v[i] = 0
 
−
 
 
−
                self._requests[i].append(components[i])
 
−
                self._c[i].wait()
 
−
 
 
−
                self._v[i] -= components[i]
 
−
                self._requests[i].pop(0)
 
−
 
 
−
 
 
−
def request(m, q):
 
−
    """
 
−
    Funzione processo che simula la richiesta di un operaio.
 
−
    """
 
−
    name = threading.current_thread().name
 
−
 
 
−
    print("[%s] Requesting %s" % (name, q))
 
−
    m.get(q)
 
−
    print("[%s] Done requesting" % (name))
 
−
 
 
−
 
 
−
def supply(m, s):
 
−
    """
 
−
    Funzione processo che simula il rifornimento di un magazziniere.
 
−
    """
 
−
    name = threading.current_thread().name
 
−
 
 
−
    print("[%s] Supplying %s" % (name, s))
 
−
    m.add(s)
 
−
    print("[%s] Done supplying" % (name))
 
−
 
 
−
 
 
−
def main():
 
−
    m = storage()
 
−
    requests = [
 
−
        threading.Thread(name='req1', target=request, args=(m, [4, 8, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0])),
 
−
        threading.Thread(name='req2', target=request, args=(m, [0, 0, 2, 4, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0])),
 
−
        threading.Thread(name='req3', target=request, args=(m, [4, 8, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0])),
 
−
        threading.Thread(name='req4', target=request, args=(m, [4, 8, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0])),
 
−
        threading.Thread(name='req5', target=request, args=(m, [4, 8, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0])),
 
−
    ]
 
−
    supplies = [
 
−
        threading.Thread(name='supply1', target=supply, args=(m, [4, 8, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0])),
 
−
        threading.Thread(name='supply2', target=supply, args=(m, [4, 8, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0])),
 
−
        threading.Thread(name='supply3', target=supply, args=(m, [4, 8, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0])),
 
−
        threading.Thread(name='supply4', target=supply, args=(m, [4, 8, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0])),
 
−
        threading.Thread(name='supply5', target=supply, args=(m, [0, 0, 2, 4, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0])),
 
−
    ]
 
−
 
 
−
    for t in requests + supplies:
 
−
        t.daemon = True
 
−
        t.start()
 
−
   
 
−
    for t in requests + supplies:
 
−
        t.join()
 
−
 
 
−
    return 0
 
−
 
 
−
 
 
−
if __name__ == "__main__":
 
−
    exit(main())
 
−
</source>
 
−
 
 
−
=== Esercizio c.2 (da controllare) ===
 
−
<source lang="c">
 
−
unsigned procs_in = 0;
 
−
semaphore mutex = new binary_semaphore(1);
 
−
queue<semaphore> semaphores = new queue<>();
 
−
 
 
−
sau_enter () {
 
−
mutex.P();
 
−
procs_in++;
 
−
mutex.V();
 
−
}
 
−
 
 
−
sau_exit () {
 
−
mutex.P();
 
−
procs_in--;
 
−
 
 
−
if (procs_in > 0) {
 
−
semaphore s = new semaphore(0);
 
−
 
 
−
semaphores.enqueue(s);
 
−
mutex.V();
 
−
s.P();
 
−
} else {
 
−
while (!sempahores.empty())
 
−
semaphores.dequeue().V();
 
−
 
 
−
mutex.V();
 
−
}
 
−
}
 
−
 
 
−
</source>
 
−
 
 
−
=== Esercizio g.1 (da controllare) ===
 
−
==== Domanda a) ====
 
−
Poiché lo scheduler è non-preemptive, una volta assegnata la CPU ad un dato processo, questi non viene cambiato finché non ha terminato. Visto il vincolo nel testo della consegna, una volta concluso il processo corrente si hanno solo due scelte: selezionare il più recente processo A o il più recente processo B.
 
−
 
 
−
Nuovi processi A partono ogni 6ms, nuovi processi B ogni 8ms; gli intervalli di tempo in cui partono sia processi A sia processi B sono multipli di mcm(6, 8) ms = 24ms: cioè ai tempi 0ms, 24ms, 48ms, 72ms, ..., parte sia un processo A sia un processo B.
 
−
 
 
−
In ognuno di questi intervalli di 24ms, si susseguono sia processi A sia processi B. I processi A sono 24ms / 6ms = 4, i processi B 24ms / 8ms = 3; i primi richiedono 4 * 3ms = 12ms, i secondi 3 * 4ms = 12ms. È possibile dimostrare induttivamente che ad ogni nuovo intervallo di 24ms, i processi di quello precedente sono stati tutti svolti e che quelli correnti saranno terminati entro 24ms (infatti ad ogni 24ms, è un po' come se le condizioni iniziali venissero ristabilite). Pertanto è possibile eseguire entrambi i processi senza portare a starvation.
 
−
 
 
−
==== Domanda b) ====
 
−
Ragionamento analogo al punto precedente, con alcune differenze date dalle permutazioni in cui certi processi vengono schedulati.
 
−
 
 
−
==== Domanda c) ====
 
−
Per definizione, uno scheudler round-robin garantisce possibilità di esecuzione a tutti i processi, pertanto è possibile. La figura mostra un intervallamento di scheduling secondo criterio RR che evidenzia come sia possibile completare tutti i processi entro i 24ms.
 
−
 
 
−
[[File:Epson 25082020151034.jpg]]
 
−
 
 
−
=== Esercizio g.2 (da controllare) ===
 
−
 
 
−
# Basso, perché vengono generate molte page trap. Così facendo i processi direttamente interessati devono attendere il caricamento delle pagine di memoria ed essere posti in attesa, riducendo l'utilizzazione della CPU.
 
−
# Sì, ad esempio il MBR (Master Boot Record) e l'area di swap. Il MBR contiene meta-informazioni sul disco stesso e non è adatto a contenere informazioni concrete, mentre l'area di swap può essere considerata un'estensione della memoria centrale del calcolatore.
 
−
# Flessibile, perché se intendo riconfigurare alcuni parametri del sistema non occorre ricompilare il kernel, ma solamente riscrivere/riconfigurare e rilanciare il programma che si fa carico del servizio in questione; affidabile, in quanto i servizi di sistema sono realizzati tramite processi a livello utente, e un loro crash non si ripercuote sull'intero sistema; meno efficiente (di un kernel monolitico) in quanto i vari servizi comunicano con il kernel non tramite chiamate di sistema, ma un vero e proprio servizio di message passing tra processi, che aggiunge overhead.
 
−
# Come voci di una directory che puntano allo stesso inode (laddove il file system sia basato su inode) o più in generale allo stesso FCB (File Control Block). Per determinare se un dato FCB non è più linkato da nessuna voce (entry) si utilizza un contatore che rappresenta il numero corrente di riferimenti; quando questo diventa 0, il FCB può essere eliminato dal file system.
 
−
 
 
−
== Esame 14/02/2019 ==
 
−
[https://www.cs.unibo.it/~renzo/so/compiti/2019.02.14.tot.pdf testo esame]
 
−
=== Esercizio c.1 (possibile soluzione corretta) ===
 
−
<source lang="python">
 
−
# Original authors: Mattia Guazzaloca & Paolo Marzolo
 
−
#
 
−
# Contributors:
 
−
#
 
−
 
 
−
class monobinarysem(monitor):
 
−
    def __init__(self, val):
 
−
        self.iszero = condition(self)
 
−
        self.val = val
 
−
       
 
−
    @entry
 
−
    def monoP(self):
 
−
        if self.val == 0:
 
−
            self.iszero.wait()
 
−
       
 
−
        self.val -= 1
 
−
       
 
−
    @entry
 
−
    def monoV(self):
 
−
        if self.val == 0:
 
−
            self.val += 1
 
−
            self.iszero.signal()
 
−
</source>
 
−
=== Esercizio c.2 (soluzione corretta) ===
 
−
<source lang="python">
 
−
# Original author: Renzo Davoli (durante la lezione)
 
−
#
 
−
# Contributors:
 
−
#
 
−
 
 
−
def pssend(message, destination):
 
−
    asend((self(),message),destination)
 
−
    while(1):
 
−
        snd, message = arecv(ANY)
 
−
        if(message == ACK):
 
−
            break
 
−
        datastruct.add(snd, message)
 
−
 
 
−
 
 
−
def psreceive(sender):
 
−
    dummy = Message(null)
 
−
    asend(self(),dummy) //self is my id
 
−
   
 
−
    while(1):
 
−
        snd, message = arecv(ANY)
 
−
        if(message == dummy):
 
−
            break
 
−
        datastruct.add(snd, message)
 
−
       
 
−
    if (datastruct.match(sender)):
 
−
        src, msg = datastruct.get(sender)
 
−
        asend((self(),ACK), src)
 
−
        return msg
 
−
    else:
 
−
        return None
 
−
</source>
 
−
 
 
−
== Esame 28/05/2019 ==
 
−
[http://www.cs.unibo.it/~renzo/so/compiti/2019.05.18.tot.pdf 2019.05.18.tot.pdf]
 
−
 
 
−
=== Esercizio c.1 (da controllare) ===
 
−
<source lang="c">
 
−
 
 
−
monitor storage:
 
−
 
 
−
    [16] int vector
 
−
    [16] condition ok2get
 
−
    [16] bool available = { 1, ..., 1 }
 
−
 
 
−
    entry get([16] int components):
 
−
        for (i from 0 to 15):
 
−
            while ((components[i] > vector[i]) || !available[i]):
 
−
                if (available[i]):
 
−
                    available[i] = false
 
−
                ok2get[i].wait()
 
−
            vector[i] -= components[i]
 
−
            available[i] = true
 
−
            ok2get[i].signal()
 
−
 
 
−
    entry add([16] int components):
 
−
        for (i from 0 to 15):
 
−
            vector[i] += components[i]
 
−
            available[i] = true
 
−
            ok2get[i].signal()
 
−
 
 
−
</source>
 
−
 
 
−
<br>
 
−
 
 
−
=== Esercizio c.1 (da controllare) ===
 
−
<source lang="c">
 
−
monitor storage{
 
−
int stored[16]
 
−
int components[16]
 
−
condition ok2make[16]
 
−
boolean required[16] //false
 
−
 
−
void add(components){
 
−
stored += components;
 
−
for(i=0; i< 16; i ++){
 
−
if(required[i] == true)
 
−
ok2make(i).signal();
 
−
}
 
−
}
 
−
 
 
−
void get(components){
 
−
for(i = 0; i< 16; i++){
 
−
if (stored[i] >= components[i])
 
−
stored[i] -= components[i]
 
−
else
 
−
required[i] = true
 
−
ok2make(i).wait();
 
−
required[i] = false
 
−
i—;
 
−
 
 
−
}
 
−
}
 
−
</source>
 
−
 
 
−
<br>
 
−
 
 
−
== Esame 19/09/2018 ==
 
−
[http://www.cs.unibo.it/~renzo/so/compiti/2018.09.19.tot.pdf Testo dell'esame].
 
−
 
 
−
=== Esercizio c.2 (da controllare) ===
 
−
 
 
−
* Controllato dall'utente ? in data ?
 
−
* ...
 
−
 
 
−
Nello pseudocodice seguente, il termine this fa riferimento al processo corrente, mentre ANY ad uno qualunque.
 
−
 
 
−
<source lang="c">
 
−
stack<message> messages;
 
−
 
 
−
void lifo_send(string m, process dest) {
 
−
do {
 
−
asend(m, dest);
 
−
} while (areceive(dest).text != "ACK");
 
−
}
 
−
 
 
−
message lifo_receive(process source) {
 
−
if (source != ANY) {
 
−
message m = areceive(source);
 
−
 
 
−
asend("ACK", source);
 
−
 
 
−
return m;
 
−
} else {
 
−
message m;
 
−
 
 
−
asend("END", this);
 
−
m = areceive(ANY);
 
−
 
 
−
while (m.text != "END" || m.sender != this) {
 
−
messages.push(m);
 
−
asend("ACK", m.sender);
 
−
 
 
−
m = areceive(ANY);
 
−
}
 
−
 
 
−
                /* Bisogna tenere conto dei casi in cui lifo_receive() viene invocata quando nessun
 
−
                * messaggio è stato ancora spedito da altri processi. In tal caso si attende il
 
−
                * il primo e lo si restituisce.
 
−
                */
 
−
if (messages.empty()) {
 
−
m = areceive(ANY);
 
−
asend("ACK", m.sender);
 
−
 
 
−
return m;
 
−
} else {
 
−
return messages.pop();
 
−
}
 
−
}
 
−
}
 
−
</source>
 
−
 
 
−
== Esame 17/07/2018 ==
 
−
[http://www.cs.unibo.it/~renzo/so/compiti/2018.07.17.tot.pdf 2018.07.17.tot.pdf]
 
−
=== 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 ===
 
−
* Visto e corretto dall'utente [[User:Acsor|Acsor]] in data 23/08/2020
 
−
* Visto e corretto dall'utente ? in data ?
 
−
* ...
 
−
 
 
−
<source lang="c">
 
−
class LIFOBuffer {
 
−
stack<T> s;
 
−
semaphore mutex(1); // mutua esclusione
 
−
semaphore ok2consume(0);
 
−
 
 
−
void push (T value) {
 
−
mutex.P();
 
−
s.push(value);
 
−
                // (1)
 
−
mutex.V()
 
−
 
 
−
ok2consume.V()  // Curiosità: che succede se spostiamo quest'istruzione in (1)?
 
−
}
 
−
 
 
−
T pop () {
 
−
T value;
 
−
 
 
−
ok2consume.P();
 
−
mutex.P();
 
−
value = s.pop();
 
−
mutex.V();
 
−
 
 
−
return value;
 
−
}
 
−
}
 
−
</source>
 
−
<br>
 
−
 
 
−
=== Esercizio g.1 ===
 
−
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>
 
−
 
 
−
=== Esercizio g.2 (da controllare) ===
 
−
# In sistemi dove dispositivi di archiviazione o supporti hardware per la memoria virtuale (e dunque per la paginazione, spesso utilizzata per realizzare il supporto di memoria virtuale) non sono presenti (es. sistemi embedded). ''(In sistemi real-time la memoria virtuale è praticabile? Annotare.)''
 
−
# Perchè ad esempio sulle chiavette USB quasi mai abbiamo il problema di dover utilizzare file di dimensione maggiore ai 4GB. Non utilizza il journaling, che richiede molteplici scritture per ogni azione ed in dispositivi portatili può ridurre di molto la durata. Non supporta i permessi sui file, e questo è un vantaggio per le chiavette USB, pensate per trasferire dati tra PC diversi.
 
−
# Per fornire parallelismo e ridondanza. Non è necessario fare backup dei dati sul disco, nel senso di mantenere una copia identica di dati già memorizzati altrove, in quanto diversi sistemi di codici permettono il rilevamento e/o la correzione di errori.
 
−
# Se in un grafo di Holt multirisorsa esiste un ciclo tra più processi e risorse, ciò non significa che allo stesso tempo non siano coinvolti processi con archi esclusivamente entranti. Ogni processo appartenente a questa categoria non è in attesa di risorse, e può dunque procedere con i suoi calcoli; quando avrà terminato rilascerà le risorse precedentemente allocategli, eventualmente sbloccando uno dei processi coinvolti nel ciclo.
 
−
 
 
−
== Esame 21/06/2018 ==
 
−
[http://www.cs.unibo.it/~renzo/so/compiti/2018.06.21.tot.pdf 2018.06.21.tot.pdf]
 
−
=== Esercizio c.1 (sbagliato) ===
 
−
<source lang="c">
 
−
/* Monitor tmon */
 
−
 
 
−
define MAX n;
 
−
define TERRAFERMA 1;
 
−
define ISOLA 2;
 
−
 
 
−
semaphore ok2unload;
 
−
semaphore ok2load;
 
−
semaphore ok2ship;
 
−
semaphore mutex(1); // la rampa è zona critica --> mutua esclusione
 
−
 
 
−
stack ferry;
 
−
int current_port = 0;
 
−
 
 
−
Procedure entry: al_porto(int location)
 
−
{
 
−
    current_port = location; // traghetto arriva a destinazione
 
−
    ok2unload.signal(); // da il via per far sbarcare le macchine
 
−
    ok2ship.wait(); // si ferma
 
−
    current_port = 0; // traghetto sta viaggiando tra i due porti
 
−
}
 
−
 
 
−
Procedure entry: imbarca(int location)
 
−
{
 
−
    mutex.wait(); // prende possesso della rampa
 
−
    ferry.push(1); // sale sul traghetto
 
−
    mutex.signal(); // libera la rampa
 
−
}
 
−
 
 
−
Procedure entry: imbarcato(int location)
 
−
{
 
−
    if(ferry.lenght() == MAX) // se il traghetto è pieno da il via per farlo salpare
 
−
    {
 
−
        ok2load.wait();
 
−
        ok2ship.signal();
 
−
    }
 
−
}
 
−
 
 
−
Procedure entry: sbarca(int location)
 
−
{
 
−
    mutex.wait(); // prende possesso della rampa
 
−
    ferry.pop(); // scende dal traghetto
 
−
    mutex.signal(); // libera la rampa
 
−
}
 
−
 
 
−
Procedure entry: sbarcato(int location)
 
−
{
 
−
    if(ferry.lenght() == 0) // se il traghetto è vuoto da il via per far imbarcare le macchine
 
−
    {
 
−
        ok2unload.wait();
 
−
        ok2load.signal();
 
−
    }
 
−
}
 
−
 
 
−
</source>
 
−
<br>
 
−
 
 
−
=== Esercizio c.1 ===
 
−
<source lang="c">
 
−
/* Monitor tmon */
 
−
 
−
#define MAX n
 
−
#define NONE 0
 
−
#define TERRAFERMA 1
 
−
#define ISOLA 2
 
−
 
−
condition ok2unload;
 
−
condition ok2load[2];
 
−
condition ok2ship;
 
−
condition empty;
 
−
 
−
int onboard = 0;
 
−
int onramp = 0;
 
−
int current_port = NONE;
 
−
 
 
−
Procedure entry: al_porto(int location)
 
−
{
 
−
    //arrivando
 
−
    current_port = location;
 
−
    ok2unload.signal();
 
−
    if (onboard > 0)
 
−
        empty.wait()
 
−
    ok2load[location].signal()
 
−
    if (onboard < MAX)
 
−
        ok2ship.wait()
 
−
    //partendo
 
−
    current_port = NONE;
 
−
}
 
−
 
−
Procedure entry: imbarca(int location)
 
−
{
 
−
    if (current_port != location || onramp > 0 || onboard >= MAX)
 
−
        ok2load[location].wait()
 
−
    onramp = 1;
 
−
}
 
−
 
 
−
Procedure entry: imbarcato(int location)
 
−
{
 
−
    onramp = 0; onboard++;
 
−
    if (onboard < MAX)
 
−
        ok2load[location].signal();
 
−
    else
 
−
        ok2ship.signal();
 
−
}
 
−
 
−
Procedure entry: sbarca(int location)
 
−
{
 
−
    if (current_port != location || onramp > 0)
 
−
        ok2unload.wait()
 
−
    onramp = 1;
 
−
}
 
−
 
−
Procedure entry: sbarcato(int location)
 
−
{
 
−
    onramp = 0; onboard--;
 
−
    if (onboard == 0)
 
−
        empty.signal();
 
−
    else
 
−
        ok2unload.signal();
 
−
}
 
−
</source>
 
−
<br>
 
−
 
 
−
=== Esercizio c.2 (sbagliato) ===
 
−
<source lang="c">
 
−
 
 
−
#define N n // limite operazioni
 
−
semaphore mutex(1); // sezione critica
 
−
 
 
−
class lim_semaphore()
 
−
{
 
−
    int value;
 
−
    semaphore plus;
 
−
    semaphore minus;
 
−
   
 
−
    P()
 
−
    {
 
−
        mutex.P();
 
−
        if(value < N)
 
−
        {
 
−
            if (value >= 0)
 
−
            {
 
−
                plus.P();
 
−
            }
 
−
            else
 
−
            {
 
−
                minus.V();
 
−
            }
 
−
            value--;
 
−
        }
 
−
        mutex.V();
 
−
    }
 
−
 
 
−
    V()
 
−
    {
 
−
        mutex.P();
 
−
        if(value > -N)
 
−
        {
 
−
            if (value <= 0)
 
−
            {
 
−
                minus.P();
 
−
            }
 
−
            else
 
−
            {
 
−
                plus.V();
 
−
            }
 
−
            value++;
 
−
        }
 
−
        mutex.V();       
 
−
    }
 
−
}
 
−
</source>
 
−
<br>
 
−
 
 
−
=== Esercizio c.2 ===
 
−
Soluzione "furba e facile"
 
−
<source lang="c">
 
−
#define N n // limite operazioni
 
−
class lim_semaphore()
 
−
{
 
−
    semaphore plus;
 
−
    semaphore minus;
 
−
    int value;  //serve per significato
 
−
   
 
−
    init(x) : { value=x; plus.init(N+x); minus.init(N-x);}  //costruttore
 
−
    P() : { plus.P(); value--; minus.V(); }
 
−
    V() : { minus.P(); value++; plus.V(); }
 
−
}
 
−
</source>
 
−
<br>
 
−
 
 
−
Soluzione "schiacciasassi"
 
−
<source lang="c">
 
−
#define N n // limite operazioni
 
−
 
 
−
class lim_semaphore()
 
−
{
 
−
    semaphore mutex;
 
−
    queue of semaphore okmin, okmax;
 
−
    int value;
 
−
    init(x) : { value=x; }
 
−
    P() {
 
−
        mutex.P();
 
−
        if (value <= -N)  {
 
−
            s=semaphore(0);
 
−
            okmin.enqueue(s);
 
−
            mutex.V();
 
−
            s.P();
 
−
        } else if (okmax.length() > 0) {
 
−
            s = okmax.dequeue()
 
−
            s.V();
 
−
            mutex.V();
 
−
        } else {
 
−
            value--;
 
−
            mutex.V();
 
−
        }
 
−
    }
 
−
    V() {
 
−
        mutex.P();
 
−
        if (value >= -N)  {
 
−
            s=semaphore(0);
 
−
            okmax.enqueue(s);
 
−
            mutex.V();
 
−
            s.P();
 
−
        } else if (okmin.length() > 0) {
 
−
            s = okmin.dequeue()
 
−
            s.V();
 
−
            mutex.V();
 
−
        } else {
 
−
            value++;
 
−
            mutex.V();
 
−
        }
 
−
    }
 
−
}
 
−
</source>
 
−
<br>
 
−
 
 
−
=== Esercizio g.1 ===
 
−
<nowiki>
 
−
IC = 10,10,10
 
−
COH = 4,4,4
 
−
 
−
      MAX    ATT    RES    AVAIL
 
−
P1 | 6,6,6 | 1,1,1 | 5,5,5 | 4,4,4
 
−
P2 | 6,6,6 | 1,1,1 | 5,5,5 | 5,5,5
 
−
P3 | 9,9,9 | 4,4,4 | 5,5,5 | 6,6,6</nowiki>
 
−
<br>
 
−
 
 
−
Minimizzato
 
−
 
 
−
<nowiki>
 
−
IC = 4,4,4    //massimo
 
−
COH = 1,1,1    //soldi in cassa
 
−
 
−
      MAX    ATT    RES 
 
−
P1 | 3,3,3 | 1,1,1 | 2,2,2
 
−
P2 | 3,3,3 | 1,1,1 | 2,2,2
 
−
P3 | 3,3,3 | 1,1,1 | 2,2,2</nowiki>
 
−
<br>
 
−
 
 
−
=== Esercizio g.2 (da controllare) ===
 
−
a) L'algoritmo di calcolo del working set serve a limitare il problema del trashing assicurandosi che le pagine di cui ha bisogno un processo (una loro approssimazione) siano già caricate in memoria prima di far partire il processo stesso. L'algoritmo viene eseguito ogni volta che avviene un page fault, cercando una pagina "vittima" non presente nel working set e sfrattandola, facendo posto alla pagina che occorre al processo in esecuzione.<br>
 
−
b) La lunghezza massima di un file che può essere memorizzato su un file system di tipo FAT viene calcolata moltiplicando il massimo numero di cluster (dimensione dell'unità di allocazione) identificabili per la loro dimensione. Il massimo numero di cluster identificabili dipende da quanti bit sono allocati per numerarli, e per questa distinzione esistono varie versioni di FAT (FAT12, FAT16, FAT32).<br>
 
−
FAT32 memorizza la dimensione dei file in un intero unsigned da 32bit, e non può quindi gestire un file di dimensione superiore ai 2^32 bit = ~4GB.<br>
 
−
FAT16, allocando 16bit per identificare i cluster, può contarne al massimo 2^16 (65536). Prendendo quindi, ad esempio, un file system FAT16 con cluster da 32KB, possiamo avere file grandi al massimo 32KB*65536 = ~2GB.<br>
 
−
FAT12 di conseguenza può numerare al massimo 2^12 (4096) cluster, ma dato che il numero dei settori del disco viene memorizzato in un intero signed a 16bit, la massima dimensione del disco è 2^15 = 32MB. Ovviamente, non si può memorizzare un file di grandezza superiore alla dimensione dell'unità di memorizzazione stessa, e quindi anche i file in FAT12 possono avere dimensione massima di 32MB.<br>
 
−
c) Un virus necessità l'intervento umano per essere avviato o per essere diffuso. Si attacca a programmi o file per potersi diffondere. Un worms è in grado di riprodursi e di diffondersi autonomamente, sfruttando le informazioni presenti sul computer.<br>
 
−
d) La ready queue di uno scheduler può essere vuota quando tutti i processi sono in esecuzione su diversi processori, oppure quando tutti i processi hanno terminato la loro esecuzione. È un caso fisiologico della vita di un sistema.
 
−
 
 
−
== Esame 28/05/2018 ==
 
−
[http://www.cs.unibo.it/~renzo/so/compiti/2018.05.28.tot.pdf 2018.05.28.tot.pdf]
 
−
=== Esercizio c.1 ===
 
−
<source lang="c">
 
−
Stack<int> entriesStack;
 
−
 
 
−
int vid[MAX];
 
−
condition ok2esci[MAX]
 
−
int in = 0;
 
−
int out = -1;
 
−
 
 
−
Procedure-entry: entra(int id) {
 
−
    if (in >= MAX)
 
−
        ok2entra.wait()
 
−
    vid[in++] = id;
 
−
    if (in < MAX)
 
−
        ok2entra.signal()
 
−
    else
 
−
        out = MAX - 1;
 
−
}
 
−
 
 
−
Procedure-entry: esci(int id) {
 
−
    int i;
 
−
    for (i = 0; i < in; i++)
 
−
        if (vid[i] == id)
 
−
            break; //cerco l'indice di id nel vettore vid
 
−
 
 
−
    if (i != out)
 
−
        ok2esci[i].wait();
 
−
 
 
−
    if (out > 0) {
 
−
        out--;
 
−
        ok2esci[out].signal();
 
−
    } else {
 
−
        out--;
 
−
        in = 0;
 
−
        ok2entra.signal();
 
−
    }
 
−
}
 
−
</source>
 
−
<br>
 
−
 
 
−
=== Esercizio c.1 (da controllare) ===
 
−
<source lang="c">
 
−
Monitor riempisvuota {
 
−
    Int MAXPROCESSI;
 
−
    Stack s;
 
−
    condition ok2enter;
 
−
    condition ok2exit;
 
−
 
−
    p.e void entra(getPid()){
 
−
        if( s.size() >= MAXPROCESSI)
 
−
            ok2enter.wait();
 
−
        s.insert(getPid());
 
−
        if(s.size() > MAXPROCESSI)
 
−
            ok2exit.signal()
 
−
    }
 
−
 
−
    p.e void esci(getPid()){
 
−
        if(s.size() > MAXPROCESSI && s.top == getPid()) {
 
−
            s.pop();
 
−
            ok2entra.signal()
 
−
        }
 
−
        else
 
−
            ok2exit.wait();
 
−
    }
 
−
</source>
 
−
<br>
 
−
=== Esercizio c.2 (da controllare) ===
 
−
<source lang="c">
 
−
proc[x]: x='a',...,'z'
 
−
while True:
 
−
  //c sarà il carattere stampato dal processo precedente
 
−
  (c, string) = arecv(*)
 
−
  if(string == wait){
 
−
    //mi metto in attesa di ricevere l'ACK da proc[x]
 
−
    m=arecv(x);
 
−
  }
 
−
  if (c == NONE){
 
−
    //significa che sei il primo a ricevere quella stringa
 
−
    print(x);
 
−
    if (len(string) > 1){
 
−
      //mando la wait a tutti, il primo che riceve qualcosa da stampare manda una wait a tutti
 
−
      asend(wait,*);
 
−
      int l = len(string);
 
−
      int i = 1;
 
−
      while(l != 0){
 
−
        asend(proc[string[i]], (x, string[i...]));
 
−
        //si mette in attesa di ricevere l'ACK dal processo dell'ultima lettera della parola
 
−
        m=areceive(proc[string[i]]);
 
−
        //rimando la wait al processo per ribloccarlo
 
−
        asend(wait, proc[string[i]])
 
−
        l--;
 
−
        i++;
 
−
      }
 
−
      //dopo aver finito la stampa della stringa sblocco tutti i processi
 
−
      asend(ACK, *);
 
−
    }
 
−
  }else{
 
−
    print(x);
 
−
    asend(ACK, x);
 
−
    //ricomincia il ciclo while, si rimette in attesa e il 'gestore gli rimanda la wait'
 
−
  }
 
−
</source>
 
−
<br>
 
−
== Esame 12/02/2018 ==
 
−
[http://www.cs.unibo.it/~renzo/so/compiti/2018.02.12.tot.pdf 2018.02.12.tot.pdf]
 
−
 
 
−
=== Esercizio c.1 (da controllare) ===
 
−
<source lang="c">
 
−
 
 
−
monitor bridge:
 
−
 
 
−
    int ncar
 
−
    bool boat_on_0
 
−
    bool boat_on_1      // per semplicità, quando nel codice si trova boat_on_(direction) oppure isBoat(direction)(),
 
−
                        // si valuta il valore booleano di direction e lo si applica sotto forma di stringa al simbolo
 
−
                        // ad esso adiacente
 
−
    bool is_raised
 
−
    queue waiting_mean  // i valori possibili sono: boat0, boat1 oppure car
 
−
    condition ok2go
 
−
 
 
−
    entry car_enter(direction):
 
−
        if is_raised || ncar == MAXCAR:
 
−
            waiting_mean.enqueue(car)
 
−
            ok2go.wait()
 
−
        is_raised = false
 
−
        ++ncar
 
−
 
 
−
    entry car_exit(direction):
 
−
        --ncar
 
−
        if (waiting_mean.top().isBoat() && ncar == 0) || waiting_mean.top().isCar():    // isBoat ritorna true se l'oggetto su cui
 
−
            waiting_mean.dequeue()                                                      // è invocata è boat0 oppure boat1
 
−
            ok2go.signal()
 
−
 
 
−
    entry boat_enter(direction):
 
−
        if !is_raised || boat_on_(direction):
 
−
            waiting_mean.enqueue(boat)
 
−
            ok2go.wait()
 
−
        if waiting_mean.top().isBoat(!direction)():
 
−
            waiting_mean.dequeue()
 
−
            ok2go.signal()
 
−
        is_raised = true
 
−
        boat_on_(direction) = true
 
−
 
 
−
    entry boat_exit(direction):
 
−
        boat_on_(direction) = false
 
−
        if !boat_on_(!direction):
 
−
            waiting_mean.dequeue()
 
−
            ok2go.signal()
 
−
 
 
−
</source>
 
−
 
 
−
<br>
 
−
 
 
−
=== Esercizio c.1 ===
 
−
<source lang="c">
 
−
monitor bridge  {
 
−
  int carsOnBridge = 0;
 
−
  int shipping[2] = {0, 0}; //navi da entrambe le direzioni
 
−
  int status = NONE; //UP DOWN NONE
 
−
  int last2pass = 0;    //ultimo che ha passato il ponte
 
−
  int waitingC = 0;      //coda delle macchine che aspettano
 
−
  int waitingS[2] = {0,0};  //navi che stanno aspettando
 
−
 
 
−
  condition ok2ship[2]
 
−
  condition ok2drive
 
−
 
−
entry car_enter(int direction){
 
−
    if(carsOnBridge >= MAX || status == UP || waitingS[0] + waitingS[1] > 0 ){
 
−
        waitingC++;ok2drive.wait;waitingC--;}
 
−
    status = DOWN;
 
−
    carsOnBridge++
 
−
    if (carsOnBridge < MAX)
 
−
      ok2drive.signal();    //vanno tutte le MAX car che stanno aspettando
 
−
}
 
−
entry car_exit(int direction){
 
−
    carsOnBridge--
 
−
    if (waitingS[0] + waitingS[1] == 0)
 
−
    ok2drive.signal();
 
−
    if(carsOnBridge == 0){
 
−
        ok2ship[0].signal(); ok2ship[1].signal();
 
−
    }
 
−
    if(carsOnBridge + waitingS[0] + waitingS[1] == 0)
 
−
    status = NONE
 
−
}
 
−
 
−
entry ship_enter(int direction){
 
−
    if (bridge = DOWN || shipping[direction] != 0 || waitingC > 0)
 
−
    {
 
−
        waitingS[i]++; ok2ship[i].wait(); waitingS[i]--;
 
−
    }
 
−
    isBridgeUp = false;
 
−
    shipping[i] = 1;
 
−
 
−
entry ship_exit(int direction){
 
−
      shipping[i] = 0;
 
−
      if (waitingC == 0)
 
−
          ok2ship[i].signal()
 
−
      else if(shipping[1-i] == 0)
 
−
          ok2drive.signal();
 
−
      if(carsOnBridge + waitingS[0] + waitingS[1] == 0)
 
−
      status = NONE
 
−
}
 
−
</source>
 
−
 
 
−
=== Esercizio c.1 (da controllare) ===
 
−
<source lang="c">
 
−
monitor bridge {
 
−
 
 
−
  UP=0;
 
−
  DOWN=1;
 
−
  bridgeis = DOWN;
 
−
 
 
−
  bool carAreExiting = false;
 
−
 
 
−
  condition ok2drive;
 
−
  condition ok2barca[2];
 
−
 
 
−
  waitingCar = 0;
 
−
  carOnBridge = 0;
 
−
 
 
−
  boatWaiting[2] = {0,0};
 
−
  boatIsPassing[2] = {false,false}
 
−
 
 
−
  entry car_enter(direction) {
 
−
 
 
−
    if (bridgeis == DOWN)
 
−
      if(carOnBridge == MAXCAR)
 
−
        waitingCar++;
 
−
        ok2drive.wait();
 
−
        waitingCar--;
 
−
      else if (carAreExiting)
 
−
        waitingCar++;
 
−
        ok2drive.wait();
 
−
        waitingCar--;
 
−
    else
 
−
      if (boatIsPassing[0] || boatIsPassing[1])
 
−
        waitingCar++;
 
−
        ok2drive.wait();
 
−
        waitingCar--;
 
−
        bridgeis = DOWN;
 
−
 
 
−
    carOnBridge++;
 
−
    carAreExiting = false;
 
−
    if(carOnBridge < MAXCAR && !carAreExiting)
 
−
      ok2drive.signal();
 
−
     
 
−
  }
 
−
 
 
−
  entry car_exit(direction) {
 
−
 
 
−
    carOnBridge--;
 
−
    carAreExiting = true;
 
−
 
 
−
    if(carOnBridge == 0)
 
−
      carAreExiting = false;
 
−
      if(boatWaiting[0] > 0)
 
−
        bridgeis = UP;
 
−
        ok2barca[0].signal();
 
−
      else if (boatWaiting[1] > 0)
 
−
        bridgeis = UP;
 
−
        ok2barca[1].signal();
 
−
      else
 
−
        ok2drive.signal();
 
−
  }
 
−
 
 
−
  entry boat_enter(direction) {
 
−
 
 
−
    if (bridgeis == UP)
 
−
    | if (boatIsPassing[direction] == true)
 
−
    | |  boatWaiting[direction]++;
 
−
    | |  ok2barca.wait();
 
−
    | |  boatWaiting[direction]--;
 
−
    else
 
−
    | if (carOnBridge > 0)
 
−
    | | boatWaiting[direction]++;
 
−
    | | ok2barca.wait();
 
−
    | | boatWaiting[direction]--;
 
−
    | | bridgeis = UP;
 
−
 
 
−
    boatIsPassing[direction] = true;
 
−
 
 
−
    if(boatIsPassing[1-direction] == false && boatWaiting[1-direction] > 0)
 
−
      ok2barca[1-direction].signal();
 
−
   
 
−
  }
 
−
 
 
−
  entry boat_exit(direction) {
 
−
 
 
−
    boatIsPassing[direction] = false;
 
−
 
 
−
    if (boatIsPassing[1-direction] == false)
 
−
      if (waitingCar > 0)
 
−
        bridgeis = DOWN;
 
−
        ok2drive.signal();
 
−
    else
 
−
        if (waitingCar == 0)
 
−
          ok2barca[direction].signal();
 
−
         
 
−
  }
 
−
</source>
 
−
 
 
−
 
 
−
=== Esercizio c.1 (sbagliato) ===
 
−
<source lang="c">
 
−
monitor bridge
 
−
  condition ok2passCar;
 
−
  condition ok2passBoat;
 
−
  condition ok2up;
 
−
  condition ok2down;
 
−
  int carOnBridge[2] = 0; //2 sensi di marcia
 
−
  int boatUnderBridge[2] = 0;
 
−
  boolean bridge_down = false; //vuol dire che il ponte parte alzato, true ponte abbassato
 
−
 
 
−
  procedure entry car_enter(direction){
 
−
      if(bridge_down && carOnBridge[direction] < MAXCAR){
 
−
        carOnBridge[direction]++;
 
−
        ok2passCar.signal();
 
−
      }else if (bridge_down && boatUnderBridge[0] == 0 && boatUnderBridge[1] == 0){
 
−
        //se non ci sono navi in transito e arriva una macchina abbassa ponte
 
−
        ok2down.signal();
 
−
        ok2passCar.signal();
 
−
        ok2passBoat.wait();
 
−
      }else{
 
−
        ok2passCar.wait();
 
−
      }
 
−
  }   
 
−
       
 
−
  procedure entry car_exit(direction){
 
−
      carOnBridge[direction]--;
 
−
      if(carOnBridge[0] == 0 && carOnBridge[1] == 0){
 
−
        bridge_down = false;
 
−
        ok2up.signal();
 
−
      }else{
 
−
        ok2up.wait();
 
−
      }
 
−
  }
 
−
     
 
−
  procedure entry boat_enter(direction){
 
−
      if(!bridge_down && boatUnderBridge[direction] < 1){
 
−
        boatUnderBridge[direction]++;
 
−
        ok2passBoat.signal();
 
−
      }else if(!bridge_down && carOnBridge[0] == 0 && carOnBridge[1] == 0){
 
−
        ok2up.signal();
 
−
        ok2passBoat.signal();
 
−
        ok2passCar.wait();
 
−
      }else {
 
−
        ok2passBoat.wait();
 
−
      }
 
−
  }
 
−
     
 
−
  procedure entry boat_exit(direction){ 
 
−
      boatUnderBridge[direction]--;
 
−
      if(boatUnderBridge[0] == 0 && boatUnderBridge[1] == 0){
 
−
        bridge_down = true;
 
−
        ok2down.signal();
 
−
      }else{
 
−
        ok2down.wait();
 
−
      }
 
−
  }
 
−
</source>
 
−
 
 
−
=== Esercizio c.1 2o (sbagliato) ===
 
−
<source lang="c">
 
−
#define car 1
 
−
#define ship 2
 
−
#define fromDX 1
 
−
#define fromSX 0
 
−
 
 
−
monitor bridge  {
 
−
  int carsOnBridge = 0;
 
−
  int shippingDX = 0; //nave che sta passando dal lato destro
 
−
  int shippingSX = 0; //nave che sta passando dal lato sinistro
 
−
  bool isBridgeUp = false;
 
−
  int last2pass = 0;    //ultimo che ha passato il ponte
 
−
  int waitingS = 0;  //navi che stanno aspettando
 
−
  int waitingC = 0 ; //auto che stanno aspettando
 
−
 
 
−
  condition ok2ship
 
−
  condition ok2drive
 
−
 
 
−
entry car_enter(int direction){
 
−
    //un auto si ferma se il numero di auto sul ponte è massimo
 
−
    //e se l'ultima a passare è stata un auto mentre ci sono navi in attesa
 
−
    if(carsOnBridge == MAX || isBridgeUp || (last2pass==car && waitingS > 0) ){
 
−
        waitingC++;
 
−
        ok2drive.wait;
 
−
    }
 
−
    carsOnBridge++;
 
−
    waitingC--;
 
−
}
 
−
 
 
−
entry car_exit(int direction){
 
−
    carsOnBridge--;
 
−
    last2pass = car;
 
−
    if(carsOnBridge == 0 && waitingS>0){
 
−
        isBrigdeUp = true;
 
−
        ok2ship.signal;
 
−
    }
 
−
}
 
−
 
 
−
entry ship_enter(int direction){
 
−
    //se la barca viene da destra
 
−
    if(direction == fromDX){
 
−
        //si ferma anche quando c'è una nave che sta già attraversando nella sua stessa direzione
 
−
        if (isBridgeup == false || shippingDX || (last2pass==ship && waitingC > 0) ){
 
−
            waitingS++;
 
−
            ok2ship.wait;
 
−
        }
 
−
        if (waitingS > 0)
 
−
            waitingS--;
 
−
        shippingDX = 1;
 
−
        }
 
−
    //se la barca viene da sinistra
 
−
    else if(direction == fromSX){
 
−
        if (isBridgeup == false || shippingSX || ( (last2pass==ship && waitingC > 0))){
 
−
        waitingS++;
 
−
        ok2ship.wait;
 
−
        }
 
−
        if (waitingS > 0)
 
−
            waitingS--;       
 
−
        shippingSX = 1;
 
−
   
 
−
    }
 
−
}
 
−
 
 
−
entry ship_exit(int direction){
 
−
        if(direction == fromDX)
 
−
            shippingDX = 0;
 
−
        else if (direction == fromSX)
 
−
            shippingSX = 0;
 
−
        last2pass = ship;
 
−
        if(shippingDX == 0 && shippingSX == 0 && waitingC)
 
−
            isBrigdeUp == false;
 
−
            ok2drive.signal;
 
−
        else if(shippingDX == 0 && shippingSX == 0 && waitingS > 0)
 
−
            ok2ship.signal;   
 
−
    }
 
−
}
 
−
</source>
 
−
 
 
−
=== Esercizio c.2 (sbagliato) ===
 
−
 
 
−
# (Ri)Controllato dall'utente [[User:Acsor|Acsor]] ([[User talk:Acsor|talk]]) in data 26/08/2020
 
−
 
 
−
<source lang="python">
 
−
list printed_msg;  # questa è una variabile condivisa che ai fini dell'esercizio non si può utilizzare (message passing)
 
−
 
 
−
process server[i]:
 
−
  while true:
 
−
    <msg, pid> = arecv(*)
 
−
 
 
−
    if printed_msg.length == 0 or <msg, pid> is not in printed_msg:
 
−
      printed_msg.append(<msg,id>)
 
−
      print(msg)
 
−
</source>
 
−
 
 
−
=== Esercizio c.2 (da controllare) ===
 
−
Nello svolgimento seguente, receiver incapsula l'ambiente privato del processo; _peers rappresenta il vettore di processi "fratelli" ai quali può essere chiesto di stampare un messaggio, mentre _printed contiene l'hash di tutti i messaggi stampati dal processo locale. Si suppone che istanze della classe receiver possano essere passate come parametro ad areceive() ed asend() (non implementate).
 
−
 
 
−
<source lang="python">
 
−
class receiver:
 
−
    def __init__(self, peers):
 
−
        """
 
−
        :param peers: list of processes this process communicates with.
 
−
        """
 
−
        self._peers = tuple(peers)
 
−
        self._printed = list()
 
−
   
 
−
    def run(self):
 
−
        while True:
 
−
            process, message = areceive(ANY)
 
−
 
 
−
            if process in self._peers:
 
−
                self._reply_query(process, message)
 
−
            else:
 
−
                self._print(process, message)
 
−
 
 
−
    def _print(self, sender, message):
 
−
        h = hash(message.text)
 
−
 
 
−
        if h not in self._printed and not self._printed_from_peers(message):
 
−
            self._printed.append(h)
 
−
            print(message.text)
 
−
 
 
−
    def _reply_query(self, sender, h):
 
−
        """
 
−
        Invoked when the current process receive a "query" from a peer process.
 
−
        `h` contains the hash of a message which may or may have not been
 
−
        sent from this process; if it was sent, the reply is `Yes`, otherwise `No`.
 
−
        """
 
−
        reply = "Yes" if int(h) in self._printed else "No"
 
−
        asend(sender, reply)
 
−
 
 
−
    def _printed_from_peers(self, message):
 
−
        """
 
−
        :return: `True` if this message has already been printed from any of the
 
−
        peer processes, `False` otherwise.
 
−
        """
 
−
        h = hash(message)
 
−
 
 
−
        for p in self._peers:
 
−
            asend(p, str(h))
 
−
 
 
−
        for p in self._peers:
 
−
            _, reply = areceive(p)
 
−
 
 
−
            if reply.text == "Yes":
 
−
                return True
 
−
            else if reply.text != "No":
 
−
                # If the response is neither "Yes" nor "No", then we have got a query
 
−
                self._reply_query(p, reply)
 
−
 
 
−
        return False
 
−
</source>
 
−
 
 
−
=== Esercizio g.1 (da controllare) ===
 
−
Sulla base dei valori in entrata, è possibile costruire le matrici Allocation (q.tà di risorse allocate per processo e per tipo), Need (q.tà di risorse che ogni processo potrebbe ancora chiedere) e il vettore Available (num. di risorse correntemente disponibili).
 
−
 
 
−
{| class="wikitable" style="float: left"
 
−
! colspan=3 | Allocation
 
−
|-
 
−
  !  !! A !! B
 
−
|-
 
−
  | p1 || 4 || 5
 
−
|-
 
−
  | p2 || 3 || 3
 
−
|-
 
−
  | p3 || 2 || 4
 
−
|}
 
−
 
 
−
{| class="wikitable" style="float: left; margin-left: 1em"
 
−
! colspan=3 | Need
 
−
|-
 
−
  !    !! A !! B
 
−
|-
 
−
  | p1 || 6 || 8
 
−
|-
 
−
  | p2 || 6 || 3
 
−
|-
 
−
  | p3 || 6 || 8
 
−
|}
 
−
 
 
−
 
 
−
{| class="wikitable" style="float: left; margin-left: 1em"
 
−
! colspan=2 | Available
 
−
|-
 
−
  ! A !! B
 
−
|-
 
−
  | x || y
 
−
|}
 
−
 
 
−
<br/><br/><br/><br/><br/><br/><br/>
 
−
 
 
−
Nel caso delle risorse di tipo A, deve aversi x >= 6 in quanto un processo dovrà essere selezionato come primo nella permutazione dell'algoritmo del banchiere multivaluta, e tutti quelli correnti hanno lo stesso valore Need(i)(1); per ciò che riguarda le risorse di tipo B, possiamo ragionare per esaustione
 
−
 
 
−
* Se il primo processo della permutazione è p1, allora y >= 8 (con questo valore posso soddisfare la richiesta di p1 e in seguito tutte le altre)
 
−
* Se il primo processo della permutazione è p2, allora y >= 5: con questo valore è possibile soddisfare la richiesta di p2; una volta che esso avrà finito, restituirà 3 unità della risorsa B, che permetteranno di soddisfare sia le richieste di A sia quelle di C
 
−
* Se il primo processo della permutazione è p3, allora y >= 8 (ragionamento analogo come per p1)
 
−
 
 
−
Volendo scegliere il minimo, y >= 5, ed in conclusione (x, y) >= (6, 5).
 
−
 
 
−
''Svolgimento basato in parte sull'approccio di Operating System Concepts di Silberschatz. et al, 9th edition, cap. 7.''
 
−
 
 
−
=== Esercizio g.2 (da controllare) ===
 
−
# Può accadere che il sistema torni in uno stato di safety o che invece porti a deadlock. Diversamente uno stato di safety non può portare direttamente ad uno stato di deadlock, ma solo ad uno di non-safety.
 
−
# Selezionare uno o più tra i processi attivi e sospenderli, salvando il loro stato su memoria secondaria operando delle operazioni di swap-out, finché l'insieme dei frame nella memoria centrale non è in grado di soddisfare tutti i processi rimasti attivi.
 
−
# La scelta è determinata perlopiù dal fattore costo. Con un sistema RAID 1 è possibile ripristinare un disco guasto molto brevemente, in quanto le operazioni coinvolte prevedono una semplice ricopiatura dal disco di backup; con un sistema RAID 5 il ripristino del disco guasto deve coinvolgere tutti i dischi dell'intero array, e ciò può richiedere anche ore per dischi di grandi dimensioni. D'altra parte RAID 1 è più costoso (con n dischi, posso memorizzare tanta informazione quanto potrei con n / 2 dischi) rispetto a RAID 5 dove, tra gli n dischi, complessivamente soltanto uno è destinato alle informazioni di ridondanza.
 
−
# ''Completare.''
 
−
 
 
−
== Esame 11/09/2017 ==
 
−
[http://www.cs.unibo.it/~renzo/so/compiti/2017.09.11.tot.pdf 2017.09.11.tot.pdf]
 
−
=== Esercizio c.1 ===
 
−
<source lang="c">
 
−
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();
 
−
 
 
−
</source>
 
−
<br>
 
−
 
 
−
=== Esercizio c.2 (da controllare) ===
 
−
<source lang="c">
 
−
// 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]
 
−
    }
 
−
}
 
−
</source>
 
−
<br>
 
−
 
 
−
== Esame 17/07/2017 ==
 
−
[http://www.cs.unibo.it/~renzo/so/compiti/2017.07.17.tot.pdf 2017.07.17.tot.pdf]
 
−
=== Esercizio c.1 ===
 
−
<source lang="c">
 
−
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;
 
−
        }
 
−
}
 
−
 
 
−
 
 
−
 
 
−
</source>
 
−
 
 
−
 
 
−
=== Esercizio c.2 (da controllare) ===
 
−
<source lang="c">
 
−
si, è possibile:
 
−
 
 
−
Implementare asend e arecv date bsend e brecv
 
−
 
 
−
asend(pid_t, msg_type msg){
 
−
    bsend (<pid_t dst, msg>);
 
−
}
 
−
 
 
−
arecv(*){
 
−
  pid_t act = getpid(); \\ act = proprio pid
 
−
  do{
 
−
    <dst, msg> = brecv(*);
 
−
  }while (dst =! act)
 
−
  return msg;
 
−
}
 
−
 
 
−
</source>
 
−
<br>
 
−
 
 
−
== Esame 19/06/2017 ==
 
−
[http://www.cs.unibo.it/~renzo/so/compiti/2017.06.19.tot.pdf 2017.06.19.tot.pdf]
 
−
=== Esercizio c.1 (da controllare)===
 
−
<source lang="c">
 
−
#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;
 
−
}
 
−
</source>
 
−
<br>
 
−
 
 
−
== Esame 29/05/2017 ==
 
−
[http://www.cs.unibo.it/~renzo/so/compiti/2017.05.29.tot.pdf 2017.05.29.tot.pdf]
 
−
=== 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
 
−
 
 
−
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.
 
−
</source>
 
−
<br>
 
−
 
 
−
== Esame 14/02/2015 ==
 
−
[http://www.cs.unibo.it/~renzo/so/compiti/2015.02.14.tot.pdf 2015.02.14.tot.pdf]
 
−
=== Esercizio c.1 (da controllare) ===
 
−
<source lang="c">
 
−
monitor altcolbb {
 
−
 
 
−
  generic_type valueBuf[MAX];
 
−
  int front = rear = 0;
 
−
 
 
−
  bool isFull = false;
 
−
 
 
−
  condition ok2write[2]; //gli indici sono i colori (red=0, blue=1)
 
−
 
 
−
  lastColor = None;
 
−
 
 
−
  entry void write(color_t color, generic_type val) {
 
−
 
 
−
    if (front == rear)
 
−
        if(isFull)
 
−
          ok2write[color].wait();
 
−
    else
 
−
      if (lastColor == color)
 
−
        ok2write[color].wait();
 
−
             
 
−
    valueBuf[front] = val;
 
−
    front = (front+1) % MAX;
 
−
    lastColor = color;
 
−
 
 
−
    if (front == rear)
 
−
      isFull = true;
 
−
    else
 
−
      ok2write[1-color].signal();
 
−
 
 
−
    ok2read.signal();
 
−
       
 
−
  }
 
−
 
 
−
  entry generic_type read(void) {
 
−
 
 
−
    if (rear == front)
 
−
      if (!isFull)
 
−
        ok2read.wait();
 
−
 
 
−
    generic_type tmpValue = valueBuf[rear];
 
−
   
 
−
    rear = (rear + 1) % MAX;
 
−
    if (rear == front)
 
−
      isFull = false;
 
−
      color_t tmpColor = lastColor;
 
−
      lastColor = None;
 
−
      ok2write[tmpColor].signal();  //quando un lettore legge l'ultimo elemento
 
−
                                    //dal buffer, ci possono solo essere scrittori
 
−
                                    //in attesa che abbiano lo stesso colore
 
−
                                    //dell'ultimo elemento.
 
−
    else
 
−
      ok2write[1-lastColor].signal();
 
−
     
 
−
    return tmpValue;
 
−
     
 
−
  }
 
−
 
 
−
}
 
−
</source>
 
−
<br>
 
−
 
 
−
 
 
−
=== Esercizio c.1 (da controllare) ===
 
−
<source lang="c">
 
−
#define MAX n
 
−
 
 
−
condition ok2read;
 
−
condition ok2write;
 
−
condition ok2red;
 
−
condition ok2blue;
 
−
 
 
−
queue buffer;
 
−
 
 
−
Procedure entry: void write(color_t color, generic_type val)
 
−
{
 
−
    if(buffer.lenght() >= MAX)
 
−
        ok2write.wait();
 
−
    if((<color> == buffer.last()) == color)
 
−
    {
 
−
        if(color == red)
 
−
            ok2red.wait();
 
−
        else
 
−
            ok2blue.wait();
 
−
    }
 
−
    buffer.enqueue(<color, val>);
 
−
    ok2read.signal();
 
−
    if(buffer.lenght() < MAX)
 
−
    {
 
−
        if(color == red)
 
−
            ok2blue.signal();
 
−
        else
 
−
            ok2red.signal();
 
−
    }
 
−
}
 
−
 
 
−
Procedure entry: generic_type read(void)
 
−
{
 
−
    generic_type val;
 
−
    if(buffer.lenght == 0)
 
−
        ok2read.wait();
 
−
    <val> = buffer.dequeue();
 
−
    ok2write.signal()
 
−
    return val;
 
−
}
 
−
</source>
 
−
<br>
 
−
 
 
−
=== Esercizio c.2 (da controllare) ===
 
−
 
 
−
* Verificato dall'utente ? in data ?
 
−
 
 
−
Il programma dispone di una mutex per l'accesso protetto alla variabile n, e dei due semafori s1 ed s2 per regolare l'alternanza tra i thread A e AB. Sulla base di essi, e del fatto che entrambi i thread eseguono 2 cicli, è possibile affermare (verificare) che
 
−
 
 
−
* L'alternanza dei due thread è A-AB-A-AB o
 
−
* L'alternanza dei due thread è AB-A-AB-A
 
−
 
 
−
Infatti se il thread A svolgesse due cicli consecutivamente, invocherebbe s1.P() due volte senza fare mai ricorso a s1.V() (ragionamento analogo per AB); pertanto è necessario attendere l'intervento dell'altro thread in attesa di una chiamata su s1.V().
 
−
 
 
−
Per concludere, i possibili valori di n al termine del programma saranno, in corrispondenza delle due diramazioni elencate sopra
 
−
 
 
−
* n = 12
 
−
* n = 5
 
−
 
 
−
=== Esercizio g.1 ===
 
−
 
 
−
* Verificato dall'utente [[User:Acsor|Acsor]] in data 23/08/2020. Ritengo sia: corretto
 
−
* Verificato dall'utente ? in data ?
 
−
 
 
−
==== Punto a) ====
 
−
MIN:
 
−
<nowiki>
 
−
Stringa di riferimenti: 0 1 2 3 4 5 0 1 2 3 4 0 1 2 3 0 1 2 0 1 0
 
−
              Frame 1: 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0
 
−
              Frame 2:  1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1
 
−
              Frame 3:    2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2
 
−
              Frame 4:      3 4 5 5 5 5 3 4 4 4 4 3 3 3 3 3 3 3
 
−
</nowiki>
 
−
 
 
−
FIFO:
 
−
<nowiki>
 
−
Stringa di riferimenti: 0 1 2 3 4 5 0 1 2 3 4 0 1 2 3 0 1 2 0 1 0
 
−
              Frame 1: 0 0 0 0 4 4 4 4 2 2 2 2 1 1 1 1 1 1 1 1 1
 
−
              Frame 2:  1 1 1 1 5 5 5 5 3 3 3 3 2 2 2 2 2 2 2 2
 
−
              Frame 3:    2 2 2 2 0 0 0 0 4 4 4 4 3 3 3 3 3 3 3
 
−
              Frame 4:      3 3 3 3 1 1 1 1 0 0 0 0 0 0 0 0 0 0
 
−
</nowiki>
 
−
 
 
−
==== Punto b) ====
 
−
<nowiki>
 
−
Stringa di riferimenti: 0 1 2 3 4 0 1 2 3 0 1 4 2 0 3 4 1 2 3 4
 
−
              Frame 1: 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 1 1 1 1
 
−
              Frame 2:  1 1 1 1 1 1 1 1 1 1 1 2 2 2 2 2 2 2 2
 
−
              Frame 3:    2 2 2 2 2 2 3 3 3 3 3 3 3 3 3 3 3 3
 
−
              Frame 4:      3 4 4 4 4 4 4 4 4 4 4 4 4 4 4 4 4
 
−
</nowiki>
 
−
<br>
 
−
 
 
−
=== Esercizio g.2 (da controllare) ===
 
−
 
 
−
* Verificato dall'utente ? in data ?
 
−
* ...
 
−
 
 
−
----
 
−
 
 
−
# Frammentazione interna: allocazioni di pagine la cui dimensione è strettamente maggiore di quella effettivamente richiesta.  Frammentazione esterna: nessuno. Infatti ogni spazio (pagina) allocato e liberato è prima o poi riallocato.
 
−
# Se non viene utilizzato un sistema di caching, una lettura diretta a più blocchi di un file di grandi dimensioni richiede: la lettura della FAT, solitamente posta all'inizio di un [[Glossario#Volume|volume]] (e dunque, su dischi rotazionali, in una traccia differente da quella attuale o da quella del blocco da leggere); la lettura del blocco stesso, e dunque lo spostamento della testina nella traccia e nel settore di interesse
 
−
# Uno scheduling a priorità statica può essere utile ad un processo interattivo, dove è necessario mantenersi all'interno di date soglie temporali o semplicemente svolgere un dato compito con meno ritardo possibile; esempi concreti: un processo che faccia streaming video; un processo appartenente ad un server il cui obiettivo primario è soddisfare le richieste dei propri client il prima possibile, ma dove può anche essere svolta qualche attività dai processi locali (es. programmi applicativi). In uno scheduling a priorità statica, se la presenza di processi ad alte priorità è costante, possono verificarsi indesiderati fenomeni di ''starvation'' nei confronti di processi meno prioritari.
 
−
# ''Domanda puramente nozionistica, la cui risposta può essere ricavata consultando note, lucidi o libri di testo.''
 
−
 
 
−
== Esame 20/01/2015 ==
 
−
[http://www.cs.unibo.it/~renzo/so/compiti/2015.01.20.tot.pdf 2015.01.20.tot.pdf]
 
−
 
 
−
=== Esercizio c.1 (da controllare) ===
 
−
 
 
−
* Controllato dall'utente [[User:Acsor|Acsor]] in data 21/08/2020
 
−
* Controllato dall'utente ? in data ?
 
−
* ...
 
−
 
 
−
<source lang="c">
 
−
#define MAX n
 
−
 
 
−
condition ok2read;
 
−
condition ok2write;
 
−
 
 
−
queue buffer;
 
−
int waiting_write = 0;
 
−
int waiting_read = 0;
 
−
 
 
−
Procedure entry: void write(generic_type val) {
 
−
    if (buffer.lenght() >= MAX) {
 
−
        if (waiting_write >= MAX) {
 
−
            buffer.dequeue(); // il valore va perso
 
−
            ok2write.signal();
 
−
        }
 
−
 
 
−
        waiting_write++;
 
−
        ok2write.wait();
 
−
        waiting_write--;
 
−
    }
 
−
 
 
−
    buffer.enqueue(val);
 
−
    ok2read.signal();
 
−
}
 
−
 
 
−
Procedure entry: generic_type read(void) {
 
−
    generic_type val;
 
−
 
 
−
    if (buffer.lenght() == 0) {
 
−
        if (waiting_read >= MAX)
 
−
            ok2read.signal();
 
−
 
 
−
        waiting_read++;
 
−
        ok2read.wait();
 
−
        waiting_read--:
 
−
    }
 
−
 
 
−
    val = buffer.length() == 0 ? NULL: buffer.dequeue();
 
−
    ok2write.signal();
 
−
 
 
−
    return val;
 
−
}
 
−
</source>
 
−
<br>
 
−
 
 
−
=== Esercizio g.1 ===
 
−
 
 
−
* Controllato e corretto dall'utente [[User:Acsor|Acsor]] in data 21/08/2020
 
−
 
 
−
==== Punto a) ====
 
−
===== Algoritmo MIN =====
 
−
 
 
−
<nowiki>
 
−
Stringa di riferimenti: 1 2 3 4 5 1 2 3 4 1 2 3 1 2 1
 
−
              Frame 1: 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1
 
−
              Frame 2:  2 2 2 2 2 2 2 2 2 2 2 2 2 2
 
−
              Frame 3:    3 4 5 5 5 3 4 4 4 3 3 3 3
 
−
</nowiki>
 
−
 
 
−
===== Algoritmo LRU =====
 
−
<nowiki>
 
−
Stringa di riferimenti: 1 2 3 4 5 1 2 3 4 1 2 3 1 2 1
 
−
              Frame 1: 1 1 1 4 4 4 2 2 2 1 1 1 1 1 1
 
−
              Frame 2:  2 2 2 5 5 5 3 3 3 2 2 2 2 2
 
−
              Frame 3:    3 3 3 1 1 1 4 4 4 3 3 3 3
 
−
</nowiki>
 
−
 
 
−
==== Punto b) ====
 
−
 
 
−
Poiché non è specificato quale dei due algoritmi precedenti applicare, sono state considerate soluzioni per ognuno di essi
 
−
 
 
−
===== Algoritmo MIN (da controllare) =====
 
−
(È possibile ottenere una stringa più breve?)
 
−
 
 
−
<nowiki>
 
−
4 3 2 1 5 3 2 1 4 5 3 2 1 3 2 4 5 1 2 4 3 1 5 4 2 1 3 4 
 
−
-------------------------------------------------------
 
−
4|4|4|4|5|  5  |5|  5  |1|  1  |1|  1  |1|  1  |  1 
 
−
|3|3|3|3|  3  |3|  3  |3|  3  |5|  5  |5|  5  |  2 
 
−
| |2|2|2|  2  |2|  2  |2|  2  |2|  2  |3|  3  |  3 
 
−
| | |1|1|  1  |4|  4  |4|  4  |4|  4  |4|  4  |  4 
 
−
 
 
−
</nowiki>
 
−
 
 
−
===== Algoritmo LRU =====
 
−
<nowiki>
 
−
Stringa di riferimenti: 4 3 2 1 5 3 2 4 1 5 4 3 1 2
 
−
              Frame 1: 4 4 4 4 5 5 5 5 1 1 1 1 1 1
 
−
              Frame 2:  3 3 3 3 3 3 3 3 5 5 5 5 2
 
−
              Frame 3:    2 2 2 2 2 2 2 2 2 3 3 3
 
−
              Frame 4:      1 1 1 1 4 4 4 4 4 4 4
 
−
</nowiki>
 
−
<br>
 
−
 
 
−
== Esame 16/07/2014 ==
 
−
[http://www.cs.unibo.it/~renzo/so/compiti/2014.07.16.tot.pdf 2014.07.16.tot.pdf]
 
−
=== 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 ===
 
−
<source lang=html5>
 
−
    0241302 ==> soluzione corretta
 
−
(0)2  2200
 
−
(1)3  1111
 
−
(2)4  4442
 
−
(3)0  0333
 
−
 
 
−
    2 3 4 0 1 2 3 4  0  1  2  3 ==> soluzione proposta, non corretta perchè non è la stringa più corta
 
−
2          1 1 1 1  0  0  0  0
 
−
3          3 2 2 2  2  1  1  1
 
−
4          4 4 3 3  3  3  2  2
 
−
0          0 0 0 4  4  4  4  3
 
−
</source>
 
−
<br>
 
−
 
 
−
== Esame 03/06/2014 ==
 
−
[http://www.cs.unibo.it/~renzo/so/compiti/2014.06.03.tot.pdf 2014.06.03.tot.pdf]
 
−
=== Esercizio c.1 (da controllare) ===
 
−
<source lang="c">
 
−
monitor sabelev
 
−
{
 
−
    #define N n //numero dei piani
 
−
 
 
−
    condition ok2enter[N][2]; //piano di partenza e direzione
 
−
    condition ok2exit[N]; //piano di arrivo
 
−
 
 
−
    procedure entry: void atfloor(int floor, int direction)
 
−
    {
 
−
        ok2exit[floor].signal(); //da il via al primo del piano che deve uscire
 
−
        ok2enter[floor][direction].signal(); //da il via al primo del piano che deve entrare e deve andare in questa direzione
 
−
    }
 
−
 
 
−
    procedure entry: void enter(int from, int to)
 
−
    {
 
−
        int direction;
 
−
        if(to > from) //controllo sulla direzione
 
−
            direction = 0;
 
−
        else
 
−
            direction = 1;
 
−
 
 
−
        ok2enter[from][direction].wait(); //mi fermo in attesa che arrivi l'ascensore
 
−
        ok2enter[from][direction].signal(); //quando arriva l'ascensore do il via a quello in attesa dopo di me
 
−
        ok2exit[to].wait(); //mi fermo dentro all'ascensore in attesa di uscire
 
−
    }
 
−
 
 
−
    procedure entry: void exit(int from, int to)
 
−
    {
 
−
        ok2exit[to].signal(); //do il via ad un altro che deve uscire a questo piano come me
 
−
    }
 
−
 
 
−
}
 
−
</source>
 
−
<br>
 
−
 
 
−
== Esame 21/02/2014 ==
 
−
[http://www.cs.unibo.it/~renzo/so/compiti/2014.02.21.tot.pdf 2014.02.21.tot.pdf]
 
−
=== Esercizio c.1 (da controllare) ===
 
−
<source lang="c">
 
−
monitor bbwl
 
−
{
 
−
    #define MAXELEM n
 
−
 
 
−
    condition ok2read;
 
−
    condition ok2write;
 
−
    condition ok2log;
 
−
 
 
−
    queue q1;
 
−
    queue q2;
 
−
 
 
−
    procedure entry: void write(eltype elem)
 
−
    {
 
−
        if (q1.size() >= MAXELEM)
 
−
            ok2write.wait();
 
−
        q1.enqueue(elem);
 
−
        ok2log.signal();
 
−
    }
 
−
 
 
−
    procedure entry: eltype read()
 
−
    {
 
−
        if (q2.size == 0)
 
−
            ok2read.wait();
 
−
        eltype elem = q2.dequeue();
 
−
        ok2write.signal();
 
−
        return elem;
 
−
    }
 
−
 
 
−
    procedure entry: eltype log()
 
−
    {
 
−
        if (q1.size() == 0)
 
−
            ok2log.wait();
 
−
        eltype elem = q1.dequeue();
 
−
        q2.enqueue(elem);
 
−
        ok2read.signal()
 
−
        return elem;
 
−
    }
 
−
}
 
−
</source>
 
−
<br>
 
−
 
 
−
== Esame 11/05/2011 ==
 
−
[http://www.cs.unibo.it/~renzo/so/compiti/2011-05-11.con.pdf 2011-05-11.con.pdf]
 
−
=== Esercizio 2 (da controllare) ===
 
−
<source lang="c">
 
−
stack s;
 
−
semaphore mutex(1);
 
−
 
 
−
lifocs_enter()
 
−
{
 
−
    s.push(getpid());
 
−
    mutex.p();
 
−
    while(s.lastElement() != getpid())
 
−
    {
 
−
        mutex.v();
 
−
        mutex.p();
 
−
    }
 
−
    s.pop();
 
−
}
 
−
 
 
−
lifocs_exit()
 
−
{
 
−
    mutex.v();
 
−
}
 
−
</source>
 
−
<br>
 
−
 
 
−
== Esame Pratico 21/09/2018 ==
 
−
http://www.cs.unibo.it/~renzo/so/pratiche/2018.09.21.pdf
 
−
=== Esercizio 1 ===
 
−
<source lang="c">
 
−
      #define _GNU_SOURCE
 
−
      #include <sys/signalfd.h>
 
−
      #include <signal.h>
 
−
      #include <sys/types.h>
 
−
      #include <sys/stat.h>
 
−
      #include <fcntl.h>
 
−
      #include <stdio.h>
 
−
      #include <unistd.h>
 
−
      #include <time.h>
 
−
      #include <string.h>
 
−
 
 
−
 
 
−
int main(int argc, char * argv[]){
 
−
        sigset_t mask;
 
−
        struct signalfd_siginfo fdsi;
 
−
        int fd;
 
−
        char* t;
 
−
        char* filename;
 
−
 
 
−
        sigemptyset(&mask);
 
−
        sigaddset(&mask, SIGUSR1);
 
−
        sigaddset(&mask, SIGUSR2);
 
−
        sigprocmask(SIG_SETMASK, &mask, NULL);
 
−
 
 
−
        int sigfd = signalfd(-1, &mask, 0);
 
−
 
 
−
        for(;;){
 
−
                read(sigfd, &fdsi, sizeof(struct signalfd_siginfo));
 
−
                if(fdsi.ssi_signo == SIGUSR1){
 
−
                        asprintf(&filename, "./%u", fdsi.ssi_pid);
 
−
                        fd = open(filename, O_APPEND | O_CREAT | O_WRONLY);
 
−
                        time_t stime = time(NULL);
 
−
                        t = ctime(&stime);
 
−
                        write(fd, t, sizeof(char)*strlen(t));
 
−
                        close(fd);
 
−
                        }
 
−
                if(fdsi.ssi_signo == SIGUSR2){
 
−
                        asprintf(&filename, "./%u", fdsi.ssi_pid);
 
−
                        fd = open(filename, O_APPEND | O_CREAT | O_WRONLY);
 
−
                        time_t stime = time(NULL);
 
−
                        t = ctime(&stime);
 
−
                        write(fd, t, sizeof(char)*strlen(t));
 
−
                        close(fd);
 
−
                        }
 
−
                }
 
−
        }
 
−
 
 
−
 
 
−
dovrebbe stampare anche il nome del segnale prima di stampare il tempo ma per il resto va bene
 
−
 
 
−
</source>
 
−
<br>
 
−
 
 
−
=== Esercizio 3 ===
 
−
<source lang="python">
 
−
#!/usr/bin/env python
 
−
import sys
 
−
import os
 
−
import re
 
−
dict = {}
 
−
 
 
−
def func(a):
 
−
    os.chdir(a)
 
−
    for root, dirs, files in os.walk("."):
 
−
      for filename in files:
 
−
        try:
 
−
          fl =file(filename)
 
−
          firstline = fl.readline()
 
−
          fl.close()
 
−
        except IOError: # caso di file che non riesce ad aprire
 
−
          #print("could not read", file)
 
−
          pass
 
−
        if (re.match('^#!', firstline)):
 
−
          dict.setdefault(firstline, []) #firstline include anche il carattere \n, quindi quando si stampa va anche a capo
 
−
          dict[firstline].append(filename)
 
−
    for k in dict.keys():
 
−
      print k
 
−
      for v in dict[k]:
 
−
        print v
 
−
      #print(" ")
 
−
 
 
−
if __name__ == '__main__':
 
−
  if (len(sys.argv)==1):
 
−
    dir = "."
 
−
  else:
 
−
    dir = sys.argv[1]
 
−
  func(dir)
 
−
 
 
−
 
 
−
 
 
−
</source>
 
−
 
 
−
== Esame Pratico 22/01/2016 ==
 
−
http://www.cs.unibo.it/~renzo/so/pratiche/2016.01.22.pdf
 
−
=== Esercizio 1 ===
 
−
<source lang="c">
 
−
#include <stdlib.h>
 
−
#include <stdio.h>
 
−
#include <dirent.h>
 
−
#include <sys/types.h>
 
−
#include <string.h>
 
−
#include <unistd.h>
 
−
 
 
−
typedef struct nameNumber {
 
−
        char *name;
 
−
        int value;
 
−
    } nameNumber;
 
−
 
 
−
 
 
−
int prefixToInt (char *string) {
 
−
 
 
−
    int i = 0;
 
−
    int num = 0;
 
−
    while (string[i] >= '0' && string[i] < '9' && i < strlen(string)) {
 
−
        num = (num*10) + (string[i]-'0');
 
−
        i++;
 
−
    }
 
−
    return num;
 
−
 
 
−
}
 
−
 
 
−
void fileSort(struct nameNumber **files) {
 
−
 
 
−
}
 
−
 
 
−
int comp (const void * el1, const void * el2) {
 
−
    struct nameNumber *f = *((nameNumber**)el1);
 
−
    struct nameNumber *s = *((nameNumber**)el2);
 
−
    if (f->value > s->value) return 1;
 
−
    if (f->value < s->value) return -1;
 
−
    return 0;
 
−
}
 
−
 
 
−
int main(int arg, char* argv[]) {
 
−
 
 
−
 
 
−
    struct nameNumber **files;
 
−
 
 
−
    DIR *dir;
 
−
    struct dirent *ent;
 
−
 
 
−
    int count = 0;
 
−
 
 
−
    if((dir = opendir(argv[1])) != NULL)
 
−
    {
 
−
        while( (ent = readdir(dir)) != NULL )
 
−
        { 
 
−
            if (ent->d_name[0] < '9' && ent->d_name[0] >= '0')
 
−
            {
 
−
                files = (struct nameNumber**)realloc(files , (count+1) * sizeof(struct nameNumber*));
 
−
                files[count] = (struct nameNumber*)malloc(sizeof(struct nameNumber));
 
−
                files[count]->name = (char*)malloc(sizeof(char)*strlen(ent->d_name) + 1);
 
−
                strcpy(files[count]->name, ent->d_name);
 
−
                files[count]->value = prefixToInt(files[count]->name);
 
−
                printf("name : %s  ,  value : %d\n", files[count]->name , files[count]->value);
 
−
                count++;
 
−
            }
 
−
        }
 
−
    }
 
−
   
 
−
   
 
−
    qsort(files, count, sizeof(nameNumber*), comp);
 
−
 
 
−
    int i;
 
−
    for (i=0; i < count; i++) {
 
−
        printf("%s\n",files[i]->name);
 
−
    }
 
−
   
 
−
 
 
−
}
 
−
 
 
−
</source>
 
−
 
 
−
== Esame di Concorrenza del 13/01/2005 ==
 
−
Il testo degli esercizi è disponibile alla pagina http://www.cs.unibo.it/~renzo/so/compiti/2005-01-13.con.pdf.
 
−
 
 
−
=== Esercizio 1 ===
 
−
Il codice di questo esercizio può essere eseguito scaricando il sorgente Python e l'archivio relativo agli [[Tool_per_semafori_e_monitor|strumenti di concorrenza per il linguaggio Python]].
 
−
 
 
−
 
 
−
<source lang="python">
 
−
#!/usr/bin/env python3
 
−
import threading
 
−
import random
 
−
import time
 
−
from pysm.semaphore import semaphore
 
−
 
 
−
 
 
−
class mod_counter:
 
−
    def __init__(self, mod, start=0):
 
−
        self._mod = mod
 
−
        self._val = start
 
−
 
 
−
    def inc(self):
 
−
        self._val = (self._val + 1) % self._mod
 
−
 
 
−
    def get(self):
 
−
        return self._val
 
−
 
 
−
 
 
−
class process(threading.Thread):
 
−
    def __init__(self, to_print, c: mod_counter, a, t, r):
 
−
        threading.Thread.__init__(self, name="proc" + to_print)
 
−
 
 
−
        if to_print not in "tar":
 
−
            raise ValueError("Unexpected printable character:", to_print)
 
−
 
 
−
        self._counter = c
 
−
        self._x = to_print
 
−
        self._semaphores = {'t': t, 'a': a, 'r': r}
 
−
        self._enter = True
 
−
 
 
−
        if self._x == 't':
 
−
            self._semaphores[self._x].V()
 
−
 
 
−
    def run(self):
 
−
        while True:
 
−
            self.sync()
 
−
            print("[%s] %c" % (self.name, self._x))
 
−
 
 
−
            # Print a trailing newline
 
−
            if (self._counter.get() == 7):
 
−
                print()
 
−
 
 
−
            time.sleep(random.random() * 0.5)
 
−
 
 
−
    def sync(self):
 
−
        if (self._enter):
 
−
            self._semaphores[self._x].P()
 
−
            self._enter = False
 
−
        else:
 
−
            self._counter.inc()
 
−
            curr = "taratata"[self._counter.get()]
 
−
 
 
−
            self._semaphores[curr].V()
 
−
 
 
−
            self._enter = True
 
−
            self.sync()
 
−
 
 
−
 
 
−
def main():
 
−
    counter = mod_counter(8)
 
−
    semaphores = (semaphore(0), semaphore(0), semaphore(0))
 
−
    procs = [process(c, counter, *semaphores) for c in "tar"]
 
−
 
 
−
    for p in procs:
 
−
        p.daemon = True
 
−
        p.start()
 
−
 
 
−
    for p in procs:
 
−
        p.join()
 
−
 
 
−
    return 0
 
−
 
 
−
 
 
−
if __name__ == "__main__":
 
−
    exit(main())
 
−
</source>
 
−
<br>
 

Revision as of 09:17, 30 August 2020

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, 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.

Prove scritte

Prove pratiche

Retrieved from "https://so.v2.cs.unibo.it/wiki/index.php?title=Prove_svolte_e_soluzioni_proposte&oldid=2583"