В информатике , голодание ресурса является проблемой , встречающейся в параллельном вычислительном , где процесс будет постоянно отрицал необходимые ресурсы для обработки своей работы. [1] Истощение может быть вызвано ошибками в алгоритме планирования или взаимного исключения , но также может быть вызвано утечкой ресурсов и может быть вызвано намеренно посредством атаки отказа в обслуживании, такой как вилочная бомба .
Когда голодание невозможно в параллельном алгоритме , алгоритм называется голоданием свободным , блокировка освобожденным [2] или указанным иметь конечный байпас . [3] Это свойство является примером живучести и одним из двух требований для любого алгоритма взаимного исключения; другая - правильность . Название «конечный обход» означает, что любой процесс (параллельная часть) алгоритма обходится не более конечного числа раз, прежде чем ему будет разрешен доступ к совместно используемому ресурсу . [3]
Планирование [ править ]
Голод обычно вызван чрезмерно упрощенным алгоритмом планирования . Например, если (плохо спроектированная) многозадачная система всегда переключается между первыми двумя задачами, а третья никогда не запускается, тогда третьей задаче не хватает процессорного времени . Алгоритм планирования, который является частью ядра , должен распределять ресурсы справедливо; то есть алгоритм должен распределять ресурсы так, чтобы ни одному процессу постоянно не хватало необходимых ресурсов.
Многие планировщики операционных систем используют концепцию приоритета процесса. Процесс A с высоким приоритетом будет выполняться перед процессом B с низким приоритетом. Если процесс с высоким приоритетом (процесс A) блокируется и никогда не завершается, процесс с низким приоритетом (B) никогда не будет (в некоторых системах) запланирован - он будет испытывать голод. Если существует процесс X с еще более высоким приоритетом, который зависит от результата процесса B, то процесс X может никогда не завершиться, даже если это самый важный процесс в системе. Это состояние называется инверсией приоритета . Современные алгоритмы планирования обычно содержат код, гарантирующий, что все процессы получат минимальное количество каждого важного ресурса (чаще всего процессорного времени), чтобы предотвратить истощение любого процесса.
В компьютерных сетях, особенно в беспроводных сетях, алгоритмы планирования могут страдать от нехватки расписания. Примером может служить планирование максимальной пропускной способности .
Истощение обычно вызывается тупиковой ситуацией, которая приводит к зависанию процесса. Два или более процесса зашли в тупик, когда каждый из них ничего не делает в ожидании ресурса, занятого другой программой в том же наборе. С другой стороны, процесс находится в состоянии "голодания", когда он ожидает ресурса, который постоянно предоставляется другим процессам. Свобода от голода является более сильной гарантией, чем отсутствие тупика: алгоритм взаимного исключения, который должен разрешить одному из двух процессов попасть в критическую секцию и выбрать один произвольно, свободен от тупиков, но не от голода. [3]
Возможное решение проблемы голодания - использовать алгоритм планирования с очередью приоритетов, который также использует метод устаревания . Старение - это метод постепенного повышения приоритета процессов, которые долгое время ждут в системе. [4]
См. Также [ править ]
Ссылки [ править ]
- ^ Таненбаум, Эндрю (2001). Современные операционные системы . Прентис Холл. С. 184–185 . ISBN 0-13-092641-8.
- ^ Херлихи, Морис ; Шавит, Нир (2012). Искусство многопроцессорного программирования . Эльзевир. п. 24. ISBN 9780123977953.
- ^ a b c Рейналь, Мишель (2012). Параллельное программирование: алгоритмы, принципы и основы . Springer Science & Business Media. п. 10–11. ISBN 3642320279.
- Перейти ↑ Galvin, Peter (2010). Понятия операционной системы . Wiley India Edition. п. 193. ISBN. 978-81-265-2051-0.
