前言

昨天花了很大的篇幅在學習spinlock ，可惜最重要的一部分 queued spinlock，還沒有機會完全參透，希望之後有機會把他弄懂，再回頭把昨天的筆記補完!! 今天也是要來學期除了 spinlock 、 atomic 以外，其他的同步鎖。

semaphore

semaphore 是作業系統中最常用的同步鎖之一。 spinlock 允許行程持續等待獲取一個鎖，相對的 semaphore 則是讓行程進入睡眠狀態，簡單來說 semaphore就是計數器，利用 up 與 down 計算擁有鎖的行程有幾個。
semaphore中最常見的例子就是消費者與生產者問題，生產者生產商品，消費者購買商品，生產者生產商品的行為就像是 semaphore 增加，消費者購買商品就像是 semaphore減少。
以下是semaphore的資料結構定義：

// <include/linux/semaphore.h>
struct semaphore {
	raw_spinlock_t		lock;
	unsigned int		count;
	struct list_head	wait_list;
};

lock ：是spinlock變量，保護 count wait_list。
count : 表示可以進入C.S的個數。
wait_list：管理在該 semaphore 上睡眠的行程，沒有獲得鎖的行程會睡眠在這個list上。
下面列出三個最常見的 semaphore 操作函數

static inline void sema_init(struct semaphore *sem, int val)
extern void up(struct semaphore *sem);
extern void down(struct semaphore *sem);

semaphore的特點就是他可以同時允許任意數量的鎖持有者，只要在semaphore的初始化時，將count 宣告成需要的數字即可，semaphore用於一些情況複雜，加鎖時間比較長的應用場景，像是kernel 與 user space的複雜交互行為。

about extern

變數使用前要先宣告(declaration)，C 的 extern 關鍵字，用來表示此變數已經在別處定義(definition)，告知程式到別的地方找尋此變數的定義(可能在同一個檔案或其他檔案)。

mutex

在 Linux中，有種類似 semaphore的機制叫做 mutex， semaphore 在同步處理的環境中對多個處理器訪問某個分享資源進行保護的機制，mutex則適用於互斥操作。
但若是將 semaphore的 count 設定為1，並且利用 down() 與 up() 仍然可以完成類似互斥鎖的結果，這樣為什麼要但讀實現互斥機制呢？
因為互斥鎖的實現比較簡單與輕便，在鎖競爭激烈的測試場景中，互斥鎖比 semaphore的執行速度還要快，可擴展性更好，互斥鎖的數據結構也比semaphore還要小，所以才會單獨實現。
下面是 mutex 的數據結構定義

// <include/linux/mutex.h>
struct mutex {
	atomic_long_t		owner;
	spinlock_t		wait_lock;
#ifdef CONFIG_MUTEX_SPIN_ON_OWNER
	struct optimistic_spin_queue osq; /* Spinner MCS lock */
#endif
	struct list_head	wait_list;
};

count : 1代表沒有行程持有鎖，0代表有持有，負數代表有被持有且有行程在等待隊列中。
wait_lock ：保護 wait_list。
wait_list ：管理所有在mutex上的所有行程。
ower ：指向鎖擁有者的 task_struct。
osq ：用於實現MCS鎖的機制。

#define DEFINE_MUTEX(mutexname) \
	struct mutex mutexname = __MUTEX_INITIALIZER(mutexname)
    
extern void mutex_lock(struct mutex *lock);
extern void mutex_unlock(struct mutex *lock);

The Linux document 中列出了使用mutex需要注意的條件

The mutex subsystem checks and enforces the following rules:

• Only one task can hold the mutex at a time.
• Only the owner can unlock the mutex.
• Multiple unlocks are not permitted.
• Recursive locking/unlocking is not permitted.
• A mutex must only be initialized via the API (see below).
• A task may not exit with a mutex held.
• Memory areas where held locks reside must not be freed.
• Held mutexes must not be reinitialized.
• Mutexes may not be used in hardware or software interrupt contexts such as tasklets and timers.