1. (punti: -1.5, 4)

L'organizzazione del sistema operativo basato sul modello orientato alle procedure:

1. include fra le sue caratteristiche la modularita', dalla quale non deriva una completa separazione delle politiche di gestione delle risorse dai meccanismi;
2. include fra le sue caratteristiche la modularita', dalla quale deriva una completa separazione delle politiche di gestione delle risorse dai meccanismi;
3. non include fra le sue caratteristiche la modularita', dalla quale deriva una completa separazione delle politiche di gestione delle risorse dai meccanismi;
4. non include fra le sue caratteristiche la modularita', dalla quale non deriva una completa separazione delle politiche di gestione delle risorse dai meccanismi;
5. prevede la trasformazione della macchina fisica in un insieme di macchine astratte utilizzabili indipendentemente da diversi utenti;
6. nessuna delle affermazioni precedenti e' corretta.

Il costrutto di sincronizzazione chiamato monitor:

1. consiste di una variabile intera, una coda di descrittori di processo e di un insieme di procedure interne e garantisce la mutua esclusione fra l'esecuzione delle procedure interne;
2. consiste di una variabile intera, una coda di descrittori di processo e di un insieme di procedure interne e non garantisce la mutua esclusione fra l'esecuzione delle procedure interne;
3. consiste di un insieme di variabili permanenti, di un insieme di procedure interne e di un programma di inizializzazione e non garantisce la mutua esclusione fra l'esecuzione delle procedure interne;
4. consiste di un insieme di variabili permanenti, di un insieme di procedure interne e di un programma di inizializzazione e garantisce la mutua esclusione fra l'esecuzione delle procedure interne;
5. non rilascia la mutua esclusione se un processo si sospende su una variabile di tipo condizione;
6. rilascia la mutua esclusione se un processo si sospende su una variabile di tipo condizione;
7. nessuna delle affermazioni precedenti e' corretta.

La primitiva hP (hardware P):

1. utilizza un semaforo ed e' invocata dal processo esterno che rappresenta un dispositivo fisico quando la corrispondente interruzione e' riconosciuta dal sistema di interruzione;
2. utilizza un semaforo e non e' invocata dal processo esterno che rappresenta un dispositivo fisico quando la corrispondente interruzione e' riconosciuta dal sistema di interruzione;
3. utilizza un semaforo ed e' invocata dal processo di controllo associato ad un dispositivo fisico con il meccanismo basato sull'istruzione TRAP;
4. utilizza un semaforo ed e' invocata dal processo di controllo associato ad un dispositivo fisico quando la corrispondente interruzione e' riconosciuta dal sistema di interruzione;
5. non utilizza un semaforo ed e' invocata dal processo esterno che rappresenta un dispositivo fisico quando la corrispondente interruzione e' riconosciuta dal sistema di interruzione;
6. non utilizza un semaforo ed e' invocata dal processo di controllo associato ad un dispositivo fisico con il meccanismo basato sull'istruzione TRAP;
7. non utilizza un semaforo ed e' invocata dal processo di controllo associato ad un dispositivo fisico quando la corrispondente interruzione e' riconosciuta dal sistema di interruzione;
8. nessuna delle affermazioni precedenti e' corretta.

Un file system F_j e' montato su un direttorio D_i del file system F_i del sistema Unix:

1. e' necessario che il direttorio D_i sia vuoto: in tal caso i cammini che attraversano D_i identificano esclusivamente archivi che appartengono ad F_j;
2. non e' necessario che D_i sia vuoto: in tal caso i cammini che attraversano D_i identificano esclusivamente archivi che appartengono ad F_j, l'originale contenuto di D_i non torna ad essere accessibile se il file system F_j viene smontato;
3. non e' necessario che D_i sia vuoto: in tal caso i cammini che attraversano D_i identificano esclusivamente archivi che appartengono ad F_j, l'originale contenuto di D_i torna ad essere accessibile se il file system F_j viene smontato;
4. non e' necessario che D_i sia vuoto: in tal caso i cammini che attraversano D_i non identificano esclusivamente archivi che appartengono ad F_j, l'originale contenuto di D_i torna ad essere accessibile se il file system F_j viene smontato;
5. non e' necessario che D_i sia vuoto: in tal caso i cammini che attraversano D_i non identificano esclusivamente archivi che appartengono ad F_j, l'originale contenuto di D_i non torna ad essere accessibile se il file system F_j viene smontato;
6. nessuna delle affermazioni precedenti e' corretta.

5. (punti: -0.5, 5.4)

Un processo del sistema Unix chiude l'archivio /users/studenti/file1 che a suo tempo era stato regolarmente aperto. 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).
 

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 P₁, P₂, P₃, P₄, P₅ con i seguenti tempi di arrivo e tempi di esecuzione in millisecondi:
 

Processo	Tempo di arrivo	Tempo di esecuzione
P1	0	16
P2	4	4
P3	9	6
P4	11	7
P5	7	8

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 = 1 0 3 5 6 1 9 19 5 18 9 15 1 3 5 1 6 19 9 3

1. (punti: 4) 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: 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)

Lungo una strada a due corsie e doppio senso di marcia, che procede in direzione nord-sud, vi e' un ponte ad una sola corsia, percorribile a senso unico alternato. Il ponte ha la capacita' di n automobili. Le automobili dirette verso nord (verso sud) possono attraversare il ponte solo se non e' attraversato da nessuna automobile diretta verso sud (verso nord). Scrivere il programma dei due generici processi "automobile diretta verso nord" e "automobile diretta verso sud" utilizzando il meccanismo dei semafori. Discutere le proprieta' della soluzione proposta (assenza di stallo, starvation, ecc.).
 
 

9. (punti: 6)

La funzione "contextGrep" visualizza insieme ad ogni linea trovata dall'operazione di grep anche la linea precedente e quella successiva. Scrivere un Perl script che esegue tale funzione in tempo lineare e spazio costante.

1. b
2. d,f
3. f
4. c

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	P2	P2	P5	P3	P3	P5	P4	P1
0-4	4-7	7-8	8-9	9-11	11-15	15-22	22-29	29-41

7.

(a) Algoritmo Second Chance (pag 473 del Maestrini):
 

TurnoMS

  TurnoMS e' inizializzato a 4.
 

	1	0	3	5	6	1	9	19	5	18	9	15	1	3	5	1	6	19	9	3
0	11	11	11	11	11	11	91	91	91	91	91	91	90	31	31	31	31	31	30	31
1		01	01	01	01	01	00	191	191	191	191	191	190	190	51	51	51	51	50	50
2			31	31	31	31	30	30	30	181	181	181	180	180	180	180	61	61	60	60
3				51	51	51	50	50	51	51	51	50	11	11	11	11	11	10	91	91
4					61	61	60	60	60	60	60	151	151	150	150	150	150	191	191	191
	P	P	P	P	P		P	P		P		P	P	P	P		P	P	P

  Numero di page fault: 5+10

(b) Algoritmo ottimo:
 

Pagina riferita

	1	0	3	5	6	1	9	19	5	18	9	15	1	3	5	1	6	19	9	3
0	1	1	1	1	1	1	1	1	1	1	1	1	1	1	1	1	6	19	19	19
1		0	0	0	0	0	9	9	9	9	9	9	9	9	9	9	9	9	9	9
2			3	3	3	3	3	3	3	3	3	3	3	3	3	3	3	3	3	3
3				5	5	5	5	5	5	5	5	5	5	5	5	5	5	5	5	5
4					6	6	6	19	19	18	18	15	15	15	15	15	15	15	15	15
	P	P	P	P	P		P	P		P		P					P	P

 Numero di page fault: 5+6

8.

Occorre: 1) implementare due liste di "attesa", una per le automobili provenineti da nord e l'altra per le automobili provenienti da sud, ed implementarle sfruttando i semafori privati (ciascuna automobile deve essere dotata di semaforo privato); 2) realizzare la mutua esclusione per l'accesso alle variabili che governano il ponte e le liste di "attesa". Il tutto con queste modalita':

• ciascuna nuova macchina che arriva in prossimita' del ponte deve controllare tre condizioni: 1) se ci sono macchine che stanno attraversando il ponte nell'altro verso; 2) se ci sono n automobili provenienti dallo stesso verso che stanno gia' attraversando il ponte; 3) se ci sono automobili che stanno attraversando il ponte nello stesso verso e ci sono altre automobili che sono in attesa dall'altra parte del ponte. In tutti e tre i casi l'automobile deve sostare "addormentandosi" su un semaforo privato.
• Quando un'automobile A_i sta attraversando il ponte, all'uscita da questo deve controllare se e' l'ultima: in tal caso ci sono automobili in attesa alla fine di questo allora si "risveglia" una di queste (una di quelle che lo dovra' attraversare in verso contrario), per evitare l'attesa indefinita, altrimenti se ne sveglia un'altra proveniente dallo stesso verso. Altrimenti, se A_i non e' l'ultima automobile ad uscire dal ponte, si deve controllare che non ci siano automobili in attesa alla fine del ponte, nel qual caso si devono risvegliare k=n-r automobili provenienti dallo stesso verso (essendo n=la portata del ponte, r=il numero di auto rimanenti sul ponte una volta che A_i ne e' uscita).

#define boolean int
#define false 0
#define true !false

boolean SulPonteDaSud=false;
int AutomobiliSulPonte=0;

/******************
 DA NORD
 ******************/
void AccessoAutomobiliProvenientiDaNord()
   {
   int i;
   
   i=DeterminaProprioIndice();
   P(mutex); /* Ottiene la mutua esclusione */
   if ( SulPonteDaSud || !Vuota(ListaAttesaDaSud) || AutomobiliSulPonte==N )
      {
      Push(ListaAttesaDaNord,i); /* l'automobile va messa in lista d'attesa */
      }
   else
      {
      SulPonteDaNord=true;
      AutomobiliSulPonte++;
      PrivV(i); /* Questa chiamata elide la PrivP: NON vogliamo che "l'automobile" si addormenti ... zzz */
      }
   V(mutex); /* Rilascia la mutua esclusione */
   PrivP; /* Addormenta "l'automobile" (il processo)? Si se una delle condizioni qui sopra e' verificata */
   }

/******************/
void UscitaAutomobiliProvenientiDaNord()   
   {   
   int j;   

   P(mutex); /* Ottiene la mutua esclusione */   
   AutomobiliSulPonte--;
   if (AutomobiliSulPonte==0) /* se e' l'ultima automobile... */
      {
      /* ...allora si deve controllare che ce non ne siano dall'altra parte */
      if ( Vuota(ListaAttesaDaSud) )
         {
         /* "sveglia" al piu' N automobili in attesa da nord */
         while ( !Vuota(ListaAttesaDaNord) && AutomobiliSulPonte<N )
            {
            AutomobiliSulPonte++;
            j=Pop(ListaAttesaDaNord);
            PrivV(j);
            }
         }
      else
         {
         /* "sveglia" al piu' N automobili in attesa da sud */   
        SulPonteDaNord=false;
         SulPonteDaSud=true;   
      while ( !Vuota(ListaAttesaDaSud) && AutomobiliSulPonte<N )   
         {   
         AutomobiliSulPonte++;   
         j=Pop(ListaAttesaDaSud);   
         PrivV(j);   
         }
         }
      }
   else
      {
      if ( Vuota(ListaAttesaDaSud) && !Vuota(ListaAttesaDaNord) )
         {
           AutomobiliSulPonte++;
           j=Pop(ListaAttesaDaNord);
           PrivV(j);
         }
      else
         {   
        SulPonteDaNord=false;
         }
      }
   V(mutex); /* Rilascia la mutua esclusione */   
   }

/******************
 DA SUD
 ******************/
void AccessoAutomobiliProvenientiDaSud()
   {
   int i;
   
   i=DeterminaProprioIndice();
   P(mutex); /* Ottiene la mutua esclusione */
   if ( SulPonteDaNord || !Vuota(ListaAttesaDaNord) || AutomobiliSulPonte==N )
      {
      Push(ListaAttesaDaSud,i); /* l'automobile va messa in lista d'attesa */
      }
   else
      {
      SulPonteDaSud=true;
      AutomobiliSulPonte++;
      PrivV(i); /* Questa chiamata elide la PrivP: NON vogliamo che "l'automobile" si addormenti ... zzz */
      }
   V(mutex); /* Rilascia la mutua esclusione */
   PrivP; /* Addormenta "l'automobile" (il processo)? Si se una delle condizioni qui sopra e' verificata */
   }

/******************/
void UscitaAutomobiliProvenientiDaSud()   
   {   
   int j;   

   P(mutex); /* Ottiene la mutua esclusione */   
   AutomobiliSulPonte--;
   if (AutomobiliSulPonte==0) /* se e' l'ultima automobile... */
      {
      /* ...allora si deve controllare che ce non ne siano dall'altra parte */
      if ( Vuota(ListaAttesaDaNord) )
         {
         /* "sveglia" al piu' N automobili in attesa da sud */
         while ( !Vuota(ListaAttesaDaSud) && AutomobiliSulPonte<N )
            {
            AutomobiliSulPonte++;
            j=Pop(ListaAttesaDaSud);
            PrivV(j);
            }
         }
      else
         {
         /* "sveglia" al piu' N automobili in attesa da nord */   
        SulPonteDaSud=false;
         SulPonteDaNord=true;   
      while ( !Vuota(ListaAttesaDaNord) && AutomobiliSulPonte<N )   
         {   
         AutomobiliSulPonte++;   
         j=Pop(ListaAttesaDaNord);   
         PrivV(j);   
         }
         }
      }
   else
      {
      if ( Vuota(ListaAttesaDaNord) && !Vuota(ListaAttesaDaSud) )
         {
           AutomobiliSulPonte++;
           j=Pop(ListaAttesaDaSud);
           PrivV(j);
         }
      else
         {   
        SulPonteDaSud=false;
         }
      }
   V(mutex); /* Rilascia la mutua esclusione */   
   }

9.

#!/usr/bin/perl
die "Errore tra i parametri." if (scalar @ARGV != 2);
$StampaRigaSuccessiva = 0; 
$RigaPrecedente = ""; 
$Pattern = $ARGV[0]; 
open(FILEIN, $ARGV[1]) || die $!;
while (<FILEIN>)
   { 
   if ($StampaRigaSuccessiva)
      {
      print $_; 
      $StampaRigaSuccessiva = 0;
      }
   if (/$Pattern/o) 
      {
      print $RigaPrecedente, $_; 
      $StampaRigaSuccessiva = 1; 
      }
   $RigaPrecedente = $_;
   }

Si ringraziano i volenterosi studenti Alessandro Cagnetti, Daniele Giabbai, Mauro Sozio e Ivo (?).