实验二 进程调度
一、实验目的
用高级语言编写和调试一个有 N个进程并行的进程调度程序，以加深对进程的概念及进程调度算法的理解。 二、实验设备
PC机、windows2000 操作系统、Turbo C 2.0 / VC++6.0 三、实验要求
本实验要求4学时完成。
实验前应复习实验中所涉及的理论知识和算法，针对实验要求完成基本代码编写、实验中认真调试所编代码并进行必要的测试、记录并分析实验结果。实验后认真书写符合规范格式的实验报告，按时上交。 四、预备知识
设计一个有N个进程并行的进程调度程序。
进程调度算法：采用最高优先数优先的调度算法（即把处理机分配给优先数最高的进程）和先来先服务算法。具体描述如下：
每个进程有一个进程控制块（ PCB）表示。进程控制块可以包含如下信息：进程名、优先数、到达时间、需要运行时间、已用CPU时间、进程状态等等。
分析：进程的优先数及需要的运行时间可以事先人为地指定（也可以由随机数产生）。进程的到达时间为进程输入的时间。
进程的运行时间以时间片为单位进行计算。
每个进程的状态可以是就绪 W（Wait）、运行R（Run）、或完成F（Finish）三种状态之一。
就绪进程获得 CPU后都只能运行一个时间片。用已占用CPU时间加1来表示。
如果运行一个时间片后，进程的已占用 CPU时间已达到所需要的运行时间，则撤消该进程，如果运行一个时间片后进程的已占用CPU时间还未达所需要的运行时间，也就是进程还需要继续运行，此时应将进程的优先数减1（即降低一级），
第 6 页 共 16 页
然后按照优先数的大小把它插入就绪队列等待CPU。
每进行一次调度程序都打印一次运行进程、就绪队列、以及各个进程的 PCB，以便进行检查。
重复以上过程，直到所要进程都完成为止。 调度算法的参考流程图如下：
五、实验步骤
1．编写一个有N个进程并发的进程调度程序。 2．在上机环境中输入程序，调试，编译。 3．设计输入数据，写出程序的执行结果。 4．根据具体实验要求，填写好实验报告。
第 7 页 共 16 页
实验三 银行家算法
一、 实验目的
1、理解死锁避免相关内容； 2、掌握银行家算法主要流程； 3、掌握安全性检查流程。
操作系统中的死锁避免部分的理论进行实验。要求实验者设计一个程序，该程序可对每一次资源申请采用银行家算法进行分配。 二、实验环境
PC机、windows2000 操作系统、VC++6.0。 三、 实验要求
1、设计多个资源（≥3）； 2、设计多个进程（≥3）；
3、设计银行家算法相关的数据结构；
4、动态进行资源申请、分配、安全性检测并给出分配结果。
5、撰写实验报告，并在实验报告中画出银行家和安全性检查函数流程图； 四、 实验相关知识
死锁避免定义：在系统运行过程中，对进程发出的每一个资源申请进行动态检查，并根据检查结果决定是否分配资源：若分配后系统可能发生死锁，则不予分配，否则予以分配。
由于在避免死锁的策略中，允许进程动态地申请资源。因而，系统在进行资源分配之前预先计算资源分配的安全性。若此次分配不会导致系统进入不安全状态，则将资源分配给进程；否则，进程等待。其中最具有代表性的避免死锁算法是银行家算法。 1、系统安全状态
（1）安全状态
所谓系统是安全的，是指系统中的所有进程能够按照某一种次序分配资源，并且依次地运行完毕，这种进程序列{ P1 ，P2 ?Pn}就是安全序列。如果存在
第 8 页 共 16 页
这样一个安全序列，则系统是安全的。
并非所有的不安全状态都会转为死锁状态，但当系统进入不安全状态后，便有可能进入死锁状态；反之，只要系统处于安全状态，系统便可避免进入死锁状态。所以避免死锁的实质：系统在进行资源分配时，如何使系统不进入不安全状态。
（2）安全状态之例
假设系统有三个进程，共有12台磁带机。各进程的最大需求和T0时刻已分配情况如下表：
进程 P1 P2 P3 最大需求 10 4 9 已分配 5 2 2 3 可用 问：T0时刻是否安全？ 答：T0时刻是安全的，因为存在安全序列：P2 ?P1? P3 不安全序列：P1?? P3?? P2?P3?P1
（3）由安全状态向不安全状态的转换
如果不按照安全序列分配资源，则系统可能会由安全状态进入不安全状态。例如，在T0时刻以后，P3又请求1台磁带机，若此时系统把剩余3台中的1台分配给P3，则系统便进入不安全状态。 因为，此时也无法再找到一个安全序列， 例如，把其余的2台分配给P2，这样，在P2完成后只能释放出4台，既不能满足P1尚需5台的要求，也不能满足P3尚需6台的要求，致使它们都无法推进到完成，彼此都在等待对方释放资源，即陷入僵局，结果导致死锁。 2、 利用银行家算法避免死锁
（1）银行家算法中的数据结构
① 可利用资源向量Available。
这是一个含有m个元素的数组，其中的每一个元素代表一类可利用的资源数目，其初始值是系统中所配置的该类全部可用资源的数目，其数值随该
第 9 页 共 16 页
类资源的分配和回收而动态地改变。如果Available［j］=K，则表示系统中现有Rj类资源K个。
② 最大需求矩阵Max。
最大需求矩阵Max。这是一个n×m的矩阵，它定义了系统中n个进程中的每一个进程对m类资源的最大需求。如果Max［i,j］=K，则表示进程i需要Rj类资源的最大数目为K。
③ 分配矩阵Allocation
这也是一个n×m的矩阵，它定义了系统中每一类资源当前已分配给每一进程的资源数。如果Allocation［i,j］=K，则表示进程i当前已分得Rj类资源的数目为K。?
④ 需求矩阵Need
这也是一个n×m的矩阵，用以表示每一个进程尚需的各类资源数。如果Need［i,j］=K，则表示进程i还需要Rj类资源K个，方能完成其任务。
Need［i,j］=Max［i,j］-Allocation［i,j］
（2）银行家算法
设Requesti是进程Pi的请求向量，如果Requesti［j］=K，表示进程Pi需要K个Rj类型的资源。当Pi发出资源请求后，系统按下述步骤进行检查：?
① 如果Requesti［j］≤Need［i,j］，便转向步骤2；否则认为出错，因为它所需要的资源数已超过它所宣布的最大值。
② 如果Requesti［j］≤Available［j］，便转向步骤(3)；否则， 表示尚无足够资源，Pi须等待。
③ 系统试探着把资源分配给进程Pi，并修改下面数据结构中的数值：? Available［j］∶=Available［j］-Requesti［j］;? Allocation［i,j］∶=Allocation［i,j］+Requesti［j］;? Need［i,j］∶=Need［i,j］-Requesti［j］;?
④ 系统执行安全性算法，检查此次资源分配后，系统是否处于安全状态。若安全，才正式将资源分配给进程Pi，以完成本次分配；否则， 将本次的试探分配作废，恢复原来的资源分配状态，让进程Pi等待。
银行家算法的参考流程图如下：
第 10 页 共 16 页