要求
一
编程实现对N个进程采用动态优先权调度算法调度执行的模拟。
每个用来标识进程的进程控制块PCB可用结构来描述,包括以下字段:
- 进程标识数ID。
- 进程优先数PRIORITY,并规定优先数越大的进程,其优先权越高。
- 进程已占用CPU时间CPUTIME。
- 进程还需占用的CPU时间ALLTIME。当进程运行完毕时,ALLTIME变为0。
- 进程的阻塞时间STARTBLOCK,表示当进程再运行STARTBLOCK个时间片后,进6程将进入阻塞状态。
- 进程被阻塞的时间BLOCKTIME,表示已阻塞的进程再等待BLOCKTIME个时间片后,将转换成就绪状态。
- 进程状态STATE。
- 队列指针NEXT,用来将PCB排成队列。
二
优先数改变的原则:
- 进程在就绪队列中呆一个时间片,优先数增加1。
- 进程每运行一个时间片,优先数减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个动作:
- 检查阻塞队列(阻塞队列是按blockTime从小到达排序的)的第一个进程是否应该结束阻塞状态(检查blockTime的值是否为0)。
- 开始执行!将running指针指向就绪队首的进程,并将其状态设置为run(0),然后将其allTime减一、cpuTime加一、先检验priority是否大于3再减三,如小于等于3直接设置为1、先检验startBlock是否大于0再减一,否则不执行(已经阻塞过的进程startBlock值为-1)。
- 不管是否执行的第三步,都执行两个函数
increasePriority();
和reducedBlockingTime();
,功能分别是“将其余就绪的进程优先数加一”和“将阻塞队列中的进程BlockTime减一”。两个函数的具体实现将在后续介绍。 - 打印所有进程的信息。
printAll(time);
函数具体实现将在后续介绍。 - 检查当前进程的剩余运行时间(allTime)和开始阻塞时间(startBlock)。如alltime=0就将其“杀掉”(执行
kill(running);
),如startBlock=0就将其阻塞(执行blocking(running);
及其他必要操作)。 - 结束本次循环的操作,如running不为空,将其状态转化为ready并将running指针指向空。
- 执行
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;
}
}
}
函数说明:本函数就是简单的冒泡排序算法,对于冒泡算法,详情请见这里。
总结
对于功能复杂的程序,我们可以分部进行编写,将程序模块化有助于对程序的解读和设计。如果哪里出现问题,可以针对某个出问题的函数进行修改。
最后附上全部代码:完整代码链接
版权声明:
本篇文章为作者原创,如若转载或应用,请注上本网站的链接地址,谢谢您遵守知识产权法。