Linux的futex是一种快速用户空间互斥体（Fast Userspace mutexes）机制，用于实现进程间和线程间的同步操作。它在Linux内核中存在已经很长时间了，从Linux 2.5.7版本开始引入。

Futex的优势

相比于传统的同步机制，futex具有以下优势：

1. 快速：futex利用用户态和内核态混合的方式实现同步，避免了频繁的用户态和内核态切换，因此具有较低的开销和较高的性能。
2. 灵活：futex支持进程内的线程同步和进程间的同步锁操作，可以满足不同场景下的同步需求。
3. 轻量级：futex的实现相对简单，占用的系统资源较少。

Futex的功能

futex提供了以下几个基本功能：

1. futex_wait：当一个任务需要陷入等待状态时，可以调用futex_wait函数。该函数会检查指定的futex变量的值是否满足特定条件，如果不满足，则任务会被阻塞在该futex变量上，直到满足条件才会被唤醒。
2. futex_wake：当需要唤醒其他任务时，可以调用futex_wake函数。该函数会唤醒指定数量的在某个futex变量上等待的任务。

数据结构

在内核中，futex变量通过struct futex_q结构与挂起的进程（线程）关联起来。该结构包含了链表节点、挂起的进程（线程）、自旋锁、futex变量地址标识等成员。

c
/*
 * Hash buckets are shared by all the futex_keys that hash to the same
 * location. Each key may have multiple futex_q structures, one for each task
 * waiting on a futex.
 */
struct futex_hash_bucket {
    atomic_t waiters;                // 等待者计数，原子变量
    spinlock_t lock;                 // 散列桶的锁
    struct plist_head chain;         // 等待在同一位置的 futex_keys 的链表
} ____cacheline_aligned_in_smp;

/*
 * Priority Inheritance state:
 */
struct futex_pi_state {
    /*
     * list of 'owned' pi_state instances - these have to be
     * cleaned up in do_exit() if the task exits prematurely:
     */
    struct list_head list;            // 拥有的 pi_state 实例的链表，用于在任务提前退出时清理

    /*
     * The PI object:
     */
    struct rt_mutex_base pi_mutex;    // 优先级继承对象的基本互斥体

    struct task_struct *owner;        // 拥有此 pi_state 的任务指针
    refcount_t refcount;              // 引用计数

    union futex_key key;              // futex 的键值
} __randomize_layout;


/**
 * struct futex_q - The hashed futex queue entry, one per waiting task
 * @list:           priority-sorted list of tasks waiting on this futex
 * @task:           the task waiting on the futex
 * @lock_ptr:       the hash bucket lock
 * @key:            the key the futex is hashed on
 * @pi_state:       optional priority inheritance state
 * @rt_waiter:      rt_waiter storage for use with requeue_pi
 * @requeue_pi_key: the requeue_pi target futex key
 * @bitset:         bitset for the optional bitmasked wakeup
 * @requeue_state:  State field for futex_requeue_pi()
 * @requeue_wait:   RCU wait for futex_requeue_pi() (RT only)
 *
 * We use this hashed waitqueue, instead of a normal wait_queue_entry_t,
 * so we can wake only the relevant ones (hashed queues may be shared).
 *
 * A futex_q has a woken state, just like tasks have TASK_RUNNING.
 * It is considered woken when plist_node_empty(&q->list) || q->lock_ptr == 0.
 * The order of wakeup is always to make the first condition true, then
 * the second.
 *
 * PI futexes are typically woken before they are removed from the hash list via
 * the rt_mutex code. See futex_unqueue_pi().
 */
struct futex_q {
    struct plist_node list;               // 一个按优先级排序的等待在此 futex 上的任务列表
    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;    // 与 requeue_pi 一起使用的 rt_waiter 存储
    union futex_key *requeue_pi_key;      // requeue_pi 目标 futex 的键值
    u32 bitset;                           // 用于可选的位掩码唤醒的位集
    atomic_t requeue_state;               // 用于 futex_requeue_pi() 的状态字段
#ifdef CONFIG_PREEMPT_RT
    struct rcuwait requeue_wait;          // 用于 futex_requeue_pi() 的 RCU 等待（仅适用于实时内核）
#endif
} __randomize_layout;

此外，全局哈希表用于维护所有挂起阻塞在futex变量上的进程（线程）。不同的futex变量会根据其地址标识计算出一个哈希索引，并定位到对应的bucket上。每个bucket包含了自旋等待哈希桶的等待数目、自旋锁和优先级链表等成员。

源码分析

futex的初始化工作在内核启动时完成。初始化包括申请固定数量的bucket用于全局哈希表管理，并初始化每个bucket的链表的自旋锁。

Learn more:

1. linux--futex原理分析
2. linux futex浅析-阿里云开发者社区
3. futex(2) - Linux manual page