操作系统试验报告.docx

中南大学操作系统实验报告学 院：_信息科学与工程学院_专业班级： 计算机科学与技术0907班 学 号： 0909092813 姓 名： 周伟航 指导教师： 李玺 2011年12 月 实验_一_进程调度一、实验目的进程调度是处理机管理的核心内容。本实验要求编写和调试一个简单的进程调度程序。通过本实验可以加深理解有关进程控制块、进程队列的概念，并体会和了解优先数和时间片轮转调度算法的具体实施办法。二、实验内容和要求设计一个有 N个进程共行的进程调度程序。进程调度算法：采用最高优先数优先的调度算法（即把处理机分配给优先数最高的进程）和先来先服务算法。每个进程有一个进程控制块（ PCB）表示。进程控制块可以包含如下信息：进程名、优先数、到达时间、需要运行时间、已用CPU时间、进程状态等等。进程的优先数及需要的运行时间可以事先人为地指定（也可以由随机数产生）。进程的到达时间为进程输入的时间。进程的运行时间以时间片为单位进行计算。每个进程的状态可以是就绪 W（Wait）、运行R（Run）、或完成F（Finish）三种状态之一。就绪进程获得 CPU后都只能运行一个时间片。用已占用CPU时间加1来表示。如果运行一个时间片后，进程的已占用 CPU时间已达到所需要的运行时间，则撤消该进程，如果运行一个时间片后进程的已占用CPU时间还未达所需要的运行时间，也就是进程还需要继续运行，此时应将进程的优先数减1（即降低一级），然后把它插入就绪队列等待CPU。每进行一次调度程序都打印一次运行进程、就绪队列、以及各个进程的 PCB，以便进行检查。重复以上过程，直到所要进程都完成为止。三、实验原理及设计方案1、实验原理；假设系统有5个进程，每个进程用一个进程控制块PCB来代表。为每个进程任意确定一个要求运行时间和到达时间。按照进程到达的先后顺序排成一个循环队列。再设一个队首指针指向第一个到达进程的首址。执行处理机调度时，开始选择队首的第一个进程运行。另外，再设一个当前运行进程的指针，指向当前正在运行的进程。进程运行一次后，估计运行时间减一，输出当前运行进程的名字进程运行一次后，以后的调度则将当前指针依此下移一个位置，指向下一个进程，即调整当前运行指针指向该进程的链接指针所指进程，以指示应运行进程。同时还应判断该进程的剩余运行时间是否为零。若不为零，则等待下一轮的运行，若该进程的剩余运行时间为零，则将该进程的状态置为完成态C，并退出循环队列。若就绪队列不空，则重复上述的（5）和（6）步骤直到所有的进程都运行完为止。在所设计的调度程序中，应包含显示或打印语句。显示或打印每次选中的进程的名称及运行一次后队列的变化情况。2、设计方案（1）设计一个有N个进程共行的进程调度程序。每个进程由一个进程控制块PCB表示。进程控制块包括以下信息：进程名，进程优先数，进程需要运行的时间，占用CPU的时间以及进程的状态等。 （2）本调度程序用时间片轮转算法。 （3）编写程序并调试运行。3、相关数据结构的说明本程序采用优先数算法对N个进程进行调度。每个进程处于R，就绪W和完成F三种状态之一，并假定起始状态就是就绪状态W。struct pcb/*创建PCB*/ char name10; /*进程标识*/char state; /*进程状态*/int ntime; /*进程运行时间*/int rtime;struct pcb*link; /*链指针*/*ready=NULL,*p;typedef struct pcb PCB;4、程序流程图5、实验的的核心代码，并附有注释，代码部分分成两栏/*插入进程队列*/void initp() PCB *first,*second;if(ready=NULL)p-link=ready;ready=p;else first=ready;second=first-link;while(second!=NULL)first=first-link;second=second-link;first-link=p;/*建立进程就绪函数*/void running(int tpit)int k=0;while(krtimentime)(p-rtime)+; k+;if(p-rtime=p-ntime) destroy();elsep-state=W;initp();五、实验结果及分析1、运行结果（要求截图）（能动态说明执行结果）简单轮转法 2、实验结果的分析及说明在操作系统中，由于进程总数多于处理机，它们必然竞争处理机。进程调度的功能就是按一定策略、动态地把处理机分配给处于就绪队列中的某一进程并使之执行。根据不同的系统设计目标，可有多种选择某一进程的策略。例如系统开销较少的静态优先数法，适合于分时系统的轮轮法以及UNIX采用的动态优先数反馈法等。本实验是采用优先数法进程调度算法来模拟演示进程调度，编程语言为 C 语言。六、调试总结及心得体会先模拟建立进程就绪链表-置所有进程的到达时间均为0，依PCB链接顺序从第一个进程PCB开始，使进程编号依次为0，1,2,3,4；就绪链表中进程的数量，由常量num 控制；再 模拟建立调度函数-取表头PCB，修改进程执行时间，得到的新时间，即为剩余执行时间，当剩余时间小于或等于0时，将此进程的PCB取出，依完成的先后次序链到完成链表中，记录当前完成进程的完成时间，同时修改就绪链表表头；最后 计算和打印里程调度信息-计算出各进程周转时间及所有进程的平均周转时间。七、心得体会由于网上给出了最高优先数优先的算法，所以照猫画虎，写轮转法起来也很容易不同的算法原理不同，但实现起来确是很像的实验难点主要在于对于算法原理的理解，理解了原理做起程序来很快第一次实验比较简单，没什么好说的。八、 思考题1、 分析不同调度算法的调度策略，比较不同调度算法的优缺点，总结它们的适用范围。先来先服务法先提交的作业先运行，运行一个之后再轮到下一个这种算法实现简单，但是响应不及时，适用于交互性要求不高的系统轮转法轮转法规定由各个准备就绪进程顺次轮流使用CPU，而且每一次使用的时间一般规定为一定值当时间片结束时，就强迫一个现行进程出让CPU。轮转法实现也较简单，而可以保证不会有进程长期得不到响应，缺点是无法照顾到一些特殊进程，早期分时系统采用的就是简单轮转法。最高优先数优先法为每一个进程设置一个优先数，CPU调度时每次选择就绪进程中优先数最大者，让它占用CPU运行。优先数法可划分成静态优先数法和动态优先数法两种：静态优先数法在创建进程时就已确定了该进程的优先数，并且在进程运行的整个过程中该优先数不再动态地改变，那么这种优先数的确定方法便称为静态优先数法。采用静态优先数法简单，而且实现比较容易，但太死板，且适用范围也较小。另外，采用静态优先数法可能会使某些低优先数的进程无限期地等待CPU，不能准确地反映出系统以及进程在运行过程中不断变化的特性。随着进程的推进，进程的许多与优先数确定相关的因素也都将随之发生变化。动态优先数法按照变化着的情况对各个进程的优先数不断适时地做出调整。从以上可以看出该算法优点是即保证了不会有进程长期等待，也能照顾到特殊进程，缺点是每次需重新计算进程优先级，占用较多资源。适用于性能较好的分时系统。实验_二 主存空间的分配与回收一、实验目的熟悉主存的分配与回收。理解在不同的存储管理方式下，如何实现主存空间的分配与回收。掌握动态分区分配方式中的数据结构和分配算法及动态分区存储管理方式及其实现过程。二、实验内容和要求1、设计主存分配和回收。2、要求：采用可变分区存储管理，使用首次适应算法、循环首次适应算法、最佳适应算法三种算法完成设计。3、要求：采用分区说明表进行。设计一个空闲区说明表，设计一个某时刻主存空间占用情况表，作为主存当前使用基础。初始化空闲区和已分配区说明表的值。自己设计一个作业申请队列以及作业完成后的释放顺序，实现主存的分配和回收。把空闲区说明表的变化情况以及各作业的申请、释放情况显示、打印出来。4、实现过程内存分配：动态输入构造空闲区表，并显打印示构造好的空闲区表。键盘接收内存申请尺寸大小。根据申请，实施内存分配，并返回分配所得内存首址。分配完后，调整空闲区表（即扣除分配部分），并显示调整后的空闲区表。若分配失败，返回分配失败信息。内存回收动态输入构造空闲区表，并显示构造好的空闲区表。根据空闲区表，按内存回收的四种情况从键盘接收回收区域的内存首址与大小。回收区域，调整空闲区表（与前面空闲区相连、与后面空闲区相连、与前后空闲区相连则合并、与前后空闲区都不相连则插入该项），并显示调整后的空闲区表。三、实验原理及设计方案1、实验原理；本程序提供两种分区管理法供用户使用，这两种算法是最佳适应算法和首次适应算法。最佳适应算法要求将所有的空闲区，按其大小以递增的顺序形成一空闲区链。这样，第一次找到的满足要求的空闲区，必然是最优的。但该算法会留下许多这样难以利用的小空闲区。首次适应算法要求空闲分区链以地址递增的次序链接。在进行内存分配时，从链首开始顺序查找，直至找到一个能满足其大小要求的空闲分区为止。然后，再按照作业的大小，从该分区中划出一快内存空间分配该请求者，余下的空闲分区仍留在空闲链中。2、设计方案综合设计的可以说是将作业调度和内存分配综合起来。分析程序需求如下设计一个程序，可以由用户初始化空闲表和作业申请队列，程序在这个基础上模拟作业调度及内存分配，并将过程显示。用户初始化空闲表的时候需要指定每一个空闲块的大小及起址，程序根据空闲块起址自动将其插入到空闲表中的相应位置用户初始化申请队列时只需输入作业名及提交时间，所需时间。程序将申请队列中的作业按提交时间排序。模拟多道作业调度，在作业到达提交时间时要求用户该作业指定所需内存数，程序尝试在空闲表中为该作业分配内存，采用首次适应算法，如果分配成功，返回相关信息，如果不成功则将作业加入等待队伍中。在作业到达结束时间时程序将自动回收该作业，并显示相关信息。3、相关数据结构的说明typedef struct node /*设置分区描述器*/ int address,size; struct node *next;RECT;4、程序流程图找到找不到开始初始化空闲表初始化申请队列主界面开始模拟调度调度结束退出用户选择退出主要流程图查找满足作业所需内存数的空闲块是否找到合适块将该块从空闲表中删除加入运行作业队伍中打印分配的内存块提示分配不成功，并将作业放入等待队列中结束分配内存流程图回收函数5、实验的核心代码，并附有注释，代码部分分成两栏/*最佳适应，back1为回收结点的地址*/void acceptment2(RECT *head,RECT *back1) RECT *before,*after; int insert ; insert=0; before=head; after=head-next; if(head-next=NULL) /*如果可利用区表为空*/ head-size=back1-size; head-next=back1; maxblocknum+; back1-next=NULL; else while(after!=NULL) /*与上一块合并*/ if(back1-address=after-size+after-address) before-next=after-next; back-size=after-size+back1-size; free(after); after=NULL; else after=after-next; before=before-next; before=head; after=head-next; while(after!=NULL) if(after-address=back1-size+back1-address) /*与下一块合并*/ back1-size=back1-size+after-size; before-next=after-next; free(after); after=NULL; else before=before-next; after=after-next; before=head;/*将回收结点插入到合适的位置*/ after=head-next; do if(after=NULL|(after-sizeback1-size) before-next=back1; back1-next=after; insert=1; else before=before-next; after=after-next; while(!insert); if(head-sizesize) /*修改最大块值和最大块数*/ head-size=back1-size; maxblocknum+; else if(head-size=back1-size) maxblocknum+; /*分配函数*/RECT *assignment(RECT *head,int application) RECT *after,*before,*assign; assign=(RECT*)malloc(sizeof(RECT); /*分配申请空间*/ assign-size=application; assign-next=NULL; if(applicationhead-size|applicationaddress=-1; /*申请无效*/ else before=head; after=head-next; while(after-sizenext; after=after-next; if(after-size=application) /*结点大小等于申请大小则完全分配*/ if(after-size=head-size) maxblocknum-; before-next=after-next; assign-address=after-address; free(after); else if(after-size=head-size) maxblocknum-; after-size=after-size-application; /*大于申请空间则截取相应大小分配*/ assign-address=after-address+after-size; if(tolower(way)=b)/*如果是最佳适应，将截取后剩余结点重新回收到合适位置*/ before-next=after-next; back=after; acceptment2(head,back); if(maxblocknum=0) /*修改最大数和头结点值*/ before=head; head-size=0; maxblocknum=1; while(before!=NULL) if(before-sizehead-size) head-size=before-size; maxblocknum=1; else if(before-size=head-size) maxblocknum+; before=before-next; assign1=assign; return assign1; /*返回分配给用户的地址*/void acceptment1(RECT *head,RECT *back1)/*首先适应*/ RECT *before,*after; int insert; before=head; after=head-next; insert=0; while(!insert) /*将回收区插入空闲区表*/ if(after=NULL)| (back1-addressaddress)& (back1-address=before-address) before-next=back1; back1-next=after; insert=1; else before=before-next; after=after-next; if(back1-address=before-address+before-size)/*与上一块合并*/ before-size=before-size+back1-size; before-next=back1-next; free(back1); back1=before; if(after!=NULL&(after-address=back1-address+back1-size) /*与下一块合并*/ back1-size=back1-size+after-size; back1-next=after-next; free(after); if(head-sizesize) /*修改最大块值和最大块个数*/ head-size=back1-size; maxblocknum=1; else if(head-size=back1-size) maxblocknum+;/*检查回收块的合法性，back1为要回收的结点地址*/int backcheck(RECT *head,RECT *back1) RECT *before,*after; int check=1; if(back1-addresssizenext; while(before!=NULL)&check)/*地址不能和空闲区表中结点出现重叠*/ if(back1-addressaddress) &(back1-address+back1-sizebefore-address) |(back1-address=before-address)&(back1-addressaddress+before-size) check=0; els