1CSE 120CSE 120Principles of Operating Principles of Operating SystemsSystemsFall 2004Fall 2004Lecture 6: SynchronizationLecture 6: SynchronizationGeoffrey M. VoelkerGeoffrey M. VoelkerOctober 7, 2004 CSE 120 – Lecture 6 – Synchronization 2SynchronizationSynchronizationz 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 Threads interleave executions arbitrarily and at different rates Scheduling is not under program controlz We control cooperation using synchronization Synchronization enables us to restrict the possible interleavings of thread executionsz Discuss in terms of threads, also applies to processes2October 7, 2004 CSE 120 – Lecture 6 – Synchronization 3Shared ResourcesShared Resourcesz We will initially focus on coordinating access to shared resourcesz 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 behaviorz 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.October 7, 2004 CSE 120 – Lecture 6 – Synchronization 4Classic ExampleClassic Examplez 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 Now suppose that you and your significant other share a bank account with a balance of $1000.z Then you each go to separate ATM machines and simultaneously withdraw $100 from the account.3October 7, 2004 CSE 120 – Lecture 6 – Synchronization 5Example ContinuedExample Continuedz We’ll represent the situation by creating a separate thread for each person to do the withdrawalsz These threads run on the same bank machine:z 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;}October 7, 2004 CSE 120 – Lecture 6 – Synchronization 6Interleaved SchedulesInterleaved Schedulesz The problem is that the execution of the two threads can be interleaved:z What is the balance of the account now?z 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 switch4October 7, 2004 CSE 120 – Lecture 6 – Synchronization 7Shared ResourcesShared Resourcesz 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)z We need mechanisms to control access to these shared resources in the face of concurrency So we can reason about how the program will operatez Our example was updating a shared bank accountz Also necessary for synchronizing access to any shared data structure Buffers, queues, lists, hash tables, etc.October 7, 2004 CSE 120 – Lecture 6 – Synchronization 8When Are Resources Shared?When Are Resources Shared?z 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 another thread’s stackz Global variables and static objects are shared Stored in the static data segment, accessible by any threadz Dynamic objects and other heap objects are shared Allocated from heap with malloc/free or new/delete5October 7, 2004 CSE 120 – Lecture 6 – Synchronization 9Mutual ExclusionMutual Exclusionz We want to use mutual exclusion to synchronize access to shared resourcesz 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 enterOctober 7, 2004 CSE 120 – Lecture 6 – Synchronization 10Critical Section RequirementsCritical Section RequirementsCritical sections have the following requirements:1) 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 cannot prevent 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) Performance The overhead of entering and exiting the critical section is small with respect to the work being done within it6October 7, 2004 CSE 120 – Lecture 6 – Synchronization 11Mechanisms For Building Mechanisms For Building Critical SectionsCritical Sectionsz Locks Very primitive, minimal semantics, used to build othersz Semaphores Basic, easy to get the hang of, but hard to program withz Monitors High-level, requires language support, operations implicitz 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 12LocksLocksz While one thread executes “withdraw”, we want some way to prevent other threads from executing in itz Locks are one way to do thisz A lock is an object in memory providing two operations acquire(): before entering the critical section release(): after leaving a critical sectionz 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?z Locks can spin (a
View Full Document
Unlocking...