Marco Lapegna » 21.Esercitazione 2: Linux

Linux: Scheduling dei processi

40 livelli di priorità: da -19 (la massima) a 20 (la minima).
I task vengono eseguiti secondo l’ordine di priorità.
Un array delle priorità conserva i puntatori alle liste dei task con la stessa priorità.

Ogni livello gestito in modalità round robin
Priorità variabile a secondo del quanto di tempo q
Time slice piccolo per task a bassa priorità
Time slice grande per task a alta priorità

Ogni task è in esecuzione fino a:

• esaurimento del quanto di tempo;
• operazioni di I/O;
• è disponibile un task con priorità maggiore.

Epoche

Per evitare la starvation dei processi il kernel divide il tempo di CPU in epoche.

Epoca = periodo di tempo predefinito (starvation limit) entro cui tutti i processi sono eseguiti almeno una volta.

All’inizio di ogni epoca viene assegnato un quanto di tempo q ad ogni processo, in funzione della sua priorità.

Durante un’epoca la CPU viene assegnata round robin più volte allo stesso processo, fino a quando q non è  esaurito.

Quando q è esaurito per tutti i processi pronti scade l’epoca e nessun processo è piu’ rischedulato.

Lo stato expired

Alla creazione di un processo si assegna un valore di default q= Q = 200ms

Quando i processi esauriscono il loro quanto oppure scade la starvation limit tutti i processi passano allo stato expired e non possono essere più schedulati.

All’inizio di una nuova epoca il nuovo quanto di tempo q viene ricalcolato come:

q = Q + T/2
(priorità maggiore)

Dove T è il tempo non usato nell’epoca precedente (es. erano bloccati per I/O).

Esercizio

P1 task CPU bound → 50 ms di uso continuo della cpu

P2 task I/O bound → 3 ms di cpu e 3 ms di I/O (continuativo)

A inizio epoca Q = q1 = q2 = 8

Esecuzione di 3 epoche

Determinare il diagramma di Gantt dell’esecuzione

Linux: Algoritmo di paginazione

Caratteristiche generali

• Quando le pagine sono lette in memoria sono inserite in una cache.
• Per migliorare le prestazioni, le pagine sporche sono copiate periodicamente (5-10sec) sul disco (write back caching).

Due tipi di pagine:

1. attive (referenziate di recente);
2. inattive (candidate all’eleminazione).

L’algoritmo di paginazione è una variante del FIFO seconda chance.

FIFO seconda chance a 2 livelli.

FIFO seconda chance a 2 livelli

2 liste di dimensione variabile: pagine attive e pagine inattive.

FIFO seconda chance in ogni lista: le pagine entrano nella lista delle pagine inattive con bit=1.

Nella lista delle pagine inattive un secondo riferimento “promuove” la pagina nella lista delle pagine attive con bit=0

Periodicamente si riorganizzano le liste:

• si spostano alcune pagine attive poco usate nella lista delle pagine inattive, con bit=0;
• circa 2/3 nella lista delle pagine attive e 1/3 tra quelle inattive.

Esercizio

Determinare il numero di page faults per la sequenza

1, 2, 2, 3, 4, 2, 1, 3, 3, 4, 1, 5, 6, 5, 2, 2, 7, 8, 1, 7, 4

Per semplicità:

• si consideri fissata e costante la lunghezza di entrambe le liste L=3;
• le liste si riorganizzano ad ogni riferimento.

Soluzione

In conclusione

Linux e Windows adottano strategie ibride per lo scheduling dei processi e per la sostituzione delle pagine.
Linux

• Scheduling CPU: priorità dinamiche + round robin + starvation limit
• Sost. Pagine: FIFO seconda chance a 2 livelli

Windows

• Scheduling CPU: priorità dinamiche + round robin
• Sost. Pagine: working set + LLRU

Entrambi cercano di privilegiare (mediante le priorità dinamiche) i processi interattivi.
Entrambi non rimuovono subito dalla memoria le pagine “poco” refernziate.