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;