DOC PREVIEW
UW CSE 303 - Concurrency Wrap-up

This preview shows page 1-2-3-4-5-6 out of 17 pages.

Save
View full document
View full document
Premium Document
Do you want full access? Go Premium and unlock all 17 pages.
Access to all documents
Download any document
Ad free experience
View full document
Premium Document
Do you want full access? Go Premium and unlock all 17 pages.
Access to all documents
Download any document
Ad free experience
View full document
Premium Document
Do you want full access? Go Premium and unlock all 17 pages.
Access to all documents
Download any document
Ad free experience
View full document
Premium Document
Do you want full access? Go Premium and unlock all 17 pages.
Access to all documents
Download any document
Ad free experience
View full document
Premium Document
Do you want full access? Go Premium and unlock all 17 pages.
Access to all documents
Download any document
Ad free experience
View full document
Premium Document
Do you want full access? Go Premium and unlock all 17 pages.
Access to all documents
Download any document
Ad free experience
Premium Document
Do you want full access? Go Premium and unlock all 17 pages.
Access to all documents
Download any document
Ad free experience

Unformatted text preview:

'&$%CSE 303:Concepts and Tools for Software DevelopmentDan GrossmanSpring 2007Lecture 23— Concurrency Wrap-up; Introduction to C++Dan Grossman CSE303 Spring 2007, Lecture 23 1'&$%Where are weDone:• Basics of shared-memory multithreading• Fork-join parallelism• Critical sections via atomic• Critical sections via careful use of locks (a.k.a. mutexes)Doing:• Pitfalls of using locks• Other concurrency gotchasThen:• Some basics of C++ (2 lectures, need 20 for the whole language)Dan Grossman CSE303 Spring 2007, Lecture 23 2'&$%Choosing how to lockNow we know what locks are (how to make them , whatacquiring/releasing means), but programming with them correctly andefficiently is difficult...• As before, if critical sections are too small we have races and toobig we m ay not communicate enough to get our work doneefficiently.• But now, if two “synchronized blocks” grab different locks, theycan be interleaved even if they access the same memory– A “data race”• Also, a lock-acquire blocks until a lock is available and only thecurrent-holder can release it.– Can have “deadlock” ...Dan Grossman CSE303 Spring 2007, Lecture 23 3'&$%DeadlockObject a;Object b;void m1() { void m2() {synchronized a { synchronized b {synchronized b { synchronized a {... ...}} }}}A cycle of threads waiting on locks means none will ever run again!Avoidance: All code acquires locks in the same order (very hard todo). Ad hoc: Don’t hold onto locks too long or while calling intounknown code.Dan Grossman CSE303 Spring 2007, Lecture 23 4'&$%Rules of ThumbAny one of the following are sufficient for avoiding races:• Keep data thread-local (an object is reachable, or at least onlyaccessed by, one thread).• Keep data read-only (do not assign to object fields after anobject’s constructor)• Use locks consistently (all accesses to an object are made whileholding a particular lock)• Use a partial-order to avoid deadlock (over-simple example: donot hold multiple locks at once?)These are tough invariants to get right, but that’s the price ofmultithreaded programming today.But... one way to do all the above is to have “one lock for all shareddata” and that is inefficient...Dan Grossman CSE303 Spring 2007, Lecture 23 5'&$%False sharing“False sharing” refers to not allowing separate things to happen inparallel.Example:synchronized x { synchronized x {++y; ++z;} }More realistic ex ample: one lock for all bank accounts rather than onefor each accountOn the other hand, acquiring/releasing locks is not so cheap, so“locking more with the same lock” can improve performance.This is the “locking granularity” question• Coarser vs. finer granularityDan Grossman CSE303 Spring 2007, Lecture 23 6'&$%Very challenging situationMy favorite example for ridiculing locks:If each bank account has its own lock, how do you write a “transfer”method such that no other thread can see the “wrong total balance”?// race (not data race) // potential deadlockvoid xfer(int a,Acct other){ void xfer(int a,Acct other){synchronized(this) { synchronized(this) {balance += a; synchronized(other) {other.balance -= a; balance += a;} other.balance -= a;} }}}The problem is there is no relative order among accounts, so “inversetransfers” could deadlockDan Grossman CSE303 Spring 2007, Lecture 23 7'&$%A final gotchaYou would naturally assume that all memory accesses happen in “someconsistent order” that is “dete rmined by the code”.Unfortunately, compilers and chips are often allowed to cheat(reorder)! The assertion in the right thread may fail!initially flag==falsedata = 42; while(!flag) {}flag = true; assert(data==42);To disallow reordering the programmer must:• Use lock acquires (no reordering across them), or• Declare flag to be volatile (for experts, not us)Dan Grossman CSE303 Spring 2007, Lecture 23 8'&$%ConclusionThreads make a lot of otherwise-correct approaches incorrect.• Writing “thread-safe” libraries can be excruciating.• Use an expert implementation, e.g., Java’s ConcurrentHashMap?But they are increasingly important for efficient use of computingresources (“the multicore revolution”).Locks and shared-m em ory are (just) one common approach.Learn about other useful synchronization mechanisms (e.g., conditionvariables) in CSE451.Dan Grossman CSE303 Spring 2007, Lecture 23 9'&$%C++C++ is an enormous language:• All of C• Classes and objects (kind of like Java, some crucial differences)• Many more little c onveniences (I/O, new/delete, functionoverloading, pass-by-reference, bigger standard library)• Namespaces (kind of like J ava packages)• Stuff we won’t do: const, different kinds of casts, exceptions,templates, multiple inheritance, ...We w ill focus on a couple themes rather than just a “big bag of newfeatures to memorize”...Dan Grossman CSE303 Spring 2007, Lecture 23 10'&$%Our focusOOP in a C-like language may help you understand C and Java better?• We c an put objects on the s tack or the heap; an object is not apointer to an object• Still have to manage memory m anually• Still lots of ways to HCBWKMSCOD (hopefully crash, but whoknows – might s ilently corrupt other data)• Still distinguish header files from implementation files• Allocation and initialization still separate concepts, but easier to“construct” and “destruct”• Programmer has more control on how method-calls work (differentdefaults from Java)Dan Grossman CSE303 Spring 2007, Lecture 23 11'&$%Hello World#include <iostream>int main() {// Use standard output stream cout// and operator << to send "Hello World"// and an end line to stdoutstd::cout << "Hello World" << std::endl;return 0;}Differences from C: “new-style” headers (no .h), namespace access(::), I/O via stream operators, ...Differences from Java: not everything is in a class, any code can go inany file, ...Dan Grossman CSE303 Spring 2007, Lecture 23 12'&$%CompilingNeed a different compiler than for C; use g++ on attu. Example:g++ -Wall -o hello hello.ccThe .cc extension is a convention (just like .c for C), but lessuniversal (also see .cpp, .cxx, .C).Uses the C preprocessor (no change there).Now: A few “niceties” before our real focus (classes and objects).Dan Grossman CSE303 Spring 2007, Lecture 23 13'&$%I/OOperator << takes a “ostream” and (various things) and outputs it;returns the stream, which is whystd::cout << 3 << "hi" << f(x) << ’\n’; works• Easier and safer than


View Full Document

UW CSE 303 - Concurrency Wrap-up

Documents in this Course
Profiling

Profiling

11 pages

Profiling

Profiling

22 pages

Profiling

Profiling

11 pages

Testing

Testing

12 pages

Load more
Download Concurrency Wrap-up
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 Concurrency Wrap-up 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 Concurrency Wrap-up 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?