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

Question

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

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

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

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

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

Answer 1

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

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

• Когда вы голодаете, некоторые потоки ДЕЙСТВИТЕЛЬНО добиваются прогресса, а некоторые потоки не выполняются.

Хорошее объяснение: 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) означает истощение процессора - вы можете рассматривать это как ресурс.Если это происходит, то проблема связана с планировщиком.

HTH

Answer 2

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

Скоро ты умрешь с голоду.;)

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

Answer 3

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

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

Answer 4

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

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

Представьте себе алгоритм, который управляет доступом компьютеров к глобальной сети или что-то в этом роде.У этого алгоритма могла бы быть политика, которая гласит "Предоставлять приоритетный доступ тем компьютерам, которые будут использовать меньшую пропускную способность". Это будет казаться правильной политикой, но что тогда происходит, когда один компьютер хочет получить доступ к сети для загрузки по ftp, которая отправит куда-то несколько ГБ?При одной только этой политике этот компьютер будет голодать, поскольку алгоритм никогда не выберет этот компьютер, поскольку всегда будут другие компьютеры, запрашивающие меньшее использование полосы пропускания.

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

Answer 5

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

Answer 6

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