摘 要：為提高單片機(jī)通訊的實(shí)時(shí)性，采用了動(dòng)態(tài)的內(nèi)存管理方法，并將其應(yīng)用到AUTO 2000DCS系統(tǒng)中，獲得了滿意的效果。
關(guān)鍵詞：動(dòng)態(tài)分區(qū) 靜態(tài)分區(qū) 最先適應(yīng)法 內(nèi)存表
?
在AUTO 2000 DCS系統(tǒng)中，我們采用了單片機(jī)實(shí)時(shí)通訊網(wǎng)絡(luò).這是一種具有不確定控制站監(jiān)控的主從式總線網(wǎng)絡(luò).大致的工作過程是:網(wǎng)絡(luò)系統(tǒng)上電，各站點(diǎn)進(jìn)行控制權(quán)爭奪確立控制站和非控制站；控制站輪詢各站點(diǎn)，被輪詢的站點(diǎn)若有數(shù)據(jù)發(fā)送即成為主站，執(zhí)行主機(jī)/從機(jī)的通訊；通訊結(jié)束后(無論成功與否)主站將控制權(quán)歸還給控制站；控制站然后輪詢下一個(gè)站點(diǎn)，周而復(fù)始。
為了提高通訊效率，采取了一系列相應(yīng)的措施.例如，我們把站點(diǎn)集分為活動(dòng)站點(diǎn)集和非活動(dòng)站點(diǎn)集.這樣，單片機(jī)網(wǎng)中如有某站點(diǎn)出現(xiàn)故障，該站點(diǎn)被控制站詢問時(shí)響應(yīng)將超時(shí)，則該站點(diǎn)將從活動(dòng)站點(diǎn)集轉(zhuǎn)到非活動(dòng)站點(diǎn)集中.這樣，系統(tǒng)在下一次輪詢時(shí)就不再輪詢?cè)撜军c(diǎn).故障站點(diǎn)恢復(fù)正常后或有新的站點(diǎn)開機(jī)上線，控制站將在輪詢周期結(jié)束后的測(cè)試周期中將它們加入到活動(dòng)站點(diǎn)集中.事實(shí)上，控制站輪詢的是活動(dòng)站點(diǎn)，測(cè)試的是非活動(dòng)站點(diǎn).這無疑是一種提高網(wǎng)絡(luò)效率的方法。
另外還有一種更為重要的途徑即為本文將要介紹的動(dòng)態(tài)內(nèi)存管理方法。DCS網(wǎng)絡(luò)系統(tǒng)所要傳輸?shù)臄?shù)據(jù)一般有下述幾種：較長的周期性數(shù)據(jù)，較短的隨機(jī)上報(bào)數(shù)據(jù)及較短的命令/響應(yīng)數(shù)據(jù)。對(duì)周期性數(shù)據(jù)，稍微的滯后甚至一兩次丟失都是允許的；而對(duì)隨機(jī)上報(bào)數(shù)據(jù)和命令/響應(yīng)數(shù)據(jù)，則要求盡可能快地完成傳輸。在傳統(tǒng)的靜態(tài)內(nèi)存分配方式下，甲網(wǎng)卡接收到乙網(wǎng)卡的數(shù)據(jù)后在上傳至宿主機(jī)前宣布內(nèi)存緩沖區(qū)滿而不能接收其它站點(diǎn)的數(shù)據(jù)。這顯然是對(duì)內(nèi)存資源的一種浪費(fèi)，同時(shí)也嚴(yán)重影響了網(wǎng)絡(luò)的通訊效率。采用動(dòng)態(tài)內(nèi)存分配方式后，甲網(wǎng)卡每收到一批數(shù)據(jù)，只從自己有限的空閑內(nèi)存中分配出合適的一塊來存放該批數(shù)據(jù)，剩下的空閑內(nèi)存仍可接收其它網(wǎng)卡的數(shù)據(jù)，并當(dāng)宿主機(jī)有空時(shí)，將所有接收的數(shù)據(jù)一并上傳至宿主機(jī)并清空內(nèi)存。因此通訊效率大為提高。
1 內(nèi)存表結(jié)構(gòu)
為了對(duì)網(wǎng)卡上單片機(jī)內(nèi)存進(jìn)行管理，設(shè)置了一張內(nèi)存狀況表(簡稱內(nèi)存表)來記錄當(dāng)前內(nèi)存的使用情況。所謂內(nèi)存管理，實(shí)際上即為內(nèi)存的分配和回收，主要解決兩個(gè)問題：
(1) 對(duì)需要申請(qǐng)的內(nèi)存長度，分配程序需從內(nèi)存表中尋找出合適的空閑區(qū).分配給該批數(shù)據(jù)使用，并對(duì)內(nèi)存表進(jìn)行更新。
(2) 進(jìn)程或作業(yè)釋放內(nèi)存資源時(shí)，和相鄰的空閑區(qū)進(jìn)行鏈接合并，更新可用表。
具體地，以某一基本容量(視系統(tǒng)通訊的數(shù)據(jù)量而定，在此為1K)對(duì)可用內(nèi)存區(qū)域(如0400H ～ 3FFFH)進(jìn)行劃分和編號(hào)(1～15)，每一個(gè)實(shí)際的已分配內(nèi)存區(qū)和空閑內(nèi)存區(qū)在內(nèi)存表中占據(jù)一個(gè)表項(xiàng)位置，而每一表項(xiàng)結(jié)構(gòu)為：
這樣在某一時(shí)刻，可能有1～15個(gè)獨(dú)立的內(nèi)存區(qū)(空閑的或已分配的)。也就是說，可用內(nèi)存表表項(xiàng)的最大數(shù)目為15。但在某一時(shí)刻，卻可能只有1個(gè)區(qū)(如初始化后只有1個(gè)空閑內(nèi)存區(qū))。為了查找某時(shí)刻實(shí)際內(nèi)存的分配情況，我們?cè)O(shè)計(jì)了逆向搜索鏈，該鏈由內(nèi)存表項(xiàng)的后兩欄組成，如圖1所示。
該圖中，第15表項(xiàng)的結(jié)束塊號(hào)肯定為15，表示編號(hào)為15的內(nèi)存區(qū)域(3C00H～3FFFH)肯定是某個(gè)已分配區(qū)域(或空閑區(qū)域)的一部分。但該區(qū)域究竟有多大，要看第15表項(xiàng)的第3欄(塊數(shù))，設(shè)為5。這就表明其相鄰的上一區(qū)域的結(jié)束塊號(hào)為15減去5。然后查找內(nèi)存表的第10表項(xiàng) ，可知其大小為8。接下來查找第2表項(xiàng)，得到其分配塊大小為2。從而可得該時(shí)刻內(nèi)存中實(shí)際分配3個(gè)區(qū)，大小分別為5，8，2。至于內(nèi)存表中的其它表項(xiàng)在該時(shí)刻是無用的。 運(yùn)行初始化程序init_table后，內(nèi)存表的結(jié)構(gòu)如圖2所示。
其中，00C0H～00C2H和00F0H的地址用來存放表頭和表尾的標(biāo)志，內(nèi)存表的主要內(nèi)容有15項(xiàng)，每一項(xiàng)3個(gè)欄目，每一個(gè)欄目占用一個(gè)實(shí)際內(nèi)存單元.初始化后的0400H到3FFFH的15K內(nèi)存均為空閑，故從終止塊號(hào)15逆推15塊，1～15塊均為空閑塊，即內(nèi)存表中只有一個(gè)內(nèi)存區(qū).在內(nèi)存表的結(jié)構(gòu)圖中反映為表中主要內(nèi)容的第15項(xiàng)的標(biāo)志位為free, 內(nèi)存區(qū)的終止塊號(hào)為15，塊數(shù)為15，其它表項(xiàng)則是無用的。
2 內(nèi)存的分配
那么，如何利用這張內(nèi)存表進(jìn)行內(nèi)存分配呢？動(dòng)態(tài)分區(qū)分配方法采用最先適應(yīng)法。用一個(gè)例子來說明這個(gè)問題。例如經(jīng)過若干次分配和空閑區(qū)回收后，甲站點(diǎn)內(nèi)存表的主要情況如圖3所示(卡上還有一批數(shù)據(jù)未傳入宿主機(jī))。
在這種情況下，乙站點(diǎn)申請(qǐng)分配4塊內(nèi)存，則先把地址指針定位00EDH處(第15項(xiàng)的標(biāo)志欄處)，由于該項(xiàng)的標(biāo)志為free但大小不夠，故需向前查找.用該項(xiàng)的終止塊號(hào)(15)減去該項(xiàng)的塊數(shù)(1)得到數(shù)字14，故將地址指針定位到第14項(xiàng)處的標(biāo)志欄處，雖塊數(shù)大小夠但該內(nèi)存區(qū)為busy，故仍需往前找.此時(shí)用第14項(xiàng)處的終止塊號(hào)(14)減去該項(xiàng)的塊數(shù)(4)得到數(shù)字10，所以將地址指針定位到第10項(xiàng)的標(biāo)志欄處。第10項(xiàng)的塊數(shù)大于需分配的內(nèi)存塊數(shù)，故可以在此處分配.分配后的內(nèi)存表的主要情況如圖4所示。
在單片機(jī)的匯編程序中，動(dòng)態(tài)分配內(nèi)存是調(diào)用allocate子程序來完成的.具體步驟是這樣的：
(1)先由入口參數(shù)寄存器R3和R2(存放需要申請(qǐng)的內(nèi)存長度)折合成需分配的內(nèi)存塊數(shù)，并將其值傳遞給變量required_size。
(2)從內(nèi)存表末(00ED H處)自后向前找.即先把地址指針定位在00EDH處(第15項(xiàng)的標(biāo)志欄處)，如果該項(xiàng)的標(biāo)志不為free或該項(xiàng)的標(biāo)志為free但該項(xiàng)的內(nèi)存塊數(shù)小于需分配的內(nèi)存塊數(shù)，則用該項(xiàng)第二欄的數(shù)字(終止塊號(hào))減去該項(xiàng)第三欄的數(shù)字(塊數(shù))作為下一次向前查找的表項(xiàng)號(hào)，并由此定位下一次向前查找的地址指針.就這樣一直向前查找，直到找到不小于需分配的內(nèi)存塊數(shù)或已到內(nèi)存表頭.
(3) 如找到不少于申請(qǐng)塊數(shù)的空閑區(qū)，將空閑區(qū)的低端分配給該批數(shù)據(jù)使用，相應(yīng)地修改內(nèi)存表中的相關(guān)項(xiàng)，子程序返回分配成功標(biāo)志；否則，子程序返回分配不成功標(biāo)志。
3 內(nèi)存的釋放和合并
雖然我們成功地制定了內(nèi)存分配的算法和子程序，但是在內(nèi)存管理中還要處理空閑區(qū)的釋放和相鄰空閑區(qū)的合并。free_and_join子程序就是用來完成這個(gè)任務(wù)的.當(dāng)接收方(從機(jī))接收完發(fā)送方(主機(jī))發(fā)來的報(bào)文數(shù)據(jù)并將數(shù)據(jù)上傳給宿主機(jī)后，就需要在free_and_join子程序中釋放該報(bào)文數(shù)據(jù)在本機(jī)中所占的內(nèi)存(free)，并且需要檢測(cè)該被釋放的內(nèi)存與其相鄰的空閑內(nèi)存是否可以合并。如能，合并之.這樣，該機(jī)如接收其它主機(jī)發(fā)來的長的報(bào)文數(shù)據(jù)時(shí)，可以有足夠大的連續(xù)的空閑內(nèi)存來分配；同時(shí)，也保證了內(nèi)存操作的完備性.算法是這樣實(shí)現(xiàn)的：
(1)內(nèi)存表中被釋放項(xiàng)的標(biāo)志改為free。
(2)由于表項(xiàng)中的第二欄為終止塊號(hào)而非起始?jí)K號(hào)，且在內(nèi)存表中向前查找是沿著內(nèi)存表的地址減小的方向進(jìn)行的，故需先尋找上相鄰，再尋找下相鄰.
(3) 判斷上相鄰表項(xiàng)是否free；如果是，合并之。
用被釋放項(xiàng)的終止塊號(hào)r_block_end (R2)減去該項(xiàng)的塊數(shù)r_block_num (R3)，并將其值傳給R4，再調(diào)用block_to_address子程序來向前找上相鄰.如果該項(xiàng)處的標(biāo)志為free，則是上相鄰.取出上相鄰表項(xiàng)處的塊數(shù)，加到本表項(xiàng)(被釋放項(xiàng))的塊數(shù)R3上，并寫入本表項(xiàng)；并將上相鄰表項(xiàng)處的標(biāo)志置為03H(異于busy和free即可)。
(4) 判斷下相鄰表項(xiàng)是否free；如果是，合并之。
把地址指針定位00ED H處(內(nèi)存表尾)，從內(nèi)存表尾向前找.取出地址指針處的表項(xiàng)的終止塊號(hào)并存入R5，再取出該表項(xiàng)的塊數(shù)并存入R4.直到R5減去R4的結(jié)果等于被釋放項(xiàng)的終止塊號(hào)為止.若此時(shí)地址指針處的表項(xiàng)的標(biāo)志為free，則該表項(xiàng)是被釋放項(xiàng)的下相鄰.在下相鄰表項(xiàng)處，將該項(xiàng)的塊數(shù)加上被釋放項(xiàng)的塊數(shù)并存入；在被釋放項(xiàng)處將標(biāo)志置為03H(異于busy和free即可).
舉一個(gè)例子能更好地表明這種動(dòng)態(tài)分區(qū)的釋放和合并算法.例如將被釋放的內(nèi)存區(qū)在內(nèi)存表中是第6塊和第7塊.其上相鄰處內(nèi)存區(qū)為第3，4，5塊，且其標(biāo)志為free；其下相鄰處內(nèi)存區(qū)為第8，9，10塊，且其標(biāo)志為free；合并的過程如圖5所示。
總之，與固定分區(qū)法相比，動(dòng)態(tài)分區(qū)法在報(bào)文接收前不建立分區(qū).分區(qū)的建立是在報(bào)文接收的過程中進(jìn)行的，且其大小可隨報(bào)文長度動(dòng)態(tài)改變，這就改變了靜態(tài)分區(qū)法中的即使是小數(shù)據(jù)量也要占據(jù)大分區(qū)的浪費(fèi)堵塞現(xiàn)象，從而提高了內(nèi)存的利用率.另外，也提高了DCS系統(tǒng)網(wǎng)絡(luò)通訊的短數(shù)據(jù)的平均傳輸速率，更適應(yīng)DCS系統(tǒng)的實(shí)時(shí)性要求.
參考文獻(xiàn)
1王祥忠，龐國仲.具有不確定控制站的主從式總線網(wǎng)絡(luò)設(shè)計(jì).微計(jì)算機(jī)信息，1998(4)
2 張堯?qū)W， 史美林.計(jì)算機(jī)操作系統(tǒng)教程.北京：清華大學(xué)出版社。