Ablieferungstermin und erreichbare Punktzahl für diese Aufgabe, sowie Voraussetzungen für die Prüfungszulassung entnehmen Sie bitte http://sar.informatik.hu-berlin.de.

Lab 3 – User Level Thread Library

In dieser Praktikumsaufgabe sollen Sie eine einfache, nicht-präemptive User-Level-Thread-Bibliothek schreiben. Aus der Vorlesung wissen wir: Ein präemptiver Thread kann an beliebiger Stelle unterbrochen und verdrängt (von einem anderen Thread abgelöst) werden – die Unterbrechungen werden gewöhnlich durch Interrupts bewirkt. Der Entwurf einer Bibliothek für nicht-präemptive Threads ist deutlich einfacher, weil Threads nicht an einem beliebigen Zeitpunkt der Abarbeitung unterbrochen werden können. Allerdings müssen die Threads nun explizit die CPU von Zeit zu Zeit freiwillig aufgeben (yield) oder sie müssen Ihre Tätigkeit bis zum Eintreffen eines Ereignisses blockieren. Diese Art der Thread-Verwaltung wird “kooperatives Multi-Tasking” genannt. Es ist vor allem für I/O-lastige Prozesse geeignet.

Die zu erstellende Bibliothek ist eine User-Level-Thread-Bibliothek, weil der Kernel am Scheduling und Thread-Wechsel nicht beteiligt ist. Alle Threads laufen in ein und demselben Unix-Prozess und damit auch auf ein und derselben CPU, wobei der Scheduler ein Bestandteil des Prozesses selbst ist.

Leistungsumfang der Bibliothek

Ihre Bibliothek soll folgende Funktionen enthalten (legen Sie dafür eine Header-Datei ult.h an):

/* type of function executed by thread */
typedef void (*ult_func)();

/* spawn a new thread, return its ID */
extern int ult_spawn(ult_func f);

Die Funktion ult_spawn() erzeugt einen Thread-Control-Block (TCB) für die Funktion f() und stellt den Thread in die Run-Queue. Sie liefert den ID des erzeugten Threads zurück. An dieser Stelle erfolgt kein Scheduling, sondern die Abarbeitung wird mit dem laufenden Thread fortgesetzt, um die Erzeugung mehrerer Threads zu ermöglichen. 

/* yield the CPU to another thread */
extern void ult_yield(); 

Die Funktion ult_yield() gibt innerhalb eines Threads freiwillig den Prozessor auf. Es erfolgt der Aufruf des Schedulers und die Umschaltung auf den vom Scheduler ausgewählten Thread. 

/* current thread exits */
extern void ult_exit(int status); 

Wird innerhalb eines Threads ult_exit() aufgerufen, so wird der Thread zum Zombie und der Exit-Status wird abgespeichert.

/* thread waits for termination of another thread */
/* returns 0 for success, -1 for failure */
/* exit-status of terminated thread is obtained */
extern int ult_waitpid(int tid, int *status);

Mit ult_waitpid() kann abgefragt, ob der Thread mit dem angegebenen ID bereits beendet wurde. Ist der Thread bereits beendet, so kehrt die Funktion sofort zurück und liefert in status den Exit-Status des Threads (welcher als Argument an ult_exit() übergeben wurde). Läuft der Thread noch, so soll der aktuelle Thread blockieren und es muss auf einen anderen Thread umgeschaltet werden. Bei nachfolgenden Aufrufen des Schedulers soll überprüft werden, ob der Thread mittlerweile beendet wurde; ist dies der Fall, so soll der aktuelle Thread geweckt werden (am besten so, dass er auch als nächster Thread die CPU erhält).

/* read from file, block the thread if no data available */
extern int ult_read(int fd, void *buf, int count); 

Hinter ult_read() verbirgt sich die Funktion read() der Unix-API, welche Daten aus einer Datei (File-Deskriptor fd) in einen Puffer (buf) liest. Die Funktion ult_read() ist eine Wrapper-Funktion für read(), welche zusätzlich überprüft, ob ausreichend Daten verfügbar sind. Ist dies nicht der Fall, so wird der Thread blockiert und ein anderer Thread erhält die CPU. Bei nachfolgenden Aufrufen des Schedulers soll überprüft werden, ob mittlerweile ausreichend Daten vorliegen; ist dies der Fall, so soll der aktuelle Thread geweckt werden (s.o.). Dies löst ein Problem mit Systemrufen, welche im Kernel blockieren können (wie z.B. read()). Ohne diesen Mechanismus würde die gesamte User-Level-Thread-Bibliothek, die aus Sicht des Kernels ein Prozess ist, blockieren (selbst wenn andere User-Level-Threads lauffähig wären). Wir kümmern uns hier nur um die read()-Funktion, obwohl auch andere Systemrufe blockieren können. 

/* start scheduling and spawn a thread running function f */
extern void ult_init(ult_func f); 

Die Funktion ult_init() initialisiert die Bibliothek (insbesondere die Datenstrukturen des Schedulers wie z.B. Thread-Listen) und muss vor allen anderen Funktionen aufgerufen werden. Sie erzeugt einen einzigen Thread (analog zum “Init-Thread” bei Unix), aus welchem heraus dann alle anderen Threads erzeugt werden und welcher danach mit ult_waitpid() auf das Ende aller Threads wartet. 

Ein mögliches Testprogramm: 

void threadA()
{
    /* some task, can also spawn more tasks */
}

void threadB()
{
    /* some task, can also spawn more tasks */
}

void myInit()
{
    int cpid[2], i, status;
    printf("spawn A\n"); fflush(stdout);
    cpid[0] = ult_spawn(threadA);
    printf("spawn B\n"); fflush(stdout);
    cpid[1] = ult_spawn(threadB);
    for (i = 0; i < 2; i++) {
        printf("waiting for cpid[%d] = %d\n", i, cpid[i]); fflush(stdout);
        if (ult_waitpid(cpid[i], &status) == -1) {
            fprintf(stderr, "waitpid for %d failed\n", cpid[i]);
            _exit(-1);
        }
        printf("(status = %d)\n", status);
    }
    puts("ciao!");
    _exit(0);
}

int  main()
{
    printf("starting myInit\n"); fflush(stdout);
    ult_init(myInit);
    exit(0);
}

Testprogramm für die Bibliothek

Die Funktionalität der Bibliothek soll an einem einfachen Programm getestet werden. Das Programm besteht aus zwei Threads A und B. Thread A kopiert in einer Endlosschleife Bytes aus /dev/random nach /dev/null und führt dabei diverse Statistiken (Anzahl an bereits kopierten Bytes, Zeit seit Start des Threads, Durchsatz, etc.) mit. Thread B stellt eine einfache Kommando-Shell bereit, mit der man einerseits die Statistiken des Threads A auslesen kann (Kommando stats). Ein weiteres Kommando exit soll das gesamte Programm beenden.

Hinweise

Als TCB (Kontext) wird eine Datenstruktur bezeichnet, welche den kompletten Zustand der CPU (in unsere Fall zumindest alles, was aus Sicht des Nutzerprogramms relevant ist) zu einem bestimmten Zeitpunkt der Abarbeitung enthält. Dazu gehört unter Anderem der Befehlszeiger (instruction pointer), welcher die Adresse des nächsten abzuarbeitenden Befehls enthält. Für die Verwaltung von Threads ist es erforderlich, dass man den aktuellen TCB abspeichern und ihn durch einen anderen TCB ersetzen kann, der zuvor abgespeichert oder auf andere Art angelegt wurde.

Nehmen wir an, es existieren drei Threads T1, T2 und T3 sowie deren TCBs, C1, C2 und C3, wobei Thread T1 aktuell die CPU besitzt. Ruft nun dieser Thread die Kontextwechsel-Funktion tcb_swap(C1,C2) auf, so wird der aktuelle Prozessor-Zustand im TCB C1 abgespeichert und anstelle dessen der Prozessor mit den Werten aus C2 geladen. Dadurch fährt die Abarbeitung an derjenigen Stelle in Thread T2 fort, welche durch den Wert des Befehlszeigers im TCB C2 bestimmt wird. Ruft nun T2 irgendwann tcb_swap(C2,C3) auf, so wird die Abarbeitung mit T3 fortgesetzt; erfolgt dort wiederum ein Aufruf von tcb_swap(C3,C1), so taucht das Programm in T1 aus dem swap-Befehl auf, d.h. die Ausführung wird hinter dem swap-Befehl fortgesetzt. Aus Sicht von T1 hat das Programm im swap-Befehl nur für einige Zeit pausiert; während dieser Zeit wurden aber T2 und T3 bearbeitet.

Mögliche Realisierung von TCB und Kontext-Switch

Für das Error-Handling stellt der ANSI C Standard Funktionen bereit, die den aktuellen Ausführungs-Kontext speichern und wiederherstellen können. Dabei speichert die Funktion setjmp den aktuellen Ausführungs-Kontext, während die Funktion longjmp zu einem zuvor gespeicherten Kontext zurückkehren kann. Um nun allerdings mit diesen Funktionen eine Thread-Verwaltung zu implementieren fehlt noch eine Möglichkeit, einen neu erzeugten Thread mit einem Stack auszustatten. Dazu kann die Funktion signalstack benutzt werden. Sie legt einen neuen Stack für einen Signal-Handler an. Nun kann ein Signal-Handler aufgesetzt und ein Signal ausgelöst werden, dass nun auf dem soeben erzeugten Stack ausgeführt wird. Der Signal-Handler speichert den aktuellen Zustand und kehrt zurück, wobei der "Signal-Handler-Kontext" mit abgebaut wird. Nun kann die Abarbeitung des Threads beginnen. Im folgenden Programmausschnitt ist die beschriebene Technik illustriert. 

#include <malloc.h>
#include <setjmp.h>
#include <signal.h>
#include <stdio.h>

// 64kB stack
#define STACK 1024*64


jmp_buf child, parent;

// The child thread will execute this function
void threadFunction()
{
    printf( "Child thread yielding to parent\n" );
if ( setjmp( child ) )
         {
                 printf( "Child thread exiting\n" );
                 longjmp( parent, 1 );
         }

         longjmp( parent, 1 );
}

void signalHandler( int arg )
{
         if ( setjmp( child ) )
         {
                 threadFunction();
         }

         return;
}

int main()
{
         stack_t stack;
         struct sigaction sa;

         // Create the new stack
         stack.ss_flags = 0;
         stack.ss_size = STACK;
         stack.ss_sp = malloc(STACK );
         if ( stack.ss_sp == 0 )
         {
                 perror( "Could not allocate stack." );
                 exit( 1 );
         }
         sigaltstack( &stack, 0 );

         // Set up the custom signal handler
         sa.sa_handler = &signalHandler;
         sa.sa_flags = SA_ONSTACK;
         sigemptyset( &sa.sa_mask );
         sigaction( SIGUSR1, &sa, 0 );

         // Send the signal to call the function on the new stack
         printf( "Creating child thread\n" );
         raise( SIGUSR1 );

         // Execute the child context
         printf( "Switching to child thread\n" );
         if ( setjmp( parent ) )
         {
             printf( "Switching to child thread again\n" );
             if ( setjmp( parent ) == 0 ) longjmp( child, 1 );
         }
         else longjmp( child, 1 );

         // Free the stack
         free( stack.ss_sp );
         printf( "Child thread returned and stack freed\n" );
         return 0;
}

Definieren Sie die Datenstruktur tcb für die Abspeicherung von Kontexten, sowie folgende Funktionen:

•  tcb_getcontext(tcb *t)
  
  speichert den aktuellen Prozessor-Kontext in der übergebenen Kontext-Datenstruktur (wird der gespeicherte Kontext später wieder in den Prozessor geladen, so wird die Abarbeitung hinter tcb_getcontext() fortgesetzt),
   

• tcb_setcontext(const tcb *t)
  
  lädt den Kontext aus der übergebenen Datenstruktur in den Prozessor (Befehle nach dieser Funktion werden nicht ausgeführt),
   

• tcb_swapcontext(tcb *ourTcb, tcb *newTcb)
  
  speichert den Prozessor-Kontext in der ersten Datenstruktur ourTcb und lädt den Kontext aus der zweiten Datenstruktur newTcb in den Prozessor (beim erneuten Laden des gespeicherten Kontextes taucht das Programm wieder aus dieser Funktion auf)
   

• tcb_makecontext(tcb *t, void *func(), int argc, ...)
  
  erzeugt aus einer als Funktionszeiger übergebenen Funktion einen neuen Kontext; wird dieser Kontext später geladen (mit tcb_setcontext() oder tcb_swapcontext()), so beginnt die Abarbeitung der Funktion.

Weitere Hinweise

Verwalten Sie getrennte Thread-Queues: eine Run-Queue (laufende und lauffähige Threads), eine Wait-Queue (blockierte Threads) und eine Liste der Zombies. Dies vereinfacht die Verwaltung gegenüber einer einzigen Threads-Queue. Sie können zudem davon ausgehen, dass jeder Thread-Deskriptor zu einem Zeitpunkt nur in genau einer der Listen enthalten ist.

Ihr Scheduler sollte ein Round-Robin-Verfahren in der Run-Queue implementieren. Zudem sollte er blockierte Threads, welche lauffähig geworden sind, wecken. Beachten Sie bei der Implementierung Spezialfälle, z.B. den Fall, dass es keine lauffähigen Threads gibt. In diesem Fall muss der gesamte übergeordnete Unix-Prozess in ihrem Scheduler blockieren. Sie können dies mit der Unix- Funktion select() erreichen. Durch diese Funktion werden gleichzeitig mehrere Datei-Deskriptoren überwacht; die Funktion blockiert den Prozess und kehrt erst zurück, wenn in mindestens einer der Dateien Daten vorliegen.

Bei der Thread-Umschaltung treten auch Fälle auf, bei denen der aktuelle und der nachfolgende Thread identisch sind. Vermeiden Sie in diesen Fällen die Umschaltung aus Gründen der Effizienz.

Abgabe

Die Folien aus der Veranstaltung sind hier zu finden. Die Abgabe der Lösung erfolgt über GOYA. Für Besonderheiten, aufgetretene Probleme und anderweitige Anmerkungen benutzen sie bitte eine Datei index.html. Die Abgabe endet am 12.06.2006 um 12:00 Uhr. Beginnen Sie bitte rechtzeitig mit der Lösung der Aufgabe, da später eingehende Lösungen nicht berücksichtigt werden können. Bitte verwenden Sie C/C++ unter Linux und legen Sie der Lösung ein Makefile bei, das die Quellen automatisiert übersetzt.