热门问题
时间线
聊天
视角

無窮迴圈

来自维基百科,自由的百科全书

Remove ads

無窮循環endless loop)又稱死循環無限循環(infinite loop),是指程式控制流程一直在重複執行某一段程式碼,無法結束的情形,其原因可能是因為程式中的循環沒有設結束循環條件,或是結束循環的條件不可能成立等。在協作式多工(cooperative multitasking)的作業系統中,無窮循環會使系統沒有反應,若是先佔式多工(preemptive multitasking)的系統中,無窮循環會用掉所有可用的處理器時間,不過可以由用戶結束程式。

有些無窮循環是因為程式錯誤而意外產生的,不過也有些程式的架構是以無窮循環為基礎,在循環執行過程中處理各種事件,這種無窮循環是正常的,不是程式錯誤。

無窮循環是造成系統假死機的原因之一,其他的可能原因包括死鎖或是記憶體區段錯誤

忙碌等待循環是在外界特定條件時(例如有按鍵輸入)才會離開的循環,有時忙碌等待循環也被稱為是無窮循環,但此情形和上述的不太一樣。忙碌等待循環可以藉由外界事件而結束循環,但上述的無窮循環是無法結束的。

Remove ads

蓄意或無意產生的無窮循環

循環是指程式可能會重複執行的某一組指令,若重複執行,在特定條件成立後才會結束,若因為循環的特性,造成特定條件無法滿足,就會形成無窮循環。

蓄意產生的無窮循環

有些情形下程式會蓄意產生無窮循環。例如早期使用ROM匣的遊戲,在主程式的循環是無窮循環,沒有結束條件,原因是一般主程式若不執行時,系統控制權是交由作業系統,但這類遊戲沒有作業系統,因此讓主程式為無窮循環,程式會一直執行到斷電為止。

現在許多的電腦互動系統需要定期的監控用戶的輸入或是裝置的活動,因此當系統閒置時,仍然會在無窮循環中執行,直到系統被重設或斷電為止。像在阿波羅計劃導航用的電腦中,程式的最外層是無窮循環,若完全沒有其他工作要進行時,電腦會關閉「電腦運作中」的指示燈號。

無意產生的無窮循環

若程式中的無窮循環是無意產生的,也就是程式錯誤。新手程式設計師常常會出現這種錯誤,但在資深程式設計師身上也有可能發生,而且錯誤的原因可能相當微妙,因此不容易除錯。

Thumb
循環鏈結串列可能會讓程式變成無窮循環

例如程式設計師想要從收集鏈結串列中所有的資料,因此會依鏈結串列依序前進,直到鏈結串列的尾端為止,但若程式未考慮鏈結串列可能是循環鏈結串列,在循環鏈結串列中依序前進的程式,反而會移動到鏈結串列較前面的部份,此時就會變成無窮循環。

大部份的無窮循環可以藉由詳細的的代碼檢視而找出,不過沒有通用的方式可以判斷程式是否會結束,或者會永遠執行(也就是無窮循環)。判斷程式會結束或會永遠執行的問題稱為停機問題,而英國電腦科學家艾倫·圖靈證明了沒有停機問題的通用演算法[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]

Remove ads

變量處理錯誤

有時不適當的循環結束條件也可能會造成無預期的無窮循環,例如以下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)就沒有這個問題,程式可能會多執行一次循環,但不會變成無窮循環。另一種解決方式則是用一個整數變量作為循環變量,再依此變量判斷是否要結束循環。

數值分析程式中也可能會出現無預期的無窮循環,例如程式需一直迭代到誤差小於某特定值為止,但若因為運算中的捨去誤差,使得誤差一直無法小於該特定值,就會產生無窮循環。

Remove ads

奧爾德森循環

奧爾德森循環(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]

Remove ads

無窮遞歸

無窮遞歸是一種由遞歸造成的無窮循環。例如以下計算階乘的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);  
  }
}
Remove ads

多個模組產生的無窮循環

無窮循環也可能因為多個模組之間的互動而產生。考慮一台伺服器若收到無法理解的需求時,會回應錯誤訊息,此架構中不會有無窮循環。但若有二台上述的伺服器(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為止。

相關條目

參考資料

Loading related searches...

Wikiwand - on

Seamless Wikipedia browsing. On steroids.

Remove ads