Нужна помощь в понимании реализации мьютекса с test_and_set - PullRequest
Новая
       52

Нужна помощь в понимании реализации мьютекса с test_and_set

1 голос
/ 08 марта 2019

Книга «Принципы операционной системы» 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 или любой другой по сути не может войти в критическую секцию навсегда. Как это справится с этим делом тогда?

1 Ответ

2 голосов
/ 08 марта 2019

Вы правы в своем описании, и такая ситуация может привести к тупику.
Но чего вам не хватает, так это того, что 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.
...