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

Παράδειγμα

int counter;

process_one()
{
	int i;

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

process_two()
{
	int i;

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

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

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

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

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

• Απενεργοποίηση των διακοπών
• Αυστηρή εναλλαγή
• Λύση του Peterson (προσθήκη μεταβλητής "ενδιαφέροντος")
• Η εντολή TSL

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

• απενεργοποίηση (sleep).
• αφύπνιση (wakeup).

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);
	}
}

Σημαφόροι

• WAIT
• SIGNAL

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);
	}
}

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

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

• wait
• signal

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

• send(destination, message)
• receive(destination, message)

• με τη χρήση γραμματοκιβωτίων (mailbox) ή
• με τον καθορισμό συνάντησης (rendezvous).

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

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

void
thread_function(int *parameter)
{
}

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

main()
{
	parameter = 42;
	_beginthread(thread_function, 0, &parameter);
}

Σημαφόροι

• Η συνάρτηση CreateMutex δημιουργεί και επιστρέφει έναν νέο σημαφόρο. Χρησιμοποιείται ως εξής:

  HANDLE    mutex;				/* Declare semaphore variable */
  
  mutex = CreateMutex(NULL, FALSE, NULL);		/* Create semaphore */
  

• Η συνάρτηση WaitForSingleObject είναι η αντίστοιχη της WAIT. Χρησιμοποιείται ως εξής:

  WaitForSingleObject(mutex, INFINITE);
  

• Η συνάρτηση ReleaseMutex είναι η αντίστοιχη της SIGNAL. Χρησιμοποιείται ως εξής:

  ReleaseMutex(mutex);
  

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);

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

cl -D_MT /MT test.c

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

/*
 * 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 = {0, 0};
	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(-3, 3);
	Delta.Y = getrandom(-3, 3);

	/* 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(400, 50);
		}
		if (Coords.Y < 0 || Coords.Y > csbiInfo.dwSize.Y) {
			Delta.Y = -Delta.Y;
			Beep(600, 50);
		}
	}
	/* 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 = {0, 0};
	FillConsoleOutputCharacter(hConsoleOut, ' ', csbiInfo.dwSize.X * csbiInfo.dwSize.Y, Home, &dummy);
}

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

• Ellis Horowitz Βασικές αρχές γλωσσών προγραμματισμού. Δεύτερη αμερικάνικη έκδοση. σ. 311-348 Εκδόσεις Κλειδάριθμος, 1984.

• Andrew S. Tanenbaum Σύγχρονα λειτουργικά συστήματα. σ. 39-101 Εκδόσεις Παπασωτηρίου, 1993.

• Andrew S. Tanenbaum. Operating Systems: Design and Implementation, pages 45–105. Prentice-Hall, 1987.

• Περιεχόμενα

 Τελευταία αλλαγή: Δευτέρα, 2 Αυγούστου 2004 12:26 πμ
 Εκτός αν αναφέρεται κάτι διαφορετικό, όλο το πρωτότυπο υλικό της σελίδας αυτής του οποίου δημιουργός είναι ο Διομήδης Σπινέλλης παρέχεται σύμφωνα με τους όρους της άδειας «Creative Commons Attribution-Share Alike 3.0 Greece License».