DOC PREVIEW
U of I CS 241 - HW1 and Synchronization & Queuing

This preview shows page 1-2-3-4-5 out of 15 pages.

Save
View full document
View full document
Premium Document
Do you want full access? Go Premium and unlock all 15 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 15 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 15 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 15 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 15 pages.
Access to all documents
Download any document
Ad free experience
Premium Document
Do you want full access? Go Premium and unlock all 15 pages.
Access to all documents
Download any document
Ad free experience

Unformatted text preview:

HW1 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, 20092pm – 4pm2405 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): Correctc) char greet[80];strcpy (‘‘Hello’’, greet); (c): IncorrectHW1d) int *p, q[2];p = malloc (sizeof (int));*p = 3;q[2]=*p; (d): ________ e) int *x, y;x = &y;*x = 10; (e): ________ HW1d) int *p, q[2];p = malloc (sizeof (int));*p = 3;q[2]=*p; (d): Incorrecte) int *x, y;x = &y;*x = 10; (e): Correct HW1Which 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 sigsuspend HW1- Change behavior of SIGUSR1- Block SIGINTWhich of these?sleep alarm sigwaitsigprocmask sigaction sigsuspend HW1a) 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 ______timed) 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 finishtime. b) The total time a process spends in queues is called waitingtimed) Response time is the interval from arrivaltime to starttimeExample 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 chopsticksithPhilosopher needs ith& i+1stchopstickOnly put down chopstick when Philosopher has finished eatingDevise a solution which satisfies mutual exclusion but avoids starvation and deadlockThe simple implementationwhile(true) {think()lock(chopstick[i])lock(chopstick[(i+1) % N])eat()unlock(chopstick[(i+1) % N])unlock(chopstick[i])}Does this work?Deadlocked!When every philosopher has picked up his left chopstick, and no philosopher has yet picked up his right chopstick, no philosopher can continue.Each philosopher waits for his right neighbor to put a chopstick down, which he will never do.This is a deadlock.Formal Requirements for DeadlockMutual exclusion Exclusive use of chopsticksHold and wait conditionHold 1 chopstick, wait for nextNo preemption conditionCannot force another to undo their holdCircular wait conditionEach waits for next neighbor to put down chopstickThe simple implementations satisfies all of these.Problems for Week 71) ds7-problem1.c contains producer-consumer code. Use the provided semaphores and mutexes to prevent buffer overflows, underflows, and race conditions.Think: When should the consumer block? When should the producer


View Full Document

U of I CS 241 - HW1 and Synchronization & Queuing

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 HW1 and Synchronization & Queuing
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 HW1 and Synchronization & Queuing 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 HW1 and Synchronization & Queuing 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?