处理机调度算法模拟实现

您所在的位置：网站首页 › 处理机调度的主要目的是什么 › 处理机调度算法模拟实现

处理机调度算法模拟实现

2023-06-15 00:40| 来源: 网络整理| 查看: 265

#define _CRT_SECURE_NO_WARNINGS #include #include #include “malloc.h” #include

#include #include #include #include using namespace std;

#define debug(x) cerr PCB* firstProg; PCB* LastProg; int size; } PCBQueue;

// 函数声明 void print(PCB pro[], int num);//每个进程的到达时间

void inputProgram(PCB pro[], int num); //所有进程的具体信息

void PrintRunningprogram(PCB* pro);//正在运行的进程的信息

void PrintReadyqueue(PCBQueue* ready_queue);//就绪队列中的所有进程的信息

void PrintSortOfRunningprogram(PCB pro1[], int num);//进程的运行顺序

void CopyProgram(PCB* pro1, PCB* pro2);//将进程pro2的信息复制到进程pro1中

void Queueinit(PCBQueue* queue);//初始化就绪队列

void EnterQueue(PCBQueue* queue, PCB* pro);//将一个进程插入到就绪队列中

PCB* poll(PCBQueue* queue);//将一个进程从就绪队列中删除

void sortWithEnterTime(PCB pro[], int num);//将所有进程按到达时间升序排序

void EnterQueueOfRuntime(PCBQueue* ready_queue, PCB* program);//将一个进程按运行时间长短插入就绪队列

void EnterQueueOfPriority(PCBQueue* ready_queue, PCB* program);//将一个进程按优先级插入就绪队列

void EnterQueueOfXyb(PCBQueue* ready_queue, PCB* program);//将一个进程按响应比插入就绪队列

void FCFS(PCB pro[], int num);//先来先服务调度算法

void SJF(PCB pro[], int num);//短作业优先调度算法

void HRRF(PCB pro[], int num);//最高响应比调度算法

void RR(PCB pro[], int num);//时间片轮转调度算法

void MLFQ(PCB pro[], int num); //多级反馈调度算法

void print(PCB pro[], int num) //输出到达时间 { int i;

for (i = 0; i < num; i++) { printf("%d ", pro[i].arrivetime); }

}

void inputProgram(PCB pro[], int num)//输入所有进程的具体信息 { int i;

for (i = 0; i < num; i++) { PCB prog; printf("\t\t\t\t\t请输入第%d个进程的名字，到达时间，服务时间，优先级\n\t\t\t\t\t", i + 1); scanf("%s", prog.name); scanf("%d", &prog.arrivetime); scanf("%d", &prog.running_time); prog.copyRunning_time = prog.running_time; scanf("%d", &prog.priority); prog.remain_time = prog.running_time; pro[i] = prog; }

}

void PrintRunningprogram(PCB* pro)//输出运行进程 { printf(“\t正在执行进程%s\n”, pro->name); printf(“\t————————————————————————————————————————————————\n”); printf(“\t进程名字到达时间服务时间优先级开始时间结束时间周转时间带权周转时间\n”); printf(“\t%s\t\t%d\t%d\t%d”, pro->name, pro->arrivetime, pro->running_time, pro->priority); printf(“\t%d\t%d\t %5.2f\t%5.2f\n”, pro->start_time, pro->done_time, pro->zztime, pro->dqzztime); //printf(“\t%f\t%d\t %5.2f\t%5.2f\n”, pro->start_time, pro->done_time, pro->zztime, pro->dqzztime); printf(“\t————————————————————————————————————————————————\n\n”); }

void PrintReadyqueue(PCBQueue* ready_queue)//输出就绪队列 { PCB* p;

p = ready_queue->firstProg->next; if (!p) { printf("\t无进程处于就绪状态！\n"); printf("\t————————————————————————————————————————————————\n\n\n"); return; } printf("\t就绪队列：\n"); printf("\t————————————————————————————————————————————————\n"); printf("\t进程名字到达时间服务时间优先级\n"); while (p) { printf("\t%s\t\t%d\t%d\t%d\n", p->name, p->arrivetime, p->running_time, p->priority); p = p->next; } printf("\t————————————————————————————————————————————————\n"); printf("\n\n\n");

}

void PrintSortOfRunningprogram(PCB pro1[], int num) //输出进程运行顺序以及周转/带权周转时间 { int i;

printf("\t进程运行顺序如下：\n"); printf("\t————————————————————————————————————————————————\n"); printf("\t进程名字到达时间服务时间开始时间结束时间周转时间带权周转时间\n"); for (i = 0; i < num; i++) { printf("\t%s\t\t%d\t%d\t", pro1[i].name, pro1[i].arrivetime, pro1[i].running_time); printf("\t%d\t%d\t %5.2f\t%5.2f\n", pro1[i].start_time, pro1[i].done_time, pro1[i].zztime, pro1[i].dqzztime); //printf("\t%5.2f\t%d\t %5.2f\t%5.2f\n", pro1[i].start_time, pro1[i].done_time, pro1[i].zztime, pro1[i].dqzztime); } printf("\t————————————————————————————————————————————————\n\n\n");

}

void CopyProgram(PCB* pro1, PCB* pro2) //信息复制 { memcpy(pro1->name, pro2->name, sizeof(pro2->name)); pro1->arrivetime = pro2->arrivetime; pro1->running_time = pro2->running_time; pro1->priority = pro2->priority; pro1->start_time = pro2->start_time; pro1->done_time = pro2->done_time; pro1->zztime = pro2->zztime; pro1->dqzztime = pro2->dqzztime; }

void Queueinit(PCBQueue* queue)//初始化就绪队列 { if (queue == NULL) { return; } queue->size = 0; queue->LastProg = (PCB*)malloc(sizeof(PCB)); queue->LastProg->next = NULL;//注意加了此句 queue->firstProg = queue->LastProg; }

void EnterQueue(PCBQueue* queue, PCB* pro)//将一个进程插入到就绪队列中

{ //加入进程队列 queue->LastProg->next = (PCB*)malloc(sizeof(PCB)); queue->LastProg = queue->LastProg->next; queue->LastProg->arrivetime = pro->arrivetime; memcpy(queue->LastProg->name, pro->name, sizeof(pro->name)); queue->LastProg->priority = pro->priority; queue->LastProg->running_time = pro->running_time; queue->LastProg->copyRunning_time = pro->copyRunning_time; queue->LastProg->start_time = pro->start_time; queue->LastProg->next = NULL;//注意加了此句 queue->size++; }

PCB* poll(PCBQueue* queue) //将一个进程从就绪队列中删除 { PCB* temp;

temp = queue->firstProg->next; if (temp == queue->LastProg) { queue->LastProg = queue->firstProg; queue->LastProg->next = NULL;//注意加了此句 queue->size--; return temp; } queue->firstProg->next = queue->firstProg->next->next; queue->size--; return temp;

}

void sortWithEnterTime(PCB pro[], int num) //将进程按到达时间（arrivetime）全部排序 {

int i, j; PCB temp; for (i = 1; i < num; i++) { for (j = 0; j < num - i; j++) { if (pro[j].arrivetime > pro[j + 1].arrivetime) { temp = pro[j]; pro[j] = pro[j + 1]; pro[j + 1] = temp; } } }

}

void EnterQueueOfRuntime(PCBQueue* ready_queue, PCB* program) //将一个进程按运行时间长短插入就绪队列 { PCB* p, * q; p = ready_queue->firstProg->next; q = ready_queue->firstProg;

while (p) { if (p->running_time > program->running_time) { program->next = p; q->next = program; break; } q = p; p = p->next; } if (!p) //如果就绪队列为空或该进程的运行时间最长，则将其插入到队尾 { ready_queue->LastProg->next = program; ready_queue->LastProg = program; program->next = NULL; } ready_queue->size++;

}

void EnterQueueOfPriority(PCBQueue* ready_queue, PCB* program) //将一个进程按优先级插入就绪队列 { PCB* p, * q; p = ready_queue->firstProg->next; q = ready_queue->firstProg;

while (p) { if (p->priority < program->priority) { //优先级大的先执行 program->next = p; q->next = program; break; } q = p; p = p->next; } if (!p) { ready_queue->LastProg->next = program; ready_queue->LastProg = program; program->next = NULL; } ready_queue->size++;

}

void EnterQueueOfXyb(PCBQueue* ready_queue, PCB* program) //将一个进程按响应比大小插入就绪队列 { PCB* p, * q; p = ready_queue->firstProg->next; q = ready_queue->firstProg;

while (p) { if (p->xyb < program->xyb) //响应比大的先执行 { program->next = p; q->next = program; break; } q = p; p = p->next; } if (!p) //如果就绪队列为空或该进程的运行时间最长，则将其插入到队尾 { ready_queue->LastProg->next = program; ready_queue->LastProg = program; program->next = NULL; } ready_queue->size++;

}

void FCFS(PCB pro[], int num) //先来先服务 { int time, done_time; int i, count, tt, pronum; float sum_T_time, sum_QT_time; PCB* curpro, * temp_PCB;

printf("\n\t\t\t\t\t先来先服务算法模拟\n\n"); printf("\t————————————————————————————————————————————————\n"); count = 0; PCB pro2[100]; sortWithEnterTime(pro, num); //按照进入到达时间顺序排序 PCBQueue* queue = (PCBQueue*)malloc(sizeof(PCBQueue)); //定义就绪队列 Queueinit(queue); //就绪队列初始化 EnterQueue(queue, &pro[0]); //将第一个进程送入就绪队列中 time = pro[0].arrivetime; //记录第一个进程的到达时间 pronum = 1; //记录当前的进程数量 sum_T_time = 0, sum_QT_time = 0; // sum_T_time 记录总的周转时间，sum_QT_time 记录总的加权周转时间 while (queue->size > 0) { curpro = poll(queue); //从进程队列中取出一个进程 if (time < curpro->arrivetime) { time = curpro->arrivetime; } done_time = time + curpro->running_time; // done_time 为该进程的结束时间（开始时间+CPU运行时间） curpro->start_time = time; curpro->done_time = done_time; curpro->zztime = done_time - curpro->arrivetime; //周转时间 curpro->dqzztime = curpro->zztime / curpro->running_time; //带权周转时间 sum_T_time += curpro->zztime; // sum_T_time 总的周转时间更新 sum_QT_time += curpro->dqzztime; // sum_T_time 总的带权周转时间更新 for (tt = time; tt = pro[pronum].arrivetime) { EnterQueue(queue, &pro[pronum]); pronum++; } } CopyProgram(&pro2[count], curpro); PrintRunningprogram(&pro2[count]); count++; if (queue->size != 0) { printf("\t就绪队列：\n"); printf("\t————————————————————————————————————————————————\n"); printf("\t进程到达时间服务时间优先级\n"); temp_PCB = queue->firstProg->next; for (i = queue->size; i > 0; i--) { printf("\t%s\t%d\t%d\t%d\n", temp_PCB->name, temp_PCB->arrivetime, temp_PCB->running_time, temp_PCB->priority); temp_PCB = temp_PCB->next; } printf("\t————————————————————————————————————————————————\n"); printf("\n\n\n"); } else { printf("\t无进程处于就绪状态!\n"); printf("\t————————————————————————————————————————————————\n\n\n"); } time += curpro->running_time; if (queue->size == 0 && pronum < num) { //防止出现前一个进程执行完到下一个进程到达之间无进程进入 EnterQueue(queue, &pro[pronum]); pronum++; } } PrintSortOfRunningprogram(pro2, count); //Print(pro2,count); printf("\t平均周转时间为:%.2f\n", sum_T_time / num); printf("\t平均带权周转时间为:%.2f\n", sum_QT_time / num);

}

void SJF(PCB pro[], int num) //短作业优先 { int time, done_time; float sum_T_time, sum_QT_time; int i, pronum; PCBQueue* ready_queue; PCB* curpro, pro1[MAXSIZE];

printf("\n\t\t\t\t\t短作业优先算法模拟\n\n"); printf("\t————————————————————————————————————————————————\n"); sortWithEnterTime(pro, num); ready_queue = (PCBQueue*)malloc(sizeof(PCBQueue)); if (!ready_queue) { printf("分配就绪队列头结点空间失败！"); exit(1); } Queueinit(ready_queue); EnterQueueOfRuntime(ready_queue, &pro[0]); time = pro[0].arrivetime; pronum = 1; //记录当前的进程 sum_T_time = 0, sum_QT_time = 0; i = 0; while (ready_queue->size > 0) { curpro = poll(ready_queue);//就绪队列中的队头进程进入CPU中运行 if (time < curpro->arrivetime) { //如果该进程与上一次运行的进程结束时间之间有间隔，则将CPU运行时间变为该进程到达时间 time = curpro->arrivetime; } done_time = time + curpro->running_time; curpro->start_time = time; curpro->done_time = done_time; curpro->zztime = done_time - curpro->arrivetime;//周转时间 curpro->dqzztime = curpro->zztime / curpro->running_time;//带权周转时间 //打印正在运行的进程 PrintRunningprogram(curpro); //将curpro的信息复制到pro1[i]中 CopyProgram(&pro1[i], curpro); i++; sum_T_time += curpro->zztime; sum_QT_time += curpro->dqzztime; while (pronum < num) { //将在CPU中的进程运行的时间内到达的进程放入就绪队列 if (pro[pronum].arrivetime size == 0 && pronum < num) { //防止出现前一个进程执行完到下一个进程到达之间无进程进入 EnterQueueOfRuntime(ready_queue, &pro[pronum]); pronum++; } } PrintSortOfRunningprogram(pro1, num); printf("\t平均周转时间为:%.2f\n", sum_T_time / num); printf("\t平均带权周转时间为:%.2f\n", sum_QT_time / num);

}

void HRRF(PCB pro[], int num) //最高响应比 { int time, done_time; float sum_T_time, sum_QT_time; int i, pronum; float xyb; PCBQueue* ready_queue; PCB* curpro, pro1[MAXSIZE];

printf("\n\t\t\t\t\t最高响应比算法模拟\n\n"); printf("\t————————————————————————————————————————————————\n"); sortWithEnterTime(pro, num); //按到达时间排序 ready_queue = (PCBQueue*)malloc(sizeof(PCBQueue)); if (!ready_queue) { printf("分配就绪队列头结点空间失败！"); exit(1); } Queueinit(ready_queue); //初始化就绪队列 EnterQueue(ready_queue, &pro[0]); //将第一个进程送入就绪队列中 time = pro[0].arrivetime; pronum = 1; //记录当前的进程 sum_T_time = 0, sum_QT_time = 0; i = 0; while (ready_queue->size > 0) { curpro = poll(ready_queue); //就绪队列中的第一个进程进入CPU中运行 if (time < curpro->arrivetime) { time = curpro->arrivetime; //如果该进程与上一次运行的进程结束时间之间有间隔，则将CPU运行时间变为该进程到达时间 } done_time = time + curpro->running_time; curpro->start_time = time; curpro->done_time = done_time; curpro->zztime = done_time - curpro->arrivetime;//周转时间 curpro->dqzztime = curpro->zztime / curpro->running_time;//带权周转时间 //打印正在运行的进程 PrintRunningprogram(curpro); //将curpro的信息复制到pro1[i]中 CopyProgram(&pro1[i], curpro); i++; sum_T_time += curpro->zztime; sum_QT_time += curpro->dqzztime; while (pronum < num) { for (int i = 0; i < num && (pro[i].arrivetime //queue Finish_queue; //已完成队列

//Wait_queue[0]为第一级反馈队列的指针 int Queue_Num; //反馈队列数量 cout > Queue_Num; //按照进入到达时间顺序排序 sortWithEnterTime(pro, num); queue Coming_queue; //还未到达队列 queue Finish_queue; //已完成队列 for (int i = 0; i < num; ++i) Coming_queue.push(pro[i]);//加入待续队列

#define time_slice 1 //第一队列时间片长度默认为1 //指向存放各反馈队列时间片数组的指针 int* Queue_time_slice; //指向存放各反馈队列的指针的指针 queue** Wait_queue = new (queue*); Queue_time_slice = new int[Queue_Num];

for (int i = 0; i < Queue_Num; i++) { Queue_time_slice[i] = time_slice * pow(2, i); Wait_queue[i] = new queue; } auto accept_process = [&](int current_time) -> bool { bool flag = false; while (1) { if (Coming_queue.empty() == false && Coming_queue.front().arrivetime push(Coming_queue.front()); Coming_queue.pop(); flag = true; } else break; } return flag; }; auto runMLFQ = [&]() { bool over; //true表示进程都执行完 int current_time = Coming_queue.front().arrivetime; //系统当前时间 PCB temp; //存放要执行进程的pcb int t; //存放时间片 int queue_serial; //要执行进程所在队列号,从1~Queue_Num int count = 1; //调度次数 while (1) { int i; over = true; //接收当前时间到达的进程 accept_process(current_time); for (i = 0; i < Queue_Num; i++) { if (Wait_queue[i]->empty() == false) { over = false; temp = Wait_queue[i]->front(); Wait_queue[i]->pop(); t = Queue_time_slice[i]; queue_serial = i + 1; break; } } if (Coming_queue.empty() == false) over = false; if (over == true) break; cout

【本文地址】

处理机调度算法模拟实现

处理机调度算法模拟实现

今日新闻

推荐新闻