Common Concurrency Problem

2018-07-16

Non-Deadlock Bugs

Atomicity-Violation Bugs

  • Definition of Atomicity Violation: The desired Serializability among multiple memory accesses is violated.
  • Solution to this bug: Just add Locks around the shared-variable references.
1
2
3
4
5
6
7
8
// Thread 1::
if (thd -> proc_info) {
  ...
  fputs(thd->proc_info, ...);
  ...
}
// Thread 2::
thd -> proc_info = NULL;
  • 在这个例子中两个线程同时访问数据thd的proc_info值，第一个线程检查该值是否为NULL，如果不是则输出proc_info的值，第二个线程将proc_info的值改变为NULL。
  • 当线程一完成检测并确定proc_info的值不为NULL时，线程二突然打断线程一并开始执行。

Order-Violation Bugs

  • Definition of Order Violation: The desired order between two memory access is flipped
  • So
1
2
3
4
5
6
7
8
9
10
11
12
13
// Thread 1::
void init() {
  ...
  mThread =  PR_CreateThread(mMain, ...);
  ...
}

// Thread 2::
void mMain(...) {
  ...
  mState = mThread -> State;
  ...
}

Deadlock Bugs

  • Four conditions need to hold for a deadlock to ocur:
    • Mutual Exclusion: Threads claim exclusive control of resources that they require
    • Hold-and-wait: Thread hold resources allocated to them while waiting for additional resources
    • No preemption: Resource cannot be forcibly removed from threads that are holding them
    • Circular wait: There exists a circular chain of threads such that each thread holds one more resources that are being requested by the next thread.

Prevent Circular Wait

  • To prevent Circular Wait, We must provide a Total Ordering on lock acquistion

Prevent Hold-and-Wait

  • The hold-and-wait Requirement for deadlock can be avoided by acquiring all locks at once, atomically.
    1
    2
    3
    4
    5
    lock(prevention);
    lock(L1);
    lock(L2);
    // ...
    unlock(prevention);

Prevent No Preemption

  • Multiple lock acquisstion often gets us into trouble because when waiting for one lock we are holding another.

  • The following method helps to avoid this situation. The trylock() routine will grab the lock if it is available, or return -1 indicating that the lock is held right now.

    1
    2
    3
    4
    5
    6
    top:
      lock(L1);
      if (trylock(L2) == -1) {
        unlock(L1);
        goto top;
      }

  • Livelock: It is possible that two threads could both be repeatedly attempting this sequence and repeatedly failing to acquire both locks. One could add a random delay before looping back and trying the entire thing over again.

Prevent Mutual Exclusion

  • Using more powerful hardware instructions, you can build data structures in a manner that does not require explicit locking.

  • Assume we have a compare-and-swap instruction, which as you may recall is an atomic instruction provided by the hardware that does the following:

    1
    2
    3
    4
    5
    6
    7
    int CompareAndSwap(int *address, int expected, int new) {
      if (*address == expected) {
        *address = nwe;
        return 1;
      }
      return 0;
    }

  • Imagine we now want to atomically increment a value by a certain amount

    1
    2
    3
    4
    5
    void AtomicIncrement(int *value, int amount) {
      do {
        int old = *value;
      } while (CompareAndSwap(value, old, old + amount) == 0);
    }

  • Instead of acquiring a lock, doing the update, and then releasing it, we have instead built an approach that repeatedly tries to update the value to the new amout and uses the compare-and-swap to do so.

Prevent Deadlock via Scheduling

  • This stratey requires some global knowledge of which locks various threads might grab during their execution, and subsequently schedules said threads in a way as to guarantee no deadlock can occur.
  • In a specific scenario, we have two processors and four threads:
    • Thread 1 grabs Lock 1 and Lock 2
    • Thread 2 grabs Lock 1 and Lock 2
    • Thread 3 just grabs Lock 2
    • Thread 4 grabs no Locks.
  • A smart scheduler could thus compute that as long as T1 and T2 are not run at the same time, no deadlock could ever arise.
    • CPU 1: T3, T4
    • CPU 2: T1, T2

      Prevent Deadlock through Detecting and Recovering

  • A deadlock detector runs periodically, building a resource graph and checking for cycyles. If a deadlock is detected, the system needs to be restarted.