Взаимное исключение с использованием инструкции TestAndSet ()

Question

Книга «Принципы операционной системы» Silberschatz, Galvin и Gagne содержит следующее определение инструкции TestAndSet () в главе о синхронизации:

boolean TestAndSet(boolean *target) {
    boolean rv = *target;
    *target = TRUE;
    return rv;
}

Реализация взаимного исключения с использованием вышеуказанной инструкции также предоставляется следующим образом:

do {
    while(TestAndSetLock(&lock))
        ; // do nothing
        // critical section
    lock = FALSE;
        // remainder section
} while(TRUE);

Теперь, как достигается взаимное исключение, если нет условия для установки target в TRUE?

Рассмотрим следующую ситуацию: процесс P0 устанавливает общую переменную lock в TRUE и входит в ее критическую секцию. Другой процесс P1 вызывает TestAndSet () в приведенном выше цикле while, он возвращает TRUE (поскольку P0 имеет блокировку), в то же время безоговорочно устанавливая lock в FALSE. Во второй раз, когда TestAndSet () вызывается в цикле while, он возвращает FALSE, и P1 входит в критическую секцию, даже если P0 находится в критической секции. Взаимное исключение затем нарушается.

Я немного искал и наткнулся на статью Митхуна Ачарьи и Роберта Фундерлика (из отделения CS Университета штата Северная Каролина), в которой содержится следующее альтернативное определение TestAndSet ():

   boolean Test-and-Set(boolean target)
    begin
        if(target == false):
            target = true;
        return target;
    end

Это имеет для меня гораздо больше смысла, я включил его для сравнения, а также потому, что в статье в качестве одной из ссылок упоминается книга Зильбершаца.

Я просто не понимаю, как определение, которое я нашел в моем учебнике (то, которое я предоставил первым), может использоваться для достижения взаимного исключения, кто-нибудь может помочь?

Answer 1

Вот способ думать об атомарном TestAndSet интуитивно.

Поток использует его перед входом в критическую область. Всего два случая:

1. Блокировка удерживается (* цель - ИСТИНА): вернуть ИСТИНА, а * цель - ИСТИНА
2. Блокировка НЕ ​​удерживается: верните ЛОЖЬ, и * target установлен в TRUE

Так что либо другой поток находится в критической области, поэтому * target (TRUE) отражает, какое значение должно быть; или «Я» сейчас вхожу в эту критическую область, поэтому установите * target на TRUE.

Answer 2

Показанная реализация может быть записана более четко так:

while(TestAndSet(&lock))
{
   // spin in this loop until TestAndSet returns false
}
do_critical_section_stuff();
lock = FALSE;
// We've now left the critical section

Я думаю, что ОП неправильно истолковал его как:

while(TestAndSet(&lock))
{
   lock = FALSE;
}
do_critical_section_stuff();

, который не работает должным образом по понятным причинам.

Answer 3

Ах, у меня тоже был этот вопрос. Позвольте мне поделиться своим пониманием.

Изначально * цель будет ЛОЖЬ. (Это дано). Это правда, что P нужно пройти while(TestAndSetLock(&lock)) ; // do nothing чтобы получить блокировку и войдите в критическую секцию . (получение блокировки - просто гипотетическая вещь, если она может пройти цикл while, значит, она имеет блокировку)

кто-то имеет блокировку, значит цель равна ИСТИНА , блокировка может быть взята на цель на FALSE . так что в начале это так,

P1 (самому первому, кто вызовет функцию, повезет), он видит, что целью является FALSE, и устанавливает для него значение true и RETURN FALSE, что приводит к тому, чтобы избежать ожидания цикла while.

Теперь цель TRUE. Другой факт - TestAndSet (блокировка boolean_ref) вернет вызванное значение , И TestAndSet (блокировка boolean_ref) будет ВСЕГДА устанавливать цель на ИСТИНА поэтому кто-то должен установить цель на ЛОЖЬ в другом месте (, чтобы тот, у кого есть блокировка, мог установить его на ЛОЖЬ )

Придут другие P и увидят, что цель - ИСТИНА, и при вызове TestAndSet(boolean_ref lock) она всегда будет возвращать ИСТИНА, пока P1 не установит цель на false.

И я нашел это хорошее графическое объяснение от Этот сайт, вы можете скачать его здесь

Answer 4

Функция TestAndSet, которую вы изначально цитируете, выполняется только тогда, когда target имеет значение false. То есть поток блокируется, пока цель не станет ложной. У меня нет этого учебника, но я уверен, что он упоминается где-то в тексте.

Обратите внимание, что TestAndSet - это «атомарная» функция, которая должна быть реализована на самых низких уровнях ОС (или даже с помощью набора команд ЦП). Если это реализовано в пользовательском приложении, между тестом и набором может произойти переключение контекста, что приведет к повреждению.

Уточнение: я уверен только в том, что функция выполняется, когда target имеет значение false, потому что где-то это должна быть операция сравнения, которая блокирует. Существует два типа TestAndSet - один, который возвращается только в том случае, если для цели установлено значение «Истина» (блокировка), и другой, который может возвращать значение «Ложь», т. Е. Немедленно возвращаться (тот активирует опрос другого потока). Я предполагаю, что тот, который вы цитируете, блокирует, потому что он, кажется, возвращается сразу после начала выполнения, что означает, что оператор «IF» выполняется механизмом более низкого уровня, например, ядро процессора или ОС.

Answer 5

Чтобы использовать метод testAndset, мы начнем с переменной Lock, для которой установлено значение false:

HdwareData lock = new HdwareData(false);

Answer 6

Рассмотрите следующую выделенную часть в вашем вопросе:

Рассмотрим следующую ситуацию: процесс P0 устанавливает блокировку общей переменной на TRUE и входит в ее критическую секцию. Другой процесс P1 вызывает TestAndSet () в приведенном выше цикле while, он возвращает TRUE (поскольку P0 имеет блокировку) , в то время как безусловно устанавливает блокировку на FALSE . Во второй раз, когда TestAndSet () вызывается в цикле while, он возвращает FALSE, и P1 входит в критическую секцию, даже если P0 находится в критической секции. Взаимное исключение затем нарушается.

P1 (или любой процесс), независимо от того, является ли блокировка True или False, не устанавливает значение блокировки в False.

• Если блокировка имеет значение False, она входит в критическую секцию и устанавливает для нее значение True, тем самым захватывая блокировку.

• Если значение блокировки равно True, оно ничего не делает (устанавливает свое значение в True, тем самым не меняя его) и ожидает, когда значение блокировки превратится в False (что происходит, когда процесс, имеющий блокировку, завершает выполнение его критической части).

Answer 7

Думайте нелинейно. Вы указали три проблемы в определении Silberchatz, предоставленном для реализации функции testAndSet () :

(1) вы правильно указали, что target установлен на TRUE безоговорочно, и поняли (ошибочно), что это проблема.

(2) Чтобы решить проблему в (1) (которая отсутствует), вы предложили протестировать target , прежде чем установить его в значение TRUE.

(3) Наконец, вы продемонстрировали свои опасения по поводу того факта, что результат установлен в FALSE также безоговорочно блоком, который реализует Взаимное исключение (это на самом деле не происходит).

Я постараюсь прояснить эти вопросы. Первоначально обратите внимание, что первое, что делает функция TestAndSet () , это скопировать значение target в rv и только потом target устанавливается безоговорочно на TRUE. Теперь выгода: если target изначально была FALSE, TestAndSet () устанавливает target в TRUE и возвращает FALSE, поэтому процесс может войти в критическую секцию. В случае, если исходное значение target было TRUE, оно все равно устанавливается в TRUE (что не причиняет вреда), а TestAndSet () возвращает TRUE, поэтому процесс НЕ может войти в критическую область. Таким образом, установка target безусловно на TRUE не является проблемой, и проблема (1) оказывается несуществующей.

Что касается проблемы (2), то, как показано выше, безвредно безоговорочно установить для target значение TRUE, нет необходимости предварительно проверять его значение.

Проблема (3) также не существует, потому что результат на самом деле не установлен безусловно на ЛОЖЬ. Я имею в виду, что это так, но только ПОСЛЕ критической области был обработан процессом; т.е. когда взаимное исключение больше не требуется. Процесс ДОЛЖЕН установить target в FALSE, как только он покинет критическую секцию (он не должен блокировать какие-либо другие процессы после выхода из критической секции). Обязательно снимите блокировку после обработки критической секции!

Answer 8

Рассматривая реализацию взаимного исключения TestAndSet (& lock), можно с уверенностью сказать, что пока TestAndSet возвращает true, процесс (P) не войдет в свою критическую секцию. Процесс будет продолжаться в своем состоянии цикла, пока не произойдет сбой (условие).

Условие выполнится успешно (TestAndSet вернет true), если другой процесс заблокирован для ресурса. Если другой процесс заблокирован для ресурса, значение блокировки равно true. Как только другой процесс освободит удержание над ресурсом, установив lock = false, TestAndSet вернет false.

Когда TestAndSet возвращает false, условие цикла while не выполняется и, следовательно, процесс P входит в критическую секцию.

TestAndSet является атомарной операцией, т.е. выполняется без прерываний. Это сделано для предотвращения условий гонки с помощью блокировки.