schedule.cpp

计算机操作系统中的重要实验

// Schedule.cpp : Defines the entry point for the console application.
//

#include "stdafx.h"
#include "Schedule.h"
#include <mmsystem.h>
#include <conio.h>
#include <time.h>
#include <list>
#include <queue>
#include <vector>
#include <iomanip>
#include <algorithm>

#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<PCB>				PCBQUEUE;			//进程控制块队列
typedef list<PCB>				PCBPQUEUE;			//进程控制块优先级队列
typedef vector<INSTRUCTION>		INSTRUCTIONSET;		//指令集合
typedef list<STATINFO_PROGLEN>	STATINFOL_PROGLEN;	//统计信息链表:程序长度
typedef list<STATINFO_PRIORITY>	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<<endl;
	cout<<"                  进程调度算法演示及其性能测试系统"<<endl<<endl;
	cout<<"                    1-----------------先来先服务"<<endl;
	cout<<"                    2-----------------短进程优先"<<endl;
	cout<<"                    3-----------------抢占式高优先权"<<endl;
	cout<<"                    4-----------------时间片轮转"<<endl;
	cout<<"                    5-----------------关于作者"<<endl;
	cout<<"                    6-----------------退出系统"<<endl;
	cout<<"请选择:";

	SetConsoleTextAttribute(g_hStdOut,CLR_IN);

Input:
	ucSelection=getch();
	if(ucSelection<'1' || ucSelection>'6')
	{
		if(ucSelection==27)
		{
			cout<<endl<<endl;
			goto Exit;
		}

		CoolBeep(CB_ERROR);
		goto Input;
	}

	putchar(ucSelection);
	if(getch()==8)
	{
		COORD dwCursorPostion;
		CONSOLE_SCREEN_BUFFER_INFO *lpConsoleScreenBufferInfo=new CONSOLE_SCREEN_BUFFER_INFO;
		
		GetConsoleScreenBufferInfo(g_hStdOut,lpConsoleScreenBufferInfo);

		dwCursorPostion.X=lpConsoleScreenBufferInfo->dwCursorPosition.X-1;
		dwCursorPostion.Y=lpConsoleScreenBufferInfo->dwCursorPosition.Y;
		SetConsoleCursorPosition(g_hStdOut,dwCursorPostion);
		FillConsoleOutputCharacter(g_hStdOut,' ',1,dwCursorPostion,0);

		goto Input;
	}

	cout<<endl<<endl;
	
	switch(ucSelection)
	{
	case '1':
	case '2':
	case '3':
	case '4':
		g_ScheduleAlgorithm=(SCHEDULEALGORITHM)(ucSelection-'1'+FCFS);
		Reset(g_ScheduleAlgorithm);
		CreateThread(0,0,GetRandProc,0,0,0);
		Schedule();
		break;

	case '5':
		AboutMe();
		break;

	case '6':
Exit:
		Exit();
		break;
	}

	SetConsoleTextAttribute(g_hStdOut,CLR_NORMALOUT);

	CoolBeep(CB_OK);
	PressAnyKey();

	goto Select;
	
	return nRetCode;
}

//产生随机随机进程并插入就绪队列
DWORD WINAPI GetRandProc(LPVOID lpParam)
{
	PROCPRIORITY procPriority;
	int nProgLen;
	PCB pcb;
	UINT uDelay;
	int i;
	INSTRUCTION instruction;
	PROGRAM program;

ContinueGet:

	program.instructionSet.clear();

	nProgLen=RANDDF*(g_nMaxRunTime-1)+1;
	procPriority=(PROCPRIORITY)((int)(RANDDF*(Low-RealTime))+RealTime);

	pcb.infoProcSch.procPriority=procPriority;
	pcb.infoStat.nRequestTime=GetTickCount();
	pcb.infoStat.nGetCPUTime=0;

	//产生随机程序
	program.nIP=0;
	GetLocalTime(&program.timeSystem);
	program.instructionSet.reserve(nProgLen);
	pcb.idProc.nInID=g_nCurProcID;
	program.nProgLen=nProgLen;
	for(i=0;i<nProgLen;i++)
	{
		instruction=rand();
		program.instructionSet.push_back(instruction);
	}

	pcb.program=program;

	EnterCriticalSection(&g_CriticalSection);

	SetConsoleTextAttribute(g_hStdOut,CLR_SECCRITICALRESULT);
	switch(g_ScheduleAlgorithm)
	{
	case FCFS:
		cout<<endl<<"进程"<<setw(2)<<g_nCurProcID<<"请求运行,其请求时间为";
		SetConsoleTextAttribute(g_hStdOut,CLR_NORMALOUT);
		cout<<setw(2)<<program.timeSystem.wMinute<<"分"
			<<setw(2)<<program.timeSystem.wSecond<<"秒"
			<<setw(3)<<program.timeSystem.wMilliseconds<<"微秒"<<endl;
		break;

	case SPF:
		cout<<endl<<"进程"<<setw(2)<<g_nCurProcID<<"请求运行,其长度为";
		SetConsoleTextAttribute(g_hStdOut,CLR_NORMALOUT);
		cout<<program.nProgLen<<endl;
		break;

	case FPF_Reaved:
		cout<<endl<<"进程"<<setw(2)<<g_nCurProcID<<"请求运行,其优先级为";
		SetConsoleTextAttribute(g_hStdOut,CLR_NORMALOUT);
		PrintPriority(procPriority);
		cout<<endl;
		break;

	case TimePiece:
		cout<<endl<<"进程"<<setw(2)<<g_nCurProcID<<"请求运行,其长度为";
		SetConsoleTextAttribute(g_hStdOut,CLR_NORMALOUT);
		cout<<program.nProgLen<<endl;
		break;
	}

	LeaveCriticalSection(&g_CriticalSection);

	switch(g_ScheduleAlgorithm)
	{
	case FCFS:
		g_pcbReadyQueue.push(pcb);
		break;

	case SPF:
		EnterCriticalSection(&g_CriticalSection);

		SortInsProgLenQ(g_pcbReadyPriorityQueue,pcb);

		LeaveCriticalSection(&g_CriticalSection);
		break;

	case FPF_Reaved:
		EnterCriticalSection(&g_CriticalSection);

		if(g_bProgIsRun)
		{
			if(pcb.infoProcSch.procPriority > 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;