Gestione dei processi
• Un sistema operativo multitasking è in grado di
gestire più processi
• Un processo corrisponde ad un programma in
esecuzione.
• Un programma tipicamente alterna sequenze di
istruzioni CPU ad operazioni di I/O
• Durante l’esecuzione di una operazione di I/O il
programma non utilizza la CPU, che pertanto può
essere assegnata dal sistema operativo ad un alto
processo
Il contesto del processo
• Rappresenta tutte le informazioni che descrivono
la “fotografia” corrente del programma in
esecuzione
• Alcune di queste informazioni sono:
– Il contenuto della memoria assegnata al processo
– Il contenuto attuale dei registri della CPU, incluso il
Program Counter, che determina lo stato di
avanzamento del programma
– Informazioni accessorie utilizzate dal sistema operativo
per la gestione del processo, quali la priorità corrente
• Tali informazioni, escluso il contenuto della
memoria sono memorizzate dal sistema operativo
nel Process Control Block associato .
Gli stati di un processo
• Definiscono se un processo è in esecuzione, o on
attesa.
• Gli stati sono:
– New: processo creato, non ancora entrato in esecuzione
– Running: il processo sta utilizzando la CPU
– Waiting: il processo è in attesa della terminazione di
un’operazione di I/O
– Ready: il processo potrebbe utilizzare la CPU, ma la
CPU è assegnata ad un altro processo
– Halted: il processo ha finito la sua esecuzione o è stato
stoppato dal sistema operativo (es. in conseguenza alla
generazione di un’eccezione)
La sequenza degli stati
L’operazione di Context Switch
La schedulazione (scheduling) dei processi
• Il sistema operativo ha generalmente più di un
processo candidato per l’utilizzo della CPU
(Ready)
• Tra le caratteristiche da tener conto nella
determinazione di un efficiente algoritmo di
scheduling sono le seguenti:
– Utilizzo della CPU: si cerca di massimizzare l’uso della
CPU
– Throughput: massimizzazione dei processi eseguiti
(terminati) per unità di tempo
– Tempo di risposta: minimizzazione del tempo di attesa
in stato Ready per ogni processo
Prima implementazione: FIFO
• L’utilizzo di una coda First-In-First out rappresenta
l’implementazione più semplice, ma anche la meno
efficiente.
• Si supponga, ad esempio, che nella coda siano tre processi
P1, P2, P3, con il processo P1 inserito per primo nella
coda. Si supponga inoltre che il processo P1 impiegherà la
CPU per un tempo di 100ms, mentre gli altri due processi
impiegheranno la CPU per un tempo di 1 ms.
• In questo caso il tempo medio di attesa risulterà pari a (100
+ 101)/3 ms.
• Se invece venissero eseguiti prima P2 e P3, il tempo medio
di attesa sarebbe, a parità di throughput: (1 + 2) /3 ms
Shortest Job First
• Con riferimento all’esempio precedente, si può
intuire che l’organizzazione ideale assegnerebbe la
CPU per prima al processo che la utilizzerà per il
tempo minore.
• Tale approccio non è tuttavia realizzabile in
pratica.
• E’ possibile dare una stima n+1 del tempo di
esecuzione previsto dopo n passi a partire dalla
stima precedentemente fatta (n) e dal tempo
effettivamente impiegato al passo precedente tn:
n+1 =  tn +(1- )n
La priorità dei processi
• In molte situazioni reali, esistono processi che
hanno una “importanza” maggiore, e pertanto per
tali processi risulta preferibile una maggiore
prontezza del sistema operativo nell’assegnazione
della CPU, a scapito di altri processi meno
importanti
• Ciò si può ottenere assegnando una priorità ai
processi.
• Il sistema operativo assegnerà la CPU al processo
Ready di priorità più alta.
Priorità fisse e variabili
• L’utilizzo di priorità fisse assegnante ai processi è adeguato
per alcune classi di utilizzi, tra cui i sistemi real-time.
• In altri utilizzi, quali gestione multi-utente, tale politica
non è ottimale in quanto rischia di creare lunghi tempi di
attesa per alcuni processi.
• In un sistema time sharing si vuole invece che la CPU
venga assegnata ai vari utenti in modo da minimizzare il
tempo di risposta.
• Ciò può essere realizzato tramite l’utilizzo di priorità
variabili: la priorità di processi che utilizzano
pesantemente la CPU viene abbassata, mentre la priorità di
processi che eseguono prevalentemente I/O viene elevata
La gestione della priorità variabile.
• Il meccanismo di cambio della priorità avviene
interrompendo periodicamente il processore, e
verificando il processo che sta correntemente
utilizzando la CPU.
• Ad ogni interruzione (tick) la priorità del processo
corrente può essere decrementata, mentre la
priorità degli altri processi può essere
incrementata.
• In questa maniera si “premiano” i processi che
eseguono prevalentemente I/O, con l’assunzione
che tali processi utilizzeranno la CPU per un
tempo breve prima di tornare nello stato wait
La gestione della priorità variabile (cont.)
• Conseguentemente, lo scheduler gestirà più code
FIFO di processi, una per ogni priorità.
• La CPU verrà assegnata al primo processo della
coda corrispondente alla priorità massima
• Ad ogni tick, i processi possono cambiare coda,
come conseguenza del loro “comportamento”
• Tale gestione pertanto fa si’ che il processo
selezionato per l’utilizzo della CPU la impegnerà
probabilmente per un tempo non più lungo rispetto
agli altri processi che in quel momento sono
ready.
Programmazione concorrente
• La programmazione concorrente definisce due o più flussi
di esecuzione tra loro indipendenti
• Le problematiche non cambiano anche considerando
sistemi a processore singolo, ma sistema operativo
multitasking
• La difficoltà nella dimostrazione della correttezza di tali
algoritmi deriva dalla necessità di tenere in considerazione
tutte le possibili combinazioni derivanti dalla esecuzione
indipendente dei programmi.
• Gli errori dovuti alla mancata considerazione di particolari
condizioni di esecuzione prendono il nome di “race
conditions”, e sono in genere molto difficili da
diagnosticare
Un esempio: l’implementazione di una
sezione critica
• Prende il nome di sezione critica un segmento di codice
che viene eseguito da non più di un processo per volta
• L’uso delle sezioni critiche è necessario per una gestione
opportuna delle risorse del sistema
• Molte risorse (ad esempio dispositivi di I/O) possono
infatti essere utilizzate solo da un processo per volta
• Più in generale, quando più di un processo condivide delle
strutture dati (ad esempio liste), ci si vuole assicurare che
solo un processo per volta modifichi tali strutture per
evitare situazioni di incosistenza
• Si consideri ad esempio l’utilizzo di una linked list
condivisa: se un processo viene interrotto dal SO nel
momento in cui sta modificando i riferimenti, altri processi
vedrebbero la lista in uno stato inconsistente
Requisiti dell’algoritmo
• L’algoritmo di mutua esclusione deve garantire i
seguenti requisiti:
– Mutua esclusione: solo un processo per volta deve
accedere alla sezione critica
– Progresso: se nessun processo sta accedendo alla
sezione critica, l’assegnazione della sezione critica ad
uno dei processi richiedenti deve avvenire in un tempo
finito (non può essere postposta indefinitamente)
– Attesa finita(bounded waiting): deve esistere un
limite finito al numero di volte in cui un processo in
attesa per l’accesso alla sezione critica vede negato
l’accesso a favore di un altro processo
Una prima implementazione della sezione critica
• Si consideri il problema dell’implementazione della
sezione critica per due processi, utilizzando variabili
condivise tra i due processi.
• In questa implementazione la struttura condivisa è un array
di due boolean:
var flag: array[0..1] of boolean
• Il processo Pi esegue le seguenti istruzioni (j si riferisce
all’indice dell’altro processo):
while(flag[j]) {//Ripeti il test}
flag[i] = true
… //Sezione critica
flag[i]= false
Analisi del primo algoritmo
• Ad una prima analisi l’algoritmo sembrerebbe garantire la
mutua esclusione: il processo Pi attende che il processo Pj
sia uscito dalla sezione critica (ovvero che flag[j] diventi
false) prima di entrare nella sezione critica.
• Una analisi più accurata rivela tuttavia che la mutua
esclusione non viene garantita in questa sequenza
(partendo da una condizione in cui nessun processo è nella
sezione critica):
– 1) P0 entra nel ciclo while e trova flag[1] false
– 2) P1 entra nel ciclo while e trova flag[0] false
– 3) P1 pone flag[1] a true ed entra nella sezione critica
– 4) P0 pone flag[0] a true ed entra nella sezione critica
Secondo algoritmo
• Visto che la race condition derivava dal fatto che il
processo Pi pone flag[i] = true dopo aver testato flag[j],
allora si può pensare di invertire le due operazioni,
ottenendo la sequenza:
flag[i] = true
while(flag[j]) {//Ripeti il test}
… //Sezione critica
flag[i]= false
Analisi del secondo algoritmo
• In questo caso la mutua esclusione viene
assicurata: infatti il processo i entra nella sezione
critica solo se flag[i] == true e flag[j] == false. Ma
la seconda condizione è verificata solamente se il
secondo processo non è nella sezione critica
• Tuttavia il requisito di progresso non è soddisfatto
dalla seguente possibile sequenza:
– 1) P0 pone flag[0] a true
– 2) P1 pone flag[1] a true
• In questa condizione i due processi si bloccano in
un’attesa infinita: si è generata una situazione di
deadlock
Algoritmo definitivo
• L’algoritmo di Peterson definisce una variabile booleana
aggiuntiva:In questa implementazione la struttura condivisa è un
array di due boolean:
var flag: array[0..1] of boolean
var turn: integer
• Il processo Pi esegue le seguenti istruzioni (j si riferisce
all’indice dell’altro processo):
flag[i] = true
turn = j
while(flag[j] and turn == j){}
//Ripeti il test
… //Sezione critica
flag[i]= false
Analisi dell’algoritmo di Peterson
• Mutua esclusione: quando Pi entra nella sezione critica o
flag[j] == false o turn = i. Se entrambi i processi sono nella
sezione critica, allora flag[0] e flag[i] sono true. Poiché la
variabile turn non può essere contemporaneamente i e j,
ciò significa che i due processi non possono essere entrati
contemporaneamente nella sezione critica. Inoltre quando
il primo dei due processi era entrato nella sezione critica,
l’altro processo doveva aver già assegnato la variabile turn.
A questo punto, tuttavia, quest’ultimo processo troverebbe
la seconda condizione true pertanto deve necessariamente
attendere che l’altro processo esca dalla sezione critica
Analisi algoritmo Peterson (Cont)
• Progresso: il processo Pi può essere bloccato prima di
entrare nella sezione critica solo e solo se flag[j] resta
true e turn resta a j. Se Pj è al di fuori della sezione
critica e non sta cercando di entrarci, allora flag[j] == false.
Se Pj ha posto flag[j] a true, allora sta cercando di entrare
nella sezione critica (eseguendo il loop while). La variabile
turn può avere solo i valori i o j, e pertanto o il processo j o
il processo i entrerà nella sezione critica (Progresso).
• Attesa finita: supponiamo che P1 e P0 continuino a
richiedere l’accesso alla sezione critica. In questo flag[0] e
flag[1] sono ripetutamente posti a true. Ciò significa che il
processo Pi riesce a superare il ciclo while in base alla
condizione turn == j. L’assegnazione della variabile turn
prima del ciclo while assicura che Pi non dovrà attendere
un numero indefinito di accessi di Pj prima di accedere a
sua volta alla sezione critica.