CSE 120 Principles of Operating Systems Winter 2007 Lecture 5 Synchronization Keith Marzullo and Geoffrey M Voelker Synchronization z Threads cooperate in multithreaded programs To share resources 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 z For correctness we need to control this cooperation z We control cooperation using synchronization z 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 January 23 2007 CSE 120 Lecture 5 Synchronization 2 1 Shared Resources We initially focus on coordinating access to shared resources z Basic problem z 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 January 23 2007 CSE 120 Lecture 5 Synchronization 3 Classic Example z 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 z z 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 January 23 2007 CSE 120 Lecture 5 Synchronization 4 2 Example Continued z z 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 z 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 January 23 2007 CSE 120 Lecture 5 Synchronization 5 Interleaved Schedules z 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 put balance account z z What is the balance of the account now Is the bank happy with our implementation January 23 2007 CSE 120 Lecture 5 Synchronization 6 3 Shared Resources z The problem is that two concurrent threads or processes accessed a shared resource account without any synchronization z We need mechanisms to control access to these shared resources in the face of concurrency z z 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 January 23 2007 CSE 120 Lecture 5 Synchronization 7 When Are Resources Shared z Local variables are not shared private z Global variables and static objects are shared z Refer to data on the stack Each thread has its own stack Never pass share store a pointer to a local variable on another thread s stack 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 January 23 2007 CSE 120 Lecture 5 Synchronization 8 4 How Interleaved Can It Get How contorted can the interleavings be z We llll assume that the only atomic operations are We reads and writes of words z z Many 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 d l a th delay thread d as llong 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 January 23 2007 CSE 120 Lecture 5 Synchronization 9 Mutual Exclusion z We want to use mutual exclusion to synchronize access to shared resources z Code that uses mutual exclusion to synchronize its execution is called a critical section z 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 An example in real life sharing your bathroom with some housemates What requirements would you place on a critical section January 23 2007 CSE 120 Lecture 5 Synchronization 10 5 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 January 23 2007 CSE 120 Lecture 5 Synchronization 11 About Requirements There are three kinds of requirements that we ll use z Safety property nothing bad happens z Liveness property something good happens z Progress Bounded waiting Performance requirement z 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 January 23 2007 CSE 120 Lecture 5 Synchronization 12 6 Mechanisms For Building Critical Sections z Atomic read write z Locks z Semaphores z Monitors z Messages Can it be done Primitive minimal semantics used to build others Basic easy to get the hang of but hard to program with High level requires language support operations implicit Si l model Simple d l off communication i ti and d synchronization h i ti based
View Full Document
Unlocking...