java - 这个算法是免费的吗？

Question

我偶然发现了 Bakerys 算法的修改版本(一个不完整的版本，当然有缺陷)

我在类里面被问到以下算法是否会出现饥饿问题:

while(true){
    number[me] = max(number[0],...,number[n]) + 1
    for (other from 0 to n) {
        while(number[other] != 0 && number[other] < number[me]) {
            // Wait
        }
    }

    /*CS*/
    number[me] = 0
}

我知道可能会出现死锁，但我想问的是这个算法是否没有饥饿？

我认为是的，因为我可以保证一旦 thread A 选择了一个数字，其他线程将始终拥有比 thread A 更大的数字，因此他最终将被允许进入CS

我的 friend 认为该算法并非没有饥饿，因为线程可能会卡在获取数字(计算 max)的过程中，并且可能会占用他的 CPU 时间。与此同时，其他线程将开始和结束，并可能再次开始(从 while 开始)，而据称 thread A 正处于饥饿状态。

我的问题可以简化为: 原始 Bakerys 算法中的 choosing 数组是否解决了饥饿问题？

Answer 1

饥饿自由可以定义为:任何试图进入临界区的进程，最终都会进入临界区。

计算 max 的行不是临界区的一部分，因此它最终会获得 cpu 时间来进行该分配。

当一个进程A收到它的id时，它将等待所有其他id低于它的进程有(较低的 id 意味着具有更高的优先级)。有时进程会离开临界区并获得一个新的 id。这个 id 将大于它拥有的那个，在那一刻 process A 将进入临界区。

最后，该算法是无饥饿的。