📄 进程调度算法.cpp
字号:
// diaodu.cpp : Defines the entry point for the console application.
//
//#include "stdafx.h"
#include "conio.h"
#include "iostream.h"
#include "fstream.h"
//--------------------------------------------------------------------------
#define KEY_EXIT '-'
typedef struct{
char ch;
char *label;
void (*pfunc)();
}MenuItemDef;
void clearscr(){cout<<"\n\n\n\n\n\n\n\n\n\n\n\n\n\n\n\n\n\n\n\n\n\n";}
int waitakey(){return getch();}
class MenuDef{
public:
int nCount;
MenuItemDef menu[24];
public:
MenuDef(){nCount=0;}
public:
void display()
{
for (int i=0;i<nCount;i++)
cout<<" "<<menu[i].ch<<"."<<menu[i].label<<endl;
cout<<" "<<KEY_EXIT<<"."<<"Exit"<<endl;
}
void run()
{ int ch;
do {
clearscr();
display();
ch=waitakey();
for (int i=0;i<nCount;i++)
if (menu[i].ch==ch)
menu[i].pfunc();
}while (ch!=KEY_EXIT);
}
void add(char ch0,char *plabel,void (*func)())
{ menu[nCount].ch=ch0;
menu[nCount].label=plabel;
menu[nCount].pfunc=func;
nCount++;
}
};
class PCB{
public:
PCB() { SetNull();}
public:
enum {kReady=0,kRun=1,kWait=2,kNew=3,kTerm=4,kDone=5};
char name[8];
int tmCPU; //需要cpu执行时间
int priority; //优先权
int tmArrive; //进程预计到达就绪队列时间
int tmEnd; //进程执行结束时间
int tmSum; //进程已经执行时间
int nStatus; //进程状态
int nPointer; //进程队列指针
public:
int IsBlank(){ return name[0]=='\0';}
int IsFinish(){ return tmSum==tmCPU;}
void Run(){tmSum++;}
void SetNull()
{name[0]='\0';tmCPU=tmArrive=tmEnd=tmSum=priority=0;nPointer=-1;nStatus=-1;}
double T(){return (double)(tmEnd-tmArrive);}
double Ti(){return (double)((tmEnd-tmArrive)*1.0/tmCPU);}
public:
public:
friend istream& operator>>(istream& stream,PCB&b)
{
stream>>b.name>>b.tmArrive>>b.tmCPU>>b.priority>>b.nPointer>>b.nStatus;
return stream;
}
friend ostream& operator<<(ostream& stream,PCB&b)
{
stream<<b.name<<'\t'<<b.tmArrive<<'\t'<<b.tmCPU<<'\t'<<b.priority<<'\t'<<b.nPointer<<'\t'<<b.nStatus<<endl;
return stream;
}
};
class Kernel{
public:
Kernel(){SetNull();}
public:
enum { kFCFS=0,kPriority,kRR}; //调度算法ID定义
int tmClick; //时钟
int bGrab; //是否允许抢占CPU，0：否 1：是
int nAlgID; //调度算法ID
PCB pcbs[32]; //进程控制块数组
int queRun,queRead,queWait; //运行、就绪、等待队列的头指针
int nSum; //进程数量
public:
void Run(); //主程序
void Process(); //输入新的进程信息
int IsFinish(); //是否所有进程已执行完毕
void SetAlgorithm(int kAlgId){nAlgID=kAlgId;}
void SetNull()
{ tmClick=bGrab=0;nAlgID=kFCFS;queRun=queRead=queWait=-1;
for (int i=0;i<sizeof(pcbs)/sizeof(pcbs[0]);i++)
pcbs[i].SetNull();
}
//functions should be implemented
void Create(PCB&pcb) //创建新进程
{
for (int i=0;i<sizeof(pcbs)/sizeof(pcbs[0]);i++)
if(pcbs[i].IsBlank())
{
pcbs[i] = pcb;
return;
}
}
void Terminate(int pid) //终止进程的执行
{
if(pcbs[pcbs[pid].nPointer].nStatus==PCB::kReady)//修改就绪队列
{
for(int i=0;i<nSum;i++)
if(pcbs[i].nPointer==pid)
{
pcbs[i].nPointer = pcbs[pid].nPointer;
break;
}
}
pcbs[pid].nStatus = PCB::kDone;
pcbs[pid].tmEnd = tmClick;
queRun = -1;
}
void FCFS() //先来先服务调度算法
{
if(queRead>=0)
{
queRun = queRead;
pcbs[queRun].nStatus = PCB::kRun;
if(pcbs[queRead].nPointer!=-1)
{
queRead = pcbs[queRead].nPointer;
}
else
queRead = -1;
}
}
void Priority() //优先权调度算法
{
int tmp=queRead,tmpi=queRead,tmpq=pcbs[queRead].priority;
while(tmp!=-1)
{
if(pcbs[tmp].priority>tmpq)
{
tmpq = pcbs[tmp].priority;
tmpi = tmp;
}
tmp = pcbs[tmp].nPointer;
}
if(tmpi==queRead)
queRead = pcbs[queRead].nPointer;
queRun = tmpi;
pcbs[queRun].nStatus = PCB::kRun;
}
void RR() //时间片轮转调度算法
{
if(queRead==-1 || pcbs[queRead].nStatus==PCB::kRun)
return;
pcbs[queRun].nStatus = PCB::kReady;
int tmp = queRead;
while(pcbs[tmp].nPointer!=queRun && tmp>0)
tmp = pcbs[tmp].nPointer;
if(tmp<0)
pcbs[queRun].nPointer = queRead;
queRun = queRead;
pcbs[queRun].nStatus = PCB::kRun;
if(pcbs[queRead].nPointer>=0)
queRead = pcbs[queRead].nPointer;
else
{
for(int i=0;i<32;i++)
if(pcbs[i].nStatus==PCB::kReady)
{
queRead = i;
break;
}
}
}
void Schedule() //调度程序
{
switch(nAlgID)
{
case kFCFS:
FCFS();
break;
case kPriority:
Priority();
break;
case kRR:
RR();
break;
default:
break;
}
return;
}
void Display() //显示状态信息
{
char zt[6][8] = {
"Ready","Run","Wait","New","Term","Done"
};
cout<<"进程名 开始时间 结束时间 周转时间 带权周转时间"<<endl;
for (int i=0;i<nSum;i++)
{
if(!pcbs[i].IsBlank())
cout<<pcbs[i].name<<"\t\t"<<pcbs[i].tmArrive<<" \t"<<pcbs[i].tmEnd<<" \t"<<pcbs[i].T()<<"\t\t"<<pcbs[i].Ti()<<endl;
}
cout<<"平均周转时间"<<T()<<endl;
cout<<"平均带权周转时间"<<Ti()<<endl;
getch();
return;
}
void DisplayAlg() //显示算法执行信息
{
char zt[6][8] = {
"Ready","Run","Wait","New","Term","Done"
};
switch(nAlgID)
{
case kFCFS:
cout<<"当前算法：FCFS"<<"\t";
break;
case kPriority:
cout<<"当前算法：Priority"<<"\t";
break;
case kRR:
cout<<"当前算法：RR"<<"\t";
break;
}
cout<<"系统运行时间"<<tmClick<<endl;
cout<<"进程名 要求时间 到达时间 优先权 运行时间 还要时间 状态"<<endl;
for (int i=0;i<nSum;i++)
{
if(!pcbs[i].IsBlank())
cout<<pcbs[i].name<<"\t\t"<<pcbs[i].tmCPU<<"\t"<<pcbs[i].tmArrive<<"\t"<<pcbs[i].priority<<"\t"<<pcbs[i].tmSum<<" \t"<<pcbs[i].tmCPU-pcbs[i].tmSum<<"\t"<<zt[pcbs[i].nStatus]<<endl;
}
}
void Input() //输入所有信息
{
cout<<"请输入进程数："<<endl;
cin>>nSum;
for(int i=0;i<nSum;i++)
{
cout<<"请输入第"<<i+1<<"个进程信息： 名称 就绪时间 需要时间 优先级"<<endl;
cin>>pcbs[i].name>>pcbs[i].tmArrive>>pcbs[i].tmCPU>>pcbs[i].priority;
pcbs[i].nStatus = PCB::kNew;
}
for (i=0;i<nSum;i++)//将输入的进程按就绪时间排列
{
for(int j=0;j<nSum-i-1;j++)
if(pcbs[j].tmArrive>pcbs[j+1].tmArrive && !pcbs[j].IsBlank() && !pcbs[j+1].IsBlank())
{
PCB tmp;
tmp = pcbs[j];
pcbs[j] = pcbs[j+1];
pcbs[j+1] = tmp;
}
}
}
double T() //平均周转时间
{
double value = 0.0;
for(int i=0;i<nSum;i++)
value+=pcbs[i].T();
return (double)(value/nSum);
}
double Ti() //平均带权周转时间
{
double value = 0.0;
for(int i=0;i<nSum;i++)
value+=pcbs[i].Ti();
return (double)(value/nSum);
}
int New2Ready(int tmClick) //将新进程状态转换为就绪状态
{
int check = 0;
for(int i=0;i<nSum;i++)
{
if(pcbs[i].nStatus == PCB::kNew && pcbs[i].tmArrive == tmClick)
{
if(queRun<0 && queRead<0)
{
queRun = i;
pcbs[i].nStatus = PCB::kRun;
}
else if(queRead<0)
{
queRead = i;
pcbs[i].nStatus = PCB::kReady;
}
else
{
int tmp = queRead;
while(pcbs[tmp].nPointer!=-1)
tmp = pcbs[tmp].nPointer;
pcbs[tmp].nPointer = i;
pcbs[i].nStatus = PCB::kReady;
}
check++;
}
}
return check;
}
public:
friend istream&operator>>(istream &stream,Kernel &k)
{
stream>>k.nSum>>k.nAlgID;
for(int i=0;i<k.nSum;i++)
stream>>k.pcbs[i];
return stream;
}
friend ostream &operator<<(ostream &stream,Kernel &k)
{
stream<<k.nSum<<'\t'<<k.nAlgID<<endl;
for(int i=0;i<k.nSum;i++)
stream<<k.pcbs[i];
return stream;
}
};
int Kernel::IsFinish()
{
for(int i=0;i<sizeof(pcbs)/sizeof(pcbs[0]);i++)
if(!pcbs[i].IsFinish())
return 0;
return 1;
}
void Kernel::Process()
{
PCB pcb;
cout<<"Format:name tmCPU priority"<<endl;
cin>>pcb.name>>pcb.tmCPU>>pcb.priority;
pcb.nStatus = PCB::kNew; //新进程标示
pcb.tmArrive = tmClick;
Create(pcb);
}
void Kernel::Run()
{
int ch;
while((!IsFinish())&&((ch = waitakey())!= KEY_EXIT))
{
if(queRun>=0)
{
pcbs[queRun].Run();//运行一个时间段
if(pcbs[queRun].IsFinish())
{
Terminate(queRun);
Schedule();
}
else if(nAlgID==kRR)
Schedule();
}
int bNew = New2Ready(tmClick);//有新进程进入就绪队列？
if(bNew&&bGrab)
Schedule();
DisplayAlg();
tmClick++;
}
Display();
}
//------------------------------------------------------------------------
MenuDef menu;
Kernel kernel;
//--------------------call-back functions for menu------------------------
void input ()
{
clearscr();
kernel.SetNull();
kernel.Input();
}
void process()
{
clearscr();
kernel.Process();
}
void display()
{
clearscr();
kernel.Display();
}
void setalg1()
{
kernel.SetAlgorithm(Kernel::kFCFS);
}
void setalg2()
{
kernel.SetAlgorithm(Kernel::kPriority);
}
void setalg3()
{
kernel.SetAlgorithm(Kernel::kRR);
}
void run()
{
clearscr();
kernel.Run();
}
void load()
{
char fname[128];
cout<<"\nLoad From file:";
cin>>fname;
ifstream inFile;
inFile.open(fname);
kernel.SetNull();
inFile>>kernel;
}
void save()
{
char fname[128];
cout<<"\nSave to file:";
cin>>fname;
ofstream outFile;
outFile.open(fname);
outFile<<kernel;
}
void main()
{
menu.add('1',"Input from keyboard", input);
menu.add('2',"Input proces", process);
menu.add('3',"Set Algorithm 1: FCFS", setalg1);
menu.add('4',"Set Algorithm 2: Priority", setalg2);
menu.add('5',"Set Algorithm 3: RR", setalg3);
menu.add('6',"Display", display);
menu.add('7',"Run", run);
menu.add('8',"load from file", load);
menu.add('9',"save to file", save);
menu.run();
}
⌨️ 快捷键说明
复制代码
Ctrl + C
搜索代码
Ctrl + F
全屏模式
F11
切换主题
Ctrl + Shift + D
显示快捷键
?
增大字号
Ctrl + =
减小字号
Ctrl + -