Активная взаимоблокировка

В некоторых ситуациях процесс старается проявить вежливость, отказавшись от уже приобретенной блокировки, как только замечает, что не может получить следющую блокировку, в которой нуждается. Затем он ждет, скажем, несколько миллисекунд и повторяет попытку.
В принципе, в таком поведении нет ничего плохого, и оно помогает обнаружить взаимоблокировку и избавиться от нее. Но если другой процесс делает то же самое в точности в то же самое время, эти процессы попадут в ситуацию, похожую на ту, когда два человека пытаются разминуться на улице и каждый из них вежливо уходит в сторону, но из этого ничего не выходит, поскольку они пытаются одновременно уйти в одну и ту же сторону. Рассмотрим атомарный примитив try_lock, с помощью которого вызывающий процесс проверяет мьютекс и либо захватывает его, либо возвращает ошибку. Иными словами, он никогда не блокируется. Программисты могут использовать этот примитив совместно с примитивом acquire lock, который также пытается захватить блокировку, но блокируется, если блокировка недоступна. Теперь представим себе два запущенных в параллель процесса (возможно, на разных ядрах), использующих два ресурса (листинг 6.3). Каждому из них нужны два ресурса, и они используют примитив try_lock, чтобы попытаться заполучить необходимые блокировки. Если попытка терпит неудачу, процесс освобождает уже удерживаемую блокировку и повторяет попытку. В листинге 6.3 первый процесс запускается и получает ресурс 1, в то же время запускается второй процесс и получает ресурс 2. Затем они пытаются получить вторую блокировку и терпят неудачу. Проявляя вежливость, они освобождают текущую удерживаемую блокировку и повторяют попытку. Эта процедура повторяется до тех пор, пока пользователю (или другой заинтересованной строне) не надоест и он не избавит один из процессов от его страданий. Понятно, что ни один из процессов не заблокирован, и можно даже сказать, что какие-то действия совершаются, следовательно, это не взаимоблокировка. Но ситуация не получает развития, поэтому мы получаем некий эквивалент — активную взаимоблокировку (livelock).

Листинг 6.3. Вежливые процессы, которые могут вызвать активную

взаимоблокировку

void process A(void) {

acquire lock(&resource 1); while (try lock(&resource 2) == FAIL) { release lock(&resource 1); wait fixed time(); acquire lock(&resource 1);

}

use both resources( ); release lock(&resource 2); release lock(&resource 1);

}

void process A(void) {

acquire lock(&resource 2); while (try lock(&resource 1) == FAIL) { release lock(&resource 2); wait fixed time(); acquire lock(&resource 2);

}

use both resources( ); release lock(&resource 1); release lock(&resource 2);

}

Активная взаимоблокировка может возникать совершенно неожиданно.

В некоторых системах общее количество разрешенных процессов определено числом записей в таблице процессов. Таким образом, элементы таблицы процессов являются конечными ресурсами. Если системный вызов ветвления — fork — не выполняется из-за того, что таблица полна, разумным подходом со стороны программы, осуществляющей fork, будет подождать некоторое время и повторить попытку.

Теперь предположим, что у UNIX-системы имеется 100 элементов в таблице процессов. Запущено 10 программ, каждой из которых необходимо создать 12 дочерних процессов. После того как каждый процесс создал 9 процессов, 10 исходных и 90 новых процессов полностью используют таблицу. Каждый из 10 исходных процессов теперь находится в бесконечном цикле попытки ветвления и отказа, то есть попадает во взаимоблокировку Вероятность того, что это произойдет, невелика, но это может случиться. Должны ли мы ликвидировать процессы и вызов fork, чтобы устранить проблему?

Максимальное количество открытых файлов также ограничено размером таблицы i-узлов, поэтому при ее заполнении возникает аналогичная проблема. Еще одним ограниченным ресурсом является пространство для свопинга на диске. Фактически почти каждая таблица в операционной системе представляет собой конечный ресурс. Должны ли мы упразднять все это, поскольку может случиться так, что в коллекции из n процессов каждый может потребовать 1/n всего количества ресурсов, а затем каждый попытается потребовать еще один ресурс? Наверное, это не самая лучшая идея.

Большинство операционных систем, включая ИШХ и просто игнорируют

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

6.7.4.

<< | >>
Источник: Э. ТАНЕНБАУМ Х. БОС. СОВРЕМЕННЫЕ ОПЕРАЦИОННЫЕ СИСТЕМ Ы 4-е ИЗДАНИЕ. 2015

Еще по теме Активная взаимоблокировка:

  1. Правило активного слушания и поддержания речевой активности гражданина.
  2. ЛИЧНОСТЬ: АКТИВНОСТЬ
  3. АКТИВНОСТЬ НАДСИТУАТИВНАЯ
  4. АКТИВНОСТЬ
  5. ПРИНЦИП АКТИВНОСТИ
  6. АКТИВНОСТЬ СВЕРХНОРМАТИВНАЯ
  7. АКТИВНОСТЬ ПОИСКОВАЯ
  8. СЛУШАНИЕ АКТИВНОЕ
  9. АКТИВНОСТЬ ПСИХИЧЕСКАЯ: БИОРИТМ
  10. Активность и пассивность
  11. ФИЗИОЛОГИЯ АКТИВНОСТИ
  12. АКТИВНОСТЬ ОБЩАЯ
  13. АКТИВНОСТЬ ОТЧУЖДЕННАЯ
  14. Активный отдых
  15. БИОРИТМ АКТИВНОСТИ ПСИХИЧЕСКОЙ
  16. 7.2. АКТИВНЫЙ СКЕПТИЦИЗМ
  17. Мастурбационная активность