Sistemi Di calcolo II

Processi e thread

Benefici dei thread

Lunedì 3 ottobre 2022 17:00

• Si impiega meno tempo a creare o terminare un nuovo thread che un processo.
• Sono più leggeri e più facili da gestire.
• Il passaggio da un thread all'altro viene fatto più velocemente del passaggio da un processo all'altro.
• I thread possono comunicare tra loro senza invocare il kernel, data la presenza dello User Address Space: zona di memoria globale a cui accedono tutti i thread. Nei processi questo spazio di memoria è individuale per ogni processo e non è condiviso, quindi c'è bisogno di meccanismi aggiuntivi.
• Foreground e background work: ci sono più thread che gestiscono diverse operazioni.
• Processamento asincrono: i thread fanno dei calcoli di cui non abbiamo necessariamente bisogno subito, accoglie informazioni e ogni tanto scrive i dati in maniera asincrona.
• Velocità di esecuzione: un core può eseguire velocemente più thread.
• Struttura modulare del programma: gestione in parallelo di diverse operazioni gestite dal thread indipendentemente e concorrente.
• Il SO gestisce i thread a livello di processo, il che ha conseguenze sui thread.
• Esempi:
  • Sospendere un processo significa sospendere tutti i thread del processo (si tratta dello stesso indirizzo di memoria).
  • Terminare un processo significa terminare tutti i thread nel processo.
• Come i processi, i thread hanno uno stato di esecuzione e possono sincronizzarsi uno con l'altro.
• I thread hanno diversi stati:
  • Running
  • Ready
  • Blocked
  • Spawned: appena creato
• Per cambiare lo stato di un thread:
  • Spawn: crea un thread figlio
  • Block: blocca il thread, potrei bloccare anche un altro thread, ma è sconsigliato
  • Unblock: sblocca il thread
  • Finish: dealloca i registri della CPU e la stack

Si considera:

• Un programma che fa due chiamate a procedure remote (RPC -> chiamate a funzioni remote su un server).
• Ci sono due differenti host in modo che entrambi facciano le proprie operazioni indipendentemente.
• Si vuole ottenere un risultato combinato.
• L'utente gestisce i thread.
• Tutta la gestione dei thread è fatta dall'applicazione.
• Il SO non è a conoscenza dell'esistenza dei thread.

Teoria

Pagina 4

• Bloccare il processo attraverso una chiamata bloccante.
• L'applicazione specifica lo scheduling dei thread gestita blocca tutti i thread che non possono essere eseguiti dall'utente in modo da decidere personalmente il tempo di esecuzione e le priorità dei vari thread -> è indipendente dal kernel.
• Non sfrutta l'architettura multi-core o multi-processore.
• Il passaggio da un thread all'altro non ha bisogno del privilegio del kernel -> non bisogna passare alla kernel mode.
• Funziona su ogni SO -> l'implementazione è fatta a livello utente per mezzo di una libreria thread.
• Il SO gestisce i thread, i processi light perché l'utente non sa come il SO gestisce i thread.
• Il SO gestisce il contesto delle informazioni del processo e dei thread -> nessun thread è gestito dall'applicazione.
• Lo scheduling è fatto sulla base dei thread.
• Il SO sa quanti thread ha il processo. Windows è basato su questo approccio.
• Il kernel può simultaneamente eseguire più thread dello stesso processo su processori multipli.
• Il trasferimento di controllo da un thread all'altro nello stesso processo richiede una chiamata a sistema -> tempo di chiamata al SO.
• Se un thread in un processo è bloccato, il kernel può mettere in esecuzione un altro thread dello stesso processo -> il SO può spostare i thread su un altro core ed eseguire parallelamente i thread non bloccati.
• Le routine del kernel possono essere multithread.
• La creazione dei thread è fatta nello spazio utente.
• Lo scheduling e la sincronizzazione dei thread è svolta nell'applicazione.
• Gli ULT sono mappati in KTL -> Questo significa che i thread generati dall'utente possono essere gestiti da SO per mezzo di librerie.
• PThreads sono dei tipi definiti in C nell'header pthread.h.
• Aumenta la performance del programma.
• Può essere creato con molto meno overhead del SO (tempo di chiamata al SO).
• Ha bisogno di meno risorse di sistema per essere eseguito.
• Richiede meno tempo rispetto alla generazione dei processi con fork().
• Per sfruttare al meglio i Pthreads, un programma dovrebbe essere organizzato in task discrete e indipendenti che possono essere eseguite concorrentemente -> task non sequenziali (in cui il risultato non deve essere solo spostato da un thread all'altro).
• Se due routine possono essere intercambiate, alternate e/o sovrapposte nell'esecuzione in parallelo allora si possono usare dei thread per rappresentarle.

Teoria

Pagina 5

• Manager/worker:
  • Un thread manager assegna un lavoro ad un altro thread, detto thread worker.
  • Il manager gestisce gli input e distribuisce il lavoro agli altri task.
• Pipeline: Una task è rotta in una serie di sotto operazioni, ognuna eseguita in serie, ma concorrentemente da un thread differente.
• Modello a memoria condivisa:
  • Tutti i thread hanno accesso alla stessa memoria globale condivisa.
  • I thread hanno anche i propri dati privati.
  • I programmatori sono responsabili dell'accesso sincronizzato ai dati globali condivisi in modo che le locazioni di memoria condivise non vengano modificate dai thread in maniera errata.
  • Questo modello rende i thread molto più efficienti dei processi: infatti, per esempio, se andassimo ad allocare memoria creando n processi, la memoria verrà allocata n volte, mentre con i thread verrà allocata una sola volta avendo questi memoria condivisa.

Un codice è thread-safe quando più thread possono essere eseguiti simultaneamente senza interazioni inattese, cioè senza:

• Modificare erroneamente i dati condivisi.
• Creare race condition (condizioni di gara).

Un'applicazione crea diversi thread, ognuno dei quali fa una chiamata alla stessa routine di libreria:

• La routine di libreria accede/modifica una struttura globale o una locazione di memoria.
• Dato che ogni thread chiama questa routine, è possibile che questi possano tentare di modificare la struttura/locazione nello stesso momento.
• Se la routine non utilizza qualche meccanismo di sincronizzazione per prevenire la corruzione dei dati, allora l'applicazione non è thread-safe.

Il metodo main() di un programma comprende un singolo thread di default.

La funzione int pthread_create (pthread_t* thread, const pthread_attr_t* attr, void* (*start_routine)(void*), void* arg); crea un nuovo thread e lo rende eseguibile dove:

• thread: puntatore a variabile di tipo pthread_t, su cui verrà memorizzato l’ID del thread creato.
• attr: attributi di creazione.
• start_routine: funzione da eseguire (prende sempre come argomento un void* e restituisce un void*).
• arg: puntatore da passare come argomento alla funzione start_routine.
• Return value: 0 in caso di successo, altrimenti la causa dell’errore.

Il massimo numero di thread che il processo può creare dipende dall'implementazione.

Una volta creati i thread sono alla pari (sono eseguiti in concorrenza) e possono anche creare altri thread.

Ci sono diversi modi per terminare un thread:

• L'esecuzione del thread è terminata la funzione che è stata attivata dal thread raggiunge l'istruzione di return.
• void pthread_exit (void* value_ptr);
  • termina il thread corrente quando ha terminato il suo lavoro e non è più necessaria la sua esistenza, rendendo disponibile il valore puntato da value_ptr ad una eventuale operazione di join.
  • Non libera le risorse quindi bisogna deallocarle personalmente.
• pthread_cancel() da parte di un altro thread.
• exit() termina tutti i thread con una chiamata al SO.
• Il main termina senza eseguire pthread_exit() -> termina il processo principale.
  • Se ci sono altri thread ancora in esecuzione, ma il main è terminato e thread_exit() è stata usata per terminare il main o pthread_detach() è stata usata su questi thread in esecuzione, allora questi andranno avanti.
• int pthread_detach(pthread_t thread);
  • rende il thread indipendente dal main -> il thread non termina quando il main termina.
  • Notifica al sistema che non ci saranno operazioni di join su thread.
  • Return value: 0 in caso di successo, altrimenti la causa dell’errore.
• int pthread_join(pthread_t thread, void** value_ptr);
  • Attende esplicitamente la terminazione del thread con ID thread.
  • Se value_ptr!=NULL, vi memorizza il valore eventualmente restituito dal thread (un void*, tramite pthread_exit).
  • Return value: 0 in caso di successo, altrimenti la causa dell’errore.

Teoria

Pagina 6

• Sono una sottoclasse di Thread o una classe che implementa runnable().
• Il thread ha un metodo run() che la sottoclasse deve ridefinire.
• Si crea un nuovo thread con new().
• Si esegue un thread con start() che chiama run().
• Un thread può aspettare un altro thread con join().
• I due thread condividono la stessa memoria e le variabili.
• La libreria standard di Python contiene i thread comprendenti le primitive più importanti.
• Si crea un nuovo thread con il metodo Thread().
• Si esegue un thread con start() che ne esegue la funzione associata.
• Un thread può aspettare un altro thread con join().

Concorrenza

Mercoledì 5 ottobre 2022 11:00

• I SO sono creati ponendo attenzione alla gestione dei processi e dei thread:
  • Multi programma: più thread in un solo processore -> alternanza (interleaving).
  • Multi processo: più processi in più processori -> parallelismo (overlapping).
  • Per mezzo di processi distribuiti: più macchine e più memorie su cui vengono eseguiti più processi -> alternanza e parallelismo.
• La concorrenza sorge in tre contesti differenti:
  1. Applicazioni multiple: per permettere che il tempo di processamento sia condiviso tra le applicazioni attive.
  2. Applicazioni strutturate: è estensione del design modulare e della programmazione strutturata.
  3. Struttura di un SO: è implementato come un insieme di processi o thread.
• L'output dei processi deve essere indipendente dalla velocità di esecuzione di un altro processo in esecuzione concorrente.
  • Questo significa che non si possono inserire blocchi di timing, perché non si può prevedere il tempo di esecuzione dei vari processi.
• Operazioni atomiche: una funzione o un'azione implementata come una sequenza di una o più istruzioni che sembrano essere indivisibili.
  • Questo implica che nessun altro processo può vedere uno stato intermedio, interrompere l'operazione o gestire l'esecuzione suddividendola.
  • La sequenza di istruzioni garantisce che venga eseguita come un gruppo o non eseguita affatto, non avendo nessun effetto visibile sullo stato del sistema.
  • Garantisce l'isolamento dai processi concorrenti.
• Sezione critica: sezione di codice in un processo che richiede l'accesso a risorse condivise e che non deve essere eseguita mentre un altro processo è in esecuzione nella sua sezione di codice.
  • Deve essere minima (con un minimo insieme di istruzioni che rappresenta la criticità) e finita.
  • È quindi una sezione di codice a cui più utenti possono accedere contemporaneamente per modificarla.
• Mutua esclusione: accade quando un processo è in una sezione critica che ha accesso a risorse condivise e nessun altro processo può essere nella stessa sezione critica per accedere a quelle risorse condivise.
• Race condition: situazione in cui più thread o processi leggono e scrivono un insieme di dati condivisi e il risultato finale dipende dal relativo tempo di esecuzione dei vari thread (e quindi dall'ordine di esecuzione dei vari processi).
  • Colui che "perde la gara" è il processo che aggiorna per ultimo il valore e determinerà il valore finale della variabile.
  • Accade quando in una sezione critica non è presente la mutua esclusione.
  • Il risultato finale non è quello previsto perché l'esecuzione dei vari processi va a modificare i dati in modo errato.
• Deadlock: è una situazione in cui due o più processi non riescono a procedere perché entrambi stanno aspettando che l'altro faccia qualcosa.
  • Si parla anche di busy waiting: deadlock in cui il processo è bloccato infinitamente su un'istruzione -> non cambia stato, quindi non si trova in running.
• Livelock: è una situazione in cui due o più processi cambiano continuamente il loro stato come risposta al cambio di stato dell'altro processo senza produrre un risultato utile.
  • Tentano di cambiare stato per risolvere un deadlock.
• Starvation: è una situazione in cui un processo runnable è bloccato indefinitivamente dallo scheduler.
  • Anche se può procedere nell'esecuzione, lo scheduler non lo sceglie mai per metterlo in stato running.
  • Potrebbe essere dovuto alla mancanza di risorse.
• Interleaving e overlapping:
  • Possono essere visti come un esempio di concorrenza.
  • Entrambi presentano gli stessi problemi.
• La relativa velocità di esecuzione di un processo non può essere predetta, perché dipende da:
  • Le attività degli altri processi.
  • Il modo in cui il SO gestisce gli interrupt.
  • Le policy di scheduling del SO.
• Difficoltà della concorrenza sono:
  • La condivisione delle risorse globali.
  • La difficoltà del SO di gestire l'allocazione di risorse in modo ottimale.
  • La difficoltà di individuare e localizzare errori di programmazione come risultati che siano non deterministici e riproducibili.

Come risultato dell'esistenza della concorrenza il SO deve:

• Essere in grado di tenere traccia dei vari processi.
• Allocare e deallocare le risorse per ogni processo attivo.
• Proteggere i dati e le risorse fisiche di ogni processo contro l'interferenza dovuto all'esecuzione degli altri processi in concorrenza.
• Assicurare che i processi e gli output siano indipendenti dalla velocità di processamento -> è compito del programmatore con l'aiuto del SO.

Mutua esclusione

Lunedì 10 ottobre 2022 17:00

• La concorrenza dei processi arriva al conflitto quando questi vogliono usare la stessa risorsa (Es. dispositivi I/O, memoria, tempo del processore, clock).
• Nel caso di processi in competizione, ci sono tre problemi di controllo da affrontare:
  • Il bisogno di avere mutua esclusione.
  • Deadlock.
  • Starvation.
• La mutua esclusione deve essere garantita.
• Un processo che si ferma nella sua sezione non critica deve farlo senza interferire con gli altri processi.
• Non ci devono essere deadlock e starvation.
• Un processore non deve negare l'accesso alla sezione critica quando non c'è nessun altro processo che sta usando quella risorsa.
• Non sono fatte assunzioni riguardo la velocità dei relativi processi o il numero dei processi.
• Un processo rimane in una sezione critica solo per un tempo finito.
• Si disabilita il processo per mezzo di interrupt.
• Funziona su sistemi con un solo processore.
• Utilizzare gli interrupt garantisce la mutua esclusione.
• Svantaggi:
  • L'efficienza dell'esecuzione può essere abbassata.
  • Questo approccio non funziona su architetture multi-processore -> più processi, eseguiti da un core diverso, possono essere nella sezione critica contemporaneamente.
• Chiamata anche istruzione compare and exchange.
• Viene fatto un paragone tra il valore in memoria e un valore di test.
• Se i valori sono uguali, viene fatto uno scambio con il nuovo valore che si trova in memoria.
• Si tratta di una funzione atomica.
• È un'istruzione hardware disponibile nelle architetture x86, IA64, Sparc e IBM.
• Scambia il contenuto di un registro con quello di una locazione di memoria.
• Implementato nelle architetture Pentium e Itanium (IA64).

Teoria

Pagina 9

• Applicabile ad un numero qualsiasi di processi su un singolo processore o su processori multipli che condividono la memoria principale solo se inizialmente bolt=0.
• Semplice e facile da verificare.
• Può essere usato per supportare sezioni critiche multiple -> ogni sezione critica può essere definita dalla sua propria variabile.
• Causa busy waiting: mentre un processo è in attesa per l'accesso alla sezione critica continua a consumare il tempo del processore -> un processo esce dal ciclo.
• È possibile ci sia starvation quando un processo lascia una sezione critica e più di un processo è in attesa.
• È possibile ci siano deadlock (Es. a causa della priorità dei processi).
• Non è disponibile in tutte le architetture -> Il programmatore deve stare attento al tipo di architettura.
• Semaforo: è un costrutto basato su un valore intero usato per la segnalazione tra i processi.
  • Su un semaforo possono essere fatte solo tre operazioni atomiche: initialize, decrement e increment.
  • L'operazione di decremento può avere come risultato il blocco del processo -> si passa dallo stato ready/running a waiting.
  • L'operazione di incremento può avere come risultato lo sblocco del processo.
• Semaforo binario: è un semaforo che prende solo valori 0 e 1.
• Mutex: simile ad un semaforo binario, con la differenza...