Era of parallelism

  • end or Dennard scaling: no of transistors for fiexd area-core -> multi-core!

  • end of Moore's law: no. of transistorf for fixed area -> hardward accelerator! ->how to coordinate parallel resources to achieve higher preformance? : synchronize safely and efficiently

  • concurrency: synchronizing parallel resources

  • parallelism: multiple resources

  • concurrency: Shared mutable resources

    • 'trivial' concurrency: don't share resources at any moment!
    • 'scalable' concurrency: WHAT WE WANT! ->

Challenge in concurrency: nondeterminism(combinatorial!)

  • interleaving: 'x <- 1; x <- 2;' depends on the order of execution

  • optimization by hardware / compiler : instruction reordering

    • mem[x] = 1; a = mem[y] || // compiler could read mem[y] first! mem[y] = 1; b = mem[x] -> (first and second instruction has no relationship)

Approaches to taming nondeterminism

  • APIs (enclosing with safe API)

  • Implementation (lock, condvar, data structure, synchronization patterns)

  • Easy: Lock-based concurrency

    • thread, lock, condvar
    • simple, but low scalability

  • Difficult: Lock-free concurrenc

    • semantics & reasoning principles (characterizing nondeterminism)
    • synchronization patters)
    • APIs

Shared-memory concurrency

  • thread: agent of execution (read/write shared memory)
  • shared memory: shared storage of data

Lock-based shared-memory concurrency

  • location is accessed by a single agent!

  •   ┌───────────────────┐     ┌───────────────────┐
  │L.acquire()        │     │L.acquire()        │
  │{                  │     │{                  │
  │  r1 = mem[x];     │     │  r2 = mem[x];     │
  │  mem[x] = r1 + 1; │     │  mem[x] = r2 + 1; │
  │}                  │     │}                  │
  │L.release()        │     │L.release()        │
  └───────────────────┘     └───────────────────┘

  • apis

    • lock.acquire();
    • lock.try_acquire();
    • lock.release();

  • challenges:

    • relate lock and resource: users should access X only when L is held.
    • match acquire/relase: users should release only locks acquired.

  • c++/raii

    • LockGuard

      • lock.acquire() returns LockGuard
      • when LockGuard is destructed, the corresponding lock releases.

    • template<class T> class Lock<T> { RawLock lock; T data; }

    • WHAT's WRONG?

      • raw pointer access -> data_ptr should not outlive data_guard
auto data_guard = data.lock();
auto data_ptr = (int*)&data_guard;
//data_guard is dropped here
foo(*data_ptr) // UAF!

Rust concurrency libraries

  • std::sync::Arc;
  • std::thread;
  • std::time::Duration;