动态优先权进程调度过程模拟

女爷i 2023-03-13 02:10 8阅读 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。

## 任务分析 ##

进程控制块用结构体来表示，包含它的各项属性。建立两个队列：一个就绪队列，一个阻塞队列。创建一个进程控制块表示当前正在运行的进程。程序开始运行时，所有进程都在就绪队列中。当startblock减少到0时，进程进入阻塞队列。在阻塞队列中的进程，当blocktime减少到0时，转入就绪队列。在就绪队列中的进程，如果优先级比当前正在执行的进程高，就可以取代当前进程获取时间片。当前进程如果运行完毕，就绪队列中优先级最高的进程就可以成为新当前进程。

## 程序流程图 ##

![程序流程图][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzM4OTAyODQ0_size_16_color_FFFFFF_t_70 1]

## 程度源代码 ##

#include <iostream>
    #include <string>
    using namespace std;
    
    #define LEN 5 // 进程最大数量
    
    typedef enum STATE		// 进程状态
    { 
    	READY,				// 就绪
    	BLOCK,				// 阻塞
    	END					// 完成
    }STATE;
    
    // 定义进程控制块
    typedef struct PCB { 
    	int id;				// 进程标识符
    	int priority;		// 进程优先级
    	int cputime;		// 已占用的CPU时间
    	int alltime;		// 还需占用的CPU时间
    	int startblock;		// 阻塞时间
    	int blocktime;		// 被阻塞时间
    	STATE state;		// 进程状态
    }PCB;
    
    // 定义队列
    typedef struct queue { 
    	int size;			// 队列中进程的数量
    	PCB *data[LEN];		// 进程的指针
    }Queue;
    
    PCB ps[LEN];				// 进程数组
    PCB *cp;				// 当前正在运行的进程
    Queue rQueue, bQueue;	// 就绪队列 和 阻塞队列 
    
    // 就绪队列按优先级降序排序(使用了冒泡排序法)
    void rQueueSort() { 
    	PCB *temp;
    	for (int i = 0; i < rQueue.size - 1; i++) { 
    		for (int j = 0; j < rQueue.size - 1 - i; j++) { 
    			if (rQueue.data[j]->priority < rQueue.data[j + 1]->priority) { 
    				temp = rQueue.data[j];
    				rQueue.data[j] = rQueue.data[j + 1];
    				rQueue.data[j + 1] = temp;
    			}
    		}
    	}
    }
    
    // 初始化
    void init() { 
    	// 给进程赋值
    	for (int i = 0; i < LEN; i++) { 
    		ps[i].id = i;
    		ps[i].state = READY;
    		ps[i].cputime = 0;
    		ps[i].alltime = 3;
    		ps[i].blocktime = 0;
    		ps[i].startblock = -1;
    	}
    
    	ps[0].priority = 9;
    	ps[1].priority = 38;
    	ps[2].priority = 30;
    	ps[3].priority = 29;
    	ps[4].priority = 0;
    
    	ps[2].alltime = 6;
    	ps[4].alltime = 4;
    	ps[0].startblock = 2;
    	ps[0].blocktime = 3;
    
    	cp = NULL;			// 当前进程赋空
    	bQueue.size = 0;	// 阻塞队列没有进程
    	for (int i = 0; i < LEN; i++) { 
    		bQueue.data[i] = NULL;
    		rQueue.data[i] = &ps[i];
    	}
    	rQueue.size = 5;	// 所有进程全部进入就绪队列
    	rQueueSort();		// 对就绪队列排序
    }
    
    // 打印
    void print() { 
    	cout << "\nRUNNING PROG: ";
    	if (cp != NULL) { 
    		cout<< cp->id;
    	}
    	cout << "\nREADY_QUEUE:";
    	for (int i = 0; i < rQueue.size; i++) { 
    		cout<< "->" << rQueue.data[i]->id;
    	}
    	cout << "\nBLOCK_QUEUE:";
    	for (int i = 0; i < bQueue.size; i++) { 
    		cout << "->" << bQueue.data[i]->id;
    	}
    	cout << "\n-------------------------------------------------------" << endl;
    
    	cout << "ID\t\t";
    	for (int i = 0; i < LEN; i++) { 
    		cout << ps[i].id << "\t";
    	}
    
    	cout << "\nPRIORITY\t";
    	for (int i = 0; i < LEN; i++) { 
    		cout << ps[i].priority << "\t";
    	}
    
    	cout << "\nCPUTIME\t\t";
    	for (int i = 0; i < LEN; i++) { 
    		cout << ps[i].cputime << "\t";
    	}
    
    	cout << "\nALLTIME\t\t";
    	for (int i = 0; i < LEN; i++) { 
    		cout << ps[i].alltime << "\t";
    	}
    
    	cout << "\nSTARTBLOCK\t";
    	for (int i = 0; i < LEN; i++) { 
    		cout << ps[i].startblock << "\t";
    	}
    
    	cout << "\nBLOCKTIME\t";
    	for (int i = 0; i < LEN; i++) { 
    		cout << ps[i].blocktime << "\t";
    	}
    
    	cout << "\nSTATE\t\t";
    	for (int i = 0; i < LEN; i++) { 
    		if (ps[i].state == READY) { 
    			cout << "READY" << "\t";
    		}
    		else if (ps[i].state == BLOCK) { 
    			cout << "BLOCK" << "\t";
    		}
    		else if (ps[i].state == END) { 
    			cout << "END" << "\t";
    		}
    	}
    
    	cout << endl;
    }
    
    // 出队，返回进程指针
    PCB* pop(Queue *q) { 
    	PCB *temp;
    	if (q->size > 0) { 
    		temp = q->data[0];			// 取出队首进程
    		for (int i = 0; i < q->size - 1; i++) { 		
    			q->data[i] = q->data[i + 1];		// 其他进程依次向前移动
    		}
    		q->size--;
    		return temp;				// 返回队首进程
    	}
    	return NULL;
    }
    
    // 入队
    void push(Queue *q, PCB *p) { 
    	if (q->size < LEN) { 
    		q->data[q->size] = p;		// 将入队的进程放在队尾
    		q->size++;
    	}
    	return;
    }
    
    // 运行进程
    void run() { 
    	if (rQueue.size > 0 || bQueue.size > 0) { 
    		if (cp == NULL) { 			// 程序一开始运行时，从就绪队列取出首进程
    			cp = pop(&rQueue);
    		}
    		// 当前进程没有结束，但优先级比就绪队列首进程低
    		if (cp->alltime > 0 && cp->priority < rQueue.data[0]->priority) { 
    			push(&rQueue, cp);		// 将当前进程放入就绪队列 
    			cp = pop(&rQueue);		// 就绪队列队首进程成为当前进程
    		}
    
    		if (cp->alltime == 0) { 		// 如果当前进程运行结束
    			cp->state = END;		// 改变进程状态
    			cp = pop(&rQueue);		// 从就绪队列取出新的当前进程
    		}
    
    		cp->priority -= 3;			// 修改当前进程的优先级
    
    		// startblock为0，标志着当前进程要进入阻塞状态
    		if (cp->startblock == 0 && cp->blocktime > 0) { 
    			cp->state = BLOCK;		// 修改当前进程的状态
    			push(&bQueue, cp);		// 将当前进程加入阻塞队列
    			cp = pop(&rQueue);		// 从就绪队列取出新的当前进程
    		}
    		else if (cp->startblock > 0) { 	// 当前进程的startblock为正数时
    			cp->startblock--;			// 运行一次减一个时间片
    		}
    
    		cp->cputime++;					// 当前进程占用CPU时间片+1
    
    		if(cp->alltime > 0){ 			// 当前进程还需运行的时间片-1
    			cp->alltime--;	
    			if (cp->alltime == 0) { 		// 减到0时，修改进程状态
    				cp->state = END;
    			}
    		}
    
    		for (int i = 0; i < rQueue.size; i++) { 		// 每运行一个时间片
    			rQueue.data[i]->priority++;				// 就绪队列中的进程优先级+1
    		}
    
    		for (int i = 0; i < bQueue.size; i++) { 		// 每运行一个时间片
    			if (bQueue.data[i]->blocktime > 0) { 	// 阻塞队列中的进程blocktime-1
    				bQueue.data[i]->blocktime--;
    			}
    		}
    		// 当阻塞队列队首进程blocktime为0时
    		if (bQueue.size > 0 && bQueue.data[0]->blocktime == 0) { 
    			bQueue.data[0]->state = READY;		// 修改进程状态
    			push(&rQueue, pop(&bQueue));		// 将阻塞队列首进程取出，放入就绪队列
    		}
    
    		// 每运行一个时间片，就绪队列排一次序
    		rQueueSort();
    	}
    }
    
    // 主函数
    int main() { 
    	init();			// 初始化
    	print();		// 打印进程信息
    	while (1) { 
    		_sleep(1000);	
    		if (rQueue.size == 0 && bQueue.size == 0) { 	// 当两个队列都为空时，结束程序
    			cp->state = END;
    			break;
    		}
    		run();		// 运行进程
    		print();	// 打印进程信息
    	}
    
    	return 0;
    }

## 运行结果 ##

![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzM4OTAyODQ0_size_16_color_FFFFFF_t_70 2]

> 程序开始执行，当前进程是优先级最高的1号进程，1号进程的优先级减3、cputime++、alltime–。在就绪队列中的进程优先级全部加1。

![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzM4OTAyODQ0_size_16_color_FFFFFF_t_70 3]

> 执行几次之后，1号进程执行完毕而且优先级也不是最高的了，所以优先级为33的2号进程成为当前进程，开始执行。

![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzM4OTAyODQ0_size_16_color_FFFFFF_t_70 4]

> 2号进程执行一次后，优先级由33降低到30，于是3号进程成为当前进程，2号进程进入就绪队列等待。

![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzM4OTAyODQ0_size_16_color_FFFFFF_t_70 5]

> 同理，执行一次后，3号进程的优先级由33降低到30，2号进程再次成为当前进程，3号进程进入就绪队列等待。这个过程会重复几次，就不重复了。

![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzM4OTAyODQ0_size_16_color_FFFFFF_t_70 6]

> 3号进程执行完毕后退出，2号进程成为当前进程。

![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzM4OTAyODQ0_size_16_color_FFFFFF_t_70 7]

> 2号进程执行完毕后，0号进程成为当前进程。

![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzM4OTAyODQ0_size_16_color_FFFFFF_t_70 8]

> 0号进程执行2次后，startblock为0了，进入阻塞队列，停止运行，4号进程开始执行。

![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzM4OTAyODQ0_size_16_color_FFFFFF_t_70 9]

> 4号进程运行几次后，0号进程的blocktime为0了，0号进程从阻塞队列转入就绪队列

![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzM4OTAyODQ0_size_16_color_FFFFFF_t_70 10]

> 此时，4号进程的优先级低于0号进程，4号进程停止运行，0号进程再次运行。

![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzM4OTAyODQ0_size_16_color_FFFFFF_t_70 11]

> 最后，0号进程执行完毕后，只剩下4号进程了，4号进程执行一次也完成了。程序总体执行完毕。

[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzM4OTAyODQ0_size_16_color_FFFFFF_t_70]: /images/20230312/34c16974d2344145993e3a300302428a.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzM4OTAyODQ0_size_16_color_FFFFFF_t_70 1]: /images/20230312/aa02b5c9c64a4eab8c6bfec72442431e.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzM4OTAyODQ0_size_16_color_FFFFFF_t_70 2]: /images/20230312/2e00ad7223224efd9ff9b2d4518716e0.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzM4OTAyODQ0_size_16_color_FFFFFF_t_70 3]: /images/20230312/37eccc61c2d34f3b9e622fc657bd22a5.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzM4OTAyODQ0_size_16_color_FFFFFF_t_70 4]: /images/20230312/60b4dd53aaaf40bebd0e2e5cffaa0e4e.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzM4OTAyODQ0_size_16_color_FFFFFF_t_70 5]: /images/20230312/f45a9b266be040199d5fc5032300922c.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzM4OTAyODQ0_size_16_color_FFFFFF_t_70 6]: /images/20230312/bc3c5dfda4b744609ee06afe9269bc04.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzM4OTAyODQ0_size_16_color_FFFFFF_t_70 7]: /images/20230312/ac54b8cc5f8647eeb9857c01b1b9a975.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzM4OTAyODQ0_size_16_color_FFFFFF_t_70 8]: /images/20230312/6e6e51862efc42c1973166d0eab3bee4.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzM4OTAyODQ0_size_16_color_FFFFFF_t_70 9]: /images/20230312/86f9d34ec7714b45bcfd012727960ab1.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzM4OTAyODQ0_size_16_color_FFFFFF_t_70 10]: /images/20230312/5c66347a5f9241abb6265cb58e6e640f.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzM4OTAyODQ0_size_16_color_FFFFFF_t_70 11]: /images/20230312/ecb2624d19ad4a59829ddf171b5cf074.png