Capitolo 2

Processi e Thread

In Unix il processo è un'unità atomica. In questo lavoro, invece, il processo è stato spezzato in unità contenute strettamente al suo interno. Queste unità sono chiamate Thread e sostanzialmente consistono in uno stack e in un Program Counter.
La regione dati e codice resta parte del processo e viene condivisa da tutti i thread che si trovano all'interno del processo (fig. 2.1).

2.1 Schedulazione di Thread

struct Tcb {
       char SMI,           /* Modulo trasmittente */
            RMI,           /* Modulo ricevente */
            PR,            /* Priorita' */
            PX,            /* Indice del processo */
            DATA[4],       /* Campo dati */
            SR[2],         /* Registro di stato */
            *a[8],         /* Registri indirizzo: A0-A7 */
            *d[8],         /* Registri dato: D0-D7 */
            *PC;           /* Contatore del Programma */
      short Stack,         /* Stack assegnato */
            heap;          /* Heap assegnato  */
       int  BornTime,      /* Tempo di creazione */
            Mem;           /* Indirizzo Memoria Dati */
       char ST_PR;         /* Priorita' iniziale */
      void (* fun)();      /* Puntatore alla funzione da eseguire */
  unsigned int PID,PPID;   /* Process ID */
  CommandLine Command;     /* Campo di dati esteso */
  char Name[NameDim];      /* Nome del processo */
  struct Tcb *CP;          /* Puntatore al prossimo TCB */
};

typedef struct Tcb TCB;

struct CommandLine {
        char param1[NameDim],   /* primo parametro */
        param2[NameDim],        /* secondo parametro */
        flags[10]               /* opzioni */
 };

typedef struct CommandLine CommandLine;

Lo schedulatore in determinati momenti scandisce dalla coda a priorità più alta fino alla più bassa finché non trova un TCB pronto per l'esecuzione.

Per evitare che Thread a bassa priorità non vengano eseguiti mai, si attiva un meccanismo di aging, cioè dopo un certo tempo che un TCB permane in una coda viene passato alla coda con priorità immediatamente superiore come si vedrà più in dettaglio in seguito. Il TCB del Thread mandato in esecuzione viene prelevato dalla coda d'attesa e memorizzato da un apposito puntatore chiamato savedTCB. Al termine dell'intervallo di tempo assegnato al Thread, il TCB viene posto nella coda della priorità di partenza del Thread. Un Thread può trovarsi in uno degli stati visualizzati nella tabella 2.1.
Gli interrupt provenienti dalle porte seriali, che corrispondono ai terminali, vengono gestiti semplicemente utilizzando una tabella chiamata itable. In questa tabella ogni interrupt causa la modifica di un flag posto nella riga corrispondente all'interrupt stesso. Le routine di input-output gestiranno questi interrupt interrogando questa tabella.
Lo schedulatore ripete indefinitamente un ciclo in cui viene attivata la funzione ServiceInterruptTable, che verifica se è giunto un interrupt dalle porte seriali, e la funzione SetviceTaskQueue che gestisce la lista dei TCB.

Schedulatore
{
    ciclo {
        se la tabella di interrupt non e' vuota
            chiama la ServiceInterruptTable;
        altrimenti
            chiama la ServiceTaskQueue;
    }
}

ServiceTaskQueue (cmid)
/* aggiorna l'anzianita' dei thread e preleva il thread da eseguire */
{
    operazioni di aging;
    cerca il primo TCB disponibile;
    se il TCB e' stato trovato {
        preleva e salva il TCB;
        aggiorna la coda;
        se il modulo e' gia' stato eseguito
            chiama RESTORE();
        altrimenti
            chiama EXE();
    }
}

Aging
/* aumenta la priorita' dei thread in coda da piu' tempo */
{
    Se sono trascorsi TstTime istanti
        Per tutti i livelli di priorita' tranne il primo {
            preleva il primo TCB se disponibile;
            aggiorna i puntatori alla coda di priorita';
            se il TCB e' in coda da almeno AdvTime {
                incrementa la priorita' del TCB;
                aggiorna il tempo del TCB;
            }
            accoda il TCB;
        }
}

bool ServiceInterruptTable (cmid)
/* esamina gli interrupt di sistema */
{
    esamina la tabella degli interrupt;
    se la tabella e' vuota
        ritorna FALSO;
    altrimenti {
        imposta i dati in itcb;
        chiama EXEINT(itcb,cmid);
        ritorna VERO;
    }
}


void EXEINT()
/* esegue un modulo senza attivare il timer */
{
    se e' un modulo di sistema
        esegui il modulo
    altrimenti
        chiama la ServiceERROR
}

• Se il Thread va eseguito in foreground passa l'input al Thread.
• Se il puntatore alla memoria dati e codice è nullo (cioè si tratta del primo Thread di un processo) alloca una zona di memoria per la regione dati e, se non è un modulo di sistema, per la regione codici.
• Alloca una regione Stack e se si esegue un modulo di sistema ponilo nel Supervisor Stack Pointer (SSP), altrimenti mettilo nello User Stack Pointer (USP).
• Se è un'applicazione prepara i parametri formali sullo Stack.
• Se non è un modulo di sistema passa al modo utente.

void EXE()
/* avvia l'esecuzione di un thread per la prima volta */
{
    alloca una zona di stack
    se il puntatore alla zona dati e codice e' nullo
        chiama il loader
    se il processo non e' in background 
        manda l'input al processo
    se il processo non e' di sistema {
        passa in modalita' utente
        prepara i parametri formali sullo stack
    }
    avvia il timer
    avvia l'esecuzione
    FreeMod /* libera le risorse occupate */
}

ContextSwitch
/* salva lo stato di un thread interrotto */
{
    aggiorna la variabile tempo;
    se il modulo e' terminato
        disattiva l'interrupt in servizio;
    altrimenti {
        aggiorna SavedTCB con lo stato della CPU;
        se thread eseguito in modo utente
            copia lo USP (User Stack Pointer)
        altrimenti
            copia lo SSP (Supervisor Stack Pointer)
        ripristina la priorita' iniziale (ST_PR);
        accoda SavedTCB;
        disattiva l'interrupt in servizio;
        salta allo schedulatore;
    }
}

RESTORE
/* riprende l'esecuzione di un thread interrotto */
{
    aggiorna i registri della CPU;
    se thread eseguito in modo utente
        ripristina lo USP (User Stack Pointer)
    altrimenti
        ripristina lo SSP (Supervisor Stack Pointer)
    attiva il timer;
    riprendi l'esecuzione del Thread;
}

2.2 Operazioni sui processi

2.2.1 Creazione dei processi

CallData (cmid,PX,PR,ID,Port,Data)
/* prepara il TCB per un nuovo processo */
{
    chiama GetTCB;
    aggiornamento del TCB ottenuto;
    chiama QueueTCB;
}

TCB *GetTCB (cmid)
/* preleva un TCB dalla coda libera */
{
    se ci sono almeno due TCB liberi e non sto servendo un errore {
        prende il primo TCB dalla coda di TCB liberi;
        aggiorna la coda di TCB liberi;
        esamina la tabella dei TCB attivi;
    }
    se coda != vuota e nr. TCB attivi <= max {
        aggiorna il TCB prelevato;
        aggiorna la tabella dei TCB attivi;
        aggiorna il nr. di TCB usati;
        aggiorna eventualmente il max. nr. di TCB usati;
    }
    altrimenti
        chiama la ServiceERROR;
    ritorna il puntatore al TCB prelevato;
}

InsertTCB (p)
/* inserisce un TCB nella lista d'attesa */
{
    Prende la priorita' di p;
    Accoda il TCB alla coda di priorita' prelevata;
}

QueueTCB (p,ID)
/* accoda un IMP nella lista d'attesa */
{
    aggiorna SMI e RMI del TCB;
    chiama InsertTCB(p);
    aggiorna la tabella dei TCB attivi;
}

2.2.2 Cancellazione dei processi

FreeMod
/* libera le risorse occupate da un processo che e' terminato */
{
    libera la memoria dati e codice
    libera la memoria heap e stack;
    aggiorna la tabella degli stack;
    stampa il prompt;
    libera il TCB;
    salta all'inizio del ciclo dello schedulatore;
}

2.3 Sincronizzazione

void down(Semaforo)
/* occupa un semaforo binario */
bool *Semaforo;
{
#asm
    movea.l (sp),a0    // mette l'indirizzo del semaforo in a0
Sem_wait:
    tas (a0)           // testa e setta il semaforo
    beq Sem_end        // esce dal ciclo se il semaforo era up
    trap #14           // chiama il context switch
    bra Sem_wait       // entra in ciclo se il semaforo era down
Sem_end:
#endasm
}

void up (Semaforo)
/* libera un semaforo binario */
bool *Semaforo;
{
    *Semaforo = FALSE;
}

2.4 Thread

In sostanza ciascun thread è costituito da:

• un identificatore di thread (TID)
• un program counter (PC)
• uno stack
• uno stack pointer (SP)
• un puntatore alla memoria condivisa con altri thread
• un insieme di registri generici
• un indicatore di priorità

• una tabella di descrittori dei file
• un contatore di thread
• una serie di semafori binari
• una zona di codice
• un nome mnemonico
• un identificatore di processo (PID)
• un identificatore del processo padre (PPID)
• un puntatore alla zona di memoria heap

2.4.1 Creazione dei Thread

2.4.2 Cancellazione dei Thread

2.4.3 Comunicazione fra Thread (ITC)

Per creare un mutex basta chiamare la thread_mutex_init; questa funzione non fa altro che cercare un mutex inutilizzato e fornirne l'indice al richiedente.
Per bloccare un mutex si utilizza la funzione thread_mutex_lock. Questa funzione verifica che l'identificatore del mutex sia valido, poi ne calcola l'indirizzo e lo passa alla funzione down la quale utilizza l'istruzione TAS.
Sbloccare un semaforo è un'operazione abbastanza più complicata del bloccaggio. Non solo si deve riconoscere se il thread che fa la richiesta è il possessore di un effettivo mutex bloccato, si deve anche verificare se il mutex ha impedito la cancellazione del possessore; in questo caso si richiamerà la funzione di cancellazione (thread_cancel) la quale verificherà di nuovo se ci sono o meno le condizioni per la cancellazione del thread.
Per cancellare un mutex si chiama la funzione thread_mutex_destroy, la quale verifica se il mutex esiste ed è sbloccato nel qual caso effettua la cancellazione.

2.4.4 Applicazione

Il thread principale alloca una zona di memoria di 40 byte, setta i puntatori all'inizio e alla fine di questa zona di memoria, crea un mutex e lancia un thread che svolge il ruolo di produttore e un altro thread che svolge il ruolo di consumatore, infine si blocca in un ciclo infinito.
Il thread produttore compie un ciclo infinito all'interno del quale blocca il mutex, verifica se c'è posto per una nuova produzione, scrive un dato (un numero progressivo a 8 bit), incrementa ciclicamente il puntatore alla memoria e visualizza il dato scritto; infine sblocca il mutex.
Il thread consumatore compie un ciclo infinito all'interno del quale blocca il mutex, verifica se c'è almeno un dato da leggere, legge un dato (un numero progressivo a 8 bit), incrementa ciclicamente il puntatore alla memoria e visualizza il dato letto; infine sblocca il mutex.

/* problema del produttore consumatore */

int  i, /* puntatore alla memoria usato dal produttore */
     j, /* puntatore alla memoria usato dal consumatore */
     k, /* puntatore alla prima locazione di memoria */
     l; /* puntatore all'ultima locazione di memoria */
char c, /* contatore di dati presenti nel buffer */
     m, /* puntatore al mutex */
     t; /* TID */

/* ------------------------- */
/* thread produttore */
void prod()           
char e;
{
    e = 0;
    while (1) {       /* ciclo infinito */
        thlock(m);    /* blocca il mutex */
        if (c<40) {
            c = c+1;
            *i = e;   /* scrive il dato */
            i = i+1;
            if (i==l)
                i = k;
            write(" p ", e);
            e = e+1;
        }
        thunlock(m);  /* sblocca il mutex */
    }
}

/* ------------------------- */
/* thread consumatore */
void cons()          
{
    while (1) {       /* ciclo infinito */
        thlock(m);    /* blocca il mutex */
        if (c) {
            c = c-1;
            write(" p ", *j);
            j = j+1;
            if (j==l)
                j = k;
        }
        thunlock(m);  /* sblocca il mutex */
    }
}


/* ------------------------- */
/* thread principale */
void main()
{
    malloc(i,40);
    j = i;
    k = i;
    l = i+40;
    thmutexi(m);       /* inizializza il mutex */
    thcreate(t, prod);
    thcreate(t, cons);
    while (1);         /* ciclo infinito */
}