Что такое голод?

В многозадачных системах некоторые ненормальные условия предотвращают прогресс выполнения процессов или потоков. Я рассмотрю как процессы, так и потоки просто как "процессы". Два из этих условий называются dead-lock и live-lock.

Первое относится к процессам, которые блокируют друг друга, тем самым предотвращая выполнение. Последнее относится к процессам, которые не позволяют друг другу прогрессировать, но фактически не блокируют выполнение. Например, они могут постоянно заставлять друг друга откатывать транзакции, и не могут их завершить.

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

Я хотел бы знать, есть ли какое-либо другое определение, особенно академическое, для "голодания", которое не ограничивается "ресурсным голоданием". Ссылки приветствуются.

И нет, это не домашнее задание.: -)

Ответ 1

Я бы не сказал, что ресурсное голодание - это особый случай оживления. Обычно:

В livelock ни одна нить не продвигается, но они продолжают выполняться. (В тупике они даже не выполняют выполнение)
При голодании некоторые потоки (DO) делают прогресс, а некоторые потоки не выполняются.

Хорошее объяснение: http://docs.oracle.com/javase/tutorial/essential/concurrency/starvelive.html. Но я понимаю, что выбор терминологии может варьироваться.

Когда дело доходит до голода, определение, которое я слышал, это:

Предположим, что можно указать бесконечный путь выполнения (чередование), согласующийся с предположениями (семантика семестра, поведение планировщика ОС...), так что поток T приостановлен в ожидании некоторого ресурса и никогда не возобновляется, даже если это возможно бесконечно много раз. Тогда T называется голодающим.

Но практика не соответствует этому. Предположим, что два потока выполняют критический раздел в бесконечном цикле. Ваш код синхронизации позволяет первому потоку входить в критический раздел один раз в час. Это голод? Оба потока могут прогрессировать, но первый из них делает работу медленным образом.

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

Классические проблемы, когда голодание хорошо известно:

Проблема читателей-писателей. Можно синхронизировать потоки таким образом, чтобы (1) читатели смогут голодать писателям (2) писатели смогут голодать читателям (3) голодания не произойдет (См. http://en.wikipedia.org/wiki/Readers-writers_problem)
Обеденные философы (http://en.wikipedia.org/wiki/Dining_philosophers_problem)

Для более подробной информации я полностью рекомендую Маленькую Книгу Семафоров (бесплатно): http://www.greenteapress.com/semaphores/.

Вы спрашиваете, вызвано ли каждое голодание ожиданием какого-либо ресурса. Я бы сказал - да.

Нить может быть приостановлена:

(1) на некотором блокирующем системном вызове - ожидание/получение мьютекса, семафора, условной переменной; write(), poll() и т.д.

(2) по некоторой неблокирующей операции - например, при выполнении вычислений.

Голодание на (1) голодает на ресурсы (мьютексы, буфер и т.д.).

Голодание на (2) голодает на CPU - вы можете рассматривать его как ресурс. Если это произойдет, проблема связана с планировщиком.

НТН

Ответ 2

Представьте, что вы находитесь в очереди, чтобы купить еду в ресторане, для которого беременные женщины имеют приоритет. И там всего целая куча беременных женщин, прибывающих все время.

Скоро вы будете голодать.;)

Теперь представьте, что вы - низкоприоритетный процесс, а беременные женщины - более приоритетные. =)

Ответ 3

Другая область, где обычно возникают голодания или "неопределенная блокировка", - это когда речь идет о алгоритмах приоритетного планирования. Алгоритм приоритетного планирования имеет возможность оставить неопределенный процесс с низким приоритетом. Постоянный поток процессов с более высоким приоритетом может предотвратить запуск низкоприоритетного процесса.

В случае приоритетных планировщиков решение является "стареющим". Старение - это метод постепенного увеличения приоритета процессов, которые ждут в системе в течение длительного времени.

Ответ 4

Голодание - это просто, когда процесс или служба не обслуживаются, даже если в системе нет тупика.

Это пример, который я только что сделал для разъяснения.

Представьте себе алгоритм, который контролирует доступ компьютеров к глобальной сети или что-то в этом роде. Этот алгоритм может иметь политику, которая гласит: "Обеспечьте приоритетный доступ к тем компьютерам, которые будут использовать меньшую пропускную способность". Это будет выглядеть как правильная политика, но тогда что произойдет, когда один компьютер захочет получить доступ к сети для загрузки ftp, которая будет отправьте несколько GB где-нибудь. Только с этой политикой этот компьютер будет голодать, поскольку алгоритм никогда не выберет этот компьютер, так как всегда будут другие компьютеры, требующие меньшего использования полосы пропускания.

Это называется голодом.

Ответ 5

Работа также является своего рода ресурсом. Когда распределение работы в настройке производителя и потребителя не является справедливым (или идеальным), некоторые потоки могут не получать достаточное количество рабочих элементов, чтобы постоянно их было занято.

Ответ 6

Сделайте пример головоломки блокировки в java. Все о приоритете потока. Не уверен, что пример хорош, но вы можете посмотреть здесь.

Ответ 7

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