建站
咨詢
售后
建站咨詢
新聞中心
1.棧是什么
不妨我們先看一下《新華字典》是如何定義的。
我們提供的服務(wù)有：成都做網(wǎng)站、成都網(wǎng)站設(shè)計(jì)、微信公眾號(hào)開發(fā)、網(wǎng)站優(yōu)化、網(wǎng)站認(rèn)證、棲霞ssl等。為上千余家企事業(yè)單位解決了網(wǎng)站和推廣的問題。提供周到的售前咨詢和貼心的售后服務(wù)，是有科學(xué)管理、有技術(shù)的棲霞網(wǎng)站制作公司
棧基本含義是儲(chǔ)存貨物或供旅客住宿的房屋，如貨棧，客棧。
說到客棧又讓我聯(lián)想到一部著名的武俠電影“新龍門客棧”，客棧就是提供給各位大俠一個(gè)臨時(shí)居住的房間。
既然客棧也是“?！?，說明棧的底層的含義一樣，都是用來做存儲(chǔ)的。在計(jì)算機(jī)中“?！笔菙?shù)據(jù)存儲(chǔ)空間中的一個(gè)區(qū)域，用于儲(chǔ)存特定的數(shù)據(jù)。
棧的承載實(shí)體通常是隨機(jī)存取存儲(chǔ)器(RAM)，CPU可以直接與RAM交換數(shù)據(jù)，RAM在工作狀態(tài)下，可以隨時(shí)從任何一個(gè)指定的地址寫入(存入)或讀出(取出)信息。
綜上所述，在計(jì)算機(jī)中“?！本褪谴鎯?chǔ)數(shù)據(jù)的一個(gè)存儲(chǔ)區(qū)域。通常說的“堆?！焙汀皸！?，這兩者意義相同。
2.棧的分類
我們知道棧就是用來存儲(chǔ)數(shù)據(jù)的，在實(shí)際使用中棧并不是只有唯一的一種形式，而是分為多種類型，接下來我們了解一下棧的分類。
根據(jù)棧在存儲(chǔ)器中的增長方向，可以把棧分為遞減棧和遞增棧 ：
遞減棧(Descend) ：向棧寫入數(shù)據(jù)時(shí)，棧的生長方向是高地址到低地址。
遞增棧(Increase) ：向棧寫入數(shù)據(jù)時(shí)，棧的生長方向是低地址到高地址。
根據(jù)棧指針SP指向的位置，可以把棧分為滿堆棧和空堆棧：
滿堆棧(Full Stack)：SP指針始終指向棧頂元素，向棧寫入數(shù)據(jù)時(shí)先移動(dòng)SP指針，再將數(shù)據(jù)放入SP指向的地址。
空堆棧(Empty Stack)：SP指針始終指向下一個(gè)將要放入元素的位置，向棧寫入數(shù)據(jù)時(shí)先將數(shù)據(jù)放入SP指向的地址，再移動(dòng)SP指針。
根據(jù)棧的增長方向和棧指針的位置，?？梢苑譃橐韵?種基本類型：
- 滿增棧(FA)：棧指針指向最后壓入的數(shù)據(jù)，棧的生長方向是低地址向高地址。
- 滿減棧(FD)：棧指針指向最后壓入的數(shù)據(jù)，棧的生長方向是高地址向低地址。
- 空增棧(EA)：棧指針指向下一個(gè)將要壓入數(shù)據(jù)的地址，棧的生長方向是低地址向高地址生長。
- 空減棧(ED)：棧指針指向下一個(gè)將要壓入數(shù)據(jù)的地址，棧的生長方向是高地址向低地址生長。
其中滿減棧是使用得最多的一種棧類型。
3.棧的操作
計(jì)算機(jī)的結(jié)構(gòu)框圖如下：
由圖可知在處理器中直接參入運(yùn)算的是寄存器堆中的寄存器，邏輯運(yùn)算的結(jié)果可以輸出到數(shù)據(jù)存儲(chǔ)器的地址端口和寄存器堆的數(shù)據(jù)端口。
寄存器堆中的寄存器值可以輸出到數(shù)據(jù)存儲(chǔ)器的數(shù)據(jù)端口，實(shí)現(xiàn)暫存寄存器的值。
棧操作就是將寄存器的值存入數(shù)據(jù)存儲(chǔ)器，或是將數(shù)據(jù)存儲(chǔ)器中的數(shù)據(jù)回讀到寄存器中。
重要的事情說三遍：
- 棧就是用來暫存處理器中寄存器的值!
- 棧就是用來暫存處理器中寄存器的值!
- 棧就是用來暫存處理器中寄存器的值!
ARM構(gòu)架處理器中的寄存器組如下：
棧操作的兩個(gè)指令：入棧PUSH和出棧POP。
對(duì)于PUSH操作，處理器先減小SP值，然后將指定寄存器存儲(chǔ)到SP寄存器指向的存儲(chǔ)器地址。
對(duì)于POP操作,處理器先將SP指向的存儲(chǔ)器地址存儲(chǔ)到指定寄存器中，然后將SP寄存器值增加。
棧的操作具有“先進(jìn)后出”的特性，先存入棧的數(shù)據(jù)，在棧的底部，后存入棧的數(shù)據(jù)在頂部，棧中的數(shù)據(jù)只能從棧頂部讀出，因此就有了“先進(jìn)后出”。
以滿減棧為例，下圖展示了連續(xù)兩次PUSH操作，SP寄存器和數(shù)據(jù)存儲(chǔ)器中的數(shù)據(jù)變化。
PUSH操作時(shí)處理器先減小SP值，然后將指定寄存器存儲(chǔ)到SP寄存器指向的存儲(chǔ)器地址。
注意：執(zhí)行PUSH操作后數(shù)據(jù)存儲(chǔ)器中(?？臻g)的數(shù)據(jù)發(fā)生變化，但是指定寄存器的值還是原有的值(不會(huì)被清零)。
以滿減棧為例，下圖展示了連續(xù)兩次POP操作，SP寄存器和指定寄存器的數(shù)據(jù)變化。
POP操作時(shí)處理器先將SP指向的存儲(chǔ)器地址存儲(chǔ)到指定寄存器中，然后將SP寄存器值增加。
注意：執(zhí)行POP操作后指定寄存器的數(shù)據(jù)發(fā)生變化，但是數(shù)據(jù)存儲(chǔ)器中(?？臻g)的數(shù)值還是原有的值(不會(huì)被清零)。
PUSH操作后由于指定的寄存器的數(shù)據(jù)被保存，因此此后可以將該寄存器用于其它用途，當(dāng)該寄存器完成其它操作后可以通過POP操作恢復(fù)原先數(shù)值。
由于在處理器中只有寄存器能直接參入運(yùn)算，通常情況下寄存器的數(shù)量有限(通常為16個(gè)或者32個(gè))，棧操作相當(dāng)于將寄存器的數(shù)量進(jìn)行擴(kuò)展。這種操作類似火影忍者中鳴人的影分身(一個(gè)真身多個(gè)假身)。
總結(jié)棧操作：
- 棧是一個(gè)數(shù)據(jù)存儲(chǔ)空間(棧空間)。
- 棧有一個(gè)棧指針，指向當(dāng)前棧地址。
- 每次執(zhí)行PUSH操作后?？臻g的數(shù)據(jù)發(fā)生變化，每次執(zhí)行POP操作后指定寄存器的數(shù)據(jù)發(fā)生變化。
- 每次PUSH和POP操作后SP棧指針都會(huì)自動(dòng)調(diào)整(無需用戶介入)。
4.棧的作用
上文描述了棧空間本質(zhì)上暫存處理器中寄存器的運(yùn)算結(jié)果，具體來說棧用于如下4情況的數(shù)據(jù)存儲(chǔ)：
1、用于保存函數(shù)執(zhí)行前的寄存器的值，以便函數(shù)結(jié)束時(shí)恢復(fù)。
2、用于存儲(chǔ)局部變量。
3、用于傳遞函數(shù)調(diào)用時(shí)的參數(shù)。
4、用于存儲(chǔ)中斷產(chǎn)生時(shí)的狀態(tài)寄存器和通用寄存器的數(shù)值。
4.1函數(shù)調(diào)用前保存寄存器值
當(dāng)被調(diào)用的函數(shù)需要使用寄存器進(jìn)行數(shù)據(jù)處理時(shí)，需要使用棧臨時(shí)保存寄存器的數(shù)值，當(dāng)函數(shù)結(jié)束時(shí)恢復(fù)寄存器的數(shù)值。
測試代碼如下：
/******************************************
* @作者 : liwei
* @Github : liyinuoman2017
*******************************************/
void test(void)
{
int l , m , n;
l = 9;
m = 8;
n = l+ m;
}
void stack_test(void)
{
int i , j , k;
i = 1;
j = 2;
test();
k = i+ j;
}
int main(void)
{
int a0,a1,a2,a3,a4,a5,a6,a7,a8,a9;
a0 = 1;
a1 = 3;
a2 = 1;
a3 = 4;
a4 = 1;
a5 = 7;
a6 = 9;
a7 = 5;
a8 = 2;
a9 = 0;
/***調(diào)用測試函數(shù)**/
stack_test();
a0 = a1 + a2;
a3 = a4 + a5;
}
mian函數(shù)中定義了較多變量從而占用了大量寄存器，stack_test函數(shù)定義了3個(gè)變量，在調(diào)用stack_test函數(shù)前處理器的寄存器已經(jīng)被全部占用，為了提供寄存器給stack_test函數(shù)使用，就必須先將部分寄存器保存到棧中，當(dāng)stack_test函數(shù)執(zhí)行結(jié)束后從棧中恢復(fù)部分寄存器的值。
main函數(shù)反匯編后的結(jié)果如下：
stack_test函數(shù)反匯編后的結(jié)果如下：
根據(jù)stack_test函數(shù)匯編代碼可知：由于stack_test函數(shù)需要使用R4，R5，R6而這3個(gè)寄存器，由于這3個(gè)寄存器已經(jīng)被占用，因此stack_test函數(shù)在使用R4，R5，R6前，必須先將這3個(gè)寄存器保存到棧中，并在stack_test函數(shù)執(zhí)行結(jié)束返回前從棧中恢復(fù)R4，R5，R6這3個(gè)寄存器的數(shù)值。
總結(jié)：調(diào)用子函數(shù)時(shí)，子函數(shù)內(nèi)需要使用寄存器，由于寄存器已經(jīng)被占用，因此需要將函數(shù)調(diào)用者使用的寄存器保存到棧中，待調(diào)用函數(shù)結(jié)束后再恢復(fù)寄存器。
4.2存儲(chǔ)局部變量
局部變量可以直接存儲(chǔ)到寄存器中，但是當(dāng)局部變量比較多時(shí)，一部分變量將會(huì)保存到棧中。
測試代碼如下：
/******************************************
* @作者 : liwei
* @Github : liyinuoman2017
*******************************************/
int main(void)
{
int a0,a1,a2,a3,a4,a5,a6,a7,a8,a9,a10,a11,a12,a13,a14,a15;
a0 = 1;
a1 = 3;
a2 = 1;
a3 = 4;
a4 = 1;
a5 = 7;
a6 = 9;
a7 = 5;
a8 = 2;
a9 = 1;
a10 = 3;
a11 = 1;
a12 = 4;
a13 = 1;
a14 = 7;
a15 = 9;
a0 = a1 + a2;
a3 = a4 + a5;
a6 = a7 + a8;
a9 = a10 + a11;
a12 = a13 + a14;
a15 = a1 + a2;
}
main函數(shù)反匯編后的結(jié)果如下：
根據(jù)反匯編可知，當(dāng)使用的局部變量較多時(shí)，部分局部變量會(huì)被保存到棧中。
4.3保存子函數(shù)參數(shù)
ARM體系結(jié)構(gòu)的過程調(diào)用標(biāo)準(zhǔn)AAPCS (Procedure Call Standard for the ARM Architecture)，它規(guī)定了子程序的調(diào)用規(guī)則，其中ARM寄存器在子程序調(diào)用中的參數(shù)傳遞規(guī)則如下：
當(dāng)子程序參數(shù)不超過4個(gè)時(shí)，使用寄存器R0-R3來傳遞參數(shù)，當(dāng)參數(shù)超過4個(gè)時(shí)，超出的參數(shù)使用棧來傳遞參數(shù)。
調(diào)用有2個(gè)參數(shù)的子函數(shù)的測試代碼如下：
/******************************************
* @作者 : liwei
* @Github : liyinuoman2017
*******************************************/
int sum(int a , int b)
{
return ( a + b );
}
int main(void)
{
int a0 = 0;
a0 = sum( 3 , 4 );
while(1);
}
代碼反匯編如下：
由反匯編可知，在跳轉(zhuǎn)到sum函數(shù)前使用R0,R1保存了sum函數(shù)的2個(gè)參數(shù)。
調(diào)用有6個(gè)參數(shù)的子函數(shù)的測試代碼如下：
/******************************************
* @作者 : liwei
* @Github : liyinuoman2017
*******************************************/
int sum(int a , int b, int c, int d, int e, int f)
{
return ( a + b + c + d + e + f );
}
int main(void)
{
int a0 = 0;
a0 = sum( 1 , 3 , 2 , 4 , 7 , 9 );
while(1);
}
代碼反匯編如下：
由反匯編可知，在跳轉(zhuǎn)到sum函數(shù)前使用R0,R1,R2,R3保存了后4個(gè)函數(shù)參數(shù)，同時(shí)將第一個(gè)和第二個(gè)參數(shù)存入棧中，在sum函數(shù)中從棧中加載參數(shù)帶入計(jì)算。
因此在很多編程規(guī)范規(guī)定函數(shù)參數(shù)不能超過3個(gè)。原因是利用棧傳遞參數(shù)影響程序執(zhí)行效率。
4.4中斷時(shí)存儲(chǔ)寄存器
當(dāng)處理器產(chǎn)生異?；蛑袛鄷r(shí)，在進(jìn)入異常函數(shù)前，處理器硬件會(huì)自動(dòng)保存部分寄存器，待異常函數(shù)執(zhí)行完畢后，執(zhí)行異常返回時(shí)，處理器硬件會(huì)自動(dòng)恢復(fù)之前保存的寄存器的值。
ARM構(gòu)架處理器中斷時(shí)序圖如下：
5.棧區(qū)的優(yōu)勢
計(jì)算機(jī)中的內(nèi)存分區(qū)通常如下：
數(shù)據(jù)存儲(chǔ)器通常分為：棧區(qū)，堆區(qū)，靜態(tài)區(qū)。
棧區(qū)用于存儲(chǔ)特定用法的變量，棧區(qū)內(nèi)的變量是臨時(shí)的變化的，棧區(qū)使用大小是動(dòng)態(tài)變化的。
堆區(qū)用于用戶主動(dòng)分配存儲(chǔ)數(shù)據(jù)。
靜態(tài)區(qū)用于存儲(chǔ)靜態(tài)變量，靜態(tài)區(qū)內(nèi)的變量的使用周期是整個(gè)程序運(yùn)行周期，每個(gè)變量對(duì)應(yīng)一個(gè)地址，“一個(gè)蘿卜一個(gè)坑”。
堆區(qū)在本文不進(jìn)行描述，本節(jié)重點(diǎn)對(duì)比棧區(qū)和靜態(tài)區(qū)。棧區(qū)的優(yōu)勢是什么?棧區(qū)能用靜態(tài)區(qū)代替嗎?
5.1棧區(qū)的優(yōu)勢
假設(shè)現(xiàn)在有如下一個(gè)函數(shù)：
void test(void)
{
char buff[100];
...
}
函數(shù)test中定義了一個(gè)100字節(jié)的數(shù)組buff，因此運(yùn)行程序執(zhí)行到test函數(shù)時(shí)會(huì)臨時(shí)占用100字節(jié)的棧區(qū)。假設(shè)把buff該成靜態(tài)類型static char buff[100] ，此時(shí)程序會(huì)使用100字節(jié)靜態(tài)區(qū)一直保存數(shù)組buff。
感覺好像沒啥優(yōu)勢呢，靜態(tài)區(qū)和棧區(qū)都會(huì)消耗100字節(jié)。
如果現(xiàn)在有50個(gè)類似test的函數(shù)，每個(gè)函數(shù)中需要使用100字節(jié)，如果全部使用靜態(tài)變量，程序?qū)⑹褂?000字節(jié)靜態(tài)區(qū)。
如果函數(shù)不使用靜態(tài)變量，而是使用臨時(shí)變量，此時(shí)程序?qū)⑴R時(shí)占用最少100字節(jié)(50個(gè)函數(shù)不發(fā)生嵌套調(diào)用)，最大5000字節(jié)(50個(gè)函數(shù)全部嵌套)，事實(shí)上很難出現(xiàn)50個(gè)函數(shù)全部嵌套的情況，按照嵌套10層算只需要1000字節(jié)棧區(qū)即可滿足程序?qū)５南摹?/p>
因此在函數(shù)較多的情況下，棧區(qū)可以顯著減少數(shù)據(jù)存儲(chǔ)區(qū)消耗量!
5.2棧區(qū)的不可替代性
前文講了棧區(qū)可以顯著減少內(nèi)存消耗量，拿我們?cè)诓豢紤]內(nèi)存消耗的情況下，取消棧區(qū)只使用靜態(tài)區(qū)，這樣可以讓數(shù)據(jù)存儲(chǔ)器中的分區(qū)更單一，更方便管理，這樣可以嗎?
假設(shè)現(xiàn)在有如下函數(shù)：
/******************************************
* @作者 : liwei
* @Github : liyinuoman2017
*******************************************/
double factorial(double n)
{
double s;
if(n >= 2)
{
s = n*factorial( n - 1 );
}
else if(n ==1)
{
s = 1;
}
return s;
}
factorial是一個(gè)遞歸函數(shù)實(shí)現(xiàn)階乘功能，遞歸函數(shù)將調(diào)用自身。這樣情況下遞歸函數(shù)中的變量如果使用靜態(tài)變量將無法正常運(yùn)行，遞歸函數(shù)中的變量只能使用局部變量，局部變量存儲(chǔ)在棧區(qū)。
假設(shè)現(xiàn)在有如下代碼：
/******************************************
* @作者 : liwei
* @Github : liyinuoman2017
*******************************************/
void main(void)
{
...
sum();
}
int sum(int a , int b)
{
int c;
c = a + b;
return c;
}
/* 中斷函數(shù) */
void irq_handler(void)
{
...
sum();
}
假設(shè)main函數(shù)在調(diào)用sum函數(shù)期間，處理器產(chǎn)生了中斷，此時(shí)程序跳轉(zhuǎn)并執(zhí)行irq_handler函數(shù)，在irq_handler函數(shù)中也調(diào)用了sum函數(shù)，此時(shí)sum函數(shù)出現(xiàn)被重復(fù)調(diào)用兩次，sum函數(shù)中的變量也必須使用局部變量。不僅僅只有遞歸函數(shù)中的變量必須使用局部變量，在一些特殊使用場景下只能使用局部變量，此時(shí)體現(xiàn)了棧區(qū)的不可替代性。
綜上所述，使用棧區(qū)可以節(jié)省數(shù)據(jù)存儲(chǔ)空間，同時(shí)一些特殊使用場景只能使用棧區(qū)。
6.every coin has two sides
前文指出棧區(qū)的使用有不可替代性，同時(shí)可節(jié)省數(shù)據(jù)存儲(chǔ)空間。那么棧區(qū)使用是不是就是一種完美的方案呢?
every coin has two sides(每個(gè)硬幣都有兩面)
任何事物都有兩面性，有優(yōu)點(diǎn)就會(huì)有缺點(diǎn)。使用棧的缺點(diǎn)是：棧溢出!
相信大家都遇到過棧溢出的情況吧，棧溢出會(huì)讓程序產(chǎn)生表現(xiàn)形式多變的BUG，這類型的BUG通常讓人很難定位。
下圖展示了棧溢出的情況：
由圖可知當(dāng)棧溢出時(shí)，可能會(huì)錯(cuò)誤的修改靜態(tài)區(qū)的變量的數(shù)值，導(dǎo)致程序出現(xiàn)BUG。而且棧溢出后修改的靜態(tài)區(qū)的數(shù)值體現(xiàn)出隨機(jī)性，因此會(huì)讓程序產(chǎn)生表現(xiàn)形式多變的BUG。
既然棧溢出會(huì)造成嚴(yán)重BUG，那么有沒有方法來檢測棧溢出?
第一種方法是采用的做法是棧區(qū)初始化時(shí)，在棧的末端填充固定的標(biāo)記字符(比如0x5a5a5a5a)，如果發(fā)生了"棧溢出"，那么棧區(qū)末端填充的標(biāo)記字符則有可能會(huì)被更改。
這樣通過檢測棧區(qū)末端標(biāo)記字符是否被更改來判斷是否有"棧溢出"，這種檢測方法并不是100%有效的，是因?yàn)槟┒说臉?biāo)記字符有可能被跳過。
第二種方法是通過?；刂泛彤?dāng)前棧地址計(jì)算當(dāng)前棧的大小，?；刂窚p當(dāng)前棧地址即可求出棧的使用大小，若計(jì)算出的棧大小大于系統(tǒng)分配的棧大小則"棧溢出"。
當(dāng)前名稱：深入研究“?！保銓W(xué)會(huì)了嗎？
分享URL：http://www.5511xx.com/article/dpophds.html
