广工操作系统实验.doc

操作系统实验报告 学生学院 计算机学院 专业班级 12级网络1班 学 号 3112006345 学生姓名 沙宇丰 指导教师 李敏 2015 年 01月 07日目录1 实验一 进程调度2 实验二 作业调度3 实验三 存储管理 实验一 进程调度（实现了最高优先级优先，时间片轮转，多级反馈队列三种算法 ）1、 实验目的 编写并调试一个模拟的进程调度程序，采用最高优先数优先算法，时间片轮转算法，多级反馈队列算法对进程进行调度。以加深对进程的概念及进程调度算法的理解 2：实验原理每个进程有一个进程控制块（ PCB）表示。进程控制块可以包含如下信息：进程名、到达时间、需要运行时间、已运行时间、进程状态等等。 每个进程的状态可以是就绪 W（Wait）、运行R（Run）两种状态之一。 就绪进程获得 CPU后都只能运行一个时间片。用运行时间加1来表示。 如果运行一个时间片后，进程的已占用 CPU时间已达到所需要的运行时间，则撤消该进程，如果运行一个时间片后进程的已占用CPU时间还未达所需要的运行时间，也就是进程需要继续运行，此时应分配时间片给就绪队列中排在该进程之后的进程，并将它插入就绪队列队尾。 3：实验内容，方法首先对于：最高优先数算法： 最高优先数算法的基本思想是把cpu分配给就绪队列中优先数最高的进程。而我采用优先数动态变化的方式，进程在没获得一次cpu时间后其优先数就减一，然后对各个进程的优先数进行重新排序。继续把cpu分配给优先数最高的进程。进程的剩余时间为0时就退出队列。首先用create（）函数创建链表并对其初始化，然后对链表按照优先级大小进行排序，然后把排序后的链表放进processing（）函数中进行处理，让其占有一个时间片执行，若进程任然未完成，则把该进程放进insert（）函数中插入就绪队列中。用disp（）函数进行进程的显示。4：流程图：5：重要函数和数据结构的说明：Struct PCB对进程结构体进行定义Create()函数进行链表的初始化Processing（）函数对整个链表的循环进行处理Sort（）函数对优先级进行动态排序：Disp（）函数对结果进行显示struct PCB *sort(struct PCB *head)/*递增排序函数：入口参数：链表的头指针，此为链表中的排序函数*/struct PCB *p,*q;int temp;for(p=head;p!=NULL;p=p-next)for(q=p-next;q!=NULL;q=q-next)if(p-prioprio) /通过对链表里面的数据进行互换达到重新排序temp=q-prio;q-prio=p-prio;p-prio=temp;temp=q-name;q-name=p-name;p-name=temp;temp=q-run;q-run=p-run;p-run=temp;temp=q-rest;q-rest=p-rest;p-rest=temp;return head; 5：实验效果：:6：实验总结： 对于最高优先数优先的算法，在设计好进程控制块链表后，就要对优先级进行排序，优先数动态变化和链表的循环是比较花时间处理的，如上图所显示，优先级在进程每执行一个时间片后减一，实现动态变化，开始在这两部分总是出问题，经过耐心的处理还是把问题很好的解决了。对于第二个：时间片轮转算法， 3：实验方法，步骤：基本思想：所有就绪进程按fcfs排成一个队列，总是把处理机分配给队首的进程，各进程占用的cpu时间片相同，如果运行进城用完时间片后还未完成，就把它送进就绪队列的末尾，把处理机重新分配给队首的集成。直至所有的进程运行完毕。4：流程图 :4：重要的函数和数据结构：Struct PCB对进程结构体进行定义 Create()函数进行链表的初始化 Insert（）函数把未完成的进程插入就绪队列的末尾 Processing（)函数对链表循环进行处理 Disp（）函数对结果进行显示其中insert（）函数对进程插入就绪队列末尾是比较重要的 void insert(struct PCB *p) struct PCB *p1,*p2; p2=p1=p; p2=(struct PCB *)malloc(sizeof(struct PCB); while(p1-next)p1=p1-next; p1-next=p2; p2-state=就绪中; p2-name=p-name; p2-run=p-rest; p2-queue=(p-queue)+1;p2-rest=p-rest; p2-fragement=2; p2-next=NULL; :5： 实验效果：:6：实验总结：如上图所示，进程在一个时间片执行完后进程，剩余时间为0，退出队列，进程2在执行完一个时间片后仍然未完成，进入就绪队列末尾，以此类推，直至三个进程都完成，这个时间片轮转算法比较简单，只需要处理好把未完成的进程插入就绪队列末尾即可，把已完成的从就绪队列中释放。调试过程中总是会出现bug，但需要我们耐心一个个解决。 第三个：多级队列反馈算法:：3：实验方法，步骤：其思想是：当一个新进程进入内存后，首先将它放入第一个队列的末尾，按fcfs的原则排队等待，当轮到该进程执行，如能在该时间片内完成，则撤出系统，倘若在时间片内未完成，则放进第二个队列的末尾，按同样的fcfs原则等待执行。首先用create（）函数创建链表并对其初始化，然后把链表放进processing（）函数中进行处理，若任然未完成，则把该进程放进insert（）函数中插入下 一队列。4：流程图:4：重要的函数和数据结构： struct PCB对进程结构体进行定义 Create()函数进行链表的初始化 Insert（）函数把未完成的进程插入下一个就绪队列的末尾 Processing（)函数对链表循环进行处理 Disp（）函数对结果进行显示Insert()函数把进程插入下一个就绪队列 void insert(struct PCB *p) struct PCB *p1,*p2; p2=p1=p; p2=(struct PCB *)malloc(sizeof(struct PCB); while(p1-next)p1=p1-next; p1-next=p2; p2-state=就绪中; p2-name=p-name; p2-run=p-rest; p2-queue=(p-queue)+1;p2-rest=p-rest; p2-fragement=2*(p-fragement); p2-next=NULL; void processing(struct PCB *head) /对占有cpu时间的进程进行系列的处理 struct PCB *p1,*p2,*p3; int n=0; p1=head; while(p1) p1-rest=p1-rest-p1-fragement; if(p1-restrest=0; p1-state=运行中; disp(p1); if(p1-rest=0) printf(ttt进程%d已完成n,p1-name); if(p1-rest0)insert(p1); p1=p1-next; 5：实验效果：6：实验总结： 对于这个多级队列反馈，我在结构体pcb的定义中增加了一个表示队列序号的queue来从逻辑上标识不同的队列，:和让时间片的大小呈指数增长的变量fragement，如上图所示，进程1在第一个时间片运行完后任然未完成，则进入第二个就绪队列，它的时间片大小变为了4，使得进入下个队列的进程能获得较大的时间片。可见，多级反馈队列能够比较好的适应长作业和短作业的需求。 实验二 作业调度 （实现了单道和多道）一：实验目的：编写并调试作业调度的模拟程序，了解作业调度在操作系统中的作用，以加深对作业调度算法的理解。二：实验内容和要求： 1、为单道批处理系统设计一个作业调度程序(1)、编写并调试一个单道处理系统的作业调度模拟程序。(2)、作业调度算法：分别采用先来先服务（FCFS）、响应比高者优先（HRN）的调度算法。 (3)、由于在单道批处理系统中，作业一投入运行，它就占有计算机的一切资源直到作业完成为止，因此调度作业时不必考虑它所需要的资源是否得到满足，它所占用的 CPU时限等因素。(4)、每个作业由一个作业控制块JCB表示，JCB可以包含如下信息：作业名、提交时间、所需的运行时间、所需的资源、作业状态、链指针等等。作业的状态可以是等待W(Wait)、运行R(Run)和完成F(Finish)三种状态之一。每个作业的最初状态总是等待W。(5)、对每种调度算法都要求打印每个作业开始运行时刻、完成时刻、周转时间、带权周转时间，以及这组作业的平均周转时间及带权平均周转时间，并比较各种算法的优缺点。3、实验设计方案及原理1、编写并调试一个单道处理系统的作业等待模拟程序。 已知它们进入系统的时间、估计运行时间。分别采用先来先服务（FCFS），最短作业优先（SJF）、响应比高者优先（HRN）的调度算法，计算出作业的平均周转时间和带权的平均周转时间 。 对每种调度算法都要求打印每个作业开始运行时刻、完成时刻、周转时间、带权周转时间，以及这组作业的平均周转时间及带权平均周转时间，并比较各种算法的优缺点。对于先来先服务fcfs调度算法：流程图：重要的函数和数据结构：Struct fcfs 定义结构体Print（）函数对到来的作业进行初始化并进行显示Sort（）函数对作业按照到来的作业的时间先后进行排序Deal（）函数对先来先服务原则对作业进行系列处理Main（）函数进行对各个函数的串接。定义结构体：struct fcfschar name10;float arrivetime;float servicetime;float starttime;float finishtime;float zztime;float dqzztime;Deal函数按照fcfs原则处理各个作业,是本程序的重要函数void deal(fcfs *p,int N) int k; for(k=0;k=N-1;k+) if(k=0) pk.starttime=pk.arrivetime; pk.finishtime=pk.arrivetime+pk.servicetime; else pk.starttime=pk-1.finishtime; pk.finishtime=pk-1.finishtime+pk.servicetime; for(k=0;k=N-1;k+) pk.zztime=pk.finishtime-pk.arrivetime; pk.dqzztime=pk.zztime/pk.servicetime; 4:实验效果：5：实验总结：对于先来先服务算法，如图所示：在就绪队列中按照时间到达先后挑选要进行的作业,各个作业的运行顺序分别是2 1 3；fcfs原则只考虑到了到达的时间先后，而未考虑作业要求的时长，这是个不足之处。在调试过程中遇到了不少bug，需要我们细心调试。短作业优先调度算法流程图：重要的函数和数据结构：Struct sjf定义结构体Print（）函数对到来的作业进行初始化并进行显示Sort（）函数对作业按照到来的作业的时间先后进行排序Deal（）函数按照最短作业优先服务原则对作业进行系列处理运行阶段中deal函数按照短作业优先原则对作业进行处理void deal(sjf *p,int N) int k; for(k=0;k=N-1;k+) if(k=0) pk.starttime=pk.arrivetime; pk.finishtime=pk.arrivetime+pk.servicetime; else pk.starttime=pk-1.finishtime; pk.finishtime=pk-1.finishtime+pk.servicetime; for(k=0;k=N-1;k+) pk.zztime=pk.finishtime-pk.arrivetime; pk.dqzztime=pk.zztime/pk.servicetime; 实验效果图：实验总结：对于短作业调度算法：如图所示,优先选择短作业，参考了几个作业调度的范例，作业调度实践起来并不难，但需要慢慢调试。和同学讨论了设计思路之后就开始做了，虽然有小错误，但是经过反复调试也修正了BUG。高响应比优先调度算法：流程图： 3：重要的函数和数据结构：Struct zgxyb定义结构体Print（）函数对到来的作业进行初始化并进行显示Sort（）函数对作业按照到来的作业的时间先后进行排序Deal（）函数按照高响应比优先原则对作业进行系列处理Deal（）函数中对在运行时各个作业的周转时间，开始时间，完成时间等变量进行处理，使得响应比高者总是先执行。void deal(struct zgxyb *p,int N) int k; for(k=0;k=N-1;k+) if(k=0) pk.starttime=pk.arrivetime; pk.finishtime=pk.arrivetime+pk.servicetime; else pk.starttime=pk-1.finishtime; pk.finishtime=pk-1.finishtime+pk.servicetime; for(k=0;klink = ready;ready = p;elsenext = ready;while (next-link != NULL)next = next-link;next-link = p;void sortByIntime()/*按提交时间进行先后排序*/JCB *first, *second, *finish = NULL;int insert;while (ready != NULL)insert = 0;p = ready;ready = p-link;p-link = NULL;if (finish = NULL) | (p-intime) intime)/*提交时间最小者，插入队首*/p-link = finish;finish = p;else/*比较提交时间，插入适当的位置中*/first = finish;second = first-link;while (second != NULL)if (p-intime) intime)/*若插入作业比当前作业提交时间*/*插入到当前作业前面*/p-link = second;first-link = p;second = NULL;insert = 1;else/*插入作业提交时间最大，则插入到队尾*/first = first-link;second = second-link;if (insert = 0) first-link = p;ready = finish;void sortByNtime()/*按提交时间进行先后排序*/JCB *first, *second, *finish = NULL;while (ready != NULL)int insert = 0;p = ready;ready = p-link;p-link = NULL;if (finish = NULL) | (p-ntime) ntime)/*需求时间最小者，插入队首*/p-link = finish;finish = p;else/*比较需求时间，插入适当的位置中*/first = finish;second = first-link;while (second != NULL)if (p-ntime) ntime)/*若插入作业比当前作业需求时间*/*插入到当前作业前面*/p-link = second;first-link = p;second = NULL;insert = 1;else/*插入作业需求时间最大，则插入到队尾*/first = first-link;second = second-link;if (insert = 0) first-link = p;ready = finish;void FCFS()int sort = 0;/作业被选中执行的次序char ch;sortByIntime();/按进入时间进行排序while (!isALLjobDONE()p = ready;while (p != NULL)if (p-state = W)/找正在等待的作业if (p-needmem needtapenum needmem;tapenum = tapenum - p-needtapenum;p-state = R;/作业状态为正在运行printf(作业%c被选中执行的次序为%d：n,p-user,sort);display();printf(任何键继续.);ch = getchar();elseprintf(作业%s请求失败n,p-name);running();/运行作业p = p-link;printf(n全部作业已经完成n);display();ch = getchar();void SJF()int sort = 0;/作业被选中执行的次序char ch;sortByNtime();/按需要运行时间进行排序while (!isALLjobDONE()p = ready;while (p != NULL)if (p-state = W)/找正在等待的作业if (p-needmem needtapenum needmem;tapenum = tapenum - p-needtapenum;p-state = R;/作业状态为正在运行printf(作业%c被选中执行的次序为%d：n, p-user, sort);display();printf(任何键继续.);ch = getchar();elseprintf(作业%s请求失败n, p-name);running();/运行作业p = p-link;printf(n全部作业已经完成n);display();ch = getchar();5：实验效果：6： 实验总结：多道批处理比起单道批，需要多考虑作业对资源的需求，fcfs和sjf的算法的实现跟前面都没有太大的不同。 实验三： 存储管理实验一：实验目的:通过编写并调试存储管理的模拟程序以加深对存储管理方案的理解，首席虚拟存储管理的各种页面淘汰算法通过编写并调试地址转换过程的模拟程序以加深地址转换过程的了解。二：实验内容和要求1、产生一个需要访问的指令地址流，它是一系列需要访问的指令的地址。为不失一般性，你可以适当地（用人工指定地方法或用随机数产生器）生成这个序列，使得 50的指令是顺序执行的。25的指令均匀地散布在前地址部分，25的地址是均匀地散布在后地址部分。2、指定合适的页面尺寸（例如以 1K或2K为1页）； 3、指定内存页表的最大长度，并对页表进行初始化； 4、 每访问一个地址时，首先要计算该地址所在的页的页号，然后查页表，判断该页是否在主存如果该页已在主存，则打印页表情况；如果该页不在主存且页表未满，则调入一页并打印页表情况；如果该页不足主存且页表已满，则按 FIFO页面淘汰算法淘汰一页后调入所需的页，打印页表情况； 逐个地址访问，直到所有地址访问完毕。三：实验方法和步骤1：设计一个固定式分区分配的存储管理方案，并模拟实现分区的分配和回收。假定每个作业都是批处理作业，并且不允许动态申请内存。为实现分区的分配和回收，可以假定一个分区说明表，按照表中的有关信息进行分配;固定式分区分配的存储管理1：重要的函数和数据结构：typedef struct Memory 该结构体定义可用分区链表节点。allocMem（）函数分配内存空间Release（）函数释放内存空间Check（）函数检查用户输入的合法性bool release(MEM *pm, int base, int size)/释放内存空间 MEM *p = pm; if(!check(pm, base ,size) return false; while(p-next) if(base + size next-base) break; p = p-next; if(base = p-base + p-size)/低地址相邻 if(p -next & p-next-base = base + size)/释放区上下都相邻 p-size += size + p-next-size; temp = p-next; p-next = p-next-next; free(temp); else/仅与地地址相邻 p-size += size; else if (p-next & p-next-base = base +size)/仅高地址相邻 p-next-base = base; p-next-size += size; else/释放区上下与空闲区都不相邻 temp = getMEM(); temp-size = size; temp-base = base; temp-next = p-next; p-next = temp; return true; int allocMem(MEM *pm, int size)/分配内存空间 MEM *p = pm; int base; while(p-next) if(p-next-size = size) break; p = p-next; if(!p-next) return -1; if(p-next-size = size)/空闲分区大小刚好等于所需分区 base = p-next-base; p-next = p-next-next; else p-next-size -= size; base = p-next-base; p-next-base += size; return base; 实验效果：实验总结：固定式分配是一种最简单的存储管理方