Lecture 5:Lecture 5:Synchronization with LocksSynchronization with LocksCSE 120: Principles of Operating SystemsAlex C. SnoerenLab 1 Due Thursday 10/20CSE 120 – Lecture 5: Synchronization 2Threads are made to shareThreads are made to share Global variables and static objects are shared◆ Stored in the static data segment, accessible by any thread Dynamic objects and other heap objects are shared◆ Allocated from heap with malloc/freeor new/delete Local variables are not shared◆ Refer to data on the stack◆ Each thread has its own stack◆ Never pass/share/store a pointer toa local variable on another thread’sstackStack (T1)CodeStatic DataHeapStack (T2)Stack (T3) Thread 3Thread 2PC(T1)PC(T3)PC(T2)Thred 1CSE 120 – Lecture 5: Synchronization 3The Trouble with ThreadsThe 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 avoiderroneous 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 4SynchronizationSynchronization 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◆ Threads interleave executions arbitrarily and at different rates◆ Scheduling is not under program control Cooperation is controlled using synchronization◆ Restrict the possible interleavings We’ll discuss in terms of threads, also applies toprocessesCSE 120 – Lecture 5: Synchronization 5Classic ExampleClassic Example Suppose we have to implement a function to handlewithdrawals 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 sharea bank account with a balance of $1000. Then you each go to separate ATM machines andsimultaneously withdraw $100 from the account.CSE 120 – Lecture 5: Synchronization 6Example ContinuedExample Continued We’ll represent the situation by creating a separatethread for each person to do the withdrawals These threads run in the same bank process: What’s the problem with this implementation?◆ Think about potential schedules of these two threadswithdraw (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;}CSE 120 – Lecture 5: Synchronization 7Interleaved SchedulesInterleaved Schedules The problem is that the execution of the two threadscan be interleaved: What is the balance of the account now? This is known as a race condition◆ Each thread is “racing” to put_balance() before the otherbalance = get_balance(account);balance = balance – amount;balance = get_balance(account);balance = balance – amount;put_balance(account, balance);put_balance(account, balance);Executionsequenceseen by CPUContext switchCSE 120 – Lecture 5: Synchronization 8Mutual ExclusionMutual Exclusion One way to ensure who wins the race is to only let onethread “compete”; this is called mutual exclusion Code that uses mutual exclusion to synchronize itsexecution 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 enterwithdraw (account, amount) { balance = get_balance(account); balance = balance – amount; put_balance(account, balance); return balance;}CriticalSectionCSE 120 – Lecture 5: Synchronization 9Critical Section RequirementsCritical Section Requirements1) Mutual exclusion◆ If one thread is in the critical section, then no other is2) Progress◆ If some thread T is not in the critical section, then T cannotprevent some other thread S from entering the critical section3) Bounded waiting (no starvation)◆ If some thread T is waiting on the critical section, then T willeventually enter the critical section4) No assumptions on performance◆ Requirements must be met with any number of CPUs witharbitrary relative speedsCSE 120 – Lecture 5: Synchronization 10LocksLocks One way to implement critical sections is to “lock thedoor” 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 11Using LocksUsing Locks◆ 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?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;balance = get_balance(account);balance = balance – amount;put_balance(account, balance);release(lock);acquire(lock);put_balance(account, balance);release(lock);CriticalSectionCSE 120 – Lecture 5: Synchronization 12 How do we implement locks? Here is one attempt: This is called a spinlock because a thread spinswaiting for the lock to be released Does this work?First Try: Spin LocksFirst Try: Spin Locksstruct 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 releasedCSE 120 – Lecture 5: Synchronization 13Spin LocksSpin Locks No. Two independent threads may both notice that
View Full Document
Unlocking...