% lec 21: synchronization # administrivia Thursday: hw4 ([C++](http://www.cplusplus.com/reference/string/string/) / [boost](http://www.boost.org/doc/libs/1_57_0/doc/html/string_algo.html) strings) & threads Friday: data race detection next Monday: undefined behavior next Friday: wrapup # today's plan review sockets & concurrency synchronization: bugs & programming interface # socket programming revisited - protocol independent: no need to handle IPv4 vs IPv6 - examples: [lec 17](l17-networks.html#/programming-interface), [lec 18](l18-sockets.html#/echo-server) - `getaddrinfo`: hostname, port → sockaddr - `getnameinfo`: sockaddr → hostname, port - `getsockname`/`getpeername`: fd → sockaddr - protocol dependent - example: [server_accept_rw_close.cc](https://courses.cs.washington.edu/courses/cse333/14au/lectures/lec18_code/server_accept_rw_close.cc), [sendreceive.cc](../sec/sec8_code/sendreceive.cc) - deal with `AF_INET[6]`, `sockaddr_in[6]` - _not_ recommended, but up to you # self-exercise: echosrv2 extend [echo server (echosrv.c)](l18-sockets.html#/echo-server) print out client/server IP address & port: [echosrv2.c](l21/echosrv2.c.html) # concurrency virtualization: process & thread separate vs shared address space review [CSE 351: processes](https://courses.cs.washington.edu/courses/cse351/15wi/lectures/09-processes_wi15.pptx) # self-exercise: parallel sum ```c++ #include #include long psum(long *v, size_t offset, size_t n) { long result = 0; for (size_t i = 0; i < n; ++i) result += v[offset + i]; return result; } int main() { std::vector v(10000, 1); std::cout << "result: " << psum(&v[0], 0, v.size()) << std::endl; } ``` modify the program to use two threads: [psum.cc](l21/psum.cc.html) `fork`? `pthread_create`? `std::thread`? see also: ex17, [openmp](https://computing.llnl.gov/tutorials/openMP/samples/C/omp_reduction.c) # invariants atomicity: all-or-nothing ordering: A must happen before B progress: no starvation/deadlock # example: global counter ```c++ #include #include #include static int counter; void foo() { ++counter; } int main() { std::vector threads; for (int i = 0; i < 1000; ++i) threads.push_back(std::thread(foo)); for (auto &thr : threads) thr.join(); std::cout << counter << std::endl; } ``` what's the result? . . . data race - undefined! # data race concurrent access to shared data; at least one write undefined behavior - _illegal_ compiler/CPU may reorder & change your code example: two threads incrementing a shared `counter` . . . see also: [Therac-25](http://en.wikipedia.org/wiki/Therac-25), [Northeast blackout of 2003](http://www.huffingtonpost.com/2013/08/14/2003-northeast-blackout_n_3751171.html) # quiz: output? ```c++ #include #include static int flag = 0; void signal_proc() { std::cout << "before signal" << std::endl; flag = 1; } void wait_proc() { while (flag == 0) {} std::cout << "after wait" << std::endl; } int main() { std::thread t1(signal_proc), t2(wait_proc); t1.join(); t2.join(); } ``` . . . undefined behavior: `g++-4.9 -O2`, infinite loop # programming interface use pthreads/C/C++ primitives to avoid data races locking: [pthread_mutex_t](https://computing.llnl.gov/tutorials/pthreads/#Mutexes), [mutx_t](http://en.cppreference.com/w/c/thread), [std::mutex](http://en.cppreference.com/w/cpp/thread/mutex) atomic: [_Atomic](http://en.cppreference.com/w/c/atomic), [std::atomic](http://en.cppreference.com/w/cpp/atomic) wait-and-signal: [pthread_cond_t](https://computing.llnl.gov/tutorials/pthreads/#ConditionVariables), [cnd_t](http://en.cppreference.com/w/c/thread), [std::condition_variable](http://en.cppreference.com/w/cpp/thread/condition_variable) demo: global counter # hardware support (x86) [LOCK prefix](http://en.wikipedia.org/wiki/Fetch-and-add#x86_implementation) [compare-and-swap](http://en.wikipedia.org/wiki/Compare-and-swap) instruction: `cmpxchg` ```c /* PSEUDO CODE */ int cmpxchg(int *addr, int old, int new) { int was = *addr; if (was == old) *addr = new; return was; } ``` # example: transfer money name balance ------ -------- Alice 230 Bob 120 ... ... bank: multithreaded server, hashtable (name, balance) transfer money from Alice to Bob invariants? # strategies coarse-grained locking: [global interpreter lock](http://en.wikipedia.org/wiki/Global_Interpreter_Lock) fine-grained locking [copy-on-write](http://en.wikipedia.org/wiki/Persistent_data_structure) [read-write lock](http://en.wikipedia.org/wiki/Readers%E2%80%93writer_lock): [``](http://en.cppreference.com/w/cpp/header/shared_mutex), [read-copy-update](http://en.wikipedia.org/wiki/Read-copy-update), ... ... trade-off: performance vs correctness # deadlock lock 1 - Alice, lock 2 - Bob thread 1: grabbed lock 1, acquiring lock 2 thread 2: grabbed lock 2, acquiring lock 1 prevention: order locks example: [`std::lock`](http://en.cppreference.com/w/cpp/thread/lock) # concurrency bugs hard to reproduce: non-deterministic hard to understand: large number of interleavings next lecture: tools & debugging techniques