进程调度之时间片轮转调度算法(实验三)

在分时系统中，最简单最常用的就是基于时间片轮转调度算法，时间片轮转调度算法是非常公平的处理机分配方式，让就绪队列的每个进程每次仅运行一个时间片。

1.时间片轮转调度算法的基本原理

   在时间片轮转调度算法中，系统根据先来先服务的原则，将所有的就绪进程排成一个就绪队列，并且每隔一段时间产生一次中断，激活系统中的进程调度程序，完成一次处理机调度，把处理机分配给就绪队列队首进程，让其执行指令。当时间片结束或进程执行结束，系统再次将cpu分配给队首进程。

2.进程切换时机

      时间片尚未结束，进程已经执行结束，立即激活调度程序，将其从就绪队列中删除，在调度就绪队列的队首进程执行，开启新的时间片（计数器置0）。

    时间片已经结束，进程尚未结束，立即激活进程调度程序，未执行完的进程放到就绪队列的队尾。

3.时间片大小的确定

   在轮转调度算法中时间片的大小对系统的性能有很大的影响。若时间片很小，将有利于短作业，其能够在这个时间片内完成。时间片过小意味着会进行频繁的进程切换，这将增大系统的开销。若时间片选择太长，时间片轮转调度算法将退化为先来先服务的进程调度算法。

时间片轮转调度算法的C语言模拟：

#include 
  
    #include 
   
     #include 
    
      //#define OUTALLINFO //若要输出详细的进程描述信息则打开宏 #define Max 256 #define time 2 //时间片大小 enum pathread_attr{ //进程的状态信息 runing = 1, wait, finsih }; struct Pthread{ //描述进程信息 char *name; int come_time; int need_time; int runing_time; double zz_time; double dqzz_time; enum pathread_attr attr; struct Pthread *next; Pthread() //默认构造函数 { name = NULL; come_time = 0; runing_time = need_time = 0; zz_time = 0; dqzz_time = 12.66; attr = wait; next = NULL; } void get_info(int end_time) //计算周转时间，带权周转时间 { #ifndef OUTALLINFO printf("pathread:%s over time:%d\n",name,end_time); #endif // OUTALLINFO this->zz_time = (end_time - this->come_time) * 1.0; dqzz_time = zz_time / need_time; } void copy_queue(struct Pthread *temp) //拷贝进程信息 { name = (char*)malloc(sizeof(char) * strlen(temp->name)); strcpy(name,temp->name); come_time = temp->come_time; need_time = temp->need_time; runing_time = temp->runing_time; attr = temp->attr; } }; int run_sum = 0; //统计进程的个数 void init_pthread(struct Pthread *head,const char *name,const int come_time,const int need_time) //初始化进程信息 { struct Pthread *temp = new Pthread(); temp->name = (char *) malloc(sizeof(char) * strlen(name)); strcpy(temp->name,name); temp->come_time = come_time; temp->need_time = need_time; temp->runing_time = need_time; temp->attr = wait; temp->next = head->next; head ->next = temp; return; } void out_one(struct Pthread *temp) //输出一个进程信息 { #ifdef OUTALLINFO printf("%s pathread info:\n",temp->name); printf("come_time: %d\n",temp ->come_time); printf("need_time: %d\n",temp ->need_time); switch(temp->attr){ case 1: printf("attr: waiting \n"); break; case 2: printf("attr: runing \n"); break; case 3: printf("attr: finsih \n"); break; } #endif // OUTALLINFO printf("周转时间: %0.2f\n",temp->zz_time); printf("带权周转时间: %0.2f\n",temp->dqzz_time); return; } void out_all(struct Pthread *head) //输出所有进程信息 { for(struct Pthread *p = head->next; p; p = p->next) out_one(p); return; } void add_queue(struct Pthread *head_temp,struct Pthread *head_queue) //添加进程到就绪队列 { struct Pthread *temp = new Pthread(); temp->copy_queue(head_temp); if(!head_queue->next) temp->attr = runing; else temp->attr = wait; struct Pthread *p = NULL; for(p = head_queue; p ->next; p = p->next); p->next = temp; return; } void queue_del(struct Pthread *head_queue) //从就绪队列删除一个进程 { if(!(head_queue ->next)) return; head_queue ->next->attr = finsih; out_one(head_queue ->next); struct Pthread *p = head_queue ->next; head_queue->next = p->next; delete p; return; } void sqrt_queue(struct Pthread *head_queue) //将时间片结束还未完成的进程放到队尾 { struct Pthread *p = head_queue->next; head_queue->next = p->next; p->next = NULL; struct Pthread *q = NULL; for(q = head_queue; q ->next; q = q->next); q ->next = p; return; } void mo_ni(struct Pthread *head,struct Pthread *head_queue) //模拟时间片轮转调度算法 { int run_i = 0,run_over = 0,time_runing = 0; while(time_runing >= 0){ for(struct Pthread *p = head ->next; p; p = p->next) //检查此时刻是否有进程到达 if(time_runing == p->come_time) add_queue(p,head_queue); if(head_queue ->next){ //如果就绪队列非空 if(run_i == time && head_queue->next->runing_time){ //时间片结束&&进程未完成 sqrt_queue(head_queue); //把进程放到就绪队列队尾 run_i = 0; //时间片置0 } if(!head_queue->next->runing_time){ //如果进程执行结束 head_queue->next->get_info(time_runing); queue_del(head_queue); //从就绪队列中删除该进程 run_i = 0; //时间片置0 run_over++; //统计已经结束的进程个数 } if(head_queue ->next) //如果有进程正在执行，服务时间减1 head_queue->next->runing_time--; run_i++; //时间片加1 } time_runing++; if(run_over == run_sum) //如果处理完所有进程则结束模拟 return; } return; } int main(int argc,char *argv[]) { struct Pthread *head = new Pthread(); //进程链表 struct Pthread *head_queue = new Pthread(); //就绪态进程链表队列 char name[Max]; int come_time,need_time; FILE *input_file = fopen("C:\\Users\\chenhongyu\\Desktop\\test.txt","r"); //读取测试信息 printf("plase input name come_time need_time priority,if over,plase input [Ctrl + Z]\n\n"); while(fscanf(input_file,"%s%d%d",name,&come_time,&need_time) != EOF){ init_pthread(head,name,come_time,need_time); //初始化进程链表 run_sum++; //统计总共有多少个进程 } mo_ni(head,head_queue); //模拟时间片轮转调度算法 return 0; }