Definizioni
Caratteristiche degli algoritmi di schedulazione
Scheduler senza prerilascio
Scheduler con prerilascio
Scheduler time-sharing
Multi-Level Feedback Queues
Struttura dello scheduler
Valutazione e scelta
Scheduler di Unix
Definizioni (Indice)
Ogni processo si trova nella sua vita in un diverso stato, a seconda se e' in possesso della CPU (stato running: un solo processo al piu' alla volta), in attesa di averla (stato ready) o in attesa di avere un servizio (stato waiting: ad esempio di una lettura da disco).
------> ready -------> running -- ---> terminato ^ | | | ---- waiting <----------
Un processo ready e' inserito nella ready queue in una posizione
che dipende da diversi criteri. Quando la CPU e' libera, viene attribuita
al processo che si trova al suo top.
Il meccanismo con cui si effettua l'inserimento in coda e si seleziona
il candidato che deve essere selezionato si chiama schedulazione (vedere
code.html ).
Abbiamo, per quanto riguarda la CPU, 3 possibilita':
Prenderemo in considerazione qui alcuni meccanismi che possono essere adottati per gli Short e Long Term scheduler.
Per valutare la performance di uno scheduler si considerano alcune quantita':
Non e' detto che un sistema di schedulazione per la CPU accettabile per processi non interattivi (o batch) lo sia anche per processi interattivi.
Caratteristiche degli algoritmi di schedulazione (Indice)
Indicando con:
A il tempo di servizio gia' ottenuto,
T il tempo di servizio richiesto,
R il tempo di arrivo nella coda ready.
abiamo la tavola riassuntiva:
| Politica | Funzione priorita' | Modalita' decisione | Regola arbitraggio |
| FCFS | -R | senza prerilascio | - |
| SJF | -T | senza prerilascio | casuale o cronologica |
| SRTF | A - T | con prerilascio all'arrivo |
casuale o cronologica |
| RR | costante | con prerilascio (quantum di tempo) |
ciclica |
| MLFQ | dinamica su piu' livelli |
- | - |
Scheduler senza prerilascio (non preemptive) (Indice)
Attivato solo quando un processo si autosospende su una richiesta di servizio.
La gestione della ready queue e' effettuata dallo scheduler, che e' una parte del kernel, ed e' attivato solo su interruzione.
All'arrivo di una interruzione esterna, il kernel potrebbe togliere dalla coda blocked un processo (precedentemente in attesa di un servizio legato all'interruzione arrivata) e inserirlo nella coda ready. Negli scheduler non preemptive questa azione non genera una sospensione del processo running, a cui viene nuovamente passata la CPU.
All'arrivo di una trap, che indica una richiesta del processo running, lo scheduler puo' inserire il processo richiedente in una coda di attesa (stato blocked), e passare il controllo ad un altro processo della coda ready.
Negli scheduler non preemptive questo e' l'unico caso di context switch possibile.
First-Come First-Served (FCFS)
E' il piu' semplice. La priorita' e' quella di arrivo dei processi che lasciano la coda waiting perche' hanno avuto soddisfatta la loro richiesta. Il comportamento si puo' analizzare considerando un caso specifico. E' usato soprattutto per long-term-scheduler.
ESEMPIO
Supponiamo che in un istante zero ci sia una certa situazione della ready queue, che ogni job occupi una fase di tempo (in unita' arbitrarie) di CPU come descritto sotto, e non arrivino altri job:
job fase CPU
1 24 2 3 3 3
La Gantt chart dell'esecuzione e':
------------------------------------------------ | job1 | job2 | job3 | ------------------------------------------------ 0 24 27 30
Il turnaround time medio e' (24+27+30)/3 = 27. Il waiting time medio
e': (0+24+27)/3 = 17 (a partire dall'istante zero).
Se l'ordine nella ready queue fosse stato job2, job3, job1, il turnaround
time medio sarebbe stato: (3+6+30)/3 = 13 e il waiting time medio: (0+3+6)/3
= 3.
Complessivamente quindi la CPU lavora sempre lo stesso tempo (notare
che in questo esempio non si e' tenuto conto dei tempi aggiuntivi dovuti
all'esecuzione dell'algoritmo di scheduler, al context switch fra processi,
e al tempo di servizio di eventuali interruzioni sopraggiunte, che non
provocano una rischedulazione, ma che sono comunque servite dal kernel).
Nel caso di long term scheduler il tempo indicato non si riferisce al solo tempo di CPU, ma all'intero tempo di esecuzione del job (permanenza nel sistema).
Nel primo caso il processo lungo e' servito subito, ma gli altri due,
che peraltro sono brevi, devono aspettare parecchio (8-9 volte la loro
effettiva durata). Nel secondo caso invece i job brevi sono serviti (quasi)
subito, e il job lungo aspetta un tempo che e' solo un quarto del suo tempo
di esecuzione. Ci si aspetta quindi un maggior "gradimento" medio
degli utenti nel secondo caso.
Shortest Job First (SJF)
Anche questo e' essenzialmente per long term scheduler. Si cerca di
ottenere uno scheduler che abbia le caratteristiche positive del secondo
caso dell'esempio precedente.
Si richiede di conoscere a priori la durata della fase di eleborazione
necessaria.
La priorita' di un processo e' inversamente proporzionale al tempo di esecuzione
valutato, cioe'
priorita' = 1 / tempo_esecuzione.
ESEMPIO
Supponiamo che in un istante zero ci sia una certa situazione della ready queue, che ogni job occupi una fase di tempo (in unita' arbitrarie) di CPU come descritto sotto, e non arrivino altri job:
job fase CPU
1 6 2 3 3 8 4 7
La Gantt chart dell'esecuzione e':
------------------------------------------- | job2 | job1 | job4 | job3 | ------------------------------------------- 0 3 9 16 24
Il turnaround time medio e' (3+9+16+24)/4 = 13.
Questo tempo e' ottimale anche nel waiting time, cioe' se i tempi previsti
sono corretti non c'e' uno scheduler diverso che possa dare un valore di
waiting time medio migliore (come scheduler non preemptive).
La cosa difficile e' fare una stima a priori dei tempi di esecuzione. Nei job eseguiti in batch e' lo stesso utente che indica una sua stima. Se usato come short term scheduler si puo' fare una supposizione, che cioe' le varie fasi abbiano durate simili. Si usa allora la formula seguente:
T(n+1) = next CPU burst valutato = media pesata delle fasi di CPU precedenti
t(n) = lunghezza effettiva dell'n-esimo CPU burst
T(n+1) = a t(n) + (1 - a) T(n)
"a" e' il peso che si intende dare alla storia piu' recente rispetto a quella passata, ed e' un valore compreso fra 0 e 1. Generalmente a = 0.5.
Questo algoritmo ha un altro difetto: non e' fair. E' infatti
possibile che un job che richiede un lungo tempo di esecuzione non sia
mai eseguito perche' continuano a presentarsi job con brevi periodi richiesti.
Questa situazione si presenta facilmente negli algoritmi che utilizzano
priorita' statiche. Si puo' evitare solo usano priorita' dinamiche,
ad esempio facendo aumentare la priorita' di un processo a mano a mano
che invecchia. Questa soluzione si chiama aging, e consente di evitare
la starvation (cioe' appunto che un processo "muoia di fame"
perche' mai schedulato). Aumentando la priorita' dei processi nel tempo,
prima o poi qualunque processo raggiungera' una priorita' tale che gli
consentira' di essere schedulato.
Ovviamente c'e una premessa: che qualunque processo prima o poi termini
(ad esempio si esclude il caso di loop infinito, o si suppone che ci sia
un time-out).
Scheduler con prerilascio (preemptive) (Indice)
La CPU puo' essere tolta al processo running prima che questo la rilasci volontariamente (all'arrivo di una interruzione esterna che provoca l'inserimento di un processo a piu' alta priorita' nella coda ready). In questo caso il processo sospeso viene reinserito nella coda ready. Si tratta di algoritmi utili nei sistemi real-time, o dove si vuole garantire che un processo con alta priorita' sia eseguito al piu'presto.
Richiede mediamente un numero maggiore di context switch e tempi maggiori per l'esecuzione dello scheduler, che viene attivato anche piu' di frequente. Si possono ottenere partendo da un algoritmo non preemptive e modificarlo. Il FCFS e' intrinsecamente non modificabile, mentre si puo' fare con il SJF.
Shortest Remaining Time First (SRTF)
Come il SJF, ma se arriva un processo che richiede minor tempo di CPU di quello ancora da utilizzare da parte del processo running, quest'ultimo viene sospeso e il nuovo running e' quello arrivato. La priorita' di un processo e' calcolata nel momento in cui arriva in coda ready, e viene in quel momento ricalcolata anche la priorita' del processo running (allo stesso modo del SJF).
ESEMPIO
In questo caso dobbiamo anche considerare diversi tempi d'arrivo in coda ready.
job tempo arrivo fase CPU
1 0 8 2 1 4 3 2 9 4 3 5
La Gantt chart dell'esecuzione e':
-----------------------------------------------------
| job1 | job2 | job4 | job1 | job3 |
-----------------------------------------------------
0 1 5 10 17 26
^
interruzione
Turnaround time medio = (17 + (5 - 1) + (26 - 2) + (10 - 3)) / 4 = 52/4
= 13.
Senza preemption sarebbe stato TTM = 14.25.
Occorrerebbe anche consederare i tempi addizionali dovuti alla rischedulazione.
L'algoritmo non e' fair, e potrebbero sorgere problemi per la contesa delle
risorse.
Interrupt clock o time sharing (Indice)
Questo tipo di scheduler potrebbe essere incluso nella categoria precedente
(con preemption) perche' la modalita' di attivazione dello scheduler e'
appunto con preemption. Viene invece in genere gestita a parte perche'
ha caratteristiche diverse concettualmente. Si basa sul fatto che periodicamente
(usando l'interruzione del clock) viene attivata la rischedulazione.
Utile per sistemi interattivi (time sharing) dove si cerca di garantire
response time brevi.
Round Robin (RR)
Gestione della coda FCFS, in cui i processi hanno un tempo limitato di CPU prima di essere sospesi e rimessi in coda ready. Questo tempo e' detto quantum o time-slice.
ESEMPIO
quantum = 4
job fase CPU
1 24 2 3 3 3
La Gantt chart dell'esecuzione e':
--------------------------------------------------------- | job1 | job2 | job3 | job1 | job1 | job1 | job1 | job1 | --------------------------------------------------------- 0 4 7 10 14 18 22 26 30
Turnaround time = (20 + 7 + 10) / 3 =circa 16.
Il risultato in questo algoritmo non e' quello di minimizzare i tempi di
attesa, ma di distribuire i tempi in modo che tutti i processi siano "rallentati"
dagli altri in ugual misura. Ovviamenti i processi si avvantaggiano comunque
rispetto a quelli lunghi.
Indicando con n i processi in coda e con q la durata del quantum, ogni processo deve aspettare al massimo (n-1)q tempo prima di avere il suo burst di CPU. Ad esempio se n=5 e q=20 millisecondi, ogni processo ha il controllo della CPU al massimo ogni 100 millisecondi.
La performance e' legata alla durata del quantum.
Considerando un tempo di context switch di 10 millisec. e il quantum
a 100 millisec., abbiamo un tempo di occupazione di CPU che potrebbe
essere del 10% superiore a quello calcolato in teoria.
Prendiamo un processo con CPU burst di 12 millisec., se q=12 riesce
a terminare, se q=6 bisogna aggiungere 1 context swith, se q=1 bisogna
aggiungere 11 context switch.
Il turnaround time medio, anche senza C.S. time, cresce col diminuire del quantum
ESEMPIO
3 job di 10 unita' di CPU burst ciascuno, quantum = 1 unita': turnaround
time medio = 29.
3 job di 10 unita' di CPU burst ciascuno, quantum = 10 unita': turnaround
time medio = 20.
Il quantum suggerito e' tale per cui l'80% delle fasi di CPU siano piu' corte del quantum.
Multi-Level Feedback Queues (Indice)
Non ci deve necessariamente essere un'unica coda, anzi normalmente se ne usano piu' di una, per usare deversi tipi di scheduler in dipendenza delle diverse caratteristiche dei processi, e per adattarsi meglio alle circostanze.
Ci sono diversi modi per gestire code multilivello. Unix ne implementa un tipo, che e' descritto in seguito nei particolari.
Un sistema potrebbe essere quello di attribuire diverse priorita' statiche ad ogni coda, per cui ci potrebbe essere una coda per i processi di sistema, seguita da una coda per processi interattivi, e per ultima una coda di job batch. Lo schedulatore inizia dalla prima coda e assegna la CPU al processo al top, se ce n'e', altrimenti passa alla seconda e cosi' via. Potrebbe poi esserci un algoritmo diverso per ogni coda, ad esempio FCFS per la prima, RR per la seconda, SJF per la terza.
Questo sistema non e' fair, per cui si potrebbe correggere imponendo un time slice fra le code, assegnando cioe' un quantum di tempo di CPU per la gestione di ogni coda prima di passare a quella successiva.
Se questo sistema e' troppo complicato si puo' utilizzare il feedback per rendere dinamiche le priorita' dei processi all'interno delle code, e farli quindi spostare verso il basso o verso l'alto, rendendo fair l'algoritmo. In questo caso ogni coda mantiene in ordine FCFS i processi con pari priorita'. Quando un processo sta troppo tempo in una coda di bassa priorita' senza essere servito, la sua priorita' viene ricalcolata e si sposta verso l'alto. Quando un processo ha gia' usufruito di un certo tempo di CPU, la priorita' viene diminuita e lui spostato verso il basso.
Un altro sistema ancora e' quello di usare RR per tutte le code, ma con quanti di tempo diverso. Se un processo viene interrotto troppe volte prima di finire la sua fase di CPU, vuol dire che e' richiesto un quantum piu' lungo e viene declassato. Con l'aging si risale.
Struttura scheduler (Indice)
La struttura dati fondamentale dello scheduler e' la ready_queue, una coda di priorita' formata da descrittori di processi ordinati secondo la loro priorita'. Ogni processo ha una priorita' iniziale assegnata. Viene poi incrementata (se il caso) in dipendenza del tempo trascorso nella coda ready.
Operazioni elementari sopra la ready_queue:
extract(ready_queue): estrae dalla coda il processo con la massima priorita'.
insert(ready_queue): inserisce nella coda un processo, nell'ordine definito dalla sua priorita'.
Quando un processo si sospende in attesa di un servizio entra in altre code di attesa.
Lo scheduler non preemptive si attiva:
Lo scheduler preemptive con calcolo statico della priorita' effettua un context switch anche quando viene inserito nella ready_queue un processo con maggiore priorita' di quello running.
Lo scheduler preemptive con calcolo dinamico della priorita' effettua un context switch anche quando un processo ready raggiunge una priorita' maggiore di quella del processo running.
Tutti i processi nella coda ready hanno uguale priorita'. Gestione FIFO.
Il quanto di tempo e' uguale per tutti i processi, e il suo valore e' registrato
nella variabile quanto.
In ProcTable sono memorizzati i descrittori dei processi, in ready_queue
gli indici dei processi ready. La variabile running memorizza l'indice
del processo running. Il valore curr_clock e'resettato dopo ogni
context switch, viene incrementato ad ogni interruzione del clock e causa
una interruzione software ogni volta che arriva al valore quanto.
switch(i) e return(i) causano un context switch. clock, sys_call
e ready_proc sono funzioni di interrupt realtive all'interruzione
per time-out, richiesta di servizio da parte del processo running e reinserimento
di un processo in attesa nella coda ready.
type ProcTable: array [1..MaxProc] of ProcDescr;
ready_queue: queue of ProcDescr pointer;
running: ProcDescr pointer;
quanto: integer;
num_proc: integer;
/* numero dei processi creati inizialmente */
function main /* inizializzazione */
begin
begin
for i:=1 to num_proc do
Crea l'i-esimo processo;
ProcTable[i]:=descrittore processo i-esimo;
insert (i, ready_queue);
quanto:=.....;
assegna l'indirizzo della funzione clock
l'indirizzo della funzione sys_call
l'indirizzo della funzione ready_proc
nel vettore delle interruzioni;
........
running:=extract(ready_queue);
curr_clock:=0;
switch(running)
end;
interrupt function clock;
begin
curr_clock:=curr_clock+1:
if (curr_clock=quanto) and (running<>nil) then
inc(ProcTable[running].CPU_time);
save_context(running);
insert(running, ready_queue);
running:=extract(ready_queue);
restore_context(running);
curr_clock:=0;
return(running)
end;
interrupt function sys_call;
begin
save_context(running);
... inserisce il processo sospeso nella
coda d'attesa opportuna ....
running:=extract(ready_queue);
if running<>nil then
curr_time:=0;
restore_context(running);
return(running)
end;
interrupt function ready_proc(i);
/* i e' un puntatore al processo che e' stato
sbloccato dall'interruzione */
begin
insert(i, ready_queue);
if running=nil then
curr_clock:=0;
running:=extract(ready_queue);
restore_context(running);
return(running)
end:
Valutazione e
scelta (Indice)
Per prima cosa occorre definire i criteri per la selezione dell'algoritmo. Ad esempio:
Una volta scelto l'algoritmo piu' adatto, si valutano e dimensione i
parametri per un certo carico (occorre quindi anche definire quale carico
e quale tipologia di processi si vuole servire).
Si possono seguire diversi criteri: Modelll deterministico, Valutazione
analitica, Simulazione, Sperimentazione.
Modello Deterministico
Si prende un workload predeterminato e i verifica la performance di un algoritmo (estensione del sistema dei Gantt chart visto prima).
ESEMPIO 1
Consideriamo la situazione:
Job Burst Time
1 10 2 29 3 3 4 7 5 12
e vediamo cosa succede con la schedulazione FCFS, SJF, RR con quantum = 10. Quale da' il minimo tempo medio di waiting?
FCFS
----------------------------------------- | 1 | 2 | 3 | 4 | 5 | ----------------------------------------- 0 10 39 42 49 61
Waiting time medio = (0 + 10 + 39 + 42 + 49) / 5 = 140 / 5 =28
SJF
----------------------------------------- | 3 | 4 | 1 | 5 | 2 | ----------------------------------------- 0 3 10 20 32 61
Waiting time medio = (10 + 32 + 0 + 3+ 20) / 5 = 65 / 5 = 13
RR
---------------------------------------------- | 1 | 2 | 3 | 4 | 5 | 2 | 5 | 2 | ---------------------------------------------- 0 10 20 23 30 40 50 52 61
Waiting time medio (senza context switch) = (0 +32 +20 +23 +40) / 5 = 115 / 5 = 23
In questo caso SJF ha meno della meta' del tempo medio di attesa di
FCFS.
Questo metodo di valutazione e' utile per i sistemi "dedicati",
in cui lo stesso programma gira piu' volte e si possono misurare i tempi
e le caratteristiche in modo statico.
ESEMPIO 2
Job Burst Time
1 10 2 7 3 5
FCFS
--------------------------- | 1 | 2 | 3 | --------------------------- 0 10 17 22
Waiting time medio = (0 + 10 + 17) / 3= 27 / 3 =9
RR con quantum = 3
----------------------------------------------------- | 1 | 2 | 3 | 1 | 2 | 3 | 1 | 2 | 1 | ----------------------------------------------------- 0 3 6 9 12 15 17 20 21 22
Waiting time medio = ((22 - 10) + (21 - 7) + (17 - 5)) / 3 = 38 / 3 = circa 13
RR con quantum = 6
------------------------------------- | 1 | 2 | 3 | 1 | 2 | ------------------------------------- 0 6 12 17 21 22
Waiting time medio = ((21 - 10) + (22 - 7) + (17 - 5)) / 3 = 38 / 3 = circa 13
RR con quantum = 7
-------------------------------- | 1 | 2 | 3 | 1 | -------------------------------- 0 7 14 19 22
Waiting time medio = ((22 - 10) + 7 + (14 - 7 )) / 3 = 26/ 3 = circa
8.7.
L'ultimo e' il valore migliore fra i tre tipi di RR.
Tempo minimo di wait:
min (17, 14, 15, 12) = 12
Valutazione Analitica
Si utilizza in questo caso un modello probabilistico (teoria delle code) che consente di valutare il comportamento combinato di code di cui si conosca la distribuzione degli arrivi e dei tempi di servizio. In questo caso si possono studiare le variazioni al cambiare dei parametri (valori medi o massimi di permanenza in coda, tasso medio di utilizzazione del processore ecc.)
Simulazione
Le tecniche di simulazione utilizzano un modello di simulazione del sistema che rappresenta la risorsa CPU e gli algoritmi per la sua gestione, le attivita' dei processi e l'avanzamento del tempo (i dati che pilotano la simulazione sono la creazione e la terminazione dei processi e, per ogni processo, la sequenza di riattivazioni e di sospensioni. Questi dati possono essere generati da un modello probabilistico oppure rilevati da un sistema reale).
L'utilizzazione di dati prelevati da sistemi reali, piuttosto che generati da un modello probabilistico, tende in generale a produrre risultati piu' attendibili, ma anche ad accrescere i costi della simulazione.
Sperimentazione
Consiste nel rilevare i dati significativi per la valutazione durante il normale funzionamento del sistema operativo, presuppone degli strumenti incorporati nel sistema operativo che permettano di rilevare con ciontinuita' e con costi accettabili i dati richiesti.
L'efficacia del metodo sperimentale dipende anche dalla posssibilita' di modificare la politica di gestione del processore adottata dal sistema operativo, per poter confrontare politiche diverse.
Deadline Scheduler
I criteri visti finora per schedulare la CPU non sono gli unici possibili. Ad esempio, in sitemi real time, e' necessario che certi job o processi siano attivati o terminino esattamente entro un tempo predefinito (deadline). Lo scheduler e' piu' complesso, ma in genere e' deterministico, cioe' e' possibile conoscere in anticipo i job da eseguire ed i loro tempi di arrivo e di esecuzione.
A differenza di Minix, in Unix non esistono processi del kernel e processi
dell'utente separati, ma solo processi che passano da modo kernel a utente
e viceversa. Infatti Unix e' un S.O. con modello a chiamata di procedura.
Un processo utente esegue una procedura del kernal in modo kernel. La procedura
non appartiene necessariamente al processo che la sta eseguendo, potrebbe
ad esempio essere una procedura di schedulazione per scegliere il successivo
processo da attivare, o una routine di interruzione a seguito di un segnale
esterno.
Quando un processo opera in modo kernel utilizza uno stack del kernel all'interno
dell'area utente.
Il codice del kernel e le sue strutture dati sono quindi condivise da tutti
i processi, e non fanno parte di un processo particolare come nel caso
di S.O. con modello client-server.
Per evitare la race condition, si devono eseguire i processi
che modificano le tabelle e i dati del kernel in mutua esclusione.
Il sistema utilizzato da Unix e' semplicemente quello di impedire l'interruzione
di tali processi a causa di interrupt (anche da parte del clock) o rischedulazione.
Le procedure eseguite in modo non interrompibile devono quindi essere brevissime.
Un processo puo' essere:
Transizioni possibili
Unix e' nato come Sistema Time Sharing, poi ampliato per la gestione
di job batch.
Possiede uno scheduler di tipo multilivello con feedback per
favorire i processi interattivi che utilizzano brevi burst di CPU.
Ad ogni processo e' assegnato un numero di priorita', che cambia in rapporto alla modalita' di esecuzione corrente. La priorita' e' inversamente proporzionale al numero.
Il valore di soglia che divide le due priorita' e' fisso.
I processi in modo utente sono eseguiti in Round Robin, mentre i processi
in modo kernel interrompibili possono solo essere sospesi per lasciare
la CPU a processi di maggiore priorita', in seguito quindi all'arrivo di
una interruzione collegata.
Figura 5.3
Esempi di operazioni con context switch:
Calcolo delle priorita': esempio VAX-Unix
La struttura Proc contiene lo stato di un processo che risiede in memoria.
Categoria Nome Descrizione
scheduling p_pri priorita' corrente p_usrpri user priority p_pcpu user requested priority p_sleeptime tempo di attesa in stato wait identifier p_pid process identifier p_ppid parent identifier p_uid user identifier .... ........ .........
La priorita' di un processo e' indicata da un numero compreso fra 0
e 127.
Il livello di soglia (puser) ' 50 (massima priorita' per l'utente).
Esistono pero' solo 32 code ready, una ogni 4 gradi di priorita'. Si tratta
di un compromesso fra efficienza e precisione.
La variabile PC indica il processo correntemente in escuzione (stato running).
Il tick e' di 10 millisecondi, il quanto di tempo e' di 10 tik, cioe' 100 millisec. Il conteggio non e' preciso: anche l'interruzione del clock e' sospesa quando c'e' in esecuzione un processo in priorita' non interrompibile.
p_cpu: stima del tempo di CPU recentemente utilizzato.
p_nice: valore modificabile dall'utente (superuser) da -20 a +20,
normalmente =0 (-20 corrisponde ad un aumento della priorita').
p_usrpri: priorita' corrente di un processo running o ready. Cambia
con il tempo per i processi in coda ready utente.
Calcolo della priorita' del processo running
Un processo kernel non cambia di priorita' in esecuzione e non puo' essere
sospeso per fine quanto di tempo.
Quando il processo running e' in modo utente, ad ogni tick il suo valore
di p_pcpu e' incrementato di 1 unita'.
Ad ogni quanto di tempo scaduto si ricalcola la sua priorita' secondo
la formula:
FP: p_usrpri = puser + (p_pcpu / 4) +
2 * p_nice
E' una priorita' user, quindi deve essere comunque inferiore a puser
(viene eventualmente troncata) e inferiore a 127. Il processo utente,
avendo terminato il suo quanto, viene sospeso e messo nella coda user corrispondente
alla sua nuova priorita', che puo' quindi diminuire.
Calcolo della priorita' del processo ready
Ad ogni secondo il valore p_pcpu di ogni processo utente nella ready
queue e' ricalcolato in base alla formula di "decadimento":
FD: p_pcpu = (2 * load)
/ (2 * load + 1) * p_pcpu
load e' il valore medio della lunghezza delle code user nel precedente
minuto.
La priorita' di ogni processo, cioe' il valore p_usrpri, e' poi
ricalcolato con la formula FP.
I processi ready vengono spostati alla coda superiore se la loro priorita'
e' aumentata.
Calcolo della priorita' del processo sleeping
Quando un processo passa da sleeping a ready, la sua priorita' di ingresso
in una coda user, cioe' il suo nuovo valore p_usrpri, viene calcolata
in base al nuovo valore p_pcpu:
p_pcpu = (((2 * load) / 2 * load + 1)) ** p_slptime) * p_pcpu
load e' il carico attuale, non quello del momento in cui il processo
e' entrato in stato sleepimg.
Unix ha anche un medium term scheduler.
Thrashing detection.
Il S.O. osserva la quantita' di memoria libera e la velocita' nel soddisfare
le richieste. Quando ci sono poche pagine di memoria libere e tante richieste,
si e' in una situazione di thrashing. Unix cerca di eliminarlo trovando
i 4 processi piu' grandi (che occupano piu' memoria) e facendo uno swap
out di quello che e' stato residente in memoria per piu' tempo. Si distribuisce
poi la memoria liberata. Se c'e' ancora thrashing, si cerca un altro processo
da sospendere. In ogni caso i processi sospesi tornano dopo al massimo
20 secondi.