操作系统实验指导书东北大学软件学院2008年10月实验要求（1）预习实验指导书有关部分，认真做好实验的准备工作。

（2）实验中及时分析记录。

（3）按指导书要求书写实验报告，提交打印版（A4）。

实验的验收将分为两个部分。

第一部分是上机操作，包括检查程序运行和即时提问。

第二部分是提交的实验报告。

实验一进程调度(4学时)一、实验目的在采用多道程序设计的系统中，往往有若干个进程同时处于就绪状态。

当就绪进程个数大于处理机数时，就必须依照某种策略来决定哪些进程优先占用处理机。

本实验模拟在单处理机情况下的处理机调度，帮助学生加深了解处理机调度的工作。

二、实验类型设计型。

三、预习内容预习课本处理机调度有关内容，包括进程占用处理机的策略方法。

四、实验内容与提示本实验中共有两个实验题。

第一题：编写并调试一个模拟的进程调度程序，采用“最高优先数优先”调度算法对五个进程进行调度。

<一>最高优先级优先调度算法1)优先级简介动态优先数是指在进程创建时先确定一个初始优先数，以后在进程运行中随着进程特性的改变不断修改优先数，这样，由于开始优先数很低而得不到CPU 的进程，就能因为等待时间的增长而优先数变为最高而得到CPU运行。

例如：在进程获得一次CPU后就将其优先数减少1。

或者，进程等待的时间超过某一时限时增加其优先数的值，等等。

2)详细设计优先权调度算法：1、设定系统中有五个进程，每一个进程用一个进程控制块（ PCB）表示，进程队列采用链表数据结构。

2、进程控制块包含如下信息：进程名、优先数、需要运行时间、已用CPU时间、进程状态等等。

3、在每次运行设计的处理调度程序之前，由终端输入五个进程的“优先数”和“要求运行时间”。

4、进程的优先数及需要的运行时间人为地指定。

进程的运行时间以时间片为单位进行计算。

5、采用优先权调度算法，将五个进程按给定的优先数从大到小连成就绪队列。

用头指针指出队列首进程，队列采用链表结构。

6、处理机调度总是选队列首进程运行。

采用动态优先数办法，进程每运行一次优先数减“1”，同时将已运行时间加“1”。

7、进程运行一次后，若要求运行时间不等于已运行时间，则再将它加入就绪队列；否则将其状态置为“结束”,且退出就绪队列。

8、“就绪”状态的进程队列不为空，则重复上面6，7步骤，直到所有进程都成为“结束”状态。

9、在设计的程序中有输入语句，输入5个进程的“优先数”和“要求运行时间”，也有显示或打印语句，能显示或打印每次被选中进程的进程名、运行一次后队列的变化，以及结束进程的进程名。

10、最后，为五个进程任意确定一组“优先数”和“要求运行时间”，运行并调试所设计的程序，显示或打印出逐次被选中进程的进程名及其进程控制块的动态变化过程。

3)流程图:图一.最高优先级优先调度算法流程图<二>简单轮转法调度算法1)简单轮转法的基本思想：所有就绪进程按 FCFS排成一个队列，总是把处理机分配给队首的进程，各进程占用CPU的时间片相同。

即将CPU的处理时间划分成一个个相同的时间片，就绪队列的诸进程轮流运行一个时间片。

当一个时间片结束时，如果运行进程用完它的时间片后还未完成，就强迫运行机制进程让出CPU，就把它送回到就绪队列的末尾，等待下一次调度。

同时，进程调度又去选择就绪队列中的队首进程，分配给它一时间片，以投入运行。

直至所有的进程运行完毕。

2)详细设计:1、设系统有5个进程，每个进程用一个进程控制块PCB来代表。

2、为每个进程任意确定一个要求运行时间。

3、按照进程输入的先后顺序排成一个队列。

再设一个队首指针指向第一个到达进程的首址。

4、执行处理机调度时，开始选择队首的第一个进程运行。

另外，再设一个当前运行进程的指针，指向当前正在运行的进程。

5.考虑到代码的可重用性, 轮转法调度程序和最高优先级优先调度是调用同一个模快进行输出。

6.进程运行一次后，以后的调度则将当前指针依此下移一个位置，指向下一个进程，即调整当前运行指针指向该进程的链接指针所指进程，以指示应运行进程。

同时还应判断该进程的要求运行时间是否等于已运行时间。

若不等，则等待下一轮的运行，否则将该进程的状态置为完成态C，并退出循环队列。

7.若就绪队列不空，则重复上述的（5）和（6）步骤直到所有的进程都运行完为止。

8.在所设计的调度程序中,包含显示或打印语句。

显示或打印每次选中的进程的名称及运行一次后队列的变化情况。

3)流程图图二. 简单轮转法调度算法流程图五、思考题(1)处理机调度的目的？(2)你实现优先数调度算法的思想？(3)你采用时间片轮转法实现处理机调度的思想？(4)比较效率如何？六、实验报告(1) 实验题目。

(2) 程序中使用的数据结构及符号说明。

(3) 流程图。

(4) 打印一份源程序并附上注释。

(5) 打印程序运行时的初值和运行结果。

参考资料(1)《计算机操作系统》（修订版），汤子瀛等编，西安电子科技大学出版社，2001-8。

(2)《<计算机操作系统>学习指导与题解》,汤子瀛等编, 西安电子科技大学出版社,2003-3。

实验二资源分配(4学时)一、实验目的多个进程动态地共享系统的资源可能会产生死锁现象。

死锁的产生，必须同时满足四个条件，第一个是互斥条件，即一个资源每次只能由一个进程占用；第二个为等待条件，即一个进程请求资源不能满足时，它必须等待，但它仍继续保持已得到的所有其它资源；第三个是非出让条件，任何一个进程不能抢占另一个进程已经获得且未释放的资源；第四个为循环等待条件，系统中存在若干个循环等待的进程，即其中每一个进程分别等待它前一个进程所持有的资源。

防止死锁的机构只须确保上述四个条件之一不出现，则系统就不会发生死锁。

在实验中假定系统中任一资源在每一时刻只能则由一个进程使用，任何进程不能抢占它进程正在使用的资源，当进程得不到资源时必须等待。

因此只要资源分配策略能保证进程不出现循环等待，则系统就不会发生死锁。

本实验要求学生编写和调试一个系统动态分配资源的简单模拟程序，观察死锁产生的条件，并采用适当的算法，有效地防止和避免死锁的发生。

二、实验类型设计型。

三、预习内容预习课本资源分配有关内容，包括死锁发生条件及防止避免死锁的方法。

四、实验要求与提示本实验中共有两个实验题。

第一题：用银行家算法实现资源分配。

要求：(1) 假定系统中有五个进程｛P0, P1, P2, P3, P4｝和三类资源｛A, B, C｝，各种资源的数量分别为10、5、7，在T0时刻的资源分配情况如图所示。

利用银行家算法设计系统，进程可动态地申请资源和释放资源，系统按各进程的申请动态地分配资源。

(2) 设计用银行家算法和随机分配算法，实现资源分配的两个资源分配程序，应具有显示或打印各进程依次要求申请的资源数以及依次分配资源的情况。

(3) 确定一组各进程依次申请资源数的序列，在相同的情况下分别运行上述两种资源分配程序，观察运行结果。

[提示]：(1) 银行家算法，顾名思义是来源于银行的借贷业务，一定数量的本金要应付多个客户的借贷周转，为了防止银行因资金无法周转而倒闭，对每一笔贷款，必须考察其是否能限期归还。

在操作系统中研究资源分配策略时也有类似的问题，系统中有限的资源要供多个进程使用，必须保证得到资源的进程能在有限的时间内归还资源，以供其它进程使用资源。

如果资源分配不得当，就会发生进程循环等待资源，各进程都无法继续执行下去的死锁现象。

银行家算法分配资源的原则是：系统掌握每个进程对资源的最大需求量，当进程要求申请资源时，系统就测试该进程尚需资源的最大量，如果系统中现存的资源数大于或等于该进程尚需的最大量时，则就满足进程的当前申请。

这样可以保证至少有一个进程可能得到全部资源而执行到结束，然后归还它所占用的全部资源供其它进程使用。

银行家算法破坏了产生死锁的第四个条件，即不可能产生循环等待，从而可以避免死锁的发生。

(2) 把各进程需要和已占用资源的情况记录在进程控制块中，假定进程控制块PCB的格式如表1。

其中“状态”有就绪态、等待态和完成态。

当进程处于等待态时，表示系统不能满足该进程当前的资源申请。

“资源需求总量”表示进程在整个执行过程中总共要申请的资源量。

“已占资源量”表示进程目前已经得到但还未归还的资源量。

因此，进程在以后还需要的最大资源量等于资源需求总量减去已占有资源量。

显然，每个进程的资源需求总量不能超过系统拥有的资源总数。

表1 PCB格式(3) 为了观察死锁现象的发生，了解用银行算法进行资源分配可以避免死锁，故在模拟程序中采用两种资源分配算法：银行算法和随机算法。

随机算法的分配原则是：当进程申请资源时，如果系统中现存资源数能满足进程的当前资源申请图1 资源分配模拟程序总流程量，就把资源分配给该进程，否则就置进程为等待态。

用随机算法分配资源可能会产生死锁。

资源分配模拟程序总流程见图1。

随机分配算法流程见图2。

图2 随机分配算法模拟流程第二题：用按序分配策略实现资源分配。

要求：(1) 设计一个3个进程共享10个资源的系统，进程可动态地申请资源和释放资源，系统按各进程的申请动态地分配资源。

(2) 设计用按序分配算法实现资源分配的资源分配程序，应具有显示或打印各进程依次要求申请的资源号以及依次分配资源地情况。

(3) 确定两组各进程依次要求申请的资源号，要求其中的一组中各进程按序地申请资源，另一组中各进程申请资源不受序号限制，分别运行上述设计的资源分配程序，观察运行结果。

[提示]：(1) 防止进程发生循环等待的另一种资源分配策略是按序分配算法，其基本思想如下：把系统中所有的资源排一个顺序，例如系统共有m个资源，用r i表示第i个资源，那么这m 个资源是：r1, r2, r3……, r m规定任何进程不得在占用资源r i（1<i≤m）后再申请r j（j<i≤m），或者说，如果里程需要资源r j，那么它必须在申请r i之前申请（j<i）。

可以证明，按这种策略分配资源时破坏了循环等待条件，故能防止发生死锁（证明略）。

(2) 把各进程申请资源的情况记录在进程控制块PCB中，现假定进程控制块PCB的格式如下：其中“状态”可以为就绪态、等待态和完成态。

当进程处于等待态时，表示系统不能满足该进程的当前资源申请，此时，PCB中的“当前等待资源号”反映了该进程等待的资源。

当系统为进程分配了一个资源后，则把分配的资源号填入“上次申请资源号”一栏中。

(3) 假定系统中拥有的资源数m=10，而系统中申请资源的进程数N=3。

按序分配算法程序流程见图3。

图3 按序分配算法模拟流程五、思考题(1)死锁发生的条件？(2)避免死锁的方法有哪些？(3)你的算法采用什么思想预防或避免死锁的发生？(4)效率如何？六、实验报告(1) 实验题目。