administrivia

Thursday: hw4 (C++ / boost strings) & threads

Friday: Eraser / 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, lec 18
  • getaddrinfo: hostname, port → sockaddr
  • getnameinfo: sockaddr → hostname, port
  • getsockname/getpeername: fd → sockaddr
• protocol dependent
  • example: server_accept_rw_close.cc, sendreceive.cc
  • deal with AF_INET[6], sockaddr_in[6]
  • not recommended, but up to you

self-exercise: echosrv2

extend echo server (echosrv.c)

print out client/server IP address & port: echosrv2.c

concurrency

virtualization: process & thread

separate vs shared address space

review CSE 351: processes

self-exercise: parallel sum

#include <iostream>
#include <vector>

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<long> v(10000, 1);
  std::cout << "result: " << psum(&v[0], 0, v.size()) << std::endl;
}

modify the program to use two threads: psum.cc

fork? pthread_create? std::thread?

see also: ex17, openmp

invariants

atomicity: all-or-nothing

ordering: A must happen before B

progress: no starvation/deadlock

example: global counter

#include <iostream>
#include <thread>
#include <vector>

static int counter;

void foo() { ++counter; }

int main() {
  std::vector<std::thread> 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

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

quiz: output?

#include <iostream>
#include <thread>
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();
}

programming interface

use pthreads/C/C++ primitives to avoid data races

locking: pthread_mutex_t, mutx_t, std::mutex

atomic: _Atomic, std::atomic

wait-and-signal: pthread_cond_t, cnd_t, std::condition_variable

demo: global counter

hardware support (x86)

LOCK prefix

compare-and-swap instruction: cmpxchg

/* PSEUDO CODE */
int cmpxchg(int *addr, int old, int new) {
  int was = *addr;
  if (was == old)
    *addr = new;
  return was;
}

example: transfer money

bank: multithreaded server, hashtable (name, balance)

transfer money from Alice to Bob

invariants?

strategies

coarse-grained locking: global interpreter lock

fine-grained locking

copy-on-write

read-write lock: <shared_mutex>, 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

concurrency bugs

hard to reproduce: non-deterministic

hard to understand: large number of interleavings

next lecture: tools & debugging techniques