В информатике нехватка ресурсов — это проблема, возникающая при параллельных вычислениях , когда процессу постоянно отказывают в необходимых ресурсах для выполнения своей работы. [1] Недостаточность может быть вызвана ошибками в планировании или алгоритме взаимного исключения , но также может быть вызвана утечкой ресурсов или может быть преднамеренно вызвана посредством атаки типа «отказ в обслуживании», такой как вилочная бомба .
Когда голодание невозможно в параллельном алгоритме , этот алгоритм называется «без голодания» , «без блокировки» [2] или говорят, что он имеет конечный обход . [3] Это свойство является примером жизнеспособности и одним из двух требований для любого алгоритма взаимного исключения; другое - правильность . Название «конечный обход» означает, что любой процесс (параллельная часть) алгоритма обходится не более конечного числа раз, прежде чем ему будет разрешен доступ к общему ресурсу . [3]
Причиной голодания обычно является слишком упрощенный алгоритм планирования . Например, если (плохо спроектированная) многозадачная система всегда переключается между первыми двумя задачами, а третья никогда не запускается, то третья задача испытывает нехватку процессорного времени . Алгоритм планирования, являющийся частью ядра , должен справедливо распределять ресурсы; то есть алгоритм должен распределять ресурсы так, чтобы ни один процесс не испытывал постоянной нехватки необходимых ресурсов.
Многие планировщики операционных систем используют концепцию приоритета процесса. Процесс A с высоким приоритетом будет запускаться раньше процесса B с низким приоритетом. Если процесс с высоким приоритетом (процесс A) блокируется и никогда не завершается, процесс с низким приоритетом (B) (в некоторых системах) никогда не будет запланирован — он будет зависать. Если существует процесс X с еще более высоким приоритетом, который зависит от результата процесса B, то процесс X может никогда не завершиться, даже если это самый важный процесс в системе. Это состояние называется инверсией приоритетов . Современные алгоритмы планирования обычно содержат код, гарантирующий, что все процессы получат минимальное количество каждого важного ресурса (чаще всего процессорного времени), чтобы предотвратить голодание любого процесса.
В компьютерных сетях, особенно в беспроводных, алгоритмы планирования могут страдать от нехватки времени. Примером является планирование максимальной пропускной способности .
Недостаточность обычно вызывается взаимоблокировкой , поскольку она приводит к зависанию процесса. Два или более процесса заходят в тупик, когда каждый из них ничего не делает, ожидая ресурса, занятого другой программой в том же наборе. С другой стороны, процесс находится в состоянии голодания, когда он ожидает ресурса, который постоянно передается другим процессам. Свобода от голодания является более сильной гарантией, чем отсутствие тупиковой ситуации: алгоритм взаимного исключения, который должен разрешить один из двух процессов в критическую секцию и выбирает один произвольно, свободен от тупиков, но не свободен от голодания. [3]
Возможным решением проблемы голодания является использование алгоритма планирования с приоритетной очередью, который также использует технику старения . Старение — это метод постепенного повышения приоритета процессов, которые ждут в системе в течение длительного времени. [4]