Tutti gli esercizi per l'orale

Esercizi da 4 punti
Esercizi da 8 punti
Esercizi da 12 punti

Esercizi da 4 punti

Per rispondere, non è concesso consultare libro e dispense



1 I seguenti due processi concorrenti condividono una variabile ed un semaforo:

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?




2 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?




3 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?




4 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 < C ≤ 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.




5 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 < C ≤ 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.




6 Considerare un insieme di cinque processi P1, P2, P3, P4, P5 con i seguenti tempi di arrivo e tempi di esecuzione in millisecondi:
ProcessoTempo di ArrivoTempo di esecuzione
P1215
P2510
P3127
P495
P5157
Assegnare questo insieme di processi ad un processore usando l'algoritmo di scheduling SRT, fino a quando non terminano tutti. Rispondere alle seguenti domande:




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




8 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:
Pagina logica0123
Frame5712
Quali sono le traduzioni dei seguenti indirizzi logici: 3, 4, 10, 32?




9 Si consideri la seguente soluzione al problema della mutua esclusione tra processi:

Assegnare un valore di verità alle seguenti affermazioni, spiegandone il motivo.




10 Si consideri la seguente soluzione al problema della mutua esclusione tra processi:

Assegnare un valore di verità alle seguenti affermazioni, spiegandone il motivo.




11 Si consideri la seguente soluzione al problema della mutua esclusione tra processi:

Assegnare un valore di verità alle seguenti affermazioni, spiegandone il motivo.




12 Si considerino le soluzioni al problema dei lettori/scrittori che usano i semafori viste a lezione, riportate qui di seguito:



Assegnare un valore di verità alle seguenti affermazioni, spiegandone il motivo.




13 Si consideri la soluzione tramite scambio messaggi al problema dei lettori/scrittori vista a lezione.

Assegnare un valore di verità alle seguenti affermazioni, spiegandone il motivo.




14 Si consideri la soluzione al problema del produttore/consumatore che usa lo scambio messaggi vista a lezione.

Si supponga che venga usata così com'è per produttori e consumatori multipli. Assegnare un valore di verità alle seguenti affermazioni, spiegandone il motivo.




15 Si supponga che la situazione ad un incrocio sia la seguente:

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?




16 Si consideri la soluzione al problema della strettoia di Trastevere vista a lezione.

Si supponga che, ad un dato istante, ci siano 3 macchine da sinistra nella strettoia, 3 macchine da sinistra che stanno per eseguire wait(strettoia), e 2 macchine da destra in attesa (su quali semafori?). Si supponga che ora arrivino altre 2 macchine da sinistra. Descrivere come evolverà la situazione, supponendo che non ci siano altri arrivi.




17 È possibile che eseguire un'istruzione non cambi né l'immagine nè il PCB di un processo?




18 Si supponga che un processo venga dapprima eseguito su un processore, poi venga sospeso o rimesso in ready, e infine venga nuovamente schedulato per l'esecuzione. Cosa accade al TLB? È possibile reinizializzarlo, all'inizio della seconda esecuzione, al valore che aveva alla fine della prima esecuzione?




19 Un computer ha una cache, la memoria principale e un disco per la memoria virtuale (paginata). In caso di cache hit, l'accesso richiede 20 ns. In caso di cache miss, ma con page hit l'accesso richiede 60 ns per caricare il dato sulla cache (includendo il tempo per accorgersi del cache miss), dopodiché l'accesso viene ripetuto da capo. In caso di cache miss seguito da page miss, l'accesso richiede 12 ms per prendere la pagina dal disco, seguito da altri 60 ns per copiarlo nella cache, e si ripete l'accesso. Se il cache hit ratio è 0.9 and il page hit ratio è 0.6, qual è il tempo medio in ns per l'accesso ad un dato?




20 Si supponga di avere una cache di 128 lines, ognuna in grado di memorizzare 8 words, ciascuna di 8 bytes. Si supponga altres&iagrave; che il bus degli indirizzi sia di 16 bit, e che la funzione di mappatura consista nel prendere i bit più significativi di un indirizzo. Quanti bit ha il tag della cache? Qual è l'overhead di memoria totale dovuto ai tag? Descrivere cosa succede con la seguente sequenza di richieste di lettura (a partire dalla cache vuota): 0x3fff, 0x3ffe, 0x3ff7, 0x000e.




Esercizi da 8 punti

Per rispondere, non è concesso consultare libro e dispense



21 Si assuma che, al tempo 5, le uniche risorse di sistema in uso siano il processore e la memoria. Si considerino i seguenti eventi:
TempoEvento
5P1 richiede una lettura al disco 3
15Finisce il quanto di tempo di P5
18P7 richiede una scrittura al disco 3
20P3 richiede una lettura al disco 2
24P5 richiede una scrittura al disco 3
28P5 viene sospeso
33Il disco 2 comunica con un interrupt il completamento della richiesta di P3
36Il disco 3 comunica con un interrupt il completamento della richiesta di P1
38P8 termina
40Il disco 3 comunica con un interrupt il completamento della richiesta di P5
44P5 torna in memoria
48Il disco 3 comunica con un interrupt la fine della richiesta di P7
Identificare, per gli istanti di tempo 22, 37 e 47, gli stati in cui si trovano i processi coinvolti; in caso si tratti di processi bloccati, precisare di quali eventi sono in attesa. Come può essere spiegato il fatto che la richiesta di P5 abbia preceduto quella di P7? Cosa si può dire dello scheduler in uso, e più in generale sui tipi di scheduler presenti? Cosa si può dire sul modello degli stati usato?




22 I seguenti due processi concorrenti condividono una variabile ed un semaforo:

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?




23 Un sistema con gestione paginata semplice della memoria ha indirizzi di B bit e pagine di dimensione P KiB. Se tutta la memoria è paginabile, qual è il numero massimo di elementi contenuti nella tabella delle pagine di un processo? E se invece K KiB 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?




24 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 KiB 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 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.




25 Considerare un insieme di n processi P1, ..., Pn. Per ciascun processo, sono noti i tempi (time-stamp) di arrivo A1, ..., An, i tempi di servizio S1, ..., Sn ed i tempi (time-stamp) di terminazione C1, ..., Cn; questi ultimi vengono ottenuti tramite un qualche algoritmo di scheduling. Rispondere alle seguenti domande:




26 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 (b = 2k 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} → {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 << z lo shift a sinistra di y per z bit e con y >> 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.




27 Si consideri la soluzione tramite scambio messaggi al problema dei lettori/scrittori vista a lezione.

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 all'interno del controller. Aggiungere anche un opportuno main.




28 Si consideri la soluzione tramite scambio messaggi al problema dei lettori/scrittori vista a lezione.






29 Uno spinlock è l'equivalente di un ciclo while (var == 1) {/* non fare niente */;}, ed implementa pertanto una forma di busy-waiting. Viene spesso usato dal kernel, in alternativa alla wait su un semaforo, se c'è la ragionevole speranza che, in caso il lock sia già stato acquisito, esso venga rilasciato in breve tempo (risparmiando così sull'esecuzione, relativamente costosa se effettuata nel kernel, della wait stessa). Discutere pregi e difetti di questa soluzione, tenendo conto che:




30 Un computer ha un sistema di input/output chiamato "Telescrivente" (teletype), consistente in una tastiera ed una stampante di solo testo. Fino agli anni 60, la telescrivente costituiva una modalità importante di interazione con i computer: essenzialmente, era come l'attuale interfaccia da riga di comando (di cui è l'antenato) ma anziché avere un monitor, ancora troppo costoso, c'era la stampante. Non a caso, in Linux i "terminali" sono indicati con tty (da teletype, appunto). Le telescriventi erano usate anche per trasmettere messaggi in remoto, ma questo uso non verrà considerato qui.
La telescrivente ha i seguenti registri: La telescrivente sa codificare il tasto prenuto sulla tastiera in codice ASCII (8 bit), e sa fare anche la decodifica (per la stampa). Quando in INPR viene caricato un valore (letto dalla tastiera), FGI viene immediatamente settato. Quando viene completata la stampa di un carattere sulla stampante, FGO viene settato.
Descrivere come la CPU può interagire con la telescrivente, usando prima solamente i primi 4 registri, poi anche l'ultimo. Le interazioni devono essere del tipo: "leggi un carattere dalla tastiera", "stampa un carattere", "leggi un carattere dalla tastiera e stampalo contemporaneamente". Mostrare che, usando l'ultimo flag, la realizzazione è più efficiente.




31 Si consideri la soluzione tramite semafori al problema dei produttori/consumatori vista a lezione.

Cosa succede scambiando, una alla volta, le seguenti coppie di segnali? La soluzione resta corretta?




32 Si assuma di avere i seguenti 3 processi che cercano di accedere a 5 risorse consumabili.


Mostrare che il deadlock è possibile, usando un grafo dell'allocazione delle risorse. Come si può modificare l'ordine delle richieste alle risorse in modo tale che non ci sia deadlock? Ovviamente, la critical region di ogni processo non può essere modificata, pertanto, dev'essere assicurato che tutte le risorse richieste siano effettivamente acquisite.




Esercizi da 12 punti

Per rispondere, non è concesso consultare libro e dispense



33 Si consideri la seguente soluzione software al problema della mutua esclusione:

Dimostrare che è possibile che la mutua esclusione venga violata. Si risolverebbe scambiando di posto i 2 while su turn e blocked? Supponendo di poter render una parte di questo codice atomica, qual è la porzione di codice più piccola da scegliere per far sì che la mutua esclusione non venga violata?




34 Si consideri la seguente soluzione al problema della mutua esclusione dovuta al grande informatico Leslie Lamport:

Affinché funzioni, come deve essere definito il minore tra coppie di numeri? Perché funziona? Evita il deadlock? Evita la starvation? Cosa succede se si elimina il vettore choosing (e tutte le istruzioni che lo riguardano)?




35 Si consideri la seguente soluzione (per il processo i-esimo) al problema della mutua esclusione dovuta a Eisenberg-McGuire:

Quali sono le variabili globali usate, e quali quelle locali? Come vanno inizializzate? Mostrare una violazione della mutua esclusione nei seguenti casi:




36 Si discuta una soluzione che eviti il deadlock (per risorse riusabili) evitando che un processo potenzialmente bloccante possa andare in esecuzione. Assumere la conoscenza delle richieste future, come nell'algoritmo del banchiere. Qual è la differenza con l'algoritmo del banchiere?




37 Il Jurassic Park consiste di un museo dei dinosauri e di un parcheggio da dove si parte per i safari. Ci sono m passeggeri e n automobili da safari, ciascuna con un solo passeggero. I passeggeri visitano il museo per un po', dopodiché si mettono in fila per salire su una macchina. Quando una macchina è disponibile, viene fatto salire il singolo passeggero e si fa il safari per un certo periodo di tempo. Se non ci sono macchine disponibili, i passeggeri aspettano; se non ci sono passeggeri disponibili, le macchine aspettano. Scrivere una soluzione a questo problema usando i semafori e la memoria condivisa.




38 Il Jurassic Park consiste di un museo dei dinosauri e di un parcheggio da dove si parte per i safari. Ci sono m passeggeri e n automobili da safari, ciascuna con un solo passeggero. I passeggeri visitano il museo per un po', dopodiché si mettono in fila per salire su una macchina. Quando una macchina è disponibile, viene fatto salire il singolo passeggero e si fa il safari per un certo periodo di tempo. Se non ci sono macchine disponibili, i passeggeri aspettano; se non ci sono passeggeri disponibili, le macchine aspettano. Scrivere una soluzione a questo problema usando le istruzioni macchina speciali.




39 Il Jurassic Park consiste di un museo dei dinosauri e di un parcheggio da dove si parte per i safari. Ci sono m passeggeri e n automobili da safari, ciascuna con un solo passeggero. I passeggeri visitano il museo per un po', dopodiché si mettono in fila per salire su una macchina. Quando una macchina è disponibile, viene fatto salire il singolo passeggero e si fa il safari per un certo periodo di tempo. Se non ci sono macchine disponibili, i passeggeri aspettano; se non ci sono passeggeri disponibili, le macchine aspettano. Scrivere una soluzione a questo problema usando lo scambio messaggi.




40 Si supponga che un sistema operativo offra lo scambio di messaggi, ma non i semafori. Mostrare come si possano offrire le funzionalità dei semafori usando solo i messaggi.




41 Si supponga che un sistema operativo offra i semafori, ma non lo scambio di messaggi. Mostrare come si possano offrire le funzionalità dei messaggi usando i semafori (e memoria condivisa).




42 Si consideri il seguente frammento di codice C:

Si supponga che: Rispondere alle seguenti domande: