Compito di Sistemi Operativi, Prof. Mancini - 30 settembre 1997

1. (punti: -1.5, 4)

I "meccanismi elementari" per la mutua esclusione:

  1. devono essere esplicitamente attivati dai processi;
  2. vengono attivati in modo trasparente ai processi;
  3. causano ai processi dei ritardi non necessari;
  4. causano ai processi solo ritardi necessari;
  5. sono applicabili senza sostanziali inconvenienti solo a sezioni critiche brevi;
  6. sono applicabili senza sostanziali inconvenienti anche a sezioni critiche lunghe;
  7. nessuna delle affermazioni precedenti e' corretta.
2. (punti: -1.5, 4)

Una risorsa e' chiamata "prerilasciabile" se e solo se:

  1. il processo P al quale e' assegnata puo' riinizializzare lo stato della risorsa in qualsiasi istante;
  2. il processo P al quale e' assegnata non puo' riinizializzare lo stato della risorsa in qualsiasi istante;
  3. puo' essere sottratta ad un processo P al quale e' assegnata senza che P la rilasci esplicitamente, successivamente la risorsa prerilasciata sara' restituita a P che nell'attesa di questo evento deve essere sospeso;
  4. puo' essere sottratta ad un processo P al quale e' assegnata solo se P la rilascia esplicitamente, successivamente la risorsa prerilasciata sara' restituita a P che nell'attesa di questo evento deve essere sospeso;
  5. puo' essere sottratta ad un processo P al quale e' assegnata senza che P la rilasci esplicitamente, successivamente la risorsa prerilasciata sara' restituita a P che nell'attesa di questo evento non deve essere sospeso;
  6. puo' essere sottratta ad un processo P al quale e' assegnata solo se P la rilascia esplicitamente, successivamente la risorsa prerilasciata sara' restituita a P che nell'attesa di questo evento non deve essere sospeso;
  7. nessuna delle affermazioni precedenti e' corretta.
3. (punti: -1.5, 4)

L'organizzazione della memoria centrale con paginazione statica:

  1. introduce una certa frammentazione interna, che e' tanto piu' rilevante quanto piu' la lunghezza media dei programmi e' grande rispetto all'ampiezza della pagina;
  2. introduce una certa frammentazione interna, che e' tanto meno rilevante quanto piu' la lunghezza media dei programmi e' grande rispetto all'ampiezza della pagina;
  3. introduce una certa frammentazione esterna, che e' tanto meno rilevante quanto piu' la lunghezza media dei programmi e' grande rispetto all'ampiezza della pagina;
  4. introduce una certa frammentazione esterna, che e' tanto piu' rilevante quanto piu' la lunghezza media dei programmi e' grande rispetto all'ampiezza della pagina;
  5. elimina la frammentazione esterna e rimuove il vincolo della contiguita' dello spazio fisico in memoria centrale;
  6. elimina la frammentazione esterna ma mantiene il vincolo della contiguita' dello spazio fisico in memoria centrale;
  7. nessuna delle affermazioni precedenti e' corretta.
4. (punti: -1.5, 4)

Una struttura dati i­node del sistema di archiviazione di Unix e' associata ad un archivio F. Il campo link (collegamenti) di questo i­node contiene:

  1. il puntatore alla posizione corrente nell'archivio F;
  2. un contatore che registra la cardinalita' dell'insieme di processi che stanno utilizzando l'archivio F;
  3. un contatore che registra la cardinalita' dell'insieme di direttori dai quali e' possibile accedere all'archivio F;
  4. un contatore che registra la cardinalita' dell'insieme di elementi nella tabella dei collegamenti che riferiscono l'i­node dell'archivio F;
  5. un contatore che registra la cardinalita' del gruppo di utenti del quale fa parte il proprietario dell'archivio F;
  6. il modo con il quale l'archivio F e' stato aperto;
  7. essuna delle affermazioni precedenti e' corretta.
5. (punti: -0.5, 5.4)

Sono nella shell del sistema Unix e cancello l'archivio file1 con il comando

rm /users/studenti/file1

L'operazione ha successo. Quali delle seguenti strutture dati sono state sicuramente modificate e quali sono rimaste sicuramente invariate durante l'esecuzione di questo comando? (Indicare M per sicuramente Modificate, I per sicuramente Invariate e lasciare in bianco altrimenti.)
 
Struttura dati  Modificata/Invariata
a) il super-block  
b) l'i-node bitmap  
c) la block bitmap   
d) l'i-node di "file1"  
e) la tabella FILP   
f) la tabella degli i-node  
g) la tabella dei processi   
h) il root-directory  
i) il direttorio "studenti"  
j) il direttorio "users"  

 

6. Considerare un insieme di cinque processi P1, P2, P3, P4, P5 con i seguenti tempi di arrivo e tempi di esecuzione in millisecondi:
 
Processo
Tempo di arrivo
Tempo di esecuzione
P1
0
16
P2
4
11
P3
9
9
P4
11
7
P5
7
10

  1. (punti: 4) Assegnare questo insieme di processi ad un processore in base alla politica Round Robin considerando un quanto di tempo di 5 millisecondi.
  2. (punti: 2) Calcolare il valor medio del tempo di attesa dei processi.
  3. (punti: 2) Calcolare 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 = 9 3 1 0 5 9 1 4 2 0 3 6 2 4 1 5 9 0 3 6

  1. (punti: 4) 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.
  2. (punti: 4) Illustrare il comportamento dell'algoritmo Ottimo di sostituzione delle pagine per una memoria fisica di 5 blocchi. Calcolare il numero di page fault che si verificano.
8. (punti: 10)

Utilizzare le primitive P e V definite sui semafori per garantire la consistenza di un insieme condiviso di dati fra processi lettori e processi scrittori.
 
 

9. (punti: 6)

Scrivere un Perl script efficiente che riceve i nomi di due archivi come argomenti e restituisce in STDOUT l'intersezione per linee di questi due archivi. Il programma da un messaggio d'errore se i due archivi non esistono.

Risultati della prova

1. a,c,e
2. c
3. b,e
4. c

5.
 
Struttura dati  Modificata/Invariata
a) il super- block I
b) l'i- node bitmap  
c) la block bitmap   
d) l'i- node di "file1" M
e) la tabella FILP  I
f) la tabella degli i- node I
g) la tabella dei processi  I
h) il root-directory I
i) il direttorio "studenti" M

 

6.
  
P1
 
P2
 
P1
 
P5
 
P3
 
P2
 
P4
 
P1
 
P5
 
P3
 
P2
 
P4
 
P1
 
0-5
 
5-10
 
10-15
 
15-20
 
20-25
 
25-30
 
30-35
 
35-40
 
40-45
 
49-49
 
49-50
 
50-52
 
52-53

Tempo medio di attesa = 165/5

Tempo medio di turnaround = 218/5

7.

(a) Algoritmo LRU (pag 469 del Maestrini):
 
 
Pagina riferita
9
3
1
0
5
9
1
4
2
0
3
6
2
4
1
5
9
0
3
6
0
9
9
9
9
9
9
9
9
9
9
3
3
3
3
3
5
5
5
5
5
1
  
3
3
3
3
3
3
4
4
4
4
4
4
4
4
4
4
4
3
3
2
    
1
1
1
1
1
1
1
1
1
6
6
6
6
6
9
9
9
9
3
      
0
0
0
0
0
2
2
2
2
2
2
2
2
2
0
0
0
4
        
5
5
5
5
5
0
0
0
0
0
1
1
1
1
1
6
 
P
P
P
P
P
    
P
P
P
P
P
    
P
P
P
P
P
P

  Numero di page fault: 5+11

(b) Algoritmo ottimo:
 
 
Pagina riferita
9
3
1
0
5
9
1
4
2
0
3
6
2
4
1
5
9
0
3
6
0
9
9
9
9
9
9
9
4
4
4
4
4
4
4
4
5
9
9
3
3
1
  
3
3
3
3
3
3
3
3
3
3
6
6
6
6
6
6
6
6
6
2
    
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
3
      
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
4
        
5
5
5
5
2
2
2
2
2
2
2
2
2
2
2
2
 
P
P
P
P
P
    
P
P
    
P
      
P
P
  
P
  

 Numero di page fault: 5+6

8. 

semaphore mutex=1, db=1;
int rc=0;

void Lettore()
   {
   P(mutex);
   rc++;
   if (rc==1) P(db);
   V(mutex);
   LetturaDB();
   P(mutex);
   rc--;
   if (rc==0) V(db);
   V(mutex);
   }

void Scrittore()
   {
   P(db);
   ScritturaDB();
   V(db);
   }

9. 

Per esercizio...

30 settembre 1997 -




Si ringraziano i volenterosi studenti Alessandro Cagnetti e Daniele Giabbai.