C语言中是否可实现真正具备严格FIFO特性的mutex？

针对严格FIFO互斥锁要求的结论 #

通用场景下，使用C语言无法实现题目定义的绝对严格FIFO互斥锁，核心原因如下：

• 不存在全局无分歧的请求时间判定基准：多核心系统各核心的本地时钟存在偏移，跨核发起的锁请求无法做到100%精准的先后时序判定；即便使用原子变量维护排队序号，线程从发起锁调用（即题目定义的“发起请求”时刻）到实际执行原子取号操作之间，存在不可消除的调度抢占窗口，可能出现更早调用锁函数的线程，反而比晚调用的线程拿到更靠后的排队序号，破坏“早请求必先获锁”的严格规则。
• 如果将“发起请求”的定义强行收窄为「线程成功完成排队号原子读取的时刻」，确实可以写出按号分配的FIFO锁，但这已经偏离了题目中“发起加锁请求”的语义——用户视角下调用锁接口的时刻才是请求发起点，中间的执行窗口是C语言运行在通用OS上无法完全消除的。

针对有界时序保证要求的结论 #

题目定义的固定n值有界公平性要求，使用C语言完全可以实现。
首先明确题目给出的判定规则：

设x_t为线程x发起加锁请求的时间。当且仅当y_t - x_t = n时，x比y年轻n；当且仅当y_t - x_t >= n时，x至少比y年轻n。要求存在固定值n，使得一个线程仅在所有至少比它年轻n的线程都被授予锁之后，才能获得锁。

这个要求本质就是并发领域的**有界等待（Bounded Waiting）**特性，已经有非常成熟的实现方案：

• 票号锁（Ticket Lock）：锁结构内维护两个原子变量，分别是next_ticket（下一个可领取的票号）和current_serving（当前可持有锁的票号）。线程加锁时先原子读取并递增next_ticket拿到自己的排队号，之后自旋等待current_serving等于自己的票号时拿锁成功；解锁时原子递增current_serving即可。这种实现下n的上限为系统同时竞争该锁的最大线程数，不会出现线程无限等待的情况，完全满足有界n的公平性要求。
• CLH锁、MCS锁等队列式自旋锁：通过原子操作将等待锁的线程组织成链式队列，锁释放时仅唤醒队列中下一个等待的线程，同样可以提供有界等待保证，且在多核高竞争场景下性能比票号锁更优。

如果运行在关闭抢占的实时系统、或绑定特定硬件时序保证的环境下，只要把n设置为大于最坏调度延迟、时钟误差的固定值，甚至可以将锁的公平性误差控制在极小范围内，接近严格FIFO的效果，但通用多任务OS下无法做到零误差的绝对FIFO。

内容的提问来源于stack exchange，提问作者Anonymous