programmazione concorrente
In un sistema di elaborazione, che sia un personal computer, un microcontrollore o un sistema embedded per una specifica applicazione, le operazioni complesse che sono svolte dalla CPU possono essere scomposte in due macro-insiemi:
Operazioni sequenziali Operazioni parallelizzabili
Prendiamo ad esempio le due seguenti operazioni: 𝑦 = 𝑎 ∙ 𝑏
𝑧 = 2 ∙ 𝑦 + 𝑐
Il calcolo di z non può prescindere dal calcolo di y perché z dipende da y. Dunque, le due operazioni saranno svolte necessariamente in sequenza, prima y e poi z, come è visibile dal diagramma di fig. 25.
Fig. 25 – Ordine di esecuzione per operazioni dipendenti tra loro
Adesso, invece, consideriamo queste altre due operazioni: 𝑦 = 𝑎 ∙ 𝑏
𝑎 𝑏 𝑐
𝑦 = 𝑎 ∙ 𝑏 𝑧 = 2 ∙ 𝑐 + 𝑑
Diversamente dalla prima situazione, in questo caso le due operazioni prescindono l’una dall’altra e possono essere svolte singolarmente in parallelo tra loro, poiché z non dipende da y e viceversa. Il diagramma di
fig. 26 mostra quanto appena detto.
Fi. 26 - Ordine di esecuzione per operazioni indipendenti tra loro
Quindi, ci sono operazioni che devono essere svolte in modo sequenziale mentre altre possono essere svolte in parallelo: dove è possibile parallelizzare le operazioni l’esecuzione del programma risulterà più veloce. Questo risultato si raggiunge solo nei sistemi multi-core, dove le operazioni parallelizzabili vengono eseguite separatamente da due core, ottimizzando i tempi e velocizzando l’esecuzione del programma.
Dunque, è possibile spezzare un complesso programma in più flussi esecutivi separati che svolgono funzioni indipendenti tra loro per arrivare più velocemente al risultato finale.
La possibilità di poter avere più flussi di esecuzione sullo stesso sistema di elaborazione è offerta dal Sistema Operativo.
In una rappresentazione a strati di un sistema di elaborazione basato su sistema operativo, mostrata in fig. 27, quest’ultimo è lo strato software che fa da intermediario tra le risorse hardware del sistema e i programmi in esecuzione.
𝑦 = 𝑎 ∙ 𝑏
𝑎 𝑏 𝑐
𝑧 = 2 ∙ 𝑐 + 𝑑
Fig. 27 – Rappresentazione a strati delle componenti principali di un sistema operativo
Il sistema operativo è sviluppato appositamente per la destinazione finale del sistema di elaborazione. Un personale computer domestico disporrà di un sistema operativo standard con un’interfaccia grafica ben sviluppata per facilitarne l’utilizzo da parte dell’utente e sarà ottimizzato per la massima rapidità di interazione e potrà svolgere un gran numero di funzioni. Un sistema embedded di una centralina di un’autovettura disporrà di un sistema operativo senza interfaccia grafica, che punta alla massima sicurezza e alla massima ottimizzazione delle risorse hardware che deve gestire, poiché un errore di calcolo o un bug di sistema possono mettere a rischio la vita degli occupanti del veicolo.
Nello specifico, le funzioni di un sistema operativo e la sua struttura stessa dipendono fortemente dall’applicazione sul quale andrà ad operare. Ci sono però un insieme di funzioni e servizi messi a disposizione dal sistema operativo che sono fondamentali e sono sempre presenti:
Gestione e controllo dei processi Gestione della memoria
Protezione
System and application programs
Operating System
Comunicazione
Per spiegare queste funzionalità occorre fare un passo indietro per fare una importante distinzione. Un programma è un insieme di istruzioni codificate in un file secondo un certo linguaggio di programmazione; un processo è un’istanza in esecuzione di un certo programma. Questo significa che quando parliamo di flussi di esecuzione ci riferiamo ad un processo. Inoltre, su un sistema di elaborazione possono essere in esecuzione più processi dello stesso programma.
Gestione e controllo dei processi
Il sistema operativo mette a disposizione un set di risorse software con le quali esso controlla e gestisce tutti i processi attivi al suo interno. Ogni processo può assumere determinati stati a seconda di ciò che sta facendo o di ciò che vuole fare ed è il sistema operativo che gestisce i processi tramite lo scheduler. Esso stabilise quando un processo può entrare in esecuzione nella CPU, secondo determinati criteri stabiliti dallo sviluppatore del sistema operativo: i criteri più comuni possono essere basati su una scala di priorità oppure sulla determinazione di un quanto di tempo per ogni processo. I principali stati che può assumere un processo all’interno di un sistema operativo sono in genere 5:
New: il processo è appena stato creato dal sistema operativo
Ready: il processo è pronto e sta aspettando di entrare in esecuzione Running: il processo è in esecuzione
Waiting: il processo è in attesa di una risorsa; per risorsa si intende in genere una locazione di memoria oppure una risorsa di I/O
Terminated: il processo ha esplicato tutte le sue funzioni ed è stato terminato
Le possibili transizioni da uno stato all’altro sono rappresentate dal seguente diagramma di fig. 28:
Fig. 28 – Diagramma di transizioni di stato per un processo in un SOA
Lo scheduler stabilisce l’ordine con cui la CPU andrà ad eseguire i vari processi in coda nello stato Ready e dunque lo svolgimento delle varie operazioni che il sistema deve compiere. Il passaggio di un processo dallo stato Running allo stato Ready è provocato dall’arrivo di un evento che ha priorità maggiore del processo in esecuzione: dunque il processo in esecuzione viene sospeso tramite revoca della CPU, passa nella coda dei processi pronti e la CPU viene assegnata alla gestione dell’evento urgente. Gli eventi di questo tipo possono essere molteplici, come ad esempio l’arrivo di un messaggio dalla rete, la fine di un’operazione effettuata da una periferica di I/O, l’input dell’utente ecc. Questi eventi generano una interruzione, in inglese interrupt, che provoca l’immediata revoca della CPU al processo che era in esecuzione in quel momento e l’assegnazione di essa ad un particolare processo, chiamato handler, che si occupa di gestire l’interruzione. Successivamente la CPU viene rilasciata allo scheduler che gli assegnerà un processo pronto da eseguire.
New Ready Running Terminated Waiting Interruzione Ammesso Schedulazione Fine del processo Risorsa
disponibile Risorsa occupata
Gestione della memoria
In un sistema di elaborazione ci sono molti tipi di memorie, ognuna dedicata ad un certo utilizzo, ma le più importanti sono due:
Memoria primaria – è la Random Access Memory (RAM), uno spazio di memoria volatile che, durante l’attività del sistema, mantiene in memoria i programmi in esecuzione e i dati utilizzati.
Memoria secondaria – è il dispositivo di archiviazione di massa, lo spazio di memoria non volatile che custodisce l’insieme dei programmi che possono essere eseguiti e l’insieme dei dati che possono essere elaborati dal sistema.
La memoria secondaria è gestita grazie al file system, una profonda suddivisione dello spazio disponibile in blocchi e pagine indicizzati in un file accessibile dalla CPU. Questa tecnica di indicizzazione è messa a disposizione dal sistema operativo e consente un rapido accesso ai file memorizzati al suo interno.
La memoria primaria è molto più critica da gestire perché da essa la CPU attinge le operazioni che deve eseguire e i dati da elaborare e poi vi salva i risultati, quindi è una memoria acceduta molto frequentemente. La problematica principale è quella della protezione delle informazioni dalla sovrascrittura voluta o non voluta di altri processi che non ne hanno il permesso. Il sistema operativo mette dunque a disposizione delle funzioni specifiche per la gestione di questo problema, che successivamente andremo ad esplicare più in dettaglio.
Protezione
Come accennato nel paragrafo precedente, il sistema operativo svolge anche funzioni di protezione per tutte quelle risorse che sono condivise tra i vari processi in esecuzione. Un processo potrebbe voler leggere un file mentre già
un altro lo sta modificando: se questo sarà permesso, il processo “lettore” che leggerà il file otterrà delle informazioni inconsistenti in quanto non è detto che il processo “scrittore” abbia già terminato di modificarle. Vediamo più in dettaglio nella fig. 29:
Fig. 29 - Il processo B leggerà delle informazioni inconsistenti!
Questo è un tipico problema di programmazione concorrente e il sistema operativo mette a disposizione del programmatore delle funzioni appositamente pensate per la sua risoluzione: i semafori.
Un semaforo non è altro che una struttura dati composta da un intero, che può assumere un certo campo di valori, e dall’insieme delle operazioni che si
… Accesso in scrittura Inizio scrittura Risorsa di memoria condivisa RAM Processo A Processo B Revoca CPU … … Accesso in lettura Revoca CPU … Assegnazione CPU Assegnazione CPU Accesso in scrittura Fine scrittura Revoca CPU Assegnazione CPU
possono effettuare sul dato. Il meccanismo di funzionamento del semaforo è semplice, molteplici invece sono le sue implementazioni software. Una possibile implementazione di un semaforo è rappresentata di seguito sottoforma di pseudocodice.
int s;
void wait(int *s) {
finché &s non è positivo aspetto; quando &s è positivo lo decremento; }
void signal(int *s) { incremento &s; }
Quando una risorsa condivisa viene creata, viene creato anche il semaforo che la protegge. L’utente inizializza il semaforo in funzione di quanti processi possono accedervi contemporaneamente alla risorsa. In generale, nei flussi esecutivi dei processi che vorranno accedere ad una risorsa condivisa, ci sarà una sequenza di operazioni composta da:
Sezione di entrata Sezione critica Sezione di uscita
La sezione di entrata ha lo scopo di verificare che ci siano le condizioni, per il processo che la esegue, di accedere alla risorsa condivisa, altrimenti di bloccarlo in qualche modo. Ci sono diversi modi con cui si può bloccare un processo che vuole accedere alla risorsa condivisa già occupata:
Facendo attesa attiva – il processo controlla di continuo lo stato del semaforo; quando lo trova libero il processo esce dalla sezione di entrata, acquisisce il permesso di entrare in sezione critica tramite il
semaforo e vi entra; questa tecnica è altamente inefficiente perché quando il processo è in esecuzione ed aspetta che il semaforo si liberi, esso fa “attesa attiva”, ovvero impiega tempo della CPU aspettando, un’operazione poco utile.
Sospendendo il processo – il processo che trova il semaforo bloccato viene sospeso ed inserito in una coda specifica che contiene tutti i processi che hanno tentato di accedere alla risorsa condivisa già occupata; quando la risorsa torna libera la coda viene svuotata risvegliando, uno per volta, quei processi che vi erano entrati in attesa della risorsa; questa soluzione è molto più efficiente della prima, poiché non si spreca inutilmente tempo di calcolo della CPU ma si sospende il processo.
Il processo che infine si appropria del diritto di accedere alla risorsa condivisa vi entra: è la sezione critica. Il processo svolge le operazioni che deve fare sulla risorsa condivisa, che principalmente sono lettura e scrittura, dopodiché passa alla sezione di uscita.
La sezione di uscita ha la funzione di rilasciare il controllo del semaforo, cosicché esso possa essere disponibile per un nuovo processo che ha bisogno di accedere alla risorsa condivisa.
Se N è il numero di processi che possono accedere alla risorsa condivisa, il semaforo viene inizializzato ad N. Ogni processo che vuole accedere alla risorsa condivisa effettua, nella sezione di entrata, la wait sul semaforo di quella risorsa: la wait controlla che il semaforo non sia arrivato a zero e lo decrementa, in caso contrario blocca il processo in attesa. Una volta acceduto alla risorsa condivisa, il processo, nella sezione di uscita, effettua la signal sul semaforo, incrementandone il suo valore e lasciando spazio ad un nuovo processo che vuole accedere alla risorsa.
Generalmente i semafori possono essere inizializzati ad un valore qualunque ma, nel caso particolare in cui soltanto un processo per volta può accedere
alla risorsa condivisa, il semaforo viene inizializzato ad 1 e viene chiamato mutex o semaforo binario, perché il suo valore può essere 0 o 1.
In una situazione pratica, quello che succede durante l’accesso ad una sezione critica protetta da un mutex si può vedere in dettaglio nel grafico di fig. 30.
Fig. 30 - Sincronizzazione di due processi per l’accesso ad una sezione di memoria condivisa tramite mutex
Una problematica da non sottovalutare dal punto di vista del programmatore che utilizza i semafori è la formazione non voluta di “deadlock”. Essi sono situazioni in cui uno o più processi, in seguito ad un errato utilizzo dei semafori, entrano in uno stato di attesa dal quale non possono più uscirne. Un tipico esempio riguarda una coppia di processi che utilizzano entrambi due semafori:
il processo A fa la wait sul semaforo S → S = 0; al processo A viene revocata la CPU;
il processo B entra in esecuzione e fa la wait sul semaforo R → R = 0; il processo B fa la wait sul semaforo S che è già bloccato → B si blocca;
Processo Processo B Wait(S) S S Sezione critica Signal(S) S Wait(S) Bloccato S Sezione critica Signal(S) S
viene eseguito il processo A che fa la wait sul semaforo R che è bloccato → A si blocca.
Entrambi i processi resteranno bloccati per sempre! Il grafico seguente di
fig. 31 illustra questa situazione.
Fig. 31 - Grafico di esecuzione di due processi che si bloccano a vicenda a causa di un errato utilizzo dei semafori
Per evitare queste situazioni è sempre consigliato fare la signal del semaforo sul quale si è eseguita la wait, oppure evitare di scambiare l’ordine di eseuzione di due wait consecutive su due semafori diversi in due processi diversi. Processo Processo B Wait(S) S Sezione critica Wait(R) Wait(R) Bloccato Sezione critica R S R S R Wait(S) Bloccato
Un altro problema importante che riguarda i semafori è la “starvation”: si definisce così una situazione in cui un processo che è bloccato in coda, in attesa di accedere ad una risorsa, non viene mai sbloccato a causa dell’arrivo in coda di altri processi che hanno una priorità maggiore della sua. La soluzione a questo problema si trova andando ad incrementare la priorità del processo bloccato da più tempo in coda: prima o poi sicuramente verrà sbloccato.
Comunicazione
Due processi coesistenti all’interno di un sistema di elaborazione possono avere la necessità di dialogare tra loro, instaurando una sorta di canale di comunicazione. Questo può avvenire principalmente in due modi:
Tramite la creazione di una mailbox Tramite protocollo TCP/IP
Tramite memoria condivisa
Una mailbox è a tutti gli effetti una casella di posta all’interno del sistema, messa a disposizione dal sistema operativo: dispone di un ID che la identifica univocamente e grazie al quale un processo vi può lasciare un messaggio. Il processo destinatario del messaggio sa già che riceverà messaggi da quella mailbox. Ci sono mailbox di vario tipo a seconda della tipologia di condivisione dei messaggi che contiene:
Da uno a uno – la mailbox funge da canale di collegamento diretto tra due processi
Da molti a uno – Mailbox del destinatario - la mailbox riceve messaggi da molti processi e da essa vengono letti da un solo processo destinatario
Da molti a molti – Mailbox di sistema - la mailbox riceve messaggi da molti processi e sono destinati a molti processi
La fig. 32 rappresenta le varie tipologie di mailbox.
Fig. 32 - Le varie tipologie di mailbox: a) mailbox uno a uno, b) mailbox di destinatario, c) mailbox di sistema
Il protocollo TCP/IP è un protocollo di impacchettamento per i messaggi che un sistema di elaborazione scambia con la rete internet a cui è collegato. Quindi esso consente, a due processi attivi su due sistemi di elaborazione diversi ma interconnessi da una rete, di scambiarsi messaggi sotto forma di pacchetti generati dal protocollo in questione. Quest’ultimo è mostrato nella sua rappresentazione standard a strati dalla fig. 33.
Fig. 33 - Rappresentazione a strati del protocollo TCP/IP in riferimento al modello standard ISO/OSI Psn Ps0 Mailbox Pd Ps0 Mailbox Pd Psn … Mailbox … Ps0 … Pd0 Pdm a b c
Questo però non vieta che il protocollo TCP/IP possa essere usato anche per mettere in comunicazione due processi attivi sullo stesso sistema di elaborazione. Questa comunicazione è messa a disposizione dal sistema operativo tramite l’utilizzo di un’entità software astratta chiamata “socket”: è un tipo di dato che viene usato come porta di comunicazione, consentendo ad uno o più processi di potervi inviare dei messaggi; il socket provvederà poi all’inoltro di essi nella rete. Hanno un numero identificativo che li contraddistingue ed inoltre hanno la caratteristica di essere bidirezionali: questo significa che sullo stesso socket possono transitare i messaggi dal processo verso la rete o dalla rete verso il processo.
Infine, due o più processi possono comunicare tramite la condivisione di uno spazio di memoria sul quale possono scrivere e/o leggere i dati di cui hanno bisogno. Questa soluzione richiede una maggiore attenzione da parte del programmatore: egli deve assicurarsi di garantire la mutua esclusione dei vari processi che vorranno accedere allo spazio di memoria comune tramite i meccanismi semaforici già analizzati nei paragrafi precedenti. Come pro, questa tecnica di scambio di messaggi e informazioni è molto semplice da implementare e risulta essere molto veloce rispetto alle altre sopracitate. Quest’ultima soluzione, grazie alla facilità di utilizzo e alla sua grande efficacia, è stata quella adottata per lo scambio dei dati tra i vari processi, o task come saranno chiamati più avanti, nel sistema di elaborazione principale del progetto in questione.