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

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

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

Обзор [ править ]

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

How_many   =   0 
 while   is_there_more_data  ()   dohow_many 
     =   +   How_many   "   1 
 end 
 display   "количество подсчитанных элементов =   how_many

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

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

птицы   =   1 
 рыба   =   2 
 , а   птицы   +   рыбы   >   1   , 
     птицы   =   3   —   птицы 
     , рыбы   =   3   —   рыбы 
 конец

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

Подробности [ править ]

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

Намеренное и непреднамеренное зацикливание [ править ]

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

Преднамеренное зацикливание [ править ]

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

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

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

Спинлоки [ править ]

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

Многопоточность [ править ]

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

Непреднамеренное зацикливание [ править ]

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

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

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

Прерывание [ править ]

Пока система реагирует, бесконечные циклы часто можно прервать, отправив сигнал процессу (например, SIGINT в Unix) или прерывание процессора, что приведет к прерыванию текущего процесса. Это можно сделать в диспетчере задач , в терминале командой Control-C , ^[9]или с помощью команды kill или системного вызова . Однако это не всегда работает, так как процесс может не реагировать на сигналы или процессор может находиться в состоянии бесперебойности, как, например, при ошибке Cyrix coma (вызванной перекрытием непрерываемых инструкций в конвейере команд ). В некоторых случаях могут работать другие сигналы, такие как 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   (;;)   // или эквивалентно, while (1) 
     printf  (  "Бесконечный цикл  \n  "  );   
    вернуть   0  ; 
  }

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

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

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

10   ПЕЧАТЬ   «БЕСКОНЕЧНЫЙ ПЕТЛЯ» 
 20   ПЕРЕХОД К   10

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

:  Эхо 
 цикла  бесконечного 
  перейти   :  А

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

Пример на Java

в то время как   (  истина  )   { 
     Система  .   вне  .   println  (  "Бесконечный цикл"  ); 
  }

Пример в Bourne Again Shell

для   ((  ;;  ))  ;    do 
	 echo   "Бесконечный цикл" 
 выполнено

Пример на Rust

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

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

Математические ошибки [ править ]

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

dim   x   как   целое число 
 do   while   x   <   5 
   x   =   1 
   x   =   x   +   1 
 цикл

Это создает ситуацию, когда 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 равно 5!  \n  "  ); 
        а  ++  ; 
     } 
    вернуть   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 :

плавающий   х   =   0,1  ; 
  while   (  x   !=   1.1  )   { 
   printf  (  "x = %22.20f  \n  "  ,   x  ); 
    х   +=   0,1  ; 
  }

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

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

x   =   0,1 
 , а   x   !=   1  : 
     напечатайте  (  x  ) 
     x   +=   0,1

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

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

Многосторонние петли [ править ]

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

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

Псевдобесконечные циклы [ править ]

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

Очень большие числа [ править ]

Пример в bash :

для   x   в   $(  seq   1000000000  )  ;    do 
 #loop код 
 готов

Невозможное условие завершения [ править ]

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

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

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

Бесконечная рекурсия [ править ]

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

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

Sub   Test1  () 
     Вызов   Test1 
 End   Sub

Оператор разрыва [ править ]

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

while   (  истина  )   { 
     if   (  $foo  ->  bar  ())   { 
         return  ; 
      } 
 }

Петля Олдерсона [ править ]

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

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

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

Термин якобы получил свое название от программиста (фамилия Олдерсон), который в 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]