【操作系统】基于动态优先级的进程调度算法-C语言实现（有代码）

这篇具有很好参考价值的文章主要介绍了【操作系统】基于动态优先级的进程调度算法-C语言实现（有代码）。希望对大家有所帮助。如果存在错误或未考虑完全的地方，请大家不吝赐教，您也可以点击"举报违法"按钮提交疑问。

本文章将会介绍如何编写动态优先级的进程调度算法，并使用从语言实现。

一、什么是动态优先级的调度算法

进程运行一个时间片后，如果进程已占用 CPU时间已达到所需要的运行时间，则撤消该进程；如果运行一个时间片后进程的已占用CPU时间还未达所需要的运行时间，也就是进程还需要继续运行，此时应将进程的优先数减1（即降低一级），然后把它插入就绪队列等待CPU。所以在在该程序中每一个时间片后都需要调整一次程序的优先级，并且在所有的进程中找到优先级最大的进程，而实现在进程中找到优先级最大的进程有两种方式：一种是遍历所有的进程找到所有的进程;第二种是根据优先级对进程进行排序。

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

进程pcb必须包含以下五个元素，可以按需求增加其他元素：

pcb
进程名
优先级
需要运行的时间
已经运行的时间
状态

三、流程图

动态优先级调度算法c语言,操作系统,算法,c语言

四、例题展示

四个进程A、B、C、D，在同一时刻到达，个程序的优先级如下图所示：

进程	到达时间	开始时间	需要运行的时间	优先级	完成时间
A	0	6	2	1	8
B	0	1	2	3	4
C	0	5	2	2	7
D	0	0	2	4	3

第一个时间片：

此时D的优先级最高，应该执行，所以D的开始时间为0，时间片结束，优先级减一，优先级变为3

第二个时间片：

此时B和D的优先级最高，都为3，如果按顺序来执行，就是B执行，所以B的开始为1，时间片结束，优先级减一，优先级变为2

第三个时间片：

此时D的优先级最高，时间片结束，优先级减一,优先级变为2，运行结束

第四个时间片：

此时B、C的优先级最高，都为2，按顺序来，B执行，时间片结束，优先级减一，优先级变为1，运行结束

第五个时间片：

此时C的优先级最高，为2，C执行，所以C的开始时间为5，时间片结束，优先级减一，优先级变为1

第六个时间片：

A、C优先级都为1，A执行，所以A的开始时间为6，时间片结束，优先级减一，优先级变为0

第七个时间片：

C的优先级最高，C执行，时间片结束，优先级减一，优先级变为0，运行结束

第八个时间片：

A运行，并允许结束

五、具体实现

5.1、数据结构

采用链式结构，即一个进程可以指向下一个进程，这样方便增加进程的个数，同时如果是使用遍历法求最大优先级的进程，在链式结构下也是十分方便实现的。

5.2、如何得到进程队列中优先级最大的进程

按照之前说的找到优先级最大的进程有两种方法，一是遍历所有的进程，二是根据进程优先级对所有的进程进行排序。第一种方法的操作简单且复杂度为O(n),第二种方法操作较为复杂且复杂度为n*logn。作者的实现是使用的第一种。

5.3、代码如下文章来源地址https://www.toymoban.com/news/detail-735914.html

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

//动态优先级
typedef struct pcb {
	int pid;
	char state;//E为完成，R为正在运行，W为在就绪队列
	int total_time;//需要的时间
	int level;//优先级
	int cputime;//已经执行的时间
	int mark;//标志位，用来表示正在执行的进程，1为在cpu，0为不在cpu
	struct pcb* next;
}*proc;


//初始化进程，返回进程队列的尾指针
proc init_pcb(struct pcb* head,struct pcb* tail,int mark,int* proc_num) {
	int i;
	//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++;
	printf("the processes level:");
	scanf("%d", &p->level);
	printf("cputime required:");
	scanf("%d", &p->total_time);
	p->state = 'W';
	p->cputime = 0;
	p->mark = mark;
	head = p;

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


//找到进程队列中优先级最高的进程，并将该进程指针返回
proc find_max_level(proc node, struct pcb* head,int* proc_num) {
	int maxlevel;
	proc p = head;
	proc tmp = p, res = p;
	tmp = node;
	//从头指针开始找优先级最大的进程
	maxlevel = head->level;
	proc find = head;
	for (int i = 0; i < *proc_num; i++) {
		//if (find->state == 'E') {
		//	find = find->next;
		//	continue;
		//}
		if (find->level >= maxlevel) {
			res = find;
			tmp->mark = 0;
			res->mark = 1;
			tmp = res;
			maxlevel = res->level;
		}
		find = find->next;
	}
	return res;
}



//调整所有进程的优先级，正在执行的优先级减一
void set_all_process_level(proc nowrunning,int* proc_num) {
	proc temp = nowrunning;
	nowrunning->level--;
}

//打印进程的id、cpu_time、req_time、level
void display(struct pcb* head,int* proc_num) {
	int i;
	proc p = head;
	printf("pid cpu_time req_time level\n");
	for (i = 0; i < *proc_num; i++) {
		printf("%d\t%d\t%d\t%d\n", p->pid, p->cputime, p->total_time, p->level);
		p = p->next;
	}
	printf("----------------------------------\n");
}

//删除进程队列中已经完成的进程
proc delete_finished_pro(proc node, struct pcb* head, struct pcb* tail,int* proc_num) {
	proc pre = tail;
	//通过id来识别已经完成的队列
	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) {//进程队列中没有进程了，直接使用init_pcb（）函数
			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));
	*insertnum = 0;
	int round = 1, i, maxlevel;
	proc p = head;
	proc t = tail;
	proc ntodo, nowmark;
	nowmark = p;
	ntodo = p;//leve最大的，马上要做的
	maxlevel = p->level;
	for (i = 0; i < *proc_num; i++) {
		p = p->next;
		if (p->level > maxlevel) {
			ntodo = p;
			nowmark->mark = 0;
			ntodo->mark = 1;
			nowmark = ntodo;
			maxlevel = ntodo->level;
		}
	}
	while (ntodo->total_time > ntodo->cputime)
	{
		*insertnum = 0;
		printf("\n* Round %d, Process %d is running\n", round, ntodo->pid);
		round++;
		ntodo->cputime++;
		if (ntodo->total_time == ntodo->cputime) {
			ntodo->state = 'E';
			tail = delete_finished_pro(ntodo, head, tail, proc_num);
			head = tail->next;
			set_all_process_level(ntodo,proc_num);
			display(head,proc_num);
			printf("\n▲ process %d is finished\n", ntodo->pid);

			if (head == tail) {
				head = NULL, tail = NULL;
			}

			
			tail = judg_insert_proc(insertnum, head, tail,proc_num);
			if (tail == NULL) {
				printf("over!!!\n");
				return;
			}
			head = tail->next;
			display(head, proc_num);
			ntodo = find_max_level(ntodo,head, proc_num);
			continue;
		}
		set_all_process_level(ntodo, proc_num);//重新调整level
		
		display(head, proc_num);
		tail = judg_insert_proc(insertnum, head, tail, proc_num);
		tail->next = head;
		ntodo = find_max_level(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;
}

到了这里，关于【操作系统】基于动态优先级的进程调度算法-C语言实现（有代码）的文章就介绍完了。如果您还想了解更多内容，请在右上角搜索TOY模板网以前的文章或继续浏览下面的相关文章，希望大家以后多多支持TOY模板网！