// 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;