Рубрики

ВОРОТА | GATE CS 2012 | Вопрос 30

Fetch_And_Add (X, i) — это атомарная инструкция Read-Modify-Write, которая считывает значение ячейки памяти X, увеличивает его на значение i и возвращает старое значение X. Она используется в псевдокоде, показанном ниже, для реализации занят-ожидание блокировки. L — целочисленная переменная общего назначения без знака, инициализированная значением 0. Значение 0 соответствует доступной блокировке, тогда как любое ненулевое значение соответствует недоступности блокировки.

  AcquireLock(L){
         while (Fetch_And_Add(L,1))
               L = 1;
   }
  ReleaseLock(L){
         L = 0;
   }

Эта реализация
(A) терпит неудачу, поскольку L может переполниться
(B) терпит неудачу, поскольку L может принимать ненулевое значение, когда блокировка фактически доступна
(C) работает правильно, но может вызвать голод
(D) работает правильно без голодания

Ответ: (Б)
Пояснение: Присмотритесь к циклу while.

     while (Fetch_And_Add(L,1))
               L = 1;  // A waiting process 
                       // can be here just after 
                       // the lock is released, 
                       // and can make L = 1.

Рассмотрим ситуацию, когда процесс только что снял блокировку и сделал L = 0. Пусть будет еще один процесс, ожидающий блокировки, то есть выполнение функции AcquireLock (). Сразу после того, как L был равен 0, пусть ожидающие процессы выполнили строку L = 1. Теперь блокировка доступна, а L = 1. Поскольку L равен 1, ожидающий процесс (и любые другие будущие будущие процессы) не могут выйти из цикла пока.

Приведенную выше проблему можно решить, изменив AcuireLock () на следующий.

  AcquireLock(L){
         while (Fetch_And_Add(L,1))
         { // Do Nothing }
   }

Переполнение может произойти, только когда большее количество процессов, чем размер int, выполняет условие проверки цикла while, но не L = 1, т. Е. Требуется вытеснение.
Но когда L равно 1, процесс повторяется в цикле while — переполнения не происходит, потому что после каждого приращения в L L снова устанавливается равным 1.
Вариант (б) является лучшим выбором по сравнению с вариантом (а).

Источник: http://espressocode.top/operating-systems-set-17/

Тест на этот вопрос

Рекомендуемые посты:

ВОРОТА | GATE CS 2012 | Вопрос 30

0.00 (0%) 0 votes