要求

编程实现对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个进程赋值。为进程输入allTimeprioritystartBlockblockTime的值,并作如注释的检验,避免非法输入。然后将其状态置为就绪,再执行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;
		}
	}
}

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

总结

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


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