2

Silberschatz、Galvin 和 Gagne 所著的《操作系统原理》一书对 test_and_set 的原子操作有以下实现

boolean test_and_set(boolean *target) {
    boolean rv = *target;
    *target = true;
    return rv;
}

他们声明了一个初始化为 0 的全局变量锁，并为每个进程使用了​​以下互斥锁实现

do {
    while(test_and_set(&lock))
        ; // do nothing
        // critical section
    lock = false;
        // remainder section
} while(true);

现在，让我们考虑一下进程 P0 正在执行临界区而进程 P1 卡在 while 循环中的情况。然后考虑以下执行顺序

//lock = true initially because P0 is in critical section
P1 boolean rv = *target; //rv = true, lock = true
//P0 now completed its critical section and is ready to leave the lock
P0 lock = false //rv = true, lock = false
P1 *target = true; //rv = true, lock = true
P1 return rv; // returns true

因此，进程 P0 或任何其他进程实际上不能永远进入临界区。那么这将如何处理这种情况呢？

4

1 回答 1

3

您的描述是对的，这种情况会导致僵局。
但是您缺少的是test_and_set必须是原子操作。这不是 atest后面跟着 aset而是执行两者的独特的牢不可破的操作。

它一般由处理器实现，指令 1/ 禁止乱序执行， 2/ 等到处理器的流水线和内存队列为空， 3/ 读取寄存器中的内存， 4/ 设置内存字。读/写内存不能被中断，不能发生线程交换，并且禁止其他处理器访问内存。

在 risc 处理器上，也有类似的机制。您首先执行一个特殊的加载来监视对内存的访问（通常称为load locked），然后是一个特殊的存储，如果对内存位置进行了任何访问，该存储将失败（store conditional）。

这样，可以确定只有一个线程可以访问内存，test_and_set并且您描述的情况不会发生。

//lock = true initially because P0 is in critical section
P1 boolean rv = *target; //rv = true, lock = true
//P0 now completed its critical section and is ready to leave the lock
// BUT P0 MUST WAIT THE COMPLETION OF THE TAS.
// NO THREAD SWAP CAN HAPPEN AND ACCESS TO *target IS LOCKED
// DELAYED UNTIL END OF TAS P0 lock = false //rv = true, lock = false
P1 *target = true; //rv = true, lock = true
P1 return rv; // returns true
//NOW WE CAN DO
P0 lock = false //rv = true, lock = false
// AND LOCK IS PROPERLY UNSET
// ON NEXT ITERATION OF THE SPINLOCK WHILE, P1 WILL GET IT.
于 2019-03-08T17:12:09.750 回答