CSE 120 Principles of Operating Systems Spring 2009 Lecture 5 Synchronization Geoffrey M Voelker Administrivia Homework 2 Due 4 23 The answers to almost all problems are short but thoughtful Travel Stockholm Bound April 14 2009 CSE 120 Lecture 5 Synchronization 2 Synchronization Threads cooperate in multithreaded programs To share resources access shared data structures Threads accessing a memory cache in a Web server To coordinate their execution One thread executes relative to another recall ping pong For correctness we need to control this cooperation We control cooperation using synchronization Threads interleave executions arbitrarily and at different rates Scheduling is not under program control Synchronization enables us to restrict the possible interleavings of thread executions Discuss in terms of threads also applies to processes April 14 2009 CSE 120 Lecture 5 Synchronization 3 Shared Resources We initially focus on coordinating access to shared resources Basic problem If two concurrent threads processes are accessing a shared variable and that variable is read modified written by those threads then access to the variable must be controlled to avoid erroneous behavior Over the next couple of lectures we will look at Mechanisms to control access to shared resources Locks mutexes semaphores monitors condition variables etc Patterns for coordinating accesses to shared resources Bounded buffer producer consumer etc April 14 2009 CSE 120 Lecture 5 Synchronization 4 Classic Example Suppose we have to implement a function to handle withdrawals from a bank account withdraw account amount balance get balance account balance balance amount put balance account balance return balance Now suppose that you and your significant other share a bank account with a balance of 1000 Then you each go to separate ATM machines and simultaneously withdraw 100 from the account April 14 2009 CSE 120 Lecture 5 Synchronization 5 Example Continued We ll represent the situation by creating a separate thread for each person to do the withdrawals These threads run on the same bank machine withdraw account amount balance get balance account balance balance amount put balance account balance return balance withdraw account amount balance get balance account balance balance amount put balance account balance return balance What s the problem with this implementation Think about potential schedules of these two threads April 14 2009 CSE 120 Lecture 5 Synchronization 6 Interleaved Schedules The problem is that the execution of the two threads can be interleaved balance get balance account balance balance amount Execution sequence seen by CPU balance get balance account balance balance amount put balance account balance Context switch put balance account balance What is the balance of the account now Is the bank happy with our implementation April 14 2009 CSE 120 Lecture 5 Synchronization 7 Shared Resources The problem is that two concurrent threads or processes accessed a shared resource account without any synchronization We need mechanisms to control access to these shared resources in the face of concurrency Known as a race condition memorize this buzzword So we can reason about how the program will operate Our example was updating a shared bank account Also necessary for synchronizing access to any shared data structure Buffers queues lists hash tables etc April 14 2009 CSE 120 Lecture 5 Synchronization 8 When Are Resources Shared Thread 2 Local variables are not shared private Thread 1 Stack T2 Stack T3 Thread 3 Heap Static Data Refer to data on the stack PC T2 Code Each thread has its own stack Never pass share store a pointer to a local variable on the stack for thread T1 to another thread T2 PC T3 PC T1 Global variables and static objects are shared Stack T1 Stored in the static data segment accessible by any thread Dynamic objects and other heap objects are shared Allocated from heap with malloc free or new delete April 14 2009 CSE 120 Lecture 5 Synchronization 9 How Interleaved Can It Get How contorted can the interleavings be We ll assume that the only atomic operations are reads and writes of words Some architectures don t even give you that We ll assume that a context switch can occur at any time We ll assume that you can delay a thread as long as you like as long as it s not delayed forever get balance account balance get balance account balance balance balance amount balance balance amount put balance account balance put balance account balance April 14 2009 CSE 120 Lecture 5 Synchronization 10 Mutual Exclusion We want to use mutual exclusion to synchronize access to shared resources Code that uses mutual exclusion to synchronize its execution is called a critical section This allows us to have larger atomic blocks Only one thread at a time can execute in the critical section All other threads are forced to wait on entry When a thread leaves a critical section another can enter Example sharing your bathroom with housemates What requirements would you place on a critical section April 14 2009 CSE 120 Lecture 5 Synchronization 11 Critical Section Requirements Critical sections have the following requirements 1 Mutual exclusion mutex If one thread is in the critical section then no other is 2 Progress If some thread T is not in the critical section then T cannot prevent some other thread S from entering the critical section A thread in the critical section will eventually leave the critical section 3 Bounded waiting no starvation If some thread T is waiting on the critical section then T will eventually enter the critical section 4 Performance The overhead of entering and exiting the critical section is small with respect to the work being done within it April 14 2009 CSE 120 Lecture 5 Synchronization 12 About Requirements There are three kinds of requirements that we ll use Safety property nothing bad happens Liveness property something good happens Progress Bounded Waiting Performance requirement Mutex Performance Properties hold for each run while performance depends on all the runs Rule of thumb When designing a concurrent algorithm worry about safety first but don t forget liveness April 14 2009 CSE 120 Lecture 5 Synchronization 13 Mechanisms For Building Critical Sections Atomic read write Locks Basic easy to get the hang of but hard to program with Monitors Primitive minimal semantics used to build others Semaphores Can it be done High level requires language support operations
View Full Document
Unlocking...