-
Compito di Sistemi Operativi, Prof. Mancini - 11 febbraio 1998

1
 
(punti: -1.5, 4) 

Nella realizzazione dei processi concorrenti: 
(a) l'immagine di un processo prelevata dai registri del processore è salvata nel campo "ImmagineNelProcessore" del descrittore del processo se e solo se un processo passa dallo stato di esecuzione a quello di attesa;
(b) non è vero che l'immagine di un processo prelevata dai registri del processore è salvata nel campo "ImmagineNelProcessore" del descrittore del processo se e solo se un processo passa dallo stato di esecuzione a quello di attesa;
(c) l'immagine di un processo prelevata dal campo "ImmagineNelProcessore" del descrittore del processo è ripristinata nei registri del processore se e solo se il processo passa dallo stato di pronto a quello di esecuzione;
(d) non è vero che l'immagine di un processo prelevata dal campo "ImmagineNelProcessore" del descrittore del processo è ripristinata nei registri del processore se e solo se il processo passa dallo stato di pronto a quello di esecuzione;
(e) il salvataggio e il ripristino non sono indispensabili affinchè, dopo essersi sospeso, il processo possa riprendere l'esecuzione del suo programma senza apparente discontinuità e senza alcuna perdita di informazione;
(f) nessuna delle affermazioni precedenti è corretta.
 

2
 
(punti: -1.5, 4) 

Le seguenti quattro condizioni (1) le risorse sono seriali, (2) le risorse sono non prerilasciabili, (3) le risorse sono gestite con richiesta bloccante, e (4) il sistema raggiunge uno stato di attesa circolare, sono collettivamente: 
(a) necessarie affinchè si verifichi lo stallo;
(b) sufficienti affinchè si verifichi lo stallo;
(c) necessarie e sufficienti affinchè si verifichi lo stallo;
(d) necessarie affinchè si verifichi l'attesa indefinita;
(e) sufficienti affinchè si verifichi l'attesa indefinita;
(f) necessarie e sufficienti affinchè si verifichi l'attesa indefinita;
(g) nessuna delle affermazioni precedenti è corretta.
 

3
 
(punti: -1.5, 4) 

L'organizzazione della memoria centrale con paginazione statica: 
(a) introduce una certa frammentazione interna, che è tanto più rilevante quanto più la lunghezza media dei programmi è grande rispetto all'ampiezza della pagina;
(b) introduce una certa frammentazione interna, che è tanto meno rilevante quanto più la lunghezza media dei programmi è grande rispetto all'ampiezza della pagina;
(c) introduce una certa frammentazione esterna, che è tanto meno rilevante quanto più la lunghezza media dei programmi è grande rispetto all'ampiezza della pagina;
(d) introduce una certa frammentazione esterna, che è tanto più rilevante quanto più la lunghezza media dei programmi è grande rispetto all'ampiezza della pagina;
(e) elimina la frammentazione esterna e rimuove il vincolo della contiguità dello spazio fisico in memoria centrale;
(f) elimina la frammentazione esterna ma mantiene il vincolo della contiguità dello spazio fisico in memoria centrale;
(g) nessuna delle affermazioni precedenti è corretta.
 

4
 
(punti: -1.5, 4) 

Una struttura dati "i-node" del sistema di archiviazione di Unix è associata ad un archivio F. Il campo "link" (collegamenti) di questo i-node contiene: 
(a) il puntatore alla posizione corrente dell'archivio F;
(b) un contatore che registra la cardinalità dell'insieme di processi che stanno utilizzando l'archivio F;
(c) un contatore che registra la cardinalità dell'insieme dei direttori dai quali è possibile accedere all'archivio F;
(d) un contatore che registra la cardinalità dell'insieme di elementi nella "tabella dei collegamenti" che riferiscono l'i-node dell'archivio F;
(e) un contatore che registra la cardinalità del gruppo di utenti del quale fa parte il proprietario dell'archivio F;
(f) il modo con il quale l'archivio F è stato aperto;
(g) nessuna delle affermazioni precedenti è corretta.
 

5
 
(punti: -0.5, 5.4) 

Sono nella shell del sistema Unix ed eseguo il comando: 
cp /users/studenti/file1 /users/studenti/file2.
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 
P2 
P3 
P4 
P5




11
15 



7
(a) (punti: 4) 
Assegnare questo insieme di processi ad un processore in base alla politica Shortest Job First con prerilascio;
(b) (punti: 2) 
Calcolare il valor medio del tempo di attesa dei processi.
(c) (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 = 3 6 0 9 3 1 0 5 9 1 4 2 0 3 6 2 4 1 5 9 
(a) (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.
(b) (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.
 
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 contine stringa anche le k linee precedenti.


 
 
Risposte Compito di Sistemi Operativi,  11 febbraio 1998 - Prof. Mancini

1
 
(b), (c)
2
 
(a), (b), (c)
3
 
(b), (e)
4
 
(g)
5
 
(a  ), (b  ), (c M), (d M), (e I), (f I), (g I), (h I), (i  )
6
 
(a)
Processi nel processore
 
P1
 
P3
 
P3
 
P2
 
P2
 
P5
 
P4
 
P1
 
Tempi in m.sec 0 4 7 9 11 15 22 31 42
 
(b) Tempo medio di attesa = ((42-15)+(15-6-9)+(9-5-4)+(31-9-7)+(22-7-11))/5 = 46/5
(c) Tempo medio di turnaround = (42+(15-9)+(9-4)+(31-7)+(22-11))/5 = 88/5
 
7
 
(a) 5+9 page fault 
3 6 0 9 3 1 0 5 9 1 4 2 0 3 6 2 4 1 5 9
3 3 3 3 3 3 3 3 3 3 4 4 4 4 4 4 4 4 4 4
6 6 6 6 6 6 5 5 5 5 5 0 0 0 0 0 1 1 1
0 0 0 0 0 0 0 0 0 2 2 2 2 2 2 2 2 2
9 9 9 9 9 9 9 9 9 9 3 3 3 3 3 5 5
1 1 1 1 1 1 1 1 1 6 6 6 6 6 9
 
(b) 5+9 page fault 
3 6 0 9 3 1 0 5 9 1 4 2 0 3 6 2 4 1 5 9
31 31 31 31 31 31 31 51 51 51 51 51 50 50 61 61 61 60 60 60
61 61 61 61 61 61 60 60 60 41 41 40 40 40 40 41 11 11 11
01 01 01 01 01 00 00 00 00 21 20 20 20 21 21 20 51 51
91 91 91 91 90 91 91 91 91 01 01 01 01 01 00 00 91
11 11 10 10 11 11 11 10 31 31 31 31 30 30 30
 
 
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 (si veda Maestrini tabella 5.16, p.195). 

type TipoMessaggio = ..........;
resource comunicazione
    BufferComunicazione: array[IndiceDiProcesso] of TipoMessaggio;
    AttesaComunicazione: array[IndiceDiProcesso, IndiceDiProcesso] of boolean;
end;

procedure send (messaggio: TipoMessaggio; destinatario: IndiceDiProcesso);
var AttesaComunicazione, BufferComunicazione: shared;
i: IndiceDiProcesso;
begin
    i:= DeterminazioneDelProprioIndice;
    if destinatario <> i then
        begin
            P(MutexComunicazione);
           if AttesaComunicazione[i, destinatario] then
               begin
                    BufferComunicazione[destinatario]:= messaggio;
                    AttesaComunicazione[i, destinatario]:= false;
                    PrivV(destinatario);
                    PrivV(i);
               end
           else
               begin
                    BufferComunicazione[i]:= messaggio;
                    AttesaComunicazione[i, destinatario]:= true;
               end
            V(MutexComunicazione);
            PrivP;
        end
end;

procedure receive (var mess: TipoMessaggio; mittente: IndiceDiProcesso);
var AttesaComunicazione, BufferComunicazione: shared;
j: IndiceDiProcesso;
begin
    j:= DeterminazioneDelProprioIndice;
    if mittente <> j then
        begin
            P(MutexComunicazione);
           if AttesaComunicazione[mittente, j] then
               begin
                    AttesaComunicazione[mittente, j]:= false;
                    BufferComunicazione[j]:= BufferComunicazione[mittente];
                    PrivV(mittente);
                    PrivV(j);
               end
           else
               begin
                    AttesaComunicazione[mittente, j]:= true;
               end
            V(MutexComunicazione);
            PrivP;
            mess:= BufferComunicazione[j];
       end
end

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. 

#!/usr/bin/perl -w
($cerca, $k, $file) = ($ARGV[0], $ARGV[1], $ARGV[2]);
for $h (0..$k) {
    $buff [$h] = "";
}
$i = -1;
open (FILEIN, "$file") || die "Errore di apertura file: $!";
while (<FILEIN>) {
    $i++;
    $i = ($i % $k);
    $buff[$i] = $_;
    if ($_ =~ /$cerca/) {
        print "Match trovato: $_";
        for $h (($i+1)..($k-1)) {
            print "$buff[$h]";
        }
        for $h (0..$i) {
            print "$buff[$h]";
        }
    }
}
close FILEIN;


  - 11 febbraio 1998 -

Si ringrazia lo studente Ivo Damato.