SO-II-4p-Sistemi Operativi

7/24/2019 SO-II-4p-Sistemi Operativi

1/14

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

Parte II

Processi e Thread


Processi

Concetto fondamentale per lo svluppo dei sistemioperativi, e di applicazioni complesse

Permette di decomporre lapplicazione in un insieme diprocessi sequenziali

I processi vengono elaborati a rotazione sulla CPU Su di un sistema uniprocessore lelaborazione in realt

non parallela mapseudoparallela Il programmatore pu concentrarsi sul singolo processo

come se avesse a disposizione lintero sistema Solo le interazioni esplicite con gli altri processi devonoessere 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 Allatto della creazione il SO li prende in carico e ne fa

avanzare lesecuzione, secondo precise politiche

Processi di sistema eprocessi 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 dellutente

Per servire una richiesta dellutente Per avviare lesecuzione di un job batch


2/14


Terminazione di processi

I processi possono terminare per cause diverse e conmodalit 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 Nellambito 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 inprocess group In Windows il concetto pi sfumato: i padri possono inqualche modo cedere i loro diritti sui figli


Stati fondamentali di un processo

Un processo si trova a rotazione in uno dei tre statiRunning: in esecuzione sulla CPU

Ready: pronto ad eseguire appena gli viene concessa la CPUBlocked: in attesa di un evento per riprendere lesecuzione


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 checausa il blocco, es. richiesta di I/O, attesa di segnale

Tra blocked e ready: dal verificarsi dellevento di cui ilprocesso in attesa, es. fine I/O, ricezione di segnale

In tutti i casi il cambiamento viene indotto da una trap o dauna interruzione

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

Cambiamenti di stato


3/14


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

Sistemi Operativi - prof. Silvio Salza - a.a. 2008-2009 I I - 10

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, laProcess 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 lostesso processo, che ne condividono le risorse

Ciascuna di queste denominata thread

I moderni sistemi operativi supportano i thread


4/14


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 stessoprocesso

Altri sono replicati per ogni thread Il SO mantiene parte dellinformazione 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 threadper ogni nuovarichiesta 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


5/14


Esempio: Web server

Il dispatcherriceve le richieste e le alloca Ogni richiesta viene assegnata ad uno worker Gli workerse 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 allapplicazione Possibile servire pi richieste contemporaneamente

Quando alcuni thread sono bloccate, altri possonoessere ready ed andare in esecuzione sulla CPU

Semplifica lo sviluppo dellapplicazione Tutti i dettagli dellelaborazione concorrente di pi

richieste sono gestite implicitamente

Il programmatore non deve tener conto di questi dettagli

Rende lesecuzione complessiva pi leggera


Esempio: word processor

Possibile avere un thread per ciascun documento apertocontemporaneamente

Fanno tutti la stessa cosa su documenti diversi

Possibile avere anche pi thread per gestire un solodocumento Gestione interfaccia Gestione dei backup periodici Riformattazione del documento

ES

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


6/14


Esempio: Power Point

Erano aperti tre documenti


Dati processo


Dati thread


Comunicazione tra processi

Processi e thread sono spesso cooperanti nellambito diuna stessa applicazione o di uno stesso sistema

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

della esecuzione Lassenza di sincronizzazione pu condurre ad una

esecuzione i cui risultati dipendono da circostanzeesterne (es. ordine di scheduling)

Sincronizzazione necessarie in presenza di condizioni dicorsa (race conditions)


7/14


8/14


Corse critiche e stallo

La mutua esclusione pu solo essere garantita tramitemeccanismi e primitive offerte dal SO

Le soluzioni proposte devono aggirare due problemi tra lorocontrastanti

I processi devono poter essere bloccati per evitare cheentrino in pi di uno nella sezione critica

Lesistenza di situazioni di blocco anche temporaneopu causare situazioni di stallo e di attesa indefinita

Purtroppo tutte le soluzioni proposte sono relativamentecomplesse, ed implicano un dispendio di risorse


Atomicit delle operazioni

Un processo prima di entrare nella sezione critica deveeffettuare due operazioni:

1. Controllare se la sezione libera

2. Entrare nella sezione, se essa libera

Alle due operazioni corrispondono almeno due istruzionimacchina, in genere molte di pi

Lelaborazione di un processo pu essere interrotta dopoqualsiasi istruzione macchina

Lintera azione non atomica cio indivisibile, e questopu provocare situazioni scorrette


Corsa critica: esempio

I due ProcessiA 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 linformazione

Lelaborazione di A viene interrotta Viene ripresa lelaborazione di B B controlla se la sezione critica libera La sezione critica libera e B memorizza linformazione B entra nella sezione critica B continua a lavorare nella sezione critica Lelaborazione di B viene interrotta Viene ripresa lelaborazione di A A entra nella sezione critica (aveva gi controllato)

SiaA 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 LOCK

2. Se LOCK=0 pone LOCK=1

3. Entra

Siccome i passi 1. e 2. richiedono istruzioni distinte, lacorsa critica si riproduce nellaccesso a LOCK

La soluzione non funziona


9/14


Alternanza stretta (busy waiting)

Corretta ma estremamente inefficiente

Un processo pu attendere anche se laltro non nellasezione critica Viola una delle condizioni


TSL (Test Set an Lock)

Soluzione che richiede laggiunta di una istruzione macchina In una sola azione ininterrompibile la TSL op1,op2

Copia il valore delloperando op2 in op1 Forza il valore di op2 ad 1


Esempio: produttore - consumatore

Lavora se trova

uno slot pieno

ConsumatoreProduttore

Lavora se trova

uno slot libero

Buffer

N slot

I due processi condividono il buffer Ilproduttore 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 ilbuffer pieno

3. Il consumatore vada in condizione di blocco quando ilbuffer vuoto

4. Il produttore venga risvegliato se in blocco e si liberauna slot

5. Il consumatore venga risvegliato se in blocco e vieneriempita una slot


10/14


11/14


Richieste di CPU (burst)

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


Obiettivi dello scheduling

Lassegnazione della CPU ai processi (thread) che sononello stato ready fatta dal processo scheduler

Vengono utilizzati particolari discipline di scheduling, basatisu criteri diversi, e spesso contrastanti

massimizzare lutilizzazione della CPU

minimizzare il tempo di esecuzione di unprocesso/thread

minimizzare il tempo di risposta, attesa prima che unprocesso produca un output


Obiettivi e tipologie di sistemi


Priorit e prelazione

Ai processi e ai thread possono essere associateprioritper avvantaggiarli o per penalizzarli:

Priorit statiche: sono una caratteristica intrinseca

dei processi

Priorit dinamiche: dipendono dai livelli di servizioconseguiti finora dal processo/thread

Lo schema di assegnazione delle priorit pu esseremodificato dallo amministratore del sistema

Laprelazione un caso estremo di priorit: consente disottrarre la CPU ad un processo in stato running


12/14


Scheduling nei sistemi batch

Obiettivi Massimizzare lutilizzazione della CPU

Massimizzare il throughput(job/ora)

Minimizzare il tempo di turnaround(media del tempo trala sottomissione e la fine del job)

Non interessa il tempo di risposta perch gli utenti non sonointerattivi

Molti grandi sistemi centralizzati hanno una parte del caricocostituita da job batch

Il carico batch viene elaborato a sistema scarico (a notte)


Scheduling nei sistemi interattivi

Lobiettivo prioritario di minimizzare i tempi di risposta

Si tende a favorire i processi con comportamento I/Obound, 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 finoal suo completamento, o fino a quando esso non la rilasciaspontaneamente

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 inbase alle esperienze recenti

Disciplina interessante perch garantisce minimizzazionedel tempo medio di risposta

Per causa un peggioramento della varianza del tempo dirisposta

Interessante soprattutto in contesti interattivi


13/14


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 nonsfruttano 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 nellordine, solo se le classisuperiori 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 burstdi CPU

richiesti dai vari processi

Ci si basa sulla storia passata per aggiornare la stima Sia n la stimaaccumulata 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


14/14


Guaranteed scheduling

Lidea quella che ciascun processo abbia la fetta di CPUche 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 pibasso


Scheduling nei sistemi real-time

Elaborazione basata su eventi al cui servizio sonoassociate scadenze (deadline)

Creato un processo per ogni evento, con vita breve ecomportamento prevedibile

Obiettivo dello scheduler: fare in modo che le deadline deiprocessi siano rispettate (in modo hardo soft)

Due tipi di eventi

Periodici: si presentano ad intervalli regolariAperiodici: 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 eperiodo Pi , la condizione

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

(2)

1

1

m

i

i i

C

P=

SO-II-4p-Sistemi Operativi

Documents

Transcript of SO-II-4p-Sistemi Operativi