Esempio di compitino
Domanda 1:
Elencare almeno 3
circostanze che possono causare la transizione di un processo da stato
di
bloccato a stato di pronto. Motivare la risposta.
Soluzione :
Esecuzione di una
up() sul semaforo su cui il processo è bloccato, arrivo di una
interruzione da
un dispositivo che ha completato una richiesta,
uscita di un processo da un
monitor su cui il processo è in attesa.
Domanda 2:
Discutere la differenza fra process table e user area in un sistema Unix. In quale delle due strutture si trova l'immagine dei registri del processore?
Soluzione:
La process table e la user area raccologono le informazioni relative ai processi nei sistemi Unix. La differenza fondamentale è che la process table viene tenuta sempre in memoria mentre la user area viene copiata su disco quando il processo è ‘swapped out’. Tipicamente la process table contiene: la signal mask, l’immagine della memoria, il pid del processo e tutte le informazioni che servono anche quando il processo non può passare in esecuzione. Esempi di informazioni contenute nella user area sono invece l’array dei gestori dei segnali, la tabella dei descrittori dei file, la kernel stack.
L’immagine dei registri si trova nella user area.
Esercizio 1:
Si consideri il
problema dei lettori e scrittori, con riferimento alla soluzione
proposta nel
testo e riportata di seguito:
semaphore mutex=1;
semaphore db=1;
int rc=0;
void reader (void) {
while (TRUE) {
down(&mutex);
rc=rc+1;
if (rc==1) down(&db); (-2-)
up(&mutex);
read_DataBase();
down(&mutex);
rc=rc-1;
if (rc==0) up(&db);
(-3-)
up(&mutex);
use_data_read();
}
}
void writer(void) {
while
(TRUE) {
Think_Up_Data();
down(&db);
(-0-)
write_data_base();
up(&db);
(-1-)
}
}
Dire cosa accade se:
a)si eliminano gli statement (-0-) e (-1-)
b)si elimina lo statement (-2-)
c)si elimina lo statement (-3-)
Soluzione:
a) si possono avere corse critiche (interferenze) fra i lettori e gli scrittori e fra più scrittori
b) i lettori possono accedere al database mentre uno scrittore lo sta modificando
c) gli scrittori possono rimanere bloccati per sempre in attesa su &db
Esercizio 2
Supponiamo di ricevere 5 job (A,B,C,D,E) tali che:
job Tempo stimato Tempo di arrivo
A 26 0
B 60 1
C 5 2
D 8 3
E
10
4
Descrivere la sequenza di esecuzione dei job in
CPU (ad es. tramite Gantt chart) e calcolare l'istante
in cui ogni job completa il suo task e il relativo tempo totale di completamento ottenuto con:
scheduling FIFO
scheduling round-robin con quanto
di
tempo 5
scheduling a code multiple di
priorita'
con quanto di tempo 5,
considerando le seguenti priorità: A: 3, B: 4,
C: 1,
D: 2, E: 2 (4 più alta)
e supponendo che lo scheduler controlli le code e possa
prelazionare la CPU ogni secondo
Si ignori il tempo impiegato nel context-switching.
Soluzione.
1. Viene prima eseguito A, quindi B, ecc.
A partire dall’istante 0, l'istante di completamento con scheduling FIFO è:
Job A: 26 (quindi tempo totale compl. = 26)
Job B: 86 (tc=85)
Job C: 91 (tc=89)
Job D: 99 (tc=96)
Job E: 109 (tc=105)
2. A viene eseguito per 5 unità, B x 5, C x 5, D x 5, E x 5, quindi nuovamente A x 5, B x 5, D x 3 (completato), E x 5 (completato),
A x 5, B x 5, A x 5, B x 5, A x 5, B x 5, A x 1, B x le restanti 35 unità.
Quindi a partire dall’istante 0, l'istante di completamento con scheduling Round Robin è:
Job A: 74 (tc=...)
Job B: 109
Job C: 15
Job D: 38
Job E: 43
3. Usiamo Gantt chart
| Tempo |
0-1 (1unita) |
1-61 (12quanti) |
61-86 (5quanti) |
86-91 (1quanto) |
91-96 (1quanto) |
96-99 (3unita) |
99-104 (1quanto) |
104-109 (1quanto) |
| Job in CPU |
A |
B | A |
D |
E |
D |
E |
C |
Quindi istante di completamento (a partire dal tempo zero):
Job A: 86
Job B: 61
Job C: 109
Job D: 99
Job E: 104
Esercizio 3
Supponiamo di
ricevere 5 job (A,B,C,D,E) tali che:
job Tempo
stimato Tempo di arrivo
Priorita
A
8
0
2
B
6
1
3
C
3
2
2
D
4
3
2
E
3
4
2
Descrivere la sequenza di esecuzione dei job in CPU (ad es. tramite Gantt chart) e calcolare l'istante
in cui ogni job completa il suo task e il relativo tempo totale di completamento ottenuto con:
Scheduling a code multiple di priorita' e feedback
dove ogni coda e' gestita con la strategia
FCFS.
Il feedback è definito
come segue: la priorità diminuisce di 1 (fino al
livello base 1) se si passano più di 6 unità di
tempo
(consecutive)
in CPU ed aumenta di 1 per ogni 6 unità di tempo passate in attesa in una qualsiasi coda.
Soluzione
Lo scheduler controlla le code (prelaziona la
CPu
se necessario) ogni unita' di tempo
Utilizzamo un Gantt chart:
| Tempo (*) |
0 |
1 |
2 |
3 |
4 |
5 |
6 |
7 |
8 |
9 |
10 |
11 |
12 |
13 |
14 |
15 |
16 |
17 |
18 |
19 |
20 |
21 |
22 |
23 | 24 |
|
Stato dei Job |
A |
2 |
3 |
2 |
3 |
3 |
||||||||||||||||||||
| B |
3 |
|||||||||||||||||||||||||
| C |
2 |
3 |
3 |
3 |
4 |
4 |
||||||||||||||||||||
| D |
2 |
3 |
4 |
|||||||||||||||||||||||
| E |
2 |
3 |
4 |
4 |
||||||||||||||||||||||
Istante di completamento:
A 24
B 7
C 23
D 19
E 22
| Non presente |
|
| N |
Esecuzione in CPU (con priorita
N) |
| N |
Attesa nella coda a priorita N |
| Completato |