Passa al contenuto principale

3. Implementazione in GORDO

3.1 Introduzione a GORDO​

GORDO è un sistema time-sharing implementato su SDS Sigma 7. Di seguito delineiamo alcune delle caratteristiche rilevanti per il nostro documento.

3.1.1 File system di GORDO​

Il file system è orientato alle pagine. Esso è composto da file e directory. Un file consiste di un'intestazione e di un certo numero di pagine che compongono il corpo del file. Una directory consiste di un certo numero di voci che puntano a file o ad altre directory.

3.1.2 Processo di GORDO​

  • Un processo è un programma (procedure e dati) più il suo ambiente logico. In altre parole, un processo è un programma noto e controllato dallo scheduler di GORDO.
  • Un utente (un job) può avere diversi processi, tanto diversi quanto un compilatore, un loader, un editor, un programma applicativo, ecc. Un processo è creato tramite una chiamata di sistema (FORK).
  • Lo spazio a cui un processo può fare riferimento è lo Spazio Virtuale di 128k parole. Una parte (8k) di esso è riservata al sistema operativo, l'altra parte (120k) è direttamente accessibile dall'utente. Quest'ultimo può riempire o modificare la sua parte dello spazio virtuale tramite il 'coupling'. (vedi sotto: chiamate di servizio) con pagine prese da file diversi. La figura 3 illustra questo accoppiamento.
  • Un processo può richiedere servizi tramite chiamate di sistema. Le chiamate di sistema rilevanti per il nostro documento sono:

WAKE per risvegliare (rendere attivo) un processo addormentato SLEEP per addormentare un altro processo (o se stesso) COUPLE per accoppiare una pagina dallo spazio dei file allo spazio virtuale.

  • Un processo normalmente viene eseguito in modalità slave. Tuttavia, se è impostato come processo I/O, può accedere a istruzioni privilegiate.
  • I processi possono condividere dati tramite file collegati a directory "mail box".

Osservazione: in questa nota i termini processo e programma sono usati in modo intercambiabile.

[Figura 3 - Spazio virtuale e accoppiamento - vedi file PDF]

3.2 Panoramica dell'organizzazione software​

La figura 4 illustra l'organizzazione complessiva.

Il sistema si basa su due programmi principali: il "Network" e l'"Handler".

L'Handler è una routine di interrupt I/O strettamente legata all'interfaccia hardware IMP-HOST. Esso serve il processo Network nel trasmettere e ricevere messaggi di rete.

Il processo Network svolge la maggior parte del lavoro.

La sua funzione principale è soddisfare le richieste degli utenti di aprire/chiudere connessioni e di trasmettere/ricevere messaggi di rete. A tal fine,

  • stabilisce, identifica e chiude i collegamenti utilizzando le tabelle di allocazione (HOST, CONNECT, INPUT LINK; vedi 3.3.1.1)
  • è consapevole della presenza di nuovi utenti esplorando la directory mail box della rete;
  • comunica con gli utenti attivi tramite pagine condivise attraverso le quali sono scambiati messaggi e richieste (pagine condivise di connessione);
  • formatta i messaggi in entrata/in uscita in una pagina di lavoro. Questa pagina di lavoro ha un'estensione (anello di emergenza);
  • comunica con l'Handler tramite una pagina condivisa (pagina di comunicazione I/O) che contiene i buffer di comunicazione I/O.

[Figura 4 - Panoramica dell'organizzazione software - vedi file PDF]

3.3 Descrizione del software​

3.3.1 Strutture dati​

Il programma Network stabilisce, identifica e chiude collegamenti e connessioni utilizzando 3 tabelle:

Una tabella ordinata per HOST remoto #.

Una tabella ordinata per connessione #.

Una tabella ordinata per collegamento in entrata #.

(a) Tabella HOST (vedi figura 5)​

È una tabella di bit che indica i collegamenti in uscita liberi. Ha le seguenti caratteristiche:

  • Posizione: residente su disco
  • Accoppiamento: accoppiata allo spazio virtuale del processo Network.
  • Dimensione: tanti slot quanti sono gli HOST[s] remoti.
  • Struttura dello slot: tanti bit quanti sono i possibili collegamenti in uscita verso un HOST remoto, cioè 256.
  • Accesso: indicizzazione. Si accede a ciascuno slot tramite un HOST remoto #.
  • Particolarità: in tutta la tabella non più di 64 bit possono essere attivati. Questa cifra corrisponde al numero massimo di collegamenti in uscita che possono essere attivati contemporaneamente (indipendentemente dal numero di HOST[s] remoti).
(b) Tabella CONNECT​

Questa tabella tiene traccia dell'ambiente di tutte le connessioni.

Ha le seguenti caratteristiche:

  • Posizione: residente su disco
  • Accoppiamento: si accoppia allo spazio virtuale del processo Network
  • Dimensione: tanti slot quante sono le connessioni in uso.
  • Struttura dello slot: vedi figura 6. Ogni slot è lungo 2 parole
  • Accesso: indicizzazione. Si accede a ciascuno slot tramite una connessione #. Vedi 3.4 per il modo in cui è gestito.
  • Particolarità 1: la struttura dello slot corrispondente a una connessione primaria non è identica a quella di una connessione ausiliaria (vedi figura 7). Ciò perché le identificazioni e le richieste degli utenti avvengono tramite le pagine condivise primarie.
  • Particolarità 2: questa tabella è gestita in parallelo con le pagine di connessione (vedi 3.3.2 (b))
  • Particolarità 3: questa tabella è usata principalmente per trasmettere messaggi. (Per ogni connessione contiene il collegamento in uscita # e l'HOST remoto #, cioè tutte le informazioni richieste per trasmettere un messaggio.)

Questa tabella tiene traccia di tutti i collegamenti in entrata (input) ed è quindi strettamente legata alla tabella CONNECT.

[Figura 5 - Tabella HOST - vedi file PDF]

[Figura 6 - Tabella CONNECT: struttura dello slot - vedi file PDF]

[Figura 7 - Tabella INSERT LINK: struttura dello slot - vedi file PDF]

Ha le seguenti caratteristiche:

  • Posizione: residente su disco.
  • Accoppiamento: accoppiata allo spazio virtuale del processo Network.
  • Dimensione: tanti slot quanti sono i collegamenti in entrata, cioè quante sono le connessioni
  • Struttura dello slot: vedi figura 7. Ogni slot è lungo 1 parola
  • Accesso: hashing. Il valore della chiave hash si basa principalmente sul collegamento in entrata # e sull'HOST remoto #.
  • Particolarità 1: questa tabella è anche usata per memorizzare momentaneamente il numero di connessione mentre si stabilisce la connessione successiva. Vedi 3.4 per il modo in cui è gestita.
  • Particolarità 2: questa tabella è usata principalmente alla ricezione dei messaggi. (Per ogni collegamento in entrata contiene la connessione # corrispondente, cioè indirettamente l'identificazione dell'utente a cui il messaggio deve essere inoltrato)

3.3.1.2 Pagine buffer​

Tutte le pagine che stiamo per descrivere contengono due buffer (input e output). Questi buffer sono usati per inoltrare o elaborare messaggi.

La dimensione di ciascuno di questi buffer dovrebbe essere almeno pari a quella di un messaggio, cioè 8095 bit. Abbiamo scelto una dimensione del buffer di 253 parole (8096 bit) affinché entrambi i buffer siano contenuti in una sola pagina (512 parole). Le 6 parole rimanenti della pagina sono generalmente usate per il controllo.

Una tipica struttura di pagina buffer è illustrata nella figura 8.

(a) Pagina di comunicazione I/O​

Vedi figura 9.

Questa pagina di comunicazione I/O è usata come interfaccia tra l'Handler e il programma Network.

Nei buffer di questa pagina i messaggi sono assemblati (input) o disassemblati (output) parola per parola dall'Handler, ad esempio un messaggio "pronto a partire", predisposto dal programma Network nel buffer di output, è inviato all'esterno parola per parola dall'Handler.

Caratteristiche principali:

  • Posizione: residente in memoria: pagina bloccata
  • Accoppiamento: accoppiata allo spazio virtuale del processo Network
  • Contenuto: * buffer di input (253 parole) per i messaggi in entrata buffer di output (253 parole) per i messaggi in uscita
    • zona di controllo dell'input (6 semi-parole)
    • zona di controllo dell'output (6 semi-parole)
  • Struttura: vedi figura 9.
  • Particolarità: * il buffer di input è riempito dall'Handler (letto dall'hardware) e svuotato dal programma Network
    • viceversa per il buffer di output
(b) Pagine condivise di connessione (zona condivisa utente-rete)​

Caratteristiche generali:

  • Vi sono tante pagine condivise quante sono le connessioni.
  • Queste pagine, condivise tra la rete e i processi utente, costituiscono una zona di comunicazione per (1) scambiare i messaggi in entrambe le direzioni e (2) scambiare informazioni di controllo, ad esempio una richiesta di stabilire nuove connessioni.

Caratteristiche principali:

  • Posizione: residente su disco
  • Accoppiamento: accoppiate sia allo spazio virtuale di un processo utente sia allo spazio virtuale del processo Network.
  • Contenuto: - buffer di input (253 parole) per i messaggi in entrata
    • buffer di output (253 parole) per i messaggi in uscita
    • zona di controllo dell'input (6 semi-parole)
    • zona di controllo dell'output (6 semi-parole)
  • Struttura: vedi figura 10.
  • Particolarità 1: - il buffer di input è riempito dal Network e svuotato dall'utente.
    • viceversa per il buffer di output.
  • Particolarità 2: la zona di controllo corrispondente a una pagina condivisa di connessione primaria differisce da quella di una connessione ausiliaria. Ciò perché è tramite una "zona di controllo della connessione primaria" che le richieste di istituzione di connessioni ausiliarie sono trasmesse al processo Network.
(c) Pagina di lavoro​

Caratteristica generale:

  • Questa pagina consente ai programmi Network e Handler di lavorare indipendentemente su messaggi diversi e contribuisce quindi a una sovrapposizione. Ad esempio, mentre l'Handler è occupato a trasmettere un messaggio all'hardware, il programma Network può formattare (intestazione, marcatura, ecc.) il messaggio successivo da inviare all'esterno, così da poter riavviare l'Handler non appena questo è libero.

Caratteristiche principali:

  • Posizione: residente su disco
  • Accoppiamento: accoppiata allo spazio virtuale del processo Network
  • Contenuto: - buffer di input (253 parole) per i messaggi in entrata
    • buffer di output (253 parole) per i messaggi in uscita

Osservazione:

Durante la ricezione può accadere che un programma utente non sia pronto ad accettare un nuovo messaggio. In tal caso, per evitare di intasare il sistema, il Network memorizza momentaneamente il messaggio in entrata in uno dei buffer dell'anello di emergenza. (Se questo anello è pieno sarà invocata una routine di aiuto.)

Durante l'emissione tutte le operazioni sono sincronizzate con gli RFNM[s], pertanto tali procedure non devono essere previste. (Il programma Network consente a un utente di riemettere solo dopo aver ricevuto l'RFNM del messaggio trasmesso in precedenza.)

[Figura 8 - Tipica pagina buffer - vedi file PDF]

[Figura 9 - Struttura della pagina di comunicazione I/O - vedi file PDF]

[Figura 10 - Struttura della pagina condivisa di connessione - vedi file PDF]

3.3.2 Programmi​

3.3.2.1 Programma Handler​

Caratteristiche generali:

È una routine di interrupt I/O che pilota l'interfaccia hardware IMP/HOST per trasmettere o ricevere messaggi. La trasmissione e la ricezione sono effettuate in modalità duplex integrale.

Caratteristiche principali:

  • Posizione: residente in memoria. L'Handler si trova nella stessa zona di memoria del sistema operativo e può essere considerato parte di esso.
  • Avvio: tramite l'interrupt hardware IMP-HOST. Questo interrupt è attivato in uno dei seguenti casi:
  • durante la trasmissione, quando una parola del messaggio è stata completamente inviata all'IMP
  • durante la ricezione, quando una parola del messaggio è stata completamente ricevuta dall'IMP
  • durante il tempo di inattività, quando l'hardware ha ricevuto un ordine 'start input' o 'start output' dalla CPU del Sigma 7. Tali ordini sono emessi dal programma Network per provocare interrupt di ritorno (e di conseguenza per avviare indirettamente l'Handler).
  • Funzioni principali: * svuota il buffer di output trasmettendone il contenuto (messaggio in uscita) all'IMP. Questa operazione è effettuata parola per parola (32 bit) e fa uso di ordini "Write" per pilotare l'hardware HOST-IMP.
  • riempie il buffer di input con i dati ricevuti dall'hardware HOST-IMP (messaggio in entrata). Questa operazione è anch'essa effettuata parola per parola e fa uso di ordini "Read" per pilotare l'hardware HOST-IMP.
  • risveglia il programma Network quando una qualsiasi delle operazioni precedenti è completata.

3.3.2.2 Programma Network​

Caratteristiche generali:

Questo programma serve l'utente per aprire/chiudere connessioni e trasmettere/ricevere messaggi. Usa l'Handler come ausilio per interfacciarsi con l'hardware.

Dal punto di vista di GORDO è un processo regolare ed è trattato come tale.

Caratteristiche principali:

  • Posizione: residente su disco. Più precisamente, è su disco quando è addormentato ed è richiamato in memoria quando è risvegliato da un programma.
  • Avvio: è avviato tramite chiamate di servizio 'WAKE' emesse sia da un processo utente sia dall'Handler.
  • Funzioni principali: * stabilisce/elimina le connessioni in uscita su richiesta degli utenti. A tal fine invia messaggi di controllo (vedi 2.4.2) agli HOST[s] remoti al fine di ottenere collegamenti stabiliti/rilasciati; quindi notifica agli utenti.
    • assicura l'elaborazione dei messaggi di controllo in entrata (trasmessi sui collegamenti di controllo), ad esempio per contribuire all'istituzione/eliminazione di connessioni (quelle richieste dagli HOST remoti).
  • prepara la trasmissione dei messaggi in uscita. Preleva i messaggi di testo dalle pagine condivise (i messaggi vi sono memorizzati dagli utenti), li formatta (aggiunge intestazione, marcatura, checksum..) e li passa all'Handler per la trasmissione.
  • assicura la consegna dei messaggi in entrata. È l'operazione opposta a quella precedente. Gli utenti a cui i messaggi devono essere consegnati sono identificati tramite le intestazioni.
  • Configurazione dello spazio virtuale: vedi figura 11.
  • Particolarità: è integrato come processo I/O, così da poter accedere a istruzioni privilegiate (RD/WD per avviare indirettamente l'Handler).

[Figura 11 - Spazio virtuale del processo Network - vedi file PDF]

3.4 Procedure software​

Le procedure software dettagliate sono fornite nei diagrammi di flusso allegati all'Appendice A.

Tuttavia, per una rapida comprensione dell'implementazione, elenchiamo di seguito alcune tipiche procedure software.

3.4.1 Descrizione di alcune sequenze tipiche​

Si considerino alcune delle transazioni a disposizione dell'utente (vedi 2.4) e si indichino le procedure software di base che esse implicano. Per ciascun caso delineeremo (i) ciò che fa il programma utente e (ii) ciò che fa il programma Network.

(a) Aprire un collegamento primario (vedi anche 2.4.2)​

(i) Ciò che fa il programma utente[1]:​
  • memorizza nella directory mail box della rete il nome di un file, ad esempio DATA;
  • accoppia la prima pagina di questo file al proprio spazio virtuale;
  • memorizza informazioni in questa pagina (il proprio job/processo #, l'HOST remoto #, ad esempio (i));
  • risveglia il processo Network;
  • si addormenta.
(ii) Ciò che fa il programma Network:​
  • esplora la directory mail box della rete e accede al file DATA;
  • accoppia la prima pagina di questo file al proprio spazio virtuale (Zona condivisa, vedi 3.3.1.2). Si supponga che questa pagina sia la k-esima nella zona condivisa; k è la connessione interna #;
  • esplora lo i-esimo slot della nuova tabella HOST (vedi 3.3.1.1 (a)) e seleziona il primo bit = 0, ad esempio il bit (alpha)-esimo; alpha corrisponde al collegamento in uscita #;
  • memorizza informazioni (job/processo #, HOST remoto # (i), collegamento in uscita # (alpha)) nel k-esimo slot della tabella CONNECT (vedi 3.3.1.2).
  • memorizza momentaneamente la connessione # (k) nella tabella INPUT LINK. Ciò è effettuato creando una voce in questa tabella (calcolando l'hash del valore chiave: "collegamento in uscita # (alpha) + HOST remoto # (i) + flag in uscita".);
  • prepara il testo del messaggio ENQ PRIM 0 0 a e formatta un messaggio completo aggiungendo intestazione, marcatura, checksum, ecc.;
  • verifica lo stato dell'Handler (bit nella pagina I/O bloccata). Se l'Handler è libero, memorizza il messaggio di controllo 'pronto a partire' nel buffer di output della pagina I/O bloccata, avvia l'Handler e si addormenta. Altrimenti si addormenta.

Dopo un po' l'Handler risveglia il processo Network perché ha ricevuto un messaggio completo. Supponiamo che questo messaggio sia il messaggio di controllo inviato dall'HOST remoto per riscontrare l'istituzione della connessione. Il testo del messaggio dovrebbe essere:

ACK ENQ PRIM 0 0 alpha 0 0 beta

dove beta è il collegamento in entrata #. (vedi 2.4.2)

Vediamo ora cosa fa il programma Network quando riceve il suddetto messaggio di controllo:

  • recupera la connessione # precedentemente memorizzata nella tabella INPUT LINK ricalcolando l'hash dello stesso valore chiave (vedi sopra). Inoltre elimina questa voce;
  • crea una voce nella tabella INPUT LINK per il collegamento in entrata. A tal fine calcola l'hash del valore chiave: "collegamento in entrata # (beta]) + HOST remoto # (i) + "flag in entrata". In questa voce memorizza l'HOST # (i), il collegamento in entrata # (beta) e la connessione # (k);
  • aggiorna il k-esimo slot della tabella CONNECT memorizzando il collegamento in entrata # (beta);
  • attiva il bit 'net-user' nella k-esima pagina condivisa (pagina corrispondente alla connessione primaria appena aperta) e risveglia il processo utente;
  • si addormenta.

(b) Trasmettere un messaggio sul collegamento primario​

(i) Ciò che fa il programma utente[1].​
  • memorizza il testo del messaggio nel buffer di output della pagina condivisa della connessione primaria (vedi 3.3.1.2);
  • attiva il bit 'user-net' di questa pagina e risveglia il processo Network;
  • si addormenta.
(ii) Ciò che fa il programma Network:​
  • cerca la richiesta dell'utente, cioè esplora in sequenza le pagine condivise di connessione e seleziona quella che ha il bit 'user-net' attivato. Si supponga che k sia il numero della pagina selezionata nella lista condivisa, K è la connessione #;
  • determina il tipo di richiesta esaminando i 'request bits' della pagina condivisa k. Scopre che si tratta di una richiesta di trasmettere un messaggio.
  • preleva il testo del messaggio dal buffer di output della pagina condivisa k, lo formatta in un messaggio completo e lo trasmette all'Handler in modo molto simile a quanto sopra (vedi Aprire un collegamento primario).
  • si addormenta.

[1] Osservazione: in una prima fase l'utente scriverà direttamente le funzioni di rete nel proprio programma. In seguito saranno messe a disposizione dell'utente delle subroutine. Queste subroutine saranno molto simili a quelle descritte in 2.4.