CSE 120 Principles of Operating Systems Spring 2009AdministriviaSynchronizationShared ResourcesClassic ExampleExample ContinuedInterleaved SchedulesShared ResourcesWhen Are Resources Shared?How Interleaved Can It Get?Mutual ExclusionCritical Section RequirementsAbout RequirementsMechanisms For Building Critical SectionsMutual Exclusion with Atomic Read/Writes: First TryMutex with Atomic R/W: Peterson's AlgorithmMutex with Atomic R/W: Peterson's AlgorithmLocksUsing LocksImplementing Locks (1)Implementing Locks (2)Implementing Locks (3)Atomic Instructions: Test-And-SetUsing Test-And-SetProblems with SpinlocksDisabling InterruptsOn Disabling InterruptsSummarize Where We AreHigher-Level SynchronizationImplementing Locks (4)Next time…TODOSemaphoresBlocking in SemaphoresUsing SemaphoresCSE 120Principles of Operating SystemsSpring 2009Lecture 5: SynchronizationGeoffrey M. VoelkerApril 14, 2009 CSE 120 – Lecture 5 – Synchronization 2Administrivia Homework #2 Due 4/23 The answers to almost all problems are short (but thoughtful) Travel: Stockholm BoundApril 14, 2009 CSE 120 – Lecture 5 – Synchronization 3Synchronization 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 We control cooperation using synchronization Synchronization enables us to restrict the possible interleavings of thread executions Discuss in terms of threads, also applies to processesApril 14, 2009 CSE 120 – Lecture 5 – Synchronization 4Shared ResourcesWe 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 5Classic 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 6Example 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: 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;}April 14, 2009 CSE 120 – Lecture 5 – Synchronization 7Interleaved Schedules The problem is that the execution of the two threads can be interleaved: What is the balance of the account now? Is the bank happy with our implementation?balance = get_balance(account);balance = balance – amount;balance = get_balance(account);balance = balance – amount;put_balance(account, balance);put_balance(account, balance);Execution sequence seen by CPUContext switchApril 14, 2009 CSE 120 – Lecture 5 – Synchronization 8Shared Resources The problem is that two concurrent threads (or processes) accessed a shared resource (account) without any synchronization Known as a race condition (memorize this buzzword) We need mechanisms to control access to these shared resources in the face of concurrency 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 9When Are ResourcesShared? Local variables are not shared (private) Refer to data on the stack 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 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/free or new/deleteStack (T1)CodeStatic DataHeapStack (T2)Stack (T3)Thread 3Thread 2PC (T1)PC (T3)PC (T2)Thread 1April 14, 2009 CSE 120 – Lecture 5 – Synchronization 10How Interleaved Can It Get?............... get_balance(account);put_balance(account, balance);put_balance(account, balance);balance = balance – amount;balance = balance – amount;balance = get_balance(account);balance = ...................................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 contextswitch can occur at anytime We'll assume that you candelay a thread as long as youlike as long as it's not delayedforeverApril 14, 2009 CSE 120 – Lecture 5 – Synchronization 11Mutual Exclusion We want to use mutual exclusion to synchronize access to shared resources This allows us to have larger atomic blocks 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 Example: sharing your bathroom with housemates What requirements would you place on a critical section?April 14, 2009 CSE 120 – Lecture 5 – Synchronization 12Critical Section RequirementsCritical sections have the following requirements:1) Mutual exclusion
View Full Document
Unlocking...