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