摘要：主要讨论常见的几种多任务实时性处理算法的优缺点，提出一种更能满足多任务实时性处理的算法——基于比特表的时间片算法。
这种算法主要是把常规的比特表中的任务按照时间片进行分配，以很好地完成实时性要求高且任务时间较长的任务，而不影响其它实时性要求更高的任务的完成。
关键词：比特表时间片实时处理引言在微机控制领域中，许多单片机应用系统是实时控制系统rtcs（real time control system）。
在实时控制系统中，为了很好地完成外界信息的实时测量、计算和相应的多种实时控制操作，必须达到两个设计目标；实时性和并行性。
即既要保证系统对外界信息以足够快的速度进行相应处理，又要同时完成多种任务操作。
在这里，多种任务之间的调度是个关键。
rtcs中允许多个实时任务并行地运行。
例如，一测控系统中，具有数据采集、数据计算、键盘处理、定时打印等任务。
在单机系统中，这些任务在宏观上是同时运行的，但在微观上只有一个任务运行。
在rtcs 中每个任务有三种状态，即运行状态、就绪状态和空闲状态。
某个任务一旦建立后即处于这三种状态之一。
处于运行状态的任务独占cpu和其它一些资源；就绪状态是某个任务现在应该运行，但由于其它任务正在运行，故只能暂时等待；当激发某个任务的条件不完备时，此任务就处于空闲状态。
rtcs中的多个任务依靠任务调度程序来决定系统中哪个任务可以获得cpu等资源或应暂时退出运行状态等，从而完成每个任务三态间的转换。
在rtcs中，任务调度算法的优劣直接关系到系统的实时性能与并行性能。
rtcs中较简单的任务调度算法有“先来先执行的调度算法”、“按时间片循环执行的调度算法”。
前者，当实时性比较差的任务长时间占用cpu时，会使得实时性较高的任务得不到及时处理，影响系统的实时性；后者，按照“先入先出”的原则激活某个任务，并分配给它们相等的时间片，从而使得多个任务有平等的享用cpu的权利。
当时间片用完时，让任务“暂时”又处于就绪状态，并激活下一个任务。
这种算法的实时性有一定程序的提高，但由于各任务简单均匀地循环轮回，从而使得实时性要求较高的任务得不到优先处理。
由于各时间片相等且固定，很容易被某些紧急任务打断。
在实时性要求较高而且任务较多的复杂情况下，各个任务的实时性要求不尽相同，不能简单地均匀分时处理任务。
基于比特表的任务调度算法，关键在于将cpu的全部时间化成若干个相等的时隙，同时根据任务的数目制定一张表格，以此来指示某一时刻的任务运行。
它把任务按照实时性要求分成中断级、时钟级、基本级三类，而且它们的优先级依次递减。
优先级越高，就越处于比特表的顶端位置。
比特表是按照任务的优先级排队的，首先满足实时性较强的中断级和时钟级，而不管实时性最低的基本级任务。
这样，时钟级任务一定能得到即时有效的处理，其实时性可以得到较好的保障，基本级任务可以没有时间限制。
但是，时钟级任务的实时性并不是完全能够得到保障。
下面举例讨论比特表算法的不足之处。
图2 任务的启动顺序和运行时间
假定有表1所示的五种任务，按照常规比特表算法根本无法设计出这样的比特表。
当时钟级的各级每次运行时间之和没有达到5ms时，比特表算法能够很好地满足系统实时性要求；然而，当中断级和时钟级的每次运行时间之和大于或者等于最高级实时性要求，更有甚者，当有一个时钟级任务的运行时间超过最高级实时性要求时，比特表算法就会失效。
因为常规的比特表算法要求，只要激活比特表中安排的中断级和时钟级任务就必须一次执行完，否则，如果这个任务被中断就无法再得到执行。
由于图像处理的运行时间为5ms，加上中断级任务执行时间，因此设计时隙必须大于5ms；而比特表的设计方法时隙只可能小于等于5ms （中断级任务和实时性最高的时钟级任务决定的）。
所以，无论安排怎样的比徨表都无法使任务d满足实时性要求。
基于这两种情况，本文提出一种用赋有优先权的时间来填充比特表的算法，以改善这两种情况。
2 程序设计值得注意的问题在任务调度算法中，关键是如何确定就绪队列、任务控制数据块的数据结构和解决资源冲突。
就绪队列指明了在某一时刻已就绪、可被执行的任务队列。
在
数据结构上通常可用位映像的方法来实现。
如系统的最多任务为32个，可采用4个字节的每一位来对应人某个任务。
若此位为“1”，则表明该任务就绪；若为“0”，则表明任务空闲。
并且可规定低位所代表的任务优先级高于高位所指示的任务。
某个任务投入运行时需保护现场数据，这些数据都存入一个地址固定的数据存储区，称为任务控制数据块。
需保护的内容应按应用程序的特点来决定。
对于常用的mcs51系列的单片机来说，现场保护数据一般应包括pc、acc、psw、sp、dptr等寄存器内容。
任务控制数据块一般放在外部数据存储器内。
为了查找方便，可以按任务号将各个任务数据块的首地址编成一个一维表格，表格的每行对应各任务数据块数据结构首地址，如图3所示。
在任务调度程序中，还应很好地解决资源的互斥问题，即保证不可共享的资源只被一个任务所访问。
在rtcs中，各任务间并非完全隔绝，它们相互合作、相互竞争。
例如，某系统中数据显示任务要定时显示某数据区的数据；数据计算任务也要在某种情况下计算、刷新此数据区内容。
在这里，数据计算任务在运行时就不允许让显示任务中断计算任务；否则，有可能导致显示的数据不正确。
解决资源竞争的方法往往是在主程序中设置一标志字节或标志位。
例如，显示任务在运行时首先判断此标志，若发现计算任务尚未完成，则不做任何工作直接退出任务。
3 小结rtcs中的实时性和并行性是非常重要的，但两者之间有一定的矛盾。
完全实现在两大特性的重要手段就是，采用有效的任务调度算法程序来协调两者之间的矛盾，从而保证系统的实时性和并行性。
在简单系统中，“按时间片循环”调度算法已能初步满足要求；但在较复杂和要求较高的系统中，这显然不满足需要。
基于bitmap的调度算法能较好地满足比较复杂系统的要求，而对于前面讲到的系统中要求执行时间长、实时性要求较高的任务而言，单纯的bitmap算法无法满足要求，这个时候我们提出将比特表的时隙细分成时间片进行分配，这比bitmap按照任务进行分配的算法更能解决复杂任务的实时性要求。
只要有效地确定任务数目和数据结构，rtcs中的实时性和并行性就能得到有效提高。
