萤火小屋

优律的知识库

  • 首页
  • 归档
  • 分类
  • 标签
  • 留言
  • 关于

  • 搜索
消息队列 RabbitMQ Redis 双指针 力扣 动态代理 Git YAML SpringBoot SpringMVC 回溯算法 分治算法 归并排序 快排 手撕 事务 MySQL索引 MySQL 小技巧 Spring Framework Spring 动态规划 Linux Android 贪心算法 操作系统 进程调度模拟 IPv6 数据库 计算机组成原理 计算机基础 栈 Java 静态路由 路由器 交换机 数字通信 网络工程 计算机网络 Web http 大学学习技巧 程序设计 算法

动态优先权调度算法模拟

发表于 2019-11-25 | 分类于 操作系统学习日记 | 0 | 阅读次数 775
要求
一

编程实现对N个进程采用动态优先权调度算法调度执行的模拟。
每个用来标识进程的进程控制块PCB可用结构来描述,包括以下字段:

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

二

优先数改变的原则:

  1. 进程在就绪队列中呆一个时间片,优先数增加1。
  2. 进程每运行一个时间片,优先数减3。
三

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

C语言实现
一、主函数

代码如下:

void main(){
	initPCB();      // 初始化
	inputProcess(); // 输入进程
	runStart();     // 开始模拟
}

为了将程序尽可能的简化,我们把所有功能都写成函数。归结成三个主要过程函数,分别是初始化函数,输入函数,和开始执行函数。初始化函数,负责给全局变量赋值,给链表头赋值。输入函数,负责输入进程信息。开始执行函数,负责开始模拟算法的执行,是主要的函数。

二、全局变量

代码如下:

enum PCBState{ run, ready, block };  // 0运行,1就绪,2阻塞  pcb状态枚举
int numOfProcess;  // 进程个数全局变量
char *stateMaping[3] = { "run", "ready", "block" };

typedef struct PCB{
	int PID;
	int priority;     // 优先数
	int cpuTime;      // 进程已占用CPU时间
	int allTime;      // 进程还需占用的CPU时间
	int startBlock;   // 进程的阻塞时间,表示当进程再运行STARTBLOCK个时间片后,进程将进入阻塞状态
	int blockTime;    // 进程被阻塞的时间,表示已阻塞的进程再等待BLOCKTIME个时间片后,将转换成就绪状态
	int state;        // 进程状态
	struct PCB *next; // 下一个指针
}PCB;

PCB * readyQueueHead;  // 就绪队列头指针
PCB * blockQueueHead;  // 阻塞队列头指针

结构体按要求设计不再赘述。定义枚举类型,0表示运行,1表示就绪,2表示阻塞。定义全局变量int numOfProcess;表示进程个数。定义状态映射字符串指针数组,打印时方便观察。定义PCB * readyQueueHead;作为就绪队列头。定义PCB * blockQueueHead;作为阻塞队列头。

三、所有函数的声明(目录)

代码如下:

void inputProcess();       // 输入进程
void showInfo(PCB* pt);    // 打印当前单个进程信息
void blocking(PCB* pt);    // 将该进程加入阻塞队列
void readying(PCB* pt);    // 将该进程加入就绪队列
int getQueueLen(PCB* pt);  // 获取队列长度
void runStart();           // 开始模拟以运行
void initPCB();            // 初始化
void increasePriority();   // 给就绪队列的就绪状态进程优先数+1
void reducedBlockingTime();// 减少被阻塞进程的剩余时间
void sortByPriority();     // 根据优先权给队列排序
void printAll(int n);      // 打印当前时间片所有的进程
void kill();               // 终结掉当前运行的进程

四、初始化函数void initPCB();

代码如下:

void initPCB(){
	readyQueueHead = (PCB*)malloc(sizeof(PCB));  // 给头指针分配内存空间
	blockQueueHead = (PCB*)malloc(sizeof(PCB));
	readyQueueHead->next = NULL;  // 将头的next置空避免野指针
	blockQueueHead->next = NULL;
	printf("请输入进程个数:");    // 打印输入信息
	scanf("%d", &numOfProcess);   // 输入进程个数
	printf("\n");
}

执行的功能:1.给头指针分配内存空间。2. 将头的next置空避免野指针。3.打印输入信息并输入进程个数赋值给numOfProcess全局变量。

五、输入进程函数void inputProcess();

代码如下:

void inputProcess(){  // 输入进程
	printf("输入%d个进程的信息(运行时间、优先数、进程的开始阻塞时间、进程被阻塞的时间,注:PID自动从1开始)\n", numOfProcess);
	for (int i = 0; i<numOfProcess; i++){    // 循环输入numOfProcess个进程
		PCB* p = (PCB*)malloc(sizeof(PCB));  // 申请空间给新进程
		printf("PID %d:", i + 1);
		scanf("%d %d %d %d", &p->allTime, &p->priority, &p->startBlock, &p->blockTime);  // 输入当前进程的基本信息
		if (p->allTime <= 0){  // 检验输入:allTime不能小于等于0
			printf("运行时间必须大于0,已设置为1\n");
			p->allTime = 1;
		}
		if (p->allTime < p->startBlock){  // 检验输入:allTime不可小于startBlock
			p->startBlock = p->allTime - 1;
			printf("阻塞开始时间不能大于运行时间,已将阻塞开始时间设定为%d。\n", p->startBlock);
		}
		if (p->priority <= 0){  // 检验输入:priority不可小于等于0
			printf("优先数不能小于等于0,已将优先数设定为1。");
			p->priority = 1;
		}
		p->PID = i + 1;    // PID默认成输入顺序
		p->cpuTime = 0;    // cpuTime设置为0
		p->state = ready;  // 状态设置成就绪
		p->next = NULL;    // 避免野指针,置NULL
		readying(p);       // 加入就绪队列
	}
}

执行的功能:循环为numOfProcess个进程赋值。为进程输入allTime、priority、startBlock和blockTime的值,并作如注释的检验,避免非法输入。然后将其状态置为就绪,再执行readying(p);方法将其加入就绪队列。

六、加入就绪队列函数void readying(PCB* pt);

代码如下:

void readying(PCB* pt){
	if (pt == NULL){  // 如果参数指针为空直接结束
		return;
	}
	PCB* p = readyQueueHead;  // p是浮动指针
	PCB* q = p->next;         // q是p的后继
	if (q == NULL){           // 如果队列为空,直接结束
		p->next = pt;
		pt->next = NULL;
	}
	else{
		while (q != NULL && (pt->priority < q->priority)){  // 加入队列是按优先权从高到低排序
			p = q;
			q = q->next;
		}
		pt->next = q;      // 将pt的next指向q
		p->next = pt;      // 将p的next指向pt
	}
	pt->state = ready;     // 将pt状态设置为ready
}

执行的功能:将传进来的指针pt指向的PCB加入就绪队列。如果pt指空,直接结束函数。定义两个浮动指针p和q,p是q的前驱,q是p的后继。将头赋值给p,q就是队列的第一个PCB,当q为空,就相当于队列为空,直接结束。否则,按照priority比较pt和q,直到找到小于pt优先级的q,并将pt插入到其前面。最后将状态设置成ready(1)。

七、开始执行函数(核心函数)void runStart();

代码如下:

void runStart(){
	PCB* running = NULL; // 定义running为当前运行的进程指针
	int time = 0;        // 定义时间片初始化为0
	printAll(time);      // 打印初始化状态的全部进程
	while (getQueueLen(readyQueueHead)>0 || getQueueLen(blockQueueHead)>0){  // 只要两个队列有一个队列不为空就一直循环
		time++;  // 时间片+1
		
		// 1.检查阻塞队列第一个进程阻塞是否结束
		if (blockQueueHead->next != NULL && blockQueueHead->next->blockTime == 0){
			PCB* t = blockQueueHead->next;
			blockQueueHead->next = t->next;
			readying(t);
		}

		// 2.运行一个时间片
		running = readyQueueHead->next;
		if (running != NULL){
			running->state = run;
			(running->allTime)--;  // 运行时间减少一个时间片
			(running->cpuTime)++;  // 已经运行时间增加一个时间片
			if (running->priority <= 3){
				running->priority = 1;  // 不足3直接设置为1
			}
			else{
				running->priority -= 3;// 优先数-3
			}
			if (running->startBlock > 0){
				(running->startBlock)--;//阻塞倒计时
			}
		}

		// 3.不管有无运行状态的进程,都运行以下代码
		increasePriority();     // 等待的进程优先数均+1
		reducedBlockingTime();  // 将阻塞队列每个进程阻塞时间-1

		// 4.打印当前时间片所有的进程信息
		printAll(time);

		// 5.检查剩余运行时间、开始阻塞时间
		if (running != NULL && running->allTime <= 0){  // 检查是否该结束
			kill(running);
			running = NULL;
		}
		else if (running != NULL && running->startBlock == 0){  // 检查是否该阻塞
			readyQueueHead->next = running->next;
			(running->startBlock)--;
			blocking(running);
		}

		// 6.本次时间片结束
		if (running != NULL && running->state == run){
			running->state = ready;
			running = NULL;
		}

		// 7.重新将就绪队列排序
		sortByPriority();
	}
}

函数说明:我们的就绪队列是按优先级由大到小排列的,也就是说,队首的进程就是当前要执行的进程。
除去将时间片加一每个循环有7个动作:

  1. 检查阻塞队列(阻塞队列是按blockTime从小到达排序的)的第一个进程是否应该结束阻塞状态(检查blockTime的值是否为0)。
  2. 开始执行!将running指针指向就绪队首的进程,并将其状态设置为run(0),然后将其allTime减一、cpuTime加一、先检验priority是否大于3再减三,如小于等于3直接设置为1、先检验startBlock是否大于0再减一,否则不执行(已经阻塞过的进程startBlock值为-1)。
  3. 不管是否执行的第三步,都执行两个函数increasePriority();和reducedBlockingTime();,功能分别是“将其余就绪的进程优先数加一”和“将阻塞队列中的进程BlockTime减一”。两个函数的具体实现将在后续介绍。
  4. 打印所有进程的信息。printAll(time);函数具体实现将在后续介绍。
  5. 检查当前进程的剩余运行时间(allTime)和开始阻塞时间(startBlock)。如alltime=0就将其“杀掉”(执行kill(running);),如startBlock=0就将其阻塞(执行blocking(running);及其他必要操作)。
  6. 结束本次循环的操作,如running不为空,将其状态转化为ready并将running指针指向空。
  7. 执行sortByPriority();函数重新排序就绪队列。(该函数将在后续介绍其实现内容)。
八、就绪进程优先数加一函数void increasePriority();

代码如下:

void increasePriority(){
	if(readyQueueHead->next == NULL){  // 如果就绪队列为空直接结束函数
		return;
	}
	PCB* p = readyQueueHead->next;  // 定义p指针指向队首程序
	while (p != NULL){              // 如p不为空,执行
		if (p->state == ready){     // 如果p的状态为ready,执行
			(p->priority)++;        // 将p的优先数加一
		}
		p = p->next;  // p指针后移
	}
}

执行的功能:通过指针后移的方法将每个就绪状态的进程优先数都加一。

九、阻塞时间减一函数void reducedBlockingTime();

代码如下:

void reducedBlockingTime(){
	if(blockQueueHead->next == NULL){  // 如果阻塞队列为空直接结束函数
		return;
	}
	PCB* p = blockQueueHead->next;  // 将p指向队首程序
	while (p != NULL){              // 如果p不为空继续循环
		(p->blockTime)--;           // p指向的程序blockTime减一
		p = p->next;                // p指针后移
	}
}

函数功能:用移动指针实现在链表中操作结构体中的变量,详细如注释,不再赘述。

十、打印所有进程函数void printAll(int n);

代码如下:

void printAll(int n){
	if (n == 0){  // 如果n为0,代表是刚输入完的初始化状态
		printf("=================================================初始化状态=================================================\n", n);
	}
	else{         // 否则是第n个时间片的打印
		printf("=================================================第%d个时间片=================================================\n", n);
	}
	printf("PID\t\tState\t\tPriority\tAllTime\t\tCPUTime\t\tStartBlock\tBlockTime\n");  // 打印表头信息
	PCB* pr = readyQueueHead;  // 定义两个可移动的队头指针
	PCB* pb = blockQueueHead;  // 分别指向就绪和阻塞队列
	while (pr->next != NULL){  // 通过指针后移来实现遍历链表
		showInfo(pr->next);
		pr = pr->next;
	}
	while (pb->next != NULL){  // 同上
		showInfo(pb->next);
		pb = pb->next;
	}
	printf("============================================================================================================\n\n");
}

函数说明:该函数通过指针后移来实现遍历两个链表,本函数调用了void showInfo(PCB* pt);函数,下面将介绍这个函数。

十一、打印单个进程的进程信息函数void showInfo(PCB* pt)

代码如下:

void showInfo(PCB* pt){
	if (pt == NULL){  // 如果pt指向空直接结束函数
		return;
	}
	printf("%-8d\t", pt->PID);     // 打印pt指向的进程所有的信息并向左对齐
	printf("%-8s\t", stateMaping[pt->state]);
	printf("%-8d\t", pt->priority);
	printf("%-8d\t", pt->allTime);
	printf("%-8d\t", pt->cpuTime);
	printf("%-8d\t", pt->startBlock);
	printf("%-8d\n", pt->blockTime);
}

函数功能:本函数是实现打印单个进程的信息,目的是配合void printAll(int n);使用。

十二、杀进程函数void kill();

代码如下:

void kill(){
	PCB* p = readyQueueHead;    // 定义p指针指向队头
	PCB* q = p->next;           // 定义q指向队首,即p的后继,即链表第一个节点
	while(q != NULL){           // 如果q不为空继续循环
		if(q->state == run){    // 找到正在运行的进程
			p->next = q->next;  // 将其前驱指向其后继
			free(q);            // 将其节点释放掉
			break;              // 然后退出循环
		}
		p = q;       // p指针后移
		q = q->next; // q指针后移
	}
}

函数说明:本函数是将run状态的进程杀掉,而不是传参来杀,所以需要在外部判断run的allTime是否为0。本函数的原理依然是利用移动指针来寻找run状态的函数(其实run状态的函数就位于就绪队列的队首,即第一个节点)。

十三、加入阻塞队列函数void blocking(PCB* pt);

代码如下:

void blocking(PCB* pt){
	if (pt == NULL){  // 如果pt指向空直接结束函数
		return;
	}
	PCB* p = blockQueueHead;  // p是浮动指针,指向对头
	PCB* q = p->next;         // q是p的后继,指向队首
	if (q == NULL){           // 如q为空
		p->next = pt;         // 直接将pt挂在对头的next
		pt->next = NULL;      // 然后将pt的next指向空
	}
	else{
		while (q != NULL && pt->blockTime > q->blockTime){  // 加入队列的同时按阻塞时间从低到高排序
			p = q;         // 通过指针后移找到插入点
			q = q->next;
		}
		pt->next = q;      // 插入,pt指向q
		p->next = pt;      // p指向pt
	}
	pt->state = block;     // pt状态设置成block(2)
}

函数说明:将进程加入阻塞队列函数的原理和加入就绪队列的原理相同,请见第六项。

十四、就绪队列排序函数void sortByPriority();

代码如下:

void sortByPriority(){
	PCB* p = readyQueueHead;  // 定义p指针指向对头
	PCB* q = p->next;         // 定义q指针指向队首,即第一个节点
	if (q == NULL){           // 如果第一个节点为空,直接结束
		return;
	}
	int n = getQueueLen(readyQueueHead);  // 获取就绪队列长度并赋值给n
	for (int i = n; i>1; i--){            // 用冒泡算法实现排序
		p = readyQueueHead;               // 每次循环开始时将p和q指针归位
		q = p->next;
		for (int j = 1; j<i; j++){        // 循环i-1次
			if (q->next != NULL && q->priority < q->next->priority){  // 比较
				PCB *t1 = (PCB*)malloc(sizeof(PCB));       // 创建用来替换的节点
				t1->allTime = q->next->allTime;            // 为新节点赋值
				t1->blockTime = q->next->blockTime;
				t1->cpuTime = q->next->cpuTime;
				t1->PID = q->next->PID;
				t1->priority = q->next->priority;
				t1->startBlock = q->next->startBlock;
				t1->state = q->next->state;
				t1->next = q->next->next;
				free(q->next);          // 释放掉q的后继
				q->next = t1->next;     // 并让q的next指向t1的后继
				t1->next = q;           // t1的next指向q
				p->next = t1;           // p的next指向t1
				q = t1;                 // q指向t1
			}
			p = q;        // 指针后移
			q = q->next;
		}
	}
}

函数说明:本函数就是简单的冒泡排序算法,对于冒泡算法,详情请见这里。

总结

对于功能复杂的程序,我们可以分部进行编写,将程序模块化有助于对程序的解读和设计。如果哪里出现问题,可以针对某个出问题的函数进行修改。
最后附上全部代码:完整代码链接


版权声明:
本篇文章为作者原创,如若转载或应用,请注上本网站的链接地址,谢谢您遵守知识产权法。

# 进程调度模拟 # 操作系统
IPv6基础
贪心算法
  • 文章目录
  • 站点概览
优律

优律

优律的知识库

83 日志
20 分类
44 标签
E-mail Twitter Instagram
Links
  • CZLisyx - 浮生志
  • Vedfolnir
0%
© 2019 — 2023 萤火小屋——优律的博客网站
网站已勉强运行 
Halo博客系统技术支持