Word版可编辑-Linux操作系统课程设计报告基于Linux的进程调度模拟程序精心整理.docx

河南中医学院linux操作系统课程设计报告题目：基于Linux的进程调度模拟程序所在院系： 信息技术学院 专业年级： 2011级 计算机科学与技术 完成学生： 2011180021 郭姗 指导教师： 阮 晓 龙 完成日期： 201X 年 06 月 22 日目 录1. 课程设计题目概述32. 研究内容与目的43. 研究方法54. 研究报告65. 测试报告/实验报告76. 课题研究结论87. 总结91、课程设计题目概述随着Linux系统的逐渐推广，它被越来越多的计算机用户所了解和应用. Linux是一个多任务的操作系统，也就是说，在同一个时间内，可以有多个进程同时执行。如果读者对计算机硬件体系有一定了解的话，会知道我们大家常用的单CPU计算机实际上在一个时间片断内只能执行一条指令，那么Linux是如何实现多进程同时执行的呢？原来Linux使用了一种称为进程调度（process scheduling）的手段，首先，为每个进程指派一定的运行时间，这个时间通常很短，短到以毫秒为单位，然后依照某种规则，从众多进程中挑选一个投入运行，其他的进程暂时等待，当正在运行的那个进程时间耗尽，或执行完毕退出，或因某种原因暂停，Linux就会重新进行调度，挑选下一个进程投入运行。因为每个进程占用的时间片都很短，在我们使用者的角度来看，就好像多个进程同时运行一样了。 本文就是对进程调度进行研究、实验的。本文首先对Linux系统进行了简要的介绍, 然后介绍了进程管理的相关理论知识。其次，又介绍最高优先数优先的调度算法（即把处理机分配给优先数最高的进程）、先来先服务算法的相关知识，并对进程调度进行最高优先数优先的调度算法和先来先服务算法模拟实验，并对比分析两种算法的优缺点，从而加深对进程概念和进程调度过程/算法的理解设计目的：在多道程序和多任务系统中，系统内同时处于就绪状态的进程可能有若干个。也就是说能运行的进程数大于处理机个数。为了使系统中的进程能有条不紊地工作，必须选用某种调度策略，选择某一进程占用处理机。使得系统中的进程能够有条不紊的运行，同时提高处理机的利用率以及系统的性能。所以设计模拟进程调度算法（最高优先数优先的调度算法、先来先服务算法），以巩固和加深处理进程的概念，并且分析这两种算法的优缺点。关键词：linux 进程调度 调度算法2. 研究内容与目的操作系统由四大功能模块组成：进程管理、存储器管理、设备管理和文件管理，进程管理是其中最重要的一个模块。本文主要研究最高优先数优先的调度算法、先来先服务算法这两种调度算法，并且分析比较这两种算法的优缺点。目的：进程是操作系统中最重要的概念，也是学习操作系统的关键。通过本次课程设计，要求理解进程的实质和进程管理的机制。掌握进程调度的工作流程以及进程调度的算法，并且分析比较这两种算法的优缺点。3. 研究方法3.1研究方法3.1.1查找资料通过查找资料了解到：（1）优先数调度算法简介优先数调度算法常用于批处理系统中。在进程调度中，每次调度时，系统把处理机分配给就绪队列中优先数最高的进程。它又分为两种：非抢占式优先数算法和抢占式优先数算法在非抢占式优先数算法下，系统一旦把处理机分配给就绪队列中优先数最高的进程后，这个进程就会一直运行，直到完成或发生某事件使它放弃处理机，这时系统才能重新将处理机分配给就绪队列中的另一个优先数最高的进程。在抢占式优先数算法下，系统先将处理机分配给就绪队列中优先数最高的进程度让它运行，但在运行的过程中，如果出现另一个优先数比它高的进程，它就要立即停止，并将处理机分配给新的高优先数进程。（2）先来先服务算法如果早就绪的进程排在就绪队列的前面，迟就绪的进程排在就绪队列的后面，那么先来先服务(FCFS: first come first service)总是把当前处于就绪队列之首的那个进程调度到运行状态。也就说，它只考虑进程进入就绪队列的先后，而不考虑它的下一个CPU周期的长短及其他因素。基本思想：先来先服务的作业调度算法：优先从后备队列中，选择一个或多个位于队列头部的作业，把他们调入内存，分配所需资源、创建进程，然后放入“就绪队列”先来先服务的进程调度算法：从“就绪队列”中选择一个最先进入队列的进程，为它分配处理器，使之开始运行原理：按照进程进入就绪队列的先后顺序调度并分配处理机执行。先来先服务调度算法是一种不可抢占的算法，先进入就绪队列的进程，先分配处理机运行。一旦一个进程占有了处理机，它就一直运行下去，直到该进程完成工作或者因为等待某事件发生而不能继续运行时才释放处理机。、系统只要有按FIFO规则建立的后备作业队列或就绪进程队列即可，就是一个作业控制块JCB或进程控制块PCB加入队列时加在相应队列末尾。、调度退出队列时从相应队列首开始顺序扫描，将相关的JCB或PCB调度移出相应队列。3.2实验方法3.2.1模拟法 根据最高优先数优先的调度算法、先来先服务算法的进程调度机制的流程，进行模拟这两种算法的实验。3.2.2控制法进行实验时，输入进程名、优先数、到达时间、需要运行时间、已用CPU时间、进程状态。3.2.3观察法观察实验的结果，分析进程调度流程。3.2.4比较法通过观察实验结果，比较两种调度算法的优缺点。3.3可行性分析（课题理论上的要求、实践的可操作性、本人能力和现实条件（相关案例、资料等）的许可等内容）3.3.1环境运行在VMware-workstation-full-10.0.0-1295980上，导入CentOS操作系统，在CentOS操作系统上运行。CentOS操作系统是Linux发行版之一，它是来自于Red Hat Enterprise Linux依照开放源代码规定释出的源代码所编译而成。相对于其他 Linux 发行版，其稳定性值得信赖。因为CentOS操作系统安装了gcc编译器，能编译C语言。3.3.2实践的可操作性 在对linux进程调度机制以及调度算法进行深入分析后，根据对于最高优先数优先的调度算法采用最高优先数算法的动态优先数法则控制进程：系统把处理机分配给就绪队列中优先数最高的进程后，如果运行一个时间片后，进程的已占用CPU时间已达到所需要的运行时间，则撤消该进程，如果运行一个时间片后进程的已占用CPU时间还未达所需要的运行时间，也就是进程还需要继续运行，此时应将进程的优先数减1（即降低一级），然后把它插入就绪队列等待CPU，而先来先服务是从“就绪队列”中选择一个最先进入队列的进程，为它分配处理器，使之开始运行而制定实验方案的。 3.3.3本人能力 虽然我对linux的进程调度方面的知识还有很多不知道的知识，但我是在不断学习的 ，遇到不懂得就通过查资料或请教他人的方法，不断地学习。4. 研究报告4.1最高优先数优先的调度算法（抢占式）4.1.1实验原理1、进程调度算法：采用最高优先数优先的调度算法（即把处理机分配给优先数最高的进程）。 2、每个进程有一个进程控制块（PCB）表示。进程控制块可以包含如下信息：进程名、优先数、需要运行时间、已用CPU时间、进程状态等等。 3、进程的优先数及需要的运行时间事先人为地指定。 4、 每个进程的状态可以是就绪 W（Wait）、运行R（Run）、或完成F（Finish）三种状态之一。 5、进程的运行时间以时间片为单位进行计算。 6、 就绪进程获得CPU后都只能运行一个时间片。用已占用CPU时间加1来表示。 7、采用最高优先数算法的动态优先数法则控制进程：如果运行一个时间片后，进程的已占用CPU时间已达到所需要的运行时间，则撤消该进程，如果运行一个时间片后进程的已占用CPU时间还未达所需要的运行时间，也就是进程还需要继续运行，此时应将进程的优先数减1（即降低一级），然后把它插入就绪队列等待CPU。 8、每进行一次调度程序都打印一次运行进程、就绪队列、以及各个进程的PCB，以便进行检查。 9、 重复以上过程，直到所要进程都完成为止。4.1.2实验内容 1、数据结构（1）进程控制块结构PCB：是struct定义的结构体，定义如下：typedef struct pcbchar qname20;/*进程名*/char state; /*进程状态*/int super; /*进程优先级*/int ndtime; /*进程需要运行的时间*/int runtime; /*进程已运行的时间*/int cpu; /*进程当前获得的时间片大小*/PCB;（2） 队列结点Node，结点储存PCB信息，定义如下：typedef struct nodePCB data; /*结点数据*/struct node *next; /*指向下一结点的指针*/Node;（3）由队列结点Node扩展的队列Queue,定义如下：typedef struct queueNode *front;/*队首*/Node *rear;/*队尾*/Queue;2相关函数（1）判断一个队列q是否为空的函数int is_empty(Queue *q);（2）将进程控制块x加入队列q的函数void enqueue(PCB x,Queue *q);（3）删除队列q的队首进程，将其值赋给x并修改状态的函数void dequeue(PCB *x,Queue *q);该函数将队列q的队首进程删除，由于可能该进程未运行完毕，需进入下一优先级队列， 所以先修改其结构体内成员变量：已运行时间为上次已运行时间加上这次获得的cpu时间；优先级减1（若该进程已是最低优先级，则将在主控过程中恢复）；下次获得的时间片为这次的时间片加1。然后将修改后的进程赋给一个临时PCB变量x，以便将x插入下一优先级队列。 （4）主函数利用上述的数据结构和函数实现模拟进程调度。3. 进程产生模拟通过标准输入模拟产生进程：先要求输入进程数目，再依次输入各个进程的进程名、进程优先数、进程需要运行的时间。4.1.3参考代码#include#include#include#include#define PCB_LEN sizeof(PCB)#define NODE_LEN sizeof(Node)#define QUEUE_LEN sizeof(Queue)/*进程控制块结构PCB*/typedef struct pcbchar qname20;/*进程名*/ char state; /*进程状态*/int super; /*进程优先级*/int ndtime; /*进程需要运行的时间*/int runtime; /*进程已运行的时间*/int cpu; /*进程当前获得的时间片大小*/PCB;/*队列结点，结点储存PCB信息*/typedef struct nodePCB data; struct node *next;Node;/*实现进程控制块的队列*/typedef struct queueNode *front;Node *rear;Queue;/*判断队列是否为空*/int is_empty(Queue *q)if(q-front)return 0;elsereturn 1;/*将进程控制块x加入队列q*/void enqueue(PCB x,Queue *q) Node *p=(Node *)malloc(NODE_LEN);(p-data).state=x.state;(p-data).super=x.super;(p-data).ndtime=x.ndtime;(p-data).runtime=x.runtime;(p-data).cpu=x.cpu;strcpy(p-data).qname,x.qname);p-next=0;if(q-front)q-rear-next=p;elseq-front=p;q-rear=p;/*删除队列q的队首进程，将其值赋给x并修改状态*/void dequeue(PCB *x,Queue *q)Node *p=(Node *)malloc(NODE_LEN); if(is_empty(q)return;/*进入下一优先级队列之前修改状态*/x-state=W;/*状态改为就绪*/strcpy(x-qname,(q-front-data).qname);/*已运行时间为上次已运行时间加上这次获得的cpu时间*/x-runtime=(q-front-data).runtime+(q-front-data).cpu;/*优先级减1，若该进程已是最低优先级，则将在主控过程中恢复*/x-super=(q-front-data).super-1;x-ndtime=(q-front-data).ndtime;/*下次获得的时间片为这次的时间片加1*/x-cpu=(q-front-data).cpu+1;p=q-front;q-front=q-front-next;free(p);/*主控过程*/void main()Queue *queue=NULL;/*设置就绪队列数组*/Node *wait=(Node *)malloc(NODE_LEN);PCB x;int numberOFcourse,i,j,super,time;int hight=0,num=0;int temp_ndtime,temp_runtime,temp_cpu;char name20;printf(n请输入进程总个数?);scanf(%d,&numberOFcourse);/*为队列数组开辟空间，每个数组表示不同的优先级队列*/queue=(Queue *)calloc(numberOFcourse,QUEUE_LEN);/*输入各进程信息并初始化，并将其加入相应的优先级队列*/for(i=0;ihight)hight=super;printf(n输入进程运行时间：);scanf(%d,&time);strcpy(x.qname,name);x.state=W; x.super=super;x.ndtime=time;x.runtime=0;x.cpu=1;enqueue(x,&queuesuper-1);printf(nn);/*进程调度过程*/for(i=hight-1;i=0;i-)/*从最高优先级队列开始调度进程，直到该队列为空，则调度下一优先级队列*/while(!is_empty(&queuei)num+;/*调度次数*/printf(按任一键继续.n);getch();printf(The execute number:%dnn,num);/*打印正在运行进程*/(queuei.front)-data).state=R;printf(*当前工作的进程是：%sn,(queuei.front)-data).qname);printf(qname state super ndtime runtimen);printf(%s,(queuei.front)-data).qname); printf(R);printf(%d,(queuei.front)-data).super); printf(%d,(queuei.front)-data).ndtime);printf(%dnn,(queuei.front)-data).runtime);/*计算一个进程运行一个时间片后，还需要运行的时间temp_time*/ temp_ndtime=(queuei.front)-data).ndtime;temp_runtime=(queuei.front)-data).runtime; temp_cpu=(queuei.front)-data).cpu;temp_ndtime=temp_ndtime-temp_runtime-temp_cpu;/*若该进程已运行完毕*/if(temp_ndtimedata).qname); (queuei.front)-data).state=F; dequeue(&x,&queuei);/*若该进程未运行完毕*/else dequeue(&x,&queuei);/*将其删除出当前队列*/*若原优先级不是最低优先级，则插入下一优先级队列*/if(i0)enqueue(x,&queuei-1);/*若原优先级是最低优先级，则插入当前队列末尾*/else/*由于删除操作中将优先级减1，所以在此恢复*/x.super=x.super+1; enqueue(x,&queuei);/*打印就绪队列状态*/ printf(*当前就绪队列状态为：n);for(j=i;j=0;j-)if(queuej.front)wait=queuej.front;while(wait)printf(qname state super ndtime runtimen); printf(%s,(wait-data).qname); printf(W); printf(%d,(wait-data).super); printf(%d ,(wait-data).ndtime); printf(%dnn,(wait-data).runtime); wait=wait-next; printf(n);/*结束*/printf(进程已经全部完成n);free(wait);free(queue);getch();4.2先来先服务算法4.2.1实验原理先来先服务调度算法按照进程进入就绪队列的先后顺序调度并分配处理机执行。先来先服务调度算法是一种不可抢占的算法，先进入就绪队列的进程，先分配处理机运行。一旦一个进程占有了处理机，它就一直运行下去，直到该进程完成工作或者因为等待某事件发生而不能继续运行时才释放处理机。4.2.2参考代码#include #include #include using namespace std; #define MAX 10 char processMAX=; /进程名 int arrivetimeMAX;/达到时间 int servicetimeMAX;/服务时间 int finishtimeMAX; /完成时间 int turnovertimeMAX;/周转时间 double avgturnovertime; /平均周转时间 double powertimeMAX; /带权周转时间 double avgpowertime; /平均带权周转时间 int init(); void FCFS(); void output(); void showsingle(int* arr,int len); /初始化，并返回进程数 int init() cout 输入进程队列名(用单个字母表示一个进程,字母间用tab间隔) endl; int i=0; while(iMAX) cin.get(processi); if(processi= | processi=/t) continue; if(processi=q | processi=/n) processi=/0; break; i+; int len=strlen(process); cout 依次输入进程到达时间(时间之间用tab间隔) endl; for(int ix=0; ix arrivetimeix; cout 依次输入服务时间(时间之间用tab间隔) endl; for(ix=0; ix servicetimeix; return len; void FCFS(int len) /完成时间的计算 for(int ix=0; ixlen; ix+) finishtimeix=accumulate(servicetime,servicetime+ix+1,0); /周转时间计算 for(ix=0; ixlen; ix+) turnovertimeix=finishtimeix-arrivetimeix; avgturnovertime=accumulate(turnovertime,turnovertime+len,0)*1.0/len; /带权周转时间计算 for(ix=0; ixlen; ix+) powertimeix=turnovertimeix*1.0/servicetimeix; /平均带权周转时间 double tmptotal=0.0; for(ix=0; ixlen; ix+) tmptotal+=powertimeix; avgpowertime=tmptotal/len; void output() cout endlendl; cout+endl; int len=strlen(process); /显示进程序列 for(int ix=0; ixlen; ix+) cout processix /t; cout endl; /显示到达时间序列 showsingle(arrivetime,len); /显示服务时间序列 showsingle(servicetime,len); cout endlendl; /显示完成时间序列 showsingle(finishtime,len); /显示周转时间序列 showsingle(turnovertime,len); cout 平均周转时间 : avgturnovertime endl; /显示带权周转时间序列 for(ix=0; ixlen; ix+) cout powertimeix /t; cout endl; cout 平均带权周转时间: avgpowertime endl; cout +endl; /对int类型的数组进行格式化输出 void showsingle(int* arr,int len) for(int ix=0; ixlen; ix+) cout arrix /t; cout endl; int main() cout /t/t|本程序是先来先服务算法| endl; int len = init(); FCFS(len); output(); system(PAUSE); return 0; 5. 测试报告/实验报告5.1最高优先数优先的调度算法5.1.1实验结果【输入输出样例】请输入进程总个数?4进程号 NO.0输入进程名：aa输入进程优先数：2输入进程运行时间：2进程号 NO.1输入进程名：vv输入进程优先数：3输入进程运行时间：2进程号 NO.2输入进程名：rr输入进程优先数：1输入进程运行时间：3进程号 NO.3输入进程名：kk输入进程优先数：2输入进程运行时间：1按任一键继续.The execute number:1*当前工作的进程是：vvqname state super ndtime runtimevv R 3 2 0*当前就绪队列状态为：qname state super ndtime runtimeaa W 2 2 0qname state super ndtime runtimekk W 2 1 0qname state super ndtime runtimevv W 2 2 1qname state super ndtime runtimerr W 1 3 0按任一键继续.The execute number:2*当前工作的进程是：aaqname state super ndtime runtimeaa R 2 2 0*当前就绪队列状态为：qname state super ndtime runtimekk W 2 1 0qname state super ndtime runtimevv W 2 2 1qname state super ndtime runtimerr W 1 3 0qname state super ndtime runtimeaa W 1 2 1按任一键继续.The execute number:3*当前工作的进程是：kkqname state super ndtime runtimekk R 2 1 0进程kk已完成*当前就绪队列状态为：qname state super ndtime runtimevv W 2 2 1qname state super ndtime runtimerr W 1 3 0qname state super ndtime runtimeaa W 1 2 1按任一键继续.The execute number:4*当前工作的进程是：vvqname state super ndtime runtimevv R 2 2 1进程vv已完成*当前就绪队列状态为：qname state super ndtime runtimerr W 1 3 0qname state super ndtime runtimeaa W 1 2 1按任一键继续.The execute number:5*当前工作的进程是：rrqname state super ndtime runtimerr R 1 3 0*当前就绪队列状态为：qname state super ndtime runtimeaa W 1 2 1qname state super ndtime runtimerr W 1 3 1按任一键继续.The execute number:6*当前工作的进程是：aaqname state super ndtime runtimeaa R 1 2 1进程aa已完成*当前就绪队列状态为：qname state super ndtime runtimerr W 1 3 1按任一键继续.The execute number:7*当前工作的进程是：rrqname state super ndtime runtimerr R 1 3 1进程rr已完成*当前就绪队列状态为：进程已经全部完成5.1.2结果分析本程序利用标准输入输出模拟了进程调度过程。输入各个进程的优先级和需要运行的时间等信息，输出给出了每进行一次调度的运行进程、就绪队列、以及各个进程的 PCB信息，每当一个进程完成运行，输出该进程已完成的信息，最后当所有进程都完成后给出所有进程都完成的信息。因为刚开始vv的优先级高，所以它先抢占CPU，运行一个时间单位后，vv的优先级数减少1，此时vv的优先级与aa、kk相等，但比rr大，所以vv排在就绪队列kk后面，aa处于运行状态；后面的也是这样分析。从而可以看出：刚开始优先数大的先运行，当进程运行一个时间片后，进程的已占用CPU时间已达到所需要的运行时间，则撤消该进程，如果运行一个时间片后进程的已占用CPU时间还未达所需要的运行时间，也就是进程还需要继续运行，此时应将进程的优先数减1（即降低一级），且此时有和它相等的优先数或比它大的优先数，则把它插入就绪队列等待CPU。 通过以上述数据测的最高优先数算法，可以看出这种算法的优点是可使资源利用率得以提高，公平性好，缺点是系统开销大，实现比较复杂。5.2先来先服务算法5.2.1实验结果/*running result: |本程序是先来先服务算法| 输入进程队列名(用单个字母表示一个进程,字母间用tab间隔) a b c d e 依次输入进程到达时间(时间之间用tab间隔) 0 1 2 3 4 依次输入服务时间(时间之间用tab间隔) 4 3 5 2 4 + a b c d e 0 1 2 3 4 4 3 5 2 4 4 7 12 14 18 4 6 10 11 14 平均周转时间 :9 1 2 2 5.5 3.5 平均带权周转时间:2.8 + 请按任意键继续