相关数据结构
由上一章节可知，futex变量创建于用户空间，在进程或线程间共享，当进程或线程想要进入临界区时，通常会判断futex变量是否满足条件，若满足则成功进入临界区，否则则阻塞在该futex变量上；当进程或线程将要离开临界区时，则会唤醒阻塞在futex变量上的其他进程或线程。在内核中通过struct futex_q结构将一个futex变量与一个挂起的进程（线程）关联起来。
struct futex_q：
struct futex_q {
struct plist_node list; //链表节点，链入链表
struct task_struct *task; //挂起在该futex变量关联的进程（线程）
spinlock_t *lock_ptr; //自旋锁，控制链表访问
union futex_key key; //futex变量地址标识
//下面三个与优先级继承相关
struct futex_pi_state *pi_state;
struct rt_mutex_waiter *rt_waiter;
union futex_key *requeue_pi_key;
u32 bitset; //类似掩码匹配
};
union futex_key：futex变量地址标识
union futex_key {
struct {
unsigned long pgoff;
struct inode *inode;
int offset;
} shared; //不同进程间通过文件共享futex变量，表明该变量在文件中的位置
struct {
unsigned long address;
struct mm_struct *mm;
int offset;
} private; //同一进程的不同线程共享futex变量，表明该变量在进程地址空间中的位置
struct {
unsigned long word;
void *ptr;
int offset;
} both;
};
在内核中通过一个哈希表来维护所有挂起阻塞在futex变量上的进程（线程），不同的futex变量会根据其地址标识计算出一个hash key定位到一个哈希桶链上，因此挂起阻塞在同一个futex变量的所有进程（线程）会定位到同一个哈希桶链上。
struct futex_hash_bucket ：
struct futex_hash_bucket {
spinlock_t lock; //自旋锁，用于控制chain的访问，struct futex_q 中lock_ptr，就是引用其所在的哈希桶链的自旋锁，方便操作
struct plist_head chain; //优先级链，与传统等待队列不同，futex使用优先级链表来实现等待队列，是为了实现优先级继承，从而解决优先级翻转问题
};
futex哈希表：
static struct futex_hash_bucket futex_queues[1<<FUTEX_HASHBITS];
同一进程下不同线程阻塞在futex变量模型：
futex.jpg
内核fuetx初始化，初始化futex哈希表的每一个哈希桶链的头。
linux/kernel/futex.c
static int __init futex_init(void)
{
int i;
futex_detect_cmpxchg();
for (i = 0; i < ARRAY_SIZE(futex_queues); i++) {
plist_head_init(&futex_queues[i].chain);
spin_lock_init(&futex_queues[i].lock);
}
return 0;
}
