发表于 | 分类于 | 0 | 阅读次数 818
要求
一

编程实现对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;
		}
	}
}

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

总结

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


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