-

Compito di Sistemi Operativi, Prof. Mancini - 4 giugno 1998

1. (punti: -1.5, 4)

Nella realizzazione di processi concorrenti:

  1. il campo "ImmagineInMemoria" del descrittore del processo P contiene l'immagine di P prelevata dai registri del processore quando P passa dallo stato di esecuzione a quello di attesa;
  2. il campo "ImmagineInMemoria" del descrittore del processo P contiene l'immagine di P prelevata dai registri del processore quando P passa dallo stato di attesa a quello di pronto;
  3. il campo "ImmagineInMemoria" del descrittore del processo P contiene l'immagine di P prelevata dai registri del processore quando P passa dallo stato di pronto a quello di esecuzione;
  4. il campo "ImmagineInMemoria" del descrittore del processo P contiene i dati necessari ad individuare l'area di memoria principale nella quale e' caricato P;
  5. il campo "ImmagineInMemoria" del descrittore del processo P non contiene i dati necessari ad individuare l'area di memoria principale nella quale e' caricato P;
  6. il salvataggio e il ripristino del processo P non sono indispensabili affinche', dopo essersi sospeso, P possa riprendere l'esecuzione del suo programma senza apparente discontinuita' e senza alcuna perdita di informazione;
  7. nessuna delle affermazioni precedenti e' corretta.
2. (punti: -1.5, 4)

Fra le trasformazioni subite dai programmi prima dell'esecuzione c'e' la rilocazione. In particolare,

  1. la rilocazione e' eseguita dopo che sia stato definito lo spazio fisico di un programma e consiste nel trasformare i suoi indirizzi logici in indirizzi fisici;
  2. la rilocazione consiste nel revocare lo spazio fisico di un programma P e nell'assegnare a P un nuovo spazio fisico generalmente diverso da quello precedente;
  3. la rilocazione dinamica e' indispensabile nel caso di caricamento dinamico e non puo' essere impiegata anche con il caricamento statico;
  4. la rilocazione dinamica non e' indispensabile nel caso di caricamento dinamico e puo' essere impiegata anche con il caricamento statico;
  5. la rilocazione dinamica e' indispensabile nel caso di caricamento dinamico e puo' essere impiegata anche con il caricamento statico;
  6. la rilocazione dinamica non e' indispensabile nel caso di caricamento dinamico e non puo' essere impiegata anche con il caricamento statico;
  7. nessuna delle affermazioni precedenti e' corretta.
3. (punti: -1.5, 4)

Assumendo in ogni caso un comportamento bloccante per la primitiva receive:

  1. i modelli di comunicazione si dicono sincroni, se la send ha un comportamento bloccante;
  2. i modelli di comunicazione si dicono sincroni, se la send non ha un comportamento bloccante;
  3. la forma di comunicazione chiamata "rendez-vous" richiede un comportamento non bloccante della send;
  4. la forma di comunicazione chiamata "rendez-vous" richiede un comportamento bloccante della send;
  5. la forma di comunicazione chiamata "rendez-vous esteso" richiede un comportamento non bloccante della send;
  6. la forma di comunicazione chiamata "rendez-vous esteso" richiede un comportamento bloccante della send;
  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 contatore che registra la cardinalita' dell'insieme di processi che utilizzano l'archivio F;
  2. il contatore che registra la cardinalita' dell'insieme di elementi nella "tabella dei collegamenti" che riferiscono l'i-node dell'archivio F;
  3. il contatore che registra la cardinalita' del gruppo di utenti del quale fa parte il proprietario dell'archivio F;
  4. il cammino assoluto che individua l'archivio F nel sistema di archiviazione;
  5. il puntatore alla posizione corrente nell'archivio F;
  6. il modo con il quale l'archivio F e' stato aperto;
  7. nessuna delle affermazioni precedenti e' corretta.
5. (punti: -0.5, 5.4)

Un processo esegue il comando:

fd = open("/users/studenti/file1", RDONLY);

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"  

 

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
15
P2
4
10
P3
4
7
P4
7
6
P5
15
7

  1. (punti: 4) Assegnare questo insieme di processi ad un processore in base alla politica Shortest Job First con prerilascio.
  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 = 2 3 6 1 8 3 0 5 1 4 2 8 6 2 4 1 5 8 3 2

  1. (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.
  2. (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.
8. (punti: 10)

Scrivere le procedure send e receive per la comunicazione tra processi secondo il modello sincrono utilizzando i semafori.

9. (punti: 6)

Estendere il comando grep di Unix realizzando un Perl script efficiente che riceve dalla linea di comando tre argomenti (una stringa, un numero k e un nome di file) e restituisce in STDOUT per ogni linea di file che contiene stringa anche le k linee precedenti

.

Risultati della prova

1. d
2. a,e
3. a,d,e
4. g

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

 

6.
  
P1
 
P3
 
P3
 
P4
 
P4
 
P5
 
P2
 
P1
 
0-4
 
4-7
 
7-11
 
11-15
 
15-17
 
17-24
 
24-34
 
34-35

Tempo medio di attesa = 56/5

Tempo medio di turnaround = 101/5

7.

(a) Algoritmo ottimo:
 
 
Pagina riferita
2
3
6
1
8
3
0
5
1
4
2
8
6
2
4
1
5
8
3
2
0
2
2
2
2
2
2
2
2
2
2
2
2
2
2
2
2
2
2
2
2
1
  
3
3
3
3
3
0
5
5
4
4
4
4
4
4
4
5
5
3
3
2
    
6
6
6
6
6
6
6
6
6
6
6
6
6
6
6
6
6
6
3
      
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
4
        
8
8
8
8
8
8
8
8
8
8
8
8
8
8
8
8
 
P
P
P
P
P
  
P
P
  
P
            
P
  
P
  

 Numero di page fault: 5+5

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

  Numero di page fault: 5+10

8.

Per questo esercizio sono considerate errate tutte le soluzioni che non considerano la gestione dei nomi mittente e destinatario e il ripristino e la sospensione dei processi coinvolti nella comunicazione. 

vedere Maestrini alla pagina 195, oppure la soluzione del compito dell' 11 febbraio 1998.

9.

Bisogna mantenere in memoria un buffer di k linee del file. La linea in esame viene aggiunta al buffer sovrascrivendo quella più vecchia ad ogni passo. Se la linea in esame contiene "stringa", allora si restituisce il contenuto del buffer lungo k e la linea in esame. 

($Pattern, $k) = ($ARGV[0], $ARGV[1]); 
for (0..$k) { $buff [$_] = ""; } # inizializzazione vettore...
$i = -1;
open (INPUT, "$ARGV[2]") || die $!; 
while ( <INPUT> ) 
   {
   $i = (++$i) % ($k+1);
   $buff[$i] = $_;
   if ( /$Pattern/o )
      {
      print "Match trovato: $_";
      for (1..$k)
         {
         print $buff[ ($_+$i) % ($k+1) ];
         }
      }
   }
Il programma e' stato testato con il Perl 5.003 per Windows 95.

- 4 giugno 1998 -




Si ringraziano i volenterosi studenti Alessandro Cagnetti e Daniele Giabbai.