Cooperazione, Bus, Arbitraggio
Dopo i vari "interrupt" giocosi dei mesi scorsi, Appunti di Informatica riprende (finalmente) a parlare di calcolatori. L'argomento di questo mese riguarda la cooperazione tra le varie unita' di cui un sistema di elaborazione e' composto: parleremo di interfacciamento a basso livello, di collegamenti dedicati e ripartiti, di meccanismi di arbitraggio deterministici e non. Buona lettura.
Cooperazione
Ogni sistema di elaborazione e' suddivo, sia logicamente che fisicamente, in vari moduli che cooperano affiatatamente per portare a termine i vari "doveri" ai quali sono "chiamati". Mentre le silenziose CPU elaborano le istruzioni dei programmi in esecuzione, le stampanti martellano sul nastro inchiostrato per produrre i loro output cosi' come il vecchio plotter del centro, tra uno scricchiolio e l'altro, arranca un po' a portare a termine il disegno richiesto. Contemporaneamente il lampeggio delle lucette delle unita' a dischi magnetici segnalano l'avvenuto completamento dell'operazione di lettura o scrittura richiesta pochi centesimi di secondo prima.
Zoomando idealmente dentro una qualsiasi di queste unita' "vedremmo" un interminabile brulichio di segnali elettrici tra i vari chip, che dialogano tra loro come il dispositivo che compongono dialoga con gli altri dispositivi della sala macchine...
Esistono essenzialmente due modi per far dialogare le varie componenti di un sistema di elaborazione: collegamenti dedicati o ripartiti. Col primo, per collegare due dispositivi si utilizza un collegamento fisico vero e proprio, nonche' privato, tra i due, cosicche' essi potranno scambiare dati in ogni momento, e senza dar conto ad altri. Lo schema di collegamento ripartito, piu' noto come collegamento a bus, a fronte di un risparmio di costo e a una espandibilita' del sistema assai facilitata, contrappone la limitazione che un solo dispositivo alla volta puo' inviare messaggi ad altri. Ovvero, se due dispositivi nello stesso istante vogliono accedere al bus per dialogare con altri dispositivi, dovranno dapprima competere per l'accesso esclusivo alla struttura di interconnessione e poi, chi dei due sara' scelto (dall'arbitro), potra' iniziare il trasferimento dei dati. L'altro aspetta.
Per il momento lasciamo perdere bus e arbitri e torniamo ai collegamenti dedicati. In figura 1 abbiamo schematizzato l'interfaccia di un collegamento dedicato tra due unita', U1 e U2, dove la prima produce un dato e l'invia alla seconda: potrebbero essere ad esempio rispettivamente un processore di I/O e una stampante... ma potrebbero anche essere una CPU e una memoria o due computer completi. Cio' che dobbiamo realizzare e' la sincronizzazione tra i due dispoditivi: U2 deve prendersi il dato dall'interfaccia solo dopo che U1 glielo ha inviato, cosi' come U1 non deve inviare altri dati se U2 non ha letto il dato precedente. L'interfaccia d'uscita di U1 e' composta da un registro detto OUT atto a contenere il dato da inviare (formato quindi da un numero di bit pari alla lunghezza, sempre in bit, dei dati) e da due flip-flop (registri di un bit) che abbiamo chiamato R1 d A1. Dall'altro lato, U2 disporra' di un registro di ingresso IN, della stessa grandezza di OUT, piu' due flip-flop R2 e A2. Per la cronaca R sta per Ready, pronto, A per Acknoveleggement, conoscenza. Tra queste tre coppie di registri, sempre come visibile in figura 1, i collegamenti elettrici non fanno altro che trasferire, nel verso della freccia, quanto presente in ognuno dei tre registri di uscita, nel corrispondente registro di ingresso del partner.
Commentiamo brevemente il funzionamento. Ricordiamo che U1 produce dati da inviare a U2. Appena un dato e' pronto per essere inviato, U1 lo inserisce nel suo registro di uscita OUT e pone ad 1 lo stato di R1 (anch'esso registro di uscita), inizialmente a 0. In questo modo avverte U2 che il dato e' pronto (ready). Subito dopo, U1, resta in attesa che U2 dia "segni di vita". Dall'altro capo del collegamento, appena U2 e' pronto a ricevere un nuovo valore testa innanzitutto il valore del suo registro di ingresso R2, se questo e' ad 1 vuol dire che e' presente un dato significatovo nel suo registro IN, se lo prende, e settando il valore di A2 (tenete sempre sott'occhio la figura 1) comunica a U1 di averlo ricevuto. Torniamo ad U1, il quale, come detto prima stava aspettando che U2 rispondesse (A2 e, consedguentemente, A1 pari a 1): ricevuta la risposta riazzera R1 per poi risettarlo al prossimo invio di un dato. U2 fara' lo stesso col suo A2. Si noti che, come promesso, e' realizzata la sincronizzazione tra i due dispositivi: non e' possibile (per doveri... d'algoritmo) che ne' U1, ne' U2 avanzi senza esplicito consenso da parte del corrispondente partner (una confessione: da buon maschilista meridionale secondo me ha sempre ragione U1... che resti tra di noi!).
Collegamenti ripartiti
In figura 2 e' mostrato, molto a grandi linee, lo schema di collegamento ripartito, o a bus che dir si voglia. Come visibile, le varie unita' sono tutte collegate alla medesima struttura di interconnessione detta appunto bus. Sul bus corrono i messaggi che le varie unita' si scambiano durante il funzionamento di tutto il sistema. Si badi, come gia' detto prima, che per unita' non si intende solo stampanti e drive per dischi magnetici, ma anche memoria, CPU, coprocessori ed altro. Per motivi di ottimizzazione, comunque, e' assai difficile che le architetture convenzionali si rifacciano completamente ad uno solo dei due schemi visti (interamente dedicato o interamente ripartito) ma si preferiscono normalmente i cosiddetti schemi misti, in cui per alcune unita' si usano collegamenti dedicati, per altre uno o piu' bus di collegamento. In ogni caso, quando in un sistema esiste un collegamento ripartito, le unita' che lo utilizzano possono accedere in scrittura solo uno per volta. Tornano alla figura 2, immaginiamo che in un dato istante il bus sia libero: in altre parle nessuna unita' sta dialogando con altri. Se in quel momento U1 decinde di dialogare con U3 puo' farlo e lo schema di sincronizzazione non e' molto dissimile da quello dedicato. L'unica differrenza riguarda il fatto che nel messaggio da inviare oltre al "testo" vero e proprio, il mittente deve inserire anche il nome del destinatario. Ovvero alcuni bit del registro OUT dell'interfaccia di uscita di ogni unita' contengono il codice del destinatario, i rimanenti il valore, come visto prima, da inviare. Il bus, ancora una volta, non e' che un insieme di fili elettrici (uno per bit, compresi i sincronizzatori A e R, come prima) sui quali e' presente l'informazione che chi scrive, ha immesso nella sua interfaccia di uscita. Chi sta aspettando un messaggio dal bus, non dovra' fare alctro che controllare se i primi bit corrispondono al suo "nome", nel qual caso puo' prelevare il dato e settare la linea A ad 1 per comunicare al mittente di aver ricevuto il dato.
A questo punto dovrebbe essere evidente che se due unita' scrivono nello stesso instante qualcosa sul bus (che, lo ripetiamo, non e' altro che un fascio di linee elettriche) i due messaggi si mischierebbero (destinatari, primi bit, compresi) rendendo impossibile il completamento delle due trasmissioni. Ovvero i due relativi destinatari dei due (distinti) messaggi sono sarebbero in grado di riconoscersi come tali essendo ormai il contenuto del bus non significativo.
Meccanismi di arbitraggio
Per garantire l'accesso esclusivo al bus occorre arbitrare i tentativi di accesso a questo, in modo tale che un solo contendente alla volta utilizzi la struttura di interconnessione in scrittura. Per quanto riguarda invece le operazioni di lettura, non e' necessario alcun arbitraggio dato che, come noto, la lettura contemporanea da parte di piu' dispositivi non altera il contenuto del bus.
I meccanismi di arbitraggio finora "inventati" possono facilmente essere suddivisi in due categorie: centralizzati e decentralizzati. Nel primo caso esiste un vero e proprio componente, separato dalle unita' collegate al bus, che decide chi, in caso di conflitto, avra' la meglio; nel secondo caso, le unita' in un certo senso intelligenti saranno in grado di cavarsela da sole senza aiuti esterni ne' fare pasticci sul bus. Cominciamo coi meccanismi centralizzati.
In figura 3 e' mostrato un primo schema di bus arbitrato: pur essendo dei piu' costosi a realizzarsi, appare come la soluzione piu' banale. Ogni unita', semplicemente, prima di accedere al bus "chiede il permesso" all'arbitro che, se non ha nulla in contrario, concedera' l'utilizzo. Le comunicazioni unita'-arbitro, come visibile sempre in figura 3, avvengono tramite collegamenti dedicati nei due versi (si notano infatti due freccie per ogni unita'). Se due o piu' unita' chiedono contemporaneamente all'arbitro di utilizzare il bus, riceveranno il consenso a turno secondo una disciplina statica o dinamica a scelta di chi progettera' l'arbitro vero e proprio. Ad esempio, se alcune unita' sono piu' iimportanti di altre, si puo' progettare l'arbitro in modo che, in caso di conflitto, dia precedenza a tali dispositivi. Oppure si puo' scegliere una disciplina pseudo casuale in cui, ad esempio, se in un precedente conflitto ha "vinto" A su B e C la prossima volta si prediligera' B e la prossima volta ancora B. Da sottolinerare che in nessun caso, se il richiedente e' unico e il bus e' libero, l'arbitro non concede d'ufficio la "vittoria" all'unico contendente.
In figura 4 e' mostrato uno schema di arbitraggio ben piu' semplice del precedente ma, come vedremo, con alcune limitazioni. Questa volta il collegamento unita'-arbitro non e' dedicato ma ripartito: un altro piccolo bus si servizio. Questo e' composto da due sole linee, Richiesta e Occupato, ambedue dalle unita' all'arbitro e non viceversa. L'arbitro, dal canto suo, dispone di una linea di uscita Disp che, collegata alla prima unita', da questa alla seconda e cosi' via, permette di far propagare le sue risposte.
Vediamo il funzionamento: quando una unita' intende utilizzare il bus in scrittura, manda la sua richiesta sull'omonima linea del bus di servizio. Se piu' di una unita' fa lo stesso non importa: le due richieste si sommeranno (restando pero' indistinguibili) e arriveranno all'arbitro come "una o piu' unita' ha chiesto il bus". Immaginiamo che al momento attuale il bus sia libero (l'arbitro, come vedremo, lo sa): e' sufficiente per l'arbitro mandare il segnale di disponibilita' alla prima unita' la quale, se non aveva richiesto l'uso, propaga tale segnale all'unita' successiva. Se invece l'unita' che riceve il segnale di disponibilita' e' effettivamente interessata all'operazione di scrittura, semplicemente blocca la propagazione e accede al bus segnalando all'arbitro, con la linea Occupato che da quel momento questo non e' piu' libero. Terminata la sua operazione di scrittura, resettando la stessa linea di prima comunica che il bus e' di nuovo disponibile. Il grosso svantaggio di questa architettura e' che, come abbiamo visto, le unita' piu' vicine all'arbitro avranno sempre la meglio su quelle piu' lontate, col ben noto rischio di attesa infinita da parte dei "piu' deboli". Sempreche' non eravamo interessati proprio a questo...
In figura 5 abbiamo una variante del precedente schema, con la quale e' possibile evitare l'inconveniente di cui sopra. Al posto della linea di disponibilita' nuda e cruda utilizziamo un altro bus di servizio col quale l'arbitro esegue un vero e proprio appello per individuare chi ha fatto la richiesta. Agendo infatti sulle linee di polling (vedi sempre figura 5) invia la disponibilita' nell'ordine che vuole, magari riprendendo dalla unita' successiva a quella che ha appena liberato il bus.
Tanto la seconda che la terza soluzione hanno l'inconveniente che un'unita', posto ad esempio che il bus e' libero, prima di ricevere il consenso, vuoi per la propagazione, vuoi per l'appello, finisce per attendere un tempo ben piu' lungo del "botta e risposta" dello schema di figura 3. A fronte pero' di questo svantaggio occorre segnalare che per quanto riguarda l'espandibilita' del sistema, ovvero la possibilita' di inserire nuovi elementi utilizzanti lo stesso bus, questa e' massima nello schema di figura 4 (basta inserire la nuova unita' in qualsiasi punto della catena), media nello schema ad appello (polling, in inglese) in quanto ci devono essere sufficienti linee sul bus di polling per ospitare nuovi arrivi e in piu' occorre comunicare in qualche modo all'arbitro tali variazioni; pressocche' nulla nello schema a richieste indipendenti. In quest'ultimo caso, infatti, per aggiungere una nuova unita' occorre cambiare interamente l'arbitro o sovradimensionarlo anzitempo (ma quanto?) in previsione di future espansioni.
Arbitri decentralizzati
I meccanismi di arbitraggio decentralizzati costano poco, hanno espandibilita' totale, funzionano egregiamente, ma... procediamo con ordine.
Presenteremo due tipi di arbitri decentralizzati, uno deterministico, l'altro non deterministico. Diciamo che in questo secondo caso, la riuscita o no di un accesso al bus e' un po' legata al caso. Sembra una barzelletta ma funziona: ne riparleremo dopo. Per prima cosa ricordiamo che, in uno schema di arbitraggio decentralizzato non esiste un particolare apparato preposto a consentire gli accessi esclusivi, ma le stesse unita' aumentate della logica necessaria, riescono a spartirsi amichevolmente il bus senza, mi scusino i... saggi, fare casino.
In figura 6 troviamo il primo esempio, deterministico. Le unita' oltre ad essere collegate al bus, tramite una linea di disponibilita' fanno circolare un omonimo segnale con disciplina circolare: U1 lo passa a U2, U2 a U3 e cosi' via fino all'ultimo della catena (nella figura Un) che lo passa nuovamente a U1. Questo accade quando il bus e' libero. Se ad un certo momento una unita' vuole scrivere sul bus, aspetta di ricevere la disponibilita' dall'unita' che la precede e sospendendo la propagazione del segnale puo' tranquillamente accedere alla struttura di interconnessione comune. Terminato l'utilizzo sara' suvviciente che l'unita' in questione faccia ripartire la disponibilita' affinche' tutto torni come prima. Lo svantaggio e' quello tipico delle discipline circolari in cui una unita' se necessita del bus subito dopo aver ceduto la disponibilita' deve attendere un intero "giro". E' deterministico dato che chiunque abbia necessita' del bus prima o poi verra' accontentato. Cosa che non e' detto che succeda col prossimo schema.
Arbitraggio non deterministico
Il meccanismo di arbitraggio certamente piu' simpatico e' quello non deterministico, forse perche' da' al funzionamento un tocco di elasticita' mentale comune al comportamento umano (purtroppo non sempre) e poco comune a tutti i rigidi schemi di funzionamento computerecci.
Per farla breve una unita' che intende utilizzare il bus, deve soltanto accertare (vedasi figura 7) che la linea di disponibilita' sia resettata, ovvero che il bus sia libero. Fatto questo setta tale linea e scrive il suo messaggio sul bus senza pero' settare la corrispondente linea di Ready con la quale autorizzerebbe il destinatario a prelevare il messaggio. Puo' infatti succedere che nello stesso istante due o piu' unita', accertato che la linea di Disponibilita' e' resettata scrivino sulla struttura di interconnessione provocando la somma dei messaggi che non e' significativa per nessuno dei destinatari. Come fa, dunque, una unita' a stabilire che sia l'unica a scrivere ? Semplice: prima di dare il Ready al destinatario prova a rileggere il suo stesso messaggio per vedere se uguale a quello che aveva scritto. Se e' tale, vuol dire che gli e' andata bene e' puo' dare il ready, altrimenti occorre leberare il bus (operazione che compieranno tutti coloro che sono entrati in collisione) e riprovare dopo un po'. Il buon funzionamento dipende molto da questo "po'", diverso per ogni unita' e calcolato accuratamente (incrociando possibilmente anche le dita), ma soprattutto occorre che le unita' non usino continuamente il bus altrimenti queste passeranno il tempo a fare tentativi piu' che ad avanzare con l'elaborazione. E questo in informatica non e' cosa buona e giusta...
