-

Prova scritta di Sistemi Operativi, Prof. Mancini - 30 Settembre 1998

1. (punti: -1,4)

Si consideri il meccanismo primitivo receive per lo scambio di messaggi:

  1. Nel modello di comunicazione sincrono, la receive determina la sospensione del processo che la invoca se la ricezione del messaggio non puo' avvenire immediatamente;
  2. Nel modello di comunicazione asincrono, la receive determina la sospensione del processo che la invoca se la ricezione del messaggio non puo' avvenire immediatamente;
  3. Nella sua forma bloccante, la receive determina la sospensione del processo che la invoca se la ricezione del messaggio non puo' avvenire immediatamente;
  4. Nella sua forma non bloccante, la receive determina la sospensione del processo che la invoca se la ricezione del messaggio non puo' avvenire immediatamente;
  5. Nel modello di comunicazione sincrono, la receive non provoca in nessun caso la sospensione del processo che la invoca;
  6. Nel modello di comunicazione asincrono, la receive non provoca in nessun caso la sospensione del processo che la invoca;
  7. Nella sua forma bloccante, la receive non provoca in nessun caso la sospensione del processo che la invoca;
  8. Nella sua forma non bloccante, la receive non provoca in nessun caso la sospensione del processo che la invoca;
  9. nessuna delle affermazioni precedenti e' corretta.
2. (punti: -1,4)

Quali fra le seguenti affermazioni sono corrette:

  1. si parla di modello ad ambiente locale, quando il modello concorrente consente ad un processo di accedere anche alle sue variabili locali;
  2. si parla di modello ad ambiente locale, quando un processo concorrente tende a concentrare i riferimenti alla memoria su un sottinsieme dell'insieme delle sue pagine;
  3. si parla di modello ad ambiente locale, quando il modello concorrente non consente la condivisione dei dati fra processi diversi;
  4. in un sistema multiprogrammato la migliore utilizzazione del processore permette di ridurre il valore medio del tempo di permanenza nel sistema dei lavori sottomessi dagli utenti e quindi il tempo di esecuzione di ogni singolo lavoro e' minore di quello che risulterebbe in un sistema uniprogrammato;
  5. in un sistema multiprogrammato la peggiore utilizzazione del processore non permette di ridurre il valore medio del tempo di permanenza nel sistema dei lavori sottomessi dagli utenti e quindi il tempo di esecuzione di ogni singolo lavoro e' maggiore di quello che risulterebbe in un sistema uniprogrammato;
  6. in un sistema multiprogrammato la peggiore utilizzazione del processore non permette di ridurre il valore medio del tempo di permanenza nel sistema dei lavori sottomessi dagli utenti ma il tempo di esecuzione di ogni singolo lavoro e' minore di quello che risulterebbe in un sistema uniprogrammato;
  7. in un sistema multiprogrammato piu' attivita' vengono eseguite concorrentemente, una sola di esse svolge un servizio di stretta pertinenza dell'utente;
  8. nessuna delle affermazioni precedenti e' corretta.
3. (punti: -1,4)

Ad ogni processo del sistema operativo Unix viene associata logicamente una quadrupla (proprietario reale, gruppo reale, proprietario effettivo, gruppo effettivo):

  1. l'identificazione degli utenti si propaga ai processi, nell'istante di creazione ogni processo e' attribuito ad un utente proprietario assegnando opportunamente i valori alla quadrupla che non puo' mai essere modificata durante l'esecuzione del processo;
  2. i meccanismi di protezione di Unix non consentono la migrazione dei processi in domini di protezione diversi da quelli dei loro proprietari;
  3. se un processo invoca la chiamata di sistema exec per eseguire il programma contenuto in un archivio Fi. Exec assegna al proprietario reale, e al gruppo reale i valori corrispondenti al proprietario dell'archivio Fi se e solo se e' vera la condizione SETUID contenuta nell' i-node di Fi;
  4. se un processo invoca la chiamata di sistema exec per eseguire il programma contenuto in un archivio Fi. Exec assegna al proprietario effettivo, e al gruppo effettivo i valori corrispondenti al proprietario dell'archivio Fi;
  5. nessuna delle affermazioni precedenti e' corretta.
4. (punti: -1,4)

Nel sistema operativo Unix un utente richiede l'esecuzione dell'archivio a.out:

  1. le pagine dell'archivio a.out sono interamente e costantemente caricate in memoria principale, le assegnazioni e i rilasci di pagine di memoria avvengono esclusivamente alla generazione e alla terminazione del processo che esegue a.out;
  2. le pagine dell'archivio a.out sono interamente caricate in memoria principale, successivi rilasci e ri-assegnazioni di pagine di memoria possono essere eseguiti un numero indeterminato di volte durante l'esecuzione di a.out;
  3. le pagine dell'archivio a.out sono interamente caricate in memoria principale inizialmente, successivi rilasci di pagine di memoria possono essere eseguiti durante l'esecuzione di a.out;
  4. solo poche pagine dell'archivio a.out sono caricate in memoria principale inizialmente, le altre pagine sono allocate unicamente quando sono riferite la prima volta durante l'esecuzione di a.out;
  5. solo poche pagine dell'archivio a.out sono caricate in memoria principale inizialmente, le successive assegnazioni sono eseguite e revocate un numero indeterminato di volte durante l'esecuzione di a.out, che comunque si avvicenda in ogni caso interamente in memoria;
  6. solo poche pagine dell'archivio a.out sono caricate in memoria principale inizialmente, le successive assegnazioni sono eseguite e revocate un numero indeterminato di volte durante l'esecuzione di a.out, le parti dell'archivio a.out che non vengono eseguite non vengono caricate in memoria principale;
  7. nessuna delle affermazioni precedenti e' corretta.
5. (punti: 6)

Illustrare in al piu' 60 parole il concetto di insieme di lavoro (working set) WS(t,d ) di un processo.

6. Considerare un insieme di cinque processi P1, P2, P3, P4, P5 con i seguenti tempi di arrivo tempi di esecuzione in millisecondi:
 
 
Processo  Tempo di arrivo  Tempo di esecuzione 
P1
0
15
P2
3
10
P3
10
7
P4
7
6
P5
13
7

 

  1. (punti: 4) Assegnare questo insieme di processi ad un processore in base alla politica Round Robin considerando un quanto di tempo di 4 millisecondi.
  2. (punti: 2) Calcolare il valor medio del tempo di attesa dei processi.
  3. (punti: 2) Calcolare il throughput medio, cioe' il numero di processi completati nell'unita' di tempo.

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

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

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

Risolvere utilizzando un monitor il problema dei processi lettori e scrittori, adottando una politica che eviti l'attesa indefinita.

9. (punti: 8)

Realizzare un Perl script efficiente che riceve dalla linea di comando un pattern ed una sequenza di file e che restituisce come risultato un file di tutte le linee che NON contengono il pattern passato come argomento.

 

Risultati della prova

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

5.
Si definisce insieme di lavoro WS(t,d) di un processo Pi al tempo virtuale t l'insieme delle pagine riferite da Pi nell'intervallo di tempo virtuale (t-d,t]. Il tempo virtuale del generico processo Pi e' definito uguale a zero alla generazione del processo e avanza con un incremento unitario a ogni riferimento alla memoria eseguito da Pi (si veda Maestrini).

6.
a) Algoritmo Round Robin con quanto = 4 millisecondi:
 
 
P1
P2
P1
P4
P2
P3
P1
P5
P4
P2
P3
P1
P5
0-4
4-8
8-12
12-16
16-20
20-24
24-28
28-32
32-34
34-36
36-39
39-42
42-45

b) media tempo di attesa dei processi: 118/5
c) throughput medio: 5/45

7.
a) Algoritmo Second Chance (pag 473 del Maestrini):
 
 
TurnoMS

  TurnoMS e' inizializzato a 4.
 
 
1
4
5
2
6
4
3
7
5
0
6
1
6
2
5
4
0
7
1
3
0
11
11
11
11
11
11
31
31
31
31
31
30
30
21
21
21
21
20
11
11
1
  
41
41
41
41
41
40
71
71
71
71
70
70
70
51
51
51
50
50
31
2
    
51
51
51
51
50
50
51
50
50
11
11
11
11
10
10
71
71
71
3
      
21
21
21
20
20
20
01
01
01
01
00
00
41
41
41
40
40
4
        
61
61
60
60
60
60
61
60
61
60
60
60
01
01
00
00
 
p
p
p
p
p
  
p
p
  
p
  
p
  
p
p
p
p
p
p
p

  Numero di page fault: 16

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

 Numero di page fault: 17

8.
Qui sono riportate le generiche procedure Lettore e Scrittore. 

void Lettore() 
 { 
 monitor.OttieniPermessoInLettura(); 
 Lettura(); 
 monitor.RilasciaPermessoInLettura(); 
 } 
void Scrittore() 
 { 
 monitor.OttieniPermessoInScrittura(); 
 Scrittura(); 
 monitor.RilasciaPermessoInScrittura(); 
 } 
 
Monitor: variabili permanenti 
condition L, S; 
boolean Scrittori=False; 
int ContatoreLettori=0, ContatoreLettoriNelMonitor=0, ContatoreScrittoriNelMonitor=0; 
 
Monitor: procedure interne 
Monitor::OttieniPermessoInLettura() 
  { 
  ContatoreLettori++; 
  If ( ContatoreScrittoriNelMonitor == 0 || Scrittori ) 
    { 
    ContatoreLettoriNelMonitor++; 
    wait(L); 
    ContatoreLettoriNelMonitor--; 
    } 
  signal(L); 
  } 

Monitor::RilasciaPermessoInLettura() 
  { 
  ContatoreLettori--; 
  If ( ContatoreLettori == ContatoreLettoriNelMonitor ) 
    signal(S); 
  } 

Monitor::OttieniPermessoInScrittura() 
  { 
  ContatoreScrittori++; 
  If ( ( ContatoreLettori == ContatoreLettoriNelMonitor ) || Scrittori ) 
    { 
    ContatoreScrittoriNelMonitor++; 
    wait(S); 
    ContatoreScrittoriNelMonitor--; 
    } 
  Scrittori=True; 
  } 

Monitor::RilasciaPermessoInScrittura() 
  { 
  ContatoreScrittori--; 
  Scrittori=False; 
  If (ContatoreLettori != 0) 
    signal(L); 
  else 
    signal(S); 
  }

9. 

#!/usr/bin/perl
die "Argomenti insufficienti!" if ( scalar(@ARGV) < 2 ); 
$Pattern = shift @ARGV; 
open(OUT,"Output") || die $!; 
foreach (@ARGV) 
  { 
  while (<>) 
    { 
    print OUT $_ if ($_ !~ /$Pattern/o); 
    } 
  }
Notare che in un ciclo 
     foreach (@ARGV) { while(<>) {...} ...}
l'interprete perl apre automaticamente tutti i files i cui nomi sono stati passati da riga di comando, senza dover specificare esplicitamente l'istruzione open.

Le soluzioni adottate in questo script sono rivolte all'efficienza, e non alla chiarezza dello script (come richiesto).

Lo script e' stato testato con il Perl 5.004 in ambiente Linux.

- 30 Settembre 1998 -


Si ringraziano i volenterosi studenti Alessandro Cagnetti e Daniele Giabbai