Interattivi

I sistemi interattivi sono quelli tipici dei PC, server e altri sistemi dove ci sono utenti impazienti di risposte rapide.

L’obiettivo principale è il tempo di risposta, ovvero minimizzare il tempo che percorre tra l’invio del comando da parte dell’utente e l’ottenimento del risultato, per questo motivo si utilizzano algoritmi preemptive:

Round-Robin (RR)
scheduling con priorità
Shortest Process Next - SPN
scheduling garantito
lottery scheduling (a lotteria)
fair-share scheduling (a quota equa)

Round-Robin

L’algoritmo Round-Robin è uno degli algoritmi :

- vecchio
- semplice
- equilibrato
- utilizzato

È un algoritmo dove ad ogni processo viene assegnato un intervallo di tempo (quantum), durante il quale può essere eseguito.

La logica dell’algoritmo è semplice:

i processi in stato ready sono mantenuti in una coda
quando un processo termina la sua quantum, si rimette in coda
se il processo è ancora in esecuzione quando finisce la sua quantum, viene sospeso e fatto eseguire un altro processo che è in coda
se il processo si blocca (es. attesa I/O) non si aspetta che finisce la quantum, ma la CPU viene assegnata al processo successivo in coda

Dobbiamo inoltre considerare che la scelta della quantum assegnata è un fattore critico:

quantum troppo breve $\to$ troppe interruzioni dei processi $\to$ + overhead per il context switch
quantum troppo alta $\to$ attesa eccessiva

Un quantum di 20-50 ms è spesso ragionevole e un buon compromesso tra efficienza e reattività.

Scheduling con priorità :luc_chevron_up:

Nello scheduling round-robin c’è l’assunzione è che tutti i processi sono ugualmente importanti, ma in molti contesti reali questa ipotesi è troppo restrittiva (es. università con differenti ruoli).

Un approccio differente è quello di assegnare una priorità a ciascun processo e lo scheduler tiene conto della priorità nel momento in cui deve scegliere il processo da mandare in esecuzione.

Per esempio un daemon mail avrebbe meno priorità di un video in tempo reale.

Inoltre per evitare che i processi ad alta priorità girino per troppo tempo, lo scheduler può:

diminuire la priorità del processo in esecuzione ad ogni ciclo di clock
- se scende sotto quella del processo successivo, avviene uno scambio
utilizzare un quantum di tempo massimo

L’assegnazione delle priorità può essere:

statica: assegnate all’inizio dell’esecuzione e mantengono un valore fisso (es. priorità basate sull’utente)
dinamica: assegnate o modificate dal sistema in modo dinamico per raggiungere obiettivi di sistema (es. basata sull’utilizzo della CPU)

Priorità + Round-Robin

Una configurazione comune combina la priorità con il Round-Robin, dove si raggruppano i processi in classi di priorità e si usa lo scheduling con priorità tra le classi (piuttosto che tra singoli processi), ma all’interno di ciascuna classe si applica l’algoritmo Round-Robin.

Per esempio consideriamo un sistema con 4 classi di priorità :

finché ci sono processi nella classe 4, esegui ognuno di questi processi con round-robin e fregatene delle altre classi
se la classe 4 è vuota, passa alla 3, se la 3 è vuota, passa alla 2 e cosi via

Bisogna però tenere in considerazione che se le priorità non cambiano occasionalmente, i processi delle classi di priorità bassa potrebbero “morire di fame” (starvation).

Shortest Process next - SPN

Poiché l’algoritmo SJF fornisce il tempo medio di risposta nei sistemi batch, sarebbe ideale applicare un principio simile anche ai processi interattivi per minimizzare il tempo medio di risposta totale.

L’algoritmo SPN tenta di applicare i principi del SJF, stimando la durata del prossimo consumo di CPU in base ai tempi di esecuzione precedenti (aging).

Il principio di misura quindi si basa sull’idea di misurare quanto durerà la prossima esecuzione in base al tempo effettivo delle esecuzioni precedenti (effettivo e non stime precedenti).

T_{i} = {t_{0} i = 1 α t_{i - 1} + (1 - α) T_{i - 1} i \geq 2

dove :

$α$ è un fattore di peso compreso tra 0 e 1, che decide quanto rapidamente la stime “dimenticano” il passato (di solito è buono 0.5)
$t_{n}$ : tempo effettivo di esecuzione
$T_{n}$ : stima

Facciamo un esempio, supponiamo di avere i tempi (esatti) di esecuzione dei 4 processi precedenti:

$t_{0} = 970 \micro s$
$t_{1} = 630 \micro s$
$t_{2} = 230 \micro s$
$t_{3} = 140 \micro s$ e vogliamo calcolare la stima del 5 processo $T_{4}$ utilizzando $α = \frac{1}{2}$ :

T_{4} = \frac{t _{3}}{2} + \frac{T _{3}}{2} = \frac{t _{3}}{2} + \frac{1}{2} [\frac{t _{2}}{2} + \frac{T _{2}}{2}] = = \frac{t _{3}}{2} + \frac{t _{2}}{4} + \frac{1}{4} [\frac{t _{1}}{2} + \frac{T _{1}}{2}] = \frac{t _{3}}{2} + \frac{t _{2}}{4} + \frac{t _{1}}{8} + \frac{T _{1}}{8} = = \frac{t _{3}}{2} + \frac{t _{2}}{4} + \frac{t _{1}}{8} + \frac{t _{0}}{8} = = \frac{140}{2} + \frac{230}{4} + \frac{630}{8} + \frac{970}{8} = = 70 + 57.5 + 78.75 + 121.25 = 327.5 \micro s

Osserviamo quindi che :

non potremmo calcolare $T_{4}$ se non conosciamo $t_{3}$
il peso di $t_{0}$ è calato di $\frac{1}{8}$ (pesa meno)

Scheduling garantito :luc_check_circle:

Un approccio completamente diverso per lo scheduling è quello stipulare promesse reali agli utenti riguardo alle prestazioni del sistema e poi rispettarle.

Il funzionamento per mantenere la promessa :

il sistema memorizza quanta CPU ciascun processo ha effettivamente utilizzato dalla sua creazione = $tempo_utilizzato$
il tempo che un processo ha diritto (promessa) è calcolato come il tempo trascorso ( $tempo_trascorso$ ) dalla sua creazione diviso per $n$ (il numero di utenti o processi concorrenti) $⟹$ $promessa = \frac{tempo_trascorso}{n}$
poi si calcola il rapporto tra il tempo effettivo utilizzato e la promessa $r = \frac{tempo_utilizzato}{promessa}$
l’algoritmo assegna la CPU al processo che presenta il rapporto più basso

Un rapporto quindi di 0.5 indica che il processo ha avuto solo metà di ciò che gli spetta.

Per esempio :

1 : creato da 20 sec, usato 10 sec 
2 : creato da 10 sec, usato 3 sec 
3 : creato da 50 sec, usato 40 sec 

promessa1 = 20/3 = 6.6
promessa2 = 10/3 = 3.3
promessa3 = 50/3 = 16.6

rapporto1 = 10/6.6 = 1.5 -> secondo
rapporto2 = 3/3.3 = 0.9 -> primo
rapporto3 = 40/16.6 = 2.4 -> terzo

Analogia per capire meglio :

Scheduling a lotteria :luc_ticket:

Fare promesse agli utenti è una bella idea ma è difficile da realizzare.

Per questo viene introdotto un algoritmo più semplice che assegna un “biglietto della lotteria” per ottenere le varie risorse del sistema, come il tempo della CPU.

Ogni volta che deve essere presa una decisione dello scheduler si “pesca” a caso un biglietto della lotteria e il processo che ha quel biglietto si “aggiudica” la risorsa (es. un quantum di tempo CPU)

A processi più importanti possono essere dati biglietti extra per incrementare la probabilità di vincere. Infatti per esempio se un processo possiede 20 biglietti su 100 biglietti totali, allora ha il 20% di probabilità di ottenere la risorsa ad ogni “estrazione”.

Le proprietà interessanti di questo algoritmo sono:

reattività : appena un processo arriva gli vengono assegnati dei biglietti e quindi ha già la possibilità di vincere alla prossima “estrazione”
cooperazione : i processi possono scambiarsi i loro biglietti, alterando dinamicamente le priorità

Consideriamo la seguente situazione: se un utente x avvia 9 processi ed un altro utente y ne avvia 1 soltanto, con round-robin o priorità uguali, il primo utente si prenderà il 90% del tempo CPU, mentre il secondo solo il 10%.

Quindi l’obiettivo dell’algoritmo fair-share è quello di impedire questa in-equità, ovvero che un utente “ricco di processi” possa dominare.

Il funzionamento si basa sulle seguenti:

a ciascun utente viene assegnata una frazione della CPU (la quota equa)
lo scheduler agisce in modo da rispettare tale quota, con un “altro algoritmo” di scheduling (indipendentemente dal numero di processi posseduti)

Consideriamo per esempio due utenti :

utente x con 4 processi : A, B, C e D
utente y con 1 processo : E
a entrambi gli utenti viene assegnata una quota del 50% di utilizzo, se lo scheduler utilizza il round-robin avremo :

AEBECEDEAEBECEDE...

oppure è possibile che l’utente x abbia una quota maggiore (es. 66.7%) e l’utente y una quota minore (es. 33.3%), si potrebbe ottenere una sequenza come la seguente (sempre round-robin) :

ABECDEABECDE...

Tabella di riepilogo

Real_time

0n1zuka

Explorer

Interattivi

Round-Robin