• 
    

    
    

      99热精品在线国产_美女午夜性视频免费_国产精品国产高清国产av_av欧美777_自拍偷自拍亚洲精品老妇_亚洲熟女精品中文字幕_www日本黄色视频网_国产精品野战在线观看

      ?

      Arduino安全遞歸調(diào)用

      2021-09-09 06:27:30樂萬德劉舟洲曹敬馨初建杰
      實(shí)驗(yàn)室研究與探索 2021年8期
      關(guān)鍵詞:那契盤子調(diào)用

      樂萬德, 劉舟洲, 曹敬馨, 初建杰

      (1.西安航空學(xué)院計(jì)算機(jī)學(xué)院,西安710077;2.西北工業(yè)大學(xué)工業(yè)設(shè)計(jì)與人機(jī)功效工信部重點(diǎn)實(shí)驗(yàn)室,西安710072)

      0 引 言

      作為一款便捷靈活的開源電子原型平臺(tái),Arduino得到了廣泛的應(yīng)用,比如汽車并線輔助系統(tǒng)[1]、智能防盜系統(tǒng)[2],制作機(jī)械書畫手臂[3]、智能盆栽養(yǎng)護(hù)瓶[4]等。Arduino在高校創(chuàng)新創(chuàng)業(yè)教育中也發(fā)揮著越來越重要的作用,不僅用于案例教學(xué)[5],參與競(jìng)賽活動(dòng)[6],還用于實(shí)驗(yàn)調(diào)試[7]、實(shí)驗(yàn)室管理[8]等,也有學(xué)者研究其生態(tài)擴(kuò)充[9]。

      遞歸算法在數(shù)學(xué)和計(jì)算機(jī)領(lǐng)域都占據(jù)著十分重要的地位。在計(jì)算機(jī)領(lǐng)域,遞歸函數(shù)由于邱奇-圖靈定理顯示出重要意義[10],邱奇-圖靈論題告訴我們一切可計(jì)算過程都可以用圖靈機(jī)模擬,1935年丘奇論題提出著名的“算法可計(jì)算函數(shù)都是遞歸函數(shù)”。同時(shí)遞歸函數(shù)是C語言等計(jì)算機(jī)編程中的一個(gè)重點(diǎn)和難點(diǎn),國內(nèi)外對(duì)于遞歸函數(shù)的教學(xué)進(jìn)行了廣泛的研究。Rinderknecht[11]在廣泛研究遞歸在編程語言中出現(xiàn)及被程序員采用的歷史之后,提出了遞歸的課程方法。文獻(xiàn)[12-14]中對(duì)C語言中遞歸函數(shù)的教學(xué)方法、教學(xué)設(shè)計(jì)、微課等教學(xué)形式進(jìn)行了探討。

      與某些單片機(jī)有限支持甚至不支持遞歸調(diào)用不同,Arduino支持遞歸調(diào)用。而前述文獻(xiàn)雖然分別對(duì)于Arduino與遞歸進(jìn)行了廣泛的研究,但Arduino內(nèi)存有限,遞歸算法在Arduio系統(tǒng)中棧溢出隱患問題鮮有研究。本文旨在探索Arduino安全遞歸調(diào)用,以期進(jìn)一步釋放Arduino應(yīng)用潛能。

      1 實(shí)驗(yàn)環(huán)境

      本文實(shí)驗(yàn)硬件為目前廣泛應(yīng)用的Arduino UNO R3。作為Arduino平臺(tái)的參考標(biāo)準(zhǔn)模板,UNO的處理器核心ATmega328,具有14路數(shù)字輸入/輸出口(其中6路可作為PWM輸出)、6路模擬輸入、SRAM 2 KB[15]。Arduino板通過USB與筆記本電腦相連。軟件開發(fā)平臺(tái)為Arduino IDE 1.8.9。

      2 問題引入

      在Arduino IDE輸入圖1所示代碼,編譯、下載到Arduino UNO后,在PC端打開串口監(jiān)視窗口。

      圖1 不安全的Arduino遞歸調(diào)用

      如圖1(a)所示,在串口監(jiān)視窗口可以看到,在Arduino UNO里用遞歸調(diào)用算法可以求出sum(1,2,…,500)的正確結(jié)果為125 250,沒有發(fā)生棧溢出。

      作為對(duì)比,把上面的代碼稍作修改,即把上面else分支中return n+sum(n-1)語句改為:

      unsigned long temp=sum(n-1);

      return n+temp;

      重新編譯、下載,在圖1(b)中串口監(jiān)視窗口中顯示異常,沒有得到期望的結(jié)果,顯然發(fā)生了遞歸棧溢出。

      由此可見,Arduino UNO在編譯時(shí)對(duì)遞歸調(diào)用在某些場(chǎng)景做了優(yōu)化,使遞歸調(diào)用??梢灾貜?fù)利用,從而避免棧溢出,但不是所有遞歸都進(jìn)行了優(yōu)化。因此,有必要對(duì)Arduino遞歸調(diào)用進(jìn)行研究,以便對(duì)Arduino進(jìn)行安全遞歸調(diào)用。

      3 安全遞歸實(shí)驗(yàn)設(shè)計(jì)

      安全遞歸調(diào)用要解決兩個(gè)基本問題,一是要設(shè)計(jì)出正確的遞歸算法;二是要防止遞歸調(diào)用棧溢出。

      3.1 遞歸算法

      遞歸算法具有兩個(gè)明顯的特點(diǎn):①一個(gè)更大規(guī)模的問題可以轉(zhuǎn)換成一個(gè)規(guī)模更小的同樣問題的求解,即問題的遞推性。②當(dāng)一個(gè)問題轉(zhuǎn)換到某個(gè)規(guī)模足夠小的問題時(shí)有確定的解,即問題的收斂性,也即遞推終止條件。

      以階乘為例,要求n!,可以把問題轉(zhuǎn)換成n*(n-1)!,即只需要求出(n-1)!這就是遞推關(guān)系,即特點(diǎn)一。遞推到足夠小比如1!為1是確定的,第2個(gè)特點(diǎn)即遞歸終止條件滿足。

      一旦識(shí)別出上述兩個(gè)特點(diǎn),不難編寫出遞歸程序,通常只需要將上述兩個(gè)條件映射為遞歸程序判斷結(jié)構(gòu)的兩個(gè)分支。

      3.2 遞歸棧溢出

      遞歸算法需要注意的第2個(gè)問題是遞歸棧溢出的問題,即本文研究的重點(diǎn)。遞歸調(diào)用本質(zhì)上是函數(shù)調(diào)用,涉及到函數(shù)參數(shù)及函數(shù)返回地址等壓棧。遞歸調(diào)用層數(shù)過多,棧地址與堆地址就會(huì)發(fā)生碰撞,也叫棧溢出。棧溢出會(huì)導(dǎo)致程序工作異常,需要避免。Arduino UNO的RAM內(nèi)存空間只有2 KB,在掌握遞歸算法的基礎(chǔ)上,更要關(guān)注遞歸棧溢出問題。

      3.3 實(shí)驗(yàn)原理

      3.3.1 AVR遞歸調(diào)用棧

      Arduino UNO采用AVR ATMega328作為芯片平臺(tái)。AVR芯片的SRAM存儲(chǔ)示意圖如圖2所示。主要包括靜態(tài)數(shù)據(jù)區(qū)、堆空間和棧空間。其中靜態(tài)數(shù)據(jù)區(qū)和堆空間占據(jù)著低地址空間,且自下而上生長。而棧空間占據(jù)著高地址空間,且自上而下生長,主要應(yīng)用于快速便捷地保存臨時(shí)數(shù)據(jù)、局部變量和中斷調(diào)用或子程序調(diào)用的返回地址。棧在系統(tǒng)程序的設(shè)計(jì)和運(yùn)行中起著非常重要的作用,只要程序中使用了中斷和子程序調(diào)用,就必須在SRAM空間建立棧空間,并正確地設(shè)置棧指針寄存器SP。

      圖2 Arduino SRAM中的存儲(chǔ)示意圖

      當(dāng)執(zhí)行PUSH指令,1 byte的數(shù)據(jù)被壓入棧,棧指針(SP中的數(shù)據(jù))將自動(dòng)減1;當(dāng)執(zhí)行子程序調(diào)用指令CALL或CPU響應(yīng)中斷時(shí),硬件會(huì)自動(dòng)把返回地址(16位數(shù)據(jù))壓入棧中,同時(shí)將棧指針自動(dòng)減2;反之,當(dāng)執(zhí)行POP指令,從棧頂部彈出1 byte的數(shù)據(jù),棧指針將自動(dòng)加1;當(dāng)執(zhí)行從子程序返回或從中斷返回指令時(shí),返回地址將從棧頂部彈出,棧指針自動(dòng)加2。

      由于AVR的棧是向下增長的,即新數(shù)據(jù)進(jìn)入棧時(shí)棧頂指針的數(shù)據(jù)將減小,所以隨著??臻g和堆空間的增長,剩余內(nèi)存會(huì)不斷減小,甚至內(nèi)存耗盡,發(fā)生棧溢出。

      3.3.2 安全遞歸調(diào)用算法

      如果在每次遞歸調(diào)用之前都能清楚地知道剩余內(nèi)存的情況和本次遞歸調(diào)用所需內(nèi)存,就可以有效防止內(nèi)存耗盡及棧溢出情況。關(guān)于Arduino剩余動(dòng)態(tài)內(nèi)存的查看,可參考文獻(xiàn)[16],本文采用圖3所示的算法來探測(cè)并規(guī)避遞歸調(diào)用棧溢出。

      圖3 Arduino剩余內(nèi)存探測(cè)

      圖3所示的算法實(shí)現(xiàn)為函數(shù),命名為availableMemory。在程序研發(fā)或者debug過程中,將availableMemory函數(shù)置于遞歸函數(shù)中,如果遞歸調(diào)用深度過深,內(nèi)存可能耗盡,availableMemory返回的內(nèi)存就會(huì)接近0。當(dāng)剩余內(nèi)存小于單次遞歸調(diào)用所需的內(nèi)存,則告警并記錄遞歸調(diào)用最大深度后安全返回。

      Arduino安全遞歸調(diào)用算法如圖4所示。在算法中設(shè)置一個(gè)遞歸調(diào)用狀態(tài)參數(shù)State,初始化State為1,表示遞歸狀態(tài)正常。每次遞歸調(diào)用時(shí)通過availableMemory計(jì)算剩余內(nèi)存,如果剩余內(nèi)存小于預(yù)設(shè)閾值,則將State變量設(shè)置為0,表示遞歸有棧溢出風(fēng)險(xiǎn),即遞歸狀態(tài)異常。每次遞歸調(diào)用時(shí)先查看State,只有當(dāng)State為1才進(jìn)行進(jìn)一步的包括遞歸調(diào)用在內(nèi)的后續(xù)操作,這樣就妥善處理了棧溢出異常。最小閾值M1可以設(shè)置為每次遞歸調(diào)用需要消耗的內(nèi)存。因?yàn)槊看芜f歸調(diào)用的壓棧過程都是從高地址向低地址順序壓棧的,對(duì)于單次遞歸調(diào)用所消耗的內(nèi)存M1,可以就兩次遞歸調(diào)用同一個(gè)變量的內(nèi)存地址相減得到。

      圖4 Arduino安全遞歸調(diào)用算法流程圖

      4 Arduino典型遞歸實(shí)驗(yàn)

      4.1 Arduino階加遞歸實(shí)驗(yàn)

      常見的入門遞歸實(shí)例是求階乘,隨著n的增加,階乘的結(jié)果迅速變大,容易造成存放其結(jié)果的數(shù)據(jù)類型越界。為了實(shí)驗(yàn)Arduino的遞歸支持能力,本文將乘改為加,設(shè)計(jì)了一個(gè)用遞歸算法實(shí)現(xiàn)從1~n求和的遞歸程序,稱之為階加。階加的遞推公式及終止條件如下:

      階加的遞歸調(diào)用算法與階乘的遞歸調(diào)用算法類似,以n=4為例,其遞歸調(diào)用棧入棧出棧如圖5所示。遞歸算法中,recSum(4)需要做函數(shù)調(diào)用,其參數(shù)及函數(shù)返回地址入棧,同理recSum(3)、recSum(2)、recSum(1)也需做遞歸調(diào)用并依次入棧,此時(shí)入棧全部結(jié)束,遞歸調(diào)用棧如圖5(a)所示。

      圖5 n為4時(shí)階加遞歸調(diào)用棧分析

      recSum(1)=1為遞歸終止條件,函數(shù)返回并出棧,此時(shí)recSum(2)=2+1也為已知,recSum(2)函數(shù)返回并出棧,同理recSum(3),recSum(4)依次返回并出棧,此時(shí)棧空間為空,如圖5(b)所示。

      由圖5可見,如果參數(shù)n足夠大,recSum(n)遞歸調(diào)用時(shí)可能發(fā)生棧溢出。此時(shí)應(yīng)該結(jié)束遞歸調(diào)用安全返回,并給出遞歸調(diào)用的最大深度提示。

      用本文安全遞歸調(diào)用算法運(yùn)行結(jié)果如圖6所示。圖6(a)是參數(shù)為300時(shí)程序運(yùn)行的部分結(jié)果,當(dāng)n逐層遞歸減到90時(shí),剩余內(nèi)存為15 bytes,本次遞歸調(diào)用后剩余內(nèi)存已經(jīng)不能繼續(xù)進(jìn)行本次遞歸調(diào)用了,給出錯(cuò)誤提示,并給出根據(jù)本次計(jì)算得到的最大遞歸深度為211。圖6(b)為按提示的最大遞歸深度211,計(jì)算1+2+…+211的結(jié)果為22 366,計(jì)算結(jié)果正確。

      圖6 階加Arduino安全遞歸調(diào)用運(yùn)行結(jié)果

      4.2 Arduino斐波那契數(shù)列遞歸實(shí)驗(yàn)

      斐波那契數(shù)列又稱黃金分割數(shù)列、兔子數(shù)列,由數(shù)學(xué)家萊昂納多·斐波那契(Leonardoda Fibonacci)提出,具有很多有趣的性質(zhì)和應(yīng)用。其遞推公式可由下式表示:

      與階加相比,斐波那契數(shù)列遞歸算法略顯復(fù)雜。主要的不同是,第n項(xiàng)的值不僅僅與第n-1項(xiàng)有關(guān),還與第n-2項(xiàng)有關(guān)。其遞歸調(diào)用棧的入棧、出棧的關(guān)系也更為復(fù)雜。以4項(xiàng)斐波那契為例,對(duì)應(yīng)式(2)的遞歸調(diào)用的出棧入棧如圖7所示,更多項(xiàng)數(shù)的出棧入棧關(guān)系類似。

      圖7(a)中為了求Fib(4),需要進(jìn)行遞歸調(diào)用,所以需要將參數(shù)n=4及其函數(shù)返回地址入棧,同理當(dāng)n=3,n=2時(shí)繼續(xù)遞歸調(diào)用并將對(duì)應(yīng)參數(shù)和函數(shù)返回地址壓棧,因?yàn)镕ib(2)=1為已知,可以直接返回,第1輪壓棧結(jié)束。圖7(b)中Fib(2)返回彈棧后Fib(3)=1+Fib(1),F(xiàn)ib(3)不能繼續(xù)彈棧,第1輪彈棧結(jié)束。圖7(c)、(d),圖7(e)、(f)分別進(jìn)行第2、第3輪入棧出棧,分析類似,不再贅述。

      圖7 n為4時(shí)斐波那契遞歸調(diào)用棧分析

      由圖7可以看出,如果參數(shù)n足夠大,在某輪入棧時(shí),可能發(fā)生棧溢出,此時(shí)應(yīng)該結(jié)束遞歸調(diào)用返回,并給出遞歸調(diào)用的最大深度提示。

      用本文安全遞歸調(diào)用算法運(yùn)行結(jié)果如圖8所示。圖8(a)是參數(shù)為300時(shí)程序運(yùn)行的部分結(jié)果,當(dāng)n逐層遞歸減到161時(shí),剩余內(nèi)存為23 bytes,本次遞歸調(diào)用后剩余內(nèi)存已經(jīng)不能繼續(xù)進(jìn)行本次遞歸調(diào)用了,給出錯(cuò)誤提示,并給出根據(jù)本次計(jì)算得到的最大遞歸深度為140。圖8(b)為按提示的最大遞歸深度140,遞歸調(diào)用正常。

      圖8 斐波那契Arduino安全遞歸調(diào)用運(yùn)行結(jié)果

      4.3 Arduino漢諾塔遞歸實(shí)驗(yàn)

      漢諾塔問題是遞歸算法處理的經(jīng)典問題。其問題可以描述為:初始狀態(tài)下A座上有n個(gè)盤子,盤子大小不等,大的在下,小的在上。要求把這n個(gè)盤子從A座移到C座,但規(guī)定每次只允許移動(dòng)一個(gè)盤,且在移動(dòng)過程中在3個(gè)座上都始終保持大盤在下,小盤在上。在移動(dòng)過程中可以利用B座。

      這是一個(gè)非數(shù)值解問題,也蘊(yùn)含著遞推關(guān)系,雖然不容易用遞推公式,但可用下面的流程圖來表達(dá)這種遞推關(guān)系。Hannoi(n,x,y,z)中n為盤子的數(shù)量,x、y、z為座子變量,取值可能為A、B、C座中的一個(gè)。表示將n個(gè)盤子從x座移動(dòng)到z座上,y座可以作為中轉(zhuǎn)。當(dāng)盤子的數(shù)量n>1時(shí),需要將n-1個(gè)盤子先從x座移到y(tǒng)座上(通過z座中轉(zhuǎn)),然后將x座上剩余的一個(gè)盤子移動(dòng)到z座上,最后將n-1個(gè)盤子從y座移到z座上(通過x座中轉(zhuǎn))。如果n=1,則滿足遞歸終止條件,直接將這1個(gè)盤子從x座移到z座上。

      由圖9可見,漢諾塔的遞歸調(diào)用從n階到n-1階的過程中具有兩次遞歸調(diào)用,因此其入棧出棧也比較復(fù)雜,以3個(gè)盤子的漢諾塔遞歸調(diào)用為例,分析其入棧出棧關(guān)系如圖10所示。更多項(xiàng)數(shù)的出棧入棧關(guān)系類似。

      圖9 漢諾塔遞歸調(diào)用算法

      圖10 n為3時(shí)漢諾塔遞歸調(diào)用棧分析

      用本文安全遞歸調(diào)用算法運(yùn)行結(jié)果如圖11所示。圖11(a)為參數(shù)為300時(shí)程序運(yùn)行的部分結(jié)果,當(dāng)n逐層遞歸減到148時(shí),剩余內(nèi)存為16 bytes,本次遞歸調(diào)用后剩余內(nèi)存已經(jīng)不能繼續(xù)進(jìn)行本次遞歸調(diào)用了,給出錯(cuò)誤提示,并給出根據(jù)本次計(jì)算得到的最大遞歸深度為153。圖11(b)為按提示的最大遞歸深度153,遞歸調(diào)用正常。

      圖11 漢諾塔Arduino安全遞歸調(diào)用運(yùn)行結(jié)果

      5 結(jié) 語

      為了防止遞歸調(diào)用棧溢出帶來的災(zāi)難性后果,本文為Arduino遞歸調(diào)用設(shè)計(jì)了防溢出的遞歸調(diào)用算法。無論是在簡(jiǎn)單階乘(階加)遞歸調(diào)用,還是在相對(duì)復(fù)雜的斐波那契數(shù)列、漢諾塔遞歸調(diào)用中,算法都穩(wěn)定可靠。在Arduino實(shí)踐中,為安全遞歸調(diào)用提供了保障,為Arduino創(chuàng)新應(yīng)用提供更豐富的手段。

      猜你喜歡
      那契盤子調(diào)用
      有趣的斐波那契數(shù)列
      放桃子
      核電項(xiàng)目物項(xiàng)調(diào)用管理的應(yīng)用研究
      LabWindows/CVI下基于ActiveX技術(shù)的Excel調(diào)用
      盤子中的童話故事
      從斐波那契數(shù)列的通項(xiàng)公式談起
      植物體上的斐波那契數(shù)列
      疑似斐波那契數(shù)列?
      基于系統(tǒng)調(diào)用的惡意軟件檢測(cè)技術(shù)研究
      “撕”掉的盤子
      襄城县| 临海市| 鄢陵县| 肇东市| 宁明县| 连城县| 普兰店市| 荔波县| 习水县| 肥乡县| 兴隆县| 莆田市| 沈丘县| 历史| 黔西县| 延吉市| 开平市| 杭州市| 天门市| 朝阳区| 乡宁县| 西乌珠穆沁旗| 丹凤县| 汪清县| 上思县| 阳城县| 新余市| 阳江市| 西乡县| 永城市| 鸡东县| 常熟市| 太白县| 铜陵市| 定陶县| 曲阳县| 阳新县| 峨眉山市| 凌源市| 云龙县| 屏边|