基于FPGA的Cache替換算法控制器設(shè)計(jì)++

基于FPGA的Cache替換算法控制器設(shè)計(jì)狀態(tài)機(jī)的概念

狀態(tài)機(jī)是軟件編程中的一個(gè)重要概念。比這個(gè)概念更重要的是對(duì)它的靈活應(yīng)用。在一個(gè)思路清晰而且高效的程序中，必然有狀態(tài)機(jī)的身影浮現(xiàn)。比如說(shuō)一個(gè)按鍵命令解析程序，就可以被看做狀態(tài)機(jī)：本來(lái)在A狀態(tài)下，觸發(fā)一個(gè)按鍵后切換到了B狀態(tài)；再觸發(fā)另一個(gè)鍵后切換到C狀態(tài)，或者返回到A狀態(tài)。這就是最簡(jiǎn)單的按鍵狀態(tài)機(jī)例子。實(shí)際的按鍵解析程序會(huì)比這更復(fù)雜些，但這不影響我們對(duì)狀態(tài)機(jī)的認(rèn)識(shí)。進(jìn)一步看，擊鍵動(dòng)作本身也可以看做一個(gè)狀態(tài)機(jī)。一個(gè)細(xì)小的擊鍵動(dòng)作包含了：釋放、抖動(dòng)、閉合、抖動(dòng)和重新釋放等狀態(tài)。同樣，一個(gè)串行通信的時(shí)序（不管它是遵循何種協(xié)議，標(biāo)準(zhǔn)串口也好、I2C也好；也不管它是有線的、還是紅外的、無(wú)線的）也都可以看做由一系列有限的狀態(tài)構(gòu)成。顯示掃描程序也是狀態(tài)機(jī)；通信命令解析程序也是狀態(tài)機(jī)；甚至連繼電器的吸合/釋放控制、發(fā)光管（LED）的亮/滅控制又何嘗不是個(gè)狀態(tài)機(jī)。當(dāng)我們打開(kāi)思路，把狀態(tài)機(jī)作為一種思想導(dǎo)入到程序中去時(shí)，就會(huì)找到解決問(wèn)題的一條有效的捷徑。有時(shí)候用狀態(tài)機(jī)的思維去思考程序該干什么，比用控制流程的思維去思考，可能會(huì)更有效。這樣一來(lái)狀態(tài)機(jī)便有了更實(shí)際的功用。程序其實(shí)就是狀態(tài)機(jī)。也許你還不理解上面這句話。請(qǐng)想想看，計(jì)算機(jī)的大廈不就是建立在“0”和“1”兩個(gè)基本狀態(tài)的地基之上么？狀態(tài)機(jī)的要素

狀態(tài)機(jī)可歸納為4個(gè)要素，即現(xiàn)態(tài)、條件、動(dòng)作、次態(tài)。這樣的歸納，主要是出于對(duì)狀態(tài)機(jī)的內(nèi)在因果關(guān)系的考慮?！艾F(xiàn)態(tài)”和“條件”是因，“動(dòng)作”和“次態(tài)”是果。詳解如下：①現(xiàn)態(tài)：是指當(dāng)前所處的狀態(tài)。②條件：又稱為“事件”。當(dāng)一個(gè)條件被滿足，將會(huì)觸發(fā)一個(gè)動(dòng)作，或者執(zhí)行一次狀態(tài)的遷移。③動(dòng)作：條件滿足后執(zhí)行的動(dòng)作。動(dòng)作執(zhí)行完畢后，可以遷移到新的狀態(tài)，也可以仍舊保持原狀態(tài)。動(dòng)作不是必需的，當(dāng)條件滿足后，也可以不執(zhí)行任何動(dòng)作，直接遷移到新?tīng)顟B(tài)。④次態(tài)：條件滿足后要遷往的新?tīng)顟B(tài)。“次態(tài)”是相對(duì)于“現(xiàn)態(tài)”而言的，“次態(tài)”一旦被激活，就轉(zhuǎn)變成新的“現(xiàn)態(tài)”了。如果我們進(jìn)一步歸納，把“現(xiàn)態(tài)”和“次態(tài)”統(tǒng)一起來(lái)，而把“動(dòng)作”忽略（降格處理），則只剩下兩個(gè)最關(guān)鍵的要素，即：狀態(tài)、遷移條件。狀態(tài)機(jī)的表示方法有許多種，我們可以用文字、圖形或表格的形式來(lái)表示一個(gè)狀態(tài)機(jī)。純粹用文字描述是很低效的，所以就不介紹了。接下來(lái)先介紹圖形的方式。狀態(tài)遷移圖（STD）

狀態(tài)遷移圖（STD），是一種描述系統(tǒng)的狀態(tài)、以及相互轉(zhuǎn)化關(guān)系的圖形方式。狀態(tài)遷移圖的畫(huà)法有許多種，不過(guò)一般都大同小異。我們結(jié)合一個(gè)例子來(lái)說(shuō)明一下它的畫(huà)法，如圖1所示。圖1狀態(tài)遷移圖①狀態(tài)框：用方框表示狀態(tài)，包括所謂的“現(xiàn)態(tài)”和“次態(tài)”。②條件及遷移箭頭：用箭頭表示狀態(tài)遷移的方向，并在該箭頭上標(biāo)注觸發(fā)條件。③節(jié)點(diǎn)圓圈：當(dāng)多個(gè)箭頭指向一個(gè)狀態(tài)時(shí)，可以用節(jié)點(diǎn)符號(hào)（小圓圈）連接匯總。④動(dòng)作框：用橢圓框表示。⑤附加條件判斷框：用六角菱形框表示。狀態(tài)遷移圖和我們常見(jiàn)的流程圖相比有著本質(zhì)的區(qū)別，具體體現(xiàn)為：在流程圖中，箭頭代表了程序PC指針的跳轉(zhuǎn)；而在狀態(tài)遷移圖中，箭頭代表的是狀態(tài)的改變。我們會(huì)發(fā)現(xiàn)，這種狀態(tài)遷移圖比普通程序流程圖更簡(jiǎn)練、直觀、易懂。這正是我們需要達(dá)到的目的。狀態(tài)遷移表

除了狀態(tài)遷移圖，我們還可以用表格的形式來(lái)表示狀態(tài)之間的關(guān)系。這種表一般稱為狀態(tài)遷移表。表1就是前面介紹的那張狀態(tài)遷移圖的另一種描述形式。表1狀態(tài)遷移表①采用表格方式來(lái)描述狀態(tài)機(jī)，優(yōu)點(diǎn)是可容納更多的文字信息。例如，我們不但可以在狀態(tài)遷移表中描述狀態(tài)的遷移關(guān)系，還可以把每個(gè)狀態(tài)的特征描述也包含在內(nèi)。②如果表格內(nèi)容較多，過(guò)于臃腫不利于閱讀，我們也可以將狀態(tài)遷移表進(jìn)行拆分。經(jīng)過(guò)拆分后的表格根據(jù)其具體內(nèi)容，表格名稱也有所變化。③比如，我們可以把狀態(tài)特征和遷移關(guān)系分開(kāi)列表。被單獨(dú)拆分出來(lái)的描述狀態(tài)特征的表格，也可以稱為“狀態(tài)真值表”。這其中比較常見(jiàn)的就是把每個(gè)狀態(tài)的顯示內(nèi)容單獨(dú)列表。這種描述每個(gè)狀態(tài)顯示內(nèi)容的表稱之為“顯示真值表”。同樣，我們把單獨(dú)表述基于按鍵的狀態(tài)遷移表稱為“按鍵功能真值表”。另外，如果每一個(gè)狀態(tài)包含的信息量過(guò)多，我們也可以把每個(gè)狀態(tài)單獨(dú)列表。④由此可見(jiàn)，狀態(tài)遷移表作為狀態(tài)遷移圖的有益補(bǔ)充，它的表現(xiàn)形式是靈活的。⑤狀態(tài)遷移表優(yōu)點(diǎn)是信息涵蓋面大，缺點(diǎn)是視覺(jué)上不夠直觀，因此它并不能取代狀態(tài)遷移圖。比較理想的是將圖形和表格結(jié)合應(yīng)用。用圖形展現(xiàn)宏觀，用表格說(shuō)明細(xì)節(jié)。二者互為參照，相得益彰。用狀態(tài)機(jī)思路實(shí)現(xiàn)一個(gè)時(shí)鐘程序

接下來(lái)，我將就狀態(tài)機(jī)的應(yīng)用，結(jié)合流程圖、狀態(tài)遷移圖和狀態(tài)遷移，舉一個(gè)實(shí)際例子。下面這張圖是一個(gè)時(shí)鐘程序的狀態(tài)遷移圖，如圖2所示。圖2時(shí)鐘程序狀態(tài)遷移圖

把這張圖稍做歸納，就可以得到它的另一種表現(xiàn)形式——狀態(tài)遷移表，如表2所示。表2時(shí)鐘程序狀態(tài)遷移表狀態(tài)機(jī)應(yīng)用的注意事項(xiàng)

基于狀態(tài)機(jī)的程序調(diào)度機(jī)制，其應(yīng)用的難點(diǎn)并不在于對(duì)狀態(tài)機(jī)概念的理解，而在于對(duì)系統(tǒng)工作狀態(tài)的合理劃分。

初學(xué)者往往會(huì)把某個(gè)“程序動(dòng)作”當(dāng)作是一種“狀態(tài)”來(lái)處理。我稱之為“偽態(tài)”。那么如何區(qū)分“動(dòng)作”和“狀態(tài)”。本匠人的心得是看二者的本質(zhì)：“動(dòng)作”是不穩(wěn)定的，即使沒(méi)有條件的觸發(fā)，“動(dòng)作”一旦執(zhí)行完畢就結(jié)束了；而“狀態(tài)”是相對(duì)穩(wěn)定的，如果沒(méi)有外部條件的觸發(fā)，一個(gè)狀態(tài)會(huì)一直持續(xù)下去。

初學(xué)者的另一種比較致命的錯(cuò)誤，就是在狀態(tài)劃分時(shí)漏掉一些狀態(tài)。我稱之為“漏態(tài)”。

“偽態(tài)”和“漏態(tài)”這兩種錯(cuò)誤的存在，將會(huì)導(dǎo)致程序結(jié)構(gòu)的渙散。因此要特別小心避免。更復(fù)雜的狀態(tài)機(jī)

前面介紹的是一種簡(jiǎn)單的狀態(tài)結(jié)構(gòu)。它只有一級(jí)，并且只有一維，如圖3所示。圖3線性狀態(tài)機(jī)結(jié)構(gòu)

如果有必要，我們可以建立更復(fù)雜的狀態(tài)機(jī)模型。

1多級(jí)狀態(tài)結(jié)構(gòu)

狀態(tài)機(jī)可以是多級(jí)的。在分層的多級(jí)狀態(tài)機(jī)系統(tǒng)里面，一個(gè)“父狀態(tài)”下可以劃分多個(gè)“子狀態(tài)”，這些子狀態(tài)共同擁有上級(jí)父狀態(tài)的某些共性，同時(shí)又各自擁有自己的一些個(gè)性。

在某些狀態(tài)下，還可以進(jìn)一步劃分子狀態(tài)。比如，我們可以把前面的時(shí)鐘例子修改如下：

把所有和時(shí)鐘功能有關(guān)的狀態(tài)，合并成1個(gè)一級(jí)狀態(tài)。在這個(gè)狀態(tài)下，又可以劃分出3個(gè)二級(jí)子狀態(tài)，分別為顯示時(shí)間、設(shè)置小時(shí)、設(shè)置分鐘；

同樣，我們也可以把所有和鬧鐘功能有關(guān)的狀態(tài)，合并成1個(gè)一級(jí)狀態(tài)。在這個(gè)狀態(tài)下，再劃分出4個(gè)二級(jí)子狀態(tài)，分別為顯示鬧鐘、設(shè)置“時(shí)”、設(shè)置“分”、設(shè)置鳴叫時(shí)間。

我們需要用另一個(gè)狀態(tài)變量（寄存器）來(lái)表示這些子狀態(tài)。

子狀態(tài)下面當(dāng)然還可以有更低一級(jí)的孫狀態(tài)（子子孫孫無(wú)窮盡也），從而將整個(gè)狀態(tài)體系變成了樹(shù)狀多級(jí)狀態(tài)結(jié)構(gòu)，如圖4所示。圖4樹(shù)狀多級(jí)狀態(tài)結(jié)構(gòu)

2多維狀態(tài)結(jié)構(gòu)

狀態(tài)結(jié)構(gòu)也可以是多維的。從不同的角度對(duì)系統(tǒng)進(jìn)行狀態(tài)的劃分，這些狀態(tài)的某些特性是交叉的。比如，在按照按鍵和顯示劃分狀態(tài)的同時(shí)，又按照系統(tǒng)的工作進(jìn)程做出另一種狀態(tài)劃分。這兩種狀態(tài)劃分同時(shí)存在，相互交叉，從而構(gòu)成了二維的狀態(tài)結(jié)構(gòu)空間。

舉一個(gè)這方面的例子，如：空調(diào)遙控器，如圖5所示。圖5多維狀態(tài)機(jī)結(jié)構(gòu)

同樣，我們也可以構(gòu)建三維、四維甚至更多維的狀態(tài)結(jié)構(gòu)。每一維的狀態(tài)都需要用一個(gè)狀態(tài)變量（寄存器）來(lái)表示。

無(wú)論多級(jí)狀態(tài)結(jié)構(gòu)和多維狀態(tài)結(jié)構(gòu)看上去多么迷人，匠人的忠告是：我們依然要盡可能地簡(jiǎn)化狀態(tài)結(jié)構(gòu)，能用單級(jí)、單維的結(jié)構(gòu)