Бесконечный цикл

В компьютерном программировании ( бесконечный цикл или бесконечный цикл ). ^[1]^[2] представляет собой последовательность инструкций, которая, как написано, будет продолжаться бесконечно, если только не произойдет внешнее вмешательство, например, отключение питания с помощью выключателя или выдергивание вилки. Это может быть намеренно.

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

Обзор

Это отличается от «типа компьютерной программы, которая непрерывно выполняет одни и те же инструкции, пока ее не остановят или не прервут». ^[3] Рассмотрим следующий псевдокод :

how_many = 0
while is_there_more_data() do
    how_many = how_many + 1
end
display "the number of items counted = " how_many

Одни и те же инструкции выполнялись непрерывно, пока не были остановлены или прерваны . . . значением FALSE , возвращаемым в какой-то момент функцией is_there_more_data .

Напротив, следующий цикл не завершится сам по себе:

birds = 1
fish = 2
while birds + fish > 1 do
    birds = 3 - birds
    fish = 3 - fish
end

птицы будут попеременно быть 1 или 2, а рыбы будут попеременно 2 или 1. Цикл не остановится, если не произойдет внешнее вмешательство («вытащите вилку»).

Подробности

Бесконечный цикл — это последовательность инструкций в компьютерной программе , которая выполняется бесконечно, либо из-за того, что цикл не имеет условий завершения, либо из-за того, что цикл не имеет условий завершения, ^[4] наличие такого, которое никогда не может быть выполнено, или такого, которое заставляет цикл начинаться заново. В старых операционных системах с совместной многозадачностью ^[5] бесконечные циклы обычно приводили к тому, что вся система переставала отвечать на запросы. В ныне распространенной модели вытесняющей многозадачности бесконечные циклы обычно приводят к тому, что программа потребляет все доступное процессорное время, но обычно может быть прекращен пользователем. Занятые циклы ожидания также иногда называют «бесконечными циклами». компьютера Бесконечные циклы — одна из возможных причин зависания или зависания ; другие включают перегрузку , взаимоблокировку и нарушения прав доступа .

Намеренное и непреднамеренное зацикливание

Цикл — это повторение набора инструкций до тех пор, пока не будет выполнено определенное условие. Бесконечный цикл возникает, когда условие никогда не будет выполнено из-за какой-либо внутренней характеристики цикла.

Преднамеренное зацикливание

Есть несколько ситуаций, когда это желательное поведение. Например, игры на игровых консолях с картриджами обычно не имеют условий выхода в основном цикле, поскольку нет операционной системы, из которой программа могла бы выйти; цикл выполняется до тех пор, пока консоль не будет выключена.

Современные интерактивные компьютеры требуют, чтобы компьютер постоянно отслеживал ввод пользователя или активность устройства, поэтому на каком-то фундаментальном уровне существует бесконечный цикл простоя обработки , который должен продолжаться до тех пор, пока устройство не будет выключено или перезагружено. Например, в управляющем компьютере Apollo этот внешний цикл содержался в программе Exec. ^[6] и если бы у компьютера не было абсолютно никакой другой работы, он запускал бы в цикле фиктивное задание, которое просто отключало бы световой индикатор «активности компьютера».

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

Спинлоки

Спин-блокировки — это механизмы синхронизации низкого уровня, используемые в параллельном программировании для защиты общих ресурсов. В отличие от традиционных блокировок, которые переводят поток в спящий режим, когда он не может получить блокировку, спин-блокировки неоднократно «вращаются» в бесконечном цикле, пока блокировка не станет доступной. Этот преднамеренный бесконечный цикл — это осознанный выбор конструкции, направленный на минимизацию времени, которое поток тратит на ожидание блокировки, и избежание накладных расходов на механизмы синхронизации более высокого уровня, такие как мьютексы .

Многопоточность

В многопоточных программах некоторые потоки могут выполняться внутри бесконечных циклов, не заставляя всю программу застревать в бесконечном цикле. Если основной поток завершается, все потоки процесса принудительно останавливаются, таким образом, все выполнение завершается, а процесс/программа завершается. Потоки внутри бесконечных циклов могут выполнять «хозяйственные» задачи или могут находиться в заблокированном состоянии, ожидая ввода (из сокета/очереди) и возобновлять выполнение каждый раз при получении ввода.

Непреднамеренное зацикливание

Чаще всего этот термин используется для тех ситуаций, когда это не является запланированным результатом; то есть, когда это ошибка . ^[7] Такие ошибки чаще всего встречаются у начинающих программистов, но их могут допустить и опытные программисты, поскольку их причины могут быть весьма тонкими.

Например, одной из распространенных причин является то, что программист намеревается перебрать последовательность узлов в структуре данных , такой как связанный список или дерево , выполняя код цикла один раз для каждого узла. Неправильно сформированные связи могут создать в структуре данных опорный цикл , в котором один узел ссылается на другой, который встречается раньше в последовательности. Это превращает часть структуры данных в кольцо , что приводит к бесконечному зацикливанию наивного кода.

Хотя большинство бесконечных циклов можно обнаружить путем внимательного изучения кода, не существует общего метода определения, остановится ли когда-либо данная программа или будет работать вечно; это неразрешимость проблемы остановки . ^[8]

Прерывание

Пока система реагирует, бесконечные циклы часто могут быть прерваны отправкой сигнала процессу (например, SIGINT в Unix) или прерыванием процессора, что приводит к прерыванию текущего процесса. Это можно сделать в диспетчере задач , в терминале командой Control-C , ^[9] или с помощью команды kill или системного вызова . Однако это не всегда работает, поскольку процесс может не реагировать на сигналы или процессор может находиться в состоянии бесперебойности, как, например, при ошибке комы Cyrix (вызванной перекрытием непрерываемых инструкций в конвейере команд ). В некоторых случаях могут работать другие сигналы, такие как SIGKILL , поскольку они не требуют реакции процесса, тогда как в других случаях цикл не может быть завершен до выключения системы.

Языковая поддержка

Бесконечные циклы могут быть реализованы с использованием различных конструкций потока управления . Чаще всего в неструктурированном программировании это переход назад ( goto ), тогда как в структурированном программировании это бесконечный цикл (цикл while), который никогда не заканчивается, либо путем пропуска условия, либо явно устанавливая для него значение true, как while (true) ....

В некоторых языках есть специальные конструкции для бесконечных циклов, обычно путем исключения условия из неопределенного цикла. Примеры включают Аду ( loop ... end loop), ^[10] Фортран ( DO ... END DO), Идти ( for { ... }), Рубин ( loop do ... end) и Руст ( loop { ... }).

Примеры преднамеренных бесконечных циклов

Простой пример (на C ):

#include <stdio.h>

int main()
{
  for (;;) // or equivalently, while (1)
    printf("Infinite Loop\n");  
  return 0;
}

Форма for (;;) поскольку бесконечный цикл является традиционным, появляется в стандартном справочнике Язык программирования C и часто шутливо произносится как «навсегда». ^[11]

Это цикл, который печатает «Бесконечный цикл» без остановки.

Аналогичный пример в BASIC 1980-х годов :

10 PRINT "INFINITE LOOP"
20 GOTO 10

Аналогичный пример в DOS пакетных файлах :

:A
echo Infinite Loop
goto :A

Здесь цикл совершенно очевиден, поскольку последняя строка безоговорочно возвращает выполнение первой.

Пример на Java

while (true) {
    System.out.println("Infinite Loop");
}

Пример в Bourne Again Shell

for ((;;)); do
	echo "Infinite Loop"
done

Пример на Rust

loop {
    println!("Infinite loop");
}

Примеры непреднамеренных бесконечных циклов

Математические ошибки

Вот один пример бесконечного цикла в Visual Basic :

dim x as integer
do while x < 5
  x = 1
  x = x + 1
loop

Это создает ситуацию, когда x никогда не будет больше 5, поскольку в начале кода цикла x присваивается значение 1 (независимо от любого предыдущего значения), прежде чем оно будет изменено на x + 1. Таким образом, цикл всегда будет приводить к x = 2 и никогда не сломается. Это можно исправить, переместив x = 1 инструкцию вне цикла, так что ее начальное значение устанавливается только один раз.

В некоторых языках путаница программистов в отношении математических символов может привести к непреднамеренному бесконечному циклу. Например, вот фрагмент на C :

#include <stdio.h>

int main(void)
{
   int a = 0;
   while (a < 10) {
      printf("%d\n", a);
      if (a = 5)
         printf("a equals 5!\n");
      a++;
   }
   return 0;
}

Ожидаемый результат — числа от 0 до 9 с вставленным знаком «а равно 5!» между 5 и 6. Однако в строке " if (a = 5)" выше оператор = (присваивание) был перепутан с оператором == (проверка равенства). Вместо этого оператору будет присвоено значение 5. a на этом этапе программы. Таким образом, a никогда не сможет перейти к 10, и этот цикл не может завершиться.

Ошибки округления

Вывод C на процессоре AMD Turion :

х = 0,10000000149011611938

х = 0,20000000298023223877

х = 0,30000001192092895508

х = 0,40000000596046447754

х = 0,50000000000000000000

х = 0,60000002384185791016

х = 0,70000004768371582031

х = 0,80000007152557373047

х = 0,90000009536743164062

х = 1,00000011920928955078

х = 1,10000014305114746094

х = 1,20000016689300537109

...

Неожиданное поведение при оценке завершающего условия также может вызвать эту проблему. Вот пример на C :

float x = 0.1;
while (x != 1.1) {
  printf("x = %22.20f\n", x);
  x += 0.1;
}

В некоторых системах этот цикл выполнится десять раз, как ожидалось, но в других системах он никогда не завершится. Проблема в том, что условие завершения цикла (x != 1.1) тесты на точное равенство двух значений с плавающей запятой , а способ представления значений с плавающей запятой на многих компьютерах приведет к провалу этого теста, поскольку они не могут точно представлять значение 0,1, что приводит к появлению ошибок округления для каждого приращения (см. Вставку).

То же самое может произойти и в Python :

x = 0.1
while x != 1:
    print(x)
    x += 0.1

Из-за вероятности неожиданного сбоя тестов на равенство или неравенство, при работе со значениями с плавающей запятой безопаснее использовать тесты «больше» или «меньше». Например, вместо проверки того, x равно 1,1, можно проверить, является ли (x <= 1.0), или (x < 1.1), любой из которых обязательно завершится после конечного числа итераций. Другой способ исправить этот конкретный пример — использовать целое число в качестве индекса цикла , подсчитывающего количество выполненных итераций.

Подобная проблема часто возникает при численном анализе : для вычисления определенного результата предполагается выполнять итерацию до тех пор, пока ошибка не станет меньше выбранного допуска. Однако из-за ошибок округления во время итерации заданный допуск никогда не может быть достигнут, что приводит к бесконечному циклу.

Многосторонние циклы

Бесконечный цикл может быть вызван взаимодействием нескольких сущностей. Рассмотрим сервер, который всегда отвечает сообщением об ошибке, если не понимает запрос. Даже если нет возможности бесконечного цикла внутри самого сервера, система, состоящая из двух из них ( A и B ), может зацикливаться бесконечно: если A получает сообщение неизвестного типа от B , то A отвечает сообщением об ошибке B. ; если B не понимает сообщение об ошибке, он отвечает A своим собственным сообщением об ошибке; если A не понимает сообщение об ошибке от B , он отправляет еще одно сообщение об ошибке и так далее.

Одним из распространенных примеров такой ситуации является цикл электронной почты . Примером зацикливания электронной почты является ситуация, когда кто-то получает письмо из почтового ящика, в котором нет ответа, но у него включен автоматический ответ. Они ответят на входящие сообщения, на которые нет ответа, что вызовет ответ «Это входящие сообщения, на которые нет ответа». Это будет отправлено пользователю, который затем отправит автоматический ответ в почтовый ящик без ответа и так далее и тому подобное.

Псевдобесконечные циклы

Псевдобесконечный цикл — это цикл, который кажется бесконечным, но на самом деле это просто очень длинный цикл.

Очень большие числа

Пример в bash :

for x in $(seq 1000000000); do
#loop code
done

Невозможное условие завершения

Пример цикла в C :

unsigned int i;
for (i = 1; i != 0; i++) {
  /* loop code */
}

Кажется, что так будет продолжаться бесконечно, но на самом деле значение i в конечном итоге достигнет максимального значения, которое можно сохранить в unsigned int и добавление 1 к этому числу приведет к возврату к 0, разрывая цикл. Фактический предел i зависит от деталей используемой системы и компилятора . При арифметике произвольной точности компьютера этот цикл будет продолжаться до тех пор, пока память не перестанет вмещать i. Если i было целым числом со знаком, а не целым числом без знака, переполнение будет неопределенным. В этом случае компилятор может оптимизировать код до бесконечного цикла.

Бесконечная рекурсия

Бесконечная рекурсия — это частный случай бесконечного цикла, вызванного рекурсией .

Следующий пример в Visual Basic для приложений (VBA) возвращает ошибку переполнения стека :

Sub Test1()
    Call Test1
End Sub

Оператор разрыва

А " while (true)На первый взгляд цикл выглядит бесконечным, но может быть способ выйти из цикла с помощью оператора Break или оператора возврата . Пример на PHP :

while (true) {
    if ($foo->bar()) {
        return;
    }
}

Петля Олдерсона

Цикл Олдерсона — это редкий жаргонный термин , обозначающий бесконечный цикл, в котором имеется условие выхода, но оно недоступно в реализации кода, обычно из-за ошибки программиста. Они наиболее распространены и заметны при отладке кода пользовательского интерфейса .

Пример C-подобного псевдокода цикла Олдерсона, где программа должна суммировать числа, заданные пользователем, до тех пор, пока не будет задан ноль, но где используется неправильный оператор:

int sum = 0;
int i;
while (true) {
   printf("Input a number to add to the sum or 0 to quit");
   i = getUserInput();
   if (i * 0) { // if i times 0 is true, add i to the sum. Note: ZERO means FALSE, Non-Zero means TRUE. "i * 0" is ZERO (FALSE)!
      sum += i; // sum never changes because (i * 0) is 0 for any i; it would change if we had != in the condition instead of *
   }
   if (sum > 100) {
      break;    // terminate the loop; exit condition exists but is never reached because sum is never added to
   }
}

Термин якобы получил свое название от программиста (фамилия Олдерсон), который в 1996 г. ^[12] написал модальное диалоговое окно в Microsoft Access без кнопок «ОК» или «Отмена», тем самым отключая всю программу всякий раз, когда появлялось это окно. ^[13]

См. также

Обнаружение цикла
Дивергенция (информатика)
Вилочная бомба (бесконечный цикл — один из двух ключевых компонентов)
Бесконечный регресс

Ссылки

^ «Определение словаря бесконечного цикла» . Архивировано из оригинала 01 августа 2020 г. Проверено 22 января 2020 г.
^ «Что такое бесконечный цикл (бесконечный цикл)» . Архивировано из оригинала 15 июля 2019 г. Проверено 22 января 2020 г.
^ Карузо, Дениз (16 августа 1999 г.). «Перегрузка прихлебателей создает ухабистую дорогу для интернет-акций» . Нью-Йорк Таймс . Архивировано из оригинала 27 декабря 2019 года . Проверено 27 декабря 2019 г.
^ «Коды и режимы: характер документальной культуры» . Журнал потока . Ноябрь 2014 г. Архивировано из оригинала 1 августа 2020 г. Проверено 23 января 2020 г. бесконечный цикл — это цикл, в котором отсутствует условие выхода
^ также известный как невытесняющая многозадачность: «Невытесняющая многозадачность» . Журнал ПК . Архивировано из оригинала 26 июля 2019 года . Проверено 7 февраля 2024 г.
^ Дэвид Хоаг (сентябрь 1976 г.). «История бортового наведения, навигации и управления Аполлона» (PDF) . Лаборатория Чарльза Старка Дрейпера. Архивировано (PDF) из оригинала 5 ноября 2016 г. Проверено 23 января 2020 г.
^ «Ответы на кроссворды Нью-Йорк Таймс» . 13 октября 2013 г. Архивировано из оригинала 2 августа 2020 г. Проверено 22 января 2020 г. вычисления.. дефект.. который.. зациклить
^ «Проблема остановки в теории вычислений» . 3 октября 2018 г. Архивировано из оригинала 9 августа 2020 г. . Проверено 22 января 2020 г.
^ «Эксплуатация переполнения буфера против программного обеспечения DameWare Remote Control» . 19 декабря 2003 г. Архивировано из оригинала 24 июля 2020 г. Проверено 22 января 2020 г. Как только командная оболочка закрывается комбинацией control-c...
^ Программирование на языке Ada: Управление: бесконечный цикл
^ «Бесконечный цикл в C/C++» . Архивировано из оригинала 3 августа 2016 г.
^ Ли Дом (24 мая 2013 г.). «Петля Олдерсона» . Архивировано из оригинала 19 июня 2020 года . Проверено 22 января 2020 г.
^ «Петля Олдерсона» . Файл жаргона , версия 4.4.7 . Архивировано из оригинала 15 мая 2006 г. Проверено 21 мая 2006 г.

Внешние ссылки

Создайте бесконечный цикл на нескольких языках на сайте program-idioms.org .

[1] «Определение словаря бесконечного цикла» . Архивировано из оригинала 01 августа 2020 г. Проверено 22 января 2020 г.

[2] «Что такое бесконечный цикл (бесконечный цикл)» . Архивировано из оригинала 15 июля 2019 г. Проверено 22 января 2020 г.

[3] Карузо, Дениз (16 августа 1999 г.). «Перегрузка прихлебателей создает ухабистую дорогу для интернет-акций» . Нью-Йорк Таймс . Архивировано из оригинала 27 декабря 2019 года . Проверено 27 декабря 2019 г.

[4] «Коды и режимы: характер документальной культуры» . Журнал потока . Ноябрь 2014 г. Архивировано из оригинала 1 августа 2020 г. Проверено 23 января 2020 г. бесконечный цикл — это цикл, в котором отсутствует условие выхода

[5] также известный как невытесняющая многозадачность: «Невытесняющая многозадачность» . Журнал ПК . Архивировано из оригинала 26 июля 2019 года . Проверено 7 февраля 2024 г.

[6] Дэвид Хоаг (сентябрь 1976 г.). «История бортового наведения, навигации и управления Аполлона» (PDF) . Лаборатория Чарльза Старка Дрейпера. Архивировано (PDF) из оригинала 5 ноября 2016 г. Проверено 23 января 2020 г.

[7] «Ответы на кроссворды Нью-Йорк Таймс» . 13 октября 2013 г. Архивировано из оригинала 2 августа 2020 г. Проверено 22 января 2020 г. вычисления.. дефект.. который.. зациклить

[8] «Проблема остановки в теории вычислений» . 3 октября 2018 г. Архивировано из оригинала 9 августа 2020 г. . Проверено 22 января 2020 г.

[9] «Эксплуатация переполнения буфера против программного обеспечения DameWare Remote Control» . 19 декабря 2003 г. Архивировано из оригинала 24 июля 2020 г. Проверено 22 января 2020 г. Как только командная оболочка закрывается комбинацией control-c...

[10] Программирование на языке Ada: Управление: бесконечный цикл

[11] «Бесконечный цикл в C/C++» . Архивировано из оригинала 3 августа 2016 г.

[12] Ли Дом (24 мая 2013 г.). «Петля Олдерсона» . Архивировано из оригинала 19 июня 2020 года . Проверено 22 января 2020 г.

[13] «Петля Олдерсона» . Файл жаргона , версия 4.4.7 . Архивировано из оригинала 15 мая 2006 г. Проверено 21 мая 2006 г.

[1]

[2]

[3]

[4]

[5]

[6]

[7]

[8]

[9]

[10]

[11]

[12]

[13]