Compito di Sistemi Operativi, Prof. Mancini - 12 gennaio 1999

---

1. (punti: -1,4)

Esistono sistemi operativi dove,

1. alcuni processi sono permanenti, cioè definiti staticamente come componenti del sistema;
2. alcuni processi sono permanenti, cioè definiti dinamicamente come componenti del sistema;
3. tutti i processi sono permanenti, cioè definiti staticamente come componenti del sistema;
4. tutti i processi sono permanenti, cioè definiti dinamicamente come componenti del sistema;
5. nessun processo e' permanente, cioè definito staticamente come componente del sistema;
6. nessun processo e' permanente, cioè definito dinamicamente come componente del sistema;
7. nessuna delle affermazioni precedenti è corretta.

2. (punti: -1,4)

Nel sistema Unix la chiamata di sistema denominata fork eseguita dal processo P_i:

1. genera un processo P_j che e' una copia di P_i, e restituisce a P_i l'indice zero e a P_j il file-descriptor di P_i. I processi P_i e P_j hanno descrittori e immagini in memoria distinte.
2. genera un processo P_j che e' una copia di P_i, e restituisce a P_i il file-descriptor di P_j e a P_j l'indice zero. I processi P_i e P_j hanno descrittori e immagini in memoria distinte.
3. genera un processo P_j che e' una copia di P_i, e restituisce a P_i l'indice zero e a P_j il PID di P_i. I processi P_i e P_j hanno descrittori e immagini in memoria distinte.
4. genera un processo P_j che e' una copia di P_i, e restituisce a P_i l'indice zero e a P_j il PID di P_i. I processi P_i e P_j non hanno descrittori e immagini in memoria distinte.
5. genera un processo P_j che e' una copia di P_i, e restituisce a P_i il PID di P_j e a P_j l'indice zero. I processi P_i e P_j hanno descrittori e immagini in memoria distinte.
6. genera un processo P_j che e' una copia di P_i, e restituisce a P_i il PID di P_j e a P_j l'indice zero. I processi P_i e P_j non hanno descrittori e immagini in memoria distinte.
7. consente dopo la generazione l'avanzamento dei due processi P_i e P_j eseguendo il medesimo programma a partire da un indirizzo logico comune;
8. consente dopo la generazione l'avanzamento dei due processi P_i e P_j eseguendo il medesimo programma a partire da un indirizzo fisico comune;
9. nessuna delle affermazioni precedenti e' corretta.

3. (punti: -1,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, solo collettivamente:

1. necessarie affinche' si verifichi lo stallo;
2. sufficienti affinche' si verifichi lo stallo;
3. necessarie affinche' si verifichi l'attesa indefinita;
4. sufficienti affinche' si verifichi l'attesa indefinita;
5. necessarie e sufficienti affinche' si verifichi l'attesa indefinita;
6. nessuna delle affermazioni precedenti e' corretta.

4. (punti: -1,4)

Nei sistemi operativi l'identificazione degli utenti avviene tramite una parola d'ordine password. Ipotizzando parole d'ordine di 8 caratteri, scelti in un alfabeto di 80 simboli (lettere maiuscole, minuscole, cifre decimali e caratteri speciali):

1. le possibili combinazioni sarebbero 8⁸⁰ e per scoprire la vera parola d'ordine bisognerebbe provarne in media la meta';
2. le possibili combinazioni sarebbero 80⁸ e per scoprire la vera parola d'ordine bisognerebbe provarne in media la meta';
3. le possibili combinazioni sarebbero 80 * 8 e per scoprire la vera parola d'ordine bisognerebbe provarne in media la radice quadrata;
4. le possibili combinazioni sarebbero 8⁸⁰ e per scoprire la vera parola d'ordine bisognerebbe provarne in media un numero lineare;
5. le possibili combinazioni sarebbero 80⁸ e per scoprire la vera parola d'ordine bisognerebbe provarne in media il doppio;
6. le possibili combinazioni sarebbero 80 * 8 e per scoprire la vera parola d'ordine bisognerebbe provarne in media un numero esponenziale;
7. nessuna delle affermazioni precedenti è corretta.

5. (punti: 6)

Illustrare in al più 60 parole il fenomeno conosciuto sotto il nome di thrashing

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	20
P2	8	5
P3	3	12
P4	10	6
P5	7	8

a (punti: 4)

Assegnare questo insieme di processi ad un processore in base alla politica Shortest Job First.

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

a (punti: 3)

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.

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 realizzare un semplice programma concorrente che possa causare l'attesa indefinita ma non lo stallo dei processi componenti.

9. (punti: 8)

Realizzare un Perl script efficiente che legga il contenuto degli archivi passati come parametro e stampi ciascuna linea nello standard output a meno che la linea non sia già stata stampata prima. Si assuma che i dati da leggere non possano essere contenuti completamente in memoria centrale.
 
 

---

Risultati della prova

---

1.a,c
2.e,g
3.a,b
4.b

---

5. In caso di gestione di memoria virtuale, il thrashing consiste nella frequente alternanza di caricamenti e scaricamenti di un ristretto numero di pagine di memoria durante l'esecuzione di un processo. Questo fenomeno contribuisce a ridurre la velocita' di avanzamento dei processi.

---

6.

a) Algoritmo Shortest Job First:
 

P1	P3	P2	P4	P3	P5	P1
0-3	3-8	8-13	13-19	19-26	26-34	34-51

b) media tempo di attesa dei processi: 64/5
c) turnaround medio: 115/5

---

7.

a. Algoritmo Second Chance:
 

TurnoMS

  TurnoMS e' inizializzato a 4.
 

	9	3	1	0	1	3	5	9	15	1	3	6	4	6	5	1	7	4	6	3
0	91	91	91	91	91	91	91	91	151	151	151	151	151	151	150	150	71	71	71	71
1		31	31	31	31	31	31	31	30	30	31	30	30	30	51	51	51	51	51	50
2			11	11	11	11	11	11	10	11	11	10	10	10	10	11	10	10	10	31
3				01	01	01	01	01	00	00	00	61	61	61	61	61	60	60	61	61
4							51	51	50	50	50	50	41	41	41	41	40	41	41	41
	p	p	p	p			p		p			p	p		p		p			p

Numero page fault: 4+7

b. Algoritmo LRU (pag. 469 del Maestrini):
 

Pagina riferita

	9	3	1	0	1	3	5	9	15	1	3	6	4	6	5	1	7	4	6	3
0	9	9	9	9	9	9	9	9	9	9	9	9	4	4	4	4	4	4	4	4
1		3	3	3	3	3	3	3	3	3	3	3	3	3	3	3	7	7	7	7
2			1	1	1	1	1	1	1	1	1	1	1	1	1	1	1	1	1	1
3				0	0	0	0	0	15	15	15	15	15	15	5	5	5	5	5	3
4							5	5	5	5	5	6	6	6	6	6	6	6	6	6
	p	p	p	p			p		p			p	p		p		p			p

Numero page fault: 4+7

---

8. Nel problema dei processi lettori e scrittori in un database puo' avvenire il fenomeno di
attesa indefinita:
Se mentre e' presente un processo lettore nella sezione critica, continuano ad arrivare altri lettori, tutti i processi scrittori dovranno aspettare (attesa indefinita) l'uscita dell'ultimo lettore^(*) dalla sua sezione critica, rilasciando cosi' la mutua esclusione sul semaforo db.

semaphore mutex=1, db=1;
int rc=0;

void Lettore()
   {
   P(mutex);
   rc++;
   if (rc==1) P(db);
   V(mutex);
   LetturaDB();
   P(mutex);
   rc--;
   if (rc==0) V(db);     (*)
   V(mutex);
   }

void Scrittore()
   {
   P(db);
   ScritturaDB();
   V(db);
   }
 

---

9.
perl -ne 'print unless $seen{$_}++' archivi

---

12 gennaio 1999 -

Si ringraziano i volenterosi studenti Alessandro Cagnetti e Daniele Giabbai