操作系统实验报告(0002)

《操作系统实验报告(0002)》由会员分享，可在线阅读，更多相关《操作系统实验报告(0002)（74页珍藏版）》请在装配图网上搜索。

1、操作系统实验报告实验一银行家算法一、实验目的1、进一步深入理解死锁的概念、产生死锁的原因、避免死锁和解除死锁的方法；2、掌握利用银行家算法避免死锁的方法。二、实验要求模拟银行家算法避免死锁的实现过程三、实验原理银行家算法是一种最有代表性的避免死锁的算法。在避免死锁方法中允许进程动态地申请资源， 但系统在进行资源分配之前， 系统必须首先确定是否有足够的资源分配给该进程， 然后计算此次分配资源的安全性， 若分配不会导致系统进入不安全状态， 则分配，否则让进城等待。数据结构如下：（1）可利用资源向量Available：含有 m个元素的数组，其中的每一个元素代表一类可利用的资源数目。如果Availab

2、lej=K，则表示系统中现有 Rj 类资源 K 个。（2）最大需求矩阵 Max：一个 nm的矩阵，它定义了系统中 n个进程中的每一个进程对 m类资源的最大需求。如果 Maxi,j=K，则表示进程 i 需要 Rj 类资源的最大数目为K。（ 3）分配矩阵 Allocation ：一个 nm的矩阵，它定义了系统中每一类资源当前已分配给每一进程的资源数。如Allocationi,j=K，则表示进程 i 当前已分得 Rj 类资源的数目为K。（ 4）需求矩阵 Need：一个 nm的矩阵，用以表示每一个进程尚需的各类资源数。如果 Needi,j=K ，则表示进程 i 还需要 Rj 类资源 K 个，方能完成其

3、任务。四、程序框图开数据结构初进程 Pi 发出资源请求超过该进Y资源请求Y系统资源试Y是否存NNN系统分配系统不分结五、实验结果六、实验小结银行家算法是一个思路很清楚的办法， 在编写的过程中， 在安全性算法那一步思考了很久， 思考找到安全序列的办法， 最后选择用贪心法求得安全序列。整个算法的核心主要是对于安全状态和不安全状态的判断，分两步，第一部是系统对请求值的合法性进行检查，第二部是安全性检查， 看是否能找到看安全序列， 若试探性分配后能找到安全序列，则进行分配，否则不予分配，从而达到避免死锁的目的。实验二页面置换算法一、实验目的1、进一步了解页面置换的原理和要求；2、理解最佳置换算法、先进

4、先出、最近最久未使用、最少使用等各类置换算法的原理。二、实验要求利用各类置换算法实现对页面的置换三、实验原理1、先进先出置换算法（FIFO）：是最简单的页面置换算法。这种算法的基本思想是： 当需要淘汰一个页面时， 总是选择驻留主存时间最长的页面进行淘汰， 即先进入主存的页面先淘汰。其理由是：最早调入主存的页面不再被使用的可能性最大。2、最近最久未使用（ LRU）算法：这种算法的基本思想是：利用局部性原理，根据一个作业在执行过程中过去的页面访问历史来推测未来的行为。它认为过去一段时间里不曾被访问过的页面，在最近的将来可能也不会再被访问。 所以，这种算法的实质是： 当需要淘汰一个页面时，总是选择在

5、最近一段时间内最久不用的页面予以淘汰。四、程序框图（FIFO 置换算法）开页面页面是否在N内存页面Y替换最先进入YN将页面直接调用结 束（LRU置换算法）开页面Y页面是否在五、实验结果六、实验小结本实验研究了若干页面置换算法，在整个学习的过程中收获很多。最后重点学习了先进先出和最近最久未使用这两种算法，这两种算法均是对于最佳置换算法的改进。 实验结果显示在234432134 这种序列下 LRU置换算法的缺页率并没有比FIFO 算法更优秀，这源自于序列的特点，一般情况下， LRU算法考虑到页面调入内存后的使用情况，结果比 FIFO 更优一些。实验三调度算法一、实验目的1、了解处理机调度的层次和调

6、度算法的目标，调度的实质与意义；2、熟悉各类调度算法的原理与实际应用。二、实验要求模拟实现各类调度算法三、实验原理1、先来先服务 (FCFS)调度算法先来先服务 (FCFS)调度算法是一种最简单的调度算法。 当在作业调度中采用该算法时， 每次调度都是从后备作业队列中选择一个或多个最先进入该队列的作业， 将它们调入内存， 为它们分配资源、 创建进程，然后放入就绪队列。在进程调度中采用 FCFS算法时，则每次调度是从就绪队列中选择一个最先进入该队列的进程， 为之分配处理机，使之投入运行。 该进程一直运行到完成或发生某事件而阻塞后才放弃处理机。2、短作业优先（ SJF）调度算法最短优先调度算法是指对

7、短作业或短进程优先调度的算法。 它们可以分别用于作业调度和进程调度。短作业优先 (SJF) 的调度算法是从后备队列中选择一个或若干个估计运行时间最短的作业， 将它们调入内存运行。而短进程优先 (SPF) 调度算法则是从就绪队列中选出一个估计运行时间最短的进程， 将处理机分配给它， 使它立即执行并一直执行到完成，或发生某事件而被阻塞放弃处理机时再重新调度。3、时间片轮转调度算法在时间片轮转法中，系统将所有的就绪进程按先来先服务的原则排成一个队列，每次调度时，把 CPU 分配给队首进程，并令其执行一个时间片。当执行的时间片用完时， 由一个计时器发出时钟中断请求，调度程序便据此信号来停止该进程的执行

8、， 并将它送往就绪队列的末尾；然后，再把处理机分配给就绪队列中新的队首进程， 同时也让它执行一个时间片。 这样就可以保证就绪队列中的所有进程在一给定的时间内均能获得一时间片的处理机执行时间。4、优先级调度算法当把优先级调度算法用于作业调度时， 系统将从后备队列中选择若干个优先权最高的作业装入内存。 当用于进程调度时， 该算法是把处理机分配给就绪队列中优先权最高的进程四、程序框图（FIFO 调度算法）开处理机是否NY选择最先进入就绪（SJF 调度算法）开处理机是否NY选择预计运行时间结（时间片轮转调度算法）开Y就绪队列是N选择第 i 个一个时间片后是N加入队尾结i+Y（优先级优先调度）开处理机是

9、否NY选择优先级最高的结五、实验结果六、实验小结调度算法是操作系统最基础的算法之一，本次实验通过对先来先服务、短作业优先、 优先级优先、 时间片轮转等算法的模拟进一步熟悉了各类调度算法，无论是在加深对作业调度或者进程调度的理解上，都收获很大。实验四地址转换一、实验目的1、熟悉基本的分页、分段存储管理方式及其原理；2、理解在分页分段存储管理方式中逻辑地址与物理地址的转化。二、实验要求模拟分页、分段存储管理方式逻辑地址与物理地址的转化三、实验原理1、分页存储管理方式：地址转换时，先从页表控制寄存器中找到相应的页表，再以页号为索引去检索页表。查找操作由硬件执行。在执行检索之前， 先将页号与页表长度进

10、行比较，如果页号大于或等于页表长度，则表示本次所访问的地址已超越进程的地址空间。于是，这一错误将被系统发现并产生一地址越界中断。若未出现越界错误，则将页表始址与页号和页表项长度的乘积相加，便得到该表项在页表中的位置，于是可从中得到该页的物理块号，将之装入物理地址寄存器中。与此同时，再将有效地址寄存器中的页内地址送入物理地址寄存器的块内地址字段中。这样便完成了从逻辑地址到物理地址的变换。2、分段存储管理方式：逻辑地址空间由一组段组成。每个段都有名字和长度。 地址指定了段名称和段内偏移。因此用户通过两个量来指定地址： 段名称和偏移。 段是编号的， 通过段号而非段名称来引用。因此逻辑地址由有序对构成

11、：()段偏移 d 因该在 0 和段界限之间，如果合法，那么就与基地址相加而得到所需字节在物理内存中的地址。因此段表是一组基地址和界限寄存器对。四、程序框图（分页存储管理方式）开输入逻输出错误是否发生YN计算块号查找页表计算物理地输出物理结 束（分段存储管理方式）开输入段号输出错误是否发生YN查找段表五、实验结果六、实验小结总的来说，逻辑地址和物理地址的转化在计算上是一个简单的操作，但是通过这次实验我们更应该了解到它的本质是对不同存储管理方式的映射关系， 了解段表、页表等结构， 从而更好地理解存储管理方式，这让我受益匪浅。1、银行家算法#include#include#ifndef MY_MAX

12、#define MY_MAX 5#endifintmax153 = 7,5,3, 3,2,2, 9,0,2, 2,2,2, 4,3,3;/*最大分配需求矩阵intallocation153 = */0,1,0, 2,0,0, 3,0,2, 2,1,1, 0,0,2;/*已分配矩阵 */intneed153 = 7,4,3,1,2,2,程序清单6,0,0 ,0,1,1,/*-*/* 生成确定范围 min,max 内的随机数 */ int random_num(int min, int max)int i, range;double j;range = max - min;i = rand();j

13、 = (double)i / (double)RAND_MAX);/伪随机数生成函数rand所能返回的最大数值i = (int)(j*(double)range);i += min;return i;/* 初始化数据 */void init0_data(void)int i, j;n_proc = 5;type_src = 3;for (i = 0; in_proc; i+)for (j = 0; jtype_src; j+)maxij = max1ij;printf( 进程号非法 ( 越界 )/n); goto require0;tmp = 0;for (j = 0; jtype_src;

14、j+)tmp += needserial_procj;if (!tmp)/ 所有需要的资源数都为 0 printf(%d 该进程处于完成状态 /n, serial_proc);goto require0;printf( 对 %d 进 程 , 各资 源 要 求 : , serial_proc);for (j = 0; jtype_src; j+)scanf_s(%d,&requestserial_procj);printf(/n);/* 请求资源超过需求资源*/int over_need()int j;for (j = 0; jneedserial_pr/* 资源申请成功 */intapply_

15、success(intbe_need,intbe_avail)if (be_need = 0 & be_avail = 0)return 1;return0;/* 安全性检查 */int check_security()int i, j, tmp;for (j = 0; jtype_src; j+)workj = availablej;for (i = 0; in_proc; i+)finishi = 0;t = 0;L2:for (i = 0; in_proc; i+)if (finishi = 0) /* 没有进行安全检查 */tmp = 1;for (j = 0; jworkj)tmp

16、= 0;break;/* 银行家算法 */void banker()intallocation_t10,available_t10,need_t10;/*临时变量*/inttmp;intj;/* 保留当前的资源分配 */for (j = 0; jtype_src; j+)available_tj = availablej;allocation_tjallocationserial_procj;need_tj = needserial_procj;=/*修改available,allocation,need矩阵*/for (j = 0; jtype_src; j+)/尝试分配资源，成功就分配，不

17、成功就恢复availablej-=requestserial_procj;needserial_procj-=requestserial_procj;requestserial_procj;/* 结果输出 */void output()inti, j;printf(n安全序列输出 进程号：);for (i = 0; it; i+)printf(%d , indexi);printf(n);printf(最大需求矩阵, 已分配矩阵, 需求矩阵 , 可利用矩阵 n);for (i = 0; in_proc; i+)printf();for (j = 0; jtype_src; j+)printf(

18、%2d, maxij);printf();for (j = 0; jtype_src; j+)printf(%2d, allocationij);printf();for (j = 0; jtype_src; j+)printf(%2d, needij);printf();if (i = serial_proc)for (j = 0; jtype_src; j+)printf(%2d, availablej);printf( 本次算法模拟已经完成！ n); printf( 继续 ?y/n);if (getchar() = y)goto start;while (true)2、页面置换算法#in

19、clude stdio.h#include stdlib.htypedef struct itemint num;int time;/页号等待时间，LRU算法会用到这个属性Pro;intpageNum;/系统分配给作业的主存中的页面数int memoryNum;/可用内存页面数voidprint(Pro*page1);/ 打印当前主存中的页面intSearch(intnum1,Pro*memory1);/ 在页面集 memory1中查找 num1，如果找到，返回其在 memory1中的下标，否则返回 -1int Max(Pro *memory1);pagei.time= 0;时间开始默认为0/

20、等待for(i= 0; i memoryNum;i+)/初始化内存中页面memoryi.num= -1;/页面为空用-1表示memoryi.time = -1;i = 0;curmemory = 0;printf(*n);printf(FIFO页面置换算法n);printf(-n);missNum = 0;printf(FIFO页面置换情况:n);for (i = 0; i pageNum; i+)if(Search(pagei.num,memory) 0)/若在主存中没有找到该页面for (i = 0; i pageNum; i+)for (int j = 0; j = 0)/time是指从

21、上次被访问以来所经历的时间， 这里访问次数加 1，所以这里 time+1memoryj.time+; l+;if(Search(pagei.num,memory) 0)/ 若在主存中没有找到该页面missNum+;if (imemoryNum)curmemory = i;/内存未满，直接存入elsecurmemory = Max(memory);/ 内存已满，找到离上次访问时间最久的进行替换memorycurmemory.num=pagei.num;/替换操作memorycurmemory.time = 0;print(memory);curmemory=(curmemory+1)%/ 在页面

22、集 memory1中查找 num1，如果找到返回其在 memory1中的下标，否则返回 -1int Search(int num1, Pro *memory1)int j;for (j = 0; j memoryNum; j+)if (num1 = memory1j.num)return j;return -1;int Max(Pro *memory1)/找到 time 最大的元素的下标int max = 0;for (int k = 1; k memory1max.time)max = k;return max;intoptimal(intnum,inttag,Pro*memory1, Pr

23、o *page1)3、调度算法#includestdio.h#define N 50void main()void sjp();void fcfs();void sjf();void yxj();int a;while (true)printf(nn);printf(tt/* */);printf(ntt/*1、先到先服务调 度*/);printf(ntt/*2、短作业优先调 度*/);printf(ntt/*3、时间片轮转调 度*/);printf(ntt/*4、优先级优先调 度*/);printf(ntt/*0 、 退出*/n);printf(nt请重新输入：);scanf_s(%d, &

24、n);printf(nn);printf(t请输入时间片大小(0sjp):t);scanf_s(%d, &sjp);while (sjp = 0)printf(nt 请重新输入： ); scanf_s(%d, &sjp);struct Gzuoint id; /int dt; /int st; /进程名字到达时刻服务时间int wct; /完成时刻int st2; /标志是否完成float zt; /周转时间float dczt; /带权周转时间;Gzuo aN;for (i = 0; in; i+)ai.id = i + 1;printf(t到达时间：);min = ai.st2;ai.st

25、2 = ai + 1.st2;ai + 1.st2 = min;min = ai.id;ai.id = ai + 1.id;ai + 1.id = min;time = a0.dt;/开始计时/printf(赋值后TIME值为：%dn,time);min = 0;while (minn)flag = true;for (i = 0; i0 & ai.dt = time)flag = false;for (i = 0; in; i+)else if (flag)for (i = 0; i0&ai.dttime)time = ai.dt;break;printf(nid ：到达时间 t 服务时间

26、t 完成时间 t 周转时间 t 带权周转时间 n);sum1 = 0;sum2 = 0; for (i = 0; in; i+)printf(%d：%dtt%dtt%dtt%.0ftt%.2fn,ai.id, ai.dt, ai.st, ai.wct, ai.zt, ai.dczt);sum1 += ai.zt;sum2 += ai.dczt;float zt; / float dczt;/周转时间带权周转时间;Gzuo aN;for (i = 0; i= 0; j-)/冒泡排序：按照到达时间的先后，从小到大排序for (i = 0; iai + 1.dt)min = ai.dt;ai.dt

27、= ai + 1.dt;ai + 1.dt = min;min = ai.st;ai.st = ai + 1.st;else/到达时间在前一个完成之前ai.wct = ai - 1.wct + ai.st; ai.zt = (float)(ai.wct-ai.dt);ai.dczt = ai.zt / ai.st;printf(nid ：到达时间 t 服务时间 t 完成时间 t 周转时间 t 带权周转时间 n);sum1 = 0;sum2 = 0;for (i = 0; i= 0; j-)/ 冒泡排序：按到达时间前后排序， 如果时间一致， 按作业时间长短从短到长排序for (i = 0; ia

28、i + 1.dt)min = ai.dt; ai.dt = ai + 1.dt; ai + 1.dt = min;min = ai.st; ai.st = ai + 1.st; ai + 1.st = min;ai.id = i + 1;printf(t 到达时间： scanf_s(%d, &ai.dt);printf(t 服务时间： scanf_s(%d, &ai.st); printf(n);Gzuo aN;for (i = 0; in; i+););a0.wct = a0.st + a0.dt;/输出第一个信息a0.zt = (float)a0.st;a0.dczt = a0.zt /

29、a0.st;for (i = 1; ia0.wct);else b = b + 1;for (j = b - 1; j = 1; j-)/冒泡排序：按服务时间长短排序for (i = 1; iai + 1.st)min = ai.dt;ai.dt = ai + 1.dt;ai + 1.dt = min;min = ai.st;ai.st = ai + 1.st;ai + 1.st = min;min = ai.id;ai.id = ai + 1.id;for (j = b - 1; j = i; j-)for (z = i; zaz + 1.st)min = az.dt;az.dt = az

30、+ 1.dt;az + 1.dt = min;min = az.st;az.st = az + 1.st;az + 1.st = min;min = ai.id;ai.id = ai + 1.id;ai + 1.id = min;printf(nid ：到达时间 t 服务时间 t 完成时间 t 周转时间 t 带权周转时间 n);sum1 = 0;sum2 = 0;printf(nt请重新输入：);scanf_s(%d, &n);printf(n);struct Gzuoint id; /int dt; /int st; /int yxj; /int wct; /float zt; /float

31、 dczt;/进程名字到达时刻服务时间优先级完成时刻周转时间带权周转时间;Gzuo aN;for (i = 0; in; i+)ai.id = i + 1;printf(t到达时间： );scanf_s(%d, &ai.dt);printf(t服务时间： );scanf_s(%d, &ai.st);printf(t优先级： );scanf_s(%d, &ai.yxj);printf(n);min = ai.id;ai.id = ai + 1.id;ai + 1.id = min;min = ai.yxj;ai.yxj = ai + 1.yxj;ai + 1.yxj = min;if (ai.d

32、t = ai + 1.dt&ai.yxjai + 1.yxj)min = ai.dt;ai.dt = ai + 1.dt;ai + 1.dt = min;min = ai.st;ai.st = ai + 1.st;ai + 1.st = min;min = ai.id;ai.id = ai + 1.id;ai + 1.id = min;min = ai.yxj;ai.yxj = ai + 1.yxj;ai + 1.yxj = min;a0.wct = a0.st + a0.dt;a0.zt = (float)a0.st;min = ai.id;ai.id = ai + 1.id;ai + 1.

33、id = min;min = ai.yxj;ai.yxj = ai + 1.yxj;ai + 1.yxj = min;for (i = 1; iai - 1.wct)ai.wct = ai.dt + ai.st;ai.zt = (float)ai.st;ai.dczt = ai.zt / ai.st;elseai.wct = ai - 1.wct + ai.st; ai.zt = (float)(ai.wct-ai.dt);ai.dczt = ai.zt / ai.st;for (j = i + 1, b = j; jai.wct);printf(nid ：到达时间 t 服务时间 t 优先级t

34、 完成时间 t 周转时间 t 带权周转时间 n);sum1 = 0;sum2 = 0;for (i = 0; in; i+)printf(%d：%dtt%dtt%dtt%dtt%.0ftt%.2fn, ai.id, ai.dt, ai.yxj, ai.st,ai.wct, ai.zt, ai.dczt);sum1 += ai.zt;sum2 += ai.dczt;printf(n 平均周转时间： %.2fn, sum1 / n);printf(n平均带权周转时间：%.2fnn, sum2 / n);4、分页分段存储方式#includeusing namespace std;addr = o *

35、 64 + k;/物理地址等于主存块号* 每块字节数+偏移量cout 物理地址为 : addr endl;cout 页面号： pi.pnot主存号 : o t偏移量： k endl;flag = 1;break;if (flag = 0)cout 该页不在主存, 产生缺页中断 endl;int main()int pagenum;int ins;/指令逻辑地址struct Page p100;cout * * endl;cout 分页地址转换 endl;cout ins;changeaddr(p, ins);int segmentnum = 0;int segmentno = 0;int si = 0;int addr;struct segment s100;cout* endl;cout 分段地址转换 endl;cout- endl;cout segmentnum;for (inti =0; i segmentnum; i+)/输入段信息si.sno = i;cout 段号： si.sno endl;cout si.length;cout si.start;