*** 作系统之进程调度

具体问题：

1.编写并调试一个模拟的进程调度程序，采用“最高优先数优先”调度算法对五个进程进行调度。可以选用静态优先数或是动态优先数。

2.写并调试一个模拟的进程调度程序，采用“轮转法”调度算法对五个进程进行调度。

相关定义：

进程加权时间：进程周转时间除以进程运行时间

平均加权时间：总加权时间/进程个数

进程周转时间：进程完成时间减去进程到达时间

平均周转时间：总周转时间/进程个数

实现过程：

最高数优先程序：

利用单向循环链表模拟实现出最高优先数优先的进程调度算法。最高优先数优先的调度算法，就是把处理机分配给优先数最高的进程。

首先每个进程有一个进程控制块（PCB）。进程控制块包含：进程名称、进程的状态、进程的优先数、到达时间、运行时间。进程的优先数及需要的运行时间由人为的电脑输入。进程的到达时间为进程输入的时间。进程的运行时间以时间片（1）为单位进行计算。每个进程的状态有三种，分别是就绪态W（Wait）、运行态R（Run）、或完成态F（Finish）。

在算法中我采用两种算法，静态优先数和动态优先数算法。静态优先数是指进程的优先数在创建进程时可以给定一个初始值，并且一直保持优先数值不改变。动态优先数是指进程的优先数在创建进程时可以给定一个初始值，并且可以按一定原则修改优先数。就绪进程获得CPU后都只能运行一个时间片。时间加1表示用已占用一次CPU。如果运行一个时间片后，进程的已占用CPU时间已达到所需要的运行时间，表示进程已经运行完成，然后就撤消该进程，如果运行一个时间片后进程的已占用CPU时间还未达所需要的运行时间，也就是进程还需要继续运行，（静态优先数直接执行下一步，如使用动态优先数算法，应在此时把进程的优先数减1，然后返回就绪队列按照优先级排序等待CPU的下一次运行）。每进行一次调度程序都打印一次运行进程、就绪队列、和各个进程的PCB，以便进行检查进程调度是否正确，直到所要进程都完成为止，进程调度结束。

//动态优先数
struct pcb {//建立进程的PCB 表
	char name[10];//进程名;
	char state;//进程的状态---->W就绪状态或R运行状态或F结束状态
	int super;//进程的优先级----->优先级高的优先执行
	int ntime;//到达时间;
	int rtime;//运行时间;
	struct pcb* link;//定义了一个进程控制块的pcb指针link
} *p, * ready = NULL;
typedef struct pcb PCB;

void sort() {//建立对进程优先级排列函数; 
	PCB* first, * second;
	int insert = 0;
	if ((ready == NULL) || (p->super) > (ready->super)) {//优先级大的，排在前面; 
		p->link = ready;
		ready = p;
	}
	else {//比较进程优先级，插入相应的位置中; 
		first = ready;
		second = first->link;
		while (second != NULL) {
			if ((p->super) > (second->super)) {//插入进程比当前进程优先级大; 
				//插入到当前进程的前面;
				p->link = second;
				first->link = p;
				second = NULL;
				insert = 1;
			}
			else {//插入进程优先数最小的插在最后; 
				first = first->link;
				second = second->link;
			}
		}
		if (insert == 0) {
			first->link = p;
		}
	}
}
void input() {//建立进程控制块函数; 
	int i, num;
	printf("\n 请输入被调度的进程数目：");
	scanf_s("%d", &num);
	for (i = 0; i < num; i++) {
		printf("\n进程号No.%d:", i + 1);
		p = new pcb;
		printf("\n输入进程名：");
		cin >> p->name;//这里用cin是因为用scanf_s总是报错，显示数组输入不全（名称输入不全）
		printf("\n输入进程的优先数：");
		cin >> p->super;//与上面同样的问题
		printf("\n输入进程的运行时间：");
		cin >> p->ntime;
		p->rtime = 0;
		p->state = 'W';
		p->link = NULL;
		sort();//用sort()函数，每一个进程输入后进行一个排序; 
	}
}
int space() {
	int m = 0; PCB* pr = ready;
	while (pr != NULL) {
		m++;
		pr = pr->link;
	}
	return(1);
}
void display(PCB* r) {//显示进程函数; 
	printf("\n qname \t state \t super \t ndtime \t runtime \n");
	printf("|%s\t", r->name);
	printf("|%c\t", r->state);
	printf("|%d\t", r->super);
	printf("|%d\t", r->ntime);
	printf("|%d\t", r->rtime);
	printf("\n");
}
void check() {//查看进程状态; 
	PCB* r;
	printf(" ****当前正在运行的进程是：%s\n", p->name);//打印当前运行进程; 
	display(p);
	r = ready;
	printf(" ****当前就绪队列状态为：\n");//显示就绪队列状态;
	while (r != NULL) {
		display(r);
		r = r->link;
	}
}
void destroy() {//进程运行结束，撤销进程，释放内存
	printf("进程[%s]已完成.\n", p->name);
	free(p);
}
void  running() {//进程运行时间倒置就绪状态
	(p->rtime)++;
	if (p->rtime == p->ntime) {
		destroy();//进程运行完成撤销; 
	}
	else {//进程运行中
		p->super--;//静态与动态运算法的区别在这
		p->state = 'W';
		sort();
	}
}

//静态优先数
struct pcb {//建立进程的PCB 表
	char name[10];//进程名;
	char state;//进程的状态---->W就绪状态或R运行状态或F结束状态
	int super;//进程的优先级----->优先级高的优先执行
	int ntime;//到达时间;
	int rtime;//运行时间;
	struct pcb* link;//定义了一个进程控制块的pcb指针link
} * p,*ready = NULL;
typedef struct pcb PCB;

void sort() {//建立对进程优先级排列函数; 
	PCB* first, * second;
	int insert = 0;
	if ((ready == NULL) || (p->super) > (ready->super)) {//优先级大的，排在前面; 
		p->link = ready;
		ready = p;
	}
	else {//比较进程优先级，插入相应的位置中; 
		first = ready;
		second = first->link;
		while (second != NULL) {
			if ((p->super) > (second->super)) {//插入进程比当前进程优先级大; 
				//插入到当前进程的前面;
				p->link = second;
				first->link = p;
				second = NULL;
				insert = 1;
			}
			else {//插入进程优先数最小的插在最后; 
				first = first->link;
				second = second->link;
			}
		}
		if (insert == 0) {
			first->link = p;
		}
	}
}
void input() {//建立进程控制块函数; 
	int i, num;
	printf("\n 请输入被调度的进程数目：");
	scanf_s("%d", &num);
	for (i = 0; i < num; i++) {
		printf("\n进程号No.%d:", i+1);
	    p = new pcb;
		printf("\n输入进程名：");
		cin>> p->name;//这里用cin是因为用scanf_s总是报错，显示数组输入不全（名称输入不全）
		printf("\n输入进程的优先数：");
		cin>> p->super;//与上面同样的问题
		printf("\n输入进程的运行时间：");
		cin>> p->ntime;
		p->rtime = 0;
		p->state = 'W';
		p->link = NULL;
		sort();//用sort()函数，每一个进程输入后进行一个排序; 
	}
}
int space() {
	int m = 0; PCB* pr = ready;
	while (pr != NULL) {
		m++;
		pr = pr->link;
	}
	return(1);
}
void display(PCB* r) {//显示进程函数; 
	printf("\n qname \t state \t super \t ndtime \t runtime \n");
	printf("|%s\t", r->name);
	printf("|%c\t", r->state);
	printf("|%d\t", r->super);
	printf("|%d\t", r->ntime);
	printf("|%d\t", r->rtime);
	printf("\n");
}
void check() {//查看进程状态; 
	PCB* r;
	printf(" ****当前正在运行的进程是：%s\n", p->name);//打印当前运行进程; 
	display(p);
	r = ready;
	printf(" ****当前就绪队列状态为：\n");//显示就绪队列状态;
	while (r != NULL) {
		display(r);
		r = r->link;
	}
}
void destroy() {//进程运行结束，撤销进程，释放内存
	printf("进程[%s]已完成.\n", p->name);
	free(p);
}
void  running() {//进程运行时间倒置就绪状态
	(p->rtime)++;
	if (p->rtime == p->ntime) {
		destroy();//进程运行完成撤销; 
	}
	else {//进程运行中
		p->state = 'W';
	}
}

FCFS（先来先服务）调度程序代码：

  首先建立一个进程，控制块PCB，包括进程名称，进程状态，进程到达时间，进程运行时间，进程需要时间， 建立一个进程控制块PCB结构体，利用单向链表显示进程运行情况。根据先来先服务调度方式（先到的程序先服务），对进程进行排序，显示进程排序结果，根据排序结果，计算进程完成时间、进程周转时间和进程加权时间。最后计算平均周转时间和平均加减时间。

struct pcb {//建立进程的PCB 表
	char name[10];//进程名;
	char state;//进程的状态---->W就绪状态或R运行状态或F结束状态
	int atime;//进程的到达时间
	int ntime;//到达时间;
	int rtime;//运行时间
	int sort;//在进程到达的前提下轮转排序，保证每个进程在到达的情况下能运行一轮
	struct pcb* link;//定义了一个进程控制块的pcb指针link
} *p, * ready = NULL;
typedef struct pcb PCB;

void sort() {//建立对进程到达时间排列函数; 
	PCB* first, * second;
	int insert = 0;
	if ((ready == NULL) || (p->sort) < (ready->sort)) {//先到达的排在前面; 
		p->link = ready;
		ready = p;
	}
	else {//比较到达时间插入相应的位置中; 
		first = ready;
		second = first->link;
		while (second != NULL) {
			if ((p->sort) < (second->sort)) { 
				//插入first,second中间
				p->link = second;
				first->link = p;
				second = NULL;
				insert = 1;
			}
			else {//插在second后; 
				first = first->link;
				second = second->link;
			}
		}
		if (insert == 0) {//就绪队列最后
			first->link = p;
		}
	}
}
void input() {//建立进程控制块函数; 
	int i, num;
	printf("\n 请输入被调度的进程数目：");
	scanf_s("%d", &num);
	for (i = 0; i < num; i++) {
		printf("\n进程号No.%d:", i + 1);
		p = new pcb;
		printf("\n输入进程名：");
		cin >> p->name;//这里用cin是因为用scanf_s总是报错，显示数组输入不全（名称输入不全）
		printf("\n输入进程的到达时间：");
		cin >> p->atime;//与上面同样的问题
		printf("\n输入进程的运行时间：");
		cin >> p->ntime;
		p->sort = p->atime;
		p->rtime = 0;
		p->state = 'W';
		p->link = NULL;
		sort();//用sort()函数，每一个进程输入后进行一个排序; 
	}
}
int space() {
	int m = 0; PCB* pr = ready;
	while (pr != NULL) {
		m++;
		pr = pr->link;
	}
	return(1);
}
void display(PCB* r) {//显示进程函数; 
	printf("\n 进程名 \t 状态\t \t 到达时间 \t 需要运行时间 \t 已经运行时间 \n");
	printf("|%s\t\t", r->name);
	printf("|%c\t\t", r->state);
	printf("|%d\t\t", r->atime);
	printf("|%d\t\t", r->ntime);
	printf("|%d\t\t", r->rtime);
	printf("\n");
}
void check() {//查看进程状态; 
	PCB* r;
	printf(" ****当前正在运行的进程是：%s\n", p->name);//打印当前运行进程; 
	display(p);
	r = ready;
	printf(" ****当前就绪队列状态为：\n");//显示就绪队列状态;
	while (r != NULL) {
		display(r);
		r = r->link;
	}
}
void destroy() {//进程运行结束，撤销进程，释放内存
	printf("进程[%s]已完成.\n", p->name);
	free(p);
}
void  running() {//进程运行时间倒置就绪状态
	(p->rtime)++;
	if (p->rtime == p->ntime) {
		destroy();//进程运行完成撤销; 
	}
	else {//进程运行中
		p->sort =p->sort+1;//按照进程到达时间轮转
		p->state = 'W';
		sort();
	}
}