-

Compito di Sistemi Operativi, Prof. Mancini - 16 giugno 1999

1. (punti: -1,4)

Nei sistemi operativi organizzati secondo il modello cliente-servente:

(a)    sono necessari dei meccanismi per la generazione e la terminazione dei processi; i processi sono così strutturati in un albero, i cui cammini collegano processi antenati a processi discendenti.

(b)   non sono necessari dei meccanismi per la generazione e la terminazione dei processi; i processi sono così strutturati in un albero, i cui cammini collegano processi antenati a processi discendenti.

(c)    il nucleo contiene i dati che descrivono i processi e le procedure che realizzano i meccanismi per la concorrenza. I processi condividono dati esplicitamente al loro livello.

(d)   il nucleo contiene i dati che descrivono i processi e le procedure che realizzano i meccanismi per la concorrenza. I processi non condividono dati esplicitamente al loro livello.

(e)    il nucleo non contiene i dati che descrivono i processi e le procedure che realizzano i meccanismi per la concorrenza. I processi condividono dati esplicitamente al loro livello.

(f)     il nucleo non contiene i dati che descrivono i processi e le procedure che realizzano i meccanismi della concorrenza. I processi non condividono dati esplicitamente al loro livello.

(g)    nessuna delle affermazioni precedenti è corretta.

2. (punti: -1,4)

Un sistema composto da processi e risorse raggiunge uno stato di attesa circolare:

(a)    se esistono un insieme non vuoto  P di processi e un insieme non vuoto  R di classi di risorse, tali che ogni P_i Î P  richiede una risorsa di una classe R_k Î R e, per ogni classe R_k Î R tutte le risorse di R_k  sono assegnate a processi dell'insieme P;

(b)   se dato un insieme non vuoto di processi e un insieme non  vuoto R di classi di risorse, esiste un processo P_i Î P che richiede una risorsa di una classe R_i Î R e, per ogni classe R_k Î R, tutte le risorse di R_k sono assegnate a processi dell'insieme P;

(c)    se esistono un insieme non vuoto P di processi e un insieme non vuoto R di classi di risorse, tali che ogni P_i Î P richiede una risorsa di una classe R_i Î R e esiste una classe R_k Î R, tale che tutte le risorse di R_k  sono assegnate a processi dell'insieme P;

(d)   se dato un insieme non vuoto P di processi e un insieme non vuoto R di classi di risorse, esiste un processo P_i Î P che richiede una risorsa di una classe R_i Î R e esiste una classe R_k Î R, tale che tutte le risorse di R_k sono assegnate a processi dell'insieme P;

(e)    se esistono un insieme non vuoto P di processi e un insieme non vuoto R di classi di risorse, tali che ogni P_i Î P è sospeso per la richiesta di una risorsa di una classe R_i Î R e, per ogni classe R_k Î R, tutte le risorse di R_k sono assegnate a processi dell'insieme P;

(f)     se dato un insieme non vuoto P  di processi e un insieme non vuoto R di classi di risorse, esiste un processo P_i Î P che è sospeso per la richiesta di una risorsa di una classe R_i Î R e, per ogni classe R_k Î R, tutte le risorse di R_k  sono assegnate a processi dell'insieme P;

(g)    se le risorse sono seriali, non prerilasciabili e sono gestite con richieste bloccanti;

(h)    nessuna delle affermazioni precedenti è corretta.

3. (punti: -1,4)

Nel sistema Unix la chiamata di sistema denominata exec eseguita dal processo:

(a)      genera un processo P_j che è una copia di P_i , e restituisce a P_i il file-descriptor di P_j e a  P_j l'indice zero. I processi P_i e P_j  hanno descrittori e immagini in memoria distinte;

(b)     genera un processo P_j che è una copia di P_i, e restituisce a P_i l'indice zero e a P_j il file-descriptor di P_i. I processi P_i e P_j hanno descrittori e immagini in memoria distinte;

(c)      invoca un processo P_j da eseguire e modifica l'immagine in memoria di P_j;

(d)     invoca un processo P_j da eseguire e modifica l'immagine in memoria di P_i;

(e)      è invocata specificando un file da eseguire e modifica l'immagine in memoria del processo P_j;

(f)       è invocata specificando un file da eseguire e modifica l'immagine iii memoria del processo P_i;

(g)      nessuna delle affermazioni precedenti è corretta.

4. (punti: -1,4)

Quali delle seguenti strutture dati appartengono al sistema di archiviazione di Unix:

(a)      La TabellaDeiDescrittoriInMS, o tabella I-node, contiene le copie dei descrittori di archivio in uso da parte di almeno un processo;

(b)     La MappaDescrittoriDiArchivio, o I-node bit map, contiene le copie dei descrittori di archivio in uso da parte di almeno un processo;

(c)      La TabellaDeiDescrittoriInMS. o I-node bit map, registra lo stato di assegnazione su disco dei descrittori di archivio;

(d)     La MappaDescrittoriDiArchivio, o tabella I-node, registra lo stato di assegnazione su disco dei descrittori di archivio;

(e)      La TabellaDeiDescrittoriInMS, o I-node bit map, ogni elemento registra la cardinalità dell'insieme di processi che stanno utilizzando l archivio ad esso associato;

(f)       La MappaDescrittoriDiArchivio,  o tabella I-node, ogni elemento registra la cardinalità dell'insieme di processi che stanno utilizzando l archivio ad esso associato;

(g)      nessuna delle affermazioni precedenti è corretta.

5. (punti: 6)

Illustrare in al più 60 parole il concetto di dominio di protezione.

6. (punti: 6)

Considerare un insieme di cinque processi P₁, P₂, P₃ , P₄, P₅ con i seguenti tempi di arrivo e tempi di esecuzione in millisecondi:

Assegnare questo insieme di processi ad un processore in base alla politica Round Robin considerando un quanto di tempo  di 4 millisecondi.

Calcolare il valor medio del tempo di attesa ed il valor medio del tempo di turnaround dei processi.

7. Considerare la seguente stringa di riferimenti di un processo alla memoria in un sistema con memoria virtuale

S=5 2 1 8 7 2 4 6 8 3 1 5 9 7 3 6 1 0 5 9

(a)  (punti: 3)

Illustrare il comportamento dell'algoritmo LRU di sostituzione delle pagine per una memoria fisica di 5 blocchi. Calcolare il numero di page fault che si verificano.

(b)  (punti: 3)

Illustrare il comportamento dell'algoritmo Second Chance di sostituzione delle pagine per una memoria fisica di 5 blocchi. Calcolare il numero di page fault che si verificano.

8. (punti: 9)

Utilizzare l'algoritmo di Peterson per realizzare un protocollo che garantisca la mutua sclusine per l'accesso ad una risorsa condivisa fra due processi.

9. (punti: 9)

Un archivio contiene una sequenza di  n stringhe parzialmente ordinate, s₁£ s₂ £ &£ s_m e s_m+1£ &£ s_n. realizzare un programma Perl efficiente che ordini l'intero archivio. Valutare la complessità in tempo e spazio del programma.
 
 

Risultati della prova

1. d

2. e

3. f

4. a

5.

Un dominio di protezione è una riga della matrice di protezione. Questa è costruita ponendo sulle colonne le risorse, sulle righe i domini e nelle celle la modalità con cui un dominio può accedere alle risorse. Generalmente ad ogni utente corrisponde un dominio.

6.

a)  

b) media tempo di attesa dei processi: ((25-9)+(53-9-13)+(52-3-17)+(42-13-5)+(43-5-9))/5 = 132/5
c) valore medio del tempo di turnaround dei processi: (25+53-9+52-3+42-13+43-5)/5 = 185/5

7.

a: Algoritmo LRU (pag. 469 del Maestrini):

5

7

7

p

Numero di page fault: 5+12

b: Algoritmo Second Chance: (pag. 473 del Maestrini)

 TURNOMS=4

p

Numero di page fault: 5+12

8. Si veda Maestrini Tab. 4.8, p. 124

9. Soluzione sulla mailing list

- 16 giugno 1999 -