需要帮助理解 test_and_set 互斥锁的实现

Question

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循环中的情况。考虑下面的执行顺序 then

//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或任何其他进程实际上永远无法进入临界区。那么这个案例是怎么处理的呢？

Answer 1

你的描述是对的，这种情况会导致死锁。
但是您缺少的是 test_and_set 必须是 atomic 操作。这不是 test 后跟 set，而是执行两者的独特牢不可破的操作。

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

在 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.

需要帮助理解 test_and_set 互斥锁的实现

Need help understanding implementation of mutex with test_and_set

concurrency

operating-system

locking

test-and-set

mutual-exclusion