问售票锁是免费的吗？(根据某些假设)

EN

我正在讨论一个票证锁，它看起来可能如下(在伪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)。

我会犯错吗？我有点困惑。我一直认为锁定意味着不需要等待，因为以下语句：“不可能从一组原子寄存器构建队列、堆栈、优先级队列、set或list的无等待实现。”(推论5.4.1多处理器编程艺术，Herlihy和Shavit)

但是，如果在上述假设下，票证锁(以及其他任何公平锁定机制)都是有界的无等待状态，则它(可能)可以构造队列、堆栈等的有界无等待实现(这是我实际上面临的问题)。

回顾一下Herlihy和Shavit的第59页“多处理器编程艺术”中有界无等待的定义：

“方法是无等待的，如果它保证每个调用都在有限的步骤中完成它的执行。如果一个方法调用所能采取的步骤数有一个界，则它是有界的没有等待的。”