动态优先权进程调度算法模拟链表实现

朱雀 2023-03-13 02:12 29阅读 0赞

## 实验名称： ##

动态优先权调度过程中就绪队列的模拟

## 实验要求： ##

采用动态优先权的进程调度算法，用C语言编程模拟调度过程中每个时间片内的就绪队列。

## 实验内容： ##

（1）每个进程控制块PCB用结构描述，包括以下字段：  
\*进程标识符id  
\*进程优先数priority,并规定优先数越大的进程，其优先权越高。  
\*进程已占用的CPU时间cputime  
\*进程还需占用的CPU时间alltime，当进程运行完毕时，aiitime变为0  
\*进程的阻塞时间startblock,当进程再运行startblock个时间片后，进程将进入阻塞状态  
\*进程被阻塞的时间blocktime,已阻塞的进程再等待blocktime 个时间片后，将转换成就绪状态  
\*进程状态state  
\*队列指针next,将PCB排成队列。

（2）调度前，系统中有五个进程，它们的初始状态如下：  
![进程初始状态][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzM4OTAyODQ0_size_16_color_FFFFFF_t_70]  
（3）进程在就绪队列呆一个时间片,优先数增加1。  
（4）进程每运行一个时间片，优先数减3。

## 程序源代码 ##

#include <stdio.h>
    #include <stdlib.h>
    
    #define LEN 5 // 进程最大数量
    
    typedef enum STATE		// 进程状态
    { 
    	RUN,				// 运行
    	READY,				// 就绪
    	BLOCK,				// 阻塞
    	END					// 完成
    }STATE;
    
    // 定义进程控制块
    typedef struct PCB { 
    	int id;				// 进程标识符
    	int priority;		// 进程优先级
    	int cputime;		// 已占用的CPU时间
    	int alltime;		// 还需占用的CPU时间
    	int startblock;		// 阻塞时间
    	int blocktime;		// 被阻塞时间
    	STATE state;		// 进程状态
    	struct PCB *next;
    }PCB;
    
    PCB* head;		// 链表头指针
    int time;		// 时间片数量
    
    // 初始化
    void init() { 
    	head = NULL;
    	time = 0;
    	int id = 0;
    	PCB* temp;
    	PCB* rear;
    	
    	// 创建5个进程控制块
    	while (id < LEN) { 
    		temp = (PCB *)malloc(sizeof(PCB));
    		temp->id = id;
    		temp->next = NULL;
    
    		if (head == NULL) { 
    			head = temp;
    			rear = temp;
    		}
    		else { 
    			rear->next = temp;
    			rear = temp;
    		}
    
    		id++;
    	}
    
    	// 给进程赋值
    	for (PCB* i = head; i != NULL; i = i->next) { 
    		i->state = READY;
    		i->cputime = 0;
    		i->alltime = 3;
    		i->blocktime = 0;
    		i->startblock = -1;
    
    		if (i->id == 0) { 
    			i->priority = 9;
    			i->startblock = 2;
    			i->blocktime = 3;
    		}
    
    		if (i->id == 1) { 
    			i->priority = 38;
    		}
    
    		if (i->id == 2) { 
    			i->priority = 30;
    			i->alltime = 6;
    		}
    
    		if (i->id == 3) { 
    			i->priority = 29;
    		}
    
    		if (i->id == 4) { 
    			i->priority = 0;
    			i->alltime = 4;
    		}
    	}
    }
    
    // 打印
    void print() { 
    	printf("\n时间片：%d", time);	// 时间片
    	printf("\nRUNNING PROG: ");		// 当前正在运行的进程
    	PCB *temp = head;
    	while (temp != NULL) { 
    		if (temp->state == RUN) { 
    			printf("%d", temp->id);
    			break;
    		}
    		temp = temp->next;
    	}
    	
    	printf("\nREADY_QUEUE:");		// 就绪队列
    	temp = head;
    	while (temp != NULL) { 
    		if (temp->state == READY) { 
    			printf("->%d", temp->id);
    		}
    		temp = temp->next;
    	}
    	
    	printf("\nBLOCK_QUEUE:");	// 阻塞队列
    	temp = head;
    	while (temp != NULL) { 
    		if (temp->state == BLOCK) { 
    			printf("->%d", temp->id);
    		}
    		temp = temp->next;
    	}
    	
    	printf("\n-------------------------------------------------------\n");
    
    	printf("ID\t\t");
    	temp = head;
    	while(temp != NULL){ 
    		printf("%d\t", temp->id);
    		temp = temp->next;
    	}
    
    	printf("\nPRIORITY\t");
    	temp = head;
    	while(temp != NULL){ 
    		printf("%d\t", temp->priority);
    		temp = temp->next;
    	}
    
    	printf("\nCPUTIME\t\t");
    	temp = head;
    	while(temp != NULL){ 
    		printf("%d\t", temp->cputime);
    		temp = temp->next;
    	}
    
    	printf("\nALLTIME\t\t");
    	temp = head;
    	while(temp != NULL){ 
    		printf("%d\t", temp->alltime);
    		temp = temp->next;
    	}
    
    	printf("\nSTARTBLOCK\t");
    	temp = head;
    	while(temp != NULL){ 
    		printf("%d\t", temp->startblock);
    		temp = temp->next;
    	}	
    
    	printf("\nBLOCKTIME\t");
    	temp = head;
    	while(temp != NULL){ 
    		printf("%d\t", temp->blocktime);
    		temp = temp->next;
    	}	
    
    	printf("\nSTATE\t\t");
    	temp = head;
    	while(temp != NULL){ 
    		if (temp->state == RUN) { 
    			printf("RUN\t");
    		}
    		else if (temp->state == READY) { 
    			printf("READY\t");
    		}
    		else if (temp->state == BLOCK) { 
    			printf("BLOCK\t");
    		}
    		else if (temp->state == END) { 
    			printf("END\t");
    		}
    		temp = temp->next;
    	}		
    
    	time++;
    	printf("\n");
    }
    
    // 模拟进程调度
    void run() { 
    	
    	PCB *temp;
    	PCB *cp;		// 当前运行的进程
    
    	cp = NULL;
    	temp = head;
    	// 从就绪队列中选择优先级最高的进程当作当前运行的进程
    	while (temp != NULL) { 
    		if (temp->state == READY) { 
    			if (cp == NULL) { 
    				cp = temp;
    			}
    			else { 
    				if (cp->priority < temp->priority) { 
    					cp = temp;
    				}
    			}
    		}
    		temp = temp->next;
    	}
    
    	cp->state = RUN;
    	cp->priority -= 3;
    	cp->cputime++;
    	cp->alltime--;
    	// alltime 为0时,进程运行结束
    	if (cp->alltime == 0) { 
    		cp->state = END;
    	}
    	// startblock 为0时,进程转为阻塞状态
    	if (cp->blocktime > 0 && cp->startblock > 0) { 
    		cp->startblock--;
    		if (cp->startblock == 0) { 
    			cp->state = BLOCK;
    		}
    	}
    
    	temp = head;
    	while (temp != NULL) { 
    		if (temp->state == READY) { 
    			temp->priority++;
    		}
    		else if (temp->state == BLOCK) { 
    			if (temp->blocktime > 0) { 
    				temp->blocktime--;
    				// 阻塞队列中的进程的blocktime 为0时,进程转为就绪状态
    				if (temp->blocktime == 0) { 
    					temp->state = READY;
    				}
    			}
    		}
    		temp = temp->next;
    	}
    
    	print();
    	if (cp->state == RUN) { 
    		cp->state = READY;
    	}
    }
    
    int main() { 
    	int flag;
    	PCB* temp;
    	init();			// 初始化
    	print();
    
    	while (1) { 
    		temp = head;
    		flag = 1;
    		while (temp != NULL) { 
    			if (temp->state != END) { 
    				flag = 0;
    			}
    			temp = temp->next;
    		}
    		// 当所有进程运行结束时退出
    		if (flag) { 
    			break;
    		}
    		run();
    	}
    	
    	return 0;
    }

[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzM4OTAyODQ0_size_16_color_FFFFFF_t_70]: /images/20230312/2f57647c535d4cbd9d91541015cb1d13.png