DomandeOrali < SO/SO1213AL

Tags: view all tags
---+ Tutti gli esercizi per l'orale

[[#esercizi_4][Esercizi da 4 punti]]<br />
[[#esercizi_8][Esercizi da 8 punti]]<br />
[[#esercizi_12][Esercizi da 12 punti]]

<a name="esercizi_4"/>
---++ Esercizi da 4 punti

Per rispondere, __non__ è concesso consultare libro e dispense

<br /><br /><br /><br />

<!-- semafori -->
I seguenti tre processi concorrenti condividono due semafori<!--forti no, non importa-->:
<br />
<textarea cols="100" rows="11" 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, stabilire se sia possibile che il numero di caratteri "B" stampati durante l'esecuzione dei tre processi sia 10, e che il numero di caratteri "C" sia 0.
<br /><br /><br /><br />

<!-- semafori -->
I seguenti due processi concorrenti condividono una variabile ed un semaforo:
<br />
<textarea cols="100" rows="10" readonly="readonly">
semaphore S = 1;
int X = 4;

[Process 1]             [Process 2]
    int Y;                   int Z;
    semWait(S);              semWait(S);
    Y = X*2;                 Z = X+1;
    X = Y;                   X = Z;
    semSignal(S);            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, stabilire se è possibile che X contenga uno dei seguenti valori al termine dell'esecuzione: 8, 9, 10. Stabilire anche se sia possibile che X abbia uno di quei valori in un qualsiasi momento dell'esecuzione combinata dei 2 processi. Cosa cambia se si elimina una delle chiamate a =semSignal=? e se si elimina una delle chiamate a =semWait=?
<br /><br /><br /><br />

<!-- paginazione -->
Un sistema con gestione paginata semplice della memoria ha indirizzi di 40 bit e pagine di dimensione 16 KiB. Se la memoria è paginabile a partire dall'indirizzo =0x000000a000=, qual è il numero massimo di elementi contenuti nella tabella delle pagine di un processo? Si supponga inoltre che tale tabella sia organizzata in 2 livelli, in modo tale che la _page directory_ (primo livello) sia indirizzata da 10 bit. Quanti bit saranno usati per indirizzare il secondo livello? Quante entry ci saranno, al massimo, tra tutte le tabelle delle pagine (primo e secondo livello) di un processo?
<br /><br /><br /><br />

<!-- tempo_di_accesso -->
Si consideri una unità disco con una velocità di rotazione di 1000 rivoluzioni al minuto (rpm). La testina, per spostarsi da una traccia alla successiva, impiega 1 ms. Ogni traccia del disco contiene 32 KiB. Si assuma che una porzione di dimensione 2 MiB di un file sia memorizzata sul disco in settori contigui (si intendono contigui anche settori su diverse tracce, per i quali sia sufficiente il semplice spostamento della testina). Indicare qual è il tempo totale, in secondi, necessario per il trasferimento di questi 2 MiB di dati dal disco in memoria principale, nel caso in cui la testina sia posizionata sulla traccia giusta, ma a 5 settori di distanza (su 32 settori totali per traccia) dal settore giusto, che è il primo della traccia stessa. Quanti byte ci sono per ogni settore?
<br /><br /><br /><br />

<!-- io_versus_cpu -->
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 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 il tempo medio di risposta, in ms, nel caso migliore e nel caso peggiore, nel caso in cui i parametri dei processi siano i seguenti: _M_ =10 ms, _N_ =4, _C_ =0.2, _F_ =3. Assumere trascurabile il tempo di switch tra processi.
<br /><br /><br /><br />

<!-- io_versus_cpu -->
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 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 il throughput, in processi al ms, nel caso migliore e nel caso peggiore, nel caso in cui i parametri dei processi siano i seguenti: _M_ =12 ms, _N_ =3, _C_ =0.3, _F_ =4. Assumere trascurabile il tempo di switch tra processi.
<br /><br /><br /><br />

<!-- scheduling -->
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;  &lt;!--ancora dentro--&gt;&lt;!--ancora dentro--&gt;&lt;!--ancora dentro--&gt;&lt;!--ancora dentro--&gt;&lt;!--ancora dentro--&gt; &lt;!--ancora dentro--&gt;&lt;!--ancora dentro--&gt;&lt;!--ancora dentro--&gt;&lt;!--ancora dentro--&gt;&lt;!--ancora dentro--&gt; &lt;!--ancora dentro--&gt;&lt;!--ancora dentro--&gt;&lt;!--ancora dentro--&gt;&lt;!--ancora dentro--&gt;&lt;!--ancora dentro--&gt; &lt;!--ancora dentro--&gt;&lt;!--ancora dentro--&gt;&lt;!--ancora dentro--&gt;&lt;!--ancora dentro--&gt;&lt;!--ancora dentro--&gt; &lt;!--ancora dentro--&gt;&lt;!--ancora dentro--&gt;&lt;!--ancora dentro--&gt;&lt;!--ancora dentro--&gt;&lt;!--ancora dentro--&gt;
| *Processo* | *Tempo di Arrivo* | *Tempo di esecuzione* |
| P1 | 2 | 15 |
| P2 | 5 | 10 |
| P3 | 12 | 7 |
| P4 | 9 | 5 |
| P5 | 15 | 7 |
<!--ancora dentro-->

Assegnare questo insieme di processi ad un processore usando l'algoritmo di _scheduling SRT_, fino a quando non terminano tutti. Rispondere alle seguenti domande:

      * Qual è il tempo medio di turnaround?

      * Quali sono i processi che non sono serviti subito (ovvero, appena arrivati)?

      * Qual è il tempo medio di attesa?

<br /><br /><br /><br />

<!-- page_replace -->
Considerare un sistema con memoria virtuale a paginazione semplice nel quale sono presenti 5 pagine fisiche dedicate ad uno specifico processo utente. Tale processo effettua i seguenti riferimenti alla memoria virtuale: 8, 0, 1, 3, 1, 2, 4, 3, 12. Mostrare le evoluzioni della memoria principale (inizialmente vuota) a seconda del diverso algoritmo di rimpiazzamento usato: FIFO, LRU, clock.
<br /><br /><br /><br />

<!-- trad_ind_log -->
Si consideri una memoria di 32 byte suddivisa in 8 pagine da 4 byte ciascuna. La page table di un processo in esecuzione è la seguente:

&lt;!----&gt; &lt;!----&gt;&lt;!--ancora dentro--&gt;&lt;!--ancora dentro--&gt;&lt;!--ancora dentro--&gt;&lt;!--ancora dentro--&gt;&lt;!----&gt; &lt;!----&gt;&lt;!--ancora dentro--&gt;&lt;!--ancora dentro--&gt;&lt;!--ancora dentro--&gt;&lt;!--ancora dentro--&gt;&lt;!----&gt;
| Pagina logica | 0 | 1 | 2 | 3 |
| Frame | 5 | 7 | 1 | 2 |
<!---->

Quali sono le traduzioni dei seguenti indirizzi logici: 3, 4, 10, 32?
<br /><br /><br /><br />

<!-- concur_macchina -->
Si consideri la seguente soluzione al problema della mutua esclusione tra processi: <br />
<textarea cols="100" rows="10" readonly="readonly">
int bolt = 0;
void P(int i)
{
    while (bolt == 1) /* do nothing */;
    bolt = 1;
    /* critical section */;
    bolt = 0;
    /* remainder */;
}
</textarea>
<br />
Assegnare un valore di verità alle seguenti affermazioni, spiegandone il motivo.

      * Assumendo che il dispatcher, prima o poi, dia l'opportunità di andare in esecuzione a tutti i processi coinvolti, è comunque possibile la starvation (rispetto all'entrata nella sezione critica)

      * Supponendo che ci siano 2 processi, se lo scheduler permette a =P(0)= di arrivare fino ad assegnare 1 a =bolt= senza interromperlo, allora il requisito base della mutua esclusione (sul numero massimo di processi nella sezione critica) è rispettato

      * Sono possibili deadlock

<br /><br /><br /><br />

<!-- concur_semafori -->
Si consideri la seguente soluzione al problema della mutua esclusione tra processi: <br />
<textarea cols="100" rows="10" readonly="readonly">
semaphore s = 0;
void P(int i)
{
    semWait(s);
    /* critical section */;
    semSignal(s);
    /* remainder */;
}
</textarea>
<br />
Assegnare un valore di verità alle seguenti affermazioni, spiegandone il motivo.

      * Se si elimina la chiamata a =semWait=, il requisito base della mutua esclusione (sul numero massimo di processi nella sezione critica) è rispettato

      * È certo il deadlock

      * Il requisito base della mutua esclusione (sul numero massimo di processi nella sezione critica) è rispettato

      * Se si scambiano le chiamate =semWait= e =semSignal=, il requisito base della mutua esclusione (sul numero massimo di processi nella sezione critica) non è rispettato

<br /><br /><br /><br />

<!-- concur_messaggi -->
Si consideri la seguente soluzione al problema della mutua esclusione tra processi: <br />
<textarea cols="100" rows="17" readonly="readonly">
const message null = /* null message */;
mailbox box;
void P(int i) {
  message msg;
  while (true) {
    receive(box, msg);
    /* critical section */;
    send(box, msg);
    /* remainder */;
} }

void main() {
  box = create_mailbox();
  nbsend(box, null);
  parbegin (P(1), P(2), . . ., P(n));
}
</textarea>
<br />
Assegnare un valore di verità alle seguenti affermazioni, spiegandone il motivo.

      * Se _n = 1_, non c'è deadlock

      * Il requisito base della mutua esclusione (sul numero massimo di processi nella sezione critica) è rispettato

      * Almeno un requisito della mutua esclusione non è rispettato

      * Se _n &gt; 1_, non c'è deadlock

<br /><br /><br /><br />

<!-- lettori_scrittori_semafori -->
Si considerino le soluzioni al problema dei lettori/scrittori che usano i semafori viste a lezione, riportate qui di seguito:<br />
<img alt="" src="lezione24_slide71.png" /><br />
<img alt="" src="lezione24_slide72.png" /><br />
<img alt="" src="lezione24_slide73.png" /><br />
Assegnare un valore di verità alle seguenti affermazioni, spiegandone il motivo.

      * Nella soluzione che dà la precedenza agli scrittori, uno scrittore, in assenza di altri scrittori, nel momento in cui chiama =semWait(wsem)=, deve aspettare tutti e soli i lettori che attualmente hanno già eseguito =semWait(rsem)=

      * Usando la soluzione che dà la precedenza ai lettori, uno scrittore, in assenza di altri scrittori, nel momento in cui chiama =semWait(wsem)=, deve aspettare tutti e soli i lettori che attualmente stanno eseguendo =READUNIT=

      * Nella soluzione che dà la precedenza agli scrittori, uno scrittore, nel momento in cui chiama =semWait(wsem)=, deve aspettare tutti e soli i lettori che attualmente stanno eseguendo =READUNIT=

<br /><br /><br /><br />

<!-- lettori_scrittori_messaggi -->
Si consideri la soluzione tramite scambio messaggi al problema dei lettori/scrittori vista a lezione.<br />
<textarea cols="100" rows="48" readonly="readonly">
void reader(int i)
{
  while (true) {
    nbsend (readrequest, null);
    receive (controller_pid, null);
    READUNIT ();
    nbsend (finished, null);
} }

void writer(int j)
{
  while (true) {
    nbsend (writerequest, null);
    receive (controller_pid, null);
    WRITEUNIT ();
    nbsend (finished, null);
} }

void controller() {
  count = MAX_READERS;
  while (true) {
    if (count &gt; 0) {
      if (!empty (finished)) { /* da reader! */
        receive (finished, msg);
        count++;
      }
      else if (!empty (writerequest)) {
        receive (writerequest, msg);
        writer_id = msg.sender;
        count = count - MAX_READERS;
      }
      else if (!empty (readrequest)) {
        receive (readrequest, msg);
        count--;
        nbsend (msg.sender, "OK");
    }  }
    if (count == 0) {
      nbsend (writer_id, "OK");
      receive (finished, msg); /* da writer! */
      count = MAX_READERS;
    }
    while (count &lt; 0) {
      receive (finished, msg); /* da reader! */
      count++;
    } /* while (count &lt; 0) */
  } /* while (true) */
} /* controller */
</textarea>
<br />
Assegnare un valore di verità alle seguenti affermazioni, spiegandone il motivo.

      * Questa soluzione dà precedenza ai lettori

      * Se =count &gt; 0=, allora c'è un solo scrittore attivo (ovvero, che abbia completato l'esecuzione della =receive=)

      * Se =count &lt; 0=, allora c'è un solo lettore attivo (ovvero, che abbia completato l'esecuzione della =receive=)

      * Si può sostituire il messaggio ="OK"= col messaggio nullo

      * C'è una corsa critica nel controllore: tra il test =empty= e la ricezione del messaggio, lo scheduler potrebbe interrompere il controllore stesso. Tuttavia, la soluzione è corretta

<br /><br /><br /><br />

<!-- concur_messaggi -->
Si consideri la soluzione al problema del produttore/consumatore che usa lo scambio messaggi vista a lezione.
<br />
<textarea cols="100" rows="28" readonly="readonly">
const int capacity = /* buffering capacity */ ;
mailbox mayproduce, mayconsume;

void main()
{
  mayproduce = create_mailbox(),
  mayconsume = create_mailbox();
  for (int i = 1; i &lt;= capacity; i++)
    nbsend (mayproduce,null);
  parbegin (producer,consumer);
}

void producer() {
  message pmsg;
  while (true) {
    receive (mayproduce,pmsg);
    pmsg = produce(); /* fa anche append */
    nbsend (mayconsume,pmsg);
} }

void consumer() {
  message cmsg;
  while (true) {
    receive (mayconsume,cmsg);
    consume (cmsg); /* fa anche take */
    nbsend (mayproduce,null);
} }
</textarea>
<br />
Si supponga che venga usata così com'è per produttori e consumatori multipli. Assegnare un valore di verità alle seguenti affermazioni, spiegandone il motivo.

      * Assumendo che non ci siano errori in precedenza, è possibile che 2 produttori tentino di immettere contemporaneamente 2 diversi prodotti nello stesso slot del buffer

      * Assumendo che non ci siano errori in precedenza, è possibile che un consumatore tenti di prelevare un prodotto dal buffer quando quest'ultimo è vuoto

      * Assumendo che non ci siano errori in precedenza, è possibile che un produttore tenti di immettere un prodotto nel buffer quando quest'ultimo è pieno

<br /><br /><br /><br />

<!-- grafi_allocazione_risorse -->
Si supponga che la situazione ad un incrocio sia la seguente:<br />
<img alt="" src="deadlock.png" /><br />
Supponendo che la macchina 1 voglia girare a destra, mentre tutte le altre vogliano andare dritto, qual è il grafo delle allocazioni delle risorse corretto? E se tutte girano a destra?
<br /><br /><br /><br />

<!-- trastevere -->
Si consideri la soluzione al problema della strettoia di Trastevere vista a lezione.<br />
<textarea cols="100" rows="27" readonly="readonly">
semaphore z = 1;
semaphore strettoia = 4;
semaphore sx = 1;
semaphore dx = 1;
int nsx = 0;
int ndx = 0;

macchina_dal_lato_sinistro() {
  wait(z);
  wait(sx);
  ++nsx;
  if (nsx <span>= 1)
    wait(dx);
  signal(sx);
  signal(z);
  wait(strettoia);
  passa_strettoia();
  signal(strettoia);
  wait(sx);
  --nsx;
  if(nsx =</span> 0)
    signal(dx);
  signal(sx);
}
</textarea>
<br />
Si supponga che, ad un dato istante, ci siano 3 macchine da sinistra nella strettoia, 3 macchina da sinistra che stanno per eseguire =wait(strettoia)=, e 2 macchina da destra in attesa (su quali grafi?). Si supponga che ora arrivino altre 2 macchine da sinistra. Descrivere come evolverà la situazione, supponendo che non ci siano altri arrivi.
<br /><br /><br /><br />

<a name="esercizi_8"/>
---++ Esercizi da 8 punti

Per rispondere, __non__ è concesso consultare libro e dispense

<br /><br /><br /><br />

<!-- semafori -->
I seguenti tre processi concorrenti condividono due semafori<!--forti no, non importa-->:
<br />
<textarea cols="100" rows="11" 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 __minimo__ ed il __massimo__ numero di caratteri "A", "B" e "C" che potrebbero venir stampati durante l'esecuzione dei tre processi?
<br /><br /><br /><br />

<!-- semafori -->
I seguenti due processi concorrenti condividono una variabile ed un semaforo:
<br />
<textarea cols="100" rows="10" readonly="readonly">
semaphore S = 1;
int X = N;

[Process 1]             [Process 2]
    int Y;                   int Z;
    semWait(S);              semWait(S);
    Y = X*2;                 Z = X+1;
    X = Y;                   X = Z;
    semSignal(S);            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? Cosa cambia se si elimina una delle chiamate a =semSignal=? e se si elimina una delle chiamate a =semWait=?
<br /><br /><br /><br />

<!-- paginazione -->
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? E se invece _K_ kB sono riservati al kernel e non sono paginabili? Si supponga inoltre che la tabella delle pagine sia organizzata in 2 livelli, in modo tale che la _page directory_ (primo livello) sia indirizzata da _D_ bit. Quanti bit saranno usati per indirizzare il secondo livello? Quante entry ci saranno, al massimo, tra tutte le tabelle delle pagine (primo e secondo livello) di un processo?
<br /><br /><br /><br />

<!-- tempo_di_accesso -->
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 _t_ ms. Ogni traccia del disco contiene _T_ KiB. Si assuma che una porzione di dimensione _P_ kB di un file sia memorizzata sul disco in settori contigui (si intendono contigui anche settori su diverse tracce, per i quali sia sufficiente il semplice spostamento della testina). Indicare qual è il tempo totale, in secondi, necessario per il trasferimento di questi _P_ <span> KiB di dati dal disco in memoria principale, nel caso in cui la testina sia già posizionata sul settore di partenza, che è il primo della traccia di cui fa parte.
<br /><br /><br /><br /> </span>

<!-- io_versus_cpu -->
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 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 ricavi la formula per il tempo medio di risposta, in ms, nel caso migliore e nel caso peggiore. Assumere trascurabile il tempo di switch tra processi.
<br /><br /><br /><br />

<!-- io_versus_cpu -->
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 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 ricavi la formula per il throughput, in processi al ms, nel caso migliore e nel caso peggiore. Assumere trascurabile il tempo di switch tra processi.
<br /><br /><br /><br />

<!-- scheduling_formule -->
Considerare un insieme di _n_ processi <em>P<sub>1</sub>, ..., P<sub>n</sub></em>. Per ciascun processo, sono noti i tempi (_time-stamp_) di arrivo <em>A<sub>1</sub>, ..., A<sub>n</sub></em>, i tempi di servizio <em>S<sub>1</sub>, ..., S<sub>n</sub></em> ed i tempi (_time-stamp_) di terminazione <em>C<sub>1</sub>, ..., C<sub>n</sub></em>; questi ultimi vengono ottenuti tramite un qualche algoritmo di _scheduling_. Rispondere alle seguenti domande:

      * Come è definito il throughput?

      * Come è definito il valor medio del tempo di turnaround normalizzato?

      * Come è definito il tempo medio di turnaround?

      * Ci sono sufficienti informazioni per definire il tempo medio di attesa?

<br /><br /><br /><br />

<!-- trad_ind_log -->
Si consideri una memoria di _B_ byte suddivisa in _P_ pagine, dove _P_ divide _B_, ovvero _B = b*P_ con _b_ intero e potenza di 2 (<em>b = 2<sup>k</sup></em> per qualche _k_ 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 formula per tradurre un generico indirizzo logico _x_ in indirizzo fisico? Supporre dapprima di avere a disposizione le operazioni di divisione intera e di modulo, e poi di avere a disposizione solo operazioni di shift e il modulo.
<br /><br /><br /><br />

<!-- lettori_scrittori_messaggi -->
Si consideri la soluzione tramite scambio messaggi al problema dei lettori/scrittori vista a lezione.<br />
<textarea cols="100" rows="48" readonly="readonly">
void reader(int i)
{
  while (true) {
    nbsend (readrequest, null);
    receive (controller_pid, null);
    READUNIT ();
    nbsend (finished, null);
} }

void writer(int j)
{
  while (true) {
    nbsend (writerequest, null);
    receive (controller_pid, null);
    WRITEUNIT ();
    nbsend (finished, null);
} }

void controller() {
  int count = MAX_READERS;
  while (true) {
    if (count &gt; 0) {
      if (!empty (finished)) { /* da reader! */
        receive (finished, msg);
        count++;
      }
      else if (!empty (writerequest)) {
        receive (writerequest, msg);
        writer_id = msg.sender;
        count = count - MAX_READERS;
      }
      else if (!empty (readrequest)) {
        receive (readrequest, msg);
        count--;
        nbsend (msg.sender, "OK");
    }  }
    if (count == 0) {
      nbsend (writer_id, "OK");
      receive (finished, msg); /* da writer! */
      count = MAX_READERS;
    }
    while (count &lt; 0) {
      receive (finished, msg); /* da reader! */
      count++;
    } /* while (count &lt; 0) */
  } /* while (true) */
} /* controller */
</textarea>
<br />
Correggere tale codice in modo tale che non ci sia più la limitazione sul numero massimo di lettori. A tal scopo, usare una variabile booleana aggiuntiva che viene settata quando uno scrittore vuole eseguire =READUNIT=. Aggiungere anche un opportuno =main=.
<br /><br /><br /><br />

<!-- lettori_scrittori_messaggi -->
Si consideri la soluzione tramite scambio messaggi al problema dei lettori/scrittori vista a lezione.<br />
<textarea cols="100" rows="48" readonly="readonly">
void reader(int i)
{
  while (true) {
    nbsend (readrequest, null);
    receive (controller_pid, null);
    READUNIT ();
    nbsend (finished, null);
} }

void writer(int j)
{
  while (true) {
    nbsend (writerequest, null);
    receive (controller_pid, null);
    WRITEUNIT ();
    nbsend (finished, null);
} }

void controller() {
  count = MAX_READERS;
  while (true) {
    if (count &gt; 0) {
      if (!empty (finished)) { /* da reader! */
        receive (finished, msg);
        count++;
      }
      else if (!empty (writerequest)) {
        receive (writerequest, msg);
        writer_id = msg.sender;
        count = count - MAX_READERS;
      }
      else if (!empty (readrequest)) {
        receive (readrequest, msg);
        count--;
        nbsend (msg.sender, "OK");
    }  }
    if (count == 0) {
      nbsend (writer_id, "OK");
      receive (finished, msg); /* da writer! */
      count = MAX_READERS;
    }
    while (count &lt; 0) {
      receive (finished, msg); /* da reader! */
      count++;
    } /* while (count &lt; 0) */
  } /* while (true) */
} /* controller */
</textarea>
<br />

      * Supporre che le mailbox non siano gestite con una FIFO, ma in modo non specificato, come avviene per i semafori deboli. Allora, può esserci starvation? Se sì, fornire un esempio; se no, motivare.

      * Si supponga di non avere il test =empty=. Come si sarebbe dovuto riscrivere il controllore?

<br /><br /><br /><br />

<a name="esercizi_12"/>
---++ Esercizi da 12 punti

Per rispondere, __non__ è concesso consultare libro e dispense

<br /><br /><br /><br />

<!-- semafori -->
I seguenti tre processi concorrenti stampano caratteri come indicato:
<br />
<textarea cols="100" rows="6" readonly="readonly">
[Process 1]         [Process 2]         [Process 3]

while(1) {          while(1) {          while(1) {
   print("A");        print("B");          print("C");
}                   }                   }
</textarea>
<br />
Si richiede di dichiarare e gestire opportunamente dei semafori in modo tale che i caratteri vengano stampati secondo la seguente tabella:

&lt;!--ancora dentro--&gt;  &lt;!--ancora dentro--&gt;&lt;!--ancora dentro--&gt;&lt;!--ancora dentro--&gt;&lt;!--ancora dentro--&gt;&lt;!--ancora dentro--&gt;&lt;!--ancora dentro--&gt; &lt;!--ancora dentro--&gt;&lt;!--ancora dentro--&gt;&lt;!--ancora dentro--&gt;&lt;!--ancora dentro--&gt;&lt;!--ancora dentro--&gt;&lt;!--ancora dentro--&gt;
| | *A* | *B* | *C* |
| *minimo* | infinito | 0 | 4 |
| *massimo* | infinito | limitato | 4 |
<!--ancora dentro-->

È richiesto anche di gestire la stessa =print= come una risorsa critica cui accedere in mutua esclusione. <br />
Si assuma solo che il dispatcher, prima o poi, dia l'opportunità di andare in esecuzione a tutti i processi, e che nessun altro processo manipoli i semafori che verranno aggiunti. Non è consentito modificare o cancellare le istruzioni già presenti.<br />
<br /><br /><br /><br />

<!-- produttore_consumatore_mod_sem -->
Un produttore P produce dati che mette in tre code FIFO, identificate con q0, q1 e q2, in modo circolare fra le tre. Tre consumatori C0, C1 e C2, prelevano un dato per volta, rispettivamente dalle code q0, q1 e q2, e li elaborano.<br />
I tempi di ogni singola produzione ed elaborazione sono molto irregolari, al punto che un consumatore può trovare la propria coda vuota, nel qual caso può prelevare un dato dalla coda successiva in senso circolare.<br />
Scrivere lo pseudo codice corrispondente ai processi P, C0, C1 e C2, utilizzando semafori generali per la sincronizzazione, e sapendo che le code q0, q1 e q2 sono di lunghezza uguale (e finita). <br />
<br /><br /><br /><br />

<!-- produttore_consumatore_mod_sem -->
3 produttori P0, P1 e P2 producono dati che mettono in 3 code FIFO, identificate con q0, q1 e q2, rispettivamente. Un consumatore C preleva un dato per volta, in modo circolare tra le code q0, q1 e q2, e lo elabora.<br />
I tempi di ogni singola produzione ed elaborazione sono molto irregolari, al punto che un produttore può trovare la propria coda piena, nel qual caso può prelevare un dato dalla coda successiva in senso circolare.<br />
Scrivere lo pseudo codice corrispondente ai processi P0, P1, P2 e C, utilizzando semafori generali per la sincronizzazione, e sapendo che le code q0, q1 e q2 sono di lunghezza uguale (e finita). <br />
<br /><br /><br /><br />

<!-- lock -->
Si supponga di avere a disposizione, come metodo di sincronizzazione, solamente le primitive =lock/unlock=. Entrambe prendono in input un'etichetta e funzionano in modo simile alle =semWaitB/semSignalB= di un semaforo binario inizializzato ad 1, con la limitazione che una chiamata ad =unlock= non ha nessun effetto se prima non era stata chiamata la =lock=. Risolvere il problema del produttore/cnsumatore usando solo le dette primitive.
<br /><br /><br /><br />

<!-- barrier -->
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.
<br /><br /><br /><br />

<!-- barrier_exch -->
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 solo l'istruzione atomica =exchange= (e ovviamente la memoria condivisa), si richiede di scrivere la primitiva =barrier= in termini dei meccanismi disponibili.
<br /><br /><br /><br />

<!-- barrier_mess -->
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 solo lo scambio di messaggi, si richiede di scrivere la primitiva =barrier= in termini dei meccanismi disponibili.
<br /><br /><br /><br />