Sistemi Operativi 1

Esame di Sistemi Operativi 1 : Luglio 2004
[Punti 33: D1(4) D2(3) D3(3) D4(3) D5(4) E1(6) E2(2) E3(3) E4(3) E5(2)]

D1: Scrivere in (pseudo) codice l'algoritmo di Peterson visto a lezione

D2: Descrivere il meccanismo dual mode di Unix.

D3:A cosa serve e come funziona la segmentazione con paginazione.

D4: Descrivere l'algoritmo del clock a due lancette per la gestione
della memoria virtuale in Unix.

(Vedi lucidi e testo per risposte)

D5: Descrivere e spiegare il significato dei seguenti attributi del file "prova":

                   drwxr-xr-x   root root    4096 May 21 2004 prova

Descrivere come cambiano gli attributi dopo l'esecuzione in sequenza di ognuno dei seguenti comandi:

1.    chgrp   collab prova
2.    chown rossi prova
3.    chmod 111 prova

Dopo l'esecuzione del comando 3 l'utente "bianchi" puo' leggere il file? E l'utente "root"?

Soluzione:

Attributi:

d=directory
owner=root
gruppo=root
root ha tutti i diritti (lettura, scrittura, accesso alla directory)
il gruppo root e gli altri utenti ha diritto di lettura ed accesso
4096=dimensione
May 21=data di ultima modifica

Comandi: Dopo 1+2+3:
d--x--x--x   rossi collab    4096 May 21 2004 prova

Bianchi non puo leggere la directoty. Root si (e' l'amministratore).

E1: Considerate il seguente programma:

semaphore M,S, T, U;
int x=0;

Processo P1
{
while (true) do

    begin
            down(&S);
            down(&M);
            x:=x+1;
            up(&M);
            up(&T);
      end;

enwhile;
}

Processo P2
{
while (true) do

     begin
            down(&T);
            down(&M);                        write(x);

up(&M);
up(&S);

end
enwhile;
}

Processo P3
{
down(&U);

while (true) do
   begin
        down(&M);
         x:=0;
        up(&M);
     end;
endwhile;

}

supponete che i processi vengano eseguiti concorrentemente sulla stessa CPU.

Qual’è l’output di tale programma se i semafori sono inizializzati come segue:

M=1 S=1 T=0 U=0
M=1 S=0 T=1 U=0
M=1 S=1 T=0 U=1

Soluzione:

1. Stampa la sequenza infinita dei numeri naturali a partire da 1: 1 2 3 4 ....

2. Stampa la sequenza infinita dei numeri naturali a partire da 0: 0 1 2 3 4 ....

3. P3 azzera x in modo non-deterministico durante l'esecuzione di P1 e P2

   Vengono stampate sequenze del tipo:

(0) 1 2 ..... n1 (0) 1 2 ... n2 (0) 1 2 ..... ecc

   dove ni >=0 (se ni=0 la sottosequenza corrispondente e' vuota)
   Ad es:
    0 0 0 ....
    1 1 1 ...
    0 1 2 0 1 2 3 .....
   ecc

Qual'e' il ruolo del semaforo M in tale programma?

Soluzione:
Garantisce mutua esclusione per l'accesso a x..

E2: Considerare un insieme di cinque processi con i seguenti tempi di arrivo ed esecuzione:

Proc.	Arrivo	Esecuzione
1	0	9
2	5	7
3	7	10
4	11	9
5	15	6

Assegnare questo insieme di processi ad un processore in base alla politica Round Robin
considerando un quanto di 4 unita' di tempo. Calcolare il valor medio del
tempo di attesa ed il valor medio del tempo di turnaround (completamento) dei processi.

Soluzione:

La sequenza dei processi schedulati e' 1 1 2 3 1 4 2 5 3 4 5 3 4
Tempo attesa: 1(8) 2(12) 3(23) 4(21) 5(17)
Tempo turnaround: 1(17) 2(19) 3(37) 4(41) 5(23)

E3: Considerate una memoria virtuale con 4 pagine logiche e la seguente sequenza di

valori per i corrispondenti reference bit dopo 4 tick del clock di sistema:

Clock Tick	Reference Bit
Clock Tick	Pag.1	Pag.2	Pag.3	Pag.4
1	1	0	0	0
2	0	0	1	0
3	0	1	0	1
4	1	0	1	1

Applicare l'algoritmo di aging per il rimpiazzamento di pagine considerando un array di
6 bit per pagina (inizialmente tutti a zero). Determinare la pagina candidata al
rimpiazzamento allo scadere del quarto tick del clock di sistema.

Soluzione:

--------> clock tlick -->
P1: 100000 010000 001000 100100
P2: 000000 000000 100000 010000
P3: 000000 100000 010000 101000
P4: 000000 000000 100000 110000

Viene selezionata la pagina 2

E4: Supponiamo che i descrittori di file contengano 3 puntatori di cui

1 puntatore diretto a blocchi, 1 puntatore indiretto e 1 puntatore doppiamente indiretto.
Se la dimensione di un blocco è 64 byte e un puntatore occupa 2 byte:

Qual è la dim. massima di un file in tale file system?

Soluzione:

1 blocco contiene 32 puntatori quindi
dim massima= (1+32+32*32)*64 byte

Quanti accessi in memoria sono necessari per acceder al byte numero 200 di un file?
E per accedere al byte numero 4000 di un file?

Soluzione: 2 acesssi per byte 200 (contando accesso al blocco di memoria che contiene il byte), 3 per 4000

E5: Dati i seguenti vettori prodotti dall'analisi dei blocchi di un file system tramite fsck

Indice Blocco	0	1	2	3	4	5	6	7	8	9	10	11	12	13	14	15
Vet. Bl. Liberi	1	1	1	1	1	1	0	1	0	0	1	3	1	0	1	0
Vet. Bl. Occupati	2	0	0	0	1	0	1	2	0	0	1	1	3	1	1	1

spiegare quali sono le azioni intraprese dalla funzione fsck per ripristinare uno stato consistente.

Soluzione (solo sequenza):

Indice Blocco	0	1	2	3	4	5	6	7	8	9	10	11	12	13	14	15
Vet. Bl. Liberi	0	1	1	1	0	1	0	0	0	0	0	0	0	0	0	0
Vet. Bl. Occupati	2	0	0	0	1	0	1	2	0	0	1	1	3	1	1	1

Indice Blocco	0	1	2	3	4	5	6	7	8	9	10	11	12	13	14	15
Vet. Bl. Liberi	0	1	1	1	0	1	0	0	1	1	0	0	0	0	0	0
Vet. Bl. Occupati	2	0	0	0	1	0	1	2	0	0	1	1	3	1	1	1

Indice Blocco	0	1	2	3	4	5	6	7	8	9	10	11	12	13	14	15
Vet. Bl. Liberi	0	0	0	0	0	0	0	0	1	1	0	0	0	0	0	0
Vet. Bl. Occupati	1	1	1	1	1	1	1	1	0	0	1	1	1	1	1	1