#include<stdio.h>
#include<stdlib.h>
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;
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();
PCB * readyQueueHead; // 就绪队列头指针
PCB * blockQueueHead; // 阻塞队列头指针
void inputProcess(){ // 输入进程
printf("输入%d个进程的信息(运行时间、优先数、进程的开始阻塞时间、进程被阻塞的时间,注:PID自动从1开始)\n", numOfProcess);
for (int i = 0; i<numOfProcess; i++){
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){
printf("运行时间必须大于0,已设置为1\n");
p->allTime = 1;
}
if (p->allTime < p->startBlock){
p->startBlock = p->allTime - 1;
printf("阻塞开始时间不能大于运行时间,已将阻塞开始时间设定为%d。\n", p->startBlock);
}
if (p->priority <= 0){
printf("优先数不能小于等于0,已将优先数设定为1。");
p->priority = 1;
}
p->PID = i + 1;
p->cpuTime = 0;
p->state = ready;
p->next = NULL;
readying(p); // 加入就绪队列
}
}
void printAll(int n){
if (n == 0){
printf("=================================================初始化状态=================================================\n", n);
}
else{
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){ // 打印进程信息
if (pt == NULL){
return;
}
printf("%-8d\t", pt->PID);
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 blocking(PCB* pt){ // 加入阻塞队列
if (pt == NULL){
return;
}
PCB* p = blockQueueHead; // p是浮动指针
PCB* q = p->next; // q是p的后继
if (q == NULL){
p->next = pt;
pt->next = NULL;
}
else{
while (q != NULL && pt->blockTime > q->blockTime){ // 加入队列的同时按阻塞时间从低到高排序
p = q;
q = q->next;
}
pt->next = q;
p->next = pt;
}
pt->state = block;
}
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;
p->next = pt;
}
pt->state = ready;
}
int getQueueLen(PCB* head){ // 获取队列长度
int counter = 0;
if (head == NULL){
return counter;
}
if (head->next == NULL){
return counter;
}
PCB* p = head->next;
while (p != NULL){
counter++;
p = p->next;
}
return counter;
}
void initPCB(){
readyQueueHead = (PCB*)malloc(sizeof(PCB));
blockQueueHead = (PCB*)malloc(sizeof(PCB));
readyQueueHead->next = NULL;
blockQueueHead->next = NULL;
printf("请输入进程个数:");
scanf("%d", &numOfProcess);
printf("\n");
}
void increasePriority(){ // 将就绪队列的进程优先数加1
if(readyQueueHead->next == NULL){
return;
}
PCB* p = readyQueueHead->next;
while (p != NULL){
if (p->state == ready){
(p->priority)++;
}
p = p->next;
}
}
void reducedBlockingTime(){
if(blockQueueHead->next == NULL){
return;
}
PCB* p = blockQueueHead->next;
while (p != NULL){
(p->blockTime)--;
p = p->next;
}
}
void sortByPriority(){ // 从高到低排序
PCB* p = readyQueueHead;
PCB* q = p->next;
if (q == NULL){
return;
}
int n = getQueueLen(readyQueueHead);
for (int i = n; i>1; i--){
p = readyQueueHead;
q = p->next;
for (int j = 1; j<i; j++){
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->next = t1->next;
t1->next = q;
p->next = t1;
q = t1;
}
p = q;
q = q->next;
}
}
}
void kill(){
PCB* p = readyQueueHead;
PCB* q = p->next;
while(q != NULL){
if(q->state == run){
p->next = q->next;
free(q);
break;
}
p = q;
q = q->next;
}
}
void runStart(){
PCB* running = NULL;
int time = 0;
printAll(time);
while (getQueueLen(readyQueueHead)>0 || getQueueLen(blockQueueHead)>0){
time++;
// 检查阻塞队列第一个进程阻塞是否结束
if (blockQueueHead->next != NULL && blockQueueHead->next->blockTime == 0){
PCB* t = blockQueueHead->next;
blockQueueHead->next = t->next;
readying(t);
}
// 运行一个时间片
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)--;//阻塞倒计时
}
}
// 不管有无运行状态的进程,都运行以下代码
increasePriority(); // 等待的进程优先数均+1
reducedBlockingTime(); // 将阻塞队列每个进程阻塞时间-1
// 打印
printAll(time);
// 检查剩余运行时间、开始阻塞时间
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);
}
// 本次时间片结束
if (running != NULL && running->state == run){
running->state = ready;
running = NULL;
}
// 重新将就绪队列排序
sortByPriority();
}
}
void main(){
initPCB(); // 初始化
inputProcess(); // 输入进程
runStart(); // 开始模拟
}