Fusyn + RTNPTL：Linux 實時健壯的同步機制

本文主要敘述了目前 Linux 環境需要提供健壯和實時同步機制的必要性，并提出了實現的一個方案。這種同步機制對于 linux 進一步開拓服務器市場是非常重要的，尤其是電信市場。

1： 背景

自從多線程編程的概念出現在 Linux 中以來，Linux 多線程應用的發展總是與兩個問題脫不開干系：兼容性、效率。 早期的 Linuxthreads 在兼容性和效率上都存在了嚴重的問題，特別是兼容性上的問題，嚴重阻礙了Linux上的跨平臺應用（如Apache）采用多線程設計，從而使得 Linux 上的線程應用一直保持在比較低的水平。在 Linux 社區中，后來它被RedHat公司牽頭研發的NPTL（Native Posix Thread Library）而替代。在技術實現上，NPTL仍然采用1:1的線程模型，并配合glibc和Linux內核在信號處理、線程同步、存儲管理等多方面進行了優化。和LinuxThreads不同，NPTL沒有使用管理線程，核心線程的管理直接放在核內進行，這也帶了性能的優化。

雖然 NPTL 無論在兼容性還是在效率上面都大大優于Linuxthread。但是它并沒有完全的符合POSIX規范，并不能提供實時的同步機制，而實時的同步機制對于服務器尤其是電信級別服務器是至關重要的。因為如果沒有實時的同步機制，就非常容易引起優先級逆轉的問題。這對于需要優先級服務的電信服務器來說是致命的。因此提供實時性的同步機制是完善Linux的一個重要環節。

另外在電信服務器上，如果只提供實時的同步機制是遠遠不夠的。因為這些服務器需要提供99.9999% 的高可用性，這也就需要同步原語即使在異常情況下也能夠提供高可用性。比如下面有兩個線程A和B，它們分別用mutex來同步共享資源。

這里線程 B 先于線程 A 進入了臨界區，線程 A 看到已經有人搶占了共享資源，它只好進入睡眠狀態等待被 B 喚醒。然而不幸的是，線程 B 在領界區程序的執行過程中遇到了異常的情況，導致線程 B 的退出。這樣線程 A 就只能沉睡下去永遠無法被喚醒。如果線程 A 是一個有時間限制的客戶服務，那就肯定無法按時完成客戶的請求了。

鑒于以上的分析，我們認為為了讓 Linux 在服務器市場上大展手腳，它至少需要提供實時并且健壯的同步機制。Intel OTC 的 Robust Mutex 正是為了提供這種服務而設立的一個項目。它不僅為 Linux 同步機制提供了實時的特性避免了優先級逆轉， 也提供了健壯的同步原語，另外也引入了動態死鎖的檢測模塊。在技術上，整個項目包括兩個部分：Linux 內核補丁即 Fusyn 和 Glibc 即 RTNPTL。以下的章節將介紹它們的基本實現原理。

回頁首

2: Fusyn

Fusyn 是 Linux 內核的一個補丁，它在內核層次上解決了以上的一些問題，主要提供了以下幾個特性：

1. 用優先級繼承(PI)和優先級保護(PP)的策略來避免優先級逆轉

2. 基于優先級提供了實時的喚醒機制

3. 提供了健壯性的同步機制

4. 同時也提供了死鎖的檢測機制

為了能夠和 NPTL 更好的相處，Fusyn 采用了層次化的設計原則，在第一層上是Fuqueue。它和NPTL的等待隊列 wait queue 類似，不同的是它提供了基于優先級排列的等待隊列，這樣就為提供優先級的喚醒機制奠定了基礎?；?Fuqueue，Fusyn 建立了 Fulock 層次，這個層次記錄了每個同步鎖的擁有者的信息，為提供鎖的健壯性打下了基礎。

2.1 Fuqueue

Fuqueue 和 Linux 內核中的等待隊列類似，不同于普通的等待隊列是基于 FIFO 策略的，而 Fuqueue 如下圖所示，它是一個基于優先級排列的等待隊列。

因此當要喚醒下一個線程的時候，就會根據優先級進行喚醒，這樣就提供了一些實時的特性。為了提供這種功能，結構體的定義如下：

在定義中，成員 wlist 是一個按優先級排列的隊列，而 fuqueue_ops 為一些 fuqueue相關的函數指針，如改變優先級函數 fuqueue_waiter_chprio() 和取消等待函數fuqueue_waiter_cancel() 等。為了使用優先級等待隊列，可以先用 fuqueue_init() 函數進行初始化，當需要根據優先級插入到等待隊列睡眠的時候，可以利用 fuqueue_wait() 函數。如果想根據優先級喚醒下一個線程，fuqueue_wake 則可以實現這種功能。另外為了能夠提供 fulock 避免優先級逆轉的功能，也實現了fuqueue_waiter_chprio() 函數，這個函數能夠設置某一個線程的優先級并重新排序等待隊列。而 fuqueue_waiter_cancel 則用來取消等待喚醒等待線程。

為了讓 fuqueue 的功能也能夠直接在用戶空間得到應用，我們需要為它增加數據結構來記錄用戶空間同步鎖和 fuqueue 隊列的對應信息，在 Fusyn 的實現中，我們定義了以下結構體：

在這里 vlocator 被用來在內核空間代表用戶空間的同步鎖，也即每一把用戶空間的同步鎖都在內核中存在了一個 vlocator 結構體，這樣 ufuqueue 結構體就可以容易的把 fuqueue 等待隊列和用戶空間的同步鎖直接聯系起來。那么在 Linux 的同步原語的實現中，同步鎖在內核中怎么標志呢？在 NPTL 的實現當中，線程間的同步鎖用鎖的虛擬地址表示，而進程間的同步鎖則需要借助于文件系統來表示。因此結構體 vl_key 的定義如下：

另外在 vlocator 的實現中，它采用了類似 JAVA 的垃圾回收機制，當refcount為零時，就有垃圾回收器對其進行回收?；?ufuqueue 結構體，我們提供了 sys_ufuqueue_wait，sys_ufuqueue_wake 和sys_ufuqueue_ctl 三個系統調用，這樣 GLIBC 就可以直接利用以上的 3 個系統調用利用fuqueue 提供的優先級隊列的服務了。

2.2 Fulock

基于以上介紹的優先級隊列fuqueue，我們在fuqueue之上構造了提供健壯同步鎖的Fulock?；驹硎歉櫭恳粋€同步鎖的目前占有者信息。結構體定義如下：

基于fulock結構體，fusyn提供了兩個函數接口fulock_lock和fulock_unlock，當調用fulock_lock的時候，它通過olist_node成員把fulock結構體掛入到線程結構體task_struct的成員struct plist fulock_olist中去，同時在fulock中設置owner的信息。而釋放的時候則相反。這樣，當一個鎖的擁有者非法退出的時候，do_exit()函數則對每一個它擁有的鎖進行釋放并喚醒一個正在等待的線程，同時并設置鎖的狀態為FULOCK_FL_DEAD，使被喚醒的線程的返回值為-EOWERDEAD?；贓OWERDEAD標志，返回線程可以判斷鎖是否可以繼續運行并通過函數fulock_ctl來設置其狀態。

和Fuqueue一樣，為了擴展到用戶空間的同步鎖，fulock也引入了ufulock和一些系統調用：sys_ufulock_lock, sys_ufulock_unlock和sys_ufulock_ctl。

2.3 其他

除了以上的功能，fusyn還提供了PI和PP機制來避免優先級逆轉，當使用PI或PP機制的時候，每一個線程遍歷它所擁有鎖的隊列找出一個最高的優先級，然后暫時的設置自己為那個最高優先級。當它釋放每一個鎖的時候，再根據隊列重新調整自己的優先級。通過這種辦法就可以解決優先級逆轉的問題。

另外，Fusyn也引入了死鎖的檢測機制，每當調用fulock_lock的時候，它都會通過調用函數__fulock_check_deadlock進行死鎖的檢測。

回頁首

3: RTNPTL

為了在用戶級別提供這些特性，基于Fusyn，我們也需要在通常的NPTL線程庫中添加相應的接口，目前支持的同步機制包括：mutex，rwlock，conditional variable 和semaphore。

首先，RTNPTL定義了一些通用變量，如同步鎖類型以及避免優先級逆轉的協議,定義如下

Enum {
            PTHREAD_MUTEX_NOROBUST_NP,
            PTHREAD_MUTEX_ROBUST_NP,
            PTHREAD_MUTEX_ROBUST2_NP
            };
            Enum {
            PHTREAD_PRIO_NONE=1,
            PTHREAD_PRIO_INHERIT,
            PTHREAD_PRIO_PROTECT
            };
            

然后，為了更好的實現Glibc中的各種同步機制，我們實現了通用的底層接口，如__lll_rtmutex_timedlock，__lll_rtmutex_unlock，__lll_rtmutex_ctl 等。通過這些接口，上層的各種同步原語可以得到較為簡單的實現。和 NPTL 不同，這里的底層函數是調用了 Fusyn提供的系統調用接口，這里給出 __lll_rtmutex_timedlock 函數實現的一些基本步驟如下：

1：先對用戶空間 vfulock 進行判斷，看鎖是否已經被人占有。

2：如果鎖還沒有被人占有，就調用 Fusyn提供的系統調用sys_ufulock_lock，格式如下：result = INTERNAL_SYSCALL (ufulock_lock, err, 3, vfulock, flags, timeout);這個調用會讓線程進入到Linux內核進行等待，直到別的線程已經退出臨界區或者擁有鎖線程的退出的時候，函數返回相應的返回值。

3：由于ufulock_lock會返回不同意義的結果，如果是ENOTRECOVERABLE，那么就馬上返回結果ENOTRECOVERABLE給線程，否則就重新返回第1步進行搶鎖。

在mutex，rwlock，conditional variable 和semaphore的同步機制實現中，除了調用這些底層的同步機制，我們在它們各自的原語實現中實現了一些特有的特性。這樣在用戶空間的程序，就可以先對同步鎖設置屬性PTHREAD_MUTEX_ROBUST_NP使它成為健壯鎖，然后就可以直接調用Glibc提供的一些同步接口如pthread_mutex_lock等來提供實時健壯的特性了。

如果我們在用戶空間中，只想使用同步機制的實時特性而不需要健壯性，這就需要在GLIBC的實現中提供實時的一套實時接口。因此我們在GLIBC中也實現了底層的實時相關的通用函數供上層調用，它們為lll_fuqueue_timedwait，lll_fuqueue_wait, lll_fuqueue_wake和lll_fuqueue_ctl。lll_fuqueue_wait實現如下：

這里lll_fuqueue_wait是通過調用Fusyn提供的fuqueue系統調用從而提供優先級的特性的。類似的還包括lll_fuqueue_wake和lll_fuqueue_ctl。這樣當用戶空間程序只想用實時特性的時候，就只需要直接調用Posix提供的相應接口而不需要設置鎖的健壯性了。

回頁首

4: 實驗

基于以上特性的支持，在我們的實驗中調整了線程的代碼，我們很容易的避免了在圖一出現的問題。這里我們假設同步鎖已經被設置為健壯的屬性，調整線程A的代碼如下：

由于提供了健壯的同步機制，這樣當線程B還在臨界區的時候異常退出，同步機制就可以通知在等待的相應的線程，因此在線程A中，和以往不同，在調用Pthread_mutex_lock的同時，可以判定返回值是否是EOWNERDEAD,也即鎖的擁有者是否已經退出，如果是，就進一步檢查它自己是否可以恢復環境，并對此進行相應的處理。通過這樣的機制，我們可以輕松的避免線程A永遠等待的情況了。同理，在我們的實驗中我證明了實時特性的有效性。

除了提供健壯的同步機制以外，它還提供了避免優先級逆轉策略PI 和PP的兩種接口，用法非常簡單，只要在初始化同步機制的時候指定響應的策略PI或者PP就可以在我們的程序中避免優先級逆轉，下圖給出了PI策略中的線程優先級的變化，從圖中可以明顯看出同步鎖擁有者的優先級提升。

最后，我們也對 Fusyn 架構進行了性能上的測試，因為我們并不希望引入太多的額外開銷。我們通過了開源的網絡測試工具 volanomark 對其性能進行測試，測試環境為 2 P3 933, 512MB RAM 和 Fedora Core2， 得到結果如下：

從圖中可以看出，我們的機制并沒有引入了大的額外開銷，因此我們有理由相信它適合被更多的應用程序所應用。

回頁首

5: 結束語

本文首先介紹了目前 Linux 提供實時健壯同步機制的必要性，并給出了一種實現方案。同時對這個方案在內核和 glibc 庫的實現給予了介紹，最終給出了一些實驗結果。