Что такое голодание?
В многозадачных системах некоторые ненормальные условия препятствуют выполнению процессов или потоков. Я буду называть и процессы, и потоки просто "процессами". Два из этих условий называются мертвым замком и живым замком.
Первый относится к процессам, которые блокируют друг друга, таким образом предотвращая выполнение любого из них. Последнее относится к процессам, которые мешают друг другу прогрессировать, но фактически не блокируют выполнение. Например, они могут постоянно заставляют друг друга откатывать транзакции, ни один из которых никогда не сможет их завершить.
Другое состояние известно как ресурсный голод, при котором один или несколько конечных ресурсов, необходимых для прогресса процессов, были исчерпаны ими и не могут быть восстановлены, если процессы не прогрессируют. Это также особый случай live-lock.
Я хотел бы знать, есть ли какое-либо другое определение, особенно академическое, для "голода", которое не ограничивается " ресурсом голод". Ссылки особенно приветствуются.
И, нет, это не домашнее задание. :- )
6 ответов:
Я бы не сказал, что ресурсное голодание-это частный случай живого потока. Обычно:
В livelock ни один поток не делает прогресса, но они продолжают выполняться. (В тупике они даже не продолжают выполнять)
При голодании некоторые потоки действительно прогрессируют, а некоторые потоки не выполняются.
Хорошее объяснение: http://docs.oracle.com/javase/tutorial/essential/concurrency/starvelive.html . но я понимаю выбор терминология может варьироваться.
Когда речь заходит о голоде, я слышу следующее определение:Предположим, что можно указать бесконечный путь выполнения (чередование), согласующийся с предположениями (Семафорная семантика, поведение планировщика ОС)...) такой, что поток 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-вы можете рассматривать его как ресурс. Если это происходит, проблема с планировщиком.
HTH
Представьте, что вы стоите в очереди, чтобы купить еду в ресторане, для которого беременные женщины имеют приоритет. И там просто целая куча беременных женщин прибывает все время.
Скоро ты будешь голодать. ;) Теперь представьте, что вы-процесс с низким приоритетом, а беременные женщины-процесс с более высоким приоритетом. =)
Другая область, где обычно возникает голодание или" неопределенная блокировка", - это когда речь идет об алгоритмах приоритетного планирования. Алгоритм приоритетного планирования имеет возможность оставить некоторый процесс с низким приоритетом в ожидании бесконечно. Постоянный поток процессов с более высоким приоритетом может помешать запуску процесса с низким приоритетом.
В случае с приоритетными планировщиками решение "стареет". Старение-это метод постепенного увеличения приоритета процессов, которые ждите в системе в течение длительного времени.
Голодание-это просто когда процесс или услуга не обслуживаются, даже если в системе нет тупика.
Это пример,который я только что придумал для разъяснения.
Представьте себе алгоритм, который контролирует доступ компьютеров к глобальной сети или что-то в этом роде. Этот алгоритм может иметь политику, которая гласит: "обеспечьте приоритетный доступ к тем компьютерам,которые будут использовать меньшую пропускную способность.", это будет выглядеть как правильная политика, но тогда что происходит, когда один компьютер хочет получить доступ к сети для ftp-загрузки, которая отправит несколько ГБ куда-то. С одной только этой политикой этот компьютер будет голодать, так как алгоритм никогда не выберет этот компьютер, так как всегда будут другие компьютеры, требующие меньшего использования полосы пропускания.
Это называется голоданием.
Работа также является своего рода ресурсом. Когда распределение работы в системе производитель-потребитель не является справедливым (или идеальным), некоторые потоки могут не получать достаточно рабочих элементов, чтобы постоянно быть занятыми.
Процесс не получает ресурс или ресурсы в течение более длительного времени. Это не тупик, потому что один процесс/ы выполняются без проблем. Старение может быть использовано для решения этой проблемы, фактор старения используется для каждого запроса.
Comments