EserciziEsame20172018 < SO/SO1213AL

Tags: view all tags
<!-- semafori -->
I seguenti tre processi concorrenti condividono due semafori<!-- forti, no non importa -->:
<br />
<textarea cols="100" rows="10" readonly="readonly">
semaphore U = 3;
semaphore V = 0;

[Process 1]         [Process 2]         [Process 3]

while(1) {          while(1) {          while(1) {
   semWait(U);        semWait(V);          semWait(V);
   print("A");        print("B");          print("C");
   semSignal(V);      semSignal(V);     }
}                   }
</textarea>
<br />
Tenendo presente che l'unica assunzione possibile sul dispatcher è che, prima o poi, dia l'opportunità di andare in esecuzione a tutti i processi, e che nessun altro processo manipola i semafori U e V, qual è il __massimo__ numero di caratteri "B" che potrebbero venir stampati durante l'esecuzione dei tre processi?

| 0 |
| 3 |
| Infinito |
| Nessuna delle altre opzioni è corretta |
<br /><br /><br /><br />

I seguenti due processi concorrenti condividono una variabile:
<br />
<textarea cols="100" rows="10" readonly="readonly">
sempahore S = 1;
int X = N;

[Process 1]             [Process 2]
    int Y;                   int Z;
    semWait(S);              
    Y = X*2;                 Z = X+1;
    X = Y;                   X = Z;
    semSignal(S);            
</textarea>
<br />
Tenendo presente che l'unica assunzione possibile sul dispatcher è che, prima o poi, dia l'opportunità di andare in esecuzione a tutti i processi, e che nessun altro processo manipola né S né X, quali sono i possibili valori di X dopo che entrambi i processi terminano l'esecuzione?

| _N_*2 + 1, 2*(_N_ + 1) |
| _N_*2 + 1, 2*(_N_ + 1), _N_ + 1 |
| _N_*2 + 1, 2*(_N_ + 1), _N_*2 |
| _N_*2 + 1, 2*(_N_ + 1), _N_ + 1, _N_*2 |
<br /><br /><br /><br />

Un sistema con gestione paginata semplice della memoria ha indirizzi di _B_ bit e pagine di dimensione _P_ KB. Se tutta la memoria è paginabile, qual è il numero massimo di elementi contenuti nella Tabella delle Pagine di un processo?

| 2<sup><em>B</em></sup>/(_P_*1024) |
| _P_*1024/2<sup><em>B</em></sup> |
| <em>P</em>/<em>B</em> |
| <em>B</em>/<em>P</em> |
<br /><br /><br /><br />

Si consideri una unità disco con una velocità di rotazione di _R_ rivoluzioni al minuto (rpm). La testina, per spostarsi da una traccia alla successiva, impiega un tempo trascurabile. Ogni traccia del disco contiene _T_ KB. Si assuma che una porzione di dimensione _P_ KB di un file sia memorizzata sul disco in settori contigui. Stimare il tempo totale, in secondi, necessario per il trasferimento di questi _P_ <span> KB di dati dal disco in memoria principale, nel caso in cui la testina sia già posizionata sul settore di partenza. </span>

| <em>T</em>/(_P_*<em>R</em>/60) |
| _P_*<em>R</em>/60 |
| <em>P</em>/(_T_*<em>R</em>/60) |
| _T_*(<em>R</em>/60)/<em>P</em> |
<br /><br /><br /><br />

Un calcolatore multiprogrammato esegue _N_ processi concorrenti. Ciascun processo ha le medesime caratteristiche ed è strutturato in fasi di attività di lunghezza di _M_ millisecondi. Solo una frazione _0 &lt; C &le; 0.5_ di questi _M_ millisecondi è passata in attività di I/O, e tale attività è concentrata o tutta all'inizio o tutta alla fine di ciascuna fase. Il resto di ogni fase è quindi speso in attività di elaborazione sul processore. Ciascun processo viene eseguito per un totale complessivo di _F_ fasi di attività usando un semplice scheduler round-robin, con quanto di tempo maggiore di _M_ millisecondi. Ciascun processore agisce su un dispositivo di I/O indipendente da quello su cui operano gli altri processi. Si calcoli l'utilizzazione media del processore, definita come il rapporto tra il tempo in cui il processore non è in attesa rispetto al tempo totale per eseguire gli _N_ processi. Assumere trascurabile il tempo di switch tra processi.

| _C_* _F_*N/(_C_* _F_* _N_ + 1 - _C_) |
| (1 - _C_)* _F_*N/((1 - _C_)* _F_* _N_ + _C_) |
| _C_* _F_*M/(_C_* _F_* _M_ + 1 - _C_) |
| (1 - _C_)*<em>N</em>/((1 - _C_)* _N_ + _C_) |
<br /><br /><br /><br />

Un calcolatore multiprogrammato esegue _N_ processi concorrenti. Ciascun processo ha le medesime caratteristiche ed è strutturato in fasi di attività di lunghezza di _M_ millisecondi. Solo una frazione _0 &lt; C &le; 0.5_ di questi _M_ millisecondi è passata in attività di I/O, e tale attività è concentrata o tutta all'inizio o tutta alla fine di ciascuna fase. Il resto di ogni fase è quindi speso in attività di elaborazione sul processore. Ciascun processo viene eseguito per un totale complessivo di _F_ fasi di attività usando un semplice scheduler round-robin. Ciascun processore agisce su un dispositivo di I/O indipendente da quello su cui operano gli altri processi. Si calcoli l'utilizzazione media del processore, definita come il rapporto tra il tempo in cui il processore non è in attesa rispetto al tempo totale per eseguire gli _N_ processi. Considerare, come durata del quanto di round-robin, quella che rende l'utilizzazione media del processore più alta (caso pessimo). Assumere trascurabile il tempo di switch tra processi.

| (1 - _C_)* _F_*N/((1 - _C_)* _F_* _N_ + _C_) |
| (1 - _C_)*<em>F</em>/((1 - _C_)* _F_ + _C_) |
| (1 - _C_)*<em>N</em>/((1 - _C_)* _N_ + _C_) |
| _C_* _F_*N/(_C_* _F_* _N_ + 1 - _C_) |
<br /><br /><br /><br />

Un produttore P produce dati che mette in due code FIFO, q0 e q1, alternando fra le due. Due consumatori C0 e C1, prelevano un dato per volta, rispettivamente dalle code q0 e q1, e li elaborano. I tempi di ogni singola produzione ed elaborazione sono molto irregolari, al punto che un consumatore può trovare la propria coda vuota. In tal caso, dovrà provare a prelevare un dato dall'altra coda.<br />
Si consideri la seguente implementazione per tali processi:<br />
<textarea cols="100" rows="35" readonly="readonly">
semaphore
  s[2] = {1, 1},
  n[2] = {0, 0},
  e[2] = {length(Q0), length(Q1)};

void P() {
  int i = 0;
  while (1) {
    produce();
    semWait(e[i]);
    semWait(s[i]);
    append(i);
    semSignal(s[i]);
    semSignal(n[i]);
    i = (i + 1)%2;
} }

void C(int i) {
  int queue;
  while (1) {
    queue = i;
    semWait(s[queue]);
    if (is_empty(i))
      queue = (i + 1)%2;
    semSignal(s[queue]);
    semWait(n[queue]);
    semWait(s[queue]);
    take(queue);
    semSignal(s[queue]);
    semSignal(e[queue]);
    consume();
} }

parbegin(P, C(0), C(1));
</textarea>
<br />
Quale delle seguenti affermazioni è vera?

| La soluzione data non è corretta, in quanto è possibile il deadlock |
| Viene fatto uso del _busy waiting_ |
| La soluzione data non è corretta, in quanto permette al consumatore di prendere un dato da una coda vuota |
| La soluzione data è corretta |
<br /><br /><br /><br />

Considerare un insieme di cinque processi P1, P2, P3, P4, P5 con i seguenti tempi di arrivo e tempi di esecuzione in millisecondi:

&lt;!--ancora dentro--&gt;      
| *Processo* | *Tempo di Arrivo* | *Tempo di esecuzione* |
| P1 | 0 | 14 |
| P2 | 8 | 16 |
| P3 | 5 | 3 |
| P4 | 11 | 7 |
| P5 | 17 | 9 |
Quale delle seguenti affermazioni è falsa?

| Non ci sono sufficienti informazioni per determinare come si comporterebbe l'algoritmo di _scheduling SRT_ |
| Non ci sono sufficienti informazioni per determinare come si comporterebbe l'algoritmo di _scheduling_ a feedback classico di Unix |
| Non ci sono sufficienti informazioni per determinare come si comporterebbe l'algoritmo di _scheduling Round-Robin_ |
| Non ci sono sufficienti informazioni per determinare come si comporterebbe l'algoritmo di _scheduling Virtual Round-Robin_ |
<br /><br /><br /><br />

Considerare un insieme di cinque processi P1, P2, P3, P4, P5 con i seguenti tempi di arrivo e tempi di esecuzione in millisecondi:

&lt;!--ancora dentro--&gt;      
| *Processo* | *Tempo di Arrivo* | *Tempo di esecuzione* |
| P1 | 0 | 14 |
| P2 | 8 | 16 |
| P3 | 5 | 3 |
| P4 | 11 | 7 |
| P5 | 17 | 9 |
Assegnare questo insieme di processi ad un processore usando l'algoritmo di _scheduling SRT_, fino a quando non terminano tutti. Quale delle seguenti affermazioni è falsa?

| Gli unici 2 processi che non sono serviti subito (ovvero, appena arrivati) sono P3 e P5 |
| Il tempo medio di attesa è tra 10 ed 11 ms |
| Il processo con il più lungo tempo di attesa è P1 |
| Il tempo medio di turnaround è tra 2 ed 3 ms |
<br /><br /><br /><br />

Considerare un sistema con memoria virtuale a paginazione semplice nel quale sono presenti 4 pagine fisiche dedicate ad uno specifico processo utente. Tale processo effettua i seguenti riferimenti alla memoria virtuale: 8, 0, 9, 3, 1, 2, 9, 0, 8. Considerare le seguenti evoluzioni della memoria principale (inizialmente vuota), a seconda del diverso algoritmo di rimpiazzamento usato, dove, per l'algoritmo di clock, vengono anche mostrati il puntatore (lancetta) e il bit di uso _dopo_ ogni gestione di una richiesta: il carattere &gt; indica l'attuale lancetta dell'orologio, mentre la presenza di un apice indica se una pagina ha il bit ad 1. <br />
<img alt="" src="clock_lru1.png" />
<br />
Quale delle seguenti affermazioni è vera?

| Le evoluzioni proposte sono corrette, e ci sono più page fault con l'algoritmo di clock che con l'algoritmo LRU |
| Le evoluzioni proposte per l'algoritmo di clock non sono corrette: dopo la gestione della prima richiesta (pagina 8) il puntatore dell'orologio sarebbe dovuto essere sulla prima pagina fisica, e non sulla seconda |
| Le evoluzioni proposte per l'algoritmo di LRU non sono corrette, in quanto manca, in input, l'informazione su _quando_ le richieste alla memoria vengono effettuate |
| Nessuna delle altre opzioni è vera |
<br /><br /><br /><br />

Si supponga di avere a disposizione, come metodo di sincronizzazione, solamente le primitive =lock/unlock=. Entrambe prendono in input una etichetta e funzionano in modo simile alle =semWaitB/semSignalB= di un semaforo binario, con la limitazione che una chiamata ad =unlock= non ha nessun effetto se prima non era stata chiamata la =lock=. Quale delle seguenti soluzioni al problema del produttore/consumatore (un produttore ed un consumatore), con buffer circolare in grado di mantenere al più =N= elementi, è corretta?

| <textarea cols="100" rows="24" readonly="readonly">
int n = 0;

void produttore() {
  while (1) {
    while (n == N) ; //do-nothing
    produce();
    lock(buffer);
    append();
    n++;
    unlock(buffer);
  }
}=

=void consumatore() {
  while (1) {
    while (n == 0) ; //do-nothing
    lock(buffer);
    take();
    n--;
    unlock(buffer);
    consume(p);
  }
}
</textarea> |
| <textarea cols="100" rows="27" readonly="readonly">
int n = 0;

void produttore() {
  while (1) {
    produce();
    lock(buffer);
    append();
    n++;
    if (n == 1)
      unlock(delay);
    unlock(buffer);
  }
}=

=void consumatore() {
int m;
  lock(delay);
  while (1) {
    lock(buffer);
    take();
    n--;
    m = n;
    unlock(buffer);
    consume(p);
    if (m == 0)
      lock(delay);
  }
}
</textarea> |
| <textarea cols="100" rows="24" readonly="readonly">
int n = 0;

void produttore() {
  while (1) {
    while (n == 0) ; //do-nothing
    produce();
    lock(buffer);
    append();
    n++;
    unlock(buffer);
  }
}=

=void consumatore() {
  while (1) {
    while (n == N) ; //do-nothing
    lock(buffer);
    take();
    n--;
    unlock(buffer);
    consume(p);
  }
}
</textarea> |
| Nessuna delle soluzioni proposte è corretta |
<br /><br /><br /><br />

Si consideri una memoria di _B_ byte suddivisa in _P_ pagine, dove _P_ divide _B_, ovvero _B = b*P_ con _b_ intero. Quindi, le pagine sono da _b = B/P_ byte ciascuna. La page table di un processo in esecuzione è data dalla funzione _p : {1, ..., P} &rarr; {1, ..., P}_. Nel seguito, si indica con _y div z_ il quoziente intero tra y e z, con _y mod z_ il resto della divisione intera tra y e z, con _y &lt;&lt; z_ lo shift a sinistra di y per z bit e con _y &gt;&gt; z_ lo shift a destra di y per z bit. Qual è la traduzione di un generico indirizzo logico _x_?

| _b*p(x mod b) + x div b_ |
| _b*p(x div b) + x mod b_ |
| _(p(x &gt;&gt; b) &lt;&lt; b) + x mod b_ |
| Nessuna delle altre opzioni è corretta |
<br /><br /><br /><br />

Talvolta le applicazioni concorrenti sono divise in fasi con la regola che nessun processo può proseguire se prima tutti i suoi simili non sono pronti a farlo. Le barriere implementano questo concetto: un processo che ha terminato la sua fase chiama una primitiva =barrier= e si blocca. Quando tutti i processi coinvolti hanno terminato il loro stadio di esecuzione invocando anch'essi la primitiva =barrier=, il sistema li sblocca tutti permettendo di passare ad uno stadio successivo. Un'applicazione concorrente composta da _N_ processi utilizza più volte durante la sua esecuzione il meccanismo della =barrier=. Dovendo migrare l'applicazione in questione ad un sistema operativo che non fornisce tale meccanismo, ma che fornisce condivisione di memoria e semafori, si richiede di scrivere la primitiva =barrier= in termini dei meccanismi disponibili. A tal proposito, si consideri la seguente soluzione: <br />
<textarea cols="100" rows="18" readonly="readonly">
semaphore mutex = 1;
semaphore barrier_sem = 0;
int n_barrier = 0;

barrier() {
  wait(mutex);
  n_barrier++;
  if (n_barrier &lt; N) {
    signal(mutex);
    wait(barrier_sem);
  }
  else {
    n_barrier = 0;
    signal(mutex);
    for (i = 1; i &lt; N; i++)
      signal(barrier_sem);
  }
}
</textarea>
<br />
Quale delle seguenti affermazioni è vera?

| La soluzione è corretta anche se i semafori impiegati sono _weak_ |
| Sono possibili deadlock |
| La soluzione è corretta solo se i semafori impiegati sono _strong_ |
| La soluzione riportata non è corretta, ma per correggerla è sufficiente spostare l'ultimo =signal(mutex)= a subito dopo il =for= |