进程调度(上)

实验目的

• 针对进程调度的特点，设计进程控制块PCB的数据结构
• 选择合适的数据结构建立进程就绪队列，实现对进程的有序组织
• 实现时间片轮转调度算法
• 实现基于优先权调度算法

实验原理

• 时间片轮转调度算法（round robin）
  • 该算法采取了非常公平的方式，即让就绪队列上的每个进程每次仅运行一个时间片。如果就绪队列上有N个进程，则每个进程每次大约都可获得1/N的处理机时间。
  • 时间片的大小对于系统性能有很大的影响。若选择很小的时间片，将有利于短作业，但意味着会频繁地执行进程调度和进程上下文的切换，这无疑会增加系统的开销。反之，若时间片选择得太长，且为使每个进程都能在一个时间片内完成，RR算法便退化为FCFS算法，无法满足短作业和交互式用户的需求。
  • 进程的切换时机体现出RR算法的特点。若一个进程在时间片还没结束时就已完成，此时立即激活调度程序，将它从执行队列中删除。若一个进程在时间片结束时还未运行完毕，则调度程序将把它送往就绪队列的末尾，等待下一次执行。用C语言编程模拟调度程序时，将时间片，程序运行时间量化为整数
• 优先权调度算法
  • 在时间片算法中，无法对进程的紧急程度加以区分。而优先级算法正好可以解决这一问题。
  • 进程优先级的确定同样重要。进程优先级可以分为静态优先级和动态优先级。静态优先级是在进程创建初期就被确定的值，此后不再更改。动态优先级指进程在创建时被赋予一个初值，此后其值会所进程的推进或等待时间的增加而改变。
  • 用C语言模拟调度程序时，可用p->priority += 1; /*优先数加,若设为0则优先级不变*/ 这条语句控制静态动态优先级的切换。

实验内容

PCB的数据结构及进程的基本操作

#define _CRT_SECURE_NO_WARNINGS
#include <stdio.h>
#include <stdlib.h>
struct pcb { // 定义进程控制块（PCB）结构体
	char name;
	char state;
	int arrivetime=65535;//到达时间
	int needtime=65535;//所需时间
	int finishtime=65535;//结束时间
	int servicetime = 0; //服务时间
	int priority = 65535; //优先数
	struct pcb* next=NULL; //下一个节点
};
typedef struct pcb PCB;
struct ReadyQueue//就绪队列
{
	PCB* head;
	PCB* tail;
};
void initQueue(struct ReadyQueue* rq) {//初始化就绪队列
	rq->head = NULL;
	rq->tail = NULL;
}
void EnQueue(struct ReadyQueue* rq, PCB* p) {//入队
	if (!rq->head) {
		rq->head = p;
		rq->tail = p;
	}
	else {
		rq->tail->next = p;
		rq->tail = p;
		p->next = NULL;
	}
}
void Dequeue(struct ReadyQueue* rq, PCB** p) {//出队
	if (rq->head != NULL) {
		*p = rq->head;
		rq->head = rq->head->next;
		if (rq->head == NULL) {
			rq->tail = NULL;
		}
		(*p)->next = NULL;  // Ensure the dequeued PCB points to NULL
	}
}

void Creat(int n, struct ReadyQueue* rq) {//创建就绪队列
	for (int i = 0; i < n; i++) {
		PCB* temp1 = new PCB;
		 // Declare temp inside the loop to create a new object for each process
		//printf("Enter process name,arrive time and execution time: \n");
		printf("Enter process name,arrive time,execution time and priority: \n");
		getchar();
		scanf("%c", &temp1->name);
		//scanf("%d%d", &temp1->arrivetime, &temp1->needtime);
		scanf("%d%d%d", &temp1->arrivetime,&temp1->needtime, &temp1->priority);
		temp1->state = 'W';
		EnQueue(rq, temp1);
	}
}
void Processin(PCB** p, ReadyQueue* rq1, int i) {//进程进入就绪队列
	while (*p && (*p)->arrivetime <= i) {
		PCB* temp1 = new PCB;
		temp1->arrivetime = (*p)->arrivetime;
		temp1->name = (*p)->name;
		temp1->state = (*p)->state;
		temp1->needtime = (*p)->needtime;
		temp1->priority = (*p)->priority;
		temp1->next = NULL;

		if (rq1->head == NULL) {
			rq1->head = temp1;
			rq1->tail = temp1;
		}
		else {
			rq1->tail->next = temp1;
			rq1->tail = temp1;
		}

		(*p) = (*p)->next;
	}
}

PCB* Getprior(struct ReadyQueue rq){ //获得优先级最高的进程
	PCB* p = rq.head; PCB* p1 = rq.head;
	while (p) {
		if (p->priority < p1->priority)p1 = p;
		p = p->next;
	}
	return p1;
}
void Delete(struct ReadyQueue* rq, PCB* p) {//删除节点
	PCB* p1 = rq->head;PCB* p2;
	if (p) {
		if (p1->name == p->name) Dequeue(rq, &p2);
		if (p1->name != p->name) {
			while (p1->next->name != p->name)
			{
				p1 = p1->next;
			}
			if (p1->next)p1->next = p1->next->next;
		}
	}
}
void Print(struct ReadyQueue rq) {//打印就绪队列
	PCB* p = rq.head;
	while (p)
	{
		//printf("进程名:%c\t到达时间:%d\t所需时间:%d\t进程状态:%c\t\n", p->name,p->arrivetime,p->needtime, p->state);
		printf("进程名:%c\t到达时间:%d\t所需时间:%d\t优先数:%d\t进程状态:%c\t\n\
", p->name, p->arrivetime, p->needtime,p->priority,p->state);
		p = p->next;
	}
}

算法实现

void RR(int n, struct ReadyQueue rq, ReadyQueue* rq1, struct ReadyQueue* rq2) {//时间片轮转
	int i = 0,j=1;
	PCB* p = rq.head;

	while (rq1->head != NULL || p) {
		if (!rq1->head && p->arrivetime - i < n&& p->arrivetime-i>0) i = p->arrivetime;
		if (!rq1->head && p->arrivetime >= i + n) { i += n; continue; j++; }
		Processin(&p, rq1, i);
		PCB* temp;
		rq1->head->state = 'R';
		int t = rq1->head->needtime;
		printf("第%d个时间片\n", j);
		Print(*rq1);
		printf("******************************\n");
		if (rq1->head->needtime > n) { rq1->head->needtime -= n; rq1->head->state = 'W'; rq1->head->servicetime += n; }
		else {
			rq1->head->finishtime = i + t; rq1->head->servicetime += t;
			rq1->head->needtime = 0;
			rq1->head->state = 'F';
		}
		Dequeue(rq1, &temp); //printf("%d", temp->needtime);
		if (temp->needtime) {
			i += n;
			Processin(&p, rq1, i);
			EnQueue(rq1, temp);
		}
		else {
			i += t;
			EnQueue(rq2, temp);
		}
		j++;
	}
}
void Preemptive(struct ReadyQueue rq, ReadyQueue* rq1, struct ReadyQueue* rq2){ //抢占式
	int i = 0;
	PCB* p = rq.head;
	while (rq1->head != NULL||p) {
		if (!rq1->head) i = p->arrivetime;
		if(p)Processin(&p, rq1, i);
		PCB* p1 = Getprior(*rq1);
		p1->state = 'R';
		printf("第%d个时刻\n", i);
		Print(*rq1);
		printf("******************************\n");
		if (p1->needtime>1) { p1->state = 'W'; p1->priority += 1;}
		else {
			p1->finishtime =i+1;
			p1->state = 'F';
		}
		p1->needtime -= 1;
		p1->servicetime += 1;
		if (!p1->needtime) { Delete(rq1, p1); EnQueue(rq2, p1); }
		//Print(*rq1);
		i++;
	}
}
void NonPreemptive(struct ReadyQueue rq, ReadyQueue* rq1, struct ReadyQueue* rq2) {//非抢占式
	int i = 0;
	PCB* p = rq.head;
	while (rq1->head != NULL || p) {
		if (!rq1->head) i = p->arrivetime;
		if (p)Processin(&p, rq1, i);
		PCB* p1 = Getprior(*rq1);
		while (p1->needtime) {
			p1->state = 'R';
			printf("第%d个时刻\n", i);
			Print(*rq1);
			printf("******************************\n");
			i++;
			p1->servicetime += 1;
			p1->state = 'W'; 
			if (p)Processin(&p, rq1, i);
			p1->needtime -= 1;
		}
		p1->finishtime = i;
		p1->state = 'F';
		Delete(rq1, p1); EnQueue(rq2, p1);
	}
}
void Show(struct ReadyQueue rq) {//打印周转时间
	PCB* p = rq.head;
	int i = 0; float t = 0, w = 0,m;
	while (p)
	{
		m = (p->finishtime - p->arrivetime)*1.0 / (p->servicetime);
		t += p->finishtime - p->arrivetime;
		w += m;
		printf("进程名:%c\t完成时间:%d\t周转时间:%d\t带权周转时间:%f\t\n", p->name, p->finishtime, p->finishtime - p->arrivetime,m);
		p = p->next;
		i++;
	}
	printf("%d个进程的平均周转时间为%f，平均带权周转时间为%f", i, t/i , w/ i);
}

int main()
{
	ReadyQueue rq, rq2; ReadyQueue rq1; initQueue(&rq1);
	initQueue(&rq); initQueue(&rq2);
	int n1, n2;
	//scanf("%d%d", &n1, &n2);
	scanf("%d", &n1);
	Creat(n1, &rq);
	NonPreemptive(rq, &rq1, &rq2);
	//RR(n2, rq, &rq1, &rq2);
	Show(rq2);
}

时间片轮转算法演示

非抢占式优先权调度算法

实验总结

通过这次实验，我们可以看出优先权调度算法和时间片轮转调度算法各有优缺点。优先权调度算法能够保证高优先级的进程优先得到执行，但可能会导致低优先级的进程饥饿；而时间片轮转调度算法能够保证所有的进程都有机会得到执行，但其效率可能会受到时间片长度选择的影响。因此，在实际应用中，需要根据具体的需求和环境来选择合适的调度算法。