车辆移动监控系统并发调度机制的研究

　　在车辆移动监控系统运行过程中，监控中心会同时接收到从不同车载终端发送过来的大量信息，这些信息分别对应着不同的事件。监控中心如何同时响应这些信息，并及时对这些信息所代表的事件做出正确处理是整个车辆移动监控系统中最为重要的部分和首要解决的问题。

　　二、监控系统的并发特性分析

　　车辆移动监控系统是一种典型的具有并发特性的系统。在监控系统运行过程中，同一时间内监控中心要并发处理多个车载终端发送过来的事件信息。与此同时，当一个车载终端正在与监控中心协作处理某事件时又可能发生新的事件。所以车辆移动监控系统存在着两个或多个事件并发的情况，系统需要拥有同时处理多个事件并发的能力，即并发处理机制。当多个事件并发时，系统依据并发处理机制在多个事件处理上反复切换[1]，直至所有事件全都处理完毕为止。

　　从车辆移动监控系统的分析可以得出其并发处理机制有以下2个特点。

　　不同的事件具有不同的紧急程度不同事件的紧急程度相差很大，系统必须具有区分事件紧急程度的能力，针对事件的不同紧急程度采取相应的调度机制和处理策略。

　　对事件的并发处理有一定的实时性要求能否满足事件处理的实时性要求对于事件的处理来说是至关重要的，不能在其规定的时间内完成处理，则对该事件的处理将失去意义。

　　监控中心如不能满足以上两点要求，则会造成整个车辆移动监控系统性能下降，甚至会引发严重后果。因此，监控中心采用何种并发调度机制对整个车辆移动监控系统的性能有着很大的影响。

　　三、监控中心并发调度算法的研究

　　（一）优先数事件队列调度算法

　　并发处理机制有多种方法可以实现，其中常用的有先来先服务，短作业优先，按优先级别高低排序，响应比排序等方法[2-5]。针对监控中心并发处理的性能要求分析，文中提出采用优先数事件队列算法来实现车辆监控中心的并发调度机制。

　　优先数事件队列调度算法给每个事件赋予一定的优先数，并对在同一优先级队列中的事件按一定算法进行排序以确保每个事件都能满足其实时裕度的要求。各事件队列之间采用可剥夺的方式实现并发处理，只有当高优先数的队列中事件处理完毕后才会处理低优先数事件队列中的事件。当有比目前处理的队列优先数更高的事件发生后，系统立刻将当前处理的事件挂起，转向处理更高优先数的事件。

　　因此，当事件发生时通过优先数的赋值，高优先数的事件会得到尽快处理。同时在队列内部实现按实时裕度排列事件方式，充分考虑事件处理所需的实时性要求。优先数事件队列调度算法如下。

　　首先默认当前处理的事件一定是优先数最高的队列中的事件。当一个新事件发生后，调度系统首先根据事件的类型赋予其一优先数，然后判断新事件优先数是否高于当前处理事件优先数，如是，则将当前处理事件挂起，系统转向处理新事件；如否，则根据新事件优先数决定其将要插入的事件队列；接着根据新事件的实时裕度决定其在预插入事件队列的位置，如果预插入的位置不能满足其实时时限的要求，则需要对事件队列中的事件作相应处理，以满足其实时性的要求。

　　（二）优先数事件队列的性质分析

　　实际工作中系统的资源是有限的，因而系统所能并发处理的事件也是有限的。在设计系统之前，有必要综合考虑系统在实际运用时需要处理的不同优先级别事件的极限，同时系统资源还要留有一定的裕度，用来作为系统资源设计的参考。

　　优先数事件队列具有如下性质。

　　性质1设事件的实时时限为K，处理事件所需时间为T，事件等待处理时间为W，则该事件的实时裕度为E=K-T-W；当某事件发生的一刻，W=0，其实时裕度E=K-T，称该实时裕度为该事件的初始裕度。

　　性质2设在某一时刻，优先数事件队列中存在一个事件P，按优先数事件队列调度算法共有N个事件在其前得到系统处理，这N个事件中每个事件所需处理时间为T（i）。那么P事件的实时时限可满足的充分条件为:EP≥∑T（i）。

　　性质3设在优先数事件队列中所有排列在第r个队列的事件最小初始裕度为E0，则前r-1个队列中所有待处理事件的总需要处理时间不能大于E0。

　　第r个队列的事件的优先数低于前r-1个队列中所有事件的优先数，其要在前r-1个队列中所有事件处理完之后才能得到响应，若当前r-1队列中待处理事件的总需要处理时间大于E0，显然第r个队列中最小初始裕度为E0的事件的实时时限无法得到满足。

　　性质4当一个事件发生时，可以将其插入该事件属于的优先数事件队列充分条件为:该事件的实时时限满足性质2要求；按优先数调度机制排在该事件后等待调度处理的事件的实时时限满足性质2要求；设队列r是当前时刻所有非空队列中优先数最低的队列，队列s是比队列r优先数低的所有空队列中优先数最高的队列。那么在当前优先数事件队列中插入该事件后，所有事件总需要处理时间不能大于E0，E0为所有可能排列在队列s中事件的最小初始裕度。

　　其中性质4的前两点可由性质2得到，第三点可由性质3得到。

　　（三）优先数事件队列的事件插入算法

　　当插入一个事件时，首先根据优先数确定其应插入的队列，再由其实时裕度确定其在队列中的插入位置，并检查该位置能否满足其实时性要求。当一个新的事件发生时，如果其不能满足性质4的要求，则不能将其插入队列之中。此时必须要对该事件或者对其预插入的队列中的其它事件进行调整，以使得队列中所有事件满足实时时限的要求。根据以上描述，提出如下插入新事件的算法。

　　确定新发生事件的优先数。

　　确定将该事件预插入的优先数事件队列。

　　确定该事件在优先数事件队列中预插入的位置。

　　实行该事件的预插入。

　　对预插入后的优先数事件队列中所有排在其后调度的事件进行实时时限检测，以确定预插入后的优先数事件队列能否满足它们的实时性要求，若不能，则该事件不能插入，返回不能插入该事件标志，退出。

　　对在性质4中所设的队列s的最小初始裕度进行检测，若不能满足，则该事件不能插入，返回不能插入该事件标志，退出。

　　若以上两步检测都可以完成，则在预插入的优先数事件队列插入该事件。

　　在插入新事件算法中需要在第3步确定新事件在队列中的预插入位置，对于该位置应满足两个要求:一是满足其实时时限要求，二是尽可能地提高系统处理时间的利用率。因此文中提出以下确定事件预插入位置算法。

　　将该事件插入预插入队列的第二位。

　　检测该位置是否满足其实时性要求。

　　若该位置满足，则将其插入下一位，返回第二步，若不满足则转到下一步。

　　取当前位置的前一位置作为预插入位置。

　　由于每插入一个新事件时，都要进行插入算法的第6步。所以当待插入事件的事件队列为空队列时，一定可以将新事件插入。如不为空队列，那么至少可以将新事件插入在队列头。另一方面，当插入事件的事件队列已有事件时，那么经过事件插入算法的第5步的检验，新事件及排在其后调度的事件的实时性必然都能得到满足，否则该事件不能插入，也就不存在插入位置的确定问题。

　　综合上述两点可知，采用预插入位置算法所得的预插入位置一定满足新事件的实时时限的要求。另外，由于插入位置是从队列头起逐步往后推，直至新事件的实时性不能满足为止，所以对于最终所得到的插入位置，系统处理时间的利用效率最高。

　　四、结束语

　　对车辆监控系统的并发特性进行了分析，在此基础上提出了优先数事件队列算法来解决车辆监控中心的并发调度问题。该算法具有易于实现、效率高等特点。由于车辆监控系统的并发处理机制具有相当的代表性，因此该算法也可应用于其它具有并发特性的系统中。