• Non ci sono risultati.

Quote of the day. (

N/A
N/A
Protected

Academic year: 2022

Condividi "Quote of the day. ("

Copied!
47
0
0

Testo completo

(1)

1

Lezione T19 Thread

Sistemi Operativi (9 CFU), CdL Informatica, A. A. 2013/2014 Dipartimento di Scienze Fisiche, Informatiche e Matematiche Università di Modena e Reggio Emilia

http://weblab.ing.unimo.it/people/andreolini/didattica/sistemi-operativi

(2)

2

Quote of the day

(http://blog.golang.org/concurrency-is-not-parallelism)

“Concurrency and parallelism are not the same thing. Concurrency is the composition of independently executing processes. Parallelism is the simultaneous execution of (possibly related) computations.”

Rob Pike (1956-)

Ingegnere del software

Progettista e sviluppatore di Plan 9 Coautore di UTF-8, Blit, Go

Coautore di “The UNIX Programming Environment”

(3)

3

PROBLEMI LEGATI AI PROCESSI

(4)

4

Il modello a processo singolo

(Un processo Una traccia di codice)

Nella sua accezione più classica, il processo è l'astrazione di un programma in esecuzione.

Aree codice, dati, stack.

Stato di esecuzione.

Modello a processo singolo: il processo esegue una singola traccia di codice in modalità interlacciata con gli altri processi.

codice dati file

registri stack

Una singola traccia

(5)

5

Problema: assenza di scalabilità

(Che succede se tanti utenti richiedono servizi al processo?)

Una applicazione basata su processo singolo è fortemente limitata nella sua scalabilità.

Una singola traccia non riesce, di solito, a servire contemporaneamente le richieste di più utenti.

In linea di principio sarebbe anche possibile tramite tecniche molto complesse di programmazione basata su eventi. Esempi:

lo strumento di load testing Web httperf.

la libreria per applicazioni distribuite Node.js.

(6)

6

Soluzione: modello multi-processo

(L'applicazione è un insieme di processi distinti)

Nel modello multi-processo, una applicazione è concepita come insieme di processi distinti.

I processi possono coordinarsi fra loro in modi diversi.

Coordinazione fork: un processo di controllo riceve richieste e crea un figlio per gestire una risposta.

Il processo figlio viene terminato dopo la risposta.

Applicazione multi-processo

fork

richiesta

fork() risposta

exit()

(7)

7

Problema: media scalabilità

(Che succede se tantissimi utenti richiedono servizi al processo?)

Una applicazione multi-processo fork ha indubbiamente una scalabilità molto migliore rispetto ad una basata su processo singolo.

Tuttavia, in caso di ingente numero di richieste (diverse centinaia/migliaia al secondo):

il SO rischia di passare la maggior parte del tempo a svolgere operazioni interne di gestione (creazione processi, distruzione processi, cambi di contesto).

il SO viene “distolto” dal compito principale, ossia l'esecuzione della traccia di codice dei processi generati.

(8)

8

Soluzione: coordinazione pre-fork

(Pool di processi riusabili per diverse richieste)

Coordinazione pre-fork: un processo di controllo

crea un insieme di processi (pool) all'inizio della sua esecuzione e li distrugge tutti alla sua uscita.

espande e riduce dinamicamente la dimensione del pool a seconda del carico ricevuto.

Una richiesta è servita da un processo del pool.

Approccio simile a quello di SLAB.

Applicazione multi-processo

pre-fork

richiesta

fork() iniziale

risposta

...

Si modifica dinamicamente

(9)

9

Esempio: Apache ≤v1.3

(Pool di processi riusabili per diverse richieste)

Il Web server Apache (fino a v1.3) adotta il modello multi-processo con coordinazione pre-fork.

Pool di processi creati alla partenza del server.

Il pool si adatta esponenzialmente al carico (raddoppia o si dimezza).

Ogni richiesta è passata ad un processo del pool.

OpenLogs PostConfig

ChildInit

Ciclo

richiesta Ciclo

richiesta Ciclo richiesta Processo di

controllo

Restart StartUp

Config

Pool di processi

(10)

10

Problema: non condivisione dei dati

(I processi figli sono isolati; e se volessero aggiornare contatori globali?)

I gestori dei processi e della memoria isolano gli spazi di indirizzamento virtuali.

È impossibile condividere una struttura dati in lettura e scrittura fra i diversi processi figli (il COW lo impedisce).

(11)

11

Problema: latenza di dispatching alta

(Con tanti processi figli attivi il kernel lavora molto per commutarli)

Se:il processo di controllo ha generato molti figli;

arrivano molte richieste;

la macchina non ha tante CPU;

allora il kernel sarà soggetto a molti cambi di contesto. Ad ogni cambio di contesto deve essere ripristinata, fra le altre cose, l'intera tabella delle pagine del nuovo processo.

→ Tale operazione abbassa il throughput del server.

(12)

12

MODELLO MULTI-THREADED

(13)

13

Le manchevolezze dei processi

(Sbattute in prima pagina)

La creazione dello spazio di indirizzamento costa ed è ripetuta per ogni processo.

Se un processo è creato e distrutto con alta frequenza, il carico di lavoro per il kernel è ancora maggiore.

Il cambio di contesto è molto oneroso.

Va sostituito un intero spazio di indirizzamento.

Se i processi fanno I/O (e si bloccano) spesso, il carico di lavoro per il kernel è ancora maggiore.

Completa assenza di condivisione dei dati.

(14)

14

L'idea

(Per far sparire queste limitazioni)

Si introduce una rappresentazione alternativa e

“leggera” di processo che

renda semplice la condivisione dei dati fra più processi.

renda più veloce la creazione di un nuovo processo condividente codice e dati.

renda fulmineo il cambio di contesto in presenza di tanti processi con stesso codice e dati.

Tale rappresentazione alternativa prende il nome di modello multi-threaded.

(15)

15

Il modello multi-threaded

(Un processo Più tracce di codice)

Modello (a processo) multi- threaded: il processo esegue più tracce di codice in modalità interlacciata fra loro e con gli altri processi. Le tracce condividono le risorse del processo che le ha create (stack e registri esclusi).

Il thread è la rappresentazione interna al SO di una traccia.

codice dati file

registri registri

Tre tracce

registri

stack stack stack

(16)

16

Vantaggi

(Perché conviene programmare in ambiente multi-threaded)

Reattività.

Il blocco di un thread non inficia sugli altri.

Maggiore fluidità di esecuzione.

Condivisione delle risorse.

I thread condividono la memoria del processo che li ha creati. Si possono avere strutture dati condivise.

Economia.

Si allocano e distruggono le risorse di processo una sola volta.

Scalabilità.

I thread eseguono in parallelo su più CPU, a differenza di un singolo processo.

(17)

17

Svantaggi

(Perché NON conviene programmare in ambiente multi-threaded)

Paradigma di programmazione complesso.

La condivisione delle risorse e della memoria implica spesso la gestione della concorrenza degli accessi a queste ultime.

Sono necessari ulteriori passi di programmazione, spesso complessi.

Debugging complesso.

È molto difficile riprodurre bug in presenza di accessi concorrenti alle risorse.

È spesso difficile individuare le cause del bug.

(18)

18

MODELLI DI PROGRAMMAZIONE

(19)

19

Supporto del SO ai thread

(User level e/o kernel level)

La rappresentazione dei thread fornita dal SO può essere implementata in tre modi diversi.

Interamente in user space, senza coinvolgimento alcuno del kernel.

Interamente in kernel space, senza altro coinvolgimento delle librerie che non sia legato alla implementazione delle relative chiamate di sistema.

In maniera ibrida (sia in user space, sia in kernel space).

(20)

20

Modello da molti a uno

(Many-to-one: tutto in user space; tanti thread utente un thread nel kernel)

Nel modello da molti a uno (many-to-one, N:1) la rappresentazione del thread avviene interamente in user space.

Il kernel gestisce una sola struttura dati (processo).

Il processo usa delle funzionalità applicative per simulare uno scheduler di processi leggeri.

I processi leggeri eseguono singole funzioni definite nel processo generante e non sono noti al kernel.

Implementazioni: Green threads (Solaris), GNU Portable Threads, Java Threads (vecchie release), Ruby Threads.

(21)

21

Modello da molti a uno

(Uno schema)

User space Kernel space

Processo

main()

f1() f2() f3()

Libreria thread

create() stop()

schedule() resume() destroy()

Thread

PCB

(22)

22

Modello da molti a uno: vantaggi

(Perché conviene implementare il modello da molti a uno)

I thread sono gestiti nel modo più efficiente possibile.

Scheduling cooperativo: un thread decide di passare la palla ad un altro. Non viene coinvolto lo scheduler del kernel.

Nessun aggravio computazionale legato ai cambi di contesto tradizionali.

Il modello da molti a uno non richiede un kernel multithreaded per poter essere implementato.

Non è più un vero vantaggio. I kernel moderni hanno tutti la nozione di “thread”.

(23)

23

Modello da molti a uno: svantaggi

(Perché NON conviene implementare il modello da molti a uno)

Se un thread effettua una chiamata bloccante, è l'intero processo a bloccarsi, e non solo il thread in questione.

Modello pessimo in caso di applicazioni con I/O.

I thread sono legati allo stesso processo, e non possono eseguire su processori fisici distinti.

Modello pessimo per la scalabilità su più CPU.

(24)

24

Modello da uno a uno

(One-to-one: tutto in kernel space; un thread utente un thread nel kernel)

Nel modello da uno a uno (one-to-one, 1:1) la rappresentazione del thread avviene interamente in kernel space.

Il kernel gestisce una struttura dati per ciascun thread.

Il processo crea thread attraverso una duplicazione simile a fork().

I thread vengono schedulati dal kernel come processi qualunque.

Implementazioni: GNU/Linux (LinuxThreads, NPTL), Windows 95/98/2000/XP/NT.

(25)

25

Modello da uno a uno

(Uno schema)

User space Kernel space

Processo

main() f()

PCB

create() destroy()

Thread

f()

TCB

Thread

f()

TCB

(26)

26

Modello da uno a uno: vantaggi

(Perché conviene implementare il modello da molti a uno)

Se un thread effettua una chiamata bloccante, non blocca gli altri thread.

I thread possono implementare funzionalità di I/O senza stallare l'intera applicazione.

I thread sono rappresentati da altrettanti TCB, e possono essere eseguiti su processori fisici distinti.

Un'applicazione può scalare con il numero di CPU.

(27)

27

Modello da uno a uno: svantaggi

(Perché NON conviene implementare il modello da molti a uno)

I thread sono gestiti dallo scheduler dei processi del kernel.

Si paga un (piccolo) dazio ad ogni cambio di contesto.

Il modello da uno a uno richiede un kernel multithreaded per poter essere implementato.

Non è più un vero svantaggio. I kernel moderni hanno tutti la nozione di “thread”.

(28)

28

Modello da molti a molti

(Many-to-many: un ibrido dei due modelli precedenti)

Nel modello da molti a molti (many-to-many, N:M) la rappresentazione del thread avviene sia in user space, sia in kernel space.

Unione dei due precedenti modelli. L'idea è quella di prendere il meglio da ciascun modello.

Il processo crea M thread a livello kernel attraverso una duplicazione.

Ciascuno di questi M thread crea N/M thread a livello utente.

Implementazioni: IRIX, HP-UX, Tru64 UNIX, Solaris (fino a v9), Windows 7.

(29)

29

Modello da molti a molti

(Uno schema)

User space Kernel space

Processo

main()

f1() f2() f3() Libreria

thread

PCB

Thread

main()

f1() f2() f3() Libreria

thread

TCB

Thread user level Thread kernel level

create()

(30)

30

Architetture multi-threaded

(Come si possono combinare i thread fra loro?)

Pipeline.

I thread una linea di assemblaggio. L'output del thread precedente viene dato in pasto al thread successivo.

Master-Slave.

Un thread “master” coordina l'esecuzione di tanti thread “slave” (che effettuano il lavoro vero e proprio).

Worker.

Ciascun thread esegue un compito specifico dell'applicazione indipendentemente dagli altri.

(31)

31

Architetture multi-threaded

(Come si possono combinare i thread fra loro?)

Pipeline

Master-Slave

Worker

processo input thread thread thread output

processo

thread thread thread

input output

processo

thread

input output

thread

input output

thread

input output

thread

input output

(32)

32

Esempio: Apache ≥v2.0

(Pool di thread riusabili per diverse richieste)

A partire dalla versione v2.0, il Web server Apache adotta il modello multi- threaded con coordinazione pre-fork o worker.

Pool di thread creati alla partenza del server.

Il pool si adatta esponenzialmente al carico (raddoppia o si dimezza).

Coordinazione pre-fork: un thread svolge tutte le operazioni.

Coordinazione worker: le operazioni sono suddivise fra thread diversi.

OpenLogs PostConfig

ChildInit

Ciclo

richiesta Ciclo

richiesta Ciclo richiesta Processo di

controllo

Restart StartUp

Config

Pool di thread

(33)

33

MODELLO MULTI-THREADED LINUX

(34)

34

Rappresentazione a livello di kernel

(Da uno a uno)

Linux adotta il modello di multi-threading da uno a uno. Processi e thread usano le task_struct come descrittore unificato.

Un thread una → task_struct.

Un processo una → task_struct.

(35)

35

Meccanismo generale di clonazione

(Funzione interna do_fork())

La chiamata di sistema clone() implementa il meccanismo generico di creazione di thread. La clone() invoca la do_fork(), che svolge il lavoro.

Meccanismo unificato di creazione: do_fork().

La do_fork() condivide le risorse opportune a seconda che si tratti di un processo o di un thread.

Il lavoro sporco è svolto dalla copy_process().

(36)

36

I clone_flag di do_fork()

(La do_fork() deve differenziarsi tra processi e thread)

Il primo parametro della do_fork() contiene:

nella parte bassa un vettore di bit, detti clone flag.

nella parte alta, il codice del segnale da inviare al padre quando il figlio termina (SIGCHLD).

Clone flag: in $LINUX/include/sched.h.

Bit CLONE_VM: memoria virtuale condivisa.

Bit CLONE_FS: info sul file system condivise.

Bit CLONE_FILES: info su file aperti condivise.

Bit CLONE_SIGHAND: gestori dei segnali condivisi.

...

(37)

37

Valori dei clone flag per fork() e clone()

(Molto diversi fra loro)

Chiamata di sistema fork().

Clone flag: SIGCHLD.

Nessuna condivisione, segnale SIGCHLD inviato al padre quando il figlio muore.

Chiamata di sistema clone().

Clone flag (i principali; quelli minori sono omessi):

CLONE_VM | CLONE_FS | CLONE_FILES | CLONE_SIGNAL

Completa condivisione di memoria, gestori segnali ed informazione su file e file system.

Nessun segnale è inviato al padre quando il thread muore.

(38)

38

Native POSIX Thread Library

(AKA “Pthreads library”)

Implementa lo standard ANSI/IEEE POSIX 1003.1c.

Funzionalità offerte:

gestione thread (creazione, distruzione).

accesso serializzato a dati condivisi (mutex).

sincronizzazione ad eventi (variabili condizione).

Concepita per i linguaggi C e C++.

(39)

39

Rappresentazione a livello user

(Un TID per ciascun thread, memorizzato nel campo PID di task_struct)

Nella libreria Pthreads, un thread è rappresentato dal tipo di dato opaco pthread_t.

Ciascun thread ha un proprio identificatore univoco, il Thread Identifier (TID). Quando viene creato un nuovo thread, si salva il TID nella variabile pthread_t corrispondente.

Un TID non è altro che un PID, a cui è associata una task_struct nel kernel.

(40)

40

TID e PID

(Una sottile differenza)

Lo standard POSIX richiede due proprietà alla libreria dei thread.

Se invocata da un thread, la chiamata di sistema getpid() deve ritornare il PID del processo che lo ha creato.

Se invocata da un thread, la chiamata di sistema gettid() deve ritornare il TID ad esso associato.

A tal scopo si introduce il concetto di gruppo di thread.

(41)

41

Gruppo di thread, leader del gruppo

(Simile al gruppo di processi ed al leader del gruppo)

Il thread creante ed i thread da esso creati formano un gruppo di thread (thread group).

A tale gruppo è associato un numero intero detto identificatore del gruppo di thread (thread group identifier, TGID).

Il TGID è il TID del thread che ha generato per primo altri thread (anche detto processo leader o thread group leader).

(42)

42

Rappresentazione di PID, TID, TGID

(Gruppo Processo leader con i suoi thread, PID processo, TID thread)

PPID=1900 TGID=2001 TID=2001

Processo

PPID=1900 TGID=2001 TID=2002

Thread A

PPID=1900 TGID=2001 TID=2003

Thread B

PPID=1900 TGID=2001 TID=2004 Thread C Gruppo con TGID=2001

(43)

43

Creazione di thread

(pthread_create())

La funzione di libreria pthread_create() crea un thread. Azioni compiute (a grandi linee):

crea una nuova task_struct per il thread.

condivide le risorse specificate dai clone flag.

imposta l'indirizzo della prossima istruzione da eseguire ad una funzione scelta dall'utente.

cambia lo stato del thread ad eseguibile.

memorizza il TID nella struttura pthread_t relativa.

File $GLIBC/nptl/pthread_create.c.

(44)

44

Distruzione di thread

(pthread_exit())

La funzione di libreria pthread_exit() permette l'uscita pulita da un thread.

Di solito, è invocata con l'argomento NULL.

Attenzione! È sconsigliato usare exit() per uscire da un thread.

→ exit() provoca l'uscita del processo, la distruzione delle risorse condivise e l'uscita immediata di tutti i thread!

File $GLIBC/nptl/pthread_exit.c.

(45)

45

Thread ed execve()

(Problema simile a quello introdotto da exit())

Per lo stesso motivo ora visto, è sconsigliabile (anche se non vietato formalmente) eseguire la chiamata di sistema execve() all'interno di un thread.

→ execve() provoca il cambio immediato di spazio di indirizzamento in tutti i thread.

(46)

46

Dati specifici dei thread

(Thread Local Data)

Nei thread:

le variabili globali sono condivise.

le variabili automatiche non sono condivise.

È possibile definire anche variabili globali specifiche al thread (Thread Local Data).

Tali variabili si comportano come se fossero globali, ma non sono condivise fra thread.

Nella libreria Pthreads si usa lo specificatore __thread.

__thread int variable;

(47)

47

Accesso condiviso ai dati

(“Mutua esclusione”)

Finora non è stato accennato nulla riguardo all'accesso a variabili condivise.

Cosa succede se due thread distinti leggono e scrivono la stessa variabile condivisa?

Tale problema sarà trattato nell'ultima parte del corso, nelle lezioni riguardanti la comunicazione e la sincronizzazione.

Riferimenti

Documenti correlati

La libfuse è fatta in modo da garantire la retrocompatibilità con le versioni precedenti: è possibile, attraverso il valore dato alla macro, compilare l'eseguibile per il sotto-

The  waterfront  is  no  longer  a  simple  line  of  demarcation  and  has  ceased  to  be  a 

| Sia il modello molti-a-molti che il modello a due livelli richiedono comunicazione per mantenere il numero appropriato di kernel thread per gestire i thread utenti creati

The following axiom (where y does not occur in A) speci…es when and only when a name concept A has an extension that can be “object”-i…ed as a value of the bound object

Ci sono almeno tre tipi di file ELF (Executable and Linking Format, come

È stato infatti dimostrato che, contrariamente a quanto ritenuto in passato, diete ad alto contenuto in CHO, soprattutto se ricche in amido e povere di fibre vegeta- li,

Dopo un’analisi storica della situazione editoriale ve- neziana dell’epoca e in particolare sul ruolo di Aldo Manuzio, è stata affrontata l’opera dal punto di vista del contenuto

The same authors also showed that it is decidable whether a 1NFT is single-valued (see also [75]), and that equivalence of single-valued 1NFT is decidable [15]. For two-way