Difference between revisions of "Prove scritte 2019"

From Sistemi Operativi
Jump to navigation Jump to search
(Svolto es c.2 dell'esame 13/09/2019)
m (Verificato es c.1 esame 14/02/2019)
Line 326: Line 326:
  
 
== Esame 14/02/2019 ==
 
== Esame 14/02/2019 ==
−
[https://www.cs.unibo.it/~renzo/so/compiti/2019.02.14.tot.pdf testo esame]
+
[https://www.cs.unibo.it/~renzo/so/compiti/2019.02.14.tot.pdf Testo d'esame].
 +
 
 
=== Esercizio c.1 (da controllare) ===
 
=== Esercizio c.1 (da controllare) ===
 +
 +
* Controllato dall'utente [[User:Acsor|Acsor]] ([[User talk:Acsor|talk]]) in data 16:03, 2 September 2020 (CEST). Ritengo sia: corretto
 +
* Controllato dall'utente ? in data ?
 +
 
<source lang="python">
 
<source lang="python">
−
# Original authors: Mattia Guazzaloca & Paolo Marzolo
+
# Original authors: Mattia Guazzaloca, Paolo Marzolo
−
#
 
−
# Contributors:
 
 
#
 
#
 +
# Contributors: utente Acsor
  
 
class monobinarysem(monitor):
 
class monobinarysem(monitor):
 
     def __init__(self, val):
 
     def __init__(self, val):
 +
        monitor.__init__(self)
 
         self.iszero = condition(self)
 
         self.iszero = condition(self)
 
         self.val = val
 
         self.val = val
Line 352: Line 357:
 
             self.iszero.signal()
 
             self.iszero.signal()
 
</source>
 
</source>
 +
 
=== Esercizio c.2 (controllato) ===
 
=== Esercizio c.2 (controllato) ===
 +
 
<source lang="python">
 
<source lang="python">
 
# Original author: Renzo Davoli (durante la lezione)
 
# Original author: Renzo Davoli (durante la lezione)

Revision as of 15:03, 2 September 2020

Esame 18/06/2019

2019.06.18.tot.pdf

Esercizio c.1 (da controllare)

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

}


Esercizio c.1 (da controllare)

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


Esercizio c.2

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


Soluzione: 

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


Esercizio g.1 (sbagliato)

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|


Esercizio g.1

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



Esercizio g.2 (da controllare)

  1. 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.
  2. 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.
  3. 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.
  4. 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

2019.05.18.tot.pdf

Esercizio c.1 (da controllare)

  • Controllato dall'utente ? in data ?
  • ...

Il sorgente seguente può essere eseguito scaricando in una stessa directory il package pysm del prof. Davoli. 

#!/usr/bin/env python3

import threading

from array import array
from pysm.monitor import condition, entry, monitor


class storage(monitor):
    ELEMS = 16

    def __init__(self):
        """
        Implementazione che permette l'avanzamento degli operai in presenza di
        altri operai in attesa.
        """
        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())

Esercizio c.2 (da controllare)

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

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.

Epson 25082020151034.jpg

Esercizio g.2 (da controllare)

  1. 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.
  2. 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.
  3. 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.
  4. 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

Testo d'esame.

Esercizio c.1 (da controllare)

  • Controllato dall'utente Acsor (talk) in data 16:03, 2 September 2020 (CEST). Ritengo sia: corretto
  • Controllato dall'utente ? in data ?
# Original authors: Mattia Guazzaloca, Paolo Marzolo
#
# Contributors: utente Acsor

class monobinarysem(monitor):
    def __init__(self, val):
        monitor.__init__(self)
        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()

Esercizio c.2 (controllato)

# 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

Esame 28/05/2019

2019.05.18.tot.pdf

Esercizio c.1 (da controllare)

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


Esercizio c.1 (da controllare)

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

		}
	}

Esame 15/07/2019

2019.07.15.tot.pdf

Esercizio c.1

  1. Verifica del 18/05/2020 dell'utente Acsor. Ritengo sia: corretto
  2. Verifica del ... dell'utente ... . Ritengo sia: ...
  3. ...

Una semplice realizzazione in Python dello pseudocodice seguente è disponibile qui. 

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

Esame 13/09/2019

Testo: 2019.09.13.tot.pdf.

Esercizio c.1 (controllato)

  • Controllato dal professor Davoli durante la lezione del 19/05/2020.
  • Controllato dall'utente Acsor (talk) in data 19:13, 1 September 2020 (CEST).
# Original author: Andrea R.

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

Esercizio c.2 (da controllare)

  • Controllato dall'utente ? in data ?
  • ...

Il programma è composto da due processi, ognuno dei quali stampa all'infinito il proprio identificatore. Perché sia possibile stampare è però necessario attendere il proprio turno, condizione gestita dal monitor bohm: esso possiede due stati (0 o 1) ed è possibile entrarvi quando l'id del processo invocante e il valore dello stato corrispondono; la procedura post() di bohm setta lo stato al valore complementare e sveglia il processo in attesa sulla coda di condizione corrispondente (al nuovo stato).

È possibile implementare il meccanismo di sincronizzazione con semafori tramite il codice seguente 

binary_sempahore[2] sem = {new binary_semaphore(1), new binary_semaphore(0)};

void pre (int n) {
    sem[n].P();
}

void post (int n) {
    sem[1 - n].V();
}
Retrieved from "https://so.v2.cs.unibo.it/wiki/index.php?title=Prove_scritte_2019&oldid=2591"