HW1 and Synchronization & QueuingTA ReviewOutlineHW1Slide 5Slide 6Slide 7Slide 8Slide 9Slide 10Slide 11Slide 12Slide 13Slide 14Slide 15HW 1Slide 17Slide 18Slide 19Slide 20Slide 21Example 1: Producer-Consumer ProblemProducer-ConsumerSlide 24Slide 25Slide 26Slide 27Slide 28Slide 29Slide 30Slide 31Slide 32Slide 33Slide 34Slide 35Slide 36Slide 37Slide 38ChallengeSynchronization variablesProducer-Consumer ExampleExample 2: Dining PhilosophersDining Philosopher ChallengeThe simple implementationDeadlocked!Formal Requirements for DeadlockProblems for Week 7Problems for Week 7 (contd)Queuing TheoryQueuing Diagram for ProcessesQueueing TheoryAnalysis of Queueing BehaviorSlide 53Useful Facts From Queuing TheoryAnalysis of Single Server QueuePoisson Arrival & Service Rates SumSlide 57HW1 andSynchronization & QueuingCS241 Discussion Section Spring 2009Week 7TA Review•Optional TA Review SessionThe TAs will hold an optional review session to answer last-minute exam questions: Saturday, March 14, 2009 2pm – 4pm 2405 SCOutline•HW1 Discussion•Synchronization problems–Producer-consumer–Dining Philosophers•Queueing theoryHW1a) int *x, q=0; *x = q; (a): ________ b) int b[2]; *b = 20; (b): ________ c) char greet[80]; strcpy (‘‘Hello’’, greet); (c): ________HW1a) int *x, q=0; *x = q; (a): Incorrectb) int b[2]; *b = 20; (b): Correct c) char greet[80]; strcpy (‘‘Hello’’, greet); (c): IncorrectHW1 d) int *p, q[2]; p = malloc (sizeof (int)); *p = 3; q[2]=*p; (d): ________ e) int *x, y; x = &y; *x = 10; (e): ________HW1 d) int *p, q[2]; p = malloc (sizeof (int)); *p = 3; q[2]=*p; (d): Incorrecte) int *x, y; x = &y; *x = 10; (e): CorrectHW1Which scheduling policya) minimizes average task waiting time? _______ b) minimizes average task response time? ________ c) suffers the convoy effect? ________ d) has the largest context switch overhead? _______ e) may suffer a starvation effect? ______HW1Which scheduling policya) minimizes average task waiting time? ___SJF_____ b) minimizes average task response time? ____RR_____ c) suffers the convoy effect? ____FIFO_____ d) has the largest context switch overhead? ____RR_____ e) may suffer a starvation effect? ___SJF___HW1while (x > 0) {};x ++; /* assume this line is atomic */execute critical section; x – –; /* assume this line is atomic */Mutual exclusion:Progress:HW1while (x > 0) {};x ++; /* assume this line is atomic */execute critical section; x – –; /* assume this line is atomic */Mutual exclusion: NoProgress: YesHW1x2 = 1; x1 = 1;while (x1 != 0) {}; while (x2 != 0) {};critical section; critical section;x2 = 0; x1 = 0;Mutual exclusion:Progress:HW1x2 = 1; x1 = 1;while (x1 != 0) {}; while (x2 != 0) {};critical section; critical section;x2 = 0; x1 = 0;Mutual exclusion: YesProgress: NoHW1while (y = = 1) {}; while (y = = 0) {};y = 1; y = 0;critical section; critical section;Mutual exclusion:Progress:HW1while (y = = 1) {}; while (y = = 0) {};y = 1; y = 0;critical section; critical section;Mutual exclusion: NoProgress: NoHW 1a) Function g() calls function f().b) Function g() creates a POSIX thread that executes function f().a) Kill – b) Exec – c) Exit –HW 1a) Function g() calls function f().control passes from function g() to function f() then returns to g() when f() ends.b) Function g() creates a POSIX thread that executes function f().when the new thread is created, f() executes concurrently with g().a) Kill – sends a signal to a processb) Exec – runs a new program in the current address spacec) Exit – terminates a unix processHW1- Change behavior of SIGUSR1-Block SIGINTWhich of these?sleep alarm sigwaitsigprocmask sigaction sigsuspendHW1- Change behavior of SIGUSR1-Block SIGINTWhich of these?sleep alarm sigwaitsigprocmask sigaction sigsuspendHW1a) The turnaround time minus the _______ time is equal to the waiting time. b) The turnaround time is the time from the process creation time to its _____ time. b) The total time a process spends in queues is called ______ time d) Response time is the interval from ______ time to _____ timeHW1a) The turnaround time minus the execution time is equal to the waiting time. b) The turnaround time is the time from the process creation time to its finish time. b) The total time a process spends in queues is called waiting time d) Response time is the interval from arrival time to start timeExample 1:Producer-Consumer ProblemProducers insert items Consumers remove itemsShared bounded buffer e.g. a circular buffer with an insert and a removal pointer.Producer-ConsumerinsertPtrremovePtrProducer-ConsumerinsertPtrremovePtrProducer-ConsumerinsertPtrremovePtrProducer-ConsumerinsertPtrremovePtrProducer-ConsumerinsertPtrremovePtrProducer-ConsumerinsertPtrremovePtrProducer-ConsumerinsertPtrremovePtrProducer-ConsumerinsertPtrremovePtrBUFFER FULL: Producer must be blocked!Producer-ConsumerinsertPtrremovePtrProducer-ConsumerinsertPtrremovePtrProducer-ConsumerinsertPtrremovePtrProducer-ConsumerinsertPtrremovePtrProducer-ConsumerinsertPtrremovePtrProducer-ConsumerinsertPtrremovePtrProducer-ConsumerinsertPtrremovePtrProducer-ConsumerinsertPtrremovePtrBUFFER EMPTY: Consumer must be blocked!ChallengeNeed to prevent:Buffer OverflowProducer writing when there is no storageBuffer UnderflowConsumer reading nonexistent dataRace conditionTwo processes editing the list at the same timeSynchronization variablesCreate these variables to prevent these problems:items semaphoreCounts how many items are in the bufferCannot drop below 0slots semaphoreCounts how may slots are available in the bufferCannot drop below 0list mutexMakes buffer access mutually exclusiveProducer-Consumer Exampleds7-problem1.c shows an example implementation for one producer and one consumer, but without synchronization code.•Running it shows–Buffer underflows•Nonsense data is consumed–Buffer overflows•Unconsumed data is overwrittenExample 2:Dining PhilosophersDining Philosopher Challenge{ Think | Eat }N Philosophers circular table with N chopsticksTo eat the Philosopher must first pickup two chopsticksith Philosopher needs ith & i+1st chopstickOnly put down chopstick when Philosopher has finished eatingDevise a solution which satisfies mutual exclusion but avoids starvation and deadlockThe simple
View Full Document
Unlocking...