-

Compito di Sistemi Operativi, Prof. Mancini - 2 luglio 1998

1. (punti: -1,4)

Il tempo di permanenza di un lavoro (job) e' definito come il tempo che intercorre fra l'immissione di un lavoro in un archivio di ingresso e la stampa dell'archivio di uscita prodotto con l'esecuzione. In un sistema multiprogrammato:

  1. 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;
  2. la migliore utilizzazione del processore 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' maggiore di quello che risulterebbe in un sistema uniprogrammato;
  3. 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;
  4. 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;
  5. piu' attivita' vengono eseguite concorrentemente, una sola di esse svolge un servizio di stretta pertinenza dell'utente;
  6. piu' attivita' vengono eseguite concorrentemente, piu' d'una di esse puo' svolgere un servizio di stretta pertinenza dell'utente;
  7. nessuna delle affermazioni precedenti e' corretta.
2. (punti: -1,4)

La primitiva hV (hardware V):

  1. e' il processo con il quale e' vincolato ad interagire un dispositivo;
  2. e' il processo che gestisce le interruzioni generate da un dato dispositivo fisico;
  3. e' invocata dal processo di controllo associato ad un dispositivo fisico con il meccanismo basato sull'istruzione TRAP;
  4. e' invocata dal processo di controllo associato ad un dispositivo fisico quando la corrispondente interruzione e' riconosciuta dal sistema di interruzione;
  5. e' invocata dal processo esterno che rappresenta un dispositivo fisico ed e' eseguita sul processore quando la corrispondente interruzione e' riconosciuta dal sistema di interruzione;
  6. e' invocata dal processo esterno che rappresenta un dispositivo fisico ed e' eseguita sul processore con il meccanismo basato sull'istruzione TRAP;
  7. nessuna delle affermazioni precedenti e' corretta.
3. (punti: -1,4)

Un processo P richiede una risorsa che non puo' essere immediatamente assegnata, la richiesta di P rimane pendente:

  1. il fenomeno dell'attesa indefinita e' tipico delle politiche di gestione basate su priorita' statica, infatti prima che possa essere soddisfatta la richiesta di P, potrebbero continuare a pervenire altre richieste con priorita' maggiore;
  2. il fenomeno dell'attesa indefinita e' evitato dalle politiche di gestione basate su priorita' statica, infatti prima che possa essere soddisfatta la richiesta di P, non possono pervenire altre richieste con priorita' maggiore;
  3. il fenomeno dell'attesa indefinita e' tipico delle politiche di gestione basate su priorita' dinamica, infatti prima che possa essere soddisfatta la richiesta di P, potrebbero incrementare progressivamente le priorita' degli altri processi;
  4. il fenomeno dell'attesa indefinita e' evitato dalle politiche di gestione basate su priorita' assegnate a tempo di compilazione, infatti prima che possa essere soddisfatta la richiesta di P, non vengono compilati processi che generano richieste con priorita' maggiore;
  5. il fenomeno dell'attesa indefinita puo' essere evitato utilizzando la politica di gestione delle richieste FIFO;
  6. il fenomeno dell'attesa indefinita non puo' essere evitato utilizzando la politica di gestione delle richieste FIFO;
  7. il fenomeno dell'attesa indefinita puo' essere evitato utilizzando il meccanismo dei semafori;
  8. il fenomeno dell'attesa indefinita non puo' essere evitato utilizzando il meccanismo dei semafori;
  9. nessuna delle affermazioni precedenti e' corretta.
4. (punti: -1,4)

L'insieme di lavoro (working set) WS(t,d ) di un processo P al tempo virtuale t e' definito come:

  1. l'insieme delle pagine fisiche di memoria virtuale accessibili da P al tempo t;
  2. l'insieme delle pagine dell'intera memoria virtuale marcate come riferite all'istante t ma non accedute da P;
  3. l'insieme delle pagine fisiche di memoria virtuale staticamente allocate al sistema operativo;
  4. l'insieme delle pagine riferite da P nell'intervallo (t-d , t];
  5. l'insieme delle pagine riferite da P nell'intervallo (t, t+d ];
  6. l'insieme delle pagine vittime che sono state rimosse nell'intervallo (t-d , t];
  7. l'insieme delle pagine vittime che sono state rimosse nell'intervallo (t, t+d ];
  8. nessuna delle affermazioni precedenti e' corretta.
5. (punti: 6)

Illustrare in al piu' 60 parole il costrutto monitor.

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

a (punti: 4)

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

b (punti: 2)

Calcolare il valor medio del tempo di attesa dei processi.

c (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 = 3 6 1 9 3 1 0 5 3 4 6 1 5 4 1 3 9 1 6 3

a (punti: 3)

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.

b (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)

Utilizzare le primitive P e V definite sui semafori per risolvere il problema dei filosofi a cena evitando lo stallo. In particolare realizzare il ProtocolloPerMangiare ed il ProtocolloPerPensare.

9. (punti: 8)

Estendere il comando grep di Unix realizzando un Perl script efficiente che puo' ricevere dalla linea di comando anche l'opzione -l, un pattern ed una sequenza di file. Nel caso in cui venga specificata l'opzione -l il comando restituisce in STOUT i nomi dei file che contengono pattern piuttosto che le linee di file che contengono il pattern passato come argomento. Si minimizzi il numero di test condizionali nel ciclo principale del programma.
 
 

Risultati della prova

1. b,f
2. e
3. a,e
4. d

5.

Il monitor consiste in un insieme di variabili permanenti, che sono le componenti del dato comune condiviso tra i processi, di un insieme di procedure interne che realizzano le operazioni ammissibili su dato comune, e di un programma d’inizializzazione. L’esecuzione delle procedure interne avviene in mutua esclusione. (Maestrini p.285, 47 parole)

6.

a) Algoritmo Round Robin con quanto = 3 millisecondi:
 
P1
P1
P5
P1
P2
P5
P3
P1
P2
P4
P5
P3
P1
P2
P4
P3
P2
0-3
3-6
6-9
9-12
12-15
15-18
18-21
21-24
24-27
27-30
30-31
31-34
34-36
36-39
39-42
42-43
43-44

b) media tempo di attesa dei processi: 112/5
c) throughput medio: 5/44

7.

  1. Algoritmo Ottimo:
 
Pagina riferita
 
3
6
1
9
3
1
0
5
3
4
6
1
5
4
1
3
9
1
6
3
0
3
3
3
3
3
3
3
3
3
3
3
3
3
3
3
3
3
3
3
3
1
  
6
6
6
6
6
6
6
6
6
6
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
      
9
9
9
9
9
9
4
4
4
4
4
4
4
9
9
9
9
4
            
0
5
5
5
5
5
5
5
5
5
5
5
5
5
 
p
p
p
p
    
p
p
  
p
            
p
      

Numero di page fault: 5+3

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

Numero di page fault: 5+6

8. Si veda Maestrini Tab. 6.12, p. 273 

#include "prototypes.h"
#define N 5
#define SINISTRA (i-1)%N
#define DESTRA (i+1)%N
#define PENSA 0
#define AFFAMATO 1
#define MANGIA 2
typedef int semaphore;
int stato[N];
semaphore mutex = 1;   /* mutua esclusione */
semaphore filosofi[N]; /* Un semaforo per filosofo */

void filosofo(int i)
{
        while(true)                     /* un filosofo fa solo questo.. */
        {
                pensa();                /* non pensare troppo.. */
                prendi_forchette(i);    /* allora hai proprio fame! */
                mangia();               /* yum -yum spaghetti al pesto.. */
                posa_forchette(i);      /* era proprio tempo!*/
        }
}
 
void prendi_forchette(int i)
{
        P(&mutex);
        stato[i] = AFFAMATO;
        test(i);
        V(&mutex);
        P(&filosofo[i]);
}
 
void posa_forchette(int i)
{
        P(&mutex);
        stato[i] = PENSA;
        test(DESTRA(i));                        /* sveglia i vicini.. */
        test(SINISTRA(i));
        V(&mutex);
}

void test(int i)
{
        if (stato[i] == AFFAMATO && stato[SINISTRA[i]] != MANGIA && 
                stato[DESTRA[i]] != MANGIA)
        {
                stato[i] = MANGIA; /* ‘se magna’ */
                V(filosofo[i]);
        }
}

9. 

#!/usr/bin/perl
$Flag = shift @ARGV if ($ARGV[0]=='-l');
$Pattern = shift @ARGV;

foreach (@ARGV)
   {
   if ( defined $Flag )  # Qui stampa i nomi di file
      {
      while(<>)
         {
         if (/$Pattern/o)
             {
             print $ARGV; # parametro corrente
             last;
             }
         }
      }
   else   # Stampa le righe
      {
      while(<>)
         { 
         print $_ 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).

- 2 luglio 1998 -





Si ringraziano i volenterosi studenti Alessandro Cagnetti e Daniele Giabbai