I Processi - Universita' degli Studi di Bari Aldo Moro

05/10/15

1

CdL MAGISTRALE in INFORMATICA

A.A. 2015-16

corso di SISTEMI DISTRIBUITI Modulo 2 > I processi : proprietà e multi-threading

Prof. S.Pizzutilo

CdL in Informatica- Magistrale Università di Bari Sistemi Distribuiti

I Processi

buffering

multidatagram

encoding/decoding

indirizzamento processi gestione failure

idempotenza

group communication

processi

comunicazione

naming sincronizzazione

sicurezza

concorrenza

05/10/15

2

I Processi

  Un processo è un programma in esecuzione identificato univocamente dall’identificatore di processo (un intero).

  Un processo necessita di alcune risorse per assolvere il proprio compito: tempo di CPU, memoria, file e dispositivi di I/O.

  Il S.O. è responsabile delle attività di gestione dei processi:   Creazione e cancellazione di processi.   Sospensione e riattivazione di processi.   Meccanismi per:

– sincronizzazione di processi – comunicazione fra processi

Comunicazione tra processi e Kernel : System Call

  Le chiamate di sistema definiscono l’interfaccia del programmatore verso il S.O.

  L’insieme dei programmi di sistema comunemente disponibili definisce invece l’interfaccia utente.

  Le interfacce del programmatore ed dell’utente definiscono il contesto che deve essere supportato dal kernel.

Ad esempio, in Unix si hanno, approssimativamente, tre categorie di chiamate di sistema :   Manipolazione di file (le stesse chiamate di sistema

supportano anche la manipolazione dei dispositivi).   Controllo dei processi.   Manipolazione dell’informazione.

05/10/15

3

Controllo dei processi

  System call per il controllo dei processi:   fork crea un nuovo processo   execve viene impiegata dopo una fork per rimpiazzare la

memoria virtuale di uno dei due processi (generalmente il “figlio”) con un nuovo programma

  exit termina un processo   Un “padre” può attendere (wait) la terminazione di un

processo “figlio”; wait fornisce il process id (pid) del figlio terminato, così da renderne nota l’identità al padre

  wait3 consente al padre di produrre statistiche sulla performance dei figli

  Processo zombie: processo terminato dopo il padre. CdL in Informatica- Magistrale

Università di Bari Sistemi Distribuiti

Stati di un processo

Ready pronto ad essere eseguito, ma non in esecuzione

running in esecuzione

waiting in attesa di un evento o di un dato

05/10/15

4

Transizioni fra gli stati di un processo

Ammissione tra i

processi pronti

READY! RUNNING!

WAITING!

Allocazione

Termina dopo quanto di tempo

Completamento evento atteso

(operazione di I/O )

Attesa di un evento

(operazione di I/O)

EXIT NEW

Rilascio

Transizioni fra gli stati   Il nucleo del SO maschera al processo la evoluzione nel tempo della sua

esecuzione eseguendo due operazioni :   Salvataggio del contesto del processo ogni volta che

viene interrotto

  Ripristino del contesto quando viene ad esso riassegnata la CPU

  La struttura dati che contiene le informazioni utili per il salvataggio e il ripristino del contesto è detta descrittore del processo

05/10/15

5

Gestione di processi

Il SO è responsabile delle seguenti attività in connessione con la gestione dei processi :   Creazione e cancellazione dei processi   Sospensione e riattivazione dei processi   Sincronizzazione dei processi   Comunicazione fra processi

  Il SO (e in particolare il suo nucleo) simula il parallelismo fra processi nel caso in cui sia presente un solo processore. In sistemi con più processori ogni processo è assegnato ad un processore diverso

  Il comportamento di un singolo processo è caratterizzato elencando la relativa sequenza di istruzioni eseguite. Tale elenco è detto traccia del processo.

  Il comportamento del processore è caratterizzato mostrando come sono interallacciate le tracce dei diversi processi.

Stati dei processi

05/10/15

6

Strutture di controllo dei processi

Per gestire processi e risorse il SO costruisce tabelle di informazioni relative a ciascuna delle entità che gestisce

Processi interlacciati

Traccia di A Traccia di

B Traccia di C

•  N u m e r o d i istruzioni eseguite da ogni processo: al massimo 6

• Indirizzo di inizio de l programma allocatore : 100 • I l p r o c e s s o B e s e g u e 4 istruzioni, l’ultima d e l l e q u a l i r i c h i e d e u n a operazione di I/O

A

B

C

A

C

05/10/15

7

Strutture di controllo dei processi

  Elementi tipici di una Process Image (immagine del processo):   Programma utente : programma o insieme di

programmi che devono essere eseguiti   Dati utente : insieme di locazioni per i dati, per la

variabili globali o locali, per le costanti   Stack di sistema : uno o più stack utilizzati per

memorizzare parametri ed indirizzi per le chiamate di procedure

  Process control block : dati che servono al SO per controllare il processo

  Identificatori del processo: informazioni sullo stato del processo, informazioni di controllo

Determinazione dello stato dei processi

Lo stato di un processo è determinato mediante:

  Strategie di accodamento dei processi in uno stato (Coda dei processi ready e Coda dei processi blocked )

  Politiche di gestione (Scheduling e Livelli di

priorità)

05/10/15

8

Politiche di gestione dei processi

Livelli di priorità dei processi Priorità legata al tipo di utente che detiene il processo :

  Livello utente : processi responsabili dell’esecuzione di programmi utente

  Livello supervisore : processi responsabili di alcune funzioni del SO

  Livello di I/O : processi di servizio degli interrupt   Livello delle eccezioni : processi responsabili della integrità del

sistema e processi che gestiscono errori ed eccezioni dovute ad esecuzione non corretta di programmi utente

bassa

alta

prio

rità

Scheduling Il SO alloca le risorse tra le potenziali necessità concorrenti di molti processi. ü  Nel caso del processore la risorsa da allocare è il tempo d’esecuzione e la tecnica

di allocazione è lo scheduling. ü  In un sistema multiprogrammato, più processi indipendenti sono mantenuti in

memoria e la CPU è assegnata loro dinamicamente. ü  necessità di algoritmi di schedulazione dei processi .

Politiche di gestione dei processi

Algoritmo di scheduling - stabilisce a quali processi assegnare la CPU, per quanto tempo e in quale momento, - deve soddisfare i seguenti requisiti:

ü  imparzialità: garantire che ogni processo abbia un’equa porzione (time-slice ) di tempo di CPU

ü  efficienza: rendere massimo il throughput (numero di lavori eseguiti nell’unità di tempo)

ü  velocità: minimizzare il tempo di risposta o Turnaround Time (intervallo di tempo tra l’invio di un processo e il suo completamento)

“First Come First Served” Semplice strategia di scheduling che tende a favorire i processi processor-bound rispetto a quelli I/O-bound:

o  quando un processo diventa ready è inserito nella coda ready, o  quando il processo al momento in esecuzione è sospeso, il più vecchio processo

nella coda ready è selezionato per l’esecuzione.

05/10/15

9

Algoritmi di scheduling

“Round Robin” Ad ogni processo è assegnato un intervallo di tempo (time slice) costante, detto ‘quanto ’, per l’utilizzo della CPU; non appena termina il quanto di un processo, esso è posto in stato di ready e la CPU è assegnata ad un altro processo.

  Vantaggio: facile implementazione •  è sufficiente mantenere la lista dei processi in stato di ready •  allo scadere del quanto, il processo è messo in coda alla lista

  Svantaggio: non tiene conto di priorità legate alle caratteristiche dei processi •  i processi I/O bound sono penalizzati rispetto a quelli CPU bound

  Problema: fissare la durata del “quanto” Ø  troppo piccolo --> bassa efficienza: la CPU sarà impegnata per gran parte del tempo nel

controllo dei frequenti passaggi da un processo ad un altro Ø  troppo grande -->bassa velocità: tempi di risposta lunghi

“Shortest Process Next” Il processo con il minor tempo di esecuzione previsto è selezionato come successivo processo da eseguire. §  Necessità di conoscere a priori i tempi di esecuzione di ciascun processo. §  Difficile applicabilità a processi interattivi, la cui durata non è nota a priori

Algoritmi di scheduling

“Priority” Ad ogni processo viene assegnata una priorità e viene concessa l’esecuzione al processo in stato di ready con priorità più alta Le priorità possono essere assegnate:

ü  staticamente ü  dinamicamente : le priorità vengono modificate durante l’esecuzione, in base al tipo di

processo (I/O bound o CPU bound) “Code multiple”

I processi vengono suddivisi in classi di diversa priorità e l’algoritmo utilizza diverse code di processi in stato di ready, una per ogni classe di priorità.

Ad ogni processo sono assegnati più quanti di tempo, a seconda della classe di priorità a cui appartiene ü  priorità maggiore --> n.ro di quanti minore

Non appena un processo termina tutti i suoi quanti, viene spostato nella classe con priorità inferiore (n.ro di quanti maggiore)

ü  per ogni processo si riduce il numero di passaggi allo stato di ready per concludere la sua esecuzione,

ü  man mano che un processo scende nelle classi, otterrà la CPU sempre meno frequentemente lasciandola libera per i processi che richiedono poco tempo di CPU.

05/10/15

10

Concorrenza fra processi

La esecuzione concorrente di più processi può portare a notevoli benefici rispetto alla esecuzione rigidamente sequenziale : ü  Aumento dell’utilizzo della CPU nei sistemi a partizione di tempo, ove si

eseguono lavori quasi parallelamente. ü  Suddivisione del carico computazionale su più processi in esecuzione

contemporanea su più CPU di uno stesso sistema o, analogamente, sulle CPU di diversi calcolatori collegati in rete.

ü  Condivisione della stessa risorsa fisica fra diversi utenti in modo trasparente e controllato.

ü  Accesso contemporaneo, da parte di diversi utenti ad una base dati comune e centralizzata.

La ottimizzazione dello sfruttamento della CPU da parte dei vari processi utente, può generare alcuni inconvenienti nel sistema di elaborazione:   Starvation   Deadlock (blocco critico)


  Starvation : fenomeno che si manifesta quando più processi potrebbero accedere alla stessa risorsa ma solo alcuni di essi vi riescono a causa della politica di gestione adottata.

Se ad ogni processo è assegnata una priorità legata al tipo di utente e il SO assegna il processore ai processi con priorità più alta, si può verificare una situazione in cui un processo non ha mai accesso al processore poiché è sempre presente un processo con priorità più alta.

  Deadlock : blocco critico che investe un gruppo di processi che rimangono tutti permanentemente bloccati senza che la risorsa contesa venga utilizzata da alcuno di essi. Ad es : Due processi condividono la stessa stampante:

ü Il processo A che inizialmente detiene la stampante, richiede i risultati del processo B per poter terminare le proprie elaborazioni e ugualmente il processo B necessita dei risultati di A.

ü Entrambi i processi si bloccano in attesa della terminazione dell’altro, senza che nessuno possa evolvere rilasciando la stampante.

05/10/15

11


Tecniche per evitare o, eventualmente, individuare e risolvere situazioni di blocco: ü  Poltica Round-Robin di assegnamento circolare del processore consente di evitare fenomeni

di starvation fra processi concorrenti. ü  Tecnica di eliminazione dei processi coinvolti sino alla completa rimozione del blocco. ü  Tecnica di assegnare a priori una aliquota delle risorse a tutti i processi coinvolti nel sistema

oppure, ad ogni richiesta di risorse, verificare preventivamente l’assenza di un blocco critico ( in applicazioni in ambito bancario o controllo di impianti industriali )

Interazioni fra processi: 1.  Indesiderate e (spesso) impreviste

I processi competono per le risorse al fine di poter completare la propria esecuzione, causando condizioni di attesa ed eventualmente problemi quali blocco critico o starvation.

2.  Desiderate e previste I processi cooperano al fine di giungere alla soluzione di un problema complesso (Architetture client-server, in cui un processo richiede un servizio ad un altro e attende da esso la risposta)


Il SO gestisce l’interazione fra processi mediante:

1.  meccanismi di sincronizzazione fra le attività che ogni processo deve svolgere in modo parallelo rispetto agli altri.

Il controllo degli eventi mediante “semafori logici” .

2.  meccanismi di comunicazione ossia modalità di scambio di dati fra processi.

Ø  Spazio di memoria comune (data sharing) in cui i processi possono scambiarsi i dati, nel caso di processi all’interno dello stesso calcolatore.

Ø  Scambio di messaggi (message passing) con send e receive fra i processi, sia all’interno dello stesso calcolatore sia in una rete di comunicazione.

05/10/15

12

Problema produttore–consumatore

E’ un paradigma classico per realizzare una forma di sincronizzazione tra processi condividendo un buffer comune .

Il processo produttore produce informazioni che deposita nel buffer. Il processo consumatore legge invece i dati dal buffer rimuovendoli.

L’accesso al buffer di due processi può essere implementato mediante l’uso di “semafori”. ü  Buffer illimitato: non vengono posti limiti pratici alla dimensione del

buffer. ü  Buffer limitato: si assume che la dimensione del buffer sia fissata.


Soluzione con buffer limitato e memoria condivisa

Lo schema della soluzione permette di avere al massimo n -1 elementi contemporaneamente contenuti nel buffer.

; dati condivisi; var n; type item = … ; var buffer: array [0..n–1] of item;

in, out: 0..n–1;

; Processo produttore ; Repeat … produce un elemento in nextp … while in+1 mod n = out do no-op; buffer [in] := nextp; in := in+1 mod n; until false;

; Processo consumatore ; Repeat while in = out do no-op; nextc := buffer [out]; out := out+1 mod n;

… consuma l’elemento in nextc

… until false;

05/10/15

13

La sezione critica

§  Si hanno n processi che competono per usare alcuni dati condivisi. §  Ciascun processo ha una parte di codice, chiamata sezione critica, in cui accede a dati

condivisi. §  Problema – assicurare che quando un processo esegue la sezione critica, nessun altro

processo possa eseguire la propria sezione critica. §  Struttura del processo Pi

repeat entry section sezione critica exit section sezione non critica until false;

ü  Mutua esclusione. Se il processo Pi sta eseguendo la propria sezione critica, allora nessun altro processo può eseguire le proprie sezioni critiche.

ü  Progresso. Se nessun processo è in esecuzione nella propria sezione critica ed esiste qualche processo che desidera entrare nella propria sezione critica, allora la selezione del processo che può entrare nella propria sezione critica non può essere rimandata indefinitamente.

ü  Attesa limitata. E’ necessario porre un limite al numero di volte che si consente ad altri processi di entrare nelle proprie sezioni critiche, prima che la richiesta del primo processo sia stata accordata.

Condizioni per la soluzione del problema della sezione critica

Semafori e/o monitor

Quando esistono n processi che leggono o scrivono lo stesso elemento contemporaneamente (più produttori e consumatori), la procedura che mette un risultato nel buffer dovrebbe contenere due azioni, una che determini uno spazio disponibile del buffer e l'altra che vi scrive il dato.

Per superare situazioni di collisione nella scrittura nel buffer, occorre che solo un produttore per volta esegua putItemIntoBuffer(); si utilizza a tal fine una sezione critica con Mutex. (un semaforo binario) il cui valore uno o zero, assicura che solo un processo può essere in esecuzione tra i due cambi di valore del semaforo (algoritmo del biglietto o del fornaio).

Prima di entrare in una sezione critica, i processi ricevono un numero (biglietto del negozio). Il possessore del numero più basso entra nella sezione critica. Se i processi Pi e Pj ricevono lo stesso numero, se i < j, allora Pi viene servito prima, altrimenti Pj è servito prima.

I lucidi 26-33 sono tratti da Operating System Concepts di Silberschatz and Galvin©1999

05/10/15

14

Semafori

q  I semafori sono strumenti di sincronizzazione che possono essere di due tipi :   Semaforo contatore – intero che può assumere valori in un dominio non

limitato.   Semaforo binario – intero che può essere settato solo a 0 o 1.

q  Si può accedere al semaforo solo attraverso due operazioni indivisibili (atomiche): wait (S): while S≤ 0 do no-op;

S := S – 1; signal (S): S := S + 1;

Variabili condivise var mutex : semaforo; (inizialmente mutex = 1)

Processo Pi repeat wait(mutex);

sezione critica…. signal(mutex);

sezione non critica….. until false;

Esempio: sezione critica con n processi

Problema scrittori–lettori

§  Alcuni processi devono accedere in lettura e/o scrittura ad una risorsa condivisa (es. file).

§  Se due lettori accedono contemporaneamente all’insieme di dati non ci sono problemi.

§  Gli scrittori devono avere accesso esclusivo all’insieme di dati condivisi. Due formulazioni del problema sono le seguenti:

ü Nessun lettore rimanga in attesa, a meno che uno scrittore abbia già ottenuto il permesso di utilizzare l’insieme di dati condiviso.

ü Uno scrittore, una volta pronto, esegua il proprio compito di scrittura al più presto (nessun nuovo lettore deve iniziare la lettura da questo momento).

05/10/15

15

•  I filosofi mangiano e pensano. •  Quando un filosofo ha fame, tenta di prendere le due bacchette che ha accanto. •  Prende prima una bacchetta poi l’altra. •  Non rilascia le bacchette finché non ha finito.

Problema dei 5 filosofi

•  Non esclude il deadlock, ad esempio se tutti i filosofi hanno fame contemporaneamente e prendono prima la bacchetta alla loro destra.

•  Alcune soluzioni: –  Solo quattro filosofi possono essere seduti contemporaneamente a tavola. –  Un filosofo può prendere le sue bacchette solo se sono entrambe disponibili

(attenzione alle sezioni critiche). –  Adottare una soluzione asimmetrica. Un filosofo dispari prende prima la

bacchetta di sinistra, un filosofo pari prende prima la bacchetta di destra.

Monitor

Dal momento che i monitor garantiscono la mutua esclusione, non è necessaria nessuna implementazione aggiuntiva per proteggere le sezioni critiche nel caso di più produttori/consumatori.

Il MONITOR è un costrutto di sincronizzazione di alto livello che permette la condivisione sicura di un tipo astratto di dati fra processi concorrenti.

type monitor-name = monitor …..dichiarazione variabili….. procedure entry P1 :(…); begin … end; procedure entry P2(…); begin … end; …………. procedure entry Pn (…); begin…end; begin …codice di inizializzazione… end

05/10/15

16

Monitor

Ø  Per permettere ad un processo di attendere dentro al monitor, devono essere dichiarate variabili condition :

var x, y: condition Ø  La variabile condition può essere usata solo con le operazioni wait e

signal. §  L’operazione wait (x)

vuol dire che il processo che chiama questa operazione viene sospeso finché un altro processo chiama signal (x);

§  L’operazione signal(x) riprende esattamente un processo sospeso. Se nessun processo è sospeso, allora l’operazione di signal non ha effetto.

Monitor per produttore/consumatore

monitor ProducerConsumer { int itemCount condition full condition empty procedure add(item) { while (itemCount == BUFFER_SIZE) { wait(full) } putItemIntoBuffer(item) itemCount = itemCount + 1 if (itemCount == 1) { notify(empty) } } procedure remove() { while (itemCount == 0) { wait(empty) } item = removeItemFromBuffer() itemCount = itemCount – 1 if (itemCount == BUFFER_SIZE - 1) { notify(full) } return item; } }

procedure producer() { while (true) { item = produceItem() ProducerConsumer.add(item) } } procedure consumer() { while (true) { item = ProducerConsumer.remove() consumeItem(item) } }

05/10/15

17

Thread

  Un thread è l’unità di base di utilizzo della CPU e consiste di :   Program counter   Insieme dei registri   Spazio dello stack

  Un thread condivide con i thread ad esso associati:   sezioni di codice   sezioni dati   risorse del sistema operativo L’insieme dei thread (e dell’ambiente da essi condiviso) è chiamato task.

  Un processo tradizionale corrisponde ad un task con un solo thread CdL in Informatica- Magistrale

Università di Bari Sistemi Distribuiti

Nei sistemi distribuiti risulta indispensabile riuscire ad aumentare la granulosità dei processi . La soluzione è l’uso di cosiddetti thread di controllo

multipli per ogni processo (task), che consentano di svolgere le diverse attività di un processo senza necessariamente bloccare l’intero processo.

Uso dei thread in sistemi NON distribuiti

L’IPC si ottiene attraverso ripetute e pesanti attività di context switching dei processi. Ciò si potrebbe evitare utilizzando thread a livello di utente (u-thread).


B Rif.: A.Tanenbaum,M.Van Steen “Sistemi distribuiti” Pearson

Prentice Hall 2007 )

- Gli u-thread svolgono la loro attività in spazio utente, non possono eseguire istruzioni privilegiate o accedere a primitive del kernel. Il sistema operativo avvia il processo multithread considerandolo come entità unica.

- Gli u-thread sono anche detti Molti-ad-Uno perché il S.O. associa tutti i thread di un processo ad un singolo contesto di esecuzione.

… i thread invece…

- Il pacchetto dei thread a livello utente (u-thread) usa una stessa routine (scheduler) per pianificare il thread successivo.

05/10/15

18

Implementazione dei Thread

Combinazione di thread diversi (Lightweight process a livello di kernel e thread a livello di utente) per parallelizzare il più possibile le attività di gestione dei processi a costi ridotti d’uso del kernel.

Rif.: A.Tanenbaum,M.Van Steen “Sistemi distribuiti” Pearson Prentice Hall 2007 )

I thread a livello kernel (k-thread o LPW) condividono lo spazio di indirizzamento del processo cui appartengono (memorizza i dati specifici per ogni thread nel sistema) ed esegue le istruzioni di un u-thread.

-  Un pacchetto di thread a livello di utente (u-thread) ha costi minori in termini di uso di risorse e di tempi di esecuzione (ad es. i context switching) e vengono svolti senza impegnare il kernel.

- Un LPW viene eseguito nel contesto di un singolo processo (il S.O. fornisce ad ogni u-thread un thread LPW a livello kernel ) ed è per questo detto multithread Uno-a-Uno.

ad es. Multi-thread di Solaris 2 implementazione ibrida del multi-threading

-  Ad ogni processo (task)

corrispondono più u-thread.

-  Ad ogni u-thread possono corrispondere uno o più LPW (ad es. per accedere ad una risorsa mediante var. mutex o semafori) che si possono raggruppare in un pool di thread.

Una soluzione ibrida prevede una associazione di thread Molti-a-Molti ( diversi u-thread ad un insieme di LPW )

Tecnica del thread pooling

Rif.: SUN Microsystems Sparc Manuale OS Solaris

Combinazione di thread diversi (Lightweight process a livello di kernel e thread a livello di utente) per parallelizzare il più possibile le attività di gestione dei processi a costi ridotti d’uso del kernel.

05/10/15

19

Thread

  In un task con più thread, mentre un thread è bloccato e in attesa, un secondo thread nello stesso task può essere in esecuzione.

  La cooperazione di più thread nello stesso job fornisce un più grande throughput e prestazioni migliorate.

  Applicazioni che richiedono la condivisione di un buffer comune (es. produttore-consumatore) traggono beneficio dall’impiego di thread.

  I thread forniscono un meccanismo che permette a processi sequenziali di effettuare chiamate di sistema bloccanti, ottenendo allo stesso tempo un’esecuzione parallela.


Thread nei sistemi distribuiti

I thread forniscono un mezzo per consentire chiamate di sistema bloccanti, senza bloccare l’intero processo in cui il thread è in esecuzione, per cui sono particolarmente utili nel realizzare in parallelo le attività di comunicazione nei sistemi distribuiti.

Il multi-threading lato client Ad esempio i Browser WEB realizzano molte delle attività previste

attraverso l’attivazione di thread multipli per nascondere la latenza della comunicazione, per la visualizzazione del file html durante la ricezione dei file, per consentire la navigazione con i link durante la visualizzazione delle immagini, ecc….

05/10/15

20

Thread per distribuire in modo trasparente le risorse sui client

Un modo possibile per la replica trasparente di oggetti remoti usando una soluzione client-server


multithreads

Multithread lato server

Un server multithread organizzato secondo il modello dispatcher/worker


Rif.: A.Tanenbaum,M.Van Steen “Sistemi distribuiti” Pearson Prentice Hall 2007 )

05/10/15

21

Server multithread

Es.: tre modi per costruire un file server con tempi ridotti di gestione ed esecuzione dei task

Model Characteristics

MultiThreads Parallelism, blocking system calls

Single-threaded process No parallelism, blocking system calls

Finite-state machine Parallelism, nonblocking system calls

I Processi - Universita' degli Studi di Bari Aldo Moro

Documents

Transcript of I Processi - Universita' degli Studi di Bari Aldo Moro