#操作系统实验指导书

1、操作系统号原理实验指导书适用专业：软件工程制定人：邓泓、熊焕亮、李光泉 教研室：软件开发教研室江西农业大学软件学院2010年7月、八刖言操作系统是计算机的核心和灵魂。操作系统软件的设计对整个计算机的功能和性能起着 至关重要的作用，所以此门课也是必不可少的，是面向计算机科学与技术、网络工程、软件工程等大多数计算机专业本科生和研究生开设的一门计算机专业课程。操作系统是计算机系统的核心，操作系统课程是计算机科学与技术专业的重要必修课。本课程的目的是使学生掌握现代计算机操作系统的基本原理、基本设计方法及实现技术，具有分析现行操作系统和设计、开发实际操作系统的基本能力。操作系统实验是操作系统课程的重要组

2、成部分，属于学科基础实验范畴。作为与相关教学内容配合的实践性教学环节，应在操作系统理论课教学过程中开设。操作系统是计算机科学与技术专业必修的专业基础课程，操作系统实验的作用是：理解操作系统的设计和实现思路，掌握典型算法。基本要求是：理解进程的概念，理解死锁，掌 握银行家算法；掌握请求页式存储管理的实现原理及页面置换算法。学生应具有高级语言编程能力、具有数据结构等基础知识。实验要求为了顺利完成操作系统课程实验，学生应做到：（1）实验前，认真学习教材以及实验指导书的相关内容，提前做好实验准备。（2）实验结束一周后提交实验报告。实验报告内容应包括：实验目的、实验内容、设计 思路和流程框图，源程序（含

3、注释）清单、测试结果以及实验总结。（3）遵守机房纪律，服从辅导教师指挥，爱护实验设备。实验的验收将分为两个部分。第一部分是上机操作，随机抽查程序运行和即时提问；第二部分是提交书面的实验报告。此外杜绝抄袭现象，一经发现雷同，双方成绩均以0分计算。实验内容安排实验第一次上机（2课时）第二次上机（2课时）实验一熟悉进程调度相关内容； 熟悉最高优先数的调度算法的示例编写“多级反馈队列轮转法”模拟程序实验二熟悉银行家算法实验三熟悉页面置换相关内容；熟悉LRU算法的示例编写FIFO模拟程序实验一进程调度实验4实验二银行家算法模拟10实验三请求页式存储管理中常用页面置换算法模拟 14实验一 进程调度实验【开

4、发语言及实现平台或实验环境】C+/C#Microsoft Visual Studio 6.0/ Microsoft Visual Studio .NET 2003【实验目的】（1 ）加深对进程的概念及进程调度算法的理解；（2 ）在了解和掌握进程调度算法的基础上，编制进程调度算法通用程序，将调试结果显示 在计算机屏幕上，再检测和笔算的一致性。【实验要求】（1 ）了解进程调度；（2 ）理解利用进程调度算法 进行调度的原理；（3 ）会使用某种编程语言。【实验原理】一、例题：设计一个有N个 进程其行的进程调度算 法。进程调度算法：采用最 高优先数的调度算法（即把 处理机分配给优先数最高的 进程）。每个

5、进程有一个进程控 制块（PCB）表示。进程控 制块可以包含如下信息：进 程名、优先数、到达时间、 需要运行时间、已用CPU时 间、进程状态等等。进程的优先数及需要的 运行时间可以事先人为的指 定（也可以由随机数产生）。 进程的到达时间为进程的输 入的时间。进程的运行时间以时间 片为单位进行计算。每个进程的状态可以是 就绪 W（ Wait）、运行 R（Run ）、或完成 F（ Finish） 三种状态之一。就绪进程获得 CPU后都只CPU时间加1表示。如果运行一个时间片后，进程的已占用CPU时间已达到所需要的运行时间，则撤销该进程，如果运行一个时间片后，进程的已占用CPU时间还未达到所需要的运行

6、时间，也就是进程还需要继续运行，此时应该将进程的优先数减1 （即降低一级），然后把它插入就绪队列等待CPU。每进行一次调度程序都打印一次运行进程、就绪队列、以及各个进程的PCB，以便进行检查。重复以上过程，直到所要的进程都完成为止。分析：使用固定队列与静动态优先级结合每个优先级为OOxFF ,并且以小的数字为高优先级，大的数字为低优先级，每次皆使用循环得到最高优先级的进程并执行，然后将其动态优先级设置为最低，并将 其他进程动态优先级提高，以使得每个进程都有机会运行。进程的优先级与运行时间由随机数产生二、代码试例#i nclude <stdlib.h>#i nclude <st

7、dio.h>#in clude <time.h>/*常量和状态定义*/#defi nePRO_NUM0x05#defi neMAX_TIME0xFF/*状态宏*/#defi neWAIT0x01#defi neRUN0x02#defi neFINISH0x03#defi neID_ERROR0x10#defi neMIN_PRIOR0xFF#defi neMAX_PRIOR0x00typedef un sig ned intUin t32;/* 进程 PCB*/struct PCB_I nfoUi nt32s_id;Ui nt32s_static_prior;Ui nt32s

8、_dyn amic_prior;Ui nt32s_start_time;Ui nt32s_n eed_time;Ui nt32s_used_time;Uin t32s_state;；/*进程队列*/PCB_I nfog_queue5Uin t32g_time;/* 模拟进程执行函数 */void Simulator();/* 初始化 5 个进程函数 */void Init_Process();/* 初始化进程队列函数 */void Init_Queue();/* 创建进程函数 */Uint32 Create_Process(Uint32 pri,Uint32 needtime);/* 系统运行

9、函数 */void Run_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 Simula

10、tor()Init_Process();Run_Process();End_Process();void Init_Process()int i;Uint32 id;srand( (unsigned)time( NULL ) );Init_Queue();for(i=0;i<PRO_NUM;+i)/* 在这里修改随机数的范围，建议优先级取值为 0 到 4 之间，进程工作总时间为 1 到 10 之间 */id=Create_Process(rand()%4,1+rand()%10);if(id!=ID_ERROR)printf（"*n"）;printf（" 创

11、建进程成功 n"）;printf（" 进程 ID 号为 :%dn",id）;printf（" 进程的静态优先权为 :%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（&q

12、uot; 进程已用 CPU 时间为 :%dn",g_queueid.s_used_time）;printf（" 进程的状态为 :%dn",g_queueid.s_state）; printf（"n"）;elseprintf（" 创建进程失败 n"）;void Init_Queue（）int i;for（i=0;i<PRO_NUM;+i）g_queuei.s_id=i; g_queuei.s_dynamic_prior=MIN_PRIOR; g_queuei.s_need_time=0; g_queuei.s_start

13、_time=0;g_queuei.s_static_prior=MIN_PRIOR;g_queuei.s_used_time=0;g_queuei.s_state=FINISH;Uint32 Create_Process（Uint32 pri,Uint32 needtime）int i=0;Uint32 id=ID_ERROR;for（i=0;i<PRO_NUM;+i）if（g_queuei.s_state=FINISH）id=g_queuei.s_id; g_queuei.s_dynamic_prior=MIN_PRIOR; g_queuei.s_need_time=needtime;

14、 g_queuei.s_start_time=g_time;g_queuei.s_state=WAIT;g_queuei.s_static_prior=pri;g_queuei.s_used_time=0x0;break;return id;void Run_Process()Uint32 id;while(id=Get_PriProcess()!=ID_ERROR)Work_Process(id);Change_Process(id);void Print_State()int i;printf(" 时间 进程 IDt 状态 已用时间 需要时间 开始时间 静优先级 动优先级 n&q

15、uot;); for(i=0;i<PRO_NUM;+i)printf("%dt%dt%dt%dt%dt%dt%dt%dn",g_time,g_queuei.s_id,g_queu ei.s_state,g_queuei.s_used_time,g_queuei.s_need_time,g_queuei.s_start_time,g_queuei.s_static_prior ,g_queuei.s_dynamic_prior);Uint32 Get_PriProcess()Uint32 id=ID_ERROR;int i,prev_id=ID_ERROR;Uint32

16、 prior=MIN_PRIOR*2,temp_prior;for(i=0;i<PRO_NUM;+i)if(g_queuei.s_state!=FINISH)temp_prior=g_queuei.s_dynamic_prior+g_queuei.s_static_prior;if(temp_prior<=prior)id=i;return id;void Work_Process(Uint32 id)+g_time;g_queueid.s_state=RUN;+g_queueid.s_used_time;Print_State();voidChange_Process(Uint3

17、2 id)int i;if(g_queueid.s_need_time=g_queueid.s_used_time) g_queueid.s_state=FINISH;elseg_queueid.s_dynamic_prior=MIN_PRIOR; g_queueid.s_state=WAIT;for(i=0;i<PRO_NUM;+i)if(i!=id)&&(g_queuei.s_state!=FINISH)g_queuei.s_dynamic_prior>0?-g_queuei.s_dynamic_prior:g_queuei.s_dyna mic_prior=0

18、;void End_Process()printf(" 所有进程结束状态 :n");Print_State();printf(" 所有进程已经结束 !n");三、实验题：调度算法对五个进编写并调试一个模拟的进程调度程序， 采用“多级反馈队列轮转法” 程进行调度。【思考题】（1）哪种算法容易实现？【参考文献】1、 汤子瀛编计算机操作系统北京：西安电子科技大出版社，2004。2、 Tanenbaum A.S Operating System Design and Implementation清华大学出版社1996年11月（影印版）；3、 陆松年 操作系统教程

19、电子工业出版社2000年10月；4、 张尧学.计算机操作系统教程（第二版）.清华大学出版社.2000.8。实验二银行家算法模拟【开发语言及实现平台或实验环境】C语言【实验目的】（1）进一步理解利用银行家算法避免死锁的问题；（2）在了解和掌握银行家算法的基础上，编制银行家算法通用程序，将调试结果显示在计 算机屏幕上，再检测和笔算的一致性。（3）理解和掌握安全序列、安全性算法【实验要求】（1）了解和理解死锁；（2）理解利用银行家算法避免死锁的原理；（3 ）会使用某种编程语言。【实验原理】一、安全状态指系统能按照某种顺序如P1,P2,Pn（称为P1,P2,Pn序列为安全序列），为每个进程分配所需的资

20、源，直至最大需求，使得每个进程都能顺利完成。二、银行家算法假设在进程并发执行时进程i提出请求j类资源k个后，表示为Requestij=k 。系统按下述步骤进行安全检查：（1）如果Requesti Needi则继续以下检查，否则显示需求申请超出最大需求值的错误。（2） 如果Requesti Available 则继续以下检查，否则显示系统无足够资源，Pi阻塞等待。（3 ）系统试探着把资源分配给进程Pi，并修改下面数据结构中的数值：Available j ： =Availablej -Requesti j ;Allocationi,j ： =Allocationi,j +Requesti j ;N

21、eed i,j ： =Need : i,j : -Requesti j :;（4）系统执行安全性算法，检查此次资源分配后，系统是否处于安全状态。若安全，才正式将资源分配给进程 Pi，以完成本次分配；否则，将本次的试探分配作废，恢复原来的资源分配状态，让进程 Pi等待。三、安全性算法（1 ）设置两个向量： 工作向量 Work:它表示系统可提供给进程继续运行所需的各类资源数目，它含有m个元素，在执行安全算法开始时，Work： =Available; Fi ni sh:它表示系统是否有足够的资源分配给进程，使之运行完成。开始时先做Finish i： =false;当有足够资源分配给进程时，再令Fin

22、ish i ： =true 。(2) 从进程集合中找到一个能满足下述条件的进程： Finish i =false; Need :i,j Work :j ;若找到，执行步骤(3),否则，执行步骤。(3) 当进程Pi获得资源后，可顺利执行，直至完成，并释放出分配给它的资源，故应执行:Work :j ： = Work : i : +Allocation i,j :;Finish i ： = true;go to step 2;(4) 如果所有进程的 Finish i =true都满足，则表示系统处于安全状态；否则，系统 处于不安全状态。【实验步骤】参考实验步骤如下：(1) 参考图1-1所示流程图编写

23、安全性算法。(2 )编写统一的输出格式。每次提出申请之后输出申请成功与否的结果。据，并且输出安全序列。初始化Work和Finish(3)参考图1-2所示流程图编写银行家算法。开始如果成功还需要输出变化前后的各种数(4)编写主函数来循环调用银行家算法示例:存在 Finishi =false开始N#i nclude <stdio.h>int mai nint claint allocation53=int i,j,k int C_A 53=0,0,0,0,0,0,0,0,0,0,0,int result5=-1,-1辽in t curren tavail3=3,3,2;printf(&

24、quot;银行家总共拥有的各类资源的printf("银行目前仍剩下的各类资源a的数量:-RecmestYj A B printf("各进程对各类资源的最大需求量：nij输出安全sAj B C' for(i=0;i<5;i+)prin tf("P%d: ",i);for(j=0;j<是;j+)疋()m 53=7,5,3,3矽YCnCnfinish 都为 true ? n '“ A :,l=0,co un t=0,m=N输入初始参数ed资j< Availablej源分配及请求情辺,2,0赠战0曙,眩怅ed脚,0,2;/大需求

25、量出错返回： 各线程巳分配资源n(err。进程都找完了?乃需要的岀错返回：(进程阻塞)return(error)10 57n");33 2n");n");prNeedij = Needij -Requestij图#1安全性算法流程图否全吗？假定分配之后，系统安printf(” %d ",claimiC_Aij=claimij-allocationjiintf("n”);申请成功。输岀各种p数据的勺各进程已分配到的各类资源:nfor(i=0;<5;i+)申请失败。B以上分配作废，恢复原来的分配状态：Availablej = Availabl

26、ej + RequestijAllocationij= Allocationij RequestijNeedij = Needij+Requestijprintf("P%d: ",i);for(j=0;j<3;j+)printf(" %d ",allocationij);printf("n");printf(" 各进程仍需的各类资源数量： n A B Cn");for(i=0;i<5;i+)printf("P%d: ",i);for(j=0;j<3;j+)printf(&quo

27、t; %d ",C_Aij);printf("n");while(resultl=-1)/for(k=0;k<5;k+) if(resultk=-1) for(j=0;j<3;j+)/判断各线程对各资源仍需量是否小于当前可分配资源总量,此量为正数才正常if(C_Akj<=currentavailj&&C_Akj>=0)/把满足条件的进程的已分配资源加到当前可分配资源中 currentavailj=currentavailj+allocationkj; m+;if(m=3)resultl=k;/ 只有 ABC 三类资源都满足才

28、把相应的线程记入数组 result 中m=0;else break;/否则退出循环，打印”系统不安全”l+;for(i=0;i<l;i+)if(resulti!=-1)printf("P%d->"，resulti);/ 把预分配成功的先打印出来 count+;1=0;/清零，为下一轮的预分配做准备if（count=5）printf（"n 系统安全 ! 上行所示为其中一个进程安全序列n"）;elseprintf（"n 系统不安全 !n"）;结果如下：银行家总共拥有的各类资源的总数：A B C10 5 7 银行目前仍剩下的各类

29、资源的数量：A B C3 3 2 各进程对各类资源的最大需求量：A B CP0: 7 5 3P1: 3 2 2P2: 9 0 2P3: 2 2 2P4: 4 3 3 各进程已分配到的各类资源：A B CP0: 0 1 0P1: 2 0 0P2: 3 0 2P3: 2 1 1P4: 0 0 2 各进程仍需的各类资源数量：A B CP0: 7 4 3P1: 1 2 2P2: 6 0 0P3: 0 1 1P4: 4 3 1 P1->P3->P4->P0->P2->系统安全 !上行所示为其中一个进程安全序列 【思考题】（1）在编程中遇到了哪些问题？你是如何解决的？（2 ）

30、在安全性算法中，为什么不用变量Available，而又定义一个临时变量 work ?【参考文献 】1、 汤子瀛编 .计算机操作系统 .北京：西安电子科技大出版社，2004。19962、 Tanenbaum A.SOperating System Design and Implementation清华大学出版社年 11 月 （影印版 ） ；3、陆松年 操作系统教程 电子工业出版社 2000 年 10 月；实验三 请求页式存储管理中常用页面置换算法模拟【开发语言及实现平台或实验环境 】C+/C#Microsoft Visual Studio 6.0/ Microsoft Visual Studio

31、 .NET 2003【实验目的 】 （1）了解内存分页管理策略（2）掌握调页策略（3）掌握一般常用的调度算法（4）学会各种存储分配算法的实现方法。（5）了解页面大小和内存实际容量对命中率的影响。【实验要求 】 （1）采用页式分配存储方案，通过分别计算不同算法的命中率来比较算法的优劣，同时也 考虑页面大小及内存实际容量对命中率的影响；（2）实现 OPT 算法 （最优置换算法 ） 、LRU 算法 （Least Recently） 、 FIFO 算法 （First IN First Out） 的模拟；（3）会使用某种编程语言。【实验原理 】分页存储管理将一个进程的逻辑地址空间分成若干大小相等的片，称

32、为页面或页。在进程运行过程中， 若其所要访问的页面不在内存而需把它们调入内存， 但内存已无空 闲空间时， 为了保证该进程能正常运行， 系统必须从内存中调出一页程序或数据， 送磁盘的 对换区中。但应将哪 个页面调出，须根据一定的算法来确定。通常，把选择换出页面的算 法称为页面置换算法 （Page_Replacement Algorithms） 。一个好的页面置换算法， 应具有较低的页面更换频率。 从理论上讲， 应将那些以后不再 会访问的页面换出，或将那些在较长时间内不会再访问的页面调出。一、 最佳置换算法 OPT（Optimal）它是由 Belady 于 1966 年提出的一种理论上的算法。 其

33、所选择的被淘汰页面， 将是以后 永不使用的或许是在最长 （未来 ）时间内不再被访问的页面。采用最佳置换算法，通常可保证 获得最低的缺页率。 但由于人目前还无法预知一个进程在内存的若干个页面中， 哪一个页面 是未来最长时间内不再被访问的， 因而该算法是无法实现的， 便可以利用此算法来评价其它 算法。二、先进先出 （FIFO） 页面置换算法 这是最早出现的置换算法。该算法总是淘汰最先进入内存的页面，即选择在内存中驻留 时间最久的页面予以淘汰。 该算法实现简单只需把一个进程已调入内存的页面， 按先后次序 链接成一个队列，并设置一个指针，称为替换指针，使它总是指向最老的页面。 三、最近最久未使用置换算

34、法1、LRU（Least Recently Used） 置换算法的描述FIFO 置换算法性能之所以较差，是因为它所依据的条件是各个页面调入内存的时间， 而页面调入的先后并不能反映页面的使用情况。最近最久未使用（ LRU ）置换算法，是根据 页面调入内存后的使用情况进行决策的。 由于无法预测各页面将来的使用情况， 只能利用“最 近的过去”作为“最近的将来”的近似，因此， LRU 置换算法是选择最近最久未使用的页 面予以淘汰。 该算法赋予每个页面一个访问字段， 用来记录一个页面自上次被访问以来所经历的时间t,，当须淘汰一个页面时，选择现有页面中其t值最大的，即最近最久未使用的页面予以淘汰。2、LR

35、U置换算法的硬件支持LRU置换算法虽然是一种比较好的算法，但要求系统有较多的支持硬件。为了了解一 个进程在内存中的各个页面各有多少时间未被进程访问，以及如何快速地知道哪一页是最近最久未使用的页面，须有以下两类硬件之一的支持：1)寄存器为了记录某个进程在内存中各页的使用情况，须为每个在内存中的页面配置一个移位寄存器，可表示为R=Rn-iRn-2Rn-3R 2R1R0当进程访问某物理块时，要将相应寄存器的Rn-1位置成1。此时，定时信号将每隔一定时间(例如100ms)将寄存器右移一位。如果我们把n位寄存器的数看作是一个整数，那么具有最小数值的寄存器所对应的页面，就是最近最久未使用的页面。如图1示出

36、了某进程在内存中具有8个页面，为每个内存页面配置一个 8位寄存器时的LRU访问情况。这里，把 8个内存页面的序号分别定为1?8。由图可以看出，第 7个内存页面的R值最小，当发生缺页时首先将它置换出去。R7R6R5R4R3R2R1R01010100102101011003000001004011010115110101106001010117000001118011011012)栈可利用一个特殊的栈来保存当前使用的各个页面的页面号。每当进程访问某页面时，便将页面的页面号从栈中移出，将它压入栈顶。因此，栈顶始终是最新被访问页面的编号民， 而栈底则是最近最久未使用的页面的页面号。【实验步骤】参考实验

37、步骤如下： (1 )现定义数据结构和全局变量。#in clude<stdio.h>#in clude<c oni o.h>#defi ne M 4#defi ne N 17#defi ne Mypri ntf printf("|-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-|n ")/* 表格控制*/typedef struct page int num; /*记录页面号*/int time; /*记录调入内存时间*/Page;/*页面逻辑结构，结构为方便算法实现设计*/Page bM;/* 内存单元数 */int cMN;/*暂

38、保存内存当前的状态：缓冲区 */int queue100; /* 记录调入队列 */int K;/* 调入队列计数变量 */(2)初始化内存单元、缓冲区void Init(Page *b,int cMN) int i,j;for(i=0;i<N;i+) bi.num=-1; bi.time=N-i-1; for(i=0;i<M;i+) for(j=0;j<N;j+)cij=-1;(3) 取得在内存中停留最久的页面 ,默认状态下为最早调入的页面 */ int GetMax(Page *b) int i;int max=-1;int tag=0; for(i=0;i<M;i+) if(bi.time>max) max=bi.time;tag=i; return tag;(4) 判断页面是否已在内存中 */int Equation(int fold,Page *b) int i;fo