操作系统实验指导书(江西农业大学).doc

操作系统实验指导书(江西农业大学) 作者： 日期：25 个人收集整理 勿做商业用途操作系统原理实验指导书课 程 号：0540251适用专业：软件工程制 定 人：邓泓、熊焕亮、李光泉教 研 室：软件开发教研室江西农业大学软件学院2010 年7 月前言操作系统是计算机的核心和灵魂。操作系统软件的设计对整个计算机的功能和性能起着至关重要的作用，所以此门课也是必不可少的，是面向计算机科学与技术、网络工程、软件工程等大多数计算机专业本科生和研究生开设的一门计算机专业课程。操作系统是计算机系统的核心，操作系统课程是计算机科学与技术专业的重要必修课。本课程的目的是使学生掌握现代计算机操作系统的基本原理、基本设计方法及实现技术，具有分析现行操作系统和设计、开发实际操作系统的基本能力。操作系统实验是操作系统课程的重要组成部分，属于学科基础实验范畴。作为与相关教学内容配合的实践性教学环节，应在操作系统理论课教学过程中开设。操作系统是计算机科学与技术专业必修的专业基础课程，操作系统实验的作用是：理解操作系统的设计和实现思路，掌握典型算法.基本要求是:理解进程的概念，理解死锁，掌握银行家算法；掌握请求页式存储管理的实现原理及页面置换算法。学生应具有高级语言编程能力、具有数据结构等基础知识.实验要求为了顺利完成操作系统课程实验，学生应做到： （1） 实验前，认真学习教材以及实验指导书的相关内容，提前做好实验准备.（2） 实验结束一周后提交实验报告。实验报告内容应包括：实验目的、实验内容、设计思路和流程框图,源程序(含注释）清单、测试结果以及实验总结.（3） 遵守机房纪律,服从辅导教师指挥，爱护实验设备。实验的验收将分为两个部分.第一部分是上机操作，随机抽查程序运行和即时提问；第二部分是提交书面的实验报告。此外杜绝抄袭现象,一经发现雷同,双方成绩均以0分计算。实验内容安排实验第一次上机(2课时）第二次上机（2课时）实验一熟悉进程调度相关内容；熟悉最高优先数的调度算法的示例编写“多级反馈队列轮转法模拟程序实验二熟悉银行家算法实验三熟悉页面置换相关内容；熟悉LRU算法的示例编写FIFO模拟程序目 录实验一 进程调度实验5实验二 银行家算法模拟12实验三 请求页式存储管理中常用页面置换算法模拟18实验一 进程调度实验【开发语言及实现平台或实验环境】C+/C#Microsoft Visual Studio 6。0/ Microsoft Visual Studio 。NET 2003【实验目的】（1）加深对进程的概念及进程调度算法的理解；（2）在了解和掌握进程调度算法的基础上，编制进程调度算法通用程序，将调试结果显示在计算机屏幕上，再检测和笔算的一致性。【实验要求】Y已达到未达到N开 始初始化PCB，输入进程信息各进程按优先数从高到低排列就绪队列空？结 束就绪队列首进程投入运行时间片到，运行进程已占用CPU时间1运行进程已占用CPU时间达到所需的运行时间？进程完成撤销该进程使运行进程的优先数减1把运行进程插入到就绪队列（1）了解进程调度；（2）理解利用进程调度算法进行调度的原理；（3）会使用某种编程语言.【实验原理】一、 例题：设计一个有N个进程其行的进程调度算法。进程调度算法：采用最高优先数的调度算法(即把处理机分配给优先数最高的进程）.每个进程有一个进程控制块（PCB）表示。进程控制块可以包含如下信息:进程名、优先数、到达时间、需要运行时间、已用CPU时间、进程状态等等。进程的优先数及需要的运行时间可以事先人为的指定（也可以由随机数产生）。进程的到达时间为进程的输入的时间。进程的运行时间以时间片为单位进行计算。每个进程的状态可以是就绪W（Wait)、运行R(Run）、或完成F（Finish）三种状态之一。就绪进程获得CPU后都只能运行一个时间片。用已占用CPU时间加1表示。如果运行一个时间片后，进程的已占用CPU时间已达到所需要的运行时间，则撤销该进程，如果运行一个时间片后,进程的已占用CPU时间还未达到所需要的运行时间,也就是进程还需要继续运行，此时应该将进程的优先数减1（即降低一级），然后把它插入就绪队列等待CPU.每进行一次调度程序都打印一次运行进程、就绪队列、以及各个进程的PCB，以便进行检查。重复以上过程，直到所要的进程都完成为止.分析: 使用固定队列与静动态优先级结合每个优先级为00xFF,并且以小的数字为高优先级,大的数字为低优先级, 每次皆使用循环得到最高优先级的进程并执行,然后将其动态优先级设置为最低,并将其他进程动态优先级提高， 以使得每个进程都有机会运行。进程的优先级与运行时间由随机数产生.二、 代码试例include 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; Uint32 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 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 Simulator（) Init_Process(）； Run_Process(）; 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（”进程的静态优先权为: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时间为:dn，g_queueid。s_used_time)； printf（”进程的状态为:%dn”,g_queueid。s_state）； printf(n”); else printf(”创建进程失败n)； void Init_Queue() int i; for(i=0;iPRO_NUM;+i） 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； 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;iPRO_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; 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); for(i=0；iPRO_NUM；+i) printf(%dt%dt%dt%dtdtdtdt%dn”，g_time,g_queuei.s_id，g_queuei.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 prior=MIN_PRIOR*2，temp_prior; for(i=0；i0?-g_queuei。s_dynamic_prior：g_queuei。s_dynamic_prior=0； void End_Process（） printf（”所有进程结束状态：n”)； Print_State()； printf（所有进程已经结束!n）；三、 实验题：编写并调试一个模拟的进程调度程序,采用“多级反馈队列轮转法调度算法对五个进程进行调度。【思考题】（1）哪种算法容易实现？【参考文献】1、 汤子瀛编。计算机操作系统。北京：西安电子科技大出版社,2004。2、Tanenbaum A。S Operating System Design and Implementation 清华大学出版社1996年11月 （影印版)；3、陆松年 操作系统教程 电子工业出版社2000年10月；4、张尧学。 计算机操作系统教程（第二版）.清华大学出版社。 2000。8。实验二 银行家算法模拟【开发语言及实现平台或实验环境】C语言【实验目的】（1）进一步理解利用银行家算法避免死锁的问题;(2）在了解和掌握银行家算法的基础上，编制银行家算法通用程序，将调试结果显示在计算机屏幕上，再检测和笔算的一致性。（3）理解和掌握安全序列、安全性算法【实验要求】（1）了解和理解死锁；（2）理解利用银行家算法避免死锁的原理；(3）会使用某种编程语言.【实验原理】一、安全状态指系统能按照某种顺序如（称为序列为安全序列），为每个进程分配所需的资源,直至最大需求，使得每个进程都能顺利完成. 二、银行家算法假设在进程并发执行时进程i提出请求j类资源k个后,表示为Requestij=k。系统按下述步骤进行安全检查:（1)如果RequestiNeedi则继续以下检查，否则显示需求申请超出最大需求值的错误。（2)如果RequestiAvailable则继续以下检查，否则显示系统无足够资源,Pi阻塞等待。（3)系统试探着把资源分配给进程Pi，并修改下面数据结构中的数值： Availablej=Availablej-Requestij； Allocationi,j=Allocationi，j+Requestij； Needi,j=Needi,j-Requestij;（4）系统执行安全性算法，检查此次资源分配后，系统是否处于安全状态。若安全，才正式将资源分配给进程Pi，以完成本次分配;否则， 将本次的试探分配作废,恢复原来的资源分配状态，让进程Pi等待。三、安全性算法(1）设置两个向量： 工作向量Work： 它表示系统可提供给进程继续运行所需的各类资源数目，它含有m个元素，在执行安全算法开始时，Work=Available； Finish: 它表示系统是否有足够的资源分配给进程，使之运行完成.开始时先做Finishi=false; 当有足够资源分配给进程时, 再令Finishi=true。（2）从进程集合中找到一个能满足下述条件的进程: Finishi=false; Needi,jWorkj； 若找到， 执行步骤(3)， 否则，执行步骤（4）。(3)当进程Pi获得资源后，可顺利执行,直至完成，并释放出分配给它的资源，故应执行： Workj=Worki+Allocationi,j； Finishi=true； go to step 2; （4)如果所有进程的Finishi=true都满足， 则表示系统处于安全状态；否则,系统处于不安全状态。【实验步骤】参考实验步骤如下：（1）参考图1-1所示流程图编写安全性算法。Y所有finish都为true？输出安全序列NYN存在Finishi =false&Needij Needij出错返回：return(error)Requestij Availablej出错返回：(进程阻塞)return(error)Availablej = Availablej RequestijAllocationij= Allocationij + RequestijNeedij = Needij Requestij假定分配：输入初始参数（资源分配及请求情况）开始 假定分配之后，系统安全吗？申请成功。输出各种数据的变化图1-2银行家算法流程图示例：include stdio。hint main(）int claim53=7,5，3，3，2，2，9，0，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；/当前可分配资源printf(银行家总共拥有的各类资源的总数：n A B Cn 10 5 7n）;printf（”银行目前仍剩下的各类资源的数量：n A B Cn 3 3 2n);printf(”各进程对各类资源的最大需求量:n A B Cn”)；for(i=0;i5；i+)printf（”P%d: ,i）；for（j=0；j3;j+)printf（ d ，claimij);C_Aij=claimij-allocationij;printf（n)；printf(”各进程已分配到的各类资源:n A B Cn);for(i=0；i5;i+）printf（”Pd: ”，i)；for（j=0;j3;j+)printf（” d ,allocationij）;printf(n”）；printf（”各进程仍需的各类资源数量:n A B Cn”）;for(i=0;i5;i+)printf（P%d: ，i）；for(j=0；j3;j+）printf( d ，C_Aij）;printf（n);while（resultl=-1）/for(k=0;k5;k+)if（resultk=1）for（j=0；j3；j+)/判断各线程对各资源仍需量是否小于当前可分配资源总量,此量为正数才正常 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;i”,resulti）;/把预分配成功的先打印出来count+;l=0；/清零,为下一轮的预分配做准备if（count=5)printf（”n系统安全！上行所示为其中一个进程安全序列n）；elseprintf（”n系统不安全！n”);结果如下：银行家总共拥有的各类资源的总数: A B C 10 5 7银行目前仍剩下的各类资源的数量： A B C 3 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 1P1P3-P4P0P2-系统安全！上行所示为其中一个进程安全序列【思考题】（1)在编程中遇到了哪些问题？你是如何解决的？（2）在安全性算法中,为什么不用变量Available，而又定义一个临时变量work？【参考文献】1、 汤子瀛编。计算机操作系统。北京:西安电子科技大出版社,2004.2、Tanenbaum A。S Operating System Design and Implementation 清华大学出版社1996年11月 (影印版）；3、陆松年 操作系统教程 电子工业出版社2000年10月；4、张尧学。 计算机操作系统教程（第二版).清华大学出版社. 2000。8。 实验三 请求页式存储管理中常用页面置换算法模拟【开发语言及实现平台或实验环境】C+/C#Microsoft Visual Studio 6.0/ Microsoft Visual Studio .NET 2003【实验目的】(1）了解内存分页管理策略（2）掌握调页策略（3)掌握一般常用的调度算法（4）学会各种存储分配算法的实现方法。（5）了解页面大小和内存实际容量对命中率的影响。【实验要求】（1）采用页式分配存储方案，通过分别计算不同算法的命中率来比较算法的优劣,同时也考虑页面大小及内存实际容量对命中率的影响；(2）实现OPT 算法 （最优置换算法）、LRU 算法 (Least Recently)、 FIFO 算法 (First IN First Out）的模拟;（3）会使用某种编程语言。【实验原理】分页存储管理将一个进程的逻辑地址空间分成若干大小相等的片，称为页面或页.在进程运行过程中，若其所要访问的页面不在内存而需把它们调入内存，但内存已无空闲空间时，为了保证该进程能正常运行，系统必须从内存中调出一页程序或数据，送磁盘的对换区中。但应将哪 个页面调出，须根据一定的算法来确定。通常，把选择换出页面的算法称为页面置换算法(Page_Replacement Algorithms). 一个好的页面置换算法,应具有较低的页面更换频率。从理论上讲，应将那些以后不再会访问的页面换出,或将那些在较长时间内不会再访问的页面调出。一、最佳置换算法OPT(Optimal）它是由Belady于1966年提出的一种理论上的算法。其所选择的被淘汰页面,将是以后永不使用的或许是在最长（未来)时间内不再被访问的页面.采用最佳置换算法,通常可保证获得最低的缺页率。但由于人目前还无法预知一个进程在内存的若干个页面中，哪一个页面是未来最长时间内不再被访问的，因而该算法是无法实现的,便可以利用此算法来评价其它算法。 二、先进先出（FIFO）页面置换算法 这是最早出现的置换算法。该算法总是淘汰最先进入内存的页面,即选择在内存中驻留时间最久的页面予以淘汰。该算法实现简单只需把一个进程已调入内存的页面，按先后次序链接成一个队列，并设置一个指针，称为替换指针，使它总是指向最老的页面。三、最近最久未使用置换算法 1、LRU(Least Recently Used)置换算法的描述FIFO置换算法性能之所以较差，是因为它所依据的条件是各个页面调入内存的时间，而页面调入的先后并不能反映页面的使用情况。最近最久未使用（LRU）置换算法，是根据页面调入内存后的使用情况进行决策的。由于无法预测各页面将来的使用情况，只能利用“最近的过去作为“最近的将来”的近似，因此，LRU置换算法是选择最近最久未使用的页面予以淘汰。该算法赋予每个页面一个访问字段，用来记录一个页面自上次被访问以来所经历的时间t，,当须淘汰一个页面时,选择现有页面中其t值最大的，即最近最久未使用的页面予以淘汰. 2、LRU置换算法的硬件支持 LRU置换算法虽然是一种比较好的算法，但要求系统有较多的支持硬件。为了了解一个进程在内存中的各个页面各有多少时间未被进程访问,以及如何快速地知道哪一页是最近最久未使用的页面,须有以下两类硬件之一的支持： 1）寄存器 为了记录某个进程在内存中各页的使用情况，须为每个在内存中的页面配置一个移位寄存器，可表示为 R=Rn-1Rn-2Rn3R2R1R0 当进程访问某物理块时，要将相应寄存器的Rn1位置成1。此时,定时信号将每隔一定时间（例如100ms）将寄存器右移一位。如果我们把n位寄存器的数看作是一个整数，那么具有最小数值的寄存器所对应的页面，就是最近最久未使用的页面。如图1示出了某进程在内存中具有8个页面，为每个内存页面配置一个8位寄存器时的LRU访问情况。这里，把8个内存页面的序号分别定为18。由图可以看出，第7个内存页面的R值最小，当发生缺页时首先将它置换出去。 R7 R6 R5 R4 R3 R2 R1 R0 1 0 1 0 1 0 0 1 0 2 1 0 1 0 1 1 0 0 3 0 0 0 0 0 1 0 0 4 0 1 1 0 1 0 1 1 5 1 1 0 1 0 1 1 0 6 0 0 1 0 1 0 1 1 7 0 0 0 0 0 1 1 1 8 0 1 1 0 1 1 0 1 2)栈 可利用一个特殊的栈来保存当前使用的各个页面的页面号。每当进程访问某页面时,便将页面的页面号从栈中移出，将它压入栈顶。因此，栈顶始终是最新被访问页面的编号民，而栈底则是最近最久未使用的页面的页面号。【实验步骤】参考实验步骤如下：（1）现定义数据结构和全局变量。#includestdio.h include #define M 4 #define N 17 #define Myprintf printf(”-+-+-+-+-+-+-+-+-+-+-|n”)/表格控制*/ typedef struct page int num;/*记录页面号/ int time；/记录调入内存时间/ Page;/* 页面逻辑结构,结构为方便算法实现设计/ Page bM；/*内存单元数/ int cMN；/*暂保存内存当前的状态：缓冲区*/ int queue100;/记录调入队列*/ int K；/*调入队列计数变量*/ （2）初始化内存单元、缓冲区 void Init（Page *b，int cMN) int i,j； for（i=0；iN；i+) bi。num=1; bi.time=N-i1; for(i=0;iM;i+） for(j=0;jN；j+)