Class Note for CMPSCI 377 at UMass(1)
Class Note for CMPSCI 377 at UMass(1)
Popular in Course
Popular in Department
This 4 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 14 views.
Reviews for Class Note for CMPSCI 377 at UMass(1)
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 6 February 12 Lecturer Mark Corner Scribes Bruno Silva Jim Partzm 601 Processes vs threads One might argue that in general processes are more exible than threads For one thing they can live in two different machines and communicate via sockets they are easy to spawn remotely eg ssh foocsumassedu ls l etc However processes require explicit communication and risk hackery Threads also have their own prob lems because they communicate through shared memory they must run on the same machine and they require threadsafe code So even though threads are faster they are much harder to program In a sense we can say that processes are far more robust than threads since they are completely isolated from other another Threads on the other hand are not that safe since whenever one thread crashes the whole process terminates When comparing processes and threads we can also analyze the cost of context switches Whenever we need to switch between two processes we must invalidate the TLB cache the so called TLB shootdown see later lectures on virtual memory This of course makes everything slower When we switch between two threads on the other hand it is not necessary to invalidate the TLB because all threads share the same address space and thus have the same contents in the cache In other words on many operating systems the cost of switching between threads is much smaller than the cost of switching between processes Most largescale systems use a mixture of processes and threads threads within a process on one server communicating via a network socket to similar processes on other servers 61 Synchronization As we already know threads must ensure consistency otherwise race conditions nondeterministic results might happen Now consider the too much milk problem two people share the same fridge and must guarantee that therels always milk but not too much milk How can we solve it First we consider some important concepts and their de nitions Mutex prevents things from operating on the same data at the same time 0 Critical section a piece of code that only one thread can execute at a time 0 Lock a mechanism for mutual exclusion the program locks on entering a critical section accesses the shared data and then unlocks Also a program waits if it tries to enter a locked section 0 Invariant something that must always be true when not holding the lock For the above mentioned problem we want to ensure some correctness properties First we want to guarantee that only one person buys milk when it is need this is the safety property aka nothing bad happens Also we want to ensure that someone does buy milk when needed the progress property aka something 6 1 62 Lecture 6 February 12 good eventually happens Now consider that we can use the following atomic operations when writing the code for the problem 0 leave a note equivalent to a lock 0 remove a note equivalent to a unlock o don7t buy milk if there s a note equivalent to a wait An atomic operation is an unbreakable operation Once it has started no other thread or process can interrupt it until it has nished Our rst try could be to use the following code on both threads if no milk and no note leave note buy milk remove note Unfortunately this doesn7t work because both threads could simultaneously verify that there s no note and no milk and then both would simultaneously leave a note and buy more milk The problem in this case is that we end up with too much milk safety property not met Now consider our solution 2 Thread A leave note quotAquot if no note quotBquot if no milk buy milk remove note quotAquot Thread B leave note quotBquot if no note quotAquot if no milk buy milk remove note quotBquot The problem now is that if both threads leave notes at the same time neither will ever do anything Then we end up with no milk at all which means that the progress property not met Lecture 6 February 12 6 3 Let us now consider an approach that does work Thread A leave note A while note B do nothing if no milk buy milk remove note A Thread B leave note B if no note A if no milk buy milk remove note B This approach unlike the two examples considered on the previous class does work However it is complicated it is not quickand easy to convince yourself that these two sections of code always produce the desired behavior Furthermore it is wasteful Thread A goes into a loop waiting for B to release its note This is called busy waiting or spinning and wastes CPU time and energy when the CPU could be doing something useful Also it is asymmetric notice that even though both threads try to achieve the same goal they do it in very different ways This is a problem specially when we were to write say a third thread This third thread would probably look very different than both A and B and this type of asymmetric code does not scale very well Finally this code is potentially nonportable it doesn7t use a standard library So the question is how can we guarantee correctness and at the same time avoid all these drawbacks The answer is that we can augment the programming language with highlevel constructs capable of solving synchronization problems Currently the best known constructs used in order to deal with concurrency problems are locks semaphores monitors 611 LocksMutexes Locks also known as mutexes short for mutual exclusion locks provide mutual exclusion to shared data inside a critical session They are implemented by means of two atomic routines acquire which waits for a lock and takes it when possible and release which unlocks the lock and wakes up the waiting threads The rules for using locksmutexes are the following only one person can have the lock locks must be acquired before accessing shared data 1 2 3 locks must release after the critical section is done 4 locks are initially released 64 Lecture 6 February 12 The syntax for using locks in CC is the following pthreadmutexinit amp1 pthreadmutex1ockamp1 update data this is the critical section pthreadmutexunlockamp1 Let us now try to rewrite the Too Much Milk77 problem in a simpler cleaner more symmetric and portable way using locksi In order to do so the code for Thread A and also for Thread B would be the following pthreadmutex1ockamp1 if no milk buy milk pthreadmutexunlockampl This is clearly much easier to understand than the preVious solutions also it is more scalable since all threads are implemented in the exact same way
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'