DOC PREVIEW
U of I CS 241 - LECTURE NOTES

This preview shows page 1-2-3 out of 8 pages.

Save
View full document
View full document
Premium Document
Do you want full access? Go Premium and unlock all 8 pages.
Access to all documents
Download any document
Ad free experience
View full document
Premium Document
Do you want full access? Go Premium and unlock all 8 pages.
Access to all documents
Download any document
Ad free experience
View full document
Premium Document
Do you want full access? Go Premium and unlock all 8 pages.
Access to all documents
Download any document
Ad free experience
Premium Document
Do you want full access? Go Premium and unlock all 8 pages.
Access to all documents
Download any document
Ad free experience

Unformatted text preview:

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

U of I CS 241 - LECTURE NOTES

Documents in this Course
Process

Process

28 pages

Files

Files

37 pages

File I/O

File I/O

52 pages

C Basics

C Basics

69 pages

Memory

Memory

23 pages

Threads

Threads

14 pages

Lecture

Lecture

55 pages

C Basics

C Basics

24 pages

Signals

Signals

27 pages

Memory

Memory

45 pages

Threads

Threads

47 pages

Threads

Threads

28 pages

LECTURE

LECTURE

45 pages

Threads

Threads

30 pages

Threads

Threads

55 pages

Files

Files

37 pages

SIGNALS

SIGNALS

22 pages

Files

Files

37 pages

Threads

Threads

14 pages

Threads

Threads

13 pages

Load more
Download LECTURE NOTES
Our administrator received your request to download this document. We will send you the file to your email shortly.
Loading Unlocking...
Login

Join to view LECTURE NOTES and access 3M+ class-specific study document.

or
We will never post anything without your permission.
Don't have an account?
Sign Up

Join to view LECTURE NOTES 2 2 and access 3M+ class-specific study document.

or

By creating an account you agree to our Privacy Policy and Terms Of Use

Already a member?