死循环endless loop)又称无穷回圈无限循环(infinite loop),是指程序控制流程一直在重复执行某一段代码,无法结束的情形,其原因可能是因为程序中的循环没有设结束循环条件,或是结束循环的条件不可能成立等。在合作式多工(cooperative multitasking)的操作系统中,死循环会使系统没有反应,若是先占式(preemptive)多工的系统中,死循环会用掉所有可用的处理器时间,不过可以由用户结束程序。死循环是造成系统假死机的原因之一,其他的可能原因包括死锁或是存储器区段错误

忙碌等待循环是在外界特定条件时(例如有按键输入)才会离开的循环,有时忙碌等待循环也被称为是死循环,但此情形和上述的不太一样。忙碌等待循环可以借由外界事件而结束循环,但上述的死循环是无法结束的。

蓄意或无意产生的死循环

编辑

循环是指程序可能会重复执行的某一组指令,若重复执行,在特定条件成立后才会结束,若因为循环的特性,造成特定条件无法满足,就会形成死循环。

蓄意产生的死循环

编辑

有些情形下程序会蓄意产生死循环。例如早期使用ROM匣的游戏,在主程序的循环是死循环,没有结束条件,原因是一般主程序若不执行时,系统控制权是交由操作系统,但这类游戏没有操作系统,因此让主程序为死循环,程序会一直执行到断电为止。

现在许多的电脑交互系统需要定期的监控用户的输入或是设备的活动,因此当系统闲置时,仍然会在死循环中执行,直到系统被重置或断电为止。像在阿波罗计划导航用的电脑中,程序的最外层是死循环,若完全没有其他工作要进行时,电脑会关闭“电脑运作中”的指示灯号。

无意产生的死循环

编辑

若程序中的死循环是无意产生的,也就是程序错误。新手程序员常常会出现这种错误,但在资深程序员身上也有可能发生,而且错误的原因可能相当微妙,因此不容易调试。

 
循环链表可能会让程序变成死循环

例如程序员想要从收集链表中所有的资料,因此会依链表依序前进,直到链表的尾端为止,但若程序未考虑链表可能是循环链表,在循环链表中依序前进的程序,反而会移动到链表较前面的部分,此时就会变成死循环。

大部分的死循环可以借由详细的的代码查看而找出,不过没有通用的方式可以判断程序是否会结束,或者会永远执行(也就是死循环)。判断程序会结束或会永远执行的问题称为停机问题,而英国计算机科学家艾伦·图灵证明了没有停机问题的通用算法[1]

举例

编辑

以下是一些死循环的例子。

C语言的死循环:

#include <stdio.h>
main()
{
  while(1) {
    printf("Infinite Loop\n");//顯示"Infinite Loop"字串
  }
}

上述程序会一直显示"Infinite Loop"字符串。

BASIC语言的死循环:

10 PRINT "Infinite Loop"
20 GOTO 10'跳到行號=10的位置

X86汇编语言的例子:

loop:
  ;空的無窮迴圈,直接跳到"loop"標籤的位置
  jmp loop

Python的例子:

while True:
    print("Infinite Loop")#顯示"Infinite Loop"字串

逻辑错误

编辑

以下是一个Visual Basic死循环的例子:

dim x as integer
do until x > 5 '根本不會有x>5的情形
  x = 1
  x = x + 1
loop

每一次执行循环时x会先设置为1,然后变为2,因为数值未大于5,所以永远不会结束。若将x = 1由循环内部移到循环之前即可以改善此一情形。

有些程序员可能因为不熟悉特定编程语言的语法而造成死循环,例如以下是一段C语言的程序:

#include <stdio.h>

main()
{
  int a = 0;

  while (a < 10) {
    printf("%d\n", a);
    if (a = 5) {//a設定為5,進入無窮迴圈
      printf("a equals 5!\n");
    }
    a++;
  }
  return 0;
}

其预期输出是数字0至9,其中5和6中间会显示"a equals 5!",但程序员在编写程序时将设置用的=运算符及判断相同的==运算符弄混了,因此程序会在每次执行循环时都会将a设置为5,因此变量a永远无法到达10,此循环就变成了死循环。

现代化的编译器,例如clang,都已经可以检测到这一类的潜在问题并给出警告。[2]

变量处理错误

编辑

有时不适当的循环结束条件也可能会造成无预期的死循环,例如以下C语言的例子:

float x = 0.1;
while (x != 1.1) {//可能會因為浮點運算的誤差而出現問題
  printf("x = %f\n", x);
  x = x + 0.1;
}

在有些操作系统中,上述程序会执行10次循环然后结束,但有些系统中,上述程序却可能会一直执行,无法结束,问题主要在循环的结束条件(x != 1.1)要在二个浮点数相等时才结束,结果会依系统处理浮点数的方式而定,只要系统执行10次循环后的结果和1.1差一点点,上述程序就会变成死循环。

若将结束条件改为(x < 1.1)就没有这个问题,程序可能会多执行一次循环,但不会变成死循环。另一种解决方式则是用一个整数变量作为循环变量,再依此变量判断是否要结束循环。

数值分析程序中也可能会出现无预期的死循环,例如程序需一直迭代到误差小于某特定值为止,但若因为运算中的舍去误差,使得误差一直无法小于该特定值,就会产生死循环。

奥尔德森循环

编辑

奥尔德森循环(Alderson loop)是指一个循环有设置结束条件,但因为程序的写法(多半是编程错误),造成永远无法满足结束条件,在针对用户界面程序调试时最容易出现这类的问题。

以下C的伪代码中有一个奥尔德森循环,程序是要计算用户输入一串数字的和,用户输入0时结束循环,但程序中用了不正确的运算符:

sum = 0;
while (true) {
    printf("Input a number to add to the sum or 0 to quit");
    i = getUserInput();
    if (i * 0) {     // 若i乘0为真,则使sum加上i的值
        sum += i;    // 但这不可能发生,因为不论i为何值(i * 0)都是0。如果条件中用的是!=而非*,代码就能正常运行
    }
    if (sum > 100) {
        break;       // 终止循环。结束条件存在,但从来没有达到过,因为sum永远不会增加
    }
}

“奥尔德森循环”来自一个Microsoft Access的程序员,他编写的程序产生一个有模式的对话框,用户需要回应,程序才能继续运作,但对话框没有OK键或取消键,因此只要此对话窗出现,Access程序就无法继续运作[3]

无穷递归

编辑

无穷递归是一种由递归造成的死循环。例如以下计算阶乘的C语言程序:

unsigned int fac(unsigned int a)
{//n!=n*(n-1)!
  return( fac(a-1) * a);
}

一般递归的程序会有一特定条件,此条件成立时直接计算结果,而不是透过递归来计算结果,若程序中未定义此条件,就会出现无穷递归。

无穷递归会造成堆栈溢出,而无穷递归不会结束,因此也是死循环的一种。不过若递归程序是使用尾部递归的处理方式,在有些编程语言(如Scheme)中会优化成循环,因此不会造成堆栈溢出。

上述的程序可以修改成没有无穷递归的程序。

unsigned int fac(unsigned int a)
{
  if (a == 0) {//定義0!=1
    return 1;
  }
  else {
    return( fac(a-1) * a);  
  }
}

多个模块产生的死循环

编辑

死循环也可能因为多个模块之间的交互而产生。考虑一台服务器若收到无法理解的需求时,会回应错误消息,此架构中不会有死循环。但若有二台上述的服务器(A和B),互相交换资料,A收到由B所提交无法理解的需求,会回应错误消息给B,但若B也无法理解A提交的需求(其实是A的错误消息),会再以自己的格式回应错误消息给,A收到后无法理解,会再回应错误消息给B……。像邮件循环英语e-mail loop就是这类的例子。

假死循环

编辑

假死循环是指一个循环看似不会结束,但只是一个执行很长时间,最后仍会结束的循环。

以下是一个C语言for循环的程序:

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

上述程序每次执行时都将i加1,若i等于0时才会结束循环,此程序看似不会结束,但最后还是会结束。程序中类型为unsigned int的变量,其数值有一定上限,当数值已到上限,再加1时,变量数值就会变为0,因此让程序结束。实际的上限值依系统及编译器而不同,假如unsigned int是一个16个比特的字符组,上述的循环会执行65536次。若使用高精度计算,程序会一直执行到存储器无法存储i为止。

相关条目

编辑

参考资料

编辑
  1. ^ 谜样的计算机科学之父
  2. ^ clang test.c -c -Wall
  3. ^ Alderson Loop页面存档备份,存于互联网档案馆) The Jargon File, Version 4.4.7. Accessed 5/21/2006. (public domain)