基于带抑制弧的Petri网的min-min算法模型研究

Research on min-min algorithm model based on Petri net model with inhibitor arcs

为了解决已有的min-min算法Petri网模型不能模拟min-min算法运行过程的问题,根据min-min算法的调度特点,利用带抑制弧的Petri网提出了一种算法模型,该模型运行过程可以严格模拟min-min算法对独立任务集的调度顺序,能够正确地描述独立任务调度系统使用min-min算法的情况。最后对该模型的空间复杂度以及每调度一个任务模型的变化情况进行了分析,随着独立任务的调度执行,该基于带抑制弧的Petri网的变迁数和弧数会随之减少,模型的空间复杂度会不断降低。

Aiming at solving the problem that the existing Petri net models of min-min algorithm couldn＇ t simulate its running process, this paper presented a modeling method based on Petri net with inhibitor arcs. Then, demonstrated that the execution of this model could simulate the scheduling order for independent task sets strictly, and this model was suitable to describe the application of min-min algorithm on scheduling the independent tasks. Finally, analyzed its space complexity and its changing style with each task being scheduled. The result shows that the numbers of both transitions and arcs in this Petri net with inhi- bitor arcs will decrease with the scheduling and execution of independent tasks, furthermore, the space complexity decreases continually.