程序级别划分与调度（第5卷）

4．2．2　程序的级别划分和调度

1．调度原则

交换机程序调度可分为静态调度和动态调度两种方式。静态调度是把处理机的时间等分为一组连续的时间片，操作系统在某一段时间内给系统中所有程序按其优先级分配若干块时间片。这种调度方法比较简单，但缺点是很难掌握合适的调度时机，处理机时间的使用效率低，不能很好地反映系统中各个任务的实时性。动态调度完全按各程序的优先级来进行，程序的优先权由操作系统中相关部分预先向调度程序登记（如排队或列表等），调度程序完全按登记的情况，根据优先级调度它们占用处理机。动态调度的优点是，调度能合理地反映各任务的实时性情况，处理机使用效率较高，但相比静态调度算法复杂一些。

2．程序的级别划分及任务

在任务调度过程中，根据程序的实时性要求将任务分为故障级、时钟级（或周期级）和基本级三级，如表4．1所示。

表4．1　程序级别的划分

（1）故障级程序的任务

负责故障的识别与处理，具有最高优先级，在发生故障时产生故障中断，立即调用故障处理程序。在故障级程序中根据故障的紧急情况，又进一步分成高、中、低三级：紧急处理（FH）级别最高，处理机故障（FM）级别次之，话路I/O子系统故障（FL）级别最低，它们分别完成紧急情况不同的故障处理任务。

（2）时钟级程序的任务

时钟级执行实时性要求严格的进程或其他要求定时执行的进程，如各种扫描程序都属于时钟级。比如时钟中断发生后，立即进入时钟级调度管理程序，确定本次时钟中断应调度哪些时钟级进程。时钟级进程的类型不同，周期也不同，例如，10 ms中断用来执行拨号脉冲扫描，即每隔10 ms启动一次拨号脉冲识别程序，扫描用户线上有无拨号脉冲；100 ms中断用于摘/挂机扫描，即每隔100 ms启动一次摘/挂机扫描程序，扫描用户是否挂机。根据实时性要求的不同，时钟级分为高、低两级：严格定时要求的处理级（H）及严格定时性稍次的处理级（L）。高级的时间要求更严格，如拨号脉冲扫描、信令发送和接收等；而控制话路和输入输出设备的进程等属于低级。时钟级的优先级别较故障级低，比基本级高。

故障级和时钟级都是在中断中执行的，为了确保时钟级程序的周期性执行，由外围设备时钟计数电路（如CTC芯片）向处理机发出定时中断的请求，称为时钟中断。时钟中断周期一般在4～10 ms之间。

（3）基本级程序的任务

基本级执行定时性要求不太严格的进程，基本级中的程序大部分没有周期性，而是按需执行，有任务就激活。可将需要执行的任务排队，如划分级别：基本级又划分为内部处理级BQ₁、内部处理级BQ₂、维护处理级BQ₃，每级有一个队列，同一级按先到来先服务的原则调度执行。基本级的任务实时性要求不高，可适当延迟执行，其优先级别最低。

正常情况下，只有时钟级和基本级交替执行。每当时钟中断到来时，就执行时钟级进程，执行完毕转入基本级的执行。

3．程序的调度和执行过程

（1）故障级程序的调度与处理

①故障级程序的调度

交换机在正常情况下，每次时钟中断到来后，先依次执行时钟级任务，然后执行基本级任务，如此循环下去。但是程控交换机在长期的运行中，总是会发生故障的，任何故障都将严重影响系统的服务质量，并且故障的发生是随机的，为了保证程控交换机能可靠地工作，要求能迅速对故障进行处理，因此故障级常采用不可屏蔽的中断方式激活处理程序。一般不通过操作系统调度，而由产生故障的资源直接向处理机发出不可屏蔽的中断请求，处理机在完整处理完一条指令后，马上响应该中断请求，进入故障处理级，这时正在执行的其他低优先级的程序将被中断执行，如图4．2所示。由图可见，每隔8 ms产生一次中断，在第一个8 ms中断周期内，处理机按时钟级、基本级的顺序执行任务，时钟级、基本级的任务执行完了以后，暂停并等待下一个中断的到来；第二个8 ms周期内，工作一切正常，还是先执行时钟级任务，然后执行基本级任务；第三个周期不到8 ms的时间，时钟级任务没有执行完就发生了故障，正在执行的任务很快被中断，程序转入故障处理级，进行故障的识别和处理。故障处理任务完成后，再返回执行时钟级任务。

图4．2　故障级程序的调度与处理

②故障级故障处理的过程

·故障的识别

各种设备中都配有故障诊断电路，以核对每次动作的结果。如果识别到不正常情况，一般通过故障中断报告给CPU，CPU通过故障处理程序中的故障识别和分析程序，可以大致分析发生了什么性质的故障和哪一个设备发生了故障。

·系统再组成

当故障识别程序发现有故障的设备后，立即将故障设备切换掉，换上备用设备。这种可重新组成能够正常工作的设备系列，称为系统再组成，它是由系统再组成程序执行的。

·恢复处理

故障发生后，进行故障处理并暂停呼叫处理工作。当系统再组成后应恢复正常的呼叫处理，由恢复处理程序来进行恢复处理。对于一般的故障中断，切断了故障设备并换上备用设备后，可以从呼叫处理程序的中断点恢复。

（2）时钟级程序的调度(www.xing528.com)

时钟级程序用于处理实时性要求较高并按一定周期执行的任务。时钟级程序通常用来发现外部事件，但不直接对事件进行处理，而是通过操作系统调度相关程序完成处理操作，即时钟中断发生后，进入时钟级调度管理程序，其任务是确定本次时钟中断应调度哪些时钟级进程，以满足各种时钟级进程的不同周期性要求。时钟级调度程序是由硬时钟中断方式启动的。在电路交换系统中，一般都设置一个系统时钟硬件定时器，它周期性的产生一个时钟中断，例如每隔4～10 ms产生一个脉冲，经处理机的中断接口激活中断服务程序。中断服务程序保护当前更低优先级程序的执行断点，然后按照时钟级程序任务调度表调度执行相关处理程序。当本时段的时钟级任务执行完以后，自动返回被中断的低优先级程序的断点继续执行。

①时钟级程序任务调度表的组成

时钟级程序任务调度表（时间表）如图4．3所示。它由4部分组成：时间计数器、有效指示器（屏蔽表）、时间表、程序入口地址表（转移表）。

②各部分的功能及工作过程

·任务调度表

任务调度表（时间表）纵向对应时间，每往下一行代表增加一个时间单位（时钟中断的周期是8～10 ms），时间表是一个执行任务的调度表，用来调度需要执行的程序。时间表横向代表所管理的程序类别，每一位代表一种程序，总位数即计算机字长，这里字长是16，故这一张时间表可容纳的程序类别数为16种。当时间表某行某位写入“1”时，表示该时钟周期可以执行列号所对应的程序；写入“0”时表示不执行该程序。例如，时间表中某列对应的每行都写入了“1”，表示该列所对应程序的执行周期为8 ms；隔1行写入了“1”的那一列所对应的程序的执行周期为16 ms；隔11（第12）行写入了“1”的那一列所对应的程序的执行周期为96 ms。因此，从时间表的各行所写入“1”的情况就可以看出各种程序的执行周期，但是否执行，还要受屏蔽表的附加控制。

图4．3　启动时钟级程序的时间表

时间表的工作过程是：首先从时间计数器中取值，每次时钟中断到来时，时间计数器加“1”。以时间计数器的值为指针，依次读取时间表的相应单元，将该单元的内容与屏蔽表的内容相“与”，再进行寻“1”操作。寻到“1”，则转向该位对应的程序的入口地址，执行该程序，执行完毕返回时间表再执行其他为“1”的相应程序。如不为“1”，则不执行。当所有单元寻“1”完毕，则转向低一级的程序。在最后一个单元的最后一位上，将时间计数器清零，以便在下一周期重新开始。

在调用过程中，后面程序的执行时刻取决于前面的程序是否被启动执行，因此，对运行间隔有严格要求的程序应排在比特表的最前边，而无严格要求的可相应排在后边（与是左寻“1”还是右寻“1”有关）。时间间隔应小于所有程序的最小执行间隔要求，而总的行数等于各程序执行周期与最短程序周期之比的最小公倍数。例如，一个时间表中除了时间计数器清零程序以外，共有3个时钟程序，它们的周期分别是8 ms、16 ms和96 ms，时钟中断周期为8 ms，那么时间表的最少行数应为12行（96 ms）。

由于各种程序的执行周期长短差异可能很大，而且对时间精确度的要求不同，故实际应用时可根据情况分设几种时间表。

·计数器

这是一个时钟级中断计数器。如果时钟级中断的周期是8 ms，计数器就按每8 ms中断并将其内容加“1”。计数器的数值用作时间表的行指针，计数器以时间表的行数为模进行循环计数。初值为“0”，每来一次周期中断就加“1”，当增加到时间表的总行数的最大值12（96 ms）时，计数器清零，返回到初始状态，重新开始计数。计数器的最大值为时间表的行数。

随着时间计数器不断地加“1”和清零，时间表就依次按单元地址号周而复始地调用执行各种程序。

·有效指示器

有效指示器（屏蔽表）表示对应比特位程序的有效性，屏蔽表可以提供对程序执行的附加控制，为“1”表示有效，为“0”表示无效。即在程序执行时，时间表中的内容要与屏蔽表中相应位内容进行逻辑“与”，若结果是“1”，则执行该程序；若结果是“0”，则不执行该程序。这样，时间表的内容可以不改变，只改变屏蔽表的内容就能控制程序是否执行。即很方便地对时间表中某些任务进行暂时删除（抑制执行）和恢复。例如，在时间表中第0列的每一行均写入了“1”，屏蔽表的第0位也写入了“1”，它们进行逻辑“与”得“1”，说明拨号脉冲识别程序8 ms调用（执行）一次；在时间表的第一列每一行均写入了“1”，但屏蔽表的第一位写入了“0”，它们进行逻辑“与”得“0”，说明测试用的拨号脉冲识别程序此时刻不执行（平时不用），只是在需要进行测试时才使用，依此类推。因此，时间表中每一行的各列写入l，只能确定对应程序的执行周期，但什么时候执行，还要结合屏蔽表的内容。

·转移表

转移表也称为程序入口地址表（任务地址表），每个单元分别记载着对应任务（程序）的入口地址。操作系统按照这个地址去调用相应的程序。

由时间表可见：拨号脉冲识别程序，启动周期为8 ms；测试用拨号脉冲识别程序，启动周期为8 ms；按键号码识别程序，启动周期为16 ms；位间隔识别程序，启动周期为96 ms；中继器扫描程序，启动周期为96 ms；用户群扫描程序，启动周期为96 ms；时间计数器清零，启动周期为96 ms。

从所要执行的程序看，最大周期为96 ms，故时间表有12个单元，即12行即可。工作过程可由时间表控制流程图4．4表示。

图4．4　时间表控制流程图

（3）基本级程序的调度

基本级中一部分程序具有周期性，可用时间表控制执行。而大部分处理任务没有周期性，可采用队列处理。同一级的处理要求可按到达的先后次序排成队列，采用先到来先处理的原则处理。

基本级中的队列就是各种事件登记表的队列。事件登记表是在发现处理要求的程序中登记的。例如，用户扫描发现用户呼出，就登记呼出事件登记表，包括应启动的程序地址、要求处理的内容和一些数据等。处理登记表构成先进先出的链形队列，或称为FIFO链。按照先进先处理的原则，依次取出每一张表进行处理。调度管理程序示意图见图4．5所示。这里采用的是分级调度和先进先出相结合的调度算法，仍以三级为例，调度程序按照Q₁、Q₂、Q₃这三个不同优先级别依次按顺序运行。当三个队列都为空时，处理机进入动态停机状态，等待新的任务或时钟中断。

图4．5　基本级调度管理程序框图

图中的链队由四张登记表组成，队首指针指第一张表的首地址（例如Q₁），每张登记表除各种数据以外，还有下一张表的首地址，故上一张表处理完毕可找到下一张表，依此类推，一直可找到最后一张表，其地址栏内写入“0”，表示链队到此为止。