Class Note for CMPSCI 377 at UMass(3)
Class Note for CMPSCI 377 at UMass(3)
Popular in Course
Popular in Department
This 3 page Class Notes was uploaded by an elite notetaker on Friday February 6, 2015. The Class Notes belongs to a course at University of Massachusetts taught by a professor in Fall. Since its upload, it has received 18 views.
Reviews for Class Note for CMPSCI 377 at UMass(3)
Report this Material
What is Karma?
Karma is the currency of StudySoup.
You can buy or earn more Karma at anytime and redeem it for class notes, study guides, flashcards, and more!
Date Created: 02/06/15
CMPSCI 377 Operating Systems Spring 2009 Lecture 8 Feb 19 Lecturer Mark Corner Scribes Bruno Silvaim Partan 81 Thread safety What does it mean for something to be threadsafe By saying that X is threadsafe we mean that if multiple threads use X at the same time we donlt have to worry about concurrency problems The STL for instance is not threadsafe if we were to create an STL queue and have two threads to operate on it simultaneously we would have to manually perform all locking operations The coat instruction is also not threadsafer Suppose now we want to build a threadsafe queue the methods we want the queue to have are insert tem remove and emptin The first question to be asked is what should remove do when the queue is empty One solution would be for it to return a special value such as NULL or 1 etc or to throw an exception It would much more elegant and useful however to make that function call wait until something actually appears in the queue By implementing this type of blocking system we are in fact implementing part of a producerconsumer systemi Now let us think of how to make the function waiti We can spin iiei write something like while emptyO x This however obviously doesnlt work since the test of emptiness needs to read shared data we need to put locks somewhere And if we lock around the whileempty line the program will hang foreveri Several other naive approaches do not work see slides for examples The conclusion is that we need some way of going to sleep and at the same time having someone to wake us up when there s something interesting to do Let us now present several possible implementations for this system and discuss why they do not work The first possibility is dequeue lockO needs to lock before checking if it s empty if queue empty sleep removeitem unlock enqueue lock insertitem if thread waiting wake up dequeuer unlock 81 82 Lecture 8 Feb 19 One problem with this approach is that the dequeuer goes to sleep while holding the lock How about the second possible approach dequeue lock need to lock before checking if it s empty if queue empty unlock sleep removeitem unlock enqueue lock insertitem if thread waiting wake up dequeuer unlock One problem here is that we are using an if instead of a while when checking whether or not the queue is empty Consider the case where the dequeuer is sleeping waiting for the enqueuer to insert an itemi The enqueuer inserts an item sends a wakeup signal and the dequeuer wakes up But then another dequeuer thread runs and removes the itemi The rst dequeuer thread now tries to remove an item from an empty queuei This problem can be xed by using a while instead of the if statement like this dequeue lock need to lock before checking if it s empty while queue empty unlock sleep removeitem unlock enqueue lock insertitem if thread waiting wake up dequeuer unlock This presents a more subtle and harder problem the dequeuer might unlock and then before it actually executes the sleep function the enqueuer could get the CPU back In this case the enqueuer would acquire the lock and insert the new item but since there would be no one sleeping there would be no thread to wake up so the enqueuer would simply unlock and never wake up the dequeuer again Then the dequeuer would get the CPU back nish calling sleep and sleep forever even though the queue is not empty The main issue is that another thread can run between the unlock and the sleep calls in dequeuei Lecture 8 Feb 19 8 3 The general solution to this type of problem is to make unlock sleep77 atomic which we will use to build our function called wait waitlock 1 cv c C unlockandsleeplc in one atomic step unlock and sleep waiting for cv c lockl reacquire the lock We use condition van39ables to do exactly that condition variables make it possible and easy to go to sleep by atomically releasing the lock putting the thread on the waiting queue and going to sleep Each condition variable has a wait queue77 of threads waiting on it managed by the threads library There are three important functions to be used when dealing with condition variables 0 wait ock l 01 c atomically releases the lock and goes to sleep When calling wait we must be holding the lock Depending upon the threads library wait may or may not reacquire the lock when awakened pthreadcondwait does reacquire the lock 0 signalcv c wakes up one waiting thread if there are any 0 broadcas cv c wakes up all waiting threads 811 Producerconsumer using condition variables Now let us present an implementation of a producerconsumer system using condition variables This im plementation works dequeue lockA while queue empty C wait A C atomically releases lock A and sleeps waiting for condition variable C When the thread wakes up it reacquires the lock C is the condition variable that means queue not empty removeitem unlockA enqueue lock A insertitem signal C unlock A In dequeue above if the thread wakes up and by chance the queue is empty there is no problem that s why we need the 77while77 loop
Are you sure you want to buy this material for
You're already Subscribed!
Looks like you've already subscribed to StudySoup, you won't need to purchase another subscription to get this material. To access this material simply click 'View Full Document'