在 Linux 多線程編程中，我們常常用 pthread_mutex_lock 來做線程間同步。當(dāng)鎖被占用時，當(dāng)前線程會進入等待隊列，直到鎖被釋放時才被喚醒。那么如果有多個線程同時在等待隊列中，喚醒順序是怎樣的呢？文檔中關(guān)于這點的解釋比較簡略：

If there are threads blocked on the mutex object referenced by mutex when pthread_mutex_unlock() is called, resulting in the mutex becoming available, the scheduling policy shall determine which thread shall acquire the mutex.

這里的 scheduling policy 是指操作系統(tǒng)的調(diào)度策略呢，還是指當(dāng)前 mutex lock 類型的調(diào)度策略，上下文并沒有提及。網(wǎng)上看到不少說法是不保證喚醒順序，但有同事說他之前看過，PTHREAD_MUTEX_TIMED_NP 類型的鎖是能保證先進先出順序的。

我們先來看下 PTHREAD_MUTEX_TIMED_NP 的語義，libc 文檔中解釋了 posix mutex 的幾種不同類型：

• PTHREAD_MUTEX_TIMED_NP 是默認(rèn)類型，能用于 pthread_mutex_timedlock 調(diào)用，可以重復(fù)拿鎖
• PTHREAD_MUTEX_ADAPTIVE_NP 會先嘗試做若干次 spin lock 再進入等待隊列，不能重復(fù)拿鎖
• PTHREAD_MUTEX_ERRORCHECK_NP 重復(fù)拿鎖會報錯
• PTHREAD_MUTEX_RECURSIVE_NP 可以重復(fù)拿鎖，拿鎖次數(shù)需要等于釋放次數(shù)

所以 PTHREAD_MUTEX_TIMED_NP 這里的“timed”是指可以用于有超時限制地拿鎖，而不是按照時間順序喚醒的意思。我們可以進一步從 glibc 代碼中確認(rèn)，對于默認(rèn)的 TIMED 類型，pthread_mutex_lock 直接調(diào)用底層鎖，而后者用 Linux kernel 的 futex 實現(xiàn)鎖的功能，并沒有額外的隊列排序功能。每次釋放鎖，都會調(diào)用 futex_wake syscall 嘗試喚醒一個線程。

而 Linux futex lock 的實現(xiàn)是以鎖的地址作為 key，把當(dāng)前線程插入到對應(yīng)的隊列中。隊列按照線程優(yōu)先級排序，相同優(yōu)先級的線程按照先進先出順序排序。所以雖然 futex 語義和文檔都明確提到不保證喚醒順序，但至少目前的實現(xiàn)中相同優(yōu)先級是 FIFO 順序。為了驗證這點，我修改了 p 哥之前的一段實驗代碼，加入優(yōu)先級設(shè)置，并同時測試 mutex 和 futex。結(jié)果與前文所述一致。（一開始設(shè)置優(yōu)先級總是不生效，折騰了很久之后才知道原來 pthread 默認(rèn)是繼承父線程的調(diào)度屬性，必須設(shè)置成 PTHREAD_EXPLICIT_SCHED 模式才能改變調(diào)度策略和優(yōu)先級。）

LWN 上有篇文章對 futex 作了簡要介紹，可以快速了解 futex 實現(xiàn)。里面也提到了 futex 的一系列優(yōu)化。比如最開始 futex 實現(xiàn)涉及到頁表操作，需要拿 mmap_sem 鎖；到 2008 年 9 月，futex 已經(jīng)徹底消除了對 mmap_sem 的依賴，這樣再也無需與 page fault 或 mmap 操作競爭搶鎖。