实时单片机通讯网络中的内存管理

      摘要：为提高单片机通讯的实时性，采用了动态的内存管理方法，并将其应用到AUTO 2000DCS系统中，获得了满意的效果。

     关键词： 动态分区 静态分区 最先适应法 内存表

     在AUTO 2000 DCS系统中，我们采用了单片机实时通讯网络．这是一种具有不确定控制站监控的主从式总线网络．大致的工作过程是网络系统上电，各站点进行控制权争夺确立控制站和非控制站；控制站轮询各站点，被轮询的站点若有数据发送即成为主站，执行主机／从机的通讯；通讯结束后（无论成功与否）主站将控制权归还给控制站；控制站然后轮询下一个站点，周而复始。　

      为了提高通讯效率，采取了一系列相应的措施．例如，我们把站点集分为活动站点集和非活动站点集．这样，单片机网中如有某站点出现故障，该站点被控制站询问时响应将超时，则该站点将从活动站点集转到非活动站点集中．这样，系统在下一次轮询时就不再轮询该站点．故障站点恢复正常后或有新的站点开机上线，控制站将在轮询周期结束后的测试周期中将它们加入到活动站点集中．事实上，控制站轮询的是活动站点，测试的是非活动站点．这无疑是一种提高网络效率的方法。

      另外还有一种更为重要的途径即为本文将要介绍的动态内存管理方法。DCS网络系统所要传输的数据一般有下述几种：较长的周期性数据，较短的随机上报数据及较短的命令／响应数据。对周期性数据，稍微的滞后甚至一两次丢失都是允许的；而对随机上报数据和命令／响应数据，则要求尽可能快地完成传输。在传统的静态内存分配方式下，甲网卡接收到乙网卡的数据后在上传至宿主机前宣布内存缓冲区满而不能接收其它站点的数据。这显然是对内存资源的一种浪费，同时也严重影响了网络的通讯效率。采用动态内存分配方式后，甲网卡每收到一批数据，只从自己有限的空闲内存中分配出合适的一块来存放该批数据，剩下的空闲内存仍可接收其它网卡的数据，并当宿主机有空时，将所有接收的数据一并上传至宿主机并清空内存。因此通讯效率大为提高。

    １ 内存表结构

      为了对网卡上单片机内存进行管理，设置了一张内存状况表（简称内存表）来记录当前内存的使用情况。所谓内存管理，实际上即为内存的分配和回收，主要解决两个问题：

     (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所示。

     其中，00COH～00C2H和00F0H的地址用来存放表头和表尾的标志，内存表的主要内容有15项，每一项3个栏目，每一个栏目占用一个实际内存单元．初始化后的0400H到3FFFH的15K内存均为空闲，故从终止块号15逆推15块，1～15块均为空闲块，即内存表中只有一个内存区．在内存表的结构图中反映为表中主要内容的第15项的标志位为free 内存区的终止块号为15，块数为15，其它表项则是无用的。

    ２ 内存的分配

      那么，如何利用这张内存表进行内存分配呢？动态分区分配方法采用最先适应法。用一个例子来说明这个问题。例如经过若干次分配和空闲区回收后，甲站点内存表的主要情况如图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 Ｈ处）自后向前找．即先把地址指针定位在00EDＨ处（第15项的标志栏处），如果该项的标志不为free或该项的标志为free但该项的内存块数小于需分配的内存块数，则用该项第二栏的数字（终止块号）减去该项第三栏的数字（块数）作为下一次向前查找的表项号，并由此定位下一次向前查找的地址指针．就这样一直向前查找，直到找到不小于需分配的内存块数或已到内存表头．

     (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系统的实时性要求．

     参考文献　

    １王祥忠，庞国仲．具有不确定控制站的主从式总线网络设计．微计算机信息，1998   (4)

    ２ 张尧学， 史美林．计算机操作系统教程．北京：清华大学出版社。

  （收稿日期：1999-03-24）