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

于占虎

[摘 要]以进程的同步与互斥中的列车调度问题为例,分析了传统的解决方法及存在的问题,提出了一种高效的、防止“饿死”的改进算法。

[关键词]进程 P、V操作 信号量 饿死

[中图分类号]R-05[文献标识码]A[文章编号]1007-9416(2009)12-0108-02

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站开出;

十分钟后;

十分钟后;

V(S1); V(S2);

…… ……

到达B站;

到达A站;

P(S1);

P(S2);

count1=count1-1;

Count2=count2-1;

if count1=0 then V(Mutex);if count2=0 then V(Mutex);

V(S1);V(S2);

…… ……

end end

改进的算法可以充分的利用系统资源,提高了系统的效率,但又出现了新的问题:当某一方向上有列车行驶时,在这个方向上其它的列车也可以依次跟在后面行驶,如果这个方向上源源不断的有列车驶出时,对面方向上的列车将长时间处于等待状态而不能驶出,此现象叫做进程的“饿死”。

5 防止“饿死”的改进算法

为了解决进程的“饿死”现象,体现公平性原则,对算法做进一步改进:当某一方向的多列列车连续通过时,如果对面方向有列车等待通过,则本方向上后到的列车将被阻塞。按照这一原则,可以在算法中增加一个信号量P,其初值为1,每列列车在通过之前,都需先争夺信号量P,这样,系统按照申请信号量S的顺序进行调度,这样可以阻止对面后来的列车的通过机会,从而消除“饿死”现象。消除“饿死”现象的P、V操作算法如下:

经过A站开往B站的列车:

经过B站开往A站的列车:

processPAi

processPBi

begin begin

…… ……

P(S); P(S);

P(S1);P(S2);

count1=count1+1;

count2=count2+1;

if count1=1 then P(Mutex);

if count2=1 then P(Mutex);

从A站开出; 从B站开出;

V(S); V(S);

十分钟后;十分钟后;

V(S1);V(S2);

…………

到达B站; 到达A站;

P(S1); P(S2);

count1=count1-1;

Count2=count2-1;

if count1=0 then V(Mutex);

if count2=0 then V(Mutex);

V(S1); V(S2);

…………

end end

6 结语

P、V操作可以实现进程的同步和共享资源的互斥使用,避免产生“与时间有关的错误”,但却不能避免死锁。当申请和释放信号量的次序安排不当时,系统即有可能发生死锁。因此,合理的P、V操作次序也是确保算法正确、高效执行的重要基础。

[参考文献]

[1] 谭耀铭.操作系统概论[M].北京:经济科学出版社,2000.4.

[2] 汤子瀛.计算机操作系统[M].西安:西安电子科技大学出版社,2002.7.