Day22 跟着 spinlock 旋转吧

前言

昨天讲完了最基础的 atomic的资讯，了解了 atomic可以保护某个变数的资料正确性，当有多个行程或是执行序想要同时存取对某个变数，利用atomic可以顺利地达成目的，但是当有些操作是要对作业系统内部的资料结构进行操作时，只有使用atomic对某个资料进行保护是不够的，这个时候就需要其他的武器来应付这样的状况，像是今天要谈的spinlock。

spinlock(自旋锁)

spinlock是Linux里面最常见的锁机制，在同一个时刻，spinlock只能被一个行程持有，如果有另一个行程想要获取已经被持有的spinlock，那麽想获取的行程就会一直忙碌等待，直到所得持有者释放该锁。自旋锁有几个性质。

1. 想获取锁的行程会一直忙碌直到持有锁的行程释放锁
2. 应该只用在比较短的 C.S (critical section)，若是C.S较长，则浪费许多在等待的时间
3. 持有锁的行程不能进入睡眠
4. 在C.S区内必须要关闭中断

<include/linux/spinlock_types.h>

typedef struct raw_spinlock {
	arch_spinlock_t raw_lock;
} raw_spinlock_t;

typedef struct spinlock {
	union {
		struct raw_spinlock rlock;

#ifdef CONFIG_DEBUG_LOCK_ALLOC
# define LOCK_PADSIZE (offsetof(struct raw_spinlock, dep_map))
		struct {
			u8 __padding[LOCK_PADSIZE];
			struct lockdep_map dep_map;
		};
#endif
	};
} spinlock_t;

Linux 内，spinlock的修改大概可以分成三个阶段。

• spinlock
• Ticket spinlock
• Queued Spinlock

1. spinlock
   在Linux2.6.25之前，spinlock的资料结构就只是一个简单的unsigned 变数，但是在这样简洁的状态之下，会发生很多其他的问题，特别是当很多个CPU同时要取得同一个spinlock的时候，可能会导致严重的不公平及性能下降，刚释放锁的CPU很有可能马上再次获得该所的使用权;或是与资料同一个NUMA节点的CPU有可能抢先获得锁，而没有考虑已经在所外面等待很久的CPU。也因此Linux 2.6.25之後，出现了基於排队的FIFO自旋锁机制。

2. Ticket spinlock
   Ticket spinlock大概就像是抽号码牌排队，想获取锁的行程，会得到两个数字，一个是目前的号码，与自己的号码，当自己的号码是下一个号码的时候，才会换成该行程获取锁。以下是部份程序码

static inline void arch_spin_unlock(arch_spinlock_t *lock)
{
    lock->tickets.owner++;
}

static inline void arch_spin_lock(arch_spinlock_t *lock)
{
    [LL/SC]

    while (lockval.tickets.next != lockval.tickets.owner) {
        wfe();
        lockval.tickets.owner = READ_ONCE(lock->tickets.owner);
    }
}

由上面的程序码可以发现，如果有多个CPU同时想获取同一个锁时，有可能会造成CPU cacheline bouncing，也就是多个CPU上的快取同时失效的状态，这个问题出现在上述程序码12行，因为每次都要拿取 lock->tickets.owner的值，如果值没有改变，就只要拿取cache的资料就可以了，当一个行程完成工作， lock->tickets.owner的值改变的时候，所有争抢锁的CPU上的cache 会同时被invalidate，所有CPU要重新从记忆体上拿取最新的资料，这样是极度浪费效能的。

3. 基於MCS算法的 Quened spinlock
   在 ticket spinlock中，因为唯一一个能拿到锁的是下一个行程，但是因为 lock->tickets.owner的改变所有的cpu都要更新cacheline，造成极大的效能浪费，因此基於MCS的quened spinlock因应而生。
   这部分有些复杂，目前我还没有看懂，待以後整理
   MCS lock
   queued spinlock

Linux 核心设计: 多核处理器和 spinlock