CS551Warm-up Project #2Bill Chenghttp://merlot.usc.edu/cs551-f121 Computer Communications - CSCI 551 Copyright © William C. Cheng2 Computer Communications - CSCI 551 Copyright © William C. Cheng Multi-threading Exercisegood source is the book by Nichols, Buttlar, and Farrell‘‘Pthreads Programming’’, O’Rielly & Associates, 1996Make sure you are familiar with the pthreads libraryyou must learn how to use mutex and condition variablescorrectlypthread_mutex_lock()/pthread_mutex_unlock()pthread_cond_wait()/pthread_cond_signal()/pthread_cond_broadcast()you must learn how to handle UNIX signalspthread_sigmask()/sigwait()pthread_setcancelstate()pthread_setcanceltype()pthread_testcancel()#include <pthread.h>/* #include <thread.h> */thread_t user_threadID;sigset_t new;void *handler(), interrupt();main( int argc, char *argv[] ) { sigemptyset(&new); sigaddset(&new, SIGINT); pthread_sigmask(SIG_BLOCK, &new, NULL); pthread_create(&user_threadID, NULL, handler, argv[1]); pthread_join(user_threadID, NULL); printf("thread handler, %d exited\n",user_threadID); sleep(2); printf("main thread, %d is done\n", thr_self());} /* end main */3 Computer Communications - CSCI 551 Copyright © William C. Cheng pthread_sigmask()Look at the man pages of pthread_sigmask() on nunki andtry to understand the example theredesignate child thread to handler SIGINTparent thread blocks SIGINTstruct sigaction act; void *handler(char argv1[]){ act.sa_handler = interrupt; sigaction(SIGINT, &act, NULL); pthread_sigmask(SIG_UNBLOCK, &new, NULL); printf("\n Press CTRL-C to deliver SIGINT\n"); sleep(8); /* give user time to hit CTRL-C */} void interrupt(int sig) { printf("thread %d caught signal %d\n", thr_self(), sig);} 4 Computer Communications - CSCI 551 Copyright © William C. Cheng pthread_sigmask()Child thread examplechild thread unblocks SIGINTchild thread is designated to handle SIGINT, no otherthread will get SIGINTline at a bankEx:5Queueing Abstraction Computer Communications - CSCI 551 Copyright © William C. ChengQ1µλµS2S1multiprocessor executing jobs from a shared job queueER6Arrivals & Departures Computer Communications - CSCI 551 Copyright © William C. ChengQ1µλµS2S1Q1S2S10 tai : arrival timedi : departure timesi : service timeri : response (system) timeqi : queueing timed1C1a1 s1 C1 r1 C2a2 s2 C2 r2 d2d47Arrivals & Departures (Cont...) Computer Communications - CSCI 551 Copyright © William C. ChengQ1µλµS2S1Q1S2S10 tq1, q2, q3 ~ 0q4 > 0d3 r4 s4 C4a4C4 q4 s3 r3 C3a3C3C1C1C2C2Execution: remove an event from the head of queue,"execute" the event (notify the corresponding object so it caninsert the next event)Insert into the event queue according to timestamp of a newevent; insertion may cause additional events to be deletedor inserted8Event Driven Simulation Computer Communications - CSCI 551 Copyright © William C. ChengAn event queue is a sorted list of events according totimestamps; smallest timestamp at the head of queueObject oriented: every object has a "next event" (what it willdo next if there is no interference), this event is inserted intothe event queuePotentially repeatable runs (if the same seed is used toinitialize random number generator)Q1 : emptyInitially:A : [ a1, create(C1) ]Ex: 4 objects, A (arrival), Q1 (passive object, does notgenerate events), S1, S29Event Driven Simulation (Cont...) Computer Communications - CSCI 551 Copyright © William C. ChengS1 : NULLS2 : NULLonly one event, next event to fire is [ a1, create(C1) ]create(C1), Q1->enqueue(C1)Q1->dequeue(C1), S1->serve(C1)A : [ a2, create(C2) ] S1 : [ d1, destroy(C1) ]S2 : NULLQ1 : emptymin(a2, d1) = a2, next event to fire is [ a2, create(C2) ]create(C2), Q1->enqueue(C2)Q1->dequeue(C2), S2->serve(C2)A : [ a3, create(C3) ] S1 : [ d1, destroy(C1) ]S2 : [ d2, destroy(C2) ]Q1 : empty10Event Driven Simulation (Cont...) Computer Communications - CSCI 551 Copyright © William C. Chengmin(a3, d1, d2) = d1, next event to fire is [ d1, destroy(C1) ]destroy(C1)A : [ a3, create(C3) ] S1 : NULLS2 : [ d2, destroy(C2) ]Q1 : emptymin(a3, d2) = a3, next event to fire is [ a3, create(C3) ]A : [ a4, create(C4) ] S1 : [ d3, destroy(C3) ]S2 : [ d2, destroy(C2) ]create(C3), Q1->enqueue(C3)Q1->dequeue(C3), S1->serve(C3)Q1 : emptyQ1 : C4min(a4, d2, d3) = a4, next event to fire is [ a4, create(C4) ]A : [ a5, create(C5) ] S1 : [ d3, destroy(C3) ]S2 : [ d2, destroy(C2) ]create(C4), Q1->enqueue(C4)etc.11Event Driven Simulation (Cont...) Computer Communications - CSCI 551 Copyright © William C. ChengQ1S2S10 tC1C1a1d1C2C2a2d2d4C4a4C4C3d3C3a312Time Driven Simulation Computer Communications - CSCI 551 Copyright © William C. ChengEvery active object is a threadTo execute a job for x msec, the thread sleeps for x msecLet your machine decide which thread to run next(irreproducible results)Compete for resources (such as Q1), must use mutexit may not get woken up more than x msec later,and sometimes, a lot more than x msec laternunki.usc.edu does not run a realtime OSyou need to decide if the extra delay is reasonableor it is due to a bug in your codea customer is a passive object, it gets passed aroundYou will need to implement 3 threads (or 1 main thread and3 child threads)13Time Driven Simulation (Cont...) Computer Communications - CSCI 551 Copyright © William C. Chengthe arrival thread sits in a loopsleeps for an interval, trying to match a giveninterarrival time (from trace or coin flip)wakes up, creates a customer object, enqueues thecustomer to Q1, and goes back to sleepif the Q1 was empty before, need to signal or broadcasta queue-not-empty conditiontwo server threadsinitially blocked, waiting for the queue-not-emptycondition to be signaled(cont...)14Time Driven Simulation (Cont...) Computer Communications - CSCI 551 Copyright © William C. Chengtwo server threads (cont...)when it is unblocked, if Q1 is not empty, dequeues acustomer, sleeps for an interval matching theservice time of the customer, eject the customer fromthe system, check if Q1 is empty, etc.if there is no work to perform, go wait for thequeue-not-empty condition to be signaledarrival thread will stop generating customers and terminate<Cntrl+C>server threads must finish serving its current customerthe arrival thread needs to clear out Q1must print statistics for all customer seenQ1 : emptyInitially:A : sleep(α1=a1)Notation:S1 : idleS2 : idleA wakes up at a1: create(C1), Q1->enqueue(C1)Q1->dequeue(C1), S1->serve(C1)A
View Full Document
Unlocking...