计算机操作系统实验报告.doc

精品文档 中国地质大学（北京）计算机操作系统实验报告姓 名 李萌 专业班级 10041311 学 号 1004131112 指导老师 郑春梅 成 绩 实验时间 2016/4/23 2016/6/1 内容摘要:为了提高本专业学生专业素养，加深对操作系统知识的理解，对算法思想更熟练的应用，由指导教师提供参考题目与学生自主命题相结合的办法选定了以下课程设计题目:1.编制银行家算法通用程序2.处理机管理3.存储器管理采用可变式分区管理4.LRU与改进型的CLOCK算法5.磁盘调度算法在指导教师的指导下，各个学生独立完成课题分析、设计、代码编写和调试，独立撰写课程设计报告。所有工作任务主要在微机实验室完成。关键词：操作系统；课程设计目录 目录内容摘要:2目录3实验一 编制银行家算法通用程序4实验二 处理机管理11实验三 存储器管理采用可变式分区管理20实验四 LRU与改进型的CLOCK算法31实验五 磁盘调度算法38 实验一 编制银行家算法通用程序（1） 需求分析编制银行家算法通用程序，并检测所给状态的系统安全性。假定系统的任何一种资源在任一时刻只能被一个进程使用。任何进程已经占用的资源只能由进程自己释放，而不能由其它进程抢占。进程申请的资源不能满足时，必须等待。设计的要求：(1) 程序中使用的数据结构及主要符号说明；(2) 资源的种类和数目可以变化的(3) 进程可以任意的顺序创建和变化（2） 概要设计：所用到的结构体：typedef struct intA;intB;intC;RESOURCE/最大需求矩阵RESOURCE MaxMAX_PROCESSES_NUMBER;/已分配资源数矩阵RESOURCE AllocationMAX_PROCESSES_NUMBER;/需求矩阵RESOURCE NeedMAX_PROCESSES_NUMBER;/可用资源向量RESOURCE Available = 3,3,2 ;int safeMAX_PROCESSES_NUMBER;/用于存放安全序列（3） 详细设计：（3）-1安全检查函数/安全性检查bool SafeCheck(int processNumber)RESOURCEWork = Available;bool *Finish = new boolprocessNumber;/boolFinish5 = false,false,false,false,false ;inti;intj = 0;for (i = 0; i processNumber; i+)Finishi = false;for (i = 0; i processNumber; i+)/是否已检查过if (Finishi = false)/是否有足够的资源分配给该进程if (Needi.A = Work.A & Needi.B = Work.B & Needi.C = Work.C)/有则使其执行完成，并将已分配给该进程的资源全部回收Work.A += Allocationi.A;Work.B += Allocationi.B;Work.C += Allocationi.C;Finishi = true;safej+ = i;i = -1;/重新进行遍历/如果所有进程的Finish向量都为true则处于安全状态，否则为不安全状态for (i = 0; i A B C A B C A;Available.B -= res-B;Available.C -= res-C;Allocationprocess.A += res-A;Allocationprocess.B += res-B;Allocationprocess.C += res-C;Needprocess.A -= res-A;Needprocess.B -= res-B;Needprocess.C -= res-C;/若试探分配后进入不安全状态，将分配回滚void RollBack(int process, RESOURCE *res)Available.A += res-A;Available.B += res-B;Available.C += res-C;Allocationprocess.A -= res-A;Allocationprocess.B -= res-B;Allocationprocess.C -= res-C;Needprocess.A += res-A;Needprocess.B += res-B;Needprocess.C += res-C;（4） 调试分析：测试数据：53 3 27 5 33 2 29 0 22 2 24 3 30 1 02 0 03 0 22 1 10 0 2测试结果截图： （5） 结论和展望：在设计合适的数据结构时遇到了一些阻碍，但最终还是敲定了代码中的结构体，程序得以完成。 本次实验不仅让我对银行家算法有了更深入的理解，并且还让我的编程能力得到了提高，希望能有更多这样的机会，借此较好的锻炼自己，从而更好的掌握和运用自己的专业知识，提高能力水平。（6） 主要参考文献。计算机操作系统第三版 西安电子科技大学出版社 汤子瀛主编实验二 处理机管理（1） 需求分析设计程序模拟进程的轮转法调度过程。假设初始状态为：有n个进程处于就绪状态，有m个进程处于阻塞状态。采用轮转法进程调度算法、高响应比优先（HRRN）进行调度(调度过程中，假设处于执行状态的进程不会阻塞)，且每过t个时间片系统释放资源，唤醒处于阻塞队列队首的进程。操作系统课程实验教学大纲 程序要求如下：操作系统课程实验教学大纲操名称(1)输出系统中进程的调度次序；(2)计算CPU利用率。操作（2） 概要设计： 数据结构：struct Processchar name100;double arriveTime; /到达时间double serveTime; /要求服务时间double waitTime; /HRRN算法等待时间double priority; /优先级bool isFinish;/是否完成;（3） 详细设计：(3)-1所使用变量int numOfAliveProcess;int sliceOfTime;/时间片double countTimes = 0;/全局时间片计数string nameOfProcess1000;/存放进程调度次序int countDispatch = 0;/调度下标double maxWaitTime=0;/用于计算cpu利用率(3)-2排序函数void sortByArriveTime(Process *pro,int n)/按照进程到达的顺序升序排列Process temp ;for (int i = 0; i n - 1; i+)for (int j = i + 1; j n; j+)if (proj.arriveTime proi.arriveTime)temp = proi;proi = proj;proj = temp;(3)-3响应比计算函数void getPriority(Process *pro, int n, double relativeTime)/计算响应比函数int i;/该作业等待时间 = 最后一个的提交时间 - 该作业到达的时刻for (i = 0; i n ; +i)proi.waitTime = relativeTime - proi.arriveTime;/响应比为（等待时间+要求服务时间）要求服务时间=等待时间/要求服务时间+1for (i = 0; i n; +i)proi.priority = (proi.waitTime / proi.serveTime) + 1;(3)-4 主函数中的关键逻辑while (!areAllFinish(process, n)nameOfProcesscountDispatch = ;+countDispatch;if (process0.serveTime = copayOfSlice)/如果当前被处理的进程要求服务的时间小于时间片大小process0.isFinish = true;/进程运行完毕process0.arriveTime = relativeTime;relativeTime += copayOfSlice;/下次计算响应比等待时间的参考时间点countTimes += process0.serveTime;/计数总的cpu提供服务的时间copayOfSlice -= process0.serveTime;/服务完此进程后剩余的时间片process0.serveTime = 0;/进程运行完后要求服务的时间置零maxWaitTime += copayOfSlice;/统计所有残余被删时间片goToEnd(process, numOfAliveProcess);/运行完的进程进入队列末尾，不再被cpu服务-numOfAliveProcess;/进程个数减一copayOfSlice = sliceOfTime;/删除残余时间片，分配新的时间片getPriority(process, numOfAliveProcess, relativeTime);/计算每个进程的响应比sortByPriority(process, numOfAliveProcess);/进程响应比降序排序cout 计算等待时间所用的相对时间： relativeTime endl;for (i = 0; i n; +i)if (processi.isFinish = true)cout 进程 状态:已结束 - processi.serveTime - processi.arriveTime - processi.priority endl;elsecout 进程 状态:运行中 - processi.serveTime - processi.arriveTime - processi.priority endl;cout endl; else/进入此分支说明一个时间片无法满足当前进程，此时间片结束后重新进行响应比计算process0.arriveTime = relativeTime;relativeTime += copayOfSlice;/下次计算响应比等待时间的参考时间点process0.serveTime -= copayOfSlice;/当前进程要求服务的时间countTimes += copayOfSlice;/计数总的cpu提供服务的时间copayOfSlice = sliceOfTime;/分配新的时间片getPriority(process, numOfAliveProcess, relativeTime);/计算每个进程的响应比sortByPriority(process, numOfAliveProcess);/进程响应比降序排序cout 计算等待时间所用的相对时间： relativeTime endl;for (i = 0; i n; +i)if (processi.isFinish = true)cout 进程 状态:已结束 - processi.serveTime - processi.arriveTime - processi.priority endl;elsecout 进程 状态:运行中 - processi.serveTime - processi.arriveTime - processi.priority endl;cout endl; （4） 调试分析：测试数据：5a12b33c21d63e59测试输出结果：（5） 结论和展望：通过本次实验，我对优先级和最高响应比这两个算法的理解和对进程调度的功能以及进程调度算法有了更深入的理解。同时我也发现了自己的不足，对书上的算法并不熟悉，导致程序逻辑出错，我明白了基础知识的重要性，以后写算法一定注意。（6） 主要参考文献。计算机操作系统第三版 西安电子科技大学出版社 汤子瀛主编实验三 存储器管理采用可变式分区管理（1） 需求分析克服固定分区中的主存资源的浪费，有利于多道程序设计，提高主存资源的利用率。 采用空闲区表，并增加已分配区表未分配区说明表、已分配区说明表（分区号、起始地址、长度、状态）。分配算法采用最佳适应算法（内存空闲区按照尺寸大小从小到大的排列）和循环首次适应算法，实现内存的分配与回收。（2） 概要设计： 数据结构：struct FreePartitionTableRow/空闲分区表的一行int ID;/分区号char processName;/工作名int processSize;/工作空间int startAddress;/开始地址bool state;/状态 ：1 可用 0 已用freePartitionTable100;（3） 详细设计：(3)-1 分配函数void allocateMemory()/分配内存给进程char name;int size;int c = 1;cout 请输入工作名: name;cout 请分配空间： size;if (isNameRepeat(name)cout 请选择要选的算法 1 最佳适应算法 2 循环首次适应算法 c;switch (c)case 1:optimalAdaptation(name, size); break;case 2:cyclicFirstAdaptation(name, size); break;(3)-2 内存回收函数void reclaimMemory()/回收内存char name;cout 请输入需要回收的工作名: name;int j;int i;/查找要回收的工作for (i = 0; i100; i+)if (freePartitionTcessName = name)cout 你要回收的工作已找到是在 freePartitionTablei.ID 分区中 endl;break;if (i = 100)cout 对不起 没有找到你要回收的工作 endl;int n = i;/第n个工作需要回收 /回收工作 4种情况if (i = 0 & freePartitionTable1.state = 1)freePartitionTable0.startAddress = 0;freePartitionTable0.state = 1;freePartitionTcessName = NULL;freePartitionTcessSize = freePartitionTcessSize + freePartitionTcessSize;for (i = 1; i100; i+)freePartitionTablei.startAddress = freePartitionTablei + 1.startAddress;freePartitionTablei.state = freePartitionTablei + 1.state;freePartitionTcessName = freePartitionTablei + 1.processName;freePartitionTcessSize = freePartitionTablei + 1.processSize;else if (freePartitionTablen - 1.state = 1 & freePartitionTablen + 1.state = 0)/下有空freePartitionTablen - 1.processSize = freePartitionTablen - 1.processSize + freePartitionTcessSize;for (j = n; j99; j+)freePartitionTablej.startAddress = freePartitionTablej + 1.startAddress;freePartitionTablej.state = freePartitionTablej + 1.state;freePartitionTcessName = freePartitionTablej + 1.processName;freePartitionTcessSize = freePartitionTablej + 1.processSize;else if (freePartitionTablen - 1.state = 0 & freePartitionTablen + 1.state = 1)/上有空freePartitionTcessSize = freePartitionTcessSize + freePartitionTablen + 1.processSize;freePartitionTcessName = NULL;freePartitionTablen.state = 1;for (j = n + 1; j99; j+)freePartitionTablej.startAddress = freePartitionTablej + 1.startAddress;freePartitionTablej.state = freePartitionTablej + 1.state;freePartitionTcessName = freePartitionTablej + 1.processName;freePartitionTcessSize = freePartitionTablej + 1.processSize;else if (freePartitionTablen - 1.state = 1 & freePartitionTablen + 1.state = 1)/上下都为空freePartitionTablen - 1.processSize = freePartitionTablen - 1.processSize + freePartitionTcessSize + freePartitionTablen + 1.processSize;for (j = n; j98; j+)freePartitionTablej.startAddress = freePartitionTablej + 2.startAddress;freePartitionTablej.state = freePartitionTablej + 2.state;freePartitionTcessName = freePartitionTablej + 2.processName;freePartitionTcessSize = freePartitionTablej + 2.processSize;else /上下不为空 直接回收freePartitionTablen.state = 1;freePartitionTcessName = NULL;(3)-3 最佳适应算法int optimalAdaptation(char name, int size)/最佳适应算法/查找一个大于size的空闲空间,将此空间的ID存入id，Worksize存入minint min = 1025;int id = -1;int i;for (i = 0; i100; i+)if (freePartitionTablei.state = 1 & freePartitionTcessSize size)id = i;min = freePartitionTcessSize;cout 最佳适应空间的id： id + 1 空间大小： min 0)/空闲空区大于申请空间,需要将空闲分区分割freePartitionTcessName = name;freePartitionTcessSize = size;freePartitionTableid.state = 0;for (int j = 100; jid + 1; j-)freePartitionTablej.startAddress = freePartitionTablej - 1.startAddress;freePartitionTablej.state = freePartitionTablej - 1.state;freePartitionTcessName = freePartitionTablej - 1.processName;freePartitionTcessSize = freePartitionTablej - 1.processSize;freePartitionTableid + 1.startAddress = freePartitionTableid.startAddress + freePartitionTcessSize;freePartitionTableid + 1.state = 1;freePartitionTableid + 1.processSize = temp;freePartitionTableid + 1.processName = NULL;return 0;(3)-4 循环首次适应算法int cyclicFirstAdaptation(char name, int size)/循环首次适应算法设定一全局变量xh,通过此变量记录上次找到的空闲分区 从此分区的下一个空闲分区开始循环查找首次适应空闲分区cout 从第 xh 项开始查找 endl;int p = xh;int go = 0;while (go= size)/开始分配int temp = freePartitionTcessSize;int sum = freePartitionTablep + 1.startAddress;freePartitionTcessSize = size;freePartitionTcessName = name;freePartitionTablep.startAddress = freePartitionTablep - 1.startAddress + freePartitionTablep - 1.processSize;freePartitionTablep + 1.startAddress = freePartitionTablep.startAddress + freePartitionTcessSize;freePartitionTablep.state = 0;if (tempsize)/将i项分成两项for (int j = 100; jp + 1; j-)freePartitionTablej.startAddress = freePartitionTablej - 1.startAddress;freePartitionTablej.state = freePartitionTablej - 1.state;freePartitionTcessName = freePartitionTablej - 1.processName;freePartitionTcessSize = freePartitionTablej - 1.processSize;freePartitionTablep + 2.startAddress = sum;freePartitionTablep + 1.state = 1;freePartitionTablep + 1.processName = NULL;freePartitionTablep + 1.processSize = temp - size;cout 成功分配！ endl;for (int j = p; j100; j+)if (freePartitionTablej.state = 1 & freePartitionTablej + 1.state = 1 & freePartitionTablej + 2.state = 1)/查找以后表 条件为3个连续空闲的空间 则视为以后都空闲freePartitionTcessSize = getAvailableSize();/将剩余空间放入j中xh = p;cout 下次循环首次适应从第 xh 项开始查找 100)/循环查找p = 0;return 0;（4） 调试分析：测试数据1a211b311c511d811e612b2d测试输出的结果（5） 结论和展望：通过努力，实现了可变分区存储管理的最佳适应算法和循环首次适应算法，掌握内存的分配与回收，通过资料查询，巩固了数据结构、C+程序设计的部分专业知识，增强了实际操作能力。测试用例的运行，更好的了解了两种算法的优缺点。（6） 主要参考文献。清华大学出版社出版的数据结构计算机操作系统第三版 西安电子科技大学出版社 汤子瀛主编实验四 LRU与改进型的CLOCK算法（1） 需求分析模拟分页式存储管理中硬件的地址转换和产生缺页中断，然后分别用LRU、改进型的CLOCK算法实现分页管理的缺页中断。要求：显示每个页面在内存中的绝对地址，页表信息、列出缺页情况等。（2） 概要设计：LRU算法思想：假定现有一进程所访问的页面序列为：4，7，0，7，1，0，1，2，1，2，6随着进程的访问，栈中页面号的变化情况如图所示。在访问页面6时发生了缺页，此时页面4是最近最久未被访问的页，应将它置换出去。CLOCK算法思想（流程图）数据结构：struct nodeint page;/页号int A;/访问位，0表示未被访问 1表示已被访问int M;/修改位，0表示未被修改 1表示已被修改node * next;/指向下个节点的指针;stacks;/用于lru算法的栈（3） 详细设计：(3)-1 clock思想算法/遍历整个链表，按照改进clock算法寻找淘汰页node *substitute(node *head)node *p = head;while (true)while (p-next != NULL)p = p-next;if (p-A = 0 & p-M = 0)/未被访问 未被修改，最佳淘汰页return p;p = head;while (p-next != NULL)p = p-next;if (p-A = 0 & p-M = 1)/未被访问 被修改，不是很好的淘汰页return p;p-A = 0;p = head; (3)-2 LUR算法void LRU(int page)stacktempS;/s替身tempS = s;int i=-1;/用于定位已存在的的页面if (tempS.empty()| compare(tempS,page, i)s.push(page);/如果栈为空，page进栈elseif (i = -1)cout 程序出现错误！ endl;elseexchange(i);cutStack(MAX);showStack(s); bool compare(stacks, int page, int &i);/与栈中元素比较，若有相同返回false，都不相同返回true,并且返回相同的位置（从0开始，从上往下）void exchange(int i);/将栈中第i个元素（从0开始，从栈顶往下数）与栈顶元素交换void showStack(stacks);/用于输出栈中元素void cutStack(int size);/用于删除超出内存范围的页面（4） 调试分析：测试数据： 547071012126测试输出的结果（5） 结论和展望： LRU算法是较好的一种算法，而由于LRU在硬件上要求较多，在实际应用中多采用LRU的近似算法。CLOCK算法就是用得较多的一种LRU近似算法。编程过程中加深了我对上述描述的理解，的确，这两种算法效率都很高，值得我们一探究竟。（6） 主要参考文献:清华大学出版社出版的数据结构计算机操作系统第三版 西安电子