实 验 报 告
课程名称：实验名称：学 号：学生姓名：班 级：指导教师：评 分：
实验日期：
操作系统 处理机管理 2012年 11月 19 日
1、实验目的： 在多道程序或多任务系统中，系统同时处于就绪态的进程有若干个，也就是说能运行的进程数远远大于处理机个数。为了使系统中的各进程能有条不紊地运行，必须选择某种调度策略，以选择一进程占用处理机。设计模拟单处理机调度的算法，巩固和加深处理机调度的概念。 2、实验要求 （1）设计一个按优先级调度的算法 （2）按时间片轮转法进行CPU调度 3、实验环境 硬件： CPU ：AMD QL64 内存： 2GB显卡：ATI 4570硬盘：日立250G 软件：Windows 2000/XP。 开发工具：VC++6.0。 4、实验内容 1）实现原理 （1）设计一个按优先级调度的算法 进程的优先数由用户自己指定或程序任意设定，且优先级数越低，优先级越高。调度时，总是选择优先级最高的进程运行。 为了调度方便，设计一个指针指向5个进程排成的就绪队列的第一个进程，另外再设计一个当前运行进程指针，指向当前正运行的进程。 为了采用动态优先级调度，进程每运行一次，其优先级减1。进程运行最后一次，若剩余的运行时间部位0，且优先级低于就绪队列的进程的优先级，则选择一个高优先级进程抢占CPU；若剩余时间为0，则把它的状态改为完成状态（C），并撤出就绪队列。 若就绪队列部位空，则重复以上操作，直到所有进程为完成状态。 在所涉及的程序中，应有显示或打印语句，以显示或打印每次被选中进程的进程名以及运行一次后进程的变化，就绪队列中的个进程排队情况等。 为5个进程任意确定一组“优先级”和“要求运行时间”，启动处理机调度程序，显示或打印为此选中的进程名以及进程控制块的动态变化过程：包括进程已运行时间，剩余时间，就绪队列中的进程等。 优先级调度算法：按照进程的优先级大小来调度。使高优先级进程或线程得到优先的处理的调度策略称为优先级调度算法。进程的优先级可以由系统自动地按一定原则赋给它，也可由系统外部来进行安排 但在许多采用优先级调度的系统中，通常采用动态优先数策略。即一个进程的优先级不是固定的，往往是随许多因素的变化而变化。尤其随作业（进程）的等待时间，已使用的处理器时间或其他系统资源的使用情况而定，以防止低优先级进程或线程长期饥饿现象发生
时间片轮转算法：时间片轮转算法主要用于处理器调度。采用此算法的系统，其进程就绪队列往往按进程到达的时间来排序。进程调度程序总是选择就绪队列中的第一个进程，也就是说按照先进先出原则调度，但一旦进程占有处理器仅使用一个时间片，在使用完一个时间片后，进程还没有完成其运行，它也必须释放出（被抢占）处理器给下一个就绪的进程。而被抢占的进程返回到就绪队列的末尾重新排队等候再次运行。 （2）按时间片轮转法进行CPU调度。 编写并调试一个模拟的进程调度程序，采用“简单时间片轮转法”进行CPU调度。 每个进程有一个进程控制块（ PCB）表示。进程控制块可以包含如下信息：进程名、到达时间、需要运行时间、已运行时间、进程状态等等。 进程的到达时间及需要的运行时间可以事先人为地指定（也可以由随机数产生）。进程的到达时间为进程输入的时间。 进程的运行时间以时间片为单位进行计算。 每个进程的状态可以是就绪 W（Wait）、运行R（Run）两种状态之一。 就绪进程获得 CPU后都只能运行一个时间片。用运行时间加1来表示。 如果运行一个时间片后，进程的已占用 CPU时间已达到所需要的运行时间，则撤消该进程，如果运行一个时间片后进程的已占用CPU时间还未达所需要的运行时间，也就是进程还需要继续运行，此时应分配时间片给就绪队列中排在该进程之后的进程，并将它插入就绪队列队尾。 每进行一次调度程序都打印一次运行进程、就绪队列、以及各个进程的 PCB，以便进行检查。 重复以上过程，直到所要进程都完成为止。 进程调度算法：采用多级反馈队列调度算法。其基本思想是：当一个新进程进入内在后，首先将它放入第一个队列的末尾，按FCFS原则排队等待高度。当轮到该进程执行时，如能在该时间片内完成，便可准备撤离系统；如果它在一个时间片结束时尚为完成，调度程序便将该进程转入第二队列的末尾，再同样地按FCFS原则等待调度执行。 2）程序结构 进程调度模拟程序进程调入AddProcess（）函数打印进程Print（）函数进程调度attemperor（）函数选择操作face（）函数进程优先级排序sort（）函数 定义结构体PCB描述进程的进程控制块，定义数组PCB pcb[Max]存放进程 进程调度程序调用face()函数选择所要进行的操作。输入1则增加进程并调度进程，输入2则打印进程，输入0则任务结束 增加进程，调用AddProcess()函数，将输入的进程存放在数组pcb[Max]中 打印进程，调用print()函数，在该函数中首先调用sort()函数对进程按优先级和先来先服务排序，然后显示输出排序后的进
程 进程调度，调用attemper()函数，调度优先级最高的进程分配给CPU使之运行一个时间片 进程优先级排序，调用sort()函数，按照先来先服务和优先级排序，使排序完最优先运行的进程存放在pcb[0]中。 3）数据结构 1. 按优先数调度算法 假定系统有五个进程每一个进程用一个进程控制块PCB来代表，进程控制块的格式为： 进程名 链接指针 进程的优先级 估计运行时间 进程状态 2.按时间片轮转法调度的算法 假定系统有五个进程每一个进程用一个进程控制块PCB来代表，进程控制块的格式为： 进程名 链接指针 到达时间 估计运行时间 进程状态 为每个进程任意确定一个要求运行时间和到达时间，按照进程到达的先后顺序排成一个循环队列，再设一个队首指针指向第一个到达进程的首址。 执行处理机调度时，开始选择队首的第一个进程运行，再设一个当前运行进程指针，指向当前正运行的程序。 进程运行给最后一次，以后的调度则将当前指针一次下移一个位置，指向下一个进程，同时还应该判断该进程的剩余时间运行是否为0. 若就绪队列不为空，则重复上诉操作指导所有进程都运行完为止。 在所涉及的程序中，应有显示或打印语句，以显示或打印每次被选中进程的进程名以及运行一次后进程的变化情况等。 4）实现步骤 （1）打开VC，选择菜单项文件->新建，输入相关程序。 按优先级调度的算法：
按时间片轮转法进行CPU调度： （2）最后在进行编译连接。并把实验结果截图保存。 5、实验测试及分析： 按优先级调度的算法： 按时间片轮转法进行CPU调度： 6、实验心得体会 通过这次实验，使我对进程的优先级调度有了一定的了解。也使我能够很好得了解进程的运行状况，实验中也用到了时间片调度，各个进程分别占用CPU使用权。
附录：源代码
按优先级调度的算法：
#include 声明函数 typedef struct process { char pname[20];//struct process *next; 进程名 int BurstTime;//所需时间 }PROCESS; int priority; // char Status; 数字越大优先级越高 void insert(PROCESS *head,PROCESS *p) //{ 入队函数 PROCESS *h; if(head->next ==NULL) { head->next =p; p->next=NULL; } else { h=head; while(h->next !=NULL) { if((h->next)->priority >=p->priority h=h->next; ) else { p->next =h->next ; h->next =p; } break; } if(h->next ==NULL) { h->next =p; } } } p->next=NULL; PROCESS *create() //{ 进程初始化 PROCESS *q,*h; int i,num; h=(struct process*)malloc(sizeof(struct process)); h->next=NULL; cout<<\"------cin>>num; 请输入进程数目:\"; for(i=1;i<=num;i++) { q=(struct process*)malloc(sizeof(struct process)); cout<<\"输入第\"< insert(h,q); cout<<\"就绪队列：\\n\"; cout<<\"进程名 所需时间 优先数 进程状态\\n\"; q=h->next; while(q) { q->Status='R'; \"< \"< } return h; } void run(PROCESS *pt ) { if(pt->next!=NULL ) { PROCESS *q; cout<<\"********************************************\"< pt->next->Status ='E'; cout<<\"进程名为\"< pt->next=q->next; free(q); } else { if(pt->next->next!=NULL) { q=pt->next; pt->next=q->next; insert(pt,q); pt->next->Status ='Z'; pt->next->next->Status ='R'; } else { q=pt->next; pt->next=q->next; insert(pt,q); pt->next->Status ='Z'; } PROCESS *l; l=pt->next; cout< cout<< endl<<\" \"<< l->pname <<\" \"< cout< cout< if(ch=='Y'||ch=='y') { run(pt); } if (ch=='C'||ch=='c') { PROCESS *q; q=(struct process*)malloc(sizeof(struct process)); //先前放在了while前面，不能创建链表进行插入 cout<<\"添加进程名 \" <<\"所需时间 \" <<\"优先数 \"< cout<<\"**********************************\"< while(q) { q->Status='R'; cout<< endl<<\" \"<< q->pname <<\" \"< char ch; if( pt->next) { cout< if(ch=='Y'||ch=='y') { run(pt); } } } } void main() { PROCESS *head; head=create(); if (head!=NULL) run(head); cout<<\"结束程序\"< /*源程序cpu_time.cpp，采用时间片轮转法在Visual C++6.0下调试运行*/ /*数据结构定义及符号说明*/ #define N 20 #include typedef struct pcb /*进程控制块定义*/ { char pname[N]; /*进程名*/ int runtime; /*运行时间*/ int arrivetime; /*到达时间*/ char state; /*进程状态*/ struct pcb *next; /*连接指针*/ }PCB; PCB head_input; PCB head_run; PCB *pcb_input; static char R='r',C='c'; unsigned long current; /*记录系统当前时间的变量*/ void inputprocess(); /*建立进程的函数*/ int readyprocess(); /*建立就绪队列函数*/ int readydata(); /*判断是否有就绪进程的函数*/ int runprocess(); /*运行进程的函数*/ FILE *f; /*定义建立就绪队列函数*/ int readyprocess() { while(1) { if(readydata()==0) /*判断是否就绪函数*/ return 1; else runprocess(); /*运行进程函数*/ } } /*定义判断就绪队列是否有进程函数*/ int readydata() { if(head_input.next==NULL) { if(head_run.next==NULL) return 0; else return 1; } PCB *p1,*p2,*p3; p1=head_run.next; p2=&head_run; while(p1!=NULL) { p2=p1; p1=p2->next; } p1=p2; p3=head_input.next; while(p3!=NULL) p2=&head_input; { if(((unsigned long)p3->arrivetime<=current)&&(p3->state==R)) { printf(\"Time slice is %8d(time%4d); Process %s start,\\n\ fprintf(f, \"Time slice is %8d(time%4d); current,(current+500)/1000,p3->pname); Process %s start,\\n\ p2->next=p3->next; current,(current+500)/1000,p3->pname); p3->next=p1->next; p1->next=p3; p3=p2; } p2=p3; p3=p3->next; } } return 1; int runprocess() { /*定义运行程序函数*/ PCB *p1,*p2; if(head_run.next==NULL) /*运行队列为空时，修改当前时间*/ { current++; } return 1; else { p1=head_run.next; p2=&head_run; while(p1!=NULL) { p1->runtime--; current++; if(p1->runtime<=0) { end.\\n\ printf(\"Time slice is %8d time %4d; end.\\n\ fprintf(f, \"Time slice is %8d time %4d; p1->state=C; p2->next=p1->next; delete p1; p1=NULL; else } { p2=p1; p1=p2->next; } } return 1; } } /*--void inputprocess() 定义建立进程函数*/ { PCB *p1,*p2; unsigned int num; long max=0; /*要建立的进程数量*/ printf(\"How many processes do you want to run :\"); fprintf(f,\"How many processes do you want to run :\"); scanf(\"%d\ fprintf(f,\"%d\\n\ p1=&head_input; p2=p1; p1->next=new PCB; for(int i=0;i Process %s Process %s printf(\"Input NO.%3d Process input pname:\ fprintf(f,\"Input NO.%3d Process inout pname:\ scanf(\"%s\fprintf(f,\"%s\\n\ printf(\" runtime:\"); fprintf(f,\" runtime:\"); scanf(\"%d\fprintf(f,\"%d\\n\ printf(\" arrivetime:\"); fprintf(f,\" arrivetime:\"); scanf(\"%d\fprintf(f,\"%d\\n\ p1->runtime=(p1->runtime)*1000; p1->arrivetime=(p1->arrivetime)*1000; p1->state=R; if((unsigned long)(p1-> arrivetime)>max) max=p1->arrivetime; p1->next=new PCB; p2=p1; p1=p1->next; } delete p1; p1=NULL; p2->next=NULL; } /*——定义建立进程函数*/ void inputprocess1() { PCB *p1; int num; /*要建立的进程数*/ unsigned long max=0; printf(\"How many processes do you want to run:\"); fprintf(f,\"How many processes do you want to run:\"); scanf(\"%d\ fprintf(f,\"%d\\n\ pcb_input=new PCB; p1=pcb_input; for(int i=0;i } void runprocess1() /*定义运行进程函数*/ { pcb *pre,*cur; if(pcb_input==NULL) return; else { cur=pcb_input; pre=cur->next; while (pre->next!=cur)//find the last node in the list { pre=pre->next; } while((cur->runtime>=0)||(cur->next!=cur)) //while(1) //if p1->next!=p1,it means that there are more than one pcb jobs //if p1->next==p1 and p1->runtime<=0 means all jobs have done; { if(current<(unsigned long)cur->arrivetime) { pre=cur; cur=cur->next; } else { if(current==(unsigned long)cur->arrivetime) { printf(\"Time slice is %8d(time %4d);Process %s start,\\n\ current,(current+500)/1000,cur->pname); fprintf(f,\"Time slice is %8d(time %4d);Process %s start,\\n\ current,(current+500)/1000,cur->pname); } cur->runtime--; if(cur->runtime<0)//means the jobs have ended. { printf(\"Time slice is %8d time %4d;Process %s end.\\n\ current,(current+500)/1000,cur->pname); fprintf(f,\"Time slice is %8d time %4d;Process %s end.\\n\ current,(current+500)/1000,cur->pname); if(cur==cur->next)//delete the last job then break; { delete cur; cur=NULL; //break; return; } else { pre->next=cur->next; pcb*tmp=cur; delete tmp; cur=pre->next; } } else { cur->runtime--; pre=cur; cur=cur->next; } } current++; } } } void main() { f=fopen(\"result.txt\ printf(\"\\ntime1=1000 time slice\\n\"); current=0; inputprocess(); readyprocess(); //inputprocess1(); //runprocess1(); getch(); fclose(f); 因篇幅问题不能全部显示，请点此查看更多更全内容