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

Question

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

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

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

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

И нет, это не домашняя работа. : -)

Answer 1

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

Ты скоро будешь голодать. ;)

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

Answer 2

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

• В 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) при некотором блокировании системного вызова - ожидание / получение мьютекса, семафора, условной переменной; написать (), опрос () и т. д.

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

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

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

НТН

Answer 3

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

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

Answer 4

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

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

Представьте себе алгоритм, который контролирует доступ компьютеров к глобальной сети или что-то в этом роде. Этот алгоритм может иметь политику, которая гласит: «Предоставлять приоритетный доступ тем компьютерам, которые будут использовать меньшую пропускную способность», это будет выглядеть как правильная политика, но что тогда произойдет, когда один компьютер захочет получить доступ к сети для загрузки по FTP, что отправьте куда-нибудь несколько ГБ. С одной только этой политикой тот компьютер будет голодать, так как алгоритм никогда не выберет тот компьютер, так как всегда будут другие компьютеры, запрашивающие меньшее использование полосы пропускания.

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

Answer 5

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

Answer 6

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