说明:
1、假设有只两种状态,就绪状态和结束状态。进程的初始状态都为就绪状态。
2、每次运行所设计的处理器调度程序调度进程之前,为每个进程随机生成它的要求运行时间。
3、模拟处理器调度,被选中的进程并不实际启动运行,而是执行已运行时间+1来模拟进程的一次
运行,表示进程已经运行过一个单位时间
主要算法的流程图。
1、非抢占式(包括FCFS,SJF,Priority):
2、抢占式(包括SRTF):
3、轮转调度(包括Round_Robin):
1、数据结构:
class Process_Control_Block; //进程控制单元类,用于存储进程信息
class PCB_LIST; //循环链表类,用于存储和处理事件队列
enum PCB_State {READY, FINISH}; //进程的两种状态,就绪状态和结束状态
2、符号说明:
using PCB = Process_Control_Block; //将PCB定义为Pross_Control_Block的别名
2、头文件:
#include <iostream>
#include<string>
#include <cstdlib>
#include<ctime> //srand()要用
#include <iomanip> //setw()要用
using namespace std;
具体声明:
//进程控制单元类
class Process_Control_Block {
public:
string name; //进程名
int arriveTime; //到达时间
int needTime; //要求运行时间
int remainTime; //剩余运行时间
int runTime; //已运行时间
int beginTime; //开始时间
bool isFirstExe; //判断是否第一次执行
int endTime; //结束时间
int priority; //作业优先级
int turnaroundTime; //轮转时间
PCB_State state; //进程状态类型
Process_Control_Block* next; //指向下一个的指针
Process_Control_Block();//无参构造
Process_Control_Block(string pcb_name, int pcb_atime, int pcb_priority);//带参构造
Process_Control_Block(const PCB* sour);//拷贝构造
void showPCB(); //打印PCB信息
};
//用于存储进程队列的循环链表类
class PCB_LIST {
public:
PCB* head; //表头结点
PCB_LIST() {
head = new PCB();
head->next = head; //初始时头结点的下一个还是头结点
}
void InsertByArriveTime(PCB* pcb); //按到达时间插入
void InsertByNeedTime(PCB* pcb); //按进程所需时间插入
void InsertByEndTime(PCB* pcb); //按进程结束时间插入
void InsertByPriority(PCB* pcb); //按进程优先级插入
void InsertByRemainTime(PCB* pcb); //按进程剩余时间插入
void InsertAtTail(PCB* pcb); //插入到队列最后
bool deleteByName(string pcb_name); //根据进程名删除进程
bool updata(PCB* pcb);//更新某进程的状态
void showAll(); //打印全部进程状态
bool isEmpty(); //判断链表中所有进程任务都已完成
int getSize(); //获得队列长度
PCB* getTail();//获得队列中最后一个PCB
double getAverTurnTime(); //获得平均轮转时间
double getAverWaitTime();//计算平均等待时间
double getThroughput();//获得吞吐量
double getResponseTime(); //获得平均响应时间
void clear_list();//清空队列
PCB* FetchFirstPCB(); //获取队列中第一个PCB
};
(其中函数具体实现代码见附录)
3、程序清单及注释:
函数声明:
//打印进程信息表头
void print_header();
//计算并打印进程总体信息(如吞吐量,CPU利用率等)
void showInfo(PCB_LIST* finishQueue);
//输入作业信息,按发生时间插入队列
void wirite_list(PCB_LIST* pcb_list);
//PCB的拷贝方法(不改变指针指向,只改变内容)
void CopyPCB(PCB* dest, const PCB* sour);
//最短作业时间优先
void SJF(PCB_LIST* pcb_list);
//先来先服务
void FCFS(PCB_LIST* pcb_list);
//最短剩余时间优先
void SRTF(PCB_LIST* pcb_list);
//按优先级,运行一个时间片后下调优先级别(时间片长度为2)
void Priority(PCB_LIST* pcb_list);
//时间片轮转(时间片大小为2)
void Round_Robin(PCB_LIST* pcb_list);
具体实现:
//最短作业时间优先
void SJF(PCB_LIST* pcb_list) {
int currentTime = 0; //当前时间
bool isCPU_Busy = false; //CPU忙碌状态
PCB_LIST* readyQueue = new PCB_LIST(); //就绪队列
PCB_LIST* finishQueue = new PCB_LIST(); //结束队列
PCB* run_pcb = pcb_list->FetchFirstPCB(); //正在运行的pcb
PCB* arrived_pcb = run_pcb; //当前已经到达的pcb
while (!pcb_list->isEmpty()) { //判断事件队列是否为空
while (arrived_pcb != pcb_list->head && currentTime >= arrived_pcb->arriveTime) {
if (isCPU_Busy) { //如CPU忙碌,则按作业时间插入就绪队列
readyQueue->InsertByNeedTime(arrived_pcb);
}
else {
run_pcb = arrived_pcb; //如CPU空闲,将到达的pcb设为正在运行的pcb
}
arrived_pcb = arrived_pcb->next;
}
if (run_pcb->state == PCB_State::READY) {
isCPU_Busy = true;
if (run_pcb->isFirstExe) { //第一次执行记录开始时间
run_pcb->beginTime = currentTime; //进程发生时间为当前时间
run_pcb->isFirstExe = false;
}
run_pcb->runTime = currentTime - run_pcb->beginTime; //已运行时间
run_pcb->remainTime = run_pcb->needTime - run_pcb->runTime; //剩余运行时间
if (run_pcb->runTime == run_pcb->needTime) {
run_pcb->endTime = currentTime; //设定结束时间
run_pcb->turnaroundTime = run_pcb->endTime - run_pcb->arriveTime;
run_pcb->state = PCB_State::FINISH; //状态改为结束
finishQueue->InsertByEndTime(run_pcb); //按结束时间插入结束队列
}
currentTime++;
}
if (run_pcb->state == PCB_State::FINISH) {
cout << "时间:" << currentTime - 1 << endl;
cout << "此时运行的进程:" << endl;
print_header();
run_pcb->showPCB();
cout << "结束的进程:" << endl;
print_header();
finishQueue->showAll();
string finish_name = run_pcb->name; //已结束进程的名字
isCPU_Busy = false;
readyQueue->deleteByName(finish_name);
if (!readyQueue->isEmpty()) {
run_pcb = readyQueue->FetchFirstPCB(); //取就绪队列的第一个
}
pcb_list->deleteByName(finish_name);
cout << "就绪队列状态:" << endl;
print_header();
readyQueue->showAll();
cout << endl;
}
}
showInfo(finishQueue); //打印总体信息
}
//先来先服务
void FCFS(PCB_LIST* pcb_list) {
int currentTime = 0; //当前时间
bool isCPU_Busy = false; //CPU忙碌状态
PCB_LIST* readyQueue = new PCB_LIST(); //就绪队列
PCB_LIST* finishQueue = new PCB_LIST(); //结束队列
PCB* run_pcb = pcb_list->FetchFirstPCB(); //取最先到达的进程运行
PCB* arrived_pcb = run_pcb; //当前已经到达的pcb
while (!pcb_list->isEmpty()) { //判断事件队列是否为空
while (arrived_pcb != pcb_list->head) {
readyQueue->InsertByArriveTime(arrived_pcb);
arrived_pcb = arrived_pcb->next;
}
if (run_pcb->state == PCB_State::READY) {
isCPU_Busy = true;
if (run_pcb->arriveTime > currentTime) {
currentTime = run_pcb->arriveTime;
}
run_pcb->beginTime = currentTime;
run_pcb->endTime = run_pcb->beginTime + run_pcb->needTime;
run_pcb->runTime = run_pcb->needTime;
currentTime = run_pcb->endTime;
run_pcb->remainTime = 0;
run_pcb->turnaroundTime = run_pcb->endTime - run_pcb->arriveTime;
run_pcb->state = PCB_State::FINISH;
finishQueue->InsertByEndTime(run_pcb);
}
if (run_pcb->state == PCB_State::FINISH) {
cout << "时间:" << currentTime - 1 << endl;
cout << "在运行的进程:" << endl;
print_header();
run_pcb->showPCB();
cout << "已完成的线程:" << endl;
print_header();
finishQueue->showAll();
string finish_name = run_pcb->name; //已结束进程的名字
isCPU_Busy = false;
readyQueue->deleteByName(finish_name);
if (!readyQueue->isEmpty()) {
run_pcb = readyQueue->FetchFirstPCB(); //取就绪队列的第一个开始运行
}
pcb_list->deleteByName(finish_name);
cout << "就绪队列状态:" << endl;
print_header();
readyQueue->showAll();
cout << endl;
}
}
showInfo(finishQueue); //打印总体信息
}
//按优先级(每次运行后优先级不变)
void Priority(PCB_LIST* pcb_list)
{
int currentTime = 0; //当前时间
bool isCPU_Busy = false; //CPU忙碌状态
PCB_LIST* readyQueue = new PCB_LIST(); //就绪队列
PCB_LIST* finishQueue = new PCB_LIST(); //结束队列
PCB* run_pcb = pcb_list->FetchFirstPCB(); //正在运行的pcb
PCB* arrived_pcb = run_pcb; //当前已经到达的pcb
while (!pcb_list->isEmpty()) { //判断事件队列是否为空
while (arrived_pcb != pcb_list->head && currentTime >= arrived_pcb->arriveTime) {
if (isCPU_Busy) { //如CPU忙碌,则按作业优先级插入就绪队列
readyQueue->InsertByPriority(arrived_pcb);
}
else {
run_pcb = arrived_pcb; //如CPU空闲,将到达的pcb设为正在运行的pcb
}
arrived_pcb = arrived_pcb->next;
}
if (run_pcb->state == PCB_State::READY) {
isCPU_Busy = true;
if (run_pcb->isFirstExe) { //第一次执行记录开始时间
run_pcb->beginTime = currentTime; //进程发生时间为当前时间
run_pcb->isFirstExe = false;
}
run_pcb->runTime = currentTime - run_pcb->beginTime; //已运行时间
run_pcb->remainTime = run_pcb->needTime - run_pcb->runTime; //剩余运行时间
if (run_pcb->runTime == run_pcb->needTime) {
run_pcb->endTime = currentTime; //设定结束时间
run_pcb->turnaroundTime = run_pcb->endTime - run_pcb->arriveTime; //计算轮转时间
run_pcb->state = PCB_State::FINISH; //状态改为结束
finishQueue->InsertByEndTime(run_pcb); //按结束时间插入结束队列
}
currentTime++;
}
if (run_pcb->state == PCB_State::FINISH) {
cout << "时间:" << currentTime - 1 << endl;
cout << "在运行的进程:" << endl;
print_header();
run_pcb->showPCB();
cout << "已完成的进程:" << endl;
print_header();
finishQueue->showAll();
string finish_name = run_pcb->name; //已结束进程的名字
isCPU_Busy = false;
readyQueue->deleteByName(finish_name);
if (!readyQueue->isEmpty()) {
run_pcb = readyQueue->FetchFirstPCB(); //取就绪队列的第一个
}
pcb_list->deleteByName(finish_name);
cout << "就绪队列状态:" << endl;
print_header();
readyQueue->showAll();
cout << endl;
}
}
showInfo(finishQueue); //打印总体信息
}
//按优先级,运行一个时间片后下调优先级别(时间片长度为2)
void Priority_2(PCB_LIST* pcb_list) {
int currentTime = 0; //当前时间
bool isCPU_Busy = false; //CPU忙碌状态
PCB_LIST* readyQueue = new PCB_LIST(); //就绪队列
PCB_LIST* finishQueue = new PCB_LIST(); //结束队列
int timeSlice = 2; //时间片大小为2
PCB* run_pcb = pcb_list->FetchFirstPCB(); //正在运行的pcb(最先到达的进程)
PCB* arrived_pcb = run_pcb; //当前已经到达的pcb
while (!pcb_list->isEmpty()) {//判断事件队列是否为空
while (arrived_pcb != pcb_list->head && currentTime >= arrived_pcb->arriveTime) { //如当前时间已超过到达时间,则插入就绪队列
if (isCPU_Busy) { //如CPU忙碌,则按到达时间插入就绪队列末尾
cout << "就绪队列状态:" << endl;
readyQueue->showAll();
run_pcb = readyQueue->FetchFirstPCB();
}
else {
run_pcb = arrived_pcb; //如CPU空闲,将到达的pcb设为正在运行的pcb
}
arrived_pcb = arrived_pcb->next; //到达的pcb指向下一个
}
if (!readyQueue->isEmpty())
run_pcb = readyQueue->FetchFirstPCB(); //取就绪队列的第一个
else { //如就绪队列为空,就直接取事件队列第一个,并将当前时间设为它的到达时间
run_pcb = pcb_list->FetchFirstPCB();
}
if (run_pcb->state == PCB_State::READY) {
isCPU_Busy = true;
if (run_pcb->isFirstExe) {
run_pcb->beginTime = currentTime; //进程发生时间为当前时间
run_pcb->isFirstExe = false;
}
currentTime += timeSlice; //每次加时间片的长度
run_pcb->runTime += timeSlice; //已运行时间+时间片长度
run_pcb->remainTime = run_pcb->needTime - run_pcb->runTime; //计算剩余时间
run_pcb->priority += 2;
if (run_pcb->remainTime <= 0) {
run_pcb->endTime = currentTime + run_pcb->remainTime; //设定结束时间(减去小于0的部分)
run_pcb->turnaroundTime = run_pcb->endTime - run_pcb->arriveTime; //计算轮转时间
run_pcb->state = PCB_State::FINISH; //状态改为结束
run_pcb->remainTime = 0; //保证剩余时间不是负数
finishQueue->InsertByEndTime(run_pcb); //按结束时间插入结束队列
}
pcb_list->updata(run_pcb); //更新事件队列中的信息
PCB* temp = new PCB(run_pcb);
readyQueue->deleteByName(run_pcb->name); //删除原队列中正在运行的进程
if (temp->state == PCB_State::READY)//如没有结束
readyQueue->InsertByPriority(temp); //重新插入就绪队列尾部
while (arrived_pcb != pcb_list->head && arrived_pcb->arriveTime <= currentTime) { //查看此时有无到达的队列
readyQueue->InsertByPriority(arrived_pcb); //插入到达的进程
arrived_pcb = arrived_pcb->next; //到达的pcb指向下一个
}
if (temp->state != PCB_State::READY) { //如进程结束了就打印信息
cout << "时间:" << currentTime << endl;
cout << "在该时间片运行进程:" << endl;
print_header();
temp->showPCB();
cout << "结束的进程:" << endl;
print_header();
finishQueue->showAll();
cout << "运行结束后就绪队列状态:" << endl;
print_header();
readyQueue->showAll();
cout << endl;
}
}
if (run_pcb->state == PCB_State::FINISH) {
string finish_name = run_pcb->name; //已结束进程的名字
isCPU_Busy = false;
readyQueue->deleteByName(finish_name);
if (!readyQueue->isEmpty()) {
run_pcb = readyQueue->FetchFirstPCB(); //取就绪队列的第一个
}
pcb_list->deleteByName(finish_name);
}
}
showInfo(finishQueue); //打印总体信息
}
//最短剩余时间优先
void SRTF(PCB_LIST* pcb_list) {
int currentTime = 0; //当前时间
bool isCPU_Busy = false; //CPU忙碌状态
PCB_LIST* readyQueue = new PCB_LIST(); //就绪队列
PCB_LIST* finishQueue = new PCB_LIST(); //结束队列
PCB* run_pcb = pcb_list->FetchFirstPCB(); //正在运行的pcb
PCB* arrived_pcb = run_pcb; //当前已经到达的pcb
while (!pcb_list->isEmpty()) {//判断事件队列是否为空
while (arrived_pcb != pcb_list->head && currentTime >= arrived_pcb->arriveTime) { //如当前时间已超过到达时间,则插入就绪队列
if (isCPU_Busy) { //如CPU忙碌,则按作业剩余时间插入就绪队列
readyQueue->InsertByRemainTime(arrived_pcb); //将新进入的进程插入就绪队列
if (arrived_pcb->remainTime <= run_pcb->remainTime) { //新进入的进程剩余时间小于正在运行的进程,则终止正在运行的进程,重新插入就绪队列
PCB* re_run = new PCB(run_pcb);
readyQueue->deleteByName(run_pcb->name); //删除原队列中的数据
readyQueue->InsertByRemainTime(re_run); //重新插入队列中
run_pcb = readyQueue->FetchFirstPCB(); //新的运行进程为就绪队列最前的进程
}
}
else {
run_pcb = arrived_pcb; //如CPU空闲,将到达的pcb设为正在运行的pcb
}
arrived_pcb = arrived_pcb->next;
}
if (run_pcb->state == PCB_State::READY) {
isCPU_Busy = true;
if (run_pcb->isFirstExe) {
run_pcb->beginTime = currentTime; //进程发生时间为当前时间
run_pcb->isFirstExe = false;
}
run_pcb->runTime++; //已运行时间+1
run_pcb->remainTime = run_pcb->needTime - run_pcb->runTime; //计算剩余时间
if (run_pcb->remainTime == 0) {
run_pcb->endTime = currentTime; //设定结束时间
run_pcb->turnaroundTime = run_pcb->endTime - run_pcb->arriveTime; //计算轮转时间
run_pcb->state = PCB_State::FINISH; //状态改为结束
finishQueue->InsertByEndTime(run_pcb); //按结束时间插入结束队列
}
currentTime++;
}
if (run_pcb->state == PCB_State::FINISH) {
cout << "时间:" << currentTime - 1 << endl;
cout << "此时运行的进程:" << endl;
print_header();
run_pcb->showPCB();
cout << "结束的进程:" << endl;
print_header();
finishQueue->showAll();
string finish_name = run_pcb->name; //已结束进程的名字
isCPU_Busy = false;
readyQueue->deleteByName(finish_name);
if (!readyQueue->isEmpty()) {
run_pcb = readyQueue->FetchFirstPCB(); //取就绪队列的第一个
isCPU_Busy = true;
}
pcb_list->deleteByName(finish_name);
cout << "就绪队列状态:" << endl;
print_header();
readyQueue->showAll();
cout << endl;
}
}
showInfo(finishQueue); //打印总体信息
}
//时间片轮转(时间片大小为2)
void Round_Robin(PCB_LIST* pcb_list) {
int currentTime = 0; //当前时间
bool isCPU_Busy = false; //CPU忙碌状态
PCB_LIST* readyQueue = new PCB_LIST(); //就绪队列
PCB_LIST* finishQueue = new PCB_LIST(); //结束队列
int timeSlice = 2; //时间片大小为2
PCB* run_pcb = pcb_list->FetchFirstPCB(); //正在运行的pcb(最先到达的进程)
PCB* arrived_pcb = run_pcb; //当前已经到达的pcb
while (!pcb_list->isEmpty()) {//判断事件队列是否为空
while (arrived_pcb != pcb_list->head && currentTime >= arrived_pcb->arriveTime) { //如当前时间已超过到达时间,则插入就绪队列
if (isCPU_Busy) { //如CPU忙碌,则按到达时间插入就绪队列末尾
run_pcb = readyQueue->FetchFirstPCB();
}
else {
run_pcb = arrived_pcb; //如CPU空闲,将到达的pcb设为正在运行的pcb
}
arrived_pcb = arrived_pcb->next; //到达的pcb指向下一个
}
if (!readyQueue->isEmpty())
run_pcb = readyQueue->FetchFirstPCB(); //取就绪队列的第一个
else { //如就绪队列为空,就直接取事件队列第一个,并将当前时间设为它的到达时间
run_pcb = pcb_list->FetchFirstPCB();
}
if (run_pcb->state == PCB_State::READY) {
isCPU_Busy = true;
if (run_pcb->isFirstExe) {
run_pcb->beginTime = currentTime; //进程发生时间为当前时间
run_pcb->isFirstExe = false;
}
currentTime += timeSlice; //每次加时间片的长度
run_pcb->runTime += timeSlice; //已运行时间+时间片长度
run_pcb->remainTime = run_pcb->needTime - run_pcb->runTime; //计算剩余时间
if (run_pcb->remainTime <= 0) {
run_pcb->endTime = currentTime + run_pcb->remainTime; //设定结束时间(减去小于0的部分)
run_pcb->turnaroundTime = run_pcb->endTime - run_pcb->arriveTime; //计算轮转时间
run_pcb->state = PCB_State::FINISH; //状态改为结束
run_pcb->remainTime = 0; //保证剩余时间不是负数
finishQueue->InsertByEndTime(run_pcb); //按结束时间插入结束队列
}
pcb_list->updata(run_pcb); //每次更新时间队列中的信息
PCB* temp = new PCB(run_pcb);
readyQueue->deleteByName(run_pcb->name); //删除原队列中正在运行的进程
if (temp->state == PCB_State::READY)//如没有结束
readyQueue->InsertAtTail(temp); //重新插入就绪队列尾部
while (arrived_pcb != pcb_list->head && arrived_pcb->arriveTime <= currentTime) { //查看此时有无到达的队列
readyQueue->InsertAtTail(arrived_pcb); //插入到达的进程
arrived_pcb = arrived_pcb->next; //到达的pcb指向下一个
}
if (temp->state != PCB_State::READY) { //如进程结束了就打信息
cout << "时间:" << currentTime << endl;
cout << "在该时间片运行进程:" << endl;
print_header();
temp->showPCB();
cout << "结束的进程:" << endl;
print_header();
finishQueue->showAll();
cout << "运行结束后就绪队列状态:" << endl;
print_header();
readyQueue->showAll();
cout << endl;
}
}
if (run_pcb->state == PCB_State::FINISH) {
string finish_name = run_pcb->name; //已结束进程的名字
isCPU_Busy = false;
readyQueue->deleteByName(finish_name);
if (!readyQueue->isEmpty()) {
run_pcb = readyQueue->FetchFirstPCB(); //取就绪队列的第一个
}
pcb_list->deleteByName(finish_name);
}
}
showInfo(finishQueue); //打印总体信息
}
//打印表头
void print_header() {
cout << setw(8) << "进程名" << setw(10) << "到达时间" << setw(10) << "所需时间" << setw(10) << "开始时间" << setw(10) << "结束时间" << setw(10)<<"运行时间" << setw(10) << "剩余时间" << setw(8) << "优先级" << endl;
}
//打印进程总体信息
void showInfo(PCB_LIST* finishQueue) {
cout << "CPU Utilization: 100%" << endl;
cout << "Throughput: " << finishQueue->getThroughput() << endl;
cout << "Average turnaround time: " << finishQueue->getAverTurnTime() << endl;
cout << "Average waiting time: " << finishQueue->getAverWaitTime() << endl;
cout << "Response time: 0" << endl;
}
//输入作业信息,按发生时间插入队列
void wirite_list(PCB_LIST* pcb_list) {
pcb_list->InsertByArriveTime(new PCB("B", 2, 1));
pcb_list->InsertByArriveTime(new PCB("A", 0, 1));
pcb_list->InsertByArriveTime(new PCB("C", 5, 2));
pcb_list->InsertByArriveTime(new PCB("D", 5, 1));
pcb_list->InsertByArriveTime(new PCB("E", 12, 4));
pcb_list->InsertByArriveTime(new PCB("F", 15, 2));
}
//PCB的拷贝方法(不改变指针指向,只改变内容)
void CopyPCB(PCB* dest, const PCB* sour) {
dest->arriveTime = sour->arriveTime;
dest->name = sour->name;
dest->needTime = sour->needTime;
dest->priority = sour->priority;
dest->remainTime = sour->remainTime;
dest->runTime = sour->runTime;
dest->beginTime = sour->beginTime;
dest->state = sour->state;
dest->endTime = sour->endTime;
dest->isFirstExe = sour->isFirstExe;
dest->turnaroundTime = sour->turnaroundTime;
}
主函数:
int main()
{
PCB_LIST* pcb_list = new PCB_LIST(); //新建事件队列
cout << "---------------SRTF---------------" << endl;
wirite_list(pcb_list);
SRTF(pcb_list);
pcb_list->clear_list();
cout << "---------------SJF---------------" << endl;
wirite_list(pcb_list);
SJF(pcb_list);
pcb_list->clear_list();
cout << "---------------FCFS---------------" << endl;
wirite_list(pcb_list);
FCFS(pcb_list);
pcb_list->clear_list();
cout << "---------------Priority---------------" << endl;
wirite_list(pcb_list);
Priority(pcb_list);
pcb_list->clear_list();
cout << "---------------Round_Robin---------------" << endl;
wirite_list(pcb_list);
Round_Robin(pcb_list);
pcb_list->clear_list();
}
附录
循环链表类PCB_LIST及进程控制块类PCB函数实现代码:
1、PCB类:
void Process_Control_Block::showPCB() {
cout<< setw(8) << name << setw(10) << arriveTime << setw(10)<< needTime << setw(10) << beginTime << setw(10) << endTime << setw(10) << runTime << setw(10) << remainTime << setw(8) << priority << endl;
}
//拷贝构造
Process_Control_Block::Process_Control_Block(const PCB* sour) {
arriveTime = sour->arriveTime;
name = sour->name;
needTime = sour->needTime;
priority = sour->priority;
remainTime = sour->remainTime;
runTime = sour->runTime;
beginTime = sour->beginTime;
state = sour->state;
endTime = sour->endTime;
turnaroundTime = sour->turnaroundTime;
isFirstExe = sour->isFirstExe;
next = NULL;
}
//无参构造
Process_Control_Block::Process_Control_Block() {
needTime = 1 + rand() % 10;
state = PCB_State::READY; //状态设为就绪
runTime = 0; //已运行时间设为0
beginTime = 0; //开始时间设为0
endTime = 0; //结束时间设为0
remainTime = needTime; //时间等于所需时间
isFirstExe = true; //是第一次指行
arriveTime = 0; //到达时间设为0
priority = 0; //优先级设为0
turnaroundTime = 0; //轮转时间设为0
next = NULL; //初始的下一个事件为空
}
//带参构造
Process_Control_Block::Process_Control_Block(string pcb_name, int pcb_atime, int pcb_priority) {
name = pcb_name;
arriveTime = pcb_atime;
priority = pcb_priority;
needTime = 1 + rand() % 10; //随机生成所需时间
state = PCB_State::READY; //状态设为就绪
runTime = 0; //已运行时间设为0
beginTime = 0; //发生时间设为0
endTime = 0; //结束时间设为0
turnaroundTime = 0; //轮转时间设为0
isFirstExe = true; //是第一次指行
remainTime = needTime; //时间等于所需时间
next = NULL; //初始的下一个事件为空
}
2、PCB_LIST类:
//获得平均响应时间
double PCB_LIST::getResponseTime() {
PCB* p = head->next;
double sum = 0;
double n = getSize();
if (p->next == head)
return -1;
while (p != head) {
sum = sum + (p->beginTime - p->arriveTime);
p = p->next;
}
return sum / n;
}
void PCB_LIST::clear_list() {
PCB* p = head->next;
while (p != head) {
head->next = p->next;
delete p;
p = head->next;
}
}
//获得吞吐量
double PCB_LIST::getThroughput() {
if (!isEmpty()) {
double sum_time = getTail()->endTime;
double n = getSize();
return n / sum_time;
}
return 0;
}
//计算平均等待时间
double PCB_LIST::getAverWaitTime() {
PCB* p = head->next;
double sum = 0;
double n = getSize();
if (p->next == head)
return -1;
while (p != head) {
sum = sum + (p->endTime - p->arriveTime - p->runTime);
p = p->next;
}
return sum / n;
}
//获得平均轮转时间
double PCB_LIST::getAverTurnTime() {
PCB* p = head->next;
double sum = 0;
double n = getSize();
if (p->next == head)
return -1;
while (p != head) {
sum += p->turnaroundTime;
p = p->next;
}
return sum / n;
}
//获得尾部结点
PCB* PCB_LIST::getTail() {
PCB* p = head;
if (p->next == head)
return NULL;
while (p->next != head) {
p = p->next;
}
return p;
}
//获得队列长度
int PCB_LIST::getSize() {
int cont = 0;
PCB* p = head->next;
while (p != head) {
p = p->next;
cont++;
}
return cont;
}
//插入到队列最后
void PCB_LIST::InsertAtTail(PCB* pcb) {
PCB* p = head;
PCB* new_pcb = new PCB(pcb);
while (p->next != head) {
p = p->next;
}
p->next = new_pcb;
new_pcb->next = head;
}
//更新某进程的状态
bool PCB_LIST::updata(PCB* pcb) {
PCB* p = head->next;
if (p == head) { //如为空返回
return false;
}
while (p != head && p->name != pcb->name) { //找到要删除结点的前一个
p = p->next;
}
if (p == head) { //如没找到,返回false
return false;
}
CopyPCB(p, pcb);
return true;
}
//按进程剩余时间插入
void PCB_LIST::InsertByRemainTime(PCB* pcb) {
PCB* p = head;
PCB* new_pcb = new PCB(pcb);
while (p->next != head && p->next->remainTime < pcb->remainTime) {
p = p->next;
}
if (p == head && head->next == head) { //如链表中只有头结点
head->next = new_pcb;
new_pcb->next = head;
}
else if (p->next == head) { //如果要插在最后
p->next = new_pcb;
new_pcb->next = head;
}
else { //在中间插入
PCB* q = p->next;
p->next = new_pcb;
new_pcb->next = q;
}
}
//按进程优先级插入
void PCB_LIST::InsertByPriority(PCB* pcb) {
PCB* p = head;
PCB* new_pcb = new PCB(pcb);
while (p->next != head && p->next->priority < pcb->priority) {
p = p->next;
}
if (p == head && head->next == head) { //如链表中只有头结点
head->next = new_pcb;
new_pcb->next = head;
}
else if (p->next == head) { //如果要插在最后
p->next = new_pcb;
new_pcb->next = head;
}
else { //在中间插入
PCB* q = p->next;
p->next = new_pcb;
new_pcb->next = q;
}
}
//按到达时间插入
void PCB_LIST::InsertByArriveTime(PCB* pcb) {
PCB* p = head;
PCB* new_pcb = new PCB(pcb);
while (p->next != head && p->next->arriveTime < pcb->arriveTime) {
p = p->next;
}
if (p == head && head->next == head) { //如链表中只有头结点
head->next = new_pcb;
new_pcb->next = head;
}
else if(p->next == head) { //如果要插在最后
p->next = new_pcb;
new_pcb->next = head;
}
else { //在中间插入
PCB* q = p->next;
p->next = new_pcb;
new_pcb->next = q;
}
}
//按进程所需时间插入
void PCB_LIST::InsertByNeedTime(PCB* pcb) {
PCB* p = head;
PCB* new_pcb = new PCB(pcb);
while (p->next != head && p->next->needTime < pcb->needTime) {
p = p->next;
}
if (p == head && head->next == head) { //如链表中只有头结点
head->next = new_pcb;
new_pcb->next = head;
}
else if (p->next == head) { //如果要插在最后
p->next = new_pcb;
new_pcb->next = head;
}
else { //在中间插入
PCB* q = p->next;
p->next = new_pcb;
new_pcb->next = q;
}
}
//按进程结束时间插入
void PCB_LIST::InsertByEndTime(PCB* pcb) {
PCB* p = head->next;
PCB* new_pcb = new PCB(pcb);
while (p->next != head && p->next->endTime < pcb->endTime) {
p = p->next;
}
if (p == head && head->next == head) { //如链表中只有头结点
head->next = new_pcb;
new_pcb->next = head;
}
else if (p->next == head) { //如果要插在最后
p->next = new_pcb;
new_pcb->next = head;
}
else { //在中间插入
PCB* q = p->next;
p->next = new_pcb;
new_pcb->next = q;
}
}
//根据进程名删除进程
bool PCB_LIST::deleteByName(string pcb_name) {
PCB* p = head;
if (p->next == head) { //如链表为空返回
return false;
}
while (p->next != head && p->next->name != pcb_name) { //找到要删除结点的前一个
p = p->next;
}
if (p->next == head) { //如没找到,返回false
return false;
}
else {
PCB* q = p->next; //q为要删除结点
p->next = q->next;
delete q;
}
return true;
}
//打印全部进程状态
void PCB_LIST::showAll() {
PCB* p = head->next;
while (p != head) {
p->showPCB();
p = p->next;
}
}
//判断是否为空表
bool PCB_LIST::isEmpty() {
if (head->next == head)
return true;
return false;
}
//获取队列中第一个PCB
PCB* PCB_LIST::FetchFirstPCB() {
if (head->next == head)
return NULL;
return head->next;
}
运行截图:
1、测试数据:
2、运行结果
①SRTF:
②SJF:
③FCFS:
④Priority:
⑤Round_Robin
文章来源:https://www.toymoban.com/news/detail-474715.html
文章来源地址https://www.toymoban.com/news/detail-474715.html
到了这里,关于五种进程调度算法C++代码实现(FCFS、SJF、Priority、SRTF,Round Robin)的文章就介绍完了。如果您还想了解更多内容,请在右上角搜索TOY模板网以前的文章或继续浏览下面的相关文章,希望大家以后多多支持TOY模板网!