1.futex引入的意義
傳統的SYSTEM V IPC機制需要系統調用進入內核態去操作某個內核對象，由內核來仲裁同步，事實上大部分情況下並沒有資源競爭即多個申請者不會同時去競爭同步對象，此種情況下仍然進入內核態會顯得很浪費，系統開銷增加進而造成性能拆扣。
Futex(Fast Userspace Mutex)快速用戶態互斥體，它是一種由用戶態和內核態共同完成的同步機制。創建時是在用戶空間通過mmap申請一片共享內存以便多進程間共同訪問此futex，用戶程序首先訪問用戶態的futex，只在判斷出存在沖突（如一個進程已經擁有此futex，另一個進程申請訪問，此時便存在一個沖突）時才進入內核態進行仲裁同步。
用戶空間的訪問和沖突判斷由glibc庫完成，沖突仲裁由內核的futex模塊完成。
內核仲裁：將用戶態的鎖置上等待標志表明有鎖的等待者存在，並調用schedule()將鎖申請者掛起；當鎖的擁有者釋放鎖(由glibc庫完成)時，檢查發現該鎖有等待者就進入內核將等待者喚醒。
Glibc庫中實現有pthread_mutex_lock()/pthread_mutex_unlock()等用戶態鎖接口，以提供快速的futex機制。
2.優先級繼承功能的futex性能比普通的futex差
pthread_mutex_lock()/pthread_mutex_unlock()配有優先級繼承（Priority Inherent簡稱pi）後的有時性能會嚴重影響了業務的正常運行。
不帶優先級繼承功能的鎖，會調用內核流程futex_wait()/futex_wake()，帶有優先級繼承功能的鎖會調用內核流程futex_lock_pi()/futex_unlock_pi()；pi鎖導致業務性能下降是實現機制以及業務模型導致。
3流程分析
3.1 glibc流程
3.1.1不帶優先級繼承(非pi)
pthread_mutex_lock
嘗試獲取鎖，如果失敗則進入內核阻塞
重復上述過程直到成功，並置持有鎖標志
pthread_mutex_unlock
如果有等待者，則進入內核態喚醒
3.1.2帶優先級繼承(pi)
pthread_mutex_lock
嘗試獲取鎖，如果失敗則進入內核阻塞
從內核返回後（通常表明加鎖成功），置持有鎖標志
pthread_mutex_unlock
如果有等待者，則進入內核態喚醒
3.1.3流程對比
在加鎖階段，非pi鎖可能會在glibc庫中多次競爭並多次進入內核態阻塞直到獲取鎖；而pi鎖最多只會進入內核態一次。從此角度可以看出，非pi鎖存在競爭的不公平性。
3.2內核流程
3.2.1不帶優先級繼承(非pi)
futex_wait
取__lock的值，與傳進來的val參數比較，如果不等，則直接返回；
將自己加入到等待隊列中，然後調用schedule將自己調度出去。
futex_wake
遍歷hash鏈表，找到對應的futex，調用wake_futex喚醒對應阻塞的線程。因為系統調用傳進來的nr_wake參數為1，實際上只喚醒1個線程就退出，優先喚醒優先級高的。
3.2.2帶優先級繼承(pi)
futex_lock_pi
使用queue_lock獲取spin_lock鎖，保證後面對信號量相關的操作都是安全的。
再次使用cmpxchg_futex_value_locked原子指令試圖將__lock字段改為tid，如果能修改成功，表明鎖擁有者釋放了該鎖。加鎖成功直接返回。
將__lock字段的bit 31置1，表明現在開始有線程將阻塞到該鎖上。
從內核維護的相關鎖信息pi_state中，找到對應的內核實時信號量；將自己放到用戶態信號量等待隊列，並調用rt_mutex_timed_lock阻塞到內核的實時信號量上。
從rt_mutex_timed_lock返回時，可能失敗，也可能是真正獲取到了信號量；這期間可能會導致pi_state相關信息不一致，如果不一致，則修正。
必要時對鎖擁有者線程進行優先級的提升。
返回rt_mutex_timed_lock的返回結果。
futex_unlock_pi
如果__lock中的tid不是自己，返回錯誤。
使用cmpxchg_futex_value_locked原子操作，如果__lock等於當前的tid，則將其改為0，然後返回。
如果用戶態信號量的等待隊列中還有線程阻塞，則使用wake_futex_pi函數挑選優先級最高的線程為新的owner，修改__lock的tid屬性為新owner的tid，並喚醒。
如果等待隊列中沒有線程阻塞，則在unlock_futex_pi函數中將__lock值改為0。
3.2.3流程對比
整個加鎖/解鎖流程中，主要有三點區別：
1. pi鎖遠比非pi鎖復雜，並使用rt_mutex內核對象進行線程的管理和喚醒，因此pi鎖在內核中的執行時間比非pi鎖要長得多；
2. pi鎖直接參於鎖的管理，非pi鎖只是簡單的掛起和喚醒線程（在glibc中管理鎖，見3.1）；
3. pi鎖會改變鎖當前持有者的優先級（優先級繼承，以避免優先級反轉）。
4 內核pi futex結構展示
Futex通過內核對象rt_mutex實現，本文針對recursive pi類型的futex以及線程間共享鎖的情況，講解內核中的futex_lock_pi()流程，展示所涉及的幾個核心數據結構。
全局變量static struct futex_hash_bucket futex_queues[1<<FUTEX_HASHBITS];
futex_queues做為一個橋梁作用，glibc系統調用進入內核時，第一件事情就是通過它來找到內核的的rt_mutex對象；利用當前task_struct->mm->mmap_sem和用戶態lock字段的地址生成key，用此key哈希到此變量數組的某個成員，從而建立起二者的聯系。
數據結構查找關系：
futex_lock_pi():
1.uaddr(即用戶態lock字段的地址), mmap_sem->key；
2.棧上分配futex_q, 將futex_q掛入futex_queues[hash(key)]中；
3.futex_q->futex_pi_state->rt_mutex，查找或分配futex_pi_state進而獲得rt_mutex；
4.棧上分配rt_mutex_waiter，將rt_mutex_waiter掛入當前task和步驟3的rt_mutex中。
futex_unlock_pi():
1.key->futex_queues[hash(key)]->futex_q->futex_pi_state->rt_mutex->rt_mutex_waiter->task，從而找到等待喚醒的任務。
數據結構關系圖：
數據結構描述(同種顏色相互對應)：
struct task_struct {
spinlock_t pi_lock;
struct plist_head pi_waiters; /* 只鏈入某rtmutex中優先級最高的rt_mutex_waiter */
/* Deadlock detection and priority inheritance handling */
struct rt_mutex_waiter *pi_blocked_on;
struct list_head pi_state_list;
struct futex_pi_state *pi_state_cache;
}
static struct futex_hash_bucket futex_queues[1<<FUTEX_HASHBITS];
struct futex_hash_bucket {
spinlock_t lock;
struct plist_head chain;
};
struct futex_q {
struct plist_node list; /* 根據當前線程的nomal_prio值鏈入 futex_hash_bucket
的chain中：plist_add(&q->list, &hb->chain); */
wait_queue_head_t waiters;
spinlock_t *lock_ptr; /* 指向futex_hash_bucket中的lock */
union futex_key key; /* 選擇futex_hash_bucket */
/* For fd, sigio sent using these: */
int fd;
struct file *filp;
/* Optional priority inheritance state: */
struct futex_pi_state *pi_state; /*指向task_struct中第一次預先分配好的pi_state_cache */
struct task_struct *task;
struct rt_mutex_waiter waiter;
};
struct futex_pi_state {
struct list_head list; /* 鏈入task_struct中的pi_state_list */
struct rt_mutex pi_mutex;
struct task_struct *owner; /* 鎖的當前擁有者 */
atomic_t refcount;
union futex_key key; /* 拷貝futex_q中的 key */
};
struct rt_mutex {
spinlock_t wait_lock;
struct plist_head wait_list; /* 所有的該鎖的rt_mutex_waiter */
struct task_struct *owner;
}
struct rt_mutex_waiter {
struct plist_node list_entry; /* 鏈入rt_mutex中的wait_list */
struct plist_node pi_list_entry; /* 鏈入task_struct中的pi_waiters */
struct task_struct *task;
struct rt_mutex *lock;
}
struct rt_mutex鎖的owner的低2位作為如下標志使用：
#define RT_MUTEX_OWNER_PENDING 1UL /* 喚醒時會將實時鎖置上此標志，
用於try_to_steal_lock() */
#define RT_MUTEX_HAS_WAITERS 2UL /* 有線程等待實時鎖置上此標志 */
#define RT_MUTEX_OWNER_MASKALL 3UL
futex_lock_pi()流程:
棧上分配struct futex_q q;
分配當前線程的pi_state_cache內存；
根據glibc中的用戶態futex鎖uaddr的地址和task_struct->mm-> mmap_sem生成q. key;
根據key找到hash_bucket, 初始化q.lock_ptr，並上鎖；
如果鎖的擁有都為當前線程，釋放q.lock_ptr鎖後退出；
將uaddr置位FUTEX_WAITERS；
正在持有futex鎖uaddr的線程p，第一次會以uaddr&0x0fff_ffff為pid找到;
lookup_pi_state()：遍歷hash_bucket-> chain，根據q.key值找到相應的pi_state；如果找不到則返回之前分配好的當前線程的pi_state_cache，並初始化pi_state：拷貝q.key，owner指向線程p，初始化pi_mutex(初始化wait_lock，將owner指向線程p)，將list鏈入線程p的pi_state_list(注pi_state始終鏈入鎖的擁有者線程中);
__queue_me()：初始化q，將q.list鏈入hash_bucket->chain中，q.task指向當前線程，並釋放q.lock_ptr鎖；
如果是高優先級的線程則可以偷鎖，偷鎖成功後會調用fixup_pi_state_owner()對pi_state以及uaddr的值進行修正；
rt_mutex_timed_lock()->rt_mutex_slowlock()->task_blocks_on_rt_mutex(lock, &waiter, detect)：
其中waiter為棧上分配的rt_mutex_waiter結構；設定當前線程為TASK_INTERRUPTIBLE狀態；初始化waiter，task指向當前線程，lock指向當前rt_mutex鎖，並使用當前線程的prio初始化兩個plist_node結構；waiter->list_entry鏈入lock->wait_list, waiter->pi_list_entry鏈入owner ->pi_waiters（owner為擁有鎖的線程即p）；當前線程的pi_blocked_on指向waiter(用於檢測死鎖和PI處理，會在被喚醒時檢查並置NULL)，最後__rt_mutex_adjust_prio(owner)進行優先級繼承操作，如果存在鎖鏈(一個低優先級rtmutex1的擁有者會繼承高優先級的waiter的優先級, 謂之PI；如果此線程阻塞在另外的rtmutex2，這個優先級會傳播到rtmutex2的擁有者，依次類推傳播，默認允許傳播1024個；此種情形暫稱之為存在鎖鏈)，則調用rt_mutex_adjust_prio_chain()進行優先級的傳播；涉及到的鎖為：lock->wait_lock和task->pi_lock；
schedule()；/* unlock pi時會調用wakeup_next_waiter()喚醒此線程 */
正常流程調用try_to_steal_lock()成功返回：當成功後清除RT_MUTEX_OWNER_PENDING標志。
當rt_mutex_timed_lock()調用失敗時（如信號喚醒），如果實時鎖的擁有者恰好為當前線程則進行rt_mutex_trylock()獲取鎖；其它情況進行相應參數修正退出；
把q.list從hash_bucket中摘除，根據情況把q.pi_state從task_struct中摘除，把q.pi_state ->pi_mutex的owner置NULL（如果沒有等待者），清除pi_state資源等。
注：2.6.21內核存在許多pi futex的BUG。例如，在頻繁fork的時候沒有處理cmpxchg_futex_value_locked返回-EFAULT的情況，還是用高版本內核為好。
