CS 241 Section Week #4(2/19/09)Topics This Section` SMP2 Review` SMP3 Forward` Semaphores` Problems` Recap of Classical Synchronization ProblemsSMP2SMP2 Review` qsort()` Define your own comparison function` int compare (const void *e1, const void *e2) {return (*(int*)e1 - *(int*)e2); }`Merge` You need to remove duplicates` How do you do that?` Pthreads` pthread_create and pthread_join` You DO NOT want to do this:for ( …) {pthread_create(…);…pthread_join(…);}SMP3SMP3 Forward` The scenario:Request: lineResponse: #client_0Serverfile0Read a lineclient_1file1Read a lineclient_2file2Read a line……SMP3 Forward` Communication is done through shared memories` queue` client_result[client_id]` You need to deal with three semaphores` queue_semaphore` To protect access to the queue` server_notify_semaphore` Client notify the server when data is added to the queue ` client_notify_semaphore` Array of semaphores` Client ID is used to access the semaphores` Server notify individual client a response is readySemaphoresExample (machex1.c)int N = 1000000;int x = 0;int main(int argc, char** argv){pthread_t threadCountUp,threadCountDown;pthread_create(&threadCountUp,NULL, countUp, NULL);pthread_create(&threadCountDown,NULL, countDown, NULL);}Examplevoid* countUp(){int i;for (i = 0; i < N; i++){int c = x;c++;x = c;}}void* countDown(){int i;for (i = 0; i < N; i++){int c = x;c--;x = c;}}Semaphores` Thread1 did ‘x++’ N times.` Thread2 did ‘x--’ N times.` Ideal result: ‘x’ is at its initial value.` Please try to compile machex1.c and run it with different N values: N= 1000, N = 1000000, etc…` Actual result?Semaphores` To fix this:` A thread must read, update, and write ‘x’ back to memory without any other threads interacting with ‘x’.` This concept is an atomic operation.Semaphores` Conceptually, we would want an ‘atomic’ scope:` void* countUp() {atomic {int c = x;c++;x = c;} // But this doesn’t exist…}Semaphores` Semaphores provides a locking mechanism to give us atomicity.` void* countUp() {sem_wait(&sema);int c = x;c++;x = c;sem_post(&sema);}Semaphores` Semaphores provides a locking mechanism to give us atomicity.` void* countUp() {sem_wait(&sema); LOCKSint c = x;c++;x = c;sem_post(&sema); UNLOCKS}Semaphores` To use a semaphore, you have to define it. Three steps to defining a semaphore:` 1. Include the header file:` #include <semaphore.h>Semaphores` To use a semaphore, you have to define it. Three steps to defining a semaphore:` 2. Declare the semaphore:` sem_t sema;(Declare this in a global scope.)Semaphores` To use a semaphore, you have to define it. Three steps to defining a semaphore:` 3. Initialize the semaphore:` sem_init(&sema, 0, 1);Semaphores` sem_init(&sema, 0, 1);` &sema: Your declared sem_t.` 0 : 0 := Thread Sync` 1 : Total of one threadinside a ‘locked’section of code.Semaphores` Three steps to starting them:` Include: #include <semaphore.h>` Define: sem_t sema;` Init: sem_init(&sema, 0, 1);Semaphores` Two functions to use them:` Acquiring the lock:sem_wait(&sema);` Releasing the lock:sem_post(&sema);Semaphores` Example Revisited:sem_wait()read x x++ context sw Î sema_wait()write x Í thread blockedsem_post()unlocked Î /*…*/ProblemsProblem 1 - Use semaphores to ensure order` machex2.c creates two threads to print out “Hello World”.` Use semaphores to ensure that that “World\nHello “ is never printed instead of “Hello World”.void *hello_thread(void *arg){sleep(2);fprintf(stderr, "Hello ");}void *world_thread(void *arg){sleep(1);fprintf(stderr, "World!\n");}int main(int argc, char **argv){pthread_t hello, world;pthread_create(&hello, NULL, hello_thread, NULL);pthread_create(&world, NULL, world_thread, NULL);pthread_join(hello, NULL);pthread_join(world, NULL);return 0;}Problem 1 - Use semaphores to ensure ordervoid *hello_thread(void *arg){sleep(2);fprintf(stderr, "Hello ");sem_post(&sem);}void *world_thread(void *arg){sleep(1);sem_wait(&sem);fprintf(stderr, "World!\n");sem_post(&sem);}sem_t sem;int main(int argc, char **argv){pthread_t hello, world;sem_init(&sem, 0, 0);pthread_create(&hello, NULL, hello_thread, NULL);pthread_create(&world, NULL, world_thread, NULL);pthread_join(hello, NULL);pthread_join(world, NULL);return 0;Problem 2 – Two semaphores` machex3.c creates two threads that both want access to two semaphores.` If you run this program, the program appears to stop running after a bit. Why?sem_t sem1, sem2;int main(int argc, char **argv){pthread_t t1, t2;sem_init(&sem1, 0, 1);sem_init(&sem2, 0, 1);pthread_create(&t1, NULL, p1, NULL);pthread_create(&t2, NULL, p2, NULL);pthread_join(t1, NULL);pthread_join(t2, NULL);return 0;}Problem 2 – Two semaphoresvoid *p1(void *arg){while (1) {printf("p1: sem_wait(&sem1);\n");sem_wait(&sem1);printf("p1: sem_wait(&sem2);\n");sem_wait(&sem2);printf("p1: locked\n");printf("p1: sem_post(&sem2);\n");sem_post(&sem2);printf("p1: sem_post(&sem1);\n");sem_post(&sem1);printf("p1: unlocked\n");}return NULL;}void *p2(void *arg){while (1) {printf("p2: sem_wait(&sem2);\n");sem_wait(&sem2);printf("p2: sem_wait(&sem1);\n");sem_wait(&sem1);printf("p2: locked\n");printf("p2:sem_post(&sem1);\n");sem_post(&sem1);printf("p2: sem_post(&sem2);\n");sem_post(&sem2);printf("p2: unlocked\n");}return NULL;Problem 2 – Two semaphoressem1_wait()sem2_wait()sem1_wait()sem2_wait()DEADLOCK!How to fix it??Classical Synchronization ProblemsProducer – consumer problem` Producers insert items ` Consumers remove items` Shared bounded buffer` Three semaphores` Slots: initialize to N, to prevent buffer overflow` Items: initialize to 0, to prevent buffer underflow` Mutex to protect accesses to shared buffer & pointers.Reader – writer problem` Multiple readers can read the data simultaneously` Only one writer can write the data at any time` A reader and a writer cannot in critical section together.` One global reader counter and 2 semaphores` Semaphore wrt to enforce mutual exclusion` Semaphore x to protect access to the global reader
View Full Document