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