Παράδειγμα
int counter;
process_one()
{
int i;
i = counter;
i = i + 1;
counter = i;
}
process_two()
{
int i;
i = counter;
i = i + 1;
counter = i;
}
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) μεταξύ των κρίσιμων τμημάτων πρέπει να εξασφαλίζει:
- Μια το πολύ διεργασία μπορεί να εκτελεί ένα κρίσιμο τμήμα.
- Δεν επιτρέπονται υποθέσεις σχετικά με την ταχύτητα ή το πλήθος των επεξεργαστών.
- Διεργασία που δε βρίσκεται σε κρίσιμο τμήμα δεν επιτρέπεται να αναστείλει άλλες διεργασίες
- Ο χρόνος στον οποίο μια διεργασία θα εισέλθει στο κρίσιμο τμήμα της πρέπει να είναι πεπερασμένος.
Ενεργός αναμονή
Ορισμένοι τρόποι για την επίτευξη του αμοιβαίου αποκλεισμού είναι οι παρακάτω:- Απενεργοποίηση των διακοπών
- Αυστηρή εναλλαγή
- Λύση του Peterson (προσθήκη μεταβλητής "ενδιαφέροντος")
- Η εντολή TSL
Απενεργοποίηση και αφύπνιση
Η οργάνωση της διαδιεργασιακής επικοινωνίας γίνεται χρησιμοποιώντας αφηρημένες βασικές αρχές διαδιεργασιακής επικοινωνίας (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);
}
}
Σημαφόροι
To ζεύγος των σημαφόρων (semaphores)- 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);
}
}
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)
- wait
- signal
Μεταβίβαση μηνύματος
Άλλος τρόπος διαδιεργασιακής επικοινωνίας είναι η χρήση της μεταβίβαση μηνύματος (message passing) που μπορεί να εκφραστεί με τις διαδικασίες:- 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
Νηματικές διεργασίες
Οι νηματικές διεργασίες (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, ¶meter);
}
Ένα νήμα μπορεί να τερματίσει τη λειτουργία του με τη συνάρτηση
_endthread.
thread_function(int *parameter)
{
}
/* Used to pass a parameter to the thread */
int parameter_value;
main()
{
parameter = 42;
_beginthread(thread_function, 0, ¶meter);
}
Σημαφόροι
Στα Windows 32 (95/98/NT/2000/...) μια σειρά από συναρτήσεις επιτρέπουν το χειρισμό σημαφόρων.-
Η συνάρτηση 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);
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 = {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);
}
* 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.
- Bill Lewis and Daniel J. Berg. Multithreaded Programming with Pthreads. Prentice-Hall, 1997.
- Bradford Nichols, Dick Buttlar, and Jacqueline Proulx Farrell. Pthreads Programming. O'Reilly and Associates, 1996.
- Kay A. Robbins and Steven Robbins. Practical Unix Programming: A Guide to Concurrency, Communication, and Multithreading. Prentice-Hall, 1996.
- 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».