Unformatted text preview:

1CSE 120CSE 120Principles of Operating Principles of Operating SystemsSystemsSystemsSystemsWinter 2007Winter 2007Lecture 5: SynchronizationLecture 5: SynchronizationKeith Marzullo and Geoffrey M. VoelkerKeith Marzullo and Geoffrey M. VoelkerSynchronizationSynchronizationz Threads cooperate in multithreaded programsTo share resources access shared data structures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 controlJanuary 23, 2007 CSE 120 – Lecture 5 – Synchronization 2z We control cooperation using synchronization Synchronization enables us to restrict the possible interleavings of thread executionsz Discuss in terms of threads, also applies to processes2Shared ResourcesShared ResourcesWe initially focus on coordinating access to shared resourceszBasic problemzBasic 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 resourcesJanuary 23, 2007 CSE 120 – Lecture 5 – Synchronization 3» Locks, mutexes, semaphores, monitors, condition variables, etc. Patterns for coordinating accesses to shared resources» Bounded buffer, producer-consumer, etc.Classic ExampleClassic Examplez Suppose we have to implement a function to handle withdrawals from a bank account: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 shareJanuary 23, 2007 CSE 120 – Lecture 5 – Synchronization 4zNow 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.3Example ContinuedExample Continuedz We’ll represent the situation by creating a separate thread for each person to do the withdrawalsthread for each person to do the withdrawalsz These threads run on the same bank machine: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;January 23, 2007 CSE 120 – Lecture 5 – Synchronization 5z What’s the problem with this implementation? Think about potential schedules of these two threads} }Interleaved SchedulesInterleaved Schedulesz The problem is that the execution of the two threads can be interleaved:can be interleaved: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 switchJanuary 23, 2007 CSE 120 – Lecture 5 – Synchronization 6z What is the balance of the account now?z Is the bank happy with our implementation?put_balance(account, balance);4Shared ResourcesShared Resourcesz The problem is that two concurrent threads (or processes) accessed ashared resource(account)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 operatezOur example was updating a shared bank accountJanuary 23, 2007 CSE 120 – Lecture 5 – Synchronization 7zOur example was updating a shared bank accountz Also necessary for synchronizing access to any shared data structure Buffers, queues, lists, hash tables, etc.When Are Resources Shared?When Are Resources Shared?z Local variables are not shared (private)Refer to data on the stack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 threadzDynamic objects and other heap objects aresharedJanuary 23, 2007 CSE 120 – Lecture 5 – Synchronization 8zDynamic objects and other heap objects are shared Allocated from heap with malloc/free or new/delete5How Interleaved Can It Get?How Interleaved Can It Get?How contorted can the interleavings be?zWe'll assume that the only atomic operations are............... get_balance(account);balance = get_balance(account);balance = ...................................zWe ll assume that the only atomic operations are reads and writes of words Many architectures don't even give you that!z We'll assume that a contextswitch can occur at anytimez We'll assume that you candl th d lJanuary 23, 2007 CSE 120 – Lecture 5 – Synchronization 9put_balance(account, balance);put_balance(account, balance);balance = balance – amount;balance = balance – amount;delay a thread as long as youlike as long as it's not delayedforeverMutual ExclusionMutual Exclusionz We want to use mutual exclusion to synchronize access to shared resources This allows us to have larger atomic blocksz 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An example in real life: sharing your bathroom with someJanuary 23, 2007 CSE 120 – Lecture 5 – Synchronization 10An example in real life: sharing your bathroom with some housemates.z What requirements would you place on a critical section?6Critical Section RequirementsCritical Section RequirementsCritical sections have the following requirements:1) Mutual exclusion (mutex))() 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 section A thread in the critical section will eventually leave the critical section3) Bounded


View Full Document

UCSD CSE 120 - Synchronization

Documents in this Course
Threads

Threads

14 pages

Deadlocks

Deadlocks

19 pages

Processes

Processes

14 pages

Paging

Paging

13 pages

Processes

Processes

18 pages

Threads

Threads

29 pages

Security

Security

16 pages

Paging

Paging

13 pages

Processes

Processes

32 pages

Lecture 2

Lecture 2

13 pages

Paging

Paging

8 pages

Threads

Threads

14 pages

Paging

Paging

13 pages

Paging

Paging

26 pages

Paging

Paging

13 pages

Lecture

Lecture

13 pages

Processes

Processes

14 pages

Paging

Paging

13 pages

Security

Security

17 pages

Threads

Threads

15 pages

Processes

Processes

34 pages

Structure

Structure

10 pages

Lecture 3

Lecture 3

13 pages

Lecture 1

Lecture 1

28 pages

Threads

Threads

15 pages

Paging

Paging

30 pages

Load more
Download Synchronization
Our administrator received your request to download this document. We will send you the file to your email shortly.
Loading Unlocking...
Login

Join to view Synchronization and access 3M+ class-specific study document.

or
We will never post anything without your permission.
Don't have an account?
Sign Up

Join to view Synchronization 2 2 and access 3M+ class-specific study document.

or

By creating an account you agree to our Privacy Policy and Terms Of Use

Already a member?