www.pudn.com > 200652619472986557.rar > Schedule.cpp

// Schedule.cpp : Defines the entry point for the console application. 
// 
 
#include "stdafx.h" 
#include "Schedule.h" 
#include  
#include  
#include  
#include  
#include  
#include  
#include  
#include  
 
#ifdef _DEBUG 
#define new DEBUG_NEW 
#undef THIS_FILE 
static char THIS_FILE[] = __FILE__; 
#endif 
 
///////////////////////////////////////////////////////////////////////////// 
// The one and only application object 
 
using namespace std; 
 
//颜色 
#define CLR_GREEN	10	//绿 
#define CLR_RED		12	//红 
#define CLR_SECRED	13	//次红 
#define	CLR_YELLOW	14	//黄 
 
#define CLR_IN					CLR_RED		//输入颜色 
#define CLR_NORMALOUT			CLR_GREEN	//一般输出颜色 
#define CLR_CRITICALOUT			CLR_RED		//重要输出颜色 
#define CLR_NORMALRESULT		CLR_YELLOW	//一般结果输出颜色 
#define CLR_CRITICALRESULT		CLR_RED		//重要结果输出 
#define CLR_SECCRITICALRESULT	CLR_SECRED  //次重要结果输出 
 
//声音类型 
#define CB_ERROR	0	//错误 
#define CB_OK		1	//正确 
 
#define RANDDF	rand()*1.0/RAND_MAX		//产生0~1之间的随机小数 
 
struct PCB; 
struct PCBPriorityCompare; 
struct PCBProgLenCompare; 
struct STATINFO_PROGLEN; 
struct STATINFO_PRIORITY; 
 
typedef int						INSTRUCTION;		//指令 
typedef queue				PCBQUEUE;			//进程控制块队列 
typedef list				PCBPQUEUE;			//进程控制块优先级队列 
typedef vector		INSTRUCTIONSET;		//指令集合 
typedef list	STATINFOL_PROGLEN;	//统计信息链表:程序长度 
typedef list	STATINFOL_PRIORITY;	//统计信息链表:进程优先级 
 
//进程状态 
enum PROCSTATUS 
{ 
	Ready,	//就绪 
	Block,	//阻塞 
	Run,	//运行 
}; 
 
//进程优先级 
enum PROCPRIORITY 
{ 
	Low,			//低 
	LowStandard,	//低于标准 
	Standard,		//标准 
	HighStandard,	//高于标准 
	High,			//高 
	RealTime,		//实时 
}; 
 
//调度算法 
enum SCHEDULEALGORITHM 
{ 
	FCFS,			//先来先服务 
	SPF,			//短进程优先	 
	FPF_Reaved,		//抢占式高优先级 
	TimePiece,		//时间片轮转 
}; 
 
//进程标识符 
struct PROCID 
{ 
	int		nInID;	//内部标识符 
	int		nOutID;	//外部标识符 
}; 
 
//处理机状态 
struct PROCESSORSTATUS 
{ 
	int		nIP;	//指令指针 
}; 
 
//进程调度信息 
struct PROCSCHINFO 
{ 
	PROCSTATUS		statusProc;		//进程状态 
	PROCPRIORITY	procPriority;	//进程优先级 
}; 
 
//进程控制信息 
struct PROCCONINFO 
{ 
	PCB		*pNextPCB;	//下一PCB 
}; 
 
//程序 
struct PROGRAM 
{ 
	int				nProgLen;			//程序大小 
	int				nIP;				//指令指针 
	SYSTEMTIME		timeSystem;			//程序请求运行时间 
	INSTRUCTIONSET	instructionSet;		//指令集合 
}; 
 
//统计信息 
struct STATINFO 
{ 
	int	nRequestTime;	//进程请求运行时间 
	int nGetCPUTime;	//系统为之提供服务时间 
}; 
 
//进程控制块 
struct PCB 
{ 
	STATINFO		infoStat;			//统计信息 
	PROCID			idProc;				//进程标识符 
	PROGRAM			program;			//该进程对应的程序 
	PROCESSORSTATUS statusProcessor;	//处理机状态 
	PROCSCHINFO		infoProcSch;		//进程调度信息 
	PROCCONINFO		infoProcCon;		//进程控制信息 
}; 
 
//统计信息:程序长度 
struct STATINFO_PROGLEN 
{ 
	int nProgLen;		//程序长度 
	int nProcID;		//进程ID 
	int nPeriod;		//周转时间 
	int nWeightPeriod;	//带权周转时间 
 
	bool operator < (STATINFO_PROGLEN infoStat) 
	{ 
		return nProgLen < infoStat.nProgLen; 
	} 
}; 
 
//统计信息:进程优先级 
struct STATINFO_PRIORITY 
{ 
	PROCPRIORITY	procPriority;	//进程优先级 
	int				nProcID;		//进程ID 
	int				nPeriod;		//周转时间 
	int				nWeightPeriod;	//带权周转时间 
 
	bool operator < (STATINFO_PRIORITY infoStat) 
	{ 
		return procPriority < infoStat.procPriority; 
	} 
}; 
 
DWORD	WINAPI GetRandProc(LPVOID lpParam);	//产生随机随机进程并插入就绪队列 
void	Schedule_FCFS();					//FCFS调度 
void	Schedule_SPF();						//短作业优先 
void	Schedule_FPF_Reaved();				//高优先权调度 
void	Schedule_TimePiece();				//时间片调度 
 
void	Schedule();						//调度程序 
BOOL	RunProc(PCB *pPcb);				//运行进程 
void	AboutMe();						//关于 
void	Exit();							//退出系统 
void	PressAnyKey();					//按任意键继续 
void	CoolBeep(UINT uiCbSort);		//非常酷的蜂鸣声 
void	AnimatePrint(char* pStr);		//动态显示 
void	Reset(SCHEDULEALGORITHM algo);	//重新设置初值 
void	PrintPriority(PROCPRIORITY p);	//以文字方式打印优先级 
BOOL	CtrlHandler(DWORD dwCtrlType);	//处理控制台事件 
void	Clean();						//事后清理 
 
void	PrintAlgorithm(SCHEDULEALGORITHM algo);								//打印算法 
void	PrintStatInfo_ProgLen(STATINFOL_PROGLEN l,SCHEDULEALGORITHM algo);	//打印统计信息:程序长度 
void	PrintStatInfo_Priority(STATINFOL_PRIORITY l,SCHEDULEALGORITHM algo);//打印统计信息:进程优先级 
 
void	SortInsProgLenQ(PCBPQUEUE& pcbQ,PCB pcb);		//按程序大小入队列 
void	SortInsPriorityQ(PCBPQUEUE& pcbQ,PCB pcb);		//按优先级入队列 
 
int					g_nCloseTime;				//模拟时间 
int					g_nMaxRunTime;				//程序最大运行时间 
int					g_nMaxInterval;				//最大间隔 
int					g_nMaxTimePiece;			//最大时间片 
 
int					g_nCurProcID=0;				//当前进程ID 
PCB					g_CurRunningProc;			//当前正在运行的进程 
int					g_nFinishedTime=0;			//模拟已完成的时间 
BOOL				g_bIsEnd=FALSE;				//结束标志 
BOOL				g_bProgIsRun;				//是否有程序正在运行 
BOOL				g_bIsPrioritierReach=FALSE;	//是否有优先级更高的进程达到 
PCB					g_pcbPrioritier;			//更高优先级的进程 
PCBQUEUE			g_pcbReadyQueue;			//就绪队列 
PCBPQUEUE			g_pcbReadyPriorityQueue;	//就绪优先级队列 
SCHEDULEALGORITHM	g_ScheduleAlgorithm;		//调度算法 
CRITICAL_SECTION	g_CriticalSection;			//临界区 
STATINFOL_PROGLEN	g_listStatInfoProgLen[3];	//统计信息链表:程序长度 
STATINFOL_PRIORITY	g_listStatInfoProcPriority;	//统计信息链表:进程优先级 
 
HANDLE g_hStdOut=GetStdHandle(STD_OUTPUT_HANDLE); 
 
int _tmain(int argc, TCHAR* argv[], TCHAR* envp[]) 
{ 
	int nRetCode = 0; 
 
	// initialize MFC and print and error on failure 
	if (!AfxWinInit(::GetModuleHandle(NULL), NULL, ::GetCommandLine(), 0)) 
	{ 
		// TODO: change error code to suit your needs 
		cerr << _T("Fatal Error: MFC initialization failed") << endl; 
		nRetCode = 1; 
	} 
 
	UCHAR ucSelection;//选择号 
 
	srand(time(0)); 
 
	InitializeCriticalSection(&g_CriticalSection); 
 
	SetConsoleTitle("进程调度算法演示及其性能测试系统");//设置标题 
 
	SetConsoleCtrlHandler((PHANDLER_ROUTINE)CtrlHandler,TRUE); 
	 
Select: 
	SetConsoleTextAttribute(g_hStdOut,CLR_NORMALOUT); 
 
	cout<'6') 
	{ 
		if(ucSelection==27) 
		{ 
			cout<dwCursorPosition.X-1; 
		dwCursorPostion.Y=lpConsoleScreenBufferInfo->dwCursorPosition.Y; 
		SetConsoleCursorPosition(g_hStdOut,dwCursorPostion); 
		FillConsoleOutputCharacter(g_hStdOut,' ',1,dwCursorPostion,0); 
 
		goto Input; 
	} 
 
	cout< g_pcbReadyPriorityQueue.front().infoProcSch.procPriority) 
			{ 
				g_bIsPrioritierReach=TRUE; 
				g_pcbPrioritier=pcb; 
			} 
		} 
		 
		SortInsPriorityQ(g_pcbReadyPriorityQueue,pcb); 
 
		LeaveCriticalSection(&g_CriticalSection); 
		break; 
	 
	case TimePiece: 
		g_pcbReadyPriorityQueue.push_back(pcb); 
		break; 
	} 
 
	uDelay=RANDDF*(g_nMaxInterval-1)+1; 
 
	if((g_nFinishedTime+=uDelay)<=g_nCloseTime) 
	{ 
		g_nCurProcID++; 
		Sleep(uDelay); 
		goto ContinueGet; 
	} 
	else 
		g_bIsEnd=TRUE; 
 
	return 0; 
} 
 
//调度程序 
void Schedule() 
{ 
	switch(g_ScheduleAlgorithm) 
	{ 
	case FCFS: 
		Schedule_FCFS(); 
		break; 
 
	case SPF: 
		Schedule_SPF(); 
		break; 
 
	case FPF_Reaved: 
		Schedule_FPF_Reaved(); 
		break; 
 
	case TimePiece: 
		Schedule_TimePiece(); 
		break; 
	} 
} 
 
//FCFS调度 
void Schedule_FCFS() 
{ 
	PCB pcb; 
	PROGRAM program; 
	int nIP=0; 
 
Schedule: 
 
	if(g_bIsEnd && g_pcbReadyQueue.empty()) 
	{ 
		g_listStatInfoProgLen[FCFS].sort(); 
		PrintStatInfo_ProgLen(g_listStatInfoProgLen[FCFS],FCFS); 
		return; 
	} 
 
	if(g_pcbReadyQueue.empty()) 
		goto Schedule; 
 
	EnterCriticalSection(&g_CriticalSection); 
 
	pcb=g_pcbReadyQueue.front(); 
	g_pcbReadyQueue.pop(); 
 
	LeaveCriticalSection(&g_CriticalSection); 
 
	RunProc(&pcb); 
 
	//添加统计信息 
	STATINFO_PROGLEN infoStat; 
 
	infoStat.nPeriod=GetTickCount()-pcb.infoStat.nRequestTime; 
	infoStat.nProgLen=pcb.program.nProgLen; 
	infoStat.nProcID=pcb.idProc.nInID; 
	infoStat.nWeightPeriod=infoStat.nPeriod/pcb.infoStat.nGetCPUTime; 
	 
	g_listStatInfoProgLen[FCFS].push_back(infoStat); 
 
	goto Schedule; 
} 
 
//短进程优先 
void Schedule_SPF()		 
{ 
	PCB pcb; 
 
Schedule: 
 
	if(g_bIsEnd && g_pcbReadyPriorityQueue.empty()) 
	{ 
		g_listStatInfoProgLen[SPF].sort(); 
		PrintStatInfo_ProgLen(g_listStatInfoProgLen[SPF],SPF); 
		return; 
	} 
 
	if(g_pcbReadyPriorityQueue.empty()) 
		goto Schedule; 
	 
	EnterCriticalSection(&g_CriticalSection); 
 
	pcb=g_pcbReadyPriorityQueue.front(); 
	g_pcbReadyPriorityQueue.pop_front(); 
 
	LeaveCriticalSection(&g_CriticalSection); 
 
	RunProc(&pcb); 
 
	//添加统计信息 
	STATINFO_PROGLEN infoStat; 
 
	infoStat.nPeriod=GetTickCount()-pcb.infoStat.nRequestTime; 
	infoStat.nProgLen=pcb.program.nProgLen; 
	infoStat.nProcID=pcb.idProc.nInID; 
	infoStat.nWeightPeriod=infoStat.nPeriod/pcb.infoStat.nGetCPUTime; 
	 
	g_listStatInfoProgLen[SPF].push_back(infoStat); 
 
	goto Schedule; 
} 
 
//抢占式高优先权调度 
void Schedule_FPF_Reaved() 
{ 
	PCB *pPcb; 
	PCBPQUEUE::iterator p; 
 
Schedule: 
 
	if(g_bIsEnd && g_pcbReadyPriorityQueue.empty()) 
	{ 
		g_listStatInfoProgLen[FPF_Reaved].sort(); 
		PrintStatInfo_ProgLen(g_listStatInfoProgLen[FPF_Reaved],FPF_Reaved); 
		return; 
	} 
 
	if(g_pcbReadyPriorityQueue.empty()) 
		goto Schedule; 
	 
	EnterCriticalSection(&g_CriticalSection); 
 
	p=g_pcbReadyPriorityQueue.begin(); 
	pPcb=&g_pcbReadyPriorityQueue.front(); 
 
	g_bProgIsRun=TRUE; 
 
	LeaveCriticalSection(&g_CriticalSection); 
 
	if(RunProc(pPcb)) 
	{ 
		//添加统计信息 
		STATINFO_PROGLEN infoStat; 
		 
		infoStat.nPeriod=GetTickCount()-pPcb->infoStat.nRequestTime; 
		infoStat.nProgLen=pPcb->program.nProgLen; 
		infoStat.nProcID=pPcb->idProc.nInID; 
		infoStat.nWeightPeriod=infoStat.nPeriod/pPcb->infoStat.nGetCPUTime; 
		 
		g_listStatInfoProgLen[FPF_Reaved].push_back(infoStat); 
 
		EnterCriticalSection(&g_CriticalSection); 
		 
		g_pcbReadyPriorityQueue.erase(p); 
		 
		LeaveCriticalSection(&g_CriticalSection);		 
	} 
 
	g_bProgIsRun=FALSE; 
 
	goto Schedule; 
} 
 
//时间片调度 
void Schedule_TimePiece() 
{ 
	PCB pcb; 
 
Schedule: 
 
	if(g_bIsEnd && g_pcbReadyPriorityQueue.empty()) 
	{ 
		g_listStatInfoProcPriority.sort(); 
		PrintStatInfo_Priority(g_listStatInfoProcPriority,TimePiece); 
		return; 
	} 
 
	if(g_pcbReadyPriorityQueue.empty()) 
		goto Schedule; 
 
	EnterCriticalSection(&g_CriticalSection); 
 
	pcb=g_pcbReadyPriorityQueue.front(); 
	g_pcbReadyPriorityQueue.pop_front(); 
 
	LeaveCriticalSection(&g_CriticalSection); 
 
	if(!RunProc(&pcb)) 
	{ 
		EnterCriticalSection(&g_CriticalSection); 
 
		g_pcbReadyPriorityQueue.push_back(pcb); 
		 
		LeaveCriticalSection(&g_CriticalSection); 
	} 
	else 
	{ 
		//添加统计信息 
		STATINFO_PRIORITY infoStat; 
		 
		infoStat.nPeriod=GetTickCount()-pcb.infoStat.nRequestTime; 
		infoStat.procPriority=pcb.infoProcSch.procPriority; 
		infoStat.nProcID=pcb.idProc.nInID; 
		infoStat.nWeightPeriod=infoStat.nPeriod/pcb.infoStat.nGetCPUTime; 
		 
		g_listStatInfoProcPriority.push_back(infoStat); 
	} 
 
	goto Schedule; 
} 
 
//运行程序 
BOOL RunProc(PCB *pPcb) 
{ 
	int i; 
	PROGRAM *pProgram=&pPcb->program; 
	int nProcID=pPcb->idProc.nInID; 
	int nSize=pProgram->instructionSet.size(); 
	int nTimePieceCnt=0; 
	int nStartTime=GetTickCount(); 
 
//	cout.unsetf(cout.dec); 
//	cout.setf(cout.hex); 
 
	switch(g_ScheduleAlgorithm) 
	{ 
	case FCFS: 
		EnterCriticalSection(&g_CriticalSection); 
 
		SetConsoleTextAttribute(g_hStdOut,CLR_CRITICALRESULT); 
		cout<timeSystem.wMinute<<"分" 
			<timeSystem.wSecond<<"秒" 
			<timeSystem.wMilliseconds<<"微秒"<instructionSet[i]); 
			 
			LeaveCriticalSection(&g_CriticalSection); 
		} 
		pPcb->infoStat.nGetCPUTime=GetTickCount()-nStartTime; 
		if(!pPcb->infoStat.nGetCPUTime) 
			pPcb->infoStat.nGetCPUTime+=2; 
 
		EnterCriticalSection(&g_CriticalSection); 
 
		SetConsoleTextAttribute(g_hStdOut,CLR_CRITICALRESULT); 
		cout<<"进程"<nProgLen<instructionSet[i]); 
 
			LeaveCriticalSection(&g_CriticalSection); 
		} 
		pPcb->infoStat.nGetCPUTime=GetTickCount()-nStartTime; 
		if(!pPcb->infoStat.nGetCPUTime) 
			pPcb->infoStat.nGetCPUTime=2; 
 
		EnterCriticalSection(&g_CriticalSection); 
 
		SetConsoleTextAttribute(g_hStdOut,CLR_CRITICALRESULT); 
		cout<<"进程"<nIP) 
		{ 
			cout<infoProcSch.procPriority); 
			cout<infoProcSch.procPriority); 
			cout<nIP;iinfoProcSch.procPriority); 
				SetConsoleTextAttribute(g_hStdOut,CLR_CRITICALRESULT); 
				cout<<")被中断执行"<nIP=i; 
 
				pPcb->infoStat.nGetCPUTime+=GetTickCount()-nStartTime; 
 
				return FALSE; 
			} 
			EnterCriticalSection(&g_CriticalSection); 
 
			SetConsoleTextAttribute(g_hStdOut,CLR_NORMALRESULT); 
 
			printf("进程%2d正在运行指令%4X...",nProcID,pProgram->instructionSet[i]); 
			cout<<"(优先级为"; 
			SetConsoleTextAttribute(g_hStdOut,CLR_NORMALOUT); 
			PrintPriority(pPcb->infoProcSch.procPriority); 
			cout<<")"<infoStat.nGetCPUTime+=GetTickCount()-nStartTime; 
		if(!pPcb->infoStat.nGetCPUTime) 
			pPcb->infoStat.nGetCPUTime=2; 
 
		EnterCriticalSection(&g_CriticalSection); 
 
		SetConsoleTextAttribute(g_hStdOut,CLR_CRITICALRESULT); 
		cout<<"进程"<nIP) 
		{ 
			cout<program.nProgLen<program.nProgLen<nIP;ig_nMaxTimePiece) 
			{ 
				EnterCriticalSection(&g_CriticalSection); 
 
				SetConsoleTextAttribute(g_hStdOut,CLR_CRITICALRESULT); 
				cout<<"进程"<nIP=i; 
 
				pPcb->infoStat.nGetCPUTime+=GetTickCount()-nStartTime; 
 
				return FALSE; 
			} 
			EnterCriticalSection(&g_CriticalSection); 
			 
			SetConsoleTextAttribute(g_hStdOut,CLR_NORMALRESULT); 
 
			printf("进程%2d正在运行指令%4X...\n",nProcID,pProgram->instructionSet[i]); 
			 
			LeaveCriticalSection(&g_CriticalSection); 
 
			nTimePieceCnt++; 
		} 
		pPcb->infoStat.nGetCPUTime+=GetTickCount()-nStartTime; 
		if(!pPcb->infoStat.nGetCPUTime) 
			pPcb->infoStat.nGetCPUTime=2; 
 
		EnterCriticalSection(&g_CriticalSection); 
 
		SetConsoleTextAttribute(g_hStdOut,CLR_CRITICALRESULT); 
		cout<<"进程"< (*p).infoProcSch.procPriority) 
		{ 
			pcbQ.insert(p,pcb); 
 
			return; 
		} 
	} 
 
	pcbQ.push_back(pcb); 
} 
 
//以文字方式打印优先级 
void PrintPriority(PROCPRIORITY p) 
{ 
	switch(p) 
	{ 
	case Low: 
		cout<<"\"低\""; 
		break; 
 
	case LowStandard: 
		cout<<"\"低于标准\""; 
		break; 
 
	case Standard: 
		cout<<"\"标准\""; 
		break; 
 
	case HighStandard: 
		cout<<"\"高于标准\""; 
		break; 
 
	case High: 
		cout<<"\"高\""; 
		break; 
 
	case RealTime: 
		cout<<"\"实时\""; 
		break; 
	} 
} 
 
//打印统计信息:程序长度 
void PrintStatInfo_ProgLen(STATINFOL_PROGLEN l,SCHEDULEALGORITHM algo) 
{ 
	int nPeriod=0; 
	int nWeightPeriod=0; 
	int nSize=l.size(); 
 
	SetConsoleTextAttribute(g_hStdOut,CLR_NORMALRESULT); 
	cout<