Prove scritte 2019

From Sistemi Operativi
Jump to navigation Jump to search

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

    • non è l'esercizio corretto**
/* 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. Ritenuta corretta Flecart (talk) 15:30, 17 January 2023 (CET)

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;

Esercizio c.2 (da controllare)

Viene ritornata x stessa, in un numero di iterazioni pari a length(x). Il calcolo viene svolto tramite message passing tra processi client e processo server; quest'ultimo opera una sorta di iterazione inoltrando a se stesso il messaggio spedito da un client finché x != "".

Se più processi chiamano la funzione dilemma() allo stesso tempo, ciò non causa disagi nel calcolo del risultato finale. Infatti l'identificatore del processo cliente destinatario è memorizzato in pid, e protratto fino alla chiamata in cui x == "". Inoltre la presenza di molteplici richieste non causa sovrapposizione, posto che asend() memorizzi il contenuto di messaggi in sospeso in una coda FIFO.

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

Esercizio g.1 (da controllare)

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

Date le variabili del problema x, y ed m, bisogna avere x < m, x < y e che il tempo di arrivo dei processi P1, P2 e P3 durante lo scheduling RR sia P1, P2 e P3. Per ulteriori informazioni vedere lo svolgimento in figura. (Nota: non è specificata la relazione tra y ed m né sono considerati i casi x = m e x = y.)

2019-09-13-g1.jpg

Esercizio g.2 (da controllare)

  1. Le opzioni per comunicare con le periferiche di IO sono solitamente due: polling (sondaggio) e interrupt. Mediante il polling il sistema verifica costantemente lo stato dei dispositivi di IO prendendo azione quando esso cambia, con gli interrupt sono i dispositivi stessi a notificare il cambiamento del loro stato. Poiché fare polling significa eseguire ciclicamente delle istruzioni che svolgano il controllo, ricevere degli interrupt è più efficiente perché nello stesso tempo è possibile svolgere altro lavoro utile.
  2. Da svolgere.
  3. Quando bisogna svolgere un'operazione di swap-in (caricamento di una pagina dalla memoria secondaria a quella primaria) e di swap-out (inversa alla precedente). L'algoritmo di rimpiazzamento è invocato durante un'operazione di swap-in che vede la memoria centrale completamente occupata: in tal caso sarà necessario individuare una pagina da spostare in memoria secondaria.
  4. Vantaggi: dimensioni del file eseguibile finale ridotte, in quanto non è richiesto mantenere all'interno dello stesso una copia delle procedure di cui ci si serve; risparmio in memoria centrale: per un dato simbolo appartenente ad una data libreria, è possibile riservare un solo spazio in memoria condiviso da più processi che ne hanno bisogno. Svantaggi: versionamento, ovvero l'installazione di versioni più aggiornate della stessa libreria in conflitto con quelle meno recenti: tale problema è risolto mediante la definizione precisa di numeri di versione delle librerie e la specificazione delle dipendenze (rispetto ad un dato numero di versione).


Esame 2019/01/15

Esercizio c1

Soluzione proposta 1

monitor wsem {
		
	condition cond;
	queue<int> waiting;
	
	wsem(value) {
		this->value = value;
	}

	P(int w) {
		if (w > value || waiting.size() > 0) {
			waiting.enqueue(w);
			cond.wait();
		}

		value -= w;
	}

	V(int w) {
		value += w;

		while (waiting.size() > 0 && waiting.front() <= value) {
			waiting.dequeue();
			cond.signal();
		}
	}

}

Esercizio c2

  • Soluzione proposta Flecart (talk) 14:38, 17 January 2023 (CET)
ms_send(pid dest, msg_t msg) {
	asend(dest, <msg, getpid()>);
	ack = arecv(dest);
}


ms_recv(int n, pid *senders, msg_t *msgs) {
	pid_t sender_pid[n];
	for (int i = 0; i < n; i++) {
		msgs[i], sender_pid[i] = arecv(senders[i]);
	}

	for (int i = 0; i < n; i++) {
		asend(senders_pid[i], ACK);
	}
}

Esempi di deadlock:

  • Due processi A, B si aspettano messaggi l'un l'altro. (entrambi chiamano recv sull'altro), questo è un deadlock comune anche al message passing sincrono.
  • L'esempio di sopra si può estendere in un caso più generale quando sia A un ms_recv ed esiste un processo all'interno di senders che stia aspettando un messaggio da A.
  • Altro deadlock che può capitare è quando uno stesso processo è presente più volte all'interno di senders, in questo caso ricevo solo una volta, è impossibile che riesca a ricevere una altra volta.
  • Per esempio basterebbe avere come input un (ANY, 1), e ricevere il primo messaggio da 1, e, nonostante soddisfi le specifiche, si avrebbe un deadlock.
Retrieved from "https://so.v2.cs.unibo.it/wiki/index.php?title=Prove_scritte_2019&oldid=2921"