前言

昨天講完了最基礎的 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