Concurency

4个重要概念:

• A critical section is a piece of code that accesses a shared resource, usually a variable or data structure.
• A race condition (or data race [NM92]) arises if multiple threads of execution enter the critical section at roughly the same time; both attempt to update the shared data structure, leading to a surprising (and perhaps undesirable) outcome.
• An indeterminate program consists of one or more race conditions; the output of the program varies from run to run, depending on which threads ran when. The outcome is thus not deterministic, something we usually expect from computer systems.
• To avoid these problems, threads should use some kind of mutual exclusion primitives; doing so guarantees that only a single thread ever enters a critical section, thus avoiding races, and resulting in deterministic program outputs.

How to build a Lock

attempt 1: 使用系统中断调用(对于single-processor system是可行的) 优点: 简单
缺点: 无法在multiprocessors使用, 某个线程可能会恶意占用critical section不退出, 滥用系统中断调用, 效率低……

void lock() {
  DisableInterrupts();
}

void unlock() {
  EnableInterrupts();
}

For these reasons, turning off interrupts is only used in limited contexts as a mutual-exclusion primitive.

attempt 2: 使用单标志位(错误见下图)
单标志不仅是错误的，同时性能上也很差，存在spin_wait。

typedef struct __lock_t { int flag; } lock_t;
void init(lock_t* mutex) {
  mutex->flag = 0;
}

void lock(lock_t* mutex) {
  while (mutex->flag == 1) ;
  mutex->flag = 1;
}

void unlock(lock_t* mutex) {
  mutex->flag = 0;
}

attempt 3: 利用硬件实现的Test-And-Set机制。

• 1、当critical section未被抢占时，当前线程call TestAndSet得到返回值为0，可以获得该锁。
• 2、当critical section已经被另一线程抢占时，当前线程想要call TestAndSet时会将*old_ptr = 1，但是由于已经被抢占了，返回的值为1，此时spin-wait(while循环调用，但是返回值一直为1)，直到另一线程unlock。

效果：correctness, fairness, performance?
正确的。 由于是抢占式的，可能存在线程一直spin-wait。 这依赖于single CPU/multiple CPUs，single cpu情况下，critical section被抢占情况下，任何其它线程都需要spin一次。

// c伪代码实现硬件过程
int TestAndSet(int *old_ptr, int new) {
  int old = *old_ptr;
  *old_ptr = new;
  return old;
}

typedef struct __lock_t { int flag; } lock_t;

void lock(lock_t* mutex) {
  while (TestAndSet(&lock_t->flag, 1) == 1) ;
}

attemp4：Compare-And-Swap c伪代码如下，机制与Test-And-Set相似。

int CompareAndSwap(int *ptr, int expected, int new) {
  int original = *ptr;
  if (original == expected)  *ptr = new;
  return original;
}

void lock(lock_t* mutex) {
  while (CompareAndSwap(&lock_t->flag, 0, 1) == 1) ;
}

How to avoid spining

假设thread0获取了锁，那么其余想要访问critical section的线程会一直spin直到消耗完time slice，效率低。

attempt 1： 利用系统调用yield释放CPU资源
考虑RR scheduler，尽管其余线程被调度时都会yield，每次切换线程的开销也非常大。

void lock()  {
  while (TestAndSet(&flag, 1) == 1)
    yield();
}

attempt 2：queue、TestAndSet、yield and wakeup