Note 9 for CMPSCI 377 at UMass
Note 9 for CMPSCI 377 at UMass
Popular in Course
Popular in Department
This 5 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 Note 9 for CMPSCI 377 at UMass
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
perahng ystems prmg 200 true 9 cto er 18 Lecturer Emery Berger Scribe Andrew McQuilkin 91 Synchronization Dif culties Independent threads will never a 39ect each other but when two or more threads are operating on the same objectx errors can occur 9 11 Race Conditions Race conditions occur when one thread executes m a particular object before another using the same object7 is done The result will be that the execution will depend on which thread nishes rst 912 Race Condition Example If both threads start at the same time the value of X will depend on which one nishes rst a Thread 1 X 1 a Thread 2 X 2 92 Too Much Milk You and your roornate always need to have milk in your apartment but you do not want to buy too much milk because it Will spoil How can you be sure that there will always be milk but never too much 921 Problem Hero is the problem if thch is no synchronization o 300 You arrive home a 305 You look in the fridge o 310 Realizing there is no milk you leave for the store a 315 Roomate arrives home a 320 Roomate looks in the fridge You arrive at the store 0 325 Roomate leaves for store You buy milk 9 2 Lecture 9 October 8 o 330 You arrive home When your rooniate gets back7 you Will have too much milk 922 How to Solve Synchronization Problems Mutual Exclusion mutex Allows only one thread at a time to Work on critical sections of the code Accomplishes this by 0 Locking down shared data once one thread has started on it o Unlocking when thread is done a Makes other threads wait for look to end Must satisfy correctness properties a Safety nothing had happens only one person buys milk 0 Progress eventually something good happens someone will buy milk if needed 923 Solution 1 A proposed solution to the too much milk problem a Both you and your roornate check to see if there is milk and if there is a note a if there is no milk and no note leave a note than go get some milk 0 When you get back with the milk remove the note Problem If both you and your rooniate get to the fridge at the same time then you will both see no note and no milk than both go and buy milk 924 Solution 2 Try leaving a not before checking for milk and a note a You leave a note a You check for a note from your roomate and if thch is any milk o If there is neither buy milk 0 Roomate does the same thing except checks for a note from you Problem If both of you arrive at the same time you will see each tlieiquots notes and neither one of you will buy milk Lecture 9 October 18 925 Solution 3 You Your You leave a note You wait until you are sure your roomate is not doing anything if once your roomate stops doing something there is still no milk go buy some Remove your 110863 roomate Roumate leaves a note If there is no milk or note from you7 he goes and buys milk He then removes his note Problems 93 To simplify synchronization highlevel language support was added exactly the Complicated Tough to gure out that it works Not intuitive Asymetrical You and your rooniate are executing different instruetions This means that each person needs their own set If there were more people you would need a set of instructions for each one Poor Utilization While you are waiting for your roomate to be done you are both not doing anything productive and also being kept busy by checking ln computequot this is know as lm quot72g This occurs when a thread that is not doing anything keeps using the CPU to cheek to see when it can continue 39IU Possilbly Nonportable The instructions rely on load and store commands to stay in the same order during execution that thev were in inside the code With pipelining th is not guaranteed and would result in nltn deterniinistio code Language Support It hides underlying details of hovc h nchronization is working This is accomplished using Locks provide mutual exclusion in critical sections of the code Atomic Operations set of operations that is Viewed as one by the processor so they are never done out of order Semaphonre A generalized lock that maintains a counter of available shared resources Monitors Automatically adds locks where needed in certain parts of the code 9 4 Lecture 9 October 8 931 Locks Looks provide mutual exclusion through two atomic routines Acquire takes a look once one it is available Release gives up the lock and alerts all the waiting threads that the lock is available In order to work correctly all locks must follow certain rule Acquire the lock before any shared data is accessed o Release the lock when clone a Shared data must be unlocked initially 932 Pthreads The synth for calling locks in U is as follows o pthl eadJnuteLinit initializes a lock object o pthrcaimutenloek Eel acquires lock when one is available a pt1r39e139rrt39lrtemunlrkt 11 releases lock 933 Too Much Milk With Locks Both you and your roomate perform the following steps Get lock on buying milk pthmadjnutenloek 851 Check for milk Z no If no milk go buy some b39lryrrtilk Release lock on buying milk pthreadmutermzloek The procedure for buying milk is now simple and syinetric 94 Implementing Locks Locks can be implemented in software using Dekker s algorithm but this has complicated code and busy waiting The best way is to have hardware support for locking 941 Disabling Internpts One way to ensure mutual exclusion is to disable interupts When the code enters a critical section the OS is told never to let the quanta expire giving the thread as much time to complete as it needs and ensuring that the processor will not switch threads lO interupts must also be disabled to prevent switching This means that you cannot use any lO in the critical section Also disabling interupts will not work on a multiprocessor system Lecture 9 October 18 95 942 Test and Set The Test and Setquot quot command is used for locking be quot y eps Within the command cannot be executed out of order The Test and Set l of 3 110A I a C i FARE and a BRANCH which sets a value lf these commands three separate commands were executed on a pipelined processor there is no guarantee that another thread would not he interleaved during their execution Using one command to do them all eliminates this problem because its commands will always be performed subsequently 943 Fences ln multithreaded processors there are no guarantees that two commands that are not directly related with be performed in any speci c order For example consider these three commands coded in this order X3 571 zx The processor will do x 3 before it does 2 x7 but there is no guarantee when y will be set to 1 If y needs to he set to 1 between the assigrmrent of x and 2 then you can use a quot fencew or memory barrier When put before and after y 17 it will prevent the processor from changing the order in which it executes that speci c line of code
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'