操作系统课程设计

课程设计题目：操作系统课程设计。

学院。专业。

班级：计科081

指导老师。小组成员：

2024年7月15日。

目录。一、概述 2

1.设计目的 2

2.开发环境 2

二、需求分析 3

1.哲学家就餐问题的提出 3

2.解决的办法 4

三、数据结构设计 6

四、算法的描述与分析 6

五、主程序** 12

六、结束语 16

七、参考文献 17

1）了解哲学家就餐问题的背景；

2）掌握信号量的概念及pv操作的原理；

3）利用信号量的原理解决哲学家就餐问题。

哲学家就餐问题是在计算机科学中的一个经典问题，用来演示在并行计算中多线程同步 (synchronization)时产生的问题。

在2024年，著名的计算机科学家艾兹格·迪科斯彻提出了一个同步问题，即假设有五台计算机都试图访问五份共享的磁带驱动器。稍后，这个问题被托尼·霍尔重新表述为哲学家就餐问题。这个问题可以用来解释死锁和资源耗尽。

哲学家就餐问题可以这样表述，假设有五位哲学家围坐在一张圆形餐桌旁，做以下两件事情之一：吃饭，或者思考。吃东西的时候，他们就停止思考，思考的时候也停止吃东西。

餐桌中间有一大碗意大利面，每两个哲学家之间有一只餐叉。因为用一只餐叉很难吃到意大利面，所以假设哲学家必须用两只餐叉吃东西。他们只能使用自己左右手边的那两只餐叉。

哲学家就餐问题有时也用米饭和筷子而不是意大利面和餐叉来描述，因为很明显，吃米饭必须用两根筷子。

哲学家就餐问题的演示：

图1-1 哲学家进餐问题设定图。

哲学家从来不交谈，这就很危险，可能产生死锁，每个哲学家都拿着左手的餐叉，永远都在等右边的餐叉（或者相反）。

即使没有死锁，也有可能发生资源耗尽。例如，假设规定当哲学家等待另一只餐叉超过五分钟后就放下自己手里的那一只餐叉，并且再等五分钟后进行下一次尝试。这个策略消除了死锁（系统总会进入到下一个状态），但仍然有可能发生“活锁”。

如果五位哲学家在完全相同的时刻进入餐厅，并同时拿起左边的餐叉，那么这些哲学家就会等待五分钟，同时放下手中的餐叉，再等五分钟，又同时拿起这些餐叉。

在实际的计算机问题中，缺乏餐叉可以类比为缺乏共享资源。一种常用的计算机技术是资源加锁，用来保证在某个时刻，资源只能被一个程序或一段**访问。当一个程序想要使用的资源已经被另一个程序锁定，它就等待资源解锁。

当多个程序涉及到加锁的资源时，在某些情况下就有可能发生死锁。例如，某个程序需要访问两个文件，当两个这样的程序各锁了一个文件，那它们都在等待对方解锁另一个文件，而这永远不会发生。

1）服务生解法。

一个简单的解法是引入一个餐厅服务生，哲学家必须经过他的允许才能拿起餐叉。因为服务生知道哪只餐叉正在使用，所以他能够作出判断避免死锁。

为了演示这种解法，假设哲学家依次标号为a至e。如果a和c在吃东西，则有四只餐叉在使用中。b坐在a和c之间，所以两只餐叉都无法使用，而d和e之间有一只空余的餐叉。

假设这时d想要吃东西。如果他拿起了第五只餐叉，就有可能发生死锁。相反，如果他征求服务生同意，服务生会让他等待。

这样，我们就能保证下次当两把餐叉空余出来时，一定有一位哲学家可以成功的得到一对餐叉，从而避免了死锁。

2）资源分级解法。

另一个简单的解法是为资源（这里是餐叉）分配一个偏序或者分级的关系，并约定所有资源都按照这种顺序获取，按相反顺序释放，而且保证不会有两个无关资源同时被同一项工作所需要。在哲学家就餐问题中，资源（餐叉）按照某种规则编号为1至5，每一个工作单元（哲学家）总是先拿起左右两边编号较低的餐叉，再拿编号较高的。用完餐叉后，他总是先放下编号较高的餐叉，再放下编号较低的。

在这种情况下，当四位哲学家同时拿起他们手边编号较低的餐叉时，只有编号最高的餐叉留在桌上，从而第五位哲学家就不能使用任何一只餐叉了。而且，只有一位哲学家能使用最高编号的餐叉，所以他能使用两只餐叉用餐。当他吃完后，他会先放下编号最高的餐叉，再放下编号较低的餐叉，从而让另一位哲学家拿起后边的这只开始吃东西。

尽管资源分级能避免死锁，但这种策略并不总是实用的，特别是当所需资源的列表并不是事先知道的时候。例如，假设一个工作单元拿着资源3和5，并决定需要资源2，则必须先要释放5，之后释放3，才能得到2，之后必须重新按顺序获取3和5。对需要访问大量数据库记录的计算机程序来说，如果需要先释放高编号的记录才能访问新的记录，那么运行效率就不会高，因此这种方法在这里并不实用。

这种方法经常是实际计算机科学问题中最实用的解法，通过为分级锁指定常量，强制获得锁的顺序，就可以解决这个问题。

3）引入信号量与p、v操作原语：

1）信号量。

信号量（semaphore）的数据结构为一个值和一个指针，指针指向等待该信号量的下一个进程。信号量的值与相应资源的使用情况有关。当它的值大于0时，表示当前可用资源的数量；当它的值小于0时，其绝对值表示等待使用该资源的进程个数，信号量的值仅能由p、v操作来改变。

一般来说，信号量s>=0时，s表示可用资源的数量。执行一次p操作意味着请求分配一个单位资源，因此s的值减1；当s<0时，表示已经没有可用资源，请求者必须等待别的进程释放该类资源，它才能运行下去。而执行一个v操作意味着释放一个单位资源，因此s的值加1；若s<=0，表示有某些进程正在等待该资源，因此要唤醒一个等待状态的进程，使之运行下去。

2）p，v原语。

pv操作的含义：pv操作由p操作原语和v操作原语组成（原语是不可中断的过程），对信号量进行操作，具体定义如下：

p（s）：①将信号量s的值减1，即s=s-1；

②如果s>=0，则该进程继续执行；否则该进程置为等待状态，排入等待队列。

v（s）：①将信号量s的值加1，即s=s+1；

②如果s>0，则该进程继续执行；否则释放队列中第一个等待信号量的进程。

p、v操作的意义：用信号量及pv操作来实现进程的同步和互斥，p、v操作属于进程的低级通信。

图3-1 哲学家类的uml图。

程序中定义一个哲学家类，包含两个私有对象和四个公有对象。

number对象：报讯哲学家的编号。

status对象：用于保存当前该哲学家的状态，0表示正在等待（即处于饥饿状态）1表示得到餐具正在吃饭，2表示正在思考。

philosopher(int num)方法：哲学家类构造函数，参数num表示哲学家编号。

find() const方法：返回该哲学家编号。

getinfo() const方法：返回哲学家当前状态。

change()方法：根据题目要求改变哲学家的状态（等待->进餐->思考->等待………

另外，程序中包含一个公有对象，bool类型数组tools[6]，用来保存6把餐当前状态：true表示该餐具当前空闲，false表示该餐具当前正被使用。

程序中还包含两个公有函数：print和toolstatus。print用来返回一个哲学家的状态，toolstatus用来返回一个餐具的状态。

1. 在什么情况下5 个哲学家全部吃不上饭？

考虑两种实现的方式，如下：

1）算法描述：

void philosopher(int i) /i：哲学家编号，从0 到4*/

while (true) ;

操作系统课程设计

操作系统课程设计

操作系统课程设计

操作系统课程设计

其他用户还读了