Articolo pubblicato sul n. 103 di MCmicrocomputer (Edizioni Technimedia Srl - Roma) nel gennaio 1991

MCmicrocomputer


Multitasking:
Parallel Processing
(prima parte)

di Andrea de Prisco

   A partire da questo numero inizia su MCmicrocomputer una nuova serie di articoli dedicati alla programmazione parallela. Di stampo principalmente didattico, gli articoli tratteranno in modo abbastanza esaustivo tutte le tematiche riguardanti questa tecnica di programmazione ormai possibile anche su molti personal computer in circolazione.Copertina del numero di MCmicrocomputer contenente l'articolo
Parleremo, certo, anche del multitasking di Amiga (la prima macchina "personal" con un VERO sistema operativo multitask), ma le nostre discussioni resteranno, finche' possibile, rigidamente ancorate a schemi del tutto generali, portando a testimoniare linguaggi di programmazione parallela molto vari e tra loro diversificati. Faremo largo uso anche dell'OCCAM, il linguaggio di programmazione del transputer, col quale mostreremo "sul campo" alcune risoluzioni a problemi tipici della programmazione parallela.

Parallelismo

I lettori ancora non "multitasking" magari si staranno gia' chiedendo perche' tutto quest'affanno riguardo questa tecnica di programmazione a loro, ahinoi, poco nota. Del resto in C, in Pascal, in Basic (orrore!!!), si riesce a programmare di tutto. Volendo anche in linguaggio macchina magari senza neanche un assemblatore simbolico. E' vero, come diceva adp "tutto quello che si puo' ben dire si puo' ben fare", e con qualsiasi mezzo di calcolo, anche una succosa Macchina di Turing, si puo' calcolare qualsiasi... algoritmo calcolabile. Ma non corriamo troppo. Anzi, non usciamo fuori tema: di calcolabilita' MC se n'e' gia' occupata svariati numeri fa nella riuscita rubrica "Appunti di Informatica" e dunque non e' il caso di tornare nuovamente sull'argomento.
Dicevamo: perche' programmazione parallela ? Le risposte a quest'interrogativo sono molteplici, e vorremmo procedere per gradi. Innanzitutto la programmazione parallela permette di risolvere piu' facilmente problemi "intrinsecamente paralleli". Pensate ad esempio ad un sistema operativo che deve rivolgersi simultaneamente a piu' dispositivi per ricevere e dare informazioni di vario tipo: dati, segnali, sincronismi. Normalmente tutto e' risolto "a colpi di interrupt", magari anche nidificati l'uno nell'altro fino ad ottenere un funzionamento piu' o meno affidabile dell'intero "accrocco". Ma quanto e' piu' bello, piu' elegante, piu' efficiente, piu' produttivo, risolvere il problema scrivendo un processo per ogni funzione svolta dal nostro sistema operativo e lasciare che questi "vadano in parallelo", con la loro armonia di esecuzioni e interruzioni indeterministicamente realizzata dallo stesso kernel gestore del multitasking ?
Cosi' avremo un processo che attende caratteri dalla tastiera, un processo che asserve le richieste su disco, un altro processo che provvede alla stampa (eventualmente appoggiato da altri processi che implementano uno spooler intelligente), un altro ancora ha a che fare con gli output su video, ed altri ancora che implementano i rimanenti dispositivi utilizzabili dagli altri processi utente. E cosi' la stampa magicamente diventa assolutamente indipendente dalle operazioni sul disco o dagli eventuali ulteriori comandi impartiti da tastiera. Analogamente le elaborazioni video (dal semplice scrolling e spostamento di finestre a vere e proprie animazioni in tempo reale) non devono fare a cazzotti con le rimanenti attivita' della macchina quali quelle relative alle altre periferiche.
E poi in un sistema operativo multitask la potenza totale di calcolo puo' facilmente aumentare passando da architetture uniprocessor (in cui tutto il parallelismo di cui sopra e' simulato attraverso meccanismi di time sharing e sospensione processi in attesa) ad architetture multiprocessor dove le varie attivita' svolte, e non solo quelle di sistema ma soprattutto quelle "utente", sono eseguite in parallelo su piu' processori contemporaneamente.
Ma se le architetture multiprocessor, almeno per quanto riguarda le utenze "personal", possono sembrare oggi ancora fantascienza, anche il semplice multitask implementato su singolo processore puo' dare risultati sorprendenti.
Immaginate ad esempio di dover eseguire una complessa ricerca su un vostro database che, probabilmente, terrebbe impegnata la macchina per alcuni minuti. Una ricerca di questo tipo implica un continuo accesso ai dischi per trovare le informazioni desiderate. Come si sa, in ogni sistema di calcolo le periferiche rappresentano sempre veri e propri colli di bottiglia: non s'e' ancora vista, infatti, una unita' a dischi piu' veloce di un processore. In pratica analizzando quel che succede nel dominio del tempo in un calcolatore monotask che esegue continui accessi al disco, vedremmo che la CPU e' minimamente impegnata a dare ordini al device e per lo piu' attende l'esito delle varie operazioni ad esso richieste. Tra la richiesta di una di queste operazioni (ad esempio: Lettura del blocco 4565...) e l'esito di tale richiesta la CPU potrebbe fare qualcos'altro. Se il sistema e' multitasking, potrebbe eseguire altri calcoli in tutti i tempi in cui dovrebbe "inutilmente" aspettare la terminazione delle operazioni disco. E' cosi' che mentre il nostro HD fa "trac-trac" cercando le informazioni richieste, nulla ci vieta di lanciare anche il nostro WP per cominciare a scrivere una relazione e magari altrettanto parallelamente lasciare la nostra scheda Fax pronta a ricevere messaggi dalla linea telefonica. Operazioni che in un sistema rigidamente monotask avremmo dovuto effettuare in tempi successivi impiegando complessivamente un tempo superiore.
Certo che se invece di una situazione simile (del tutto normale, pero') avremmo la necessita' di calcolare un enorme spread sheet e contemporaneamente disegnare una porzione dell'insieme di Mandelbrot (situazione per nulla normale, pero') su un sistema multitask-uniprocessor non ci guadagneremo nulla non riuscendo a sfruttare tempi morti come nel caso precedente. Anzi, per la verita', impiegheremmo addirittura un tempo superiore dato che comunque il multitasking ha un suo costo in termini di tempo macchina utilizzato dal sistema per la sua stessa implementazione (il cosiddetto overhead).

Zoccoli e CPU

Aprendo un computer, la visione di un po' di zoccoli vuoti per integrati presenti sulla mother board ci richiama subito alla mente la possibilita' di espandere la memoria del sistema o al piu' di aggiungere un coprocessore matematico alla CPU. Sarebbe bello invece trovare un giorno all'interno dei personal computer alcuni zoccoli, diciamo una decina o anche piu', pronti ad accogliere altri processori per espandere la potenza di calcolo del nostro sistema. Il tutto, magari, in maniera assolutamente trasparente: al momento del boot il sistema farebbe un bel check dei processori installati in quel momento (eliminando via software eventualmente i processori guasti) configurandosi opportunamente come macchina mono o multiprocessore. Inoltre tale "dinamicita'" potrebbe permanere anche a computer funzionante eliminando anche nel bel mezzo di una elaborazione CPU difettose.
Ogni processore in funzione preleverebbe dalla lista dei processi in stato di pronto un processo per eseguirlo fino a successiva sospensione dovuta a richiesta di I/O o a "quanto di tempo scaduto". Cosi' in ogni istante se 'n' sono i processi funzionanti in quel momento, fino ad 'n' saranno i processi in esecuzione parallela. Inoltre ogni processore implementerebbe a sua volta un proprio multitask (in questo caso a parallelismo simulato) in modo che se 'n' sono le CPU attive in quel momento ed 'm' i processi da eseguire su ogni processore saranno eseguiti 'm/n' processi contemporaneamente.
In pratica potenza di calcolo REALMENTE configurabile secondo le effettive necessita'.

Multitasking vs Monotasking

Grazie alla programmazione strutturata e' ormai possibile scrivere i propri programmi non solo come insieme di linee di codice logicamente collegate da salti condizionati e non, ma piu' elegantemente come un insieme di moduli autonomi (le procedure) con le quali dialogare per mezzo dei meccanismi del passaggio dei parametri. Al punto che nei moderni linguaggi di programmazione appena un po' evoluti ogni procedura ha un proprio ambiente locale nel quale riconosce ed utilizza proprie variabili e strutture che nulla hanno a che spartire con analoghi riferimenti simbolici visibili in altre zone del programma. In piu', nella programmazione appunto sequenziale, e' di solito riconoscibile nella struttura di un programma il cosiddetto "main" che invoca varie procedure e funzioni e, per l'appunto, la definizione di quest'ultime.
Nel passaggio alla programmazione multitask, puo' essere conveniente (in alcuni casi necessario) vedere le singole procedure come veri e propri processi attivi, in attesa di ricevere sui propri canale i dati da elaborare e da rispedire a chi ha richiesto l'elaborazione. In pratica al posto di una procedura di sort possiamo immaginare un processo ordinatore che riceve in ingresso l'array da riordinare e restituisce in uscita (al committente) l'array ordinato.
Sparisce poi, in un certo senso, anche il concetto di "main" (o programma principale). Tutti i processi che formano il nostro programma multitask sono tra loro equivalenti: tutti attendono sulle loro porte di ingresso gli input per fornire degli output.
In figura 1A e' mostrata tale analogia tra le due tecniche di programmazione mono e multitask. In figura 1B troviamo anche il caso in cui le procedure siano invocate anche l'un l'altra (oltre che dal "main"): nella soluzione multitask altrettanto e' possibile che i processi cooperino tra loro prima, eventualmente, di restituire un risultato al processo committente.
I vantaggi di una soluzione simile sono praticamente ovvi: in una gestione "main-procedure" il chiamante ferma la sua elaborazione fino a quando la procedura non termina la sua, restituendo i risultati. Anche se tali risultati non servono immediatamente per una successiva elaborazione. Nella soluzione multitask, sempre se si vuole, e' invece possibile demandare un determinato compito piu' o meno gravoso ad un processo concorrente e continuare la propria elaborazione invocando, ad esempio, altri servizi.
E se pensate che un meccanismo simile non porti poi benefici quando il parallelismo e' solo simulato (nei computer uniprocessor) basta pensare alla soluzione ben piu' allettante dei computer multiprocessor in cui otterremo davvero un incremento di velocita' potendo realmente eseguire piu' calcoli contemporaneamente. Banalmente e' vero che un programma di per se' sequenziale non "corre di piu'" su un'architettura multiprocessor mentre il discorso e' ben diverso per i programmi multitask.

Forme di comunicazione

Esistono fondamentalmente due tipi di comunicazione tra processi in esecuzione parallela. Ad ambiente locale e ad ambiente globale. Nel primo caso ogni processo ha soltanto una propria zona di memoria privata nella quale realizza il suo ambiente (costanti, variabili, array, strutture, liste), nel secondo caso oltre a questa esiste una ulteriore zona di memoria condivisa da tutti i processi in esecuzione.
In base a questa distinzione cambia, conseguentemente, il meccanismo di comunicazione tra processi. Meccanismo che, comunque, e' strettamente necessario dal momento che a ben poco servirebbe un sistema multitask in cui i vari processi non fossero in grado di comunicare tra loro.
Vedremo maggiormente in dettaglio tutto questo nelle prossime puntate di questa rubrica. In questa sede anticiperemo solo la differenza fondamentale tra le due forme sopra indicate. In figura 2A e' rappresentata schematicamente la memoria utente di un computer multitask in cui i processi cooperano ad ambiente locale. In pratica per ogni processo in esecuzione e' riservata una zona di memoria contenente il codice da eseguire e un'ulteriore zona di memoria (sempre per ogni processo) in cui sono mantenuta tutte le variabili (e le altre strutture) di quel processo. Nella cooperazione ad ambiente globale (figura 2B) oltre a questo troviamo anche un Environment comune a tutti i processi in esecuzione.
Nel primo caso non disponendo di zone di memoria condivise la comunicazione interprocess avviene attraverso porte e canali di comunicazione utilizzando primitive di scambio messaggio tipo:

SEND(Porta, Messaggio)

che spedisce il messaggio indicato sulla porta indicata, e

RECEIVE(Porta, Messaggio)

che riceve dalla porta indicata il messaggio in arrivo depositandolo nella variabile (o struttura) indicata come secondo parametro.
Nel caso dell'ambiente globale la comunicazione avviene, come detto, utilizzando zone di memoria condivisa. In questo caso e' pero' necessario arbitrare in qualche modo l'accesso a questo zone di interscambio per evitare ad esempio che piu' processi la utilizzino per scrivere oppure che un processo destinatario inizi a leggere prima che un altro processo mittente abbia terminato di scrivere o viceversa. I meccanismi per implementare tale arbitraggio sono vari e si va dalla semplice sospensione del multitasking per tutta la durata dell'operazione di lettura/scrittura a piu' sofisticati meccanismi di locking, semafori o monitor per gestire, ad esempio, condivisione di device. Ma di tutto questo, come detto, ne riparleremo nelle prossime puntate.

Multitasking e pipeline

Per concludere questa breve introduzione alle tecniche multitask, vogliamo indicarvi un altro utilizzo di questo tipo di programmazione. I processi di cui e' formato un programma possono anche avere un funzionamento pipeline (catena di montaggio) in cui ogni modulo e' collegato ad un modulo successivo e ad un modulo precedente, eccezion fatta, ovviamente, per il modulo iniziale e finale della catena.
In figura 3 e' mostrato uno spooler di stampa "evoluto" con questo tipo di funzionamento. Il primo processo preleva da un opportuno canale di input (ad esempio un file su disco o lo stesso flusso di uscita di qualsiasi altro programma) i caratteri da stampare e li spedisce, l'uno dopo l'altro, al processo successivo che forma le parole. In pratica raggruppa insiemi di caratteri separati da almeno un spazio. Le parole cosi' formate vengono passate al processo MakeLine che, come dice il suo nome, forma una prima bozza della linea da stampare occupandosi di unire tra loro tante parole fino ad arrivare ad una lunghezza massima pari alla dimensione della linea di stampa.
La linea grezza cosi' formata e' passata al processo Justify che esegue la justificazione rispetto ai margini e la centratura della linea rispetto alla pagina di stampa. Cosi' le linee ormai gistificate possono essere passate all'ultimo processo "attore" che raccoglie le linee giustificate per formare le pagine di stampa complete, eventualmente, di numerazione, titolo di giro, ecc. Per finire le pagine sono inviate al processo di stampa che semplicemente si occupa dell'interfacciamento con la stampante vera e propria.
Ovviamente mentre e' in stampa il documento 'x' gli altri processi possono essere occupati nel medesimo istante a "lavorare" il documento 'x-1', 'x-2', ecc. ecc. Proprio come si conviene ad una catena di montaggio.
Sul prossimo numero cominceremo trattare un po' piu' da vicino alcune delle argomentazioni introdotte questo mese. Arrivederci..


Articolo pubblicato su www.digiTANTO.it - per ulteriori informazioni clicca qui