Ταυτοχρονισμός στα Windows NT

Διομήδης Σπινέλλης
Τμήμα Διοικητικής Επιστήμης και Τεχνολογίας
Οικονομικό Πανεπιστήμιο Αθηνών
dds@aueb.gr

Παραλληλία σε επίπεδο υλικού

Παραλληλία με τη χρήση αγωγών

Παραδείγματα

Ανάγνωση αποτελεσμάτων

υπολογισμός |
μετατροπή σε λέξη |
φωνητική ανάγνωση

bc | 
number | 
speak

Συχνότητα λέξεων

Μετατροπή κειμένου σε λέξεις |
φιλτράρισμα λέξεων |
ταξινόμηση |
μέτρηση κοινών γραμμών |
ταξινόμηση

tr -cs A-Za-z '\012' | 
grep '^A-Za-z' | 
sort | 
uniq -c | 
sort -rn

Συνθήκες ανταγωνισμού

Συνθήκες ανταγωνισμού ονομάζονται οι συνθήκες κατά τις οποίες το τελικό αποτέλεσμα της εκτέλεσης μιας σειράς διεργασιών κάτω από αυτές εξαρτάται από τη σειρά εκτέλεσής τους.

Παράδειγμα

int counter;

process_one()
{
        int i;

        i = counter;
        i = i + 1;
        counter = i;
}

process_two()
{
        int i;

        i = counter;
        i = i + 1;
        counter = i;
}

Κρίσιμα τμήματα

Το τμήμα του κώδικα μιας διεργασίας το οποίο δεν είναι ασφαλές να εκτελεστεί παράλληλα με άλλη διεργασία ονομάζεται κρίσιμο τμήμα (critical section).

Κάθε λύση στο πρόβλημα του αμοιβαίου αποκλεισμού (mutual exclusion) μεταξύ των κρίσιμων τμημάτων πρέπει να εξασφαλίζει:

  1. Μια το πολύ διεργασία μπορεί να εκτελεί ένα κρίσιμο τμήμα.
  2. Δεν επιτρέπονται υποθέσεις σχετικά με την ταχύτητα ή το πλήθος των επεξεργαστών.
  3. Διεργασία που δε βρίσκεται σε κρίσιμο τμήμα δεν επιτρέπεται να αναστείλει άλλες διεργασίες
  4. Ο χρόνος στον οποίο μια διεργασία θα εισέλθει στο κρίσιμο τμήμα της πρέπει να είναι πεπερασμένος.

Ενεργός αναμονή

Ορισμένοι τρόποι για την επίτευξη του αμοιβαίου αποκλεισμού είναι οι παρακάτω: Όλες οι παραπάνω λύσεις επιβάλουν στη διαδικασία που αναμένει να εκτελεί εντολές.

Απενεργοποίηση και αφύπνιση

Η οργάνωση της διαδιεργασιακής επικοινωνίας γίνεται χρησιμοποιώντας αφηρημένες βασικές αρχές διαδιεργασιακής επικοινωνίας (interprocess communication primitives). To ζεύγος είναι μια τέτοια αρχή. Με τις κλήσεις αυτές μπορεί να εκφραστεί το πρόβλημα του παραγωγού-καταναλωτή (producer-consumer).

const N = 100;

int queue[N];
int count;

void
producer(void)
{
        int item;

        for (;;) {
                create(&item);
                if (count == N)
                        sleep();
                count = count + 1;
                queue[count - 1] = item;
                if (count == 1)
                        wakeup(consumer);
        }
}

void
consumer(void)
{
        int item;

        for (;;) {
                if (count == 0)
                        sleep();
                item = queue[count - 1];
                count = count - 1;
                if (count == N - 1)
                        wakeup(producer);
                consume(&item);
        }
}
Η παραπάνω λύση έχει πρόβλημα συνθήκης ανταγωνισμού ως προς τη χρήση της μεταβλητής count.

Σημαφόροι

To ζεύγος των σημαφόρων (semaphores) επιτρέπει την οργάνωση της διαδιεργασιακής επικοινωνίας μια και αυτοί εκφράζουν ατομικές ενέργειες (atomic action). Με τις κλήσεις αυτές μπορεί να λυθεί το πρόβλημα του παραγωγού-καταναλωτή.
const N = 100;

semaphore mutex = 1;
semaphore empty = N;
semaphore full = 0;

void
producer(void)
{
        int item;

        for (;;) {
                create(&item);
                signal(&empty);

                signal(&mutex);
                count = count + 1;
                queue[count - 1] = item;
                wait(&mutex)

                wait(&full);
        }
}

void
consumer(void)
{
        int item;

        for (;;) {
                signal(&full);

                signal(&mutex);
                item = queue[count - 1];
                count = count - 1;
                wait(&mutex);

                wait(&empty);
                consume(&item);
        }
}

Παρακολουθητές

Οι παρακολουθητές (monitors) (ή ελεγκτές) είναι δομή της γλώσσας προγραμματισμού που εξασφαλίζει ότι σε μια συγκεκριμένη χρονική στιγμή μπορεί να εκτελείται. το πολύ μια διαδικασία μέσα στον παρακολουθητή.

Η δομή αυτή εξασφαλίζει τον αμοιβαίο αποκλεισμό κρισίμων τμημάτων. H αναστολή διεργασιών που δεν μπορούν να συνεχίσουν εξασφαλίζεται με τη χρήση των μεταβλητών συνθήκης (condition variables)

Μεταβίβαση μηνύματος

Άλλος τρόπος διαδιεργασιακής επικοινωνίας είναι η χρήση της μεταβίβαση μηνύματος (message passing) που μπορεί να εκφραστεί με τις διαδικασίες: Ο συντονισμός της αποστολής και της παραλαβής μπορεί να γίνει: Με τις κλήσεις αυτές μπορεί να εκφραστεί το πρόβλημα του παραγωγού-καταναλωτή.

const N = 100;

int queue[N];

void
producer(void)
{
        int item;
        message m;

        for (;;) {
                create(&item);
                receive(consumer, &m);
                build_message(item, &m);
                send(consumer, &m);
        }
}

void
consumer(void)
{
        int item;
        message m;

        for (i = 0;  i < 100; i++)
                send(producer, &m);
        for (;;) {
                receive(producer, &m);
                extract_item(&m, &item);
                send(producer, &m);
                consume(&item);
        }
}

Κλασικά προβλήματα

To πρόβλημα των συνδαιτημόνων φιλοσόφων

Λύσεις (σωστές και λανθασμένες):

Ταυτοχρονισμός στα Windows NT

Νηματικές διεργασίες

Οι νηματικές διεργασίες (threads) είναι ένας τρόπος ταυτοχρονισμού στον οποίο οι διεργασίες μοιράζονται τα όλα τα δεδομένα εκτός από αυτά που υπάρχουν στη στοίβα (δηλ. τις τοπικές μεταβλητές). Η δημιουργία τους υποστηρίζεται συνήθως από το λειτουργικό σύστημα και το μεταγλωττιστή. Στα Windows NT μπορούμε να δημιουργήσουμε πολλαπλές νηματικές διεργασίες με τη συνάρτηση _beginthread Χρησιμοποιείται ως εξής:
void
thread_function(int *parameter)
{
}

/* Used to pass a parameter to the thread */
int parameter_value;

main()
{
        parameter = 42;
        _beginthread(thread_function, 0, &parameter);
}
Ένα νήμα μπορεί να τερματίσει τη λειτουργία του με τη συνάρτηση _endthread.

Σημαφόροι

Στα Windows 32 (95/98/NT/2000/...) μια σειρά από συναρτήσεις επιτρέπουν το χειρισμό σημαφόρων. Παράδειγμα αποκλεισμού περιοχής:
HANDLE    mutex= CreateMutex(NULL, FALSE, NULL);

WaitForSingleObject(mutex, INFINITE);
/* Critical work starts here */
fseek(fp, desired_position, 0L );
fwrite(data, sizeof( data ), 1, fp );
/* Critical work ends here */
ReleaseMutex(mutex);

Μεταγλώττιση

Δηλώσεις για τις συναρτήσεις που αναφέραμε στις προηγούμενες παραγράφους υπάρχουν στην επικεφαλίδα <windows.h> και <process.h>. Για να μεταγλωττίσουμε ένα πρόγραμμα που περιέχει νηματικές διεργασίες προσθέτουμε στην εντολή του μεταγλωττιστή τις παραμέτρους /D_MT /MT . Παράδειγμα:
cl -D_MT /MT test.c

Παράδειγμα εφαρμογής

Το παρακάτω πρόγραμμα, bounce.c (βασισμένο σε πρόγραμμα που περιέχεται ως παράδειγμα στην τεκμηρίωση της Microsoft Visual C++) δημιουργεί ένα νέο νήμα που κινεί ένα πρόσωπο στην οθόνη κάθε φορά που πληκτρολογούμε A ή a. Τερματίζει τη λειτουργία του όταν πληκτρολογήσουμε q ή Q.
/*
 * Bounce - Creates a new thread each time the letter 'a' is typed. Each
 * thread bounces a happy face of a different color around the screen. All
 * threads are terminated when the letter 'Q' is entered. 
 *
 * This program requires the multithread library. For example, compile with the
 * following command line: CL /MT BOUNCE.C 
 */

#include <windows.h>
#include <stdlib.h>
#include <string.h>
#include <stdio.h>
#include <conio.h>
#include <process.h>

const int MAX_THREADS=32;

/*
 * getrandom returns a random number between min and max, which must be in
 * integer range. 
 */
static int
getrandom(int min, int max)
{
        return ((rand() % (int)(((max) + 1) - (min))) + (min));
}

void main(void);                        /* Thread 1: main */
void KbdFunc(void);                     /* Keyboard input, thread dispatch */
void BounceProc(char *MyID);            /* Threads 2 to n: display */
void ClearScreen(void);                 /* Screen clear */
void ShutDown(void);                    /* Program shutdown */
void WriteTitle(int ThreadNum);         /* Display title bar information */

HANDLE          hConsoleOut;    /* Handle to the console */
HANDLE          hRunMutex;      /* "Keep Running" mutex */
HANDLE          hScreenMutex;   /* "Screen update" mutex  */
int             ThreadNr;       /* Number of threads started */
CONSOLE_SCREEN_BUFFER_INFO csbiInfo;    /* Console information */


void 
main()
{                               /* Thread One */
        /* Get display screen information & clear the screen. */
        hConsoleOut = GetStdHandle(STD_OUTPUT_HANDLE);
        GetConsoleScreenBufferInfo(hConsoleOut, &csbiInfo);
        ClearScreen();
        WriteTitle(0);
        /* Create the mutexes and reset thread count. */
        hScreenMutex = CreateMutex(NULL, FALSE, NULL);  /* Cleared */
        hRunMutex = CreateMutex(NULL, TRUE, NULL);      /* Set */
        ThreadNr = 0;

        /* Start waiting for keyboard input to dispatch threads or exit. */
        KbdFunc();

        /* All threads done. Clean up handles. */
        CloseHandle(hScreenMutex);
        CloseHandle(hRunMutex);
        CloseHandle(hConsoleOut);
}

/*
 * Finish processing
 */
void 
ShutDown(void)
{                               /* Shut down threads */
        while (ThreadNr > 0) {
                /* Tell thread to die and record its death. */
                ReleaseMutex(hRunMutex);
                ThreadNr--;
        }
        /* Clean up display when done */
        WaitForSingleObject(hScreenMutex, INFINITE);
        ClearScreen();
}

/*
 * Read an process keyboard commands
 */
void 
KbdFunc(void)
{                               /* Dispatch and count threads. */
        int             KeyInfo;

        do {
                KeyInfo = _getch();
                if (tolower(KeyInfo) == 'a' && ThreadNr < MAX_THREADS) {
                        ThreadNr++;
                        _beginthread(BounceProc, 0, &ThreadNr);
                        WriteTitle(ThreadNr);
                }
        } while (tolower(KeyInfo) != 'q');

        ShutDown();
}

/*
 * Bounce the face around the screen.
 * This procedure is run by each thread.
 */
void 
BounceProc(char *MyID)
{
        char            MyCell, OldCell;
        WORD            MyAttrib, OldAttrib;
        char            BlankCell = 0x20;
        COORD           Coords, Delta;
        COORD           Old = {00};
        DWORD           Dummy;

        /* Generate update increments and initial display coordinates. */
        srand((unsigned) *MyID * 3);
        Coords.X = getrandom(0, csbiInfo.dwSize.X - 1);
        Coords.Y = getrandom(0, csbiInfo.dwSize.Y - 1);
        Delta.X = getrandom(-33);
        Delta.Y = getrandom(-33);

        /* Set up "happy face" & generate color attribute from thread number. */
        if (*MyID > 16)
                MyCell = 0x01;  /* outline face */
        else
                MyCell = 0x02;  /* solid face */
        MyAttrib = *MyID & 0x0F;/* force black background */

        do {
                /* Wait for display to be available, then lock it. */
                WaitForSingleObject(hScreenMutex, INFINITE);

                /* If we still occupy the old screen position, blank it out. */
                ReadConsoleOutputCharacter(hConsoleOut, &OldCell, 1, Old, &Dummy);
                ReadConsoleOutputAttribute(hConsoleOut, &OldAttrib, 1, Old, &Dummy);
                if ((OldCell == MyCell) && (OldAttrib == MyAttrib))
                        WriteConsoleOutputCharacter(hConsoleOut, &BlankCell, 1, Old, &Dummy);

                /* Draw new face, then clear screen lock */
                WriteConsoleOutputCharacter(hConsoleOut, &MyCell, 1, Coords, &Dummy);
                WriteConsoleOutputAttribute(hConsoleOut, &MyAttrib, 1, Coords, &Dummy);
                ReleaseMutex(hScreenMutex);

                /* Increment the coordinates for next placement of the block. */
                Old.X = Coords.X;
                Old.Y = Coords.Y;
                Coords.X += Delta.X;
                Coords.Y += Delta.Y;

                /* If we are about to go off the screen, reverse direction */
                if (Coords.X < 0 || Coords.X >= csbiInfo.dwSize.X) {
                        Delta.X = -Delta.X;
                        Beep(40050);
                }
                if (Coords.Y < 0 || Coords.Y > csbiInfo.dwSize.Y) {
                        Delta.Y = -Delta.Y;
                        Beep(60050);
                }
        }
        /* Repeat while RunMutex is still taken. */
        while (WaitForSingleObject(hRunMutex, 75L) == WAIT_TIMEOUT);

}

void 
WriteTitle(int ThreadNum)
{
        char            NThreadMsg[80];

        sprintf(NThreadMsg, "Threads running: %02d.  Press 'A' to start a thread,'Q' to quit.", ThreadNum);
        SetConsoleTitle(NThreadMsg);
}

void 
ClearScreen(void)
{
        DWORD           dummy;
        COORD           Home = {00};
        FillConsoleOutputCharacter(hConsoleOut, ' ', csbiInfo.dwSize.X * csbiInfo.dwSize.Y, Home, &dummy);
}

Βιβλιογραφία