Sistemi operativi

Esercizi di scheduling

I'm sorry, I can't transcribe the text from this image.

I'm sorry, but the image does not contain any text that I can transcribe.

RR: quantum di tempo Q = 3 ms

Calcolo tempo medio attesa CPU.

Diagramma di Gantt.

Processo | BT | Arrivo
P1 | 6 | 0
P2 | 9 | 4
P3 | 7 | 6
P4 | 12 | 1

Tempo medio = somma tempi di attesa ogni processo / n° processi.

Tempi di attesa

P1 = (0 - 0) + (6 - 3) = 0 + 3 = 3

P2 = (4 - 4) + (6 - 6) + (15 - 12) = 3 + 6 = 9

P3 = (6 - 6) + (12 - 6) + 1 = 1 + 6 + 4 = 5 = 4

P4 = (3 - 1) + (12 - 6) + 1 = (30 - 24) = 20

=> Tempo medio => (3+21+44+20)/4 = 54/4 = 13,5 ms

Gantt: P4 (1) ➔ P4 (3) ➔ P4 (3) ➔ P2 (3) ➔ P3 (3) ➔ P2 (3) ➔ P4 (3) ➔ P3 (3) ➔ P2 (3) ➔ P4 (3)

Secondo esercizio

2° Process | Run Time | Arrivo
P4 | 3 | 0
P2 | 3 | 2
P3 | 4 | 3
P4 | 5 | 9
P5 | 5 | 1

SJF Preemptive e No Preemptive.

Tempo medio di attesa per entrambi:

Gantt.

Non Preemptive: non si interrompono i processi in esecuzione.

Tempi di attesa

P4 = 4 - 0 = 4 = 1 ms

P2 = 12 - 2 = 9 ms

P3 = 8 - 4 = 3 ms

=> Tempo di attesa = (0+4+4+1+9+3) / 5 = 5,4 ms

Gantt: P4 (1) ➔ P3 (2) ➔ P4 (1) ➔ P2 (3) ➔ P4 (1) ➔ P2 (3) ➔ P5 (3)

Preemptive: hanno priorità i processi più brevi.

P4 = 0
P5 = 0
P2 = 2
P3 = 3
P1 = 5
P4 = 0
P2 = 0
P3 = 0
P5 = 0
P1 = 40          1          2          3          6          8          10          11          12          13          14          15          16          19

Tempo di attesa

P4 = 0 (4-2-1) = 11

P2 = (2-2) = 0

P3 = (3-2) = 0

P5 = (1-4) = 6

P1 = (7-2) + (10-4) = 6

Tempo medio d’attesa => (11 + 0 + 4 + 0 + 6) / 5 = 3,6 ms

Gantt: P4(1) -> P5(1) -> P2(3) -> P3(2) -> P4(1) -> P5(2) -> P4(1) -> P5(2) = P4(7)

Scheduling SSF

Process | Burst Time | Arrival

• P4 8 0
• P2 3 2
• P3 2 4
• P5 4 5
• P5 5 1

SSF Non Preemptive e Preemptive.

Tempo medio d’attesa.

Gantt.

Non Preemptive: P4(8) -> P4(1) -> P3(2) -> P2(3) -> P5(5)

Tempo di attesa

P4 = 0

P2 = (11-2) = 9

P3 = (12-4) = 5

P5 = (8-3) = 0

P5 = (16-1) = 13

T.M.A. => (9+5 = 34+3+0)/5 = 6 ms

Preemptivi: P1 P2 P3 P2 P4 P2 P3 P5 P3 P10 2 5 6 8 9 11 12 14 15 19

P1 5 0
P2 3 1
P3 2 3
P4 2 4
P5 3 44

RR: ultimo esercizio

Process | BT | Arrivi
P1 5 0
P2 3 1
P3 2 3
P4 2 4
P5 3 4

Quanto q 2 ms.

Gantt.

P1 0 0 1 5 2 6 2 8
P2 1 2 2 4 1 5
P3 3 4 1 5
P4 4 5 1 2
P5 5 6 2 8

P1 = (0-0) + (8-2) - (12-2) = 8

P2 = (2-1) + (7-4) = 4 + 9

P3 = (4-3) = 2

P4 = (9-3) + 4

P5 = (4-4) + (13-14) = 7

Tmedio = (8+8+2+4+9)/5 = 5,8 ms

P1(1) -> P2 (2) -> P3 (4) -> P4 (2) -> P5(2) -> P2(1) -> P1(1) -> P5(1)

Deadlock: Banker's

Allocation

A B C
P1 0 1 0
P2 2 0 0
P3 3 0 2
P4 2 1 1
P5 0 0 2

Max

A B C
P1 7 5 3
P2 3 2 2
P3 9 0 2
P4 2 2 2
P5 4 3 3

Available

A B C
3 3 2

Lo stato è ammissibile?

Completa la matrice NEED.

Completa la sequenza sicura con l’esecuzione del vettore work.

Verifica che le due condizioni siano in uno stato ammissibile.

ALLOCATION[i,j] <= MAX[i,j] MAX[i,j]

MAX[i,j] < = TOT

TOT = Allocation + Available (Σ i, Σ j, Σ c)= [(0+2+3+2+0); (1+0+0+1+0); (0+0+2+1+2)]+[3;3;2] = [10;5;7]

NEED = MAX - ALLOCATION

P1 7 4 3
P2 1 2 2
P3 6 0 0
P4 0 1 1
P5 4 3 1

Allocation

A B C
P1 0 1 0
P2 2 0 0
P3 3 0 2
P4 2 1 1
P5 0 0 2

Max

A B C
P1 7 5 3
P2 3 2 2
P3 9 0 2
P4 2 2 2
P5 4 3 3

Available

A B C
3 3