于占虎

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

[关键词]进程 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站,为确保行驶安全,必须保证在同一时刻两站之间不能有相对行驶的列车,即当有列车从某一车站开往另一个车站时,从另一个车站开往本站的列车只能等待,当有两列列车分别从两个车站出发相对行驶时,系统就发生了与时间有关的错误。……