Нужна помощь в понимании реализации мьютекса с 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. Рассмотрим следующий порядок исполнения

//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 должна быть атомная операция. Это не test с последующим set но уникальная небьющаяся операция, которая выполняет оба.

Обычно он реализуется процессорами с инструкцией, которая 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.