票证锁定是否有界免等待？ （在某些假设下）

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 是非抢占式的，因此没有等待锁的睡眠线程。