Бесконечная петля - Infinite loop

Эта статья посвящена термину программирования. Для улицы, названной в честь этого термина, см. Бесконечный цикл (улица). Книгу Майкла С. Мэлоуна см. Бесконечный цикл (книга).
«Бесконечный цикл» перенаправляется сюда. EP Эйко Шимамия см. Бесконечный цикл.
Конструкции петель

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

Обзор

Это отличается от:

  • «тип компьютерной программы, которая выполняет одни и те же инструкции непрерывно, пока она не будет остановлена ​​или прервана».[3]

Рассматривать:

Как много = 0в то время как is_there_more_data() делать    Как много = Как много + 1конецдисплей "количество подсчитанных предметов =" Как много

Те же инструкции были запущены непрерывно, пока он не был остановлен или прерван . . . посредством ЛОЖНЫЙ возвращается в какой-то момент функцией is_there_more_data.

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

птицы = 1рыбы = 2в то время как птицы + рыбы > 1 делать    птицы = 3 - птицы    рыбы = 3 - рыбыконец

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

подробности

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

Преднамеренный цикл против непреднамеренного

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

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

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

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

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

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

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

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

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

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

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

Прерывание

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

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

Смотрите также: Поток управления

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

В некоторых языках есть специальные конструкции для бесконечных циклов, обычно путем исключения условия из неопределенного цикла. Примеры включают Ada (цикл ... конец цикла),[10] Фортран (ДЕЛАТЬ ... КОНЕЦ ДЕЛАТЬ), Идти (для { ... }) и Ruby (цикл делать ... конец).

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

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

 1 #включают <stdio.h> 2  3 int основной() 4 { 5   для (;;) // или эквивалентно while (1) 6   { 7     printf("Бесконечная петля п"); 8   } 9   вернуть 0;10 }

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

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

Похожий пример в 1980-е годы БАЗОВЫЙ:

10РАСПЕЧАТАТЬ"БЕСКОНЕЧНАЯ ПЕТЛЯ"20ПЕРЕЙТИ К10

Аналогичный пример в ДОС командные файлы:

:Аэхо Бесконечная петляперейти к :А

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

Пример в Ява

в то время как (правда)     Система.вне.println("Бесконечная петля");

Пример в Bourne Again Shell

для ((;;)); делать	эхо "Бесконечная петля"сделанный

Пример в Ржавчина

петля{println!("Бесконечная петля");}

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

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

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

тусклый Икс так как целое числоделать в то время как Икс < 5  Икс = 1  Икс = Икс + 1петля

Это создает ситуацию, когда Икс никогда не будет больше 5, так как в начале кода цикла Икс дается значение 1, поэтому цикл всегда будет заканчиваться на 2, и цикл никогда не прерывается. Это можно исправить, переместив х = 1 инструкция вне цикла. По сути, этот бесконечный цикл дает компьютеру команду продолжать прибавлять 1 к 1, пока не будет достигнуто 5. Поскольку 1 + 1 всегда равно 2, этого никогда не произойдет.

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

#включают <stdio.h>int основной(пустота){   int а = 0;   в то время как (а < 10) {      printf("% d п", а);      если (а = 5)         printf("а равно 5! п");      а++;   }   вернуть 0;}

Ожидаемый результат - числа от 0 до 9 с вставленным "a равно 5!" от 5 до 6. Однако в строке "если (a = 5)"выше, программист перепутал оператор = (присваивание) с оператором == (проверка равенства). Вместо этого он присвоит значение 5 а в этот момент в программе. Таким образом, а никогда не сможет перейти к 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:

плавать Икс = 0.1;в то время как (Икс != 1.1) {  printf("x =% 22.20f п", Икс);  Икс += 0.1;}

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

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

Икс = 0.1в то время как Икс != 1:    Распечатать(Икс)    Икс += 0.1

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

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

Многопартийные петли

Видео бесконечного цикла от Google Home и Amazon Echo

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

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

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

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

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

Пример в трепать:

для х в $(seq 1000000000); делать#loop codeсделанный

Невозможное условие прекращения

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

беззнаковый int я;для (я = 1; я != 0; я++) {  / * код цикла * /}

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

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

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

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

Sub Test1()    Вызов Test1Конец Sub

Заявление о перерыве

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

в то время как (правда) {    если ($ foo->бар()) {        вернуть;    }}

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

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

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

int сумма = 0;int я;в то время как (правда) {   printf(«Введите число, чтобы добавить к сумме, или 0, чтобы выйти»);   я = getUserInput();   если (я * 0) { // если i умножить на 0 верно, добавляем i к сумме. Примечание: НУЛЬ означает ЛОЖЬ, Ненулевое значение означает ИСТИНА. «i * 0» - НУЛЬ (ЛОЖЬ)!      сумма += я; // сумма никогда не меняется, потому что (i * 0) равно 0 для любого i; он бы изменился, если бы в условии! = вместо *   }   если (сумма > 100) {      перерыв;    // завершаем цикл; условие выхода существует, но никогда не достигается, потому что сумма никогда не добавляется к   }}

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

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

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

использованная литература

  1. ^ "Определение словаря бесконечного цикла".
  2. ^ «Что такое бесконечный цикл (бесконечный цикл)».
  3. ^ Дениз Карузо (16 августа 1999 г.). «Перегрузка вешалок создает ухабистую дорогу для интернет-акций». Нью-Йорк Таймс.
  4. ^ «Коды и приемы: характер документальной культуры». Журнал потока. Ноябрь 2014 г. бесконечный цикл - это тот, в котором отсутствует .. условие выхода
  5. ^ также известная как многозадачность без вытеснения: «Бесперебойная многозадачность». Журнал ПК. Получено 15 августа, 2015.
  6. ^ Дэвид Хоаг (сентябрь 1976 г.). "История бортового наведения, навигации и управления Apollo" (PDF). Лаборатория Чарльза Старка Дрейпера.
  7. ^ "Ответы на кроссворды New York Times". 13 октября 2013 г. вычисление .. дефект .. который .. зацикливать
  8. ^ «Проблема остановки в теории вычислений».
  9. ^ «Использование переполнения буфера против программы дистанционного управления DameWare». 19 декабря 2003 г. Как только командная оболочка закрывается комбинацией control-c ...
  10. ^ Программирование на Ada: управление: бесконечный цикл
  11. ^ «Бесконечный цикл в C / C ++». В архиве из оригинала от 03.08.2016.
  12. ^ Ли Дом (24 мая 2013 г.). «Петля Алдерсона».
  13. ^ "Петля Олдерсона". Файл жаргона, Версия 4.4.7. В архиве из оригинала 15.05.2006. Получено 2006-05-21.