1、熟悉银行家算法实验三熟悉页面置换相关内容；熟悉LRU算法的示例编写FIFO模拟程序实验一 进程调度实验【开发语言及实现平台或实验环境】C+/C#Microsoft Visual Studio 6。0/ Microsoft Visual Studio 。NET 2003【实验目的】（1）加深对进程的概念及进程调度算法的理解；（2）在了解和掌握进程调度算法的基础上，编制进程调度算法通用程序，将调试结果显示在计算机屏幕上，再检测和笔算的一致性。【实验要求】（1）了解进程调度；（2）理解利用进程调度算法进行调度的原理；（3）会使用某种编程语言.【实验原理】一、例题：设计一个有N个进程其行的进程调度算法
2、。进程调度算法：采用最高优先数的调度算法（即把处理机分配给优先数最高的进程）.每个进程有一个进程控制块（PCB）表示。进程控制块可以包含如下信息:进程名、优先数、到达时间、需要运行时间、已用CPU时间、进程状态等等。进程的优先数及需要的运行时间可以事先人为的指定（也可以由随机数产生）。进程的到达时间为进程的输入的时间。进程的运行时间以时间片为单位进行计算。每个进程的状态可以是就绪W（Wait）、运行R（Run）、或完成F（Finish）三种状态之一。就绪进程获得CPU后都只能运行一个时间片。用已占用CPU时间加1表示。如果运行一个时间片后，进程的已占用CPU时间已达到所需要的运行时间，则撤销该
3、进程，如果运行一个时间片后,进程的已占用CPU时间还未达到所需要的运行时间,也就是进程还需要继续运行，此时应该将进程的优先数减1（即降低一级），然后把它插入就绪队列等待CPU.每进行一次调度程序都打印一次运行进程、就绪队列、以及各个进程的PCB，以便进行检查。重复以上过程，直到所要的进程都完成为止.分析: 使用固定队列与静动态优先级结合每个优先级为00xFF,并且以小的数字为高优先级,大的数字为低优先级,每次皆使用循环得到最高优先级的进程并执行,然后将其动态优先级设置为最低,并将其他进程动态优先级提高，以使得每个进程都有机会运行。进程的优先级与运行时间由随机数产生.二、代码试例include
4、stdlib.h#include stdio。hinclude time.h/*常量和状态定义*/#define PRO_NUM 0x05define MAX_TIME 0xFF /*状态宏/#define WAIT 0x01#define RUN 0x02define FINISH 0x03define ID_ERROR 0x10define MIN_PRIOR 0xFF#define MAX_PRIOR 0x00typedef unsigned int Uint32;/*进程PCB/struct PCB_Info Uint32 s_id； Uint32 s_static_prior; Ui
5、nt32 s_dynamic_prior； Uint32 s_start_time; Uint32 s_need_time； Uint32 s_used_time; Uint32 s_state;/*进程队列/PCB_Info g_queue5；Uint32 g_time;/*模拟进程执行函数/void Simulator（）;/*初始化5个进程函数/void Init_Process（）；/*初始化进程队列函数/void Init_Queue（）；/创建进程函数/Uint32 Create_Process（Uint32 pri,Uint32 needtime）；/系统运行函数/void Ru
6、n_Process（）；/得到最高优先级进程 ID函数/Uint32 Get_PriProcess（）;/*进程时间片执行函数/void Work_Process（Uint32 id）;/改变进程状态和优先级函数*/void Change_Process（Uint32 id）;/*打印进程状态函数*/void Print_State（）；/结束系统函数*/void End_Process（）；/入口函数*/int main（ int argc, char *argv ） Simulator（）; return 0；void Simulator（） Init_Process（）； Run_Pro
7、cess（）; End_Process（）；void Init_Process（） int i; Uint32 id; srand（ （unsigned）time（ NULL ） ）; Init_Queue（）; for（i=0;iPRO_NUM；+i） /*在这里修改随机数的范围，建议优先级取值为0到4之间,进程工作总时间为1到10之间*/ id=Create_Process（rand（）4，1+rand（）10）; if（id!=ID_ERROR） printf（”*n）； printf（”创建进程成功n”）; printf（进程ID号为:dn”,id）; printf（”进程的静态优先权
8、为:dn”，g_queueid.s_static_prior）； printf（”进程的动态优先权为:%dn，g_queueid。s_dynamic_prior）； printf（”进程的到达时间为：%dn”,g_queueid.s_start_time）； printf（”进程需要时间为：dn”，g_queueid.s_need_time）; printf（”进程已用CPU时间为:dns_used_time）； printf（”进程的状态为:%dn”,g_queueid。s_state）；n”）; else printf（”创建进程失败n void Init_Queue（）iPRO_NUM;
9、 g_queuei.s_id=i； g_queuei。s_dynamic_prior=MIN_PRIOR； g_queuei.s_need_time=0； g_queuei.s_start_time=0； g_queuei。s_static_prior=MIN_PRIOR；s_used_time=0； g_queuei.s_state=FINISH;Uint32 Create_Process（Uint32 pri，Uint32 needtime） int i=0； Uint32 id=ID_ERROR；i0?-g_queuei。s_dynamic_prior：g_queuei。s_dynami
10、c_prior=0；void End_Process（） printf（”所有进程结束状态：n”）；所有进程已经结束!n三、实验题：编写并调试一个模拟的进程调度程序,采用“多级反馈队列轮转法调度算法对五个进程进行调度。【思考题】（1）哪种算法容易实现？【参考文献】1、 汤子瀛编。计算机操作系统。北京：西安电子科技大出版社,2004。2、Tanenbaum A。S Operating System Design and Implementation 清华大学出版社1996年11月 （影印版）；3、陆松年 操作系统教程 电子工业出版社2000年10月；4、张尧学。 计算机操作系统教程（第二版）.清
11、华大学出版社。 2000。8。实验二 银行家算法模拟C语言（1）进一步理解利用银行家算法避免死锁的问题;（2）在了解和掌握银行家算法的基础上，编制银行家算法通用程序，将调试结果显示在计算机屏幕上，再检测和笔算的一致性。（3）理解和掌握安全序列、安全性算法（1）了解和理解死锁；（2）理解利用银行家算法避免死锁的原理；一、安全状态指系统能按照某种顺序如（称为序列为安全序列），为每个进程分配所需的资源,直至最大需求，使得每个进程都能顺利完成. 二、银行家算法假设在进程并发执行时进程i提出请求j类资源k个后,表示为Requestij=k。系统按下述步骤进行安全检查:（1）如果RequestiNeedi
12、则继续以下检查，否则显示需求申请超出最大需求值的错误。（2）如果RequestiAvailable则继续以下检查，否则显示系统无足够资源,Pi阻塞等待。（3）系统试探着把资源分配给进程Pi，并修改下面数据结构中的数值： Availablej=Availablej-Requestij； Allocationi,j=Allocationi，j+Requestij； Needi,j=Needi,j-Requestij;（4）系统执行安全性算法，检查此次资源分配后，系统是否处于安全状态。若安全，才正式将资源分配给进程Pi，以完成本次分配;否则， 将本次的试探分配作废,恢复原来的资源分配状态，让进程Pi
13、等待。三、安全性算法（1）设置两个向量： 工作向量Work： 它表示系统可提供给进程继续运行所需的各类资源数目，它含有m个元素，在执行安全算法开始时，Work=Available； Finish: 它表示系统是否有足够的资源分配给进程，使之运行完成.开始时先做Finishi=false; 当有足够资源分配给进程时, 再令Finishi=true。（2）从进程集合中找到一个能满足下述条件的进程: Finishi=false; Needi,jWorkj； 若找到， 执行步骤（3）， 否则，执行步骤（4）。（3）当进程Pi获得资源后，可顺利执行,直至完成，并释放出分配给它的资源，故应执行： Work
14、j= Worki+Allocationi,j； Finishi= true； go to step 2;（4）如果所有进程的Finishi=true都满足， 则表示系统处于安全状态；否则,系统处于不安全状态。【实验步骤】 参考实验步骤如下：（1）参考图1-1所示流程图编写安全性算法。（2）编写统一的输出格式. 每次提出申请之后输出申请成功与否的结果。如果成功还需要输出变化前后的各种数据，并且输出安全序列.（3）参考图12所示流程图编写银行家算法。（4）编写主函数来循环调用银行家算法。示例：include stdio。hint main（） int claim53=7,5，3，3，2，2，9，0
15、，2,2，2，2,4，3,3;/各线程最大需求量 int allocation53=0，1,0，2,0，0,3,0,2,2，1，1，0,0，2;/各线程已分配资源 int i,j，k，l=0,count=0,m=0； int C_A53=0,0，0，0，0，0,0,0，0，0，0,0，0,0，0；/各进程仍需要的各类资源 int result5=1,1，1,1,-1;/存放预分配成功的线程 int currentavail3=3,3,2；/当前可分配资源银行家总共拥有的各类资源的总数：n A B Cn 10 5 7n printf（”银行目前仍剩下的各类资源的数量：n A B Cn 3 3 2
16、n printf（”各进程对各类资源的最大需求量:n A B Cn”）；i5；i+） printf（”P%d: ,i）； for（j=0；j3;j+） printf（ d ，claimij）; C_Aij=claimij-allocationij; printf（ printf（”各进程已分配到的各类资源:n A B Cni5; printf（”Pd: ”，i）； for（j=0; printf（” d ,allocationij）; printf（”各进程仍需的各类资源数量:n A B Cn”）;5;P%d:，i）；，C_Aij）; while（resultl=-1）/ for（k=0;k5
17、;k+） if（resultk=1） for（j=0；j3；/判断各线程对各资源仍需量是否小于当前可分配资源总量,此量为正数才正常 if（C_Akj=currentavailjC_Akj=0） /把满足条件的进程的已分配资源加到当前可分配资源中 currentavailj=currentavailj+allocationkj; m+； if（m=3） resultl=k;/只有ABC三类资源都满足才把相应的线程记入数组result中 m=0; else break;/否则退出循环，打印系统不安全” l+; for（i=0;l; if（resulti！=1） printf（”Pd-”,resul
18、ti）;/把预分配成功的先打印出来 count+; l=0；/清零,为下一轮的预分配做准备 if（count=5） printf（”n系统安全！上行所示为其中一个进程安全序列n printf（”n系统不安全！结果如下：银行家总共拥有的各类资源的总数: A B C 10 5 7银行目前仍剩下的各类资源的数量： 3 3 2各进程对各类资源的最大需求量：P0： 7 5 3P1： 3 2 2P2： 9 0 2P3: 2 2 2P4： 4 3 3各进程已分配到的各类资源： 0 1 0P1: 2 0 0 3 0 2P3： 2 1 1 0 0 2各进程仍需的各类资源数量：P0: 7 4 3 1 2 2 6 0 0 0 1 1P4: 4 3 1P1P3-P4P0P2-系统安全！上行所示为其中一个进程安全序列（1）在编程中遇到了哪些问题？你是如何解决的？（2）在安全性算法中,为什么不用变量Available，而又定义一个临时变量work？1、汤子瀛编。北京:西安电子科技大出版社,2004. 计算机操作系统教程（第二版）.清华大学出版社. 2000。实验三 请求页式存储管理中常用页面置换算法模拟Microsoft Visual Studio 6.0/ Microsoft Visual Studio .NET 2003（1）了解内存分页管理策略
