Parte II Processi e Thread - diag.uniroma1.itsalza/SO/SO-II-1p.pdf · Sistemi Operativi - prof....

Sistemi Operativi - prof. Silvio Salza - a.a. 2008-2009 II - 1

Parte II

Processi e Thread


Processi

• Concetto fondamentale per lo svluppo dei sistemi operativi, e di applicazioni complesse

• Permette di decomporre l’applicazione in un insieme di processi sequenziali

• I processi vengono elaborati a rotazione sulla CPU• Su di un sistema uniprocessore l’elaborazione in realtà

non è parallela ma pseudoparallela• Il programmatore può concentrarsi sul singolo processo

come se avesse a disposizione l’intero sistema• Solo le interazioni esplicite con gli altri processi devono

essere considerate


Processi

• Solo un programma è attivo in ogni istante• La multiprogrammazione virtualizza la CPU• È come se ogni processo avesse una CPU per se• Il SO mantiene sotto controllo lo stato dei processi


Creazione di processi

• I processi vengono creati per svolgere precisi compiti• All’atto della creazione il SO li ‘prende in carico’ e ne fa

avanzare l’esecuzione, secondo precise politiche• Processi di sistema e processi utente• Situazioni in cui vengono creati processi

– Al bootstrap del SO– Viene avviato un primo processo (iniziatore)– Questo crea altri processi per i servizi del SO– Alcuni processi accettano richieste dell’utente

– Per servire una richiesta dell’utente– Per avviare l’esecuzione di un job batch


Terminazione di processi

• I processi possono terminare per cause diverse e con modalità diverse

• Questo può avvenire con o senza il loro ‘consenso’• Tipiche situazioni di terminazione

– Uscita normale (volontaria)

– Uscita per errore (volontaria)

– Fatal error (involontaria)

– Ucciso da un altro processo (involontaria)


Gerarchie di processi

• Un processo può creare un altro processo– Processo genitore (parent process)– Processo figlio (child process)

• I figli possono creare altri figli: ‘crescete e riproducetevi’• Nell’ambito della gerarchia i padri (e gli avi) conservano

particolari diritti sui figli, per esempio quello di ucciderli• UNIX ha un concetto chiaro e netto di gerarchia, e

organizza i processi in process group• In Windows il concetto è più sfumato: i padri possono in

qualche modo cedere i loro diritti sui figli


Stati fondamentali di un processo

• Un processo si trova a rotazione in uno dei tre stati

–Running: è in esecuzione sulla CPU

–Ready: pronto ad eseguire appena gli viene concessa la CPU

–Blocked: in attesa di un ‘evento’ per riprendere l’esecuzione


• I cambiamenti di stato sono indotti:– Tra ready e running (e vice-versa): dallo scheduler, il

processo del SO che assegna la CPU– Tra running e blocked: dal verificarsi di un evento che

causa il blocco, es. richiesta di I/O, attesa di segnale…– Tra blocked e ready: dal verificarsi dell’evento di cui il

processo è in attesa, es. fine I/O, ricezione di segnale• In tutti i casi il cambiamento viene indotto da una trap o da

una interruzione • Le trap e le interruzioni vengono gestite dal (micro)kernel

Cambiamenti di stato


Stati dei processi

• Oltre agli stati fondamentali esistono molti altri stati• Definizioni sofisticate e dipendenti dal SO• Tipicamente lo stato contiene informazioni su

– Comportamento del processo in tempi recenti– Risorse possedute dal processo, e.g. memoria– Priorità

• Alcuni esempi– Sleeping– Hybernate


Implementazione dei processi

• Il sistema operativo mantiene per ciascun processo tutte le informazioni necessarie a gestirlo

– Identificazione e gerarchia– Risorse assegnate– Stato del processo– Stato della CPU etc.

• Le informazioni sono riunite in una apposita struttura, la Process Table

• La struttura differisce nei dettagli a seconda del SO


La Process Table


Thread

• In un processo è possibile distinguere due componenti– Le risorse allocate al processo: files aperti, processi

figli, etc. (vedi Process Table)– La sua esecuzione: e tutti i dettagli relativi, stato della

CPU, stack etc.• È pensabile e vantaggioso avere più esecuzioni per lo

stesso processo, che ne condividono le risorse• Ciascuna di queste è denominata thread• I moderni sistemi operativi supportano i thread


Thread e processi

(a) Tre processi ciascuno con un unico thread(b) Un unico processo con tre thread


Thread e processi (2)

• Alcuni item sono condivisi da tutti i thread di uno stesso processo

• Altri sono replicati per ogni thread• Il SO mantiene parte dell’informazione a livello di thread


Gestione dello stack

• Ogni thread ha il proprio stack• Tutte le variabili locali si mantengono distinte


Benefici del multithreading

• Creazione e terminazione di un thread molto più leggere• Modularità e flessibilità delle applicazioni • Implementazione di server concorrenti:

– creazione dinamica di un thread per ogni nuova richiesta di servizio

– gestione implicita della concorrenza• Parallelismo di esecuzione: uno stesso processo può essere

elaborato in parallelo da più processori• Aumento del livello di multiprogrammazione: migliore

utilizzazione della/e CPU


Esempio: Web server

• Il dispatcher riceve le richieste e le alloca• Ogni richiesta viene assegnata ad uno worker• Gli worker se non occupati ‘dormono’


Web server: schema del codice

(a) Schema del codice del dispatcher(b) Schema del codice dello worker


Web server con thread: vantaggi

• Aumenta il parallelismo all’applicazione– Possibile servire più richieste contemporaneamente– Quando alcuni thread sono bloccate, altri possono

essere ready ed andare in esecuzione sulla CPU • Semplifica lo sviluppo dell’applicazione

– Tutti i dettagli dell’elaborazione concorrente di piùrichieste sono gestite implicitamente

– Il programmatore non deve tener conto di questi dettagli• Rende l’esecuzione complessiva più leggera


Esempio: word processor

• Possibile avere un thread per ciascun documento aperto contemporaneamente

• Fanno tutti la stessa cosa su documenti diversi• Possibile avere anche più thread per gestire un solo

documento– Gestione interfaccia– Gestione dei backup periodici– Riformattazione del documento

ESCon tre documenti aperti su Power Point, possocontrollare sul Task Manager, e vedo che ho 8 thread


Esempio: Power Point

Erano aperti tre documenti


Dati processo


Dati thread


Comunicazione tra processi

• Processi e thread sono spesso cooperanti nell’ambito di una stessa applicazione o di uno stesso sistema

• Per cooperare necessitano di– Scambiarsi informazioni (dati, messaggi)– Sincronizzarsi, per garantire la correttezza della esecuzione

• L’assenza di sincronizzazione può condurre ad una esecuzione i cui risultati dipendono da circostanze esterne (es. ordine di scheduling)

• Sincronizzazione necessarie in presenza di ‘condizioni di corsa’ (race conditions)


Condizioni di corsa: esempio

• Due processi cercano di accedere ‘contemporaneamente’alla stessa slot nella directory di spool

• Se lo scheduler ci mette lo zampino, possono finire per assegnarsi la stessa slot


Sezione critica

• Per evitare le condizioni di corsa occorre individuare una sezione critica nel codice di ciascuno dei due processi

La sezione critica racchiude un insieme di operazioni la cui esecuzione non può essere interrotta

• Le condizioni di corsa si possono verificare se entrambi i processi si trovano nella sezione critica

• Occorre imporre la mutua esclusione nell’accesso alla sezione critica

• Se un processo entra, l’altro deve aspettare che esca


Condizioni per la mutua esclusione

Per assicurare una soluzione corretta ed efficiente alla mutua esclusione occorre garantire le seguenti condizioni

– Mai due processi devono poter essere nella loro sezione critica contemporaneamente

– Deve funzionare indipendentemente dal numero e dalla velocità delle CPU

– Nessun processo al di fuori della sua sezione critica deve poter bloccare un altro processo

– Nessun processo deve poter aspettare indefinitamente per entrare nella sua sezione critica


Sezione critica e mutua esclusione


Corse critiche e stallo

• La mutua esclusione può solo essere garantita tramite meccanismi e primitive offerte dal SO

• Le soluzioni proposte devono aggirare due problemi tra loro contrastanti

– I processi devono poter essere bloccati per evitare che entrino in più di uno nella sezione critica

– L’esistenza di situazioni di blocco anche temporaneo può causare situazioni di stallo e di attesa indefinita

• Purtroppo tutte le soluzioni proposte sono relativamente complesse, ed implicano un dispendio di risorse


Atomicità delle operazioni

• Un processo prima di entrare nella sezione critica deve effettuare due operazioni:

1. Controllare se la sezione è libera2. Entrare nella sezione, se essa è libera

• Alle due operazioni corrispondono almeno due istruzioni macchina, in genere molte di più

• L’elaborazione di un processo può essere interrotta dopo qualsiasi istruzione macchina

• L’intera azione non è ‘atomica’ cioè indivisibile, e questo può provocare situazioni scorrette


Corsa critica: esempioI due Processi A e B condividono una sezione critica e si alternano sulla sezione critica

• A controlla se la sezione critica è libera• La sezione critica è libera e A memorizza l’informazione• L’elaborazione di A viene interrotta• Viene ripresa l’elaborazione di B• B controlla se la sezione critica è libera• La sezione critica è libera e B memorizza l’informazione• B entra nella sezione critica• B continua a lavorare nella sezione critica• L’elaborazione di B viene interrotta• Viene ripresa l’elaborazione di A• A entra nella sezione critica (aveva già controllato)

Sia A che B si trovano nella sezione critica


Soluzione ingenua

• Proteggere la sezione critica con un flag LOCK– LOCK=0: sezione critica libera– LOCK=1: sezione critica occupata

• Un processo prima di entrare1. Controlla LOCK2. Se LOCK=0 pone LOCK=13. Entra

• Siccome i passi 1. e 2. richiedono istruzioni distinte, la corsa critica si riproduce nell’accesso a LOCK

• La soluzione non funziona


Alternanza stretta (busy waiting)

• Corretta ma estremamente inefficiente• Un processo può attendere anche se l’altro non è nella

sezione critica • Viola una delle condizioni


TSL (Test Set an Lock)

• Soluzione che richiede l’aggiunta di una istruzione macchina• In una sola azione ininterrompibile la TSL op1,op2

– Copia il valore dell’operando op2 in op1– Forza il valore di op2 ad 1


Esempio: produttore - consumatore

Lavora se trovauno slot pieno

ConsumatoreProduttore

Lavora se trovauno slot libero

Buffer

N slot

• I due processi condividono il buffer• Il produttore scrive nel buffer se trova almeno una slot libera;

se no attende• Il consumatore legge dal buffer se trova almeno una slot

piena; se no attende


Produttore - consumatore: problemi

Una soluzione al problema deve garantire che

1. I due processi non manipolino contemporaneamente il buffer (sezione critica)

2. Il produttore vada in condizione di blocco quando il buffer è pieno

3. Il consumatore vada in condizione di blocco quando il buffer è vuoto

4. Il produttore venga risvegliato se è in blocco e si libera una slot

5. Il consumatore venga risvegliato se è in blocco e viene riempita una slot


Semafori

• Variabili intere di sistema non negative modificabili solo tramite due primitive atomiche (ininterrompibili):

• DOWN(S) – S > 0 : S ← S - 1– S = 0 : il processo attende su S

• UP(S)– S > 0 : S ← S + 1– S = 0 : S ← S + 1; risveglia i processi in attesa su S

• L’esecuzione delle primitive UP e DOWN è garantita dal SO


Semafori binari

• Sono un caso particolare: S ∈ {0,1}• Vengono usati per controllare l’accesso ad una sezione

critica:– Quando la sezione critica è libera: S=1– Per entrare un processo fa DOWN(S), quindi S diventa 0– Se un processo trova S=0 si mette in attesa– Quando il processo esce dalla sezione critica, fa UP(S) e

sveglia un eventuale processo in attesa


Produttore-Consumatore con semafori


Scheduling

• L’assegnazione della CPU ai processi (thread) che sono nello stato ready è fatta dal processo scheduler

• Vengono utilizzati particolari discipline di scheduling, basati su criteri diversi, e spesso contrastanti

– massimizzare l’utilizzazione della CPU– minimizzare il tempo di esecuzione di un

processo/thread– minimizzare il tempo di risposta, attesa prima che un

processo produca un output


Richieste di CPU (burst)

• Molto variabili e dipendono dalla natura del processo– (a) CPU bound– (b) I/O bound


Obiettivi dello scheduling

• L’assegnazione della CPU ai processi (thread) che sono nello stato ready è fatta dal processo scheduler

• Vengono utilizzati particolari discipline di scheduling, basati su criteri diversi, e spesso contrastanti

– massimizzare l’utilizzazione della CPU– minimizzare il tempo di esecuzione di un

processo/thread– minimizzare il tempo di risposta, attesa prima che un

processo produca un output


Obiettivi e tipologie di sistemi


Priorità e prelazione

• Ai processi e ai thread possono essere associate prioritàper avvantaggiarli o per penalizzarli:

– Priorità statiche: sono una caratteristica intrinseca dei processi

– Priorità dinamiche: dipendono dai livelli di servizio conseguiti finora dal processo/thread

• Lo schema di assegnazione delle priorità può essere modificato dallo amministratore del sistema

• La prelazione è un caso estremo di priorità: consente di sottrarre la CPU ad un processo in stato running


Scheduling nei sistemi batch

• Obiettivi– Massimizzare l’utilizzazione della CPU– Massimizzare il throughput (job/ora)– Minimizzare il tempo di turnaround (media del tempo tra

la sottomissione e la fine del job)• Non interessa il tempo di risposta perché gli utenti non sono

interattivi• Molti grandi sistemi centralizzati hanno una parte del carico

costituita da job batch• Il carico batch viene elaborato a sistema scarico (a notte)


Scheduling nei sistemi interattivi

• L’obiettivo prioritario è di minimizzare i tempi di risposta• Si tende a favorire i processi con comportamento I/O

bound, a scapito dei CPU bound• Non ha senso lo scheduling a tre livelli• Ha senso uno scheduling a due livelli

– Memory scheduling– CPU scheduling

• Di seguito si discute il CPU scheduling


Scheduling FCFS

• FCFS: First Come First Served• I processi vengono mandati in esecuzione nello stesso

ordine in cui sono entrati nella ready list• Non vi è prelazione: ogni processo rimane sulla CPU fino

al suo completamento, o fino a quando esso non la rilascia spontaneamente

• Penalizza i processi I/O bound che chiedono poca CPU • Favorisce i processi CPU bound• Causa un sottoutilizzo dei dispositivi di I/O


Scheduling SSTF

• SSTF: Shortest Service Time First• Viene scelto sempre il processo che richiede il tempo di

servizio più corto• I tempi di servizio richiesti non sono noti: vengono previsti in

base alle esperienze recenti • Disciplina interessante perché garantisce minimizzazione

del tempo medio di risposta• Però causa un peggioramento della varianza del tempo di

risposta• Interessante soprattutto in contesti interattivi


Scheduling SSTF: esempio

(a) FCFS (8,4,4,4)

– Tempo totale 20– Tempo medio 13.5– Tempo minimo 8– Tempo massimo 20

(b) SSTF (4,4,4,8)

– Tempo totale 20– Tempo medio 11– Tempo minimo 4– Tempo massimo 20


Scheduling Round-Robin

• Round-Robin : la giostra• Ciascun processo/thread resta sulla CPU al massimo per

un tempo τ, detto quantum• Trascorso questo viene reinserito alla fine della coda• Processi I/O-bound: fanno prevalentemente I/O e non

sfruttano quasi mai il tempo di CPU concesso• Processi CPU-bound: utilizzano tutto il tempo di CPU

concesso, e devono fare molti giri

richiesta di I/O fine processo

CPU

tempo scaduto

processi ready


Round-Robin a code multiple

• Classi di priorità servite nell’ordine, solo se le classi superiori sono esaurite

• Priorità dinamiche usate per riparare alle ‘ingiustizie’


Shortest process next

• Viene scelto il processo con la minore richiesta di CPU• Problema: stimare a priori la durata dei burst di CPU

richiesti dai vari processi• Ci si basa sulla storia passata per aggiornare la stima• Sia Θn la stima accumulata al passo n e Tn il tempo

effettivamente sperimentato• La nuova stima sarà Θn+1 = α Θn+ (1- α) Tn

• La costante α permette di stabilire quanto pesa la storia passata e quanto quella recente

• La tecnica di previsione si chiama aging


Guaranteed scheduling

• L’idea è quella che ciascun processo abbia la fetta di CPU che gli spetta da una divisione equa

• Se i processi sono n la sua share dovrebbe essere 1/n• Si accumula per ciascuno il tempo totale di CPU goduto• Ad ogni passo si calcola per ogni processo il rapporto fra il

tempo goduto e quello spettante• Rapporti bassi significano ingiustizie subite• Lo scheduler sceglie sempre il processo con il rapporto più

basso


Scheduling nei sistemi real-time

• Elaborazione basata su eventi al cui servizio sono associate scadenze (deadline)

• Creato un processo per ogni evento, con vita breve e comportamento prevedibile

• Obiettivo dello scheduler: fare in modo che le deadline dei processi siano rispettate (in modo hard o soft)

• Due tipi di eventi– Periodici: si presentano ad intervalli regolari– Aperiodici: non prevedibili


Scheduling nei sistemi real-time

• In genere ci sono diverse serie di eventi periodici• Il requisito minimo e che il sistema possa sostenere il carico

(schedulable system)• Se ci sono m serie di eventi con richeste di CPU pari a Ci e

periodo Pi , la condizione è

• Scheduling di tipo statico o dinamico• Caso di particolare interesse i sistemi multimedia

(2)

11

mi

i i

CP=

≤∑

Parte II Processi e Thread - diag.uniroma1.itsalza/SO/SO-II-1p.pdf · Sistemi Operativi - prof....

Documents

Transcript of Parte II Processi e Thread - diag.uniroma1.itsalza/SO/SO-II-1p.pdf · Sistemi Operativi - prof....