Голод (информатика) - Starvation (computer science)

Для использования в других целях см. Голод (значения).

В Информатика, ресурсный голод проблема возникает в параллельные вычисления где процесс постоянно отрицают необходимость Ресурсы обработать свою работу.[1] Голод может быть вызван ошибками в расписании или взаимное исключение алгоритм, но также может быть вызван утечки ресурсов, и могут быть намеренно вызваны атака отказа в обслуживании например, вилка бомба.

Когда голодание невозможно в параллельный алгоритм, алгоритм называется без голода, освобожденный от локаута[2] или сказал, что имеет конечный обход.[3] Это свойство является экземпляром живость, и является одним из двух требований для любого алгоритма взаимного исключения; другое существо правильность. Название «конечный обход» означает, что любой процесс (параллельная часть) алгоритма обходится не более конечного числа раз, прежде чем ему будет разрешен доступ к общий ресурс.[3]

Планирование

Голод обычно вызывается чрезмерно упрощенным алгоритм планирования. Например, если (плохо спроектированная) многозадачная система всегда переключается между первыми двумя задачами, а третья никогда не запускается, тогда третья задача не хватает Время процессора. Алгоритм планирования, который является частью ядро предполагается справедливое распределение ресурсов; то есть алгоритм должен распределять ресурсы так, чтобы ни один процесс постоянно не испытывал недостатка в необходимых ресурсах.

Многие планировщики операционных систем используют концепцию приоритета процесса. Процесс A с высоким приоритетом будет выполняться перед процессом с низким приоритетом B. Если процесс с высоким приоритетом (процесс A) блокируется и никогда не завершается, процесс с низким приоритетом (B) никогда не будет (в некоторых системах) запланирован - он будет испытывать голод. Если существует процесс X с еще более высоким приоритетом, который зависит от результата процесса B, то процесс X может никогда не завершиться, даже если это самый важный процесс в системе. Это состояние называется инверсия приоритета. Современные алгоритмы планирования обычно содержат код, гарантирующий, что все процессы получат минимальное количество каждого важного ресурса (чаще всего процессорного времени), чтобы предотвратить истощение любого процесса.

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

Голод обычно вызывается тупик в том, что это приводит к зависанию процесса. Два или более процесса зашли в тупик, когда каждый из них ничего не делает в ожидании ресурса, занятого другой программой в том же наборе. С другой стороны, процесс находится в режиме ожидания, когда он ожидает ресурса, который постоянно предоставляется другим процессам. Свобода от голода - более сильная гарантия, чем отсутствие тупика: алгоритм взаимного исключения, который должен разрешить один из двух процессов в одну критическая секция и выбирает один произвольно, без тупиков, но не без голода.[3]

Возможное решение проблемы голодания - использовать алгоритм планирования с приоритетной очередью, который также использует старение техника. Старение - это метод постепенного повышения приоритета процессов, которые долгое время ждут в системе.[4]

Смотрите также

Рекомендации

  1. ^ Таненбаум, Эндрю (2001). Современные операционные системы. Прентис Холл. стр.184–185. ISBN  0-13-092641-8.
  2. ^ Херлихи, Морис; Шавит, Нир (2012). Искусство многопроцессорного программирования. Эльзевир. п. 24. ISBN  9780123977953.
  3. ^ а б c Рейналь, Мишель (2012). Параллельное программирование: алгоритмы, принципы и основы. Springer Science & Business Media. п. 10–11. ISBN  3642320279.
  4. ^ Галвин, Питер (2010). Понятия операционной системы. Wiley India Edition. п. 193. ISBN  978-81-265-2051-0.