博客

本文章将会介绍最高响应比优先的进程调度算法，并按照以下需求进行实现：

代码在文章最后

• 由用户输入每个进程的名称、要求运行时间
• 每一轮调度，计算每个进程的响应比，R = (W+S)/S=1+W/S，W：等待时间，S：预计执行时间
• 每次调度响应比最高的就绪进程
• 若某进程“要求运行时间” ==“已运行时间”，则将其状态置为“结束” ，并退出队列 运行程序，显示每次调度时被调度运行的进程名称，以及各进程控制块的动态变化过程

一、什么是最高响应比优先的进程调度算法

高响应比优先调度算法（

H

ighest

R

esponse

R

atio

N

ext）是一种对CPU

中央控制器

响应比的分配的一种算法。HRRN是介于FCFS（先来先服务算法）与SJF（短作业优先算法）之间的折中算法，既考虑作业等待时间又考虑作业运行时间，既照顾短作业又不使长作业等待时间过长，改进了调度性能。该算法使等待时间较长的长作业也能获得执行的机会 但每次调度时都要估算响应比，会消耗较多的CPU时间。

响应比的计算方法如下所示：

响应比 =（等待时间+要求服务时间）/ 要求服务时间,即RR=（w+s）/s=1+w/s，因此响应比一定是大于等于1的，其中,W：等待时间，S：预计执行时间。

二、进程pcb中必须包含的元素

进程pcb必须包含以下元素，可以更具需求继续扩充：

三、示例展示

进程队列如下：

进程服务如下：

执行的顺序如下：

A——>B——>C——>E——>D

四、具体实现

4.1、数据结构

在代码实现中使用的是链式结构，使得每个进程通过指针连接起来，这样使得在查询最高响应比的进程的时候方便，同时也使得进程的添加更加方便。

4.2、算法核心

该算法的核心有二，第一个是进程队列的响应比的更新，由于最高响应比优先的进程调度是非抢占式的，所以每个进程在执行完后，进程队列中的进程的等待时间要做响应的调整，并重新计算响应比。第二个是找到进程队列中响应比最高的进程，而找到响应比最高的进程有两种方法，第一种是遍历进程队列的所有进程的响应比找到最大的，该方法的时间复杂度是O(n)；第二种是对所有进程进行排序，该方法的时间复杂度至少为n*logn。在作者的实现代码中是使用的第一种方法。

4.3、代码实现

#include <stdio.h>
#include <stdlib.h>

//最高响应比
typedef struct pcb {
	int pid;
	char state;//E为完成，R为正在运行，W为在就绪队列
	int total_time;//需要的时间
	
	double waittime;//等待时间
	double response;//响应比
	int cputime;//已经执行的时间
	int mark;//标志位，用来表示正在执行的进程，1为在cpu，0为不在cpu
	struct pcb* next;
}*proc;


//初始化进程，需要用户输入进程id和需要cpu的时间
proc init_pcb(struct pcb* head,struct pcb* tail,int mark,int* proc_num) {
	int i;
	//防止进程id重复
	//static int pcb_id[20] = { 0 };
	//static int pcb_id_index = 0;
	int numofpcb;
	proc p, tmp;
	printf("please input the number of process:\n");
	scanf("%d", &numofpcb);
	printf("there are %d processes,please input pcb info:\n", numofpcb);
	p = (proc)malloc(sizeof(struct pcb));
	printf("process id:");
	scanf("%d", &p->pid);
	//do {
	  //printf("process id:");
	  //scanf("%d", &p->pid);
	//	if (pcb_id_index != 0) {
	//		for (int i = 0; i < pcb_id_index; i++) {
	//			if (p->pid == pcb_id[i]) {
	//				printf("process id exist!\n");
	//				break;
	//			}
	//		}
	//	}
	//} while (1);
	//pcb_id[pcb_id_index] = p->pid;
	//pcb_id_index++;
	p->response = 1.0;
	printf("cputime required:");
	scanf("%d", &p->total_time);
	p->state = 'W';
	p->cputime = 0;
	p->mark = mark;
	p->waittime = 0;
	
	head = p;

	for (i = numofpcb; i > 1; i--) {
		tmp = p;
		p = (proc)malloc(sizeof(struct pcb));
		printf("process id:");
		scanf("%d", &p->pid);
		p->response = 1.0;
		printf("cputime required:");
		scanf("%d", &p->total_time);
		p->state = 'W';
		p->cputime = 0;
		p->mark = 0;
		p->waittime = 0;
		
		tmp->next = p;
	}
	tail = p;
	p->next = head;
	*proc_num = (*proc_num) + numofpcb;
	return tail;
}


//找到响应比最大的进程，并返回该进程
proc find_max_response(proc node, struct pcb* head,int* proc_num) {
	double maxresponse;
	proc p = head;
	proc tmp = p, res = p;
	
	//在进程队列中找到响应比最大的进程
	tmp = node;
	proc find = head;
	maxresponse = find->response;
	for (int i = 0; i < *proc_num; i++) {
		if (find->response > maxresponse) {
			res = find;
			tmp->mark = 0;
			res->mark = 1;
			tmp = res;
			maxresponse = res->response;
		}
		find = find->next;
	}
	return res;
}



//调整所有进程的响应，正在执行的进程响应不变，重新计算其他进程的响应比
//因为为抢占式的，平且进程队列会将完成的进程从进程队列删除，所以在进程队列中的进程全是需要调整响应比的
void set_all_process_response(proc head,int* proc_num,proc ntodo) {
	proc tmp = head;
	for (int i = 0; i < *proc_num; i++)
	{
		tmp->waittime = tmp->waittime + ntodo->total_time;
		tmp->response = 1 + tmp->waittime / tmp->total_time;
		tmp = tmp->next;
	}
}

//打印进程的pid、waittime、req_time、response
void display(struct pcb* head,int* proc_num) {
	int i;
	proc p = head;
	printf("pid\twait\treq_time\tresponse\n");
	for (i = 0; i < *proc_num; i++) {
		printf("%d\t%.0lf\t%d\t\t%lf\n", p->pid, p->waittime, p->total_time, p->response);
		p = p->next;
	}
	printf("----------------------------------\n");
}

//删除已经执行完成的进程，并返回进程队列的尾指针
proc delete_finished_pro(proc node, struct pcb* head, struct pcb* tail,int* proc_num) {
	if (head == tail) {
		return NULL;
	}
	proc pre = tail;

	for (int i = 0; i < *proc_num; i++) {
		if (pre->next->pid == node->pid) {
			pre->next = node->next;
			tail = pre;
			head = pre->next;
			break;
		}
	}
	//调整进程数量
	(*proc_num)--;
	return tail;
}

//插入新进程，使用init_pcb（）函数完成该功能，并将新进程插入到原进程队列
//中得到新进程队列，并返回新进程队列的尾指针
proc insert_proc(int* insertnum,proc head,proc tail,int* proc_num) {
	proc inhead = NULL, intail = NULL;
	intail = init_pcb(inhead, intail, 0,proc_num);
	inhead = intail->next;
	proc tmp = inhead;

	tail->next = inhead;
	tail = intail;
	tail->next = head;
	//*proc_num = (*proc_num) + *insertnum;
	return tail;
}

//用户选择是否插入新进程，返回进程队列的尾指针
proc judg_insert_proc(int* insertnum,proc head,proc tail,int* proc_num) {
	int choice = 0;
	/*proc intail;*/
	printf("insert new processes or not,please input number(1 yes,0 no):");
	scanf("%d", &choice);
	if (choice == 1) {
		if (head == NULL) {
			tail = init_pcb(head, tail, 1, proc_num);
			head = tail->next;
			return tail;
		}
		tail = insert_proc(insertnum, head, tail,proc_num);
	}
	return tail;
}

//基于动态优先级的进程调度算法，找出优先级最大的进程执行，每一个cpu时间片，调整一次
//所有进程的优先级，再重新寻找优先级最高的进程
void priority(struct pcb* head, struct pcb* tail,int* proc_num) {
	int* insertnum = (int*)malloc(sizeof(int));
	proc intail, inhead;
	*insertnum = 0;
	int i, round;
	double maxlevel;
	round = 1;
	proc p = head;
	proc t = tail;
	proc ntodo, nowmark;
	nowmark = p;
	ntodo = p;//response最大的，马上要做的
	maxlevel = p->response;
	for (i = 0; i < *proc_num; i++) {
		p = p->next;
		if (p->response > maxlevel) {
			ntodo = p;
			nowmark->mark = 0;
			ntodo->mark = 1;
			nowmark = ntodo;
			maxlevel = ntodo->response;
		}
	}
	while (ntodo->total_time > ntodo->cputime)
	{
		*insertnum = 0;
		printf("\n* Round %d, Process %d is running\n", round, ntodo->pid);
		round = round + ntodo->total_time;
		ntodo->state = 'E';
		
		set_all_process_response(head,proc_num,ntodo);
		tail = delete_finished_pro(ntodo, head, tail, proc_num);
		if (tail == NULL) {
			head = NULL;
		}
		else
		{
			head = tail->next;
			display(head, proc_num);
		}
		
		printf("\n▲ process %d is finished\n", ntodo->pid);

		if (head == tail&&head==NULL) {
			
			tail = judg_insert_proc(insertnum, head, tail, proc_num);
			if (tail == NULL) {
				printf("over!!!\n");
				return;
			}
			head = tail->next;
		}
		else
		{
			tail= judg_insert_proc(insertnum, head, tail, proc_num);
			head = tail->next;
		}
		

		ntodo = find_max_response(ntodo,head, proc_num);
	}
}

int main() {
	int* proc_num = (int*)malloc(sizeof(int));
	*proc_num = 0;
	int mark = 1, inmark = 0;
	struct pcb* head = NULL, * tail = NULL;
	tail = init_pcb(head, tail,mark,proc_num);
	head = tail->next;
	display(head,proc_num);
	priority(head,tail,proc_num);
	return 0;
}