CSE 120 Principles of Operating Systems Fall 2004 Lecture 6 Synchronization Geoffrey M Voelker Synchronization z 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 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 October 7 2004 CSE 120 Lecture 6 Synchronization 2 1 Shared Resources z z We will initially focus on coordinating access to shared resources 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 Patterns for coordinating accesses to shared resources Locks mutexes semaphores monitors condition variables Bounded buffer producer consumer etc October 7 2004 CSE 120 Lecture 6 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 October 7 2004 CSE 120 Lecture 6 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 October 7 2004 CSE 120 Lecture 6 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 z z What is the balance of the account now Is the bank happy with our implementation October 7 2004 CSE 120 Lecture 6 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 October 7 2004 CSE 120 Lecture 6 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 October 7 2004 CSE 120 Lecture 6 Synchronization 8 4 Mutual Exclusion z z 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 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 October 7 2004 CSE 120 Lecture 6 Synchronization 9 Critical Section Requirements Critical sections have the following requirements 1 Mutual exclusion 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 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 October 7 2004 CSE 120 Lecture 6 Synchronization 10 5 Mechanisms For Building Critical Sections z Locks z Semaphores z Basic easy to get the hang of but hard to program with Monitors z Very primitive minimal semantics used to build others High level requires language support operations implicit Messages Simple model of communication and synchronization based on atomic transfer of data across a channel Direct application to distributed systems Messages for synchronization are straightforward once we see how the others work October 7 2004 CSE 120 Lecture 6 Synchronization 11 Locks z z z While one thread executes withdraw we want some way to prevent other threads from executing in it Locks are one way to do this A lock is an object in memory providing two operations z Threads pair calls to acquire and release z acquire before entering the critical section release after leaving a critical section Between acquire release the thread holds the lock acquire does not return until any previous holder releases What can happen if the calls are not paired Locks can spin a spinlock or block a mutex October 7 2004 CSE 120 Lecture 6 Synchronization 12 6 Using Locks withdraw account amount acquire lock balance get balance account balance balance amount put balance account balance release lock return balance acquire lock balance get balance account balance balance amount acquire lock Critical Section put balance account balance release lock balance get balance account balance balance amount put balance account balance release lock What happens when blue tries to acquire the lock Why is the return outside the critical section Is this ok What happens when a third thread calls acquire October 7 2004 CSE 120 Lecture 6 Synchronization 13
View Full Document
Unlocking...