使用动态优先权的进程调度算法 C语言模拟实现 含详细源代码和实验结果

使用动态优先权的进程调度算法 C语言模拟实现 含详细源代码和实验结果

• 题目描述

1. 实现对N个进程采用某种进程调度算法（如动态优先权调度）的调度

2. 每个用来标识进程的进程控制块PCB可用结构来描述，包括以下字段

   • 进程标识数ID
   • 进程优先数 PRIORITY，并规定优先数越大的进程，其优先权越高
   • 进程已占用CPU时间 CPUTIME
   • 进程还需占用的CPU时间 ALLTIME，当进程运行完毕时， ALLTIME变为0
   • 进程的阻塞时间 STARTBLOCK，表示当进程再运行 STARTBLOCK个时间片后，进程将进入阻塞状态
   • 进程被阻塞的时间 BLOCKTIME，表示已阻塞的进程再等待 BLOCKTIME个时间片后，将转换成就绪状态
   • 进程状态 STATE
   • 队列指针NEXT，用来将PCB排成队列

3. 优先数改变的原则

   • 进程在就绪队列中呆一个时间片，优先数增加1
   • 进程每运行一个时间片，优先数减3

4. 假设在调度前，系统中有5个进程，合理设计它们的初始状态

5. 初始状态参考示例如下

为了清楚地观察每个进程的调度过程，程序应将每个时间片内的进程的情况显示出来，包括正在运行的进程，处于就绪队列中的进程和处于阻塞队列中的进程。
参照的具体格式如下：

• 源代码

#include <stdio.h>
#include <stdlib.h>
#include <string.h>
// 最大进程数
#define MAX_PROCESS_NUM 100
// 初始进程数
int process_num = 0;
// 进程结构体
typedef struct PCB {
	int ID;
	int PRIORITY;
	int CPUTIME;
	int ALLTIME;
	int STARTBLOCK;
	int BLOCKTIME;
	char STATE[10];
	struct PCB* NEXT;
}PCB;
// 全局进程队列
PCB* ALL_PROCESS[MAX_PROCESS_NUM];
// 阻塞队列头节点，空数据
PCB* block_process_queue_head = (PCB*)malloc(sizeof(PCB));
// 就绪队列头节点，空数据
PCB* ready_process_queue_head = (PCB*)malloc(sizeof(PCB));


// 初始化进程
void init_process() {
	printf("输入进程的初始化信息:\n");
	PCB* before = ready_process_queue_head;
	for (int i=0; i<process_num; i++) {
		PCB* p = (PCB*)malloc(sizeof(PCB));
		// 加入全局进程队列
		ALL_PROCESS[i] = p;
		before->NEXT = p;
		scanf("%d %d %d %d %d %d %s", &p->ID, &p->PRIORITY, &p->CPUTIME, &p->ALLTIME, &p->STARTBLOCK, &p->BLOCKTIME, p->STATE);
		p->NEXT = NULL;
		before = p;
		
	}

}

void print_addr(PCB* head) {
	PCB* curr = head;
	while (curr != NULL) {
		printf("%p --> ", curr);
		curr = curr->NEXT;
	}
	printf("\n");
}

void print_ready_queue(int curr_pid) {
	PCB* curr = ready_process_queue_head->NEXT;
	while (curr != NULL) {
		if (curr->ID != curr_pid) {
			printf("-->id:%d ", curr->ID);
		}
		curr = curr->NEXT;
	}
	printf("\n");
}

void print() {

	printf("ID\t\t");
	for (int i=0; i<5; i++) {
		printf("%d\t", ALL_PROCESS[i]->ID);
	}
	printf("\n");
	
	printf("PRIORITY\t");
	for (int i=0; i<5; i++) {
		printf("%d\t", ALL_PROCESS[i]->PRIORITY);
	}
	printf("\n");

	printf("CPUTIME\t\t");
	for (int i=0; i<5; i++) {
		printf("%d\t", ALL_PROCESS[i]->CPUTIME);
	}
	printf("\n");

	printf("ALLTIME\t\t");
	for (int i=0; i<5; i++) {
		printf("%d\t", ALL_PROCESS[i]->ALLTIME);
	}
	printf("\n");

	printf("STARTBLOCK\t");
	for (int i=0; i<5; i++) {
		printf("%d\t", ALL_PROCESS[i]->STARTBLOCK);
	}
	printf("\n");
	
	
	printf("BLOCKTIME\t");
	for (int i=0; i<5; i++) {
		printf("%d\t", ALL_PROCESS[i]->BLOCKTIME);
	}
	printf("\n");
	
	printf("STATE\t\t");
	for (int i=0; i<5; i++) {
		printf("%s\t", ALL_PROCESS[i]->STATE);
	}
	
	printf("\n\n\n");
	
}

void print_wait_queue() {
	PCB* curr = block_process_queue_head->NEXT;
	while (curr != NULL) {
		printf("-->id:%d ", curr->ID);
		curr = curr->NEXT;
	}
	printf("\n");		
}

// 查找优先级最高的就绪进程
PCB* find_max_priority_process() {
	PCB* temp = ready_process_queue_head->NEXT;
	int max_priority = 0;
	PCB* max_pointer = NULL;
	while (temp != NULL) {
		if(max_priority <= temp->PRIORITY) {
			max_priority = temp->PRIORITY;
			max_pointer = temp;
		}
		temp = temp->NEXT;
	}
	return max_pointer;
	
}
// 将阻塞的进程加入等待队列，并从就绪队列中移除
void push_to_block_process(int be_block_pid) {
	PCB* before_curr = ready_process_queue_head;
	PCB* curr = ready_process_queue_head->NEXT;
	while (curr != NULL) {
		if (curr->ID == be_block_pid) {
			strcpy(curr->STATE, "BLOCK");
			before_curr->NEXT = curr->NEXT;
			
			PCB* temp = block_process_queue_head->NEXT;
			block_process_queue_head->NEXT = curr;
			curr->NEXT = temp;
			break;
		}
		before_curr = before_curr->NEXT;
		curr = curr->NEXT;
	}
}


// 就绪队列优先数改变
void change_ready_process_priority(int curr_pid) {
	PCB* curr = ready_process_queue_head->NEXT;
	while (curr != NULL) {
		if (curr->ID != curr_pid) {
			curr->PRIORITY ++;
		}
		curr = curr->NEXT;	
	}
}

// 阻塞队列检查
void check_block_process() {
	PCB* before_curr = block_process_queue_head;
	PCB* curr = block_process_queue_head->NEXT;
	while (curr != NULL) {
		if(curr -> BLOCKTIME == 0) {
			// 移出阻塞队列，加入就绪队列
			before_curr->NEXT = curr->NEXT;
			PCB* temp = ready_process_queue_head->NEXT;
			ready_process_queue_head->NEXT = curr;
			curr->NEXT = temp;
			curr->STARTBLOCK = -1;
			strcpy(curr->STATE, "READY");
			curr = before_curr->NEXT;
		} else if (curr -> BLOCKTIME > 0) {
			curr -> BLOCKTIME --;
			curr = curr->NEXT;
			before_curr = before_curr->NEXT;
		}
	}
}
// 进行执行完成，移出就绪队列
void process_finish(int curr_pid) {
	PCB* before = ready_process_queue_head;
	PCB* curr = ready_process_queue_head->NEXT;
	while (curr != NULL) {
		if (curr->ID == curr_pid) {
			before->NEXT = curr->NEXT;
			strcpy(curr->STATE, "END");
			break;
		}
		before = before->NEXT;
		curr = curr->NEXT;
		
	}
}

// 运行某一进程, 每运行一个时间片, 都要从队列中重新检查优先数
void run_process() {

	// 每一次循环代表一次时间片
	for (int time_slice = 1; ready_process_queue_head->NEXT != NULL || block_process_queue_head->NEXT != NULL; time_slice++) {
		printf("第%d个 time_slice:\n", time_slice);
		// 找到当前优先数最大的就绪进程
		PCB* ready_to_run = find_max_priority_process();
	
		if (ready_to_run != NULL) {	
			
			// 当前运行进程的优先数-3
			if(ready_to_run->PRIORITY-3 > 0) {
				ready_to_run->PRIORITY -= 3;
			} else {
				ready_to_run->PRIORITY = 0;
			}
			
			// 就绪队列进程的优先数+1
			change_ready_process_priority(ready_to_run->ID);
						
			// 当前进程占用时间片+1
			ready_to_run->CPUTIME ++;
			// 当前进程还需要的时间片-1
			ready_to_run->ALLTIME = ready_to_run->ALLTIME > 0 ? ready_to_run->ALLTIME-1 : ready_to_run->ALLTIME;
			// 	当前进程开始阻塞倒计时-1
			if (ready_to_run->STARTBLOCK > 0) {
				ready_to_run->STARTBLOCK --;
			}
			printf("RUNNING_PROG: %d\n", ready_to_run->ID);
			
			// 到达阻塞时刻
			if(ready_to_run->STARTBLOCK == 0) {
				printf("开始阻塞\n");
				// 进入阻塞队列
				push_to_block_process(ready_to_run->ID);
			}
			
//			print_addr(ready_process_queue_head);
			
			// 进程完成
			if(ready_to_run -> ALLTIME == 0) {
				process_finish(ready_to_run->ID);
			}
			
			printf("READY_QUEUE: ");
			print_ready_queue(ready_to_run->ID);
			
			printf("BLOCK_QUEUE:");
			print_wait_queue();
			
			printf("----------------------------------------------------\n");
		}
		// 阻塞队列检查
		check_block_process();	
		print();
	}	
}
int main() {
	printf("输入需要初始化进程的个数:\n");
	scanf("%d", &process_num);
	// 初始化进程信息
	init_process();
	// 运行进程
	run_process();
	return 0;
}

// test data
//0 9 0 3 2 3 READY
//1 38 0 3 -1 0 READY
//2 30 0 6 -1 0 READY
//3 29 0 3 -1 0 READY
//4 0 0 4 -1 0 READY

• 实验截图