高响应比优先调度算法（Highest Response Ratio Next）是一种对CPU中央控制器响应比的分配的一种算法。HRRN是介于FCFS（先来先服务算法）与SJF（短作业优先算法）之间的折中算法，既考虑作业等待时间又考虑作业运行时间，既照顾短作业又不使长作业等待时间过长，改进了调度性能。 ——百度百科
其中响应比的计算公式为：响应比 =（等待时间+要求服务时间）/ 要求服务时间
用纯C写的，进程信息是随机生成，因为不是重点。。。 有好多问题，还请大佬们指正。
#include<stdio.h> #include<stdlib.h> #include<string.h> #include<time.h> #define MAX_QUEUE_SIZE 100 typedef struct PCB { char name[15]; //名称 double index_z; //涉及响应比,使用浮点数 int time_now; //到达时间 int time_need; //需要时间 int time_cpu; //已用cpu时间 char status; //状态 W代表就绪(wait) R代表运行(run) F代表完成(finish) }PCB; PCB* create_process(const char *name,int timenow,int need) { //PCB创建函数 PCB* new=(PCB*)malloc(sizeof(PCB)); new->index_z=-1.024; //？？？ strcpy(new->name,name); new->time_cpu=0; new->time_need=need; new->time_now=timenow; new->status='W'; return new; } void Response_Compute(PCB* queue[],int head,int end,int last_time) { //更新优先级 double max_index_z=0; int max_id=0; for(int i=end;i!=head;i=(i+1)%MAX_QUEUE_SIZE) { PCB* now=queue[i]; double wait_time=last_time-now->time_now; //等待时间 now->index_z=(wait_time+(double)now->time_need)/(double)now->time_need; if(now->index_z>max_index_z) { max_index_z=now->index_z; max_id=i; } } PCB* temp=queue[end]; //找到最大优先级的PCB与end位置的交换 queue[end]=queue[max_id]; queue[max_id]=temp; } void PrintProcess(PCB* now) //两个打印进程 { printf("%14s%12.4f%10d%10d%10d%10c\n",now->name,now->index_z,now->time_cpu,now->time_now,now->time_need,now->status); } void PrintQueue(PCB* queue[],int head,int end) { for(int i=end;i!=head;i=(i+1)%MAX_QUEUE_SIZE) { PCB* now=queue[i]; PrintProcess(now); } } void HRRN(int N) { PCB* queue[MAX_QUEUE_SIZE]; //手动模拟队列 PCB* finish[MAX_QUEUE_SIZE]; //完成队列 int head=0,end=0; //队头，队尾指针 int finish_head=0; //完成队列队头指针 int time_now=0; //最后一个到达的进程时间 for(int i=0;i<N;i++) //随机生成进程信息 { char name[15]={'c','h','e','n','g','h','a','o'}; name[8]=i/100+'0',name[9]=i/10%10+'0',name[10]=i%10+'0',name[11]='\0'; int time_need=rand()%5+1; time_now+=rand()%10+1; PCB* new=create_process(name,time_now,time_need); queue[head]=new; head=(head+1)%MAX_QUEUE_SIZE; } PrintQueue(queue,head,end); while(end!=head) { Response_Compute(queue,head,end,time_now); //每次开始进程之前都进行一次优先级的更新，也导致此算法的缺点（系统开销大） PCB* now=queue[end]; //取出优先级最大的PCB end=(end+1)%MAX_QUEUE_SIZE; now->status='R'; now->time_cpu+=now->time_need; //时间片加1 printf("正在运行的程序：\n"); PrintProcess(now); printf("就绪队列：\n"); PrintQueue(queue,head,end); printf("已完成队列：\n"); PrintQueue(finish,finish_head,0); time_now+=now->time_need; if(now->time_cpu==now->time_need) //程序运行结束 { now->status='F'; finish[finish_head++]=now; //将其添加到结束队列中 } else { now->status='W'; //否则继续放入就绪队列继续下一次操作 queue[head]=now; head=(head+1)%MAX_QUEUE_SIZE; } } } void main() { srand(time(NULL)); printf("%14s%12s%10s%10s%10s%10s\n","进程名称","优先级","已用时","到达时间","需要时间","状态"); int n=5; HRRN(n); }
