申请成功。输出各种数据的变化 申请失败。 以上分配作废，恢复原来的分配状态： Available[j] = Available[j] + Request[i][j] Allocation[i][j]= Allocation[i][j]－Request[i][j] Need[i][j] = Need[i][j]+Request[i][j] 是 假定分配之后，系统安全吗？ 否 假定分配： Request[i][j]> Need[i][j] 开始 输入初始参数（资源分配及请求情Y 出错返回：return(erroN Request[i][j]> Available[j] Y 出错返回：(进程阻塞) return(error) N Available[j] = Available[j] – Request[i][j] Allocation[i][j]= Allocation[i][j] + Request[i][j] Need[i][j] = Need[i][j] – Request[i][j]
结束 图 银行家算法流程图 3、安全性算法
（1）设置两个向量：
① 工作向量Work: 它表示系统可提供给进程继续运行所需的各类资源数目，它含有m个元素，在执行安全算法开始时，Work∶=Available；
② Finish: 它表示系统是否有足够的资源分配给进程，使之运行完成。开
第 11 页 共 16 页
始时先做Finish［i］∶=false; 当有足够资源分配给进程时， 再令Finish［i］∶=true。
（2）从进程集合中找到一个能满足下述条件的进程： ? ① Finish［i］=false；
② Need［i,j］≤Work［j］； 若找到， 执行步骤(3)， 否则，执行步骤(4)。? （3） 当进程Pi获得资源后，可顺利执行，直至完成，并释放出分配给它的资源，故应执行：?
Work［j］∶=?Work［i］+Allocation［i,j］;? Finish［i］∶=?true;? go to step （2）；
（4） 如果所有进程的Finish［i］=true都满足， 则表示系统处于安全状态；否则，系统处于不安全状态。
安全性算法的参考流程图如下：
五、实验步骤
N 所有进程都找完了？ 存在Finish[i] =false &&Need[i][j]< Available[j] 开始 初始化Work和Finish N Y Finish[i]=true，Work[j]=Work[j]+ Allocation[j] Y 所有finish都为true？ Y 输出安全序列 图 安全性算法流程图 第 12 页 共 16 页
1、设计并编写银行家算法模拟程序。 2、在上机环境中输入程序，调试，编译。 3、设计输入数据，写出程序的执行结果。 4、根据具体实验要求，填写好实验报告。
第 13 页 共 16 页
实验四 请求页式存储管理中常用页面置换算法模拟
一、实验目的
1、了解内存分页管理策略 2、掌握调页策略
3、掌握一般常用的调度算法
4、学会各种存储分配算法的实现方法。
5、了解页面大小和内存实际容量对命中率的影响。 二、实验环境
PC机、windows2000 操作系统、VC++6.0。 三、实验要求
1、 采用页式分配存储方案，通过分别计算不同算法的命中率来比较算法的
优劣，同时也考虑页面大小及内存实际容量对命中率的影响； 2、 实现OPT 算法 (最优置换算法) 、LRU 算法 (Least Recently) 、
FIFO 算法 (First IN First Out)的模拟；（三选一） 3、 会使用某种编程语言。
实验前应复习实验中所涉及的理论知识和算法，针对实验要求完成基本代码编写、实验中认真调试所编代码并进行必要的测试、记录并分析实验结果。实验后认真书写符合规范格式的实验报告，按时上交。 四、相关知识
请求分页存储管理将一个进程的逻辑地址空间分成若干大小相等的片，称为页面。并把一部分页面装入内存，启动运行。
在进程运行过程中，若其所要访问的页面不在内存而需把它们调入内存，但内存已无空闲空间时，为了保证该进程能正常运行，系统必须从内存中调出一页程序或数据，送磁盘的对换区中。但应将哪个页面调出，须根据一定的算法来确定。通常，把选择换出页面的算法称为页面置换算法(Page_Replacement Algorithms)。
一个好的页面置换算法，应具有较低的页面更换频率。从理论上讲，应将那
第 14 页 共 16 页
些以后不再会访问的页面换出，或将那些在较长时间内不会再访问的页面调出。 1、最佳置换算法OPT(Optimal)
它是由Belady于1966年提出的一种理论上的算法。其所选择的被淘汰页面，将是以后永不使用的或许是在最长(未来)时间内不再被访问的页面。采用最佳置换算法，通常可保证获得最低的缺页率。但由于人目前还无法预知一个进程在内存的若干个页面中，哪一个页面是未来最长时间内不再被访问的，因而该算法是无法实现的，但可以利用此算法来评价其它算法。 2、先进先出(FIFO)页面置换算法
这是最早出现的置换算法。该算法总是淘汰最先进入内存的页面，即选择在内存中驻留时间最久的页面予以淘汰。该算法实现简单只需把一个进程已调入内存的页面，按先后次序链接成一个队列，并设置一个指针，称为替换指针，使它总是指向最老的页面。 3、最近最久未使用置换算法
（1）LRU(Least Recently Used)置换算法的描述
FIFO置换算法性能之所以较差，是因为它所依据的条件是各个页面调入内存的时间，而页面调入的先后并不能反映页面的使用情况。最近最久未使用（LRU）置换算法，是根据页面调入内存后的使用情况进行决策的。由于无法预测各页面将来的使用情况，只能利用“最近的过去”作为“最近的将来”的近似，因此，LRU置换算法是选择最近最久未使用的页面予以淘汰。该算法赋予每个页面一个访问字段，用来记录一个页面自上次被访问以来所经历的时间t，当须淘汰一个页面时，选择现有页面中其t值最大的，即最近最久未使用的页面予以淘汰。 （2）LRU置换算法的硬件支持
LRU置换算法虽然是一种比较好的算法，但要求系统有较多的支持硬件。为了了解一个进程在内存中的各个页面各有多少时间未被进程访问，以及如何快速地知道哪一页是最近最久未使用的页面，须有以下两类硬件之一的支持： ① 寄存器
为了记录某个进程在内存中各页的使用情况，须为每个在内存中的页面配置一个移位寄存器，可表示为R=Rn-1Rn-2Rn-3??R2R1R0 当进程访问某物理块时，要将相应寄存器的Rn-1位置成1。此时，定时信号将每隔一定时间(例如100ms)将寄存器右移一位。如果我们把n位寄存器的数看作是一个整数，那么具有最小
第 15 页 共 16 页
数值的寄存器所对应的页面，就是最近最久未使用的页面。如下图示出了某进程在内存中具有8个页面，为每个内存页面配置一个8位寄存器时的LRU访问情况。这里，把8个内存页面的序号分别定为1??8。由图可以看出，第7个内存页面的R值最小，当发生缺页时首先将它置换出去。
R7 1 2 3 4 5 6 7 8 0 1 0 0 1 0 0 0 R6 1 0 0 1 1 0 0 1 R5 0 1 0 1 0 1 0 1 R4 1 0 0 0 1 0 0 0 R3 0 1 0 1 0 1 0 1 R2 0 1 1 0 1 0 1 1 R1 1 0 0 1 1 1 1 0 R0 0 0 0 1 0 1 1 1 ② 栈 可利用一个特殊的栈来保存当前使用的各个页面的页面号。每当进程访问某页面时，便将页面的页面号从栈中移出，将它压入栈顶。因此，栈顶始终是最新被访问页面的编号民，而栈底则是最近最久未使用的页面的页面号。 五、实验步骤
1、编写程序，实现请求页式存储管理中常用页面置换算法的模拟。要求屏
幕显示各算法的性能分析表、缺页中断次数以及缺页率。 2、在上机环境中输入程序，调试，编译。 3、设计输入数据，写出程序的执行结果。 4、根据具体实验要求，填写好实验报告。
第 16 页 共 16 页