Linux操作系统专业课程设计方案报告基于Linux的进程调度模拟程序.docx

河南中医学院linux操作系统课程设计汇报题目：基于Linux进程调度模拟程序所在院系： 信息技术学院 专业年级： 级 计算机科学和技术 完成学生： 180021 郭姗 指导老师： 阮 晓 龙 完成日期： 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 + 请按任意键继续. . . */ 5.2.2结果分析输入a、b、c、d、e，是五个进程名；0、1、2、3、4为各个进程抵达时间；4、3、5、2、4是各个进程占用CPU时间；，当a进程结束时，b进程才是运行状态，以这类推，各个进程处于完成F（finish）状态时间是4、7、12、14、18.，从而能够看出各个进程是根据进程进入就绪队列前后次序调度并分配处理机实施，优异入就绪队列进程，先分配处理机运行。一旦一个进程占有了处理机，它就一直运行下去，直到该进程完成工作或因为等候某事件发生而不能继续运行时才释放处理机。 不过，a进程运行时间是4，结束时间也是4；而d进程运行时间是2，结束时间是14，说明先来先服务有利于长作业进程，而不利于短作业进程。这是因为若一个长作业先抵达系统，就会使很多短作业等候很长时间，从而引发很多短作业用户不满。有利于CUP繁忙作业，不利于I/O繁忙作6. 课题研究结论总而言之，此次课题经过采取最高优先数优先调度算法（即把处理机分配给优先数最高进程）、先来先服务算法，对进程调度进行模拟试验，并分析试验数据，得到以下结论:1、最高优先数优先调度算法进入运行状态依据是：优先数越大就先运行；先来先服务算法进入运行状态依据是：进入就绪队列前后次序，优异就先运行。2、最高优先数优先调度算法调度方法是：抢占式和非抢占式；先来先服务算法调度方法是：非抢占式。3、最高优先数优先调度算法吞吐量高；先来先服务算法吞吐量不突出。4、最高优先数优先调度算法响应时间很好；先来先服务算法响应时间不突出。5、最高优先数优先调度算法系统开销大；先来先服务算法系统开销小。6、最高优先数优先调度算法对进程作用：有利于紧迫作业；先来先服务算法对进程作用：有利于长作业（进程），不利于短作业，有利于CUP繁忙作业，不利于I/O繁忙作业 7. 总结正文：此次课题关键研究