2009年12月13日 星期日

堆疊 (Stack)

http://4rdp.blogspot.com/2009/12/stack.html

近日網友 0319 留言請教關於 NXC 編譯問題,在此補充討論另一核心議題,MCU (Micro Control Unit) 的角度看程式執行,這樣可能可以解答一些程式設計者的疑惑。

學過計算機概論的朋友,應該知道什麼是 CPU (Central Processing Unit)、ROM (Read-Only Memory)、RAM (Random-Access Memory)、IO (Input/Output),簡單說這些東西相當於人的頭腦、永久記憶區、臨時記憶區、感官與四肢。 CPU 在執行程式時對於 RAM 的使用,有些重要的觀念,因為教科書很少提及或是老師略過沒教,導致許多程式設計師並不明白原理,個人就在此補充說明。

首先,堆疊觀念,CPU 會選定一塊 RAM 區域當堆疊運用,所有的 CPU 都有這麼一塊區域,它受 CPU 控制使用,一般使用者沒辦法直接使用它。什麼是堆疊?它像許多本書堆在一起,每一本書代表一筆資料,新資料會疊在舊資料的上面,因此最上面的東西沒被取走之前,被壓在下面的東西是沒辦法使用,LIFO (Last In First Out) 後進先出就是它的操作程序。什麼時候用?呼叫副程式時,必須記住現在程式位置,因此 CPU 會將目前程式位址存入堆疊中,然後跳到副程式執行,如果第一個副程式又再呼叫第二個副程式,那麼會在堆疊中放入第一個副程式的位置。執行完第二個副程式後,會先從堆疊中取出第一個副程式位置跳回去,執行完第一個副程式後,從堆疊中再取出主程式位置跳回去。請參考下圖。


NXT 無法使用遞歸 (Recursion) 一文,曾討論過 NXC 無法編譯遞歸的程式,主要就是 NXT 的作業系統限制使用者,如果樂高開放這項限制,那麼可能會有當機的災難發生,只要使用者寫了一個自己呼叫自己的程式,並且執行不完,那麼所有的記憶體就會被堆疊佔用而當機,尤其 NXT 的主要使用者多為學生很喜歡亂搞或者是搞不清楚狀況,那麼 LEGO 就會被抱怨不完。

第二,區域變數 (Local Variables) 與全域變數 (Global Variables) ,這兩類變數的最大差異在於區域變數限用於副程式本身,外部的程式是無法使用的,在標準 C 語言,變數放置位置的宣告有四種方式:auto、register、extern、static,而這些在 NXC 都被省略,在此進一步討論,先談標準 C,再論 NXC。下列例子應該可以說明所有變數情形,

   file1.c

char variable_A; // static & global
static char variable_B; // static & global

void main(void) {

char i; // auto & local

variable_A = 1;

for (i=0 ; i<10 ; i++)
sub1(i);

}

---------------------------------------------------------------------------

file2.c

extern char variable_A; // static & global
extern char variable_B; // static & global

void sub1(char variable_C) { // auto & local

char variable_D; // auto & local
auto char variable_E; // auto & local
register char variable_F; // register & local
static char variable_G; // static & local

variable_A++;
variable_B++;
variable_C++;
variable_D++;
variable_E++;
variable_F++;
variable_G++;

}

static 表示靜態資料會放在堆疊之外,會有自己獨立的記憶空間,資料不會隨意清除,如果是全域變數則所有的程式都可以使用,像 variable_A,main() 將它設為 1,而 sub1() 加十次變為 11。
extern 表示外部變數,這一定是全域變數,變數已經在 file1.c 宣告,file2.c 引用它而已。
auto 表示自動,通常資料會動態放置於堆疊之中,下次再執行相同程式,先前存放的資料會不見,並且會不確定其內容。
register 表示以暫存器放資料,什麼是暫存器?一般 CPU 至少有兩個以上暫存器,可以當資料暫放的地方,利用暫存器做資料運算處理很快,因為它在 CPU 內部,但是你使用 register 變數宣告,編譯器並不一定讓你用得到它!?因為暫存器數量有限,不夠用時,編譯器會找個地方擺資料。資深的韌體工程師為確保編譯結果符合預期,都會再檢查編譯後的機械碼,確定變數資料型態與位置正確。

就個人對 NXC 的了解,它應該使用 static 方式處理變數,這樣使用者的程式較能精確掌控。

沒有留言:

張貼留言