lock

Posted on | Post modified | In | Visitors

What a lock do?

Lock is used to make sure code in critical section been executed atomically.

Atomic: An operation (or set of operations) is atomic, linearizable, indivisible or uninterruptible if it appears to the rest of the system to occur at once without being interrupted. Atomicity is a guarantee of isolation from interrupts, signals, concurrent processes and threads.

build a Lock

with the help of hardware and os, some primitive instructions can help to build a lock.

Evaluating a Lock

  1. provide mutual exclusion
  2. fairness, no starvation
  3. how is the performance

Spin lock with Test-and-set

We can test the old value while simultaneously setting the memory location to new value.
atomic test-and-set instruction(in C)

1
2
3
4
5
int TestAndSet(int *old_ptr, int new) {
  int old = *old_ptr; // fetch old value at old_ptr
  *old_ptr = new; // store ’new’ into old_ptr
  return old; // return the old value
}

spin lock:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
typedef struct __lock_t {
  int flag;
} lock_t;

void init(lock_t *lock) {
// 0 indicates that lock is available, 1 that it is held
  lock->flag = 0;
}

void lock(lock_t *lock) {
 while (TestAndSet(&lock->flag, 1) == 1)
 ; // spin-wait (do nothing)
}

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

初始化，没有锁。假如有一个 thread 调用 lock() 函数；那么因为返回值是0，不会进入 spin lock。但是这时候，lock->flag 被置为 new value 1；假如该 thread 并没有释放lock，那么 lock->flag 就一直为 1；当另一个 thread 调用 lock() 时候，test-and-set 返回 1，并继续设置为 1。进入 spin lock。

  1. 提供 mutual exclusion
  2. 不提供 fairness，可能出现 starvation
  3. performance：对于单核来说，很不好。假如有 N 个 thread 共用一个 lock，一旦一个 thread 锁住 lock，其他 thread 因为会一直 spin，所以会占用 (N-1) 个 time period 做无用的循环。

Spin lock with compare-and-swap

Spin lock with Load-Linked and Store-Conditional

Spin lock with Fetch-And-Add

0%