哲学家共餐问题与计算机的资源管理

2022年5月15日09:43:31哲学家共餐问题与计算机的资源管理已关闭评论

计算机的资源分为软件资源和硬件资源。硬件的资源主要有CPU、存储器以及输入输出设备等;软件资源则是指存储于硬盘等存储设备之中的各类文件。

在计算机中,操作系统负责对计算机软硬件资源进行控制和管理,要使计算机系统中的软硬件资源得到高效使用,就会遇到由于资源共享而产生的问题。

狄克斯特拉在生产者-消费者问题的基础上,针对多进程互斥地访问有限资源(如I/O设备)的问题,提出并解决了一个被人们称为哲学家共餐(Dining Philosopher)的多进程同步问题(见图2.10)。

哲学家共餐问题与计算机的资源管理

图2.10 5个哲学家共餐

对哲学家共餐问题可以做这样的描述:5个哲学家围坐在一张圆桌旁,每个人的面前摆有一碗面条,碗的两旁各摆有一支筷子(注:狄克斯特拉原来提到的是叉子和意大利面条,因有人习惯用一个叉子吃面条,于是后来的研究人员又将叉子和意大利面条改写为中国筷子和面条)。

假设哲学家的生活除了吃饭就是思考问题(这是一种抽象,即对该问题而言其他活动都无关紧要),而吃饭的时候需要左手拿一支筷子,右手拿一支筷子,然后开始进餐。吃完后又将筷子摆回原处,继续思考问题。那么,一个哲学家的生活进程可表示为:

(1)思考问题。

(2)饿了停止思考,左手拿一支筷子(如果左侧哲学家已持有它,则需等待)。

(3)右手拿一支筷子(如果右侧哲学家已持有它,则需等待)。

(4)进餐。

(5)放右手筷子。

(6)放左手筷子。

(7)重新回到思考问题状态(1)。

现在的问题是:如何协调5个哲学家的生活进程,使得每一个哲学家最终都可以进餐。考虑下面的两种情况:

(1)按哲学家的活动进程,当所有的哲学家都同时拿起左手筷子时,所有的哲学家都将拿不到右手的筷子,并处于等待状态,那么哲学家都将无法进餐,最终饿死。

(2)将哲学家的活动进程修改一下,变为当右手的筷子拿不到时,就放下左手的筷子,这种情况是不是就没有问题?不一定,因为可能在一个瞬间,所有的哲学家都同时拿起左手的筷子,则自然拿不到右手的筷子,于是都同时放下左手的筷子,等一会,又同时拿起左手的筷子,如此永远重复下去,则所有的哲学家一样都吃不到饭。

以上两个方面的问题其实反映的是程序并发执行时进程同步的两个问题,一个是死锁(Deadlock),另一个是饥饿(Starvation)。

为了提高系统的处理能力和机器的利用率,并发程序被广泛地使用,因此,必须彻底解决并发程序中的死锁和饥饿问题。于是,人们将5个哲学家问题推广为更一般性的 个进程和 个共享资源的问题,并在研究过程中给出了解决这类问题的不少方法和工具,如Petri网、并发程序语言等工具。

  • 版权声明:本篇文章(包括图片)来自网络,由程序自动采集,著作权(版权)归原作者所有,如有侵权联系我们删除,联系方式(QQ:452038415)。