使用PV操作解决列车调度问题的改进算法-2024年文档

使用PV操作解决列车调度问题的改进算法

1 引言

在多道程序设计的系统中,当处理器的数量少于进程的数量时,多个进程就会轮流使用处理器,即一个进程的工作没有全部完成之前,另一个进程就开始工作。如果并发执行的多个进程共享了相同的资源,而进程的调度又不加以控制,则不同的调度次序将会产生不同的结果,即系统会发生“与时间有关的错误”[1]。

荷兰学者Dijkstra发明的信号量机制是一种卓有成效的进程同步工具,它通过P、V两个操作原语来保证进程之间的同步与互斥,进而可以避免产生与时间有关的错误[2]。信号量机制虽然能避免产生与时间有关的错误,但在使用时,如果考虑不严密则会使系统效率大大降低,或者出现进程长时间得不到服务的“饿死”现象。笔者结合列车调度问题,分析传统解决方法的不足,并给出了既能提高效率,又能防止进程“饿死”的改进算法。 2 列车调度问题的描述

如图1所示,假设A、B两个火车站之间是单轨连接的,现有许多列车需经过A站开往B站,也有许多列车需经过B站开往A站,为确保行驶安全,必须保证在同一时刻两站之间不能有相对行驶的列车,即当有列车从某一车站开往另一个车站时,从另一个车站开往本站的列车只能等待,当有两列列车分别从两个车站

出发相对行驶时,系统就发生了与时间有关的错误。 3 传统的解决方法及存在的问题

解决列车调度问题的最简单的方法是使用P、V操作。将每列列车看作是一个进程,将两个车站之间的单轨铁路看作是共享资源,设置一个互斥信号量Mutex,其初值为1,用于对共享资源的互斥访问。多个进程并发执行的P、V操作算法如下: 经过A站开往B站的列车: 经过B站开往A站的列车: processPAi processPBi beginbegin …………

P(Mutex); P(Mutex);

经过A站到达B站;经过B站到达A站; V(Mutex); V(Mutex); ………… endend

上述算法虽然避免了与时间有关的错误,但要求同一时刻在两站之间只能有一列列车行驶,在这种情况下,系统的效率将大大降低。事实上,当某列列车从一个车站开往另一个车站时,同方向的列车也可以依次(但不可以同时出站)跟在后面同向行驶。因此,只需要某一方向的第一列列车申请共享资源的信号量Mutex即可,其它同向行驶的列车不必申请共享资源信号量,当同一方

向的所有列车均通过后再释放共享资源信号量Mutex。 4 提高效率的算法

对上面的算法加以改进。设置2个变量count1、count2分别对两边的列车进行计数,其初值均为0。由于每列列车均使用变量count1或count2,因此,设置信号量S1、S2分别用于对变量count1、count2的互斥访问,其初值均为1,信号量S1和S2可以防止同一方向有两列列车同时出站行驶。为安全起见,设置两列列车从同一车站驶出的时间间隔不低于十分钟,即每列列车在出站十分钟后再释放可以唤醒下列列车的信号量S1或S2。改进后的P、V操作算法如下: 经过A站开往B站的列车: 经过B站开往A站的列车: processPAi processPBi begin begin ………… P(S1); P (S2);

count1=count1+1;count2=count2+1;

if count1=1 then P(Mutex);if count2=1 then P(Mutex); 从A站开出; 从B站开出;