时间片轮转算法在单片机程序设计中的应用

liyf

时间片轮转算法在单片机程序设计中的应用

摘要：提出一种采用时间片轮转算法改进单片机系统程序设计，实现多任务机制的软件设计方法，并给出了在MCS-51分级分布式系统中应用该算法进行程序设计的实例。
   关键词：时间片 多任务机制 单片机系统
传统的单任务编程思想对于明显的顺序控制要求编程简单、思路清晰、开发周期短；但对于任务较多、控制功能复杂的问题时，却难以满足要求。因此，有必要对传统的单任务设计思想进行改进。时间片轮转算法是实现多任务调度的一种常用算法。在这种算法中，系统将所有的任务按顺序排成一个队列，每次调度时把CPU分配给队首的任务，并令其执行一个时间片，构成微观上轮流运行、宏观上并执行的多任务效果。作者在基于单片机的分级分布式控制系统——程控对讲系统的用户控制器程序中引入多任务机制，采用时间片轮转算法极大地改善了程序结构，实现了对32个独立用户的有效控制。这种程序设计思想也可以到其它以单片机为核心的分级分布控制系统软件设计中。
1 系统组成
程控对讲系统是一个基于MCS-51的多级分布式系统，用户控制器是其中的一级，整个系统总体结构如图1所示。

    主控制器以单片机AT89C52为核心扩展非易失性存储器及其它功能器件，完成系统各用户对讲关系的编程和存储，并根据对讲关系对用户模块进行实时控制。用户控制器以单片机AT89C52为核心扩展用户机接口模块组成，每个用户控制器负责对其下一级的32个用户机进行管理与控制。
主控制器与用户控制器之间的信息交换采用主从方式的串行通信。主控制器对8个用户控制器轮流查询，各用户控制器只对与本模块相关的命令作出反应，用户控制器通过双绞线与用户机相连，以降低系统成本。用户机与用户控制器之间传输距离较远，最远可达8km。为保证在复杂的环境中正确传输数据，两者之间的通信采用DTMF编码。
2 任务的分配和时间片的划分
2.1 用户控制器子任务的确定
用户控制器需要实时管理32个独立的用户机，一方面实时接收用户机的呼叫信号进行处理后传送给主控制器；另一方面根据系统工作状况向用户机发送被呼叫信息。
用户控制器接收来自用户机的信号有两类。一类是DTMF编码信号，用于检测用户机是否需要呼叫其它用户机。用户机与控制器之间传送数据的位数是不等长的，每位DTMF编码数据的发送至少需要104ms，发送时间和空闲时间各占一半。另一类是话，DTMF编码信号和话音信号的复用可以降低系统的线路成本。

    在每次通信结束后，为使用户控制器能启动下一轮的DTMF编码数据的接收，用户机需要给用户控制器发送一个起始信号——挂机信号。用户机的工作电源直接从用户线路上提取，在话音和DTMF编码传送时用户线路有一定的工作电流（大于20mA），挂机信号使用户线路上电流接近于零（小于5mA），用户控制器检测用户线路上电路的这种变化后，进入新一轮的DTMF编码数据通信。挂机信号的持续时间为78ms。
用户控制器向用户机发送的只有DTMF编码数据，用于告诉用户机谁正在呼叫它。
要完成一个呼叫过程（即使通话时间为零），至少需要2×104ms（接收、发送DTMF编码时间）+78ms（挂机时间）=286ms；完成一个被呼叫过程也至少需要2×104ms=208ms。如果每个用户机的请求就不能实时作出响应。为解决这个问题，在用户控制器程序设计过程中引入多任务机制。为便于任务调度程序的调度，根据用户操作流程将用户机的操作细分为16个字操作，每个子操作构成个子任务，用户子任务分配表如表1所示。

表1 用户子任务分配表

子任务号	功   能	执行时间
0	等待接收	26×n
1	接收预处理	26
2	用户机查询	26×4
3	应答	26×4
4	接收第1位数据	26×4
5	接收第2位数据	26×4
6	接收第3位数据	26×4
7	等待上传	26×n
8	确认	26×n
9	响应	26×4
10	通话	26×n
11	挂机	26×2
12	发送预处理	26
13	发送第1位数据	26×4
14	发送第2位数据	26×4
15	发送第3位数据	26×4

2.2 时间片的划分
在时间片的轮转算法中，时间片的大小对系统性能有很大影响。如果时间片太大，大到每个任务都能在一个时间片内执行完毕，则时间片轮转算法便退化为FCFS算法。时间片的确定通常要考虑三个因素：任务的数目、系统对响应时间的要求、系统的处理能力。
本系统中用户控制器需要对32个用户机进行管理控制，应划分成32个时间片。在不同时刻每个用户机处于不同的工作状况，用户控制器需要执行不同的用户机任务，其处理时间也不相同。为缩短程序运行时间把，时间片设置为可变的，时间片的长短取决于各个用户机子任务的工作量。但用户控制器与用户机之间的通信时间要求很严，如DTMF的发送定时时间为104ms，包括52ms发送时间和52ms空闲时间，所以用户控制器必须在52ms内对每个用户机巡检一次，才能正确地接收用户机的编码数据。也就是说一个任务调度周期不应大于52ms。为满足用户机与控制器之间的通信对时间要求，对整个任务调度周期进行精确定时。
综合考虑本系统中与时间片划分相关的三种因素：单片机本身的运算速度、用户机数目及用户机与控制器之间信号的传送要求，确定任务调度周期为26ms。即在26ms内用户控制器对其下一级的32个用户机的任务都要执行一次。一般完成一个任务占用一个时间片，较长任务可以占用多个时间片，如14号子任务（发送第2位DTMF编码数据）需要占用4个时间片才能完成。
为实时掌握各用户机的运行状态，在用户控制器的存储器开辟出一个缓冲区为任务记录表，供任务调度程序使用。任务记录表中设置了三项内容：用户编号、子任务号及时间片数，如表2所示。

表2 任务记录表

用户编号	子任务号	时间片数
0～31	0～15	0～16

3 软件设计
3.1 任务调度程序的设计
根据上述分析，可以确定任务调度程序的功能：
（1）按用户机编号调用各用户子任务；
（2）完成一个调度周期的时间不超过26ms，并在每个周期结束时对26ms进行精确定时；
（3）在调度周期开始时，读取所有用户的DTMF编码和摘/挂机状态，供各用户子任务处理；
（4）在调度周期结束前，根据用户子任务处理结果向用户机发送DTMF编码。
调度程序的流程如图2所示。

    3.2 用户子任务的设计
用户子任务根据该用户缓冲区的数据进行处理，并把处理结果存放于结果单元。各个子任务并不与外部输入输出接口直接交换数据，对接口的输入输出由任务调度程序在调度周期开始和结束时调用专门子程序完成。用户子任务的切换工作根据操作流程在各子任务中完成。用户的操作被细分为16个子操作，相应地有16个子任务，图3为14号子任务的流程图。
在该子任务的开始（0ms）和中间（52ms）时刻设置DTMF数据发送缓冲区，分别允许和禁止DTMF编码的发送。在该子任务结束时根据该用户缓冲区内需发送的数据计算第2个的DTMF值，并修改任务记录表中该用户的调度数据，指向它的下一个子任务。其它子任务的设计思想与此子任务类似。
本文在单片机实时控制系统中引入了现代操作系统的多任务思想，采用时间片轮转调度算法对传统单片机编程思想进行了改进，并应用在基于MCS-51的分级分布式系统中，有效地完成了对32个独立用户的控制。实践证明这种结构清晰、调度灵活，适用于定时要求复杂、实时性要求强的系统。

李小路

谢谢分享！