Lecture 5 Synchronization with Locks CSE 120 Principles of Operating Systems Alex C Snoeren Lab 1 Due Thursday 10 20 Threads are made to share Global variables and static objects are shared Dynamic objects and other heap objects are shared Stored in the static data segment accessible by any thread Allocated from heap with malloc free or new delete Local variables are not shared Stack T1 Thread 2 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 Stack T2 Stack T3 Thread 3 Heap Static Data PC T2 CSE 120 Lecture 5 Synchronization Thred 1 Code PC T3 PC T1 2 The Trouble with Threads Basic problem If two concurrent threads 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 Patterns for coordinating accesses to shared resources Bounded buffer producer consumer etc CSE 120 Lecture 5 Synchronization 3 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 Cooperation is controlled using synchronization Threads interleave executions arbitrarily and at different rates Scheduling is not under program control Restrict the possible interleavings We ll discuss in terms of threads also applies to processes 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 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 in the same bank process 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 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 This is known as a race condition Each thread is racing to put balance before the other CSE 120 Lecture 5 Synchronization 7 Mutual Exclusion One way to ensure who wins the race is to only let one thread compete this is called mutual exclusion 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 withdraw account amount balance get balance account balance balance amount put balance account balance return balance CSE 120 Lecture 5 Synchronization Critical Section 8 Critical Section 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 No assumptions on performance Requirements must be met with any number of CPUs with arbitrary relative speeds CSE 120 Lecture 5 Synchronization 9 Locks One way to implement critical sections is to lock the door on the way in and unlock it again on the way out A lock is an object in memory providing two operations acquire before entering the critical section release after leaving a critical section Threads pair calls to acquire and release 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 CSE 120 Lecture 5 Synchronization 10 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 Critical Section acquire lock 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 CSE 120 Lecture 5 Synchronization 11 First Try Spin Locks How do we implement locks Here is one attempt struct lock int held 0 void acquire lock while lock held lock held 1 void release lock lock held 0 busy wait spin wait for lock to be released This is called a spinlock because a thread spins waiting for the lock to be released Does this work CSE 120 Lecture 5 Synchronization 12 Spin Locks No Two independent threads may both notice that a lock has been released and thereby acquire it struct lock int held 0 void acquire lock while lock held lock held 1 void release lock lock held 0 CSE 120 Lecture 5 Synchronization A context switch can occur here causing a race condition 13 Take Turns How did we solve this problem in Kindergarden Let s assume only two threads and take turns struct lock int turn 0 void acquire lock while lock turn this thread void release lock lock turn other thread Does this work Why not CSE 120 Lecture 5 Synchronization 14 Declaring Intent Problem was we didn t know if other thread was ready Let s be polite and wait until the other thread isn t interested struct lock int interested 2 FALSE FALSE void acquire lock lock interested this thread TRUE while lock interested other thread void release lock lock
View Full Document
Unlocking...