门票是否等待免票？ （在一定条件下）

Question

我讲的一票锁可能如下所示（伪-C语法）：

unsigned int ticket_counter = 0, lock_counter = 0; 

void lock() { 
    unsigned int my_ticket = fetch_and_increment(ticket_counter); 

    while (my_ticket != lock_counter) {} 
} 

void unlock() { 
    atomic_increment(lock_counter); 
} 

让我们假设这样的票锁定同步访问临界截面S是等待免费，即执行关键部分需要恰好c个周期/指令。假设系统中至多有p个线程，是否使用门票锁定等待S的同步？

在我看来，它是，因为门票是公平的，因此等待的上限是O（p * c）。

我犯了一个错误吗？我有点困惑。我一直认为锁定意味着不会因为以下语句而等待（有界）： “不可能从一组原子中构造一个等待自由实现的队列，堆栈，优先级队列，集合或列表寄存器。” （在多处理器编程艺术中的推论5.4.1，Herlihy和Shavit）

然而，如果门票锁（以及其他任何公平的锁定机制）在所提到的假设下等待自由，那么它（可能）的建筑界无等待队列，栈等实现（这是我实际上面临的问题。）

---

召回“多处理器编程的艺术”有界无等待的定义， Herlihy和Shavit撰写的第59页：

“一种方法是无等待的，如果它保证每个调用在有限的步骤中完成其执行。如果有一个方法调用可以采取的步骤数的限制，人们界无等待。”

Answer 1

好吧，我相信你是正确的，有一些注意事项。

也就是说，有界无等待属性只有在关键部分S是非抢占式时才会保留，我认为你只能保证内核空间代码（通过禁用关键部分中的中断）。否则，操作系统可能决定切换到另一个线程，而一个线程在关键部分，然后等待时间是无界的，不是？

此外，对于内核代码，我想p不是软件线程数，而是硬件线程数（或核心，对于CPU不支持每个CPU核心的几个线程）。因为一次最多可以运行p个软件线程，并且由于S是非抢占式的，所以没有等待锁的睡眠线程。