Esame di Sistemi Operativi 1 : 12 Febbraio 2004

Testo e soluzioni
  1. Tipo A
  2. Tipo B


TIPO A

Domanda 1
Descrivere il metodo di gestione della memoria chiamato segmentazione e l'architettura di base per
la sua gestione.

Risposta:
Suddivisione in "segmenti" di dimensione variabile della memoria principale....
Gestione con tabella dei segmenti (inizio, limite), ....indirizzi con segmento, offset nel segmento...ecc

Domanda 2
Si definiscano i seguenti tre termini:  Race condition,  Starvation,   e Deadlock.
Risposta:
Vedi libro/lucidi

Domanda 3
Descrivere le differenze tra sistemi operativi monolitici, a strati (layered),  e a microkernel. 
Risposta:
Vedi lucidi

Domanda 4
Descrivere e spiegare il significato degli attributi del file "pluto" risultato del comando "ls" -al:

 -rw-r--r-x    giorgio  collab          41139 Feb 11 11:20 pluto

Qual e' l'effetto del comando "chmod 624 pluto"?

Risposta:
  -rw-r--r-x: permessi del file: rw- (lettura/scrittura) per owner (giorgio), r-- (lettura) per gruppo, r-x (lettura esecuzione) per altri utenti
  giorgio: owner
  collab: gruppo
  41139: dimensione
  Feb 11 11:20 data ora di ult, modifica
  pluto: nome

chmod 624 pluto:

  -rw--w-r--    giorgio  collab   41139  ....  pluto


Domanda 5
Descrivere la tecnica di allocazione indicizzata dei file, illustrandone vantaggi e svantaggi in termini di
efficienza nell'accesso al file e  di riduzione della frammentazione.

Risposta:
Vedi lucidi

Esercizio 1
Considerate i seguenti  processi

Risorse condivise
  semaphore  S=1, M=1;
  int x=10;
Processo P1
{
    down(&M);
    x:=x+1;
    up(&M);  

   down(&M);
   write(x);
    up(&M);

   up(&S);

}
 Processo P2
{
    down(&S);
 
    down(&M);
    x:=x-1;
    up(&M);
 
    down(&M);
   write(x);
    up(&M);
}

supponete che i processi vengano eseguiti concorrentemente sulla stessa CPU.

  1. Individuate le regioni critiche nel codice di P1 e P2.
    Si possono verificare race conditions per la variabile condivisa x?

  2. Determinare tutti i possibili output di tale programma concorrente (P1 in parallelo con P2).

  3. Supponiamo di inizializzare il semaforo  S a 0 invece che a 1.
    Determinare tutti i possibili output del programma (P1 in parallelo con P2) modificato.

Soluzione
  1. Regioni critiche:
    1. R1: x:=x+1;
    2. R2: write(x);
    3. R3: x:=x-1,
    4. R4: write(x) 

  2. Le regioni critiche sono protette da semafori per cui non vi sono race conditions su x.

  3. Il semaforo S non influisce sul flusso di esecuzione e quindi l'output dipende dall'ordine di esecuzione
    di R1-R2 e R3-R4:
    1. Prima R1,R3 (in qualsiasi ordine) e poi R2,R4 (in qualsiasi ordine)--> stampa: 10 10
    2. R1 R2 R3 R4 --> stampa: 11 10
    3. R3 R4 R1 R2 --> stampa:  9  10

  4. Il semaforo forza l'ordine di esecuzione P1 -> P2 e quindi ci sara' un solo output: 11 10


Esercizio 2
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

9

P2

3

17

P3

7

10

P4

11

9

P5

15

6

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


Soluzione 

P1

P2

P1

P3

P2

P4

P1

P5

P3

P2

P4

P5

P3

P2

P4

P2

0-4

4-8

8-12

12-16

16-20

20-24

24-25

25-29

29-33

33-37

37-41

41-43

43-45

45-49

49-50

50-51

Nota: Quando arriva P3 P1 e' gia in coda! Quindi allo scadere del II quanto viene schedulato di nuovo
P1 (la strategia di base  e' sempre FIFO) e cosi via....
  1. Tempo di attesa=Tempo di completamento-Tempo di esecuzione
    Media tempo di attesa dei processi: ((25-0-9)+(51-3-17)+(45-7-10)+(50-11-9)+(43-15-6) = 127/5

  2. Tempo di completamento= Istante di completamento - Tempo di arrivo
    Valore medio del tempo di turnaround dei processi: (25+(51-3)+(45-7)+(50-11)+(43-15))/5 = 178/5

Esercizio 3
Considerare la seguente stringa di riferimenti alla memoria di un processo in un sistema con memoria virtuale

S = 10 6 2 4 6 8 3 1 4 5 11 8 7 6 10 9 7 8 11 2

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.


Soluzione
Rif.
 10
 6
 2
 4
 6
 8
 3
 1
 4
 5
 11
 8
 7
 6
 10
 9
 7
 8
 11
 2
1
 10
 10
 10
 10
 10
 10
 3
 3
 3
 3
 3
 8
 8
 8
 8
 8
 8
 8
 8
 8
2
6
 6
 6
 6
 6
 6
 6
 6
 5
 5
 5
 5
 5
 10
 10
 10
 10
 10
 2
3

2
 2
 2
 2
 2
 1
 1
 1
 1
 1
 7
 7
 7
 7
 7
 7
 7
 7
4


4
 4
 4
 4
 4
 4
 4
 4
 4
 4
 6
 6
 6
 6
 6
 11
 11
5




8
 8
 8
 8
 8
 11
 11
 11
 11
 11
 9
 9
 9
 9
 9
Page Fault
 *
 *
 *
 *
*
 *
 *
*
 *
 *
 *
 *
 *
 *

*
 *

In neretto: pagina selezionata
Numero di page fault: 16

Esercizio 4
Data una memoria partizionata in maniera fissa come segue:
Partizione
 Dimensione
0 200K
1
 500K
2
 300K
3
 600K

e dato che il sistema operativo deve allocare quattro processi P1 di 212K, P2 di 417K, P3 di 112K e P4 di 427K
(in quest'ordine),  scrivere in quale partizione  il sistema alloca ciascun processo se viene usato l'algoritmo:
  1. First Fit
  2. Best Fit
  3. Worst Fit
(se il processo non puo' essere allocato, segnare "X" come partizione).

Soluzione
Nota: le partizioni sono fisse: non si possono mettere due processi nella stessa partizione!
  1. First fit: P1:1, P2: 3, P3:0, P4:X
  2. Best fit:  P1:2, P2: 1, P3:0, P4:3
  3. Worst fit: P1:3, P2:1, P3:2, P4:X

Esercizio 5
Considerare un file system dove la dimensione di un blocco logico e' 2KB e con indirizzi di blocchi a 16 bit.
  1. Determinare la dimensione massima di un file in caso di
    1. allocazione concatenata
    2. allocazione indicizzata con due livelli di blocco indice

  2. Determinare il numero di blocchi effettivamente assegnati ad un file di 200KB per i due tipi di allocazione.
Soluzione
Indirizzi a 16 bit --> 216 blocchi fisici
  1. Dim. massima
    1. Allocazione concatenata: ogni blocco ha 2KB-2B=2046 Byte di spazio dati quindi il file piu grande ha dimensione 216 * 2046 Byte
    2. Allocazione indicizzata: ogni blocco puo contenere 2048/2=1024 puntatori, quindi con due livelli: (1024)2*2 K (senza considerare spazio per la tabella)

  2. Numero blocchi
    1.  Dim file/Spazio in un blocco = 200 KB/2046 = 101 blocchi
    2.  100 blocchi


  TIPO B


Domanda 1
Cos'e', come viene usata e come puo' essere  implementata l'istruzione Test & Set?
Risposta:
Istruzione che testa e imposta il valore di una variabile/registro in modo atomico...
Utilizzata per implementare ad es. spinlock....(esempio)
Implementata o a livello hardware o software se si hannp costrutti "atomici"...

Domanda 2
Si descrivano brevemente caratteristiche e differenze di job, processi, thread e fibre in Windows 2000.

Risposta:
In Windows 2000: job = collezione di processi, ....

Domanda 3
Descrivere due diverse strategie per la gestione dei "nomi" dei file in una directory.

Risposta:
I record di una directory possono avere dimensione fissa o variabile.
Nel primo caso se i nomi hanno lunghezza variabile si puo fissare la dim. max utlizzare
un puntatore ad uno heap che mantiene l'insieme dei nomi separati da un carattere speciale....

 Domanda 4
Descrivere e spiegare il significato degli attributi del file "esempio" risultato del comando "ls" -al:

drwxr-x--x     giorgio  collab       4096 Feb 11 11:20 esempio

Qual e' l'effetto del comando "chmod 523 esempio"?
Risposta:
  d: il file e' una directory (x= permesso di entrare nella dir.)
  rwxr-x--x : permessi del file: rwx (lettura/scrittura/entrare) per owner (giorgio), r-x (lettura/entrare) per gruppo, --x (entrare) per altri utenti
  giorgio: owner
  collab: gruppo
  4096: dimensione directory
  Feb 11 11:20 data ora di ult, modifica
  esempio: nome

chmod 523 pluto:

  -r-x-w--wx    giorgio  collab   4096  ....  esempio

Domanda 5
Descrivere la struttura della MFT e il contenuto di un suo record.
In quel formato vengono memorizzate le informazioni sui blocchi di dati per un file con le seguenti
caratteristiche:  7 blocchi con indirizzi fisici  10,11,21,22,23,45,46.

Risposta:
MFT/MFT record  ... vedi lucidi
Blocchi:   0:7 - 10:2 - 21:3 - 45:2

Esercizio 1
Considerate i seguenti  processi

Risorse condivise
  semaphore  S=0, M=1;
  int x=10;
Processo P1
{
    down(&M);
    x:=x+1;
    up(&M);  

   down(&M);
   write(x);
    up(&M);

   up(&S);

}
 Processo P2
{
    down(&S);
 
    down(&M);
    x:=x-1;
    up(&M);
 
    down(&M);
   write(x);
    up(&M);
}

supponete che i processi vengano eseguiti concorrentemente sulla stessa CPU.

  1. Individuate le regioni critiche nel codice di P1 e P2.
    Si possono verificare race conditions per la variabile condivisa x?

  2. Determinare tutti i possibili output di tale programma concorrente (P1 in parallelo con P2).

  3. Supponiamo di inizializzare il semaforo S a 1 invece che a 0.
    Determinare tutti i possibili output del programma (P1 in parallelo con P2) modificato.

Soluzione
  1. Regioni critiche:
    1. R1: x:=x+1;
    2. R2: write(x);
    3. R3: x:=x-1,
    4. R4: write(x)
          Le regioni critiche sono protette da semafori per cui non vi sono race conditions su x
  1. Il semaforo forza l'ordine di esecuzione P1 -> P2 e quindi ci sara' un solo output: 11 10

  2. Il semaforo S non influisce sul flusso di esecuzione e quindi l'output dipende dall'ordine di esecuzione
    di R1-R2 e R3-R4:
    1. Prima R1,R3 (in qualsiasi ordine) e poi R2,R4 (in qualsiasi ordine)--> stampa: 10 10
    1. R1 R2 R3 R4 --> stampa: 11 10
    1. R3 R4 R1 R2 --> stampa:  9  10


Esercizio 2
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 11 7
P2 5 5
P3 10 10
P4 6 9
P5 0 17

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

Soluzione

P5
P5
 P2 P4 P5 P3 P1 P2 P4 P5 P3 P1 P4 P5 P3















0-4ms 4-8 8-12 12-16 16-20 20-24 24-28 28-29 29-33 33-37 37-41 41-44 44-45 45-46 46 - 48 48ms

  1. Tempo di attesa=Tempo di completamento-Tempo di esecuzione
    Media tempo di attesa dei processi: ((44-11-7)+(29-5-5)+(48-10-10)+(45-6-9)+(46-0-17)/5

  2. Tempo di completamento= Istante di completamento - Tempo di arrivo
    Valore medio del tempo di turnaround dei processi: (44-11)+(29-5)+(48-10)+(45-6)+(46-0)/5 = 180/5

Esercizio 3
Considerare la seguente stringa di riferimenti alla memoria di un processo in un sistema con memoria virtuale

S = 20 18 15 10 6 2 15 18 20 6 10 11 8 6 10 9 7 8 11 2 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.


Soluzione 
 Pagina Riferita
  20 18 15 10 6 2 15 18 20 6 10 11 8 6 10 9 7 8 11 2
0 20 20 20 20 20 2 2 2 2 2 10 10 10 10 10 10 10 10 10 2
1
18 18 18 18 18 18 18 18 18 18 18 8 8 8 8 8 8 8 8
2

15 15 15 15 15 15 15 15 15 11 11 11 11 11 7 7 7 7
3


10 10 10 10 10 20 20 20 20 20 20 20 9 9 9 9 9
4



6 6 6 6 6 6 6 6 6 6 6 6 6 6 11 11

                        5 + 9 = 14 page fault




Esercizio 4
Data una memoria partizionata in maniera fissa come segue:
Partizione
 Dimensione
0 200K
1
 600K
2
 150K
3
 500K
e dato che il sistema operativo deve allocare quattro processi P1 di 120K, P2 di 400K, P3 di 180K e P4 di 450K (in quest'ordine),
scrivere in quale partizione il sistema alloca ciascun processo se viene usato l'algoritmo:
  1. First Fit
  2. Best Fit
  3. Worst Fit
(se il processo non puo' essere allocato, segnare "X" come partizione).


Soluzione
Nota: le partizioni sono fisse: non si possono mettere due processi nella stessa partizione!
  1. First fit: P1:0, P2: 1, P3:3, P4:X
  2. Best fit:  P1:2, P2: 3, P3:0, P4:1
  3. Worst fit: P1:1, P2:3, P3:0, P4:X
Esercizio 5
Considerare un file system dove la dimensione di un blocco logico e' 1KB e con indirizzi di blocchi a 16 bit.
  1. Determinare la dimensione massima di un file in caso di 
    1. allocazione concatenata
    2. allocazione indicizzata con due livelli di blocco indice
  2. Determinare il numero di blocchi effettivamente assegnati ad un file di 200KB per i due tipi di allocazione.
Soluzione
Indirizzi a 16 bit --> 216 blocchi fisici
  1. Dim. massima
    1. Allocazione concatenata: ogni blocco ha 1KB-2B=1022 Byte di spazio dati quindi il file piu grande ha dimensione 216 * 1022 Byte
    2. Allocazione indicizzata: ogni blocco puo contenere 1024/2=512 puntatori, quindi con due livelli: (512)2* 1 KB
      (senza considerare spazio per la tabella)

  2. Numero blocchi
    1.  Dim file/Spazio in un blocco = 200 KB/1022 = 201 blocchi
    2.  200 blocchi