模拟Linux操作系统下处理机调度实验报告.docx

处理机调度 一、实验目的： 1、了解Linux下 Emacs编辑器的使用方法，掌握各种常用的键盘操作命令； 2、理解并掌握处理机调度算法。 二、实验内容及要求： 在采用多道系统的设计程序中，往往有若干进程同时处于就绪状态。当就绪状态进程数 大于处理机数时，就必须按照某种策略来决定哪些进程优先占用处理机。本实验模拟在单处 理机情况下处理机调度。 1、优先调度算法实现处理机的调度： 设计思路： 1)每个进程用一个进程控制块PCB来代表，进程控制块包括进程名(进程的标识)、指针(按优 先数的大小把进程连成队列，用指针指出下一个进程的进程控制块首地址，最后一个进程中 的指针为、要求运行时间、优先数、状态(就绪、结束)； 2)每次运行处理机调度程序前，为每个进程确定它的 的指针为 要求运行时间 ； 3)把给定的进程按优先数的大小连成队列，用一单元指出队首进程； 4)每模拟执行一次进程，优先数减一，要求运行时间减一； 5)如果要求运行的时间>=0，再将它加入队列（按优先数的大小插入，重置队首标志）；如果 要求运行的时间=0，那么把它的状态修改为结束，且推出队列； 6)若就绪队列不为空，重复上述，直到所有的进程都结束； 7)程序有显示和打印语句，每次运行后显示变化。 2、按时间片轮转法实现处理机调度： 设计思路： 1)每个进程用一个进程控制块PCB来代表，进程控制块包括进程名(进程的标识)、指针(把进 程连成循环队列，用指针指出下一个进程的进程控制块首地址，最后一个进程中的指针指出 第一个进程的进程控制块首地址)、已运行时间、状态(就绪、结束)； 每次运行处理机调度程序前，为每个进程确定它的 要求运行时间 2)每次运行处理机调度程序前，为每个进程确定它的 要求运行时间 ； 3)用指针把给定的进程按顺序排成循环队列，用另一标志单元记录轮到的进程； 4)每模拟运行一次进程，已运行时间加一； 5)进程运行一次后，把该进程控制块的指针值送到标志单元，以指示下一个轮到的进程。若 该进程要求运行时间已运行时间，未执行结束，待到下一轮再执行；若要求运行时间=已运 行时间，状态改为结束，退出队列； 6)若就绪队列不为空，重复步骤四和五； 7)程序有显示和打印语句，每次运行后显示变化。 三、程序设计： 1、优先数调度算法： /*我的思路：先主函数输入要进行调度的进程数，然后调用函数create(),把进程的信息输入， 再调用函数insert(),把输入的函数按照优先数的大小排成链表，然后调用函数prio()实现优先 数调度*/ #include <stdio.h> #include <stdlib.h> #include <string.h> typedef struct node char name10; /*进程名*/ int prio; /*优先数*/ int cputime; /*占用 cpu时间*/ int needtime; /*要求运行时间*/ char state; /*状态*/ struct node *next; /*指针*/ PCB; PCB *ready,*run,*finish; /*就绪 执行 结束指针*/ int N; void prt() /*输出函数，可以方便看到进程执行的演示*/ PCB *p; NAME CPUTIME NEEDTIME PRIORITY SSTTAATTUUSS if(run!=NULL) >state); /*输出执行的进程的信息*/ p=ready; while(p!=NULL) /*输出就绪进程的信息*/ p=p->next; p=finish; while(p!=NULL) /*输出结束队列的信息*/ p=p->next; getchar(); /*使用 getchar()函数可以让输出时停留画面，等待人按回车继续*/ void insert(PCB *q) /*插入新进程，把进程按优先数大小排序*/ PCB *p1,*s,*r; int b; s=q; /*指针s指向新要插入的进程*/ p1=ready; /*指针p1指向原来的进程队列的队首*/ r=p1; /*使用指针 r是指向p1前面的进程*/ b=1; while(p1!=NULL)&&b) if(p1->prio>=s->prio) r=p1; p1=p1->next; /*新进程的优先数小，则p1 else b=0; 指向下一个进程继续比*/ if(r!=p1) r->next=s; s->next=p1; /*新进程找到位置，插在 r和p1之间*/ else s->next=p1; ready=s; /*新进程的优先数最大，插在队首，并 void create() 修改就绪队首ready指针*/ PCB *p; int i; finish=NULL; ready=NULL; run=NULL; finish=NULL; /*输入进程名、和*/ for(i=0;i<N;i+) p=malloc(sizeof(PCB); /*为新进程开辟空间*/ /*输入进程名*/ /*输入进程要求运行时间*/ /*输入进程优先数*/ p->cputime=0; p->state='W' /*表示就绪队列中未在队首先执行，但也是就绪状态*/ if (ready!=NULL) insert(p); /*就绪队首不为NULL，插入新进程*/ else p->next=ready; ready=p; /*否则先插在NULL前*/ Display is going to start: prt(); run=ready; /*队列排好，run指向就绪队列队首*/ ready=ready->next; /*ready指向下一个进程，这样当进程执行时如果优先数小于其 他的进程，应该先进行优先数最大的进程*/ run->state='R' /*队首进程的状态为就绪*/ void prio() while(run!=NULL) run->cputime=run->cputime+1; /*运行一次cpu占用时间加一*/ run->needtime=run->needtime- 1/;* 运行一次要求运行时间减一*/ run->prio=run->prio-1; /*运行一次优先数减一*/ if(run->needtime=0) /*若要求运行时间为0时*/ run->next=finish; /*退出队列*/ finish=run; /*finish为结束进程的队列 */ run->state='E' /*修改状态为结束*/ run=NULL; /*释放run指针*/ if (ready!=NULL) /*创建新就绪队列的头指针*/ run=ready; run->state='R' ready=ready->next; else if(ready!=NULL)&&(run->prio<ready->prio) /*队首进程的优先数比它下一个小，且下一个进程不为NULL时执行*/ run->state='W' run->next=NULL; /*队首进程退出进程队列*/ insert(run); /*在进程队列中重新插入原来的队首进程*/ run=ready; /*重新置就绪队列的头指针*/ run->state='R' ready=ready->next; prt(); void main() create(); /*模拟创建进程，并输入相关信息*/ prio(); /*优先数调度算法*/ 2、时间片轮转法： #include <stdio.h> #include <stdlib.h> #include <string.h> typedef struct node char name10; /*进程名*/ int count; /*计数器，判断是否=时间片的大小*/ int cputime; /*占用 cpu时间*/ int needtime; /*要求运行时间*/ char state; /*状态*/ struct node *next; /*指针*/ PCB; PCB *ready,*run,*finish,*tail; /*就绪 执行 结束 尾指针*/ int N，round; void prt() /*输出函数，可以方便看到进程执行的演示*/ /*略 同优先数法*/ void insert(PCB *q) /*在队尾插入新的进程*/ tail->next=q; tail=q; q->next=NULL; void create() PCB *p; int i; finish=NULL; ready=NULL; run=NULL; finish=NULL; /*输入进程名、和*/ for(i=0;i<N;i+) p=malloc(sizeof(PCB); /*为新进程开辟空间*/ /*输入进程名*/ /*输入进程要求运行时间*/ p->cputime=0; p->state='W' /*表示就绪队列中未在队首先执行，但也是就绪状态*/ if (ready!=NULL) insert(p); /*就绪队首不为NULL，插入新进程*/ else p->next=ready; ready=p; tail=p; Display is going to start: prt(); run=ready; /*队列排好，run指向就绪队列队首*/ ready=ready->next; /*ready指向下一个进程*/ run->state='R' /*队首进程的状态为就绪*/ void count() while(run!=NULL) run->cputime=run->cputime+1; /*运行一次cpu占用时间加一*/ run->needtime=run->needtime- 1/;* 运行一次要求运行时间减一*/ run->count=run->count+1; /*运行一次计数器加一*/ if(run->needtime=0) /*若要求运行时间为0时*/ run->next=finish; /*退出队列*/ finish=run; /*finish为结束进程的队列 */ run->state='E' /*修改状态为结束*/ run=NULL; /*释放run指针*/ if (ready!=NULL) /*创建新就绪队列的头指针*/ run=ready; run->state='R' ready=ready->next; else if(run->count=round) /*如果时间片到*/ run->count=0; /*计数器置0*/ if(ready!=NULL) /*如就绪队列不空*/ run->state='W' insert(run); /*在进程队列中重新插入原来的队首进程*/ run=ready; /*重新置就绪队列的头指针*/ run->state='R' ready=ready->next; prt(); void main() /*输入时间片的大小，不应太大*/ create(); /*模拟创建进程，并输入相关信息*/ count(); /*优先数调度算法*/ 四、程序运行的初值及执行结果： 1、优先数调度算法： 以下是输出的结果（符合优先数调度）： 2、时间片轮转法调度算法： 以下是输出结果（符合时间片轮转法调度）： 五、结果分析： 在优先数调度中，程序首先输出各个进程的初始值，按回车之后，由于进程p1的优先数 最大，排在就绪队列的队首，首先执行，执行一次后优先数减一，要求运行时间减一，cpu 占用时间加一，再和其他的进程比较优先数，还是最大，继续执行，再执行一次后优先数小 ，按这样的顺序，在就绪队列队首的进程状态为，不 于进程p3，所以下一个执行的是p3，按这样的顺序，在就绪队列队首的进程状态为 在队首的就绪进程状态为，结束的进程状态为 直到所有进程状态都为， 在队首的就绪进程状态为 结束的进程状态为，一直执行，直到所有进程状态都为 调度完成。 在时间片轮转法调度中，先设置了时间片的大小为1，然后各个进程按循环队列依次执 行，每执行一次，要求运行时间减一，若等于0了了，则则状状态态改改为为，退出队列，直到所有进 程的状态为，调度完成。 程的状态为