操作系统进程调度算法模拟__MFC实现
#include "windows.h"
#include "windowsx.h"
#include "tchar.h"
#include "strsafe.h"
#include "resource.h"
#pragma warning(disable:4312)
#pragma warning(disable:4244)
#define EDITLEN 20
#define RR 2 // 时间片
#define chHANDLE_DLGMSG(hWnd, message, fn) \
case (message): return (SetDlgMsgResult(hWnd, uMsg, \
HANDLE_##message((hWnd), (wParam), (lParam), (fn))))
struct ProcInfo {
int procID; // 进程ID
float arriveT; // 达到时间
float serverT; // 服务时间
float remainT; // 剩余运行时间
float lastrunT; // 上次运行时间
float runT; // 运行时间总和
float priority; // 优先级,高响应比优先调度算法时初始为1,其他算法未用到,初始为0
struct ProcInfo *next; // 下一结点
} *startProc,*endProc;
HWND hWnd;
/*
检查6个进程的到达时间和服务时间是否已经全部输入
已经全部输入返回TRUE,否则返回FALSE
*/
bool CheckEdits()
{
wchar_t str[EDITLEN];
for (int i=IDC_A1;i<=IDC_F1;i+=5) {
GetDlgItemText(hWnd,i,str,EDITLEN);
if (lstrcmp(str,_T("\0")) == 0)
return false;
GetDlgItemText(hWnd,i+1,str,EDITLEN);
if (lstrcmp(str,_T("\0")) == 0 )
return false;
}
return true;
}
/*
计算平均周转时间和平均带权周转时间,并显示
*/
void ShowEdits()
{
float zzsj=0,pjzz=0;
wchar_t str[10];
for (int i=IDC_A4;i<=IDC_F4;i+=5) {
GetDlgItemText(hWnd,i,str,10);
zzsj += _wtof(str);
GetDlgItemText(hWnd,i+1,str,10);
pjzz += _wtof(str);
}
StringCchPrintf(str,10,_T("%f"),zzsj/6);
SetDlgItemText(hWnd,IDC_TIME1,str);
StringCchPrintf(str,10,_T("%f"),pjzz/6);
SetDlgItemText(hWnd,IDC_TIME2,str); }
/*
清除所有编辑框的内容
*/
void ClearEdits()
{
for (int i=IDC_A1;inext = node;
endProc = node;
if (startProc->next == NULL) {
startProc->next = endProc;
}
}
}
/*
移除链表头结点
*/
void RemoveNode()
{
if (startProc != NULL) {
float finishT;
wchar_t str[10];
ProcInfo *tmp = startProc;
if (startProc->next != NULL) {
startProc = startProc->next;
startProc->lastrunT = tmp->lastrunT+tmp->remainT;
} else {
startProc = endProc = NULL;
}
finishT = tmp->lastrunT+tmp->remainT;
StringCchPrintf(str,10,_T("%f"),finishT);
SetDlgItemText(hWnd,IDC_A3+5*tmp->procID,str);
StringCchPrintf(str,10,_T("%f"),finishT-tmp->arriveT);
SetDlgItemText(hWnd,IDC_A4+5*tmp->procID,str);
StringCchPrintf(str,10,_T("%f"),(finishT-tmp->arriveT)/(float)tmp->serverT);
SetDlgItemText(hWnd,IDC_A5+5*tmp->procID,str);
delete tmp;
}
}
/*
当链表头结点被抢占或时间片到时,将头结点移到尾结点
参数:moreT为头结点运行到被抢占或时间片到的时间间隔
*/
void ChangeNode(int moreT) {
if (startProc != NULL) {
if (startProc->next != NULL) {
ProcInfo *tmp = startProc;
startProc = startProc->next;
tmp->next = NULL;
tmp->runT += moreT;
tmp->remainT -= moreT;
endProc->next = tmp;
endProc = tmp;
startProc->lastrunT = tmp->lastrunT+moreT;
} else {
startProc->lastrunT += moreT;
startProc->runT += moreT;
startProc->remainT -= moreT;
}
}
}
/*
先到先服务调度算法
*/
void AlgoFCFS(int *arrive,int *server) {
int procNum = 6;
int index = 0;
ProcInfo *node;
startProc = endProc = NULL;
while (procNum) {
if (startProc != NULL) {
// 直接将每个进程插入链表,链表中每个结点按顺序运行
while (index<6) {
node = new ProcInfo;
node->procID = index;
node->arriveT = arrive[index];
node->serverT = server[index];
node->remainT = server[index];
node->lastrunT = arrive[index];
node->runT = 0;
node->priority = 0;
node->next = NULL;
index++;
InsertNode(node);
}
RemoveNode();
procNum--;
} else {
if (index<6) {
node = new ProcInfo;
node->procID = index;
node->arriveT = arrive[index];
node->serverT = server[index];
node->remainT = server[index];
node->lastrunT = arrive[index];
node->runT = 0;
node->priority = 0;
node->next = NULL;
index++;
InsertNode(node);
} else
break;
}
}
}
/*
短进程优先调度算法
*/
void AlgoSJF(int *arrive,int *server) {
int procNum = 6;
int index = 0;
float minremainT;
ProcInfo *node,*tmp,*seize,*mid,*tmp2;
startProc = endProc = NULL;
while (procNum) {
if (startProc != NULL) {
tmp = seize = startProc;
minremainT = startProc->remainT;
// 查看链表中是否有剩余运行时间比头结点小的进程,如果有存入最小运行
时间
while ((tmp=tmp->next) != NULL) {
if (tmp->remainT < minremainT) {
minremainT = tmp->remainT;
seize = tmp;
} else if (minremainT < startProc->remainT && tmp->remainT ==
minremainT) {
if (tmp->arriveT < seize->arriveT)
seize = tmp;
}
}
while (index<6) {
// 查看在头结点被短进程抢占,或运行结束时,是否有新进程到达
if (arrive[index] < (startProc->lastrunT+minremainT)) {
node = new ProcInfo;
node->procID = index;
node->arriveT = arrive[index];
node->serverT = server[index];
node->remainT = server[index];
node->lastrunT = arrive[index];
node->runT = 0;
node->priority = 0;
node->next = NULL;
index++;
InsertNode(node);
// 当有新进程到达时,根据剩余运行时间插入到链表中
mid = NULL;
tmp = startProc;
while (tmp->next != endProc) {
if (tmp->next->remainT > endProc->remainT) {
mid = tmp;
break;
}
tmp = tmp->next;
}
if (mid != NULL) {
tmp = startProc->next;
while (tmp->next != NULL) {
if (tmp->next == endProc) {
tmp2 = endProc;
tmp->next = NULL;
endProc = tmp;
tmp2->next = mid->next;
mid->next = tmp2;
break;
}
tmp = tmp->next;
}
}
// 查看刚插入的结点的剩余运行时间是否小于最小剩余时间
if (node->remainT < minremainT) {
minremainT = node->remainT;
seize = node;
} else if (minremainT < startProc->remainT && node->remainT ==
minremainT) {
if (node->arriveT < seize->arriveT)
seize = node;
}
} else
break;
}
// 当seize仍为头结点时,表示没有比头结点更小的剩余运行时间,故移除头结点
if (seize == startProc) {
RemoveNode();
procNum--;
} else { // 否则,将抢占进程移到头结点之后,并更改结点
tmp = startProc;
while (tmp != NULL) {
if (tmp->next == seize) {
tmp->next = seize->next;
if (seize == endProc)
endProc = tmp;
break;
}
tmp = tmp->next;
}
seize->next = startProc->next;
if (startProc == endProc)
endProc = seize;
startProc->next = seize;
ChangeNode(minremainT);
}
} else {
if (index<6) {
node = new ProcInfo;
node->procID = index;
node->arriveT = arrive[index];
node->serverT = server[index];
node->remainT = server[index];
node->lastrunT = arrive[index];
node->runT = 0;
node->priority = 0;
node->next = NULL;
index++;
InsertNode(node);
} else
break;
}
}
}
/*
高响应比优先调度算法
*/
void AlgoHRP(int *arrive,int *server) {
int procNum=6;
int index=0;
float waitT,minwaitT,waitT2,lastwaitT;
ProcInfo *node,*tmp,*seize,*second;
float prio=0,stmp;
startProc = endProc = NULL;
while(procNum) {
if (startProc != NULL) {
tmp = seize = second = startProc;
minwaitT = startProc->remainT;
// 计算在头结点剩余时间内,是否有进程的优先级超过头结点,如果有,取最先超过头结点的进程为抢占进程
while((tmp=tmp->next) != NULL) {
waitT = (startProc->priority-1)*tmp->serverT+0.1; // 计算超过头结点的最小等待时间
lastwaitT = waitT-(startProc->lastrunT-tmp->arriveT-tmp->runT); // 计算头结点运行期间还需要等待的时间
if (lastwaitT < minwaitT) { // 当小于最小时间时,更新最小时间,优先级,
和抢占进程
minwaitT = lastwaitT;
tmp->priority = waitT/tmp->serverT+1;
seize = tmp;
} else if (minwaitT < startProc->remainT && lastwaitT == minwaitT) { // 当等于最小时间时,服务时间越小,优先级越高
if (tmp->serverT < seize->serverT) {
tmp->priority = waitT/tmp->serverT+1;
seize = tmp;
} else if (tmp->serverT == seize->serverT) { // 当等于最小时间,服务时间也相同时,先到达者优先
if (tmp->arriveT < seize->arriveT) {
tmp->priority = waitT/tmp->serverT+1;
seize = tmp;
}
}
} else {
if (minwaitT == startProc->remainT) { // 当头结点剩余时间内,没有进程的优先级抢占时,计算优先级第二高的进程
waitT2 =
startProc->lastrunT-tmp->arriveT-tmp->runT+startProc->remainT;
stmp = waitT2/tmp->serverT+1;
if (stmp>prio) {
tmp->priority = prio = stmp;
second = tmp;
}
}
}
}
while (index<6) { // 查看在头结点的剩余时间内,或被抢占的时间间隔内,是否有进程到达
if (arrive[index] < (startProc->lastrunT+minwaitT)) {
node = new ProcInfo;
node->procID = index;
node->arriveT = arrive[index];
node->serverT = server[index];
node->remainT = server[index];
node->lastrunT = arrive[index];
node->runT = 0;
node->priority = 1;
node->next = NULL;
index++;
InsertNode(node);
// 查看在该进程到达,到头结点运行结束,或被抢占前,优先级是否能超过头结点
waitT = (startProc->priority-1)*node->serverT+0.1;
lastwaitT = waitT+(node->arriveT-startProc->lastrunT);
if (lastwaitT < minwaitT) {
minwaitT = lastwaitT;
node->priority = waitT/node->serverT+1;
seize = node;
} else if (minwaitT < startProc->remainT && lastwaitT == minwaitT) {
if (node->serverT < seize->serverT) {
node->priority = waitT/node->serverT+1;
seize = node;
} else if (node->serverT == seize->serverT) {
if (node->arriveT < seize->arriveT) {
node->priority = waitT/node->serverT+1;
seize = node;
}
}
} else {
if (minwaitT == startProc->remainT) {
waitT2 =
startProc->remainT-(node->arriveT-startProc->lastrunT);
stmp = waitT2/node->serverT+1;
if (stmp > prio) {
node->priority = prio = stmp;
second = node;
}
}
}
} else
break;
}
// 当计算的抢占结点仍为头结点时,表示没有抢占的进程,故将第二高优先级的进程移到头结点之后,并移除头结点
if (seize == startProc) {
if (second != startProc) {
tmp = startProc;
while (tmp != NULL) {
if (tmp->next == second) {
tmp->next = second->next;
if (second == endProc)
endProc = tmp;
break;
}
tmp = tmp->next;
}
second->next = startProc->next;
if (startProc == endProc)
endProc = second;
startProc->next = second;
}
RemoveNode();
procNum--;
} else { // 当计算的抢占结点不为头结点时,表示存在能够抢占的进程,故将该抢占进程移到头结点之后,并更改结点
tmp = startProc;
while (tmp != NULL) {
if (tmp->next == seize) {
tmp->next = seize->next;
if (seize == endProc)
endProc = tmp;
break;
}
tmp = tmp->next;
}
seize->next = startProc->next;
if (startProc == endProc)
endProc = seize;
startProc->next = seize;
ChangeNode(minwaitT);
}
} else {
if (index<6) {
node = new ProcInfo;
node->procID = index;
node->arriveT = arrive[index];
node->serverT = server[index];
node->remainT = server[index];
node->lastrunT = arrive[index];
node->runT = 0;
node->priority = 1;
node->next = NULL;
index++;
InsertNode(node);
} else
break;
}
}
}
/*
时间片轮转调度算法
*/
void AlgoRR(int *arrive,int *server) {
int procNum=6; // 进程数
int index=0;
ProcInfo *node;
startProc = endProc = NULL;
while(procNum) {
if (startProc != NULL) { // 队列不为空时
while (index<6) {
// 当头结点运行到时间片到,或运行到自行结束,这段时间间隔内有进程到达时插入链表
if ((arrive[index] <=
(startProc->lastrunT+((startProc->remainT<=RR)?startProc->remainT:RR)))) {
node = new ProcInfo;
node->procID = index;
node->arriveT = arrive[index];
node->serverT = server[index];
node->remainT = server[index];
node->lastrunT = arrive[index];
node->runT = 0;
node->priority = 0;
node->next = NULL;
index++;
InsertNode(node);
} else
break;
}
// 当头结点进程的剩余时间小于等于时间片时,移除头结点,否则将结点移到链表末尾,第二结点开始运行
if (startProc->remainT<=RR) {
RemoveNode();
procNum--;
} else /*if(start->remainT>RR)*/{
ChangeNode(RR);
}
} else { // 队列为空时
if (index < 6) {
node = new ProcInfo;
node->procID = index;
node->arriveT = arrive[index];
node->serverT = server[index];
node->remainT = server[index];
node->lastrunT = arrive[index];
node->runT = 0;
node->priority = 0;
node->next = NULL;
index++;
InsertNode(node);
} else
break;
}
}
}
BOOL OnInitDialog(HWND hwnd, HWND hwndFocus, LPARAM lParam)
{
hWnd = hwnd;
SendMessage(hwnd,WM_SETICON,ICON_BIG,(LPARAM)LoadIcon((HINSTANCE)GetW
indowLongPtr(hwnd,GWLP_HINSTANCE),
MAKEINTRESOURCE(IDI_MAIN)));
SendMessage(hwnd,WM_SETICON,ICON_SMALL,(LPARAM)LoadIcon((HINSTANCE)
GetWindowLongPtr(hwnd,GWLP_HINSTANCE),
MAKEINTRESOURCE(IDI_MAIN)));
return TRUE;
}
void OnCommand(HWND hwnd, int id, HWND hwndCtl, UINT codeNotify)
{
unsigned int value1,value2;
wchar_t str[EDITLEN];
wchar_t str2[EDITLEN];
switch(id) {
case IDCANCEL:
EndDialog(hwnd,id);
break;
case IDOK:
ClearEdits();
break;
case IDC_FCFS:
case IDC_SJF:
case IDC_HRP:
case IDC_RR:
{
if (!CheckEdits()) {
MessageBox(hWnd,_T("将信息填写完整"),_T("提示"),MB_OK);
return;
}
int arrive[6];
int server[6];
int n=0;
for (int i=IDC_A1; i<=IDC_F1; i+=5,n++) {
arrive[n] = GetDlgItemInt(hWnd,i,NULL,TRUE);
server[n] = GetDlgItemInt(hWnd,i+1,NULL,TRUE);
}
if (id == IDC_FCFS)
AlgoFCFS(arrive,server);
else if (id == IDC_SJF)
AlgoSJF(arrive,server);
else if (id == IDC_HRP)
AlgoHRP(arrive,server);
else if (id == IDC_RR)
AlgoRR(arrive,server);
ShowEdits();
}
break;
case IDC_B1:
if (codeNotify == EN_KILLFOCUS) {
GetDlgItemText(hWnd,IDC_A1,str,EDITLEN);
GetDlgItemText(hWnd,IDC_B1,str2,EDITLEN);
if ( lstrcmp(str,_T("\0"))!=0 && lstrcmp(str2,_T("\0"))!=0 ) {
value1 = GetDlgItemInt(hWnd,IDC_A1,NULL,TRUE);
value2 = GetDlgItemInt(hWnd,IDC_B1,NULL,TRUE);
if (value1 >= value2) {
MessageBox(hWnd,_T("该进程到达时间应比前一进程晚"),_T("提示"),MB_OK);
SetDlgItemText(hWnd,IDC_B1,_T(""));
SetFocus(GetDlgItem(hWnd,IDC_B1));
}
} else if ( lstrcmp(str,_T("\0"))==0 && lstrcmp(str2,_T("\0"))!=0 ) {
MessageBox(hWnd,_T("先填写前一进程的到达时间"),_T("提示"),MB_OK);
SetDlgItemText(hWnd,IDC_B1,_T(""));
SetFocus(GetDlgItem(hWnd,IDC_A1));
}
}
break;
case IDC_C1:
if (codeNotify == EN_KILLFOCUS) {
GetDlgItemText(hWnd,IDC_B1,str,EDITLEN);
GetDlgItemText(hWnd,IDC_C1,str2,EDITLEN);
if ( lstrcmp(str,_T("\0"))!=0 && lstrcmp(str2,_T("\0"))!=0 ) {
value1 = GetDlgItemInt(hWnd,IDC_B1,NULL,TRUE);
value2 = GetDlgItemInt(hWnd,IDC_C1,NULL,TRUE);
if (value1 >= value2) {
MessageBox(hWnd,_T("该进程到达时间应比前一进程晚"),_T("提示"),MB_OK);
SetDlgItemText(hWnd,IDC_C1,_T(""));
SetFocus(GetDlgItem(hWnd,IDC_C1));
}
} else if ( lstrcmp(str,_T("\0"))==0 && lstrcmp(str2,_T("\0"))!=0 ) {
MessageBox(hWnd,_T("先填写前一进程的到达时间"),_T("提示"),MB_OK);
SetDlgItemText(hWnd,IDC_C1,_T(""));
SetFocus(GetDlgItem(hWnd,IDC_B1));
}
}
break;
case IDC_D1:
if (codeNotify == EN_KILLFOCUS) {
GetDlgItemText(hWnd,IDC_C1,str,EDITLEN);
GetDlgItemText(hWnd,IDC_D1,str2,EDITLEN);
if ( lstrcmp(str,_T("\0"))!=0 && lstrcmp(str2,_T("\0"))!=0 ) {
value1 = GetDlgItemInt(hWnd,IDC_C1,NULL,TRUE);
value2 = GetDlgItemInt(hWnd,IDC_D1,NULL,TRUE);
if (value1 >= value2) {
MessageBox(hWnd,_T("该进程到达时间应比前一进程晚"),_T("提示"),MB_OK);
SetDlgItemText(hWnd,IDC_D1,_T(""));
SetFocus(GetDlgItem(hWnd,IDC_D1));
}
} else if ( lstrcmp(str,_T("\0"))==0 && lstrcmp(str2,_T("\0"))!=0 ) {
MessageBox(hWnd,_T("先填写前一进程的到达时间"),_T("提示"),MB_OK);
SetDlgItemText(hWnd,IDC_D1,_T(""));
SetFocus(GetDlgItem(hWnd,IDC_C1));
}
}
break;
case IDC_E1:
if (codeNotify == EN_KILLFOCUS) {
GetDlgItemText(hWnd,IDC_D1,str,EDITLEN);
GetDlgItemText(hWnd,IDC_E1,str2,EDITLEN);
if ( lstrcmp(str,_T("\0"))!=0 && lstrcmp(str2,_T("\0"))!=0 ) {
value1 = GetDlgItemInt(hWnd,IDC_D1,NULL,TRUE);
value2 = GetDlgItemInt(hWnd,IDC_E1,NULL,TRUE);
if (value1 >= value2) {
MessageBox(hWnd,_T("该进程到达时间应比前一进程晚"),_T("提示"),MB_OK);
SetDlgItemText(hWnd,IDC_E1,_T(""));
SetFocus(GetDlgItem(hWnd,IDC_E1));
}
} else if ( lstrcmp(str,_T("\0"))==0 && lstrcmp(str2,_T("\0"))!=0 ) {
MessageBox(hWnd,_T("先填写前一进程的到达时间"),_T("提示"),MB_OK);
SetDlgItemText(hWnd,IDC_E1,_T(""));
SetFocus(GetDlgItem(hWnd,IDC_D1));
}
}
break;
case IDC_F1:
if (codeNotify == EN_KILLFOCUS) {
GetDlgItemText(hWnd,IDC_E1,str,EDITLEN);
GetDlgItemText(hWnd,IDC_F1,str2,EDITLEN);
if ( lstrcmp(str,_T("\0"))!=0 && lstrcmp(str2,_T("\0"))!=0 ) {
value1 = GetDlgItemInt(hWnd,IDC_E1,NULL,TRUE);
value2 = GetDlgItemInt(hWnd,IDC_F1,NULL,TRUE);
if (value1 >= value2) {
MessageBox(hWnd,_T("该进程到达时间应比前一进程晚"),_T("提示"),MB_OK);
SetDlgItemText(hWnd,IDC_F1,_T(""));
SetFocus(GetDlgItem(hWnd,IDC_F1));
}
} else if ( lstrcmp(str,_T("\0"))==0 && lstrcmp(str2,_T("\0"))!=0 ) {
MessageBox(hWnd,_T("先填写前一进程的到达时间"),_T("提示
"),MB_OK);
SetDlgItemText(hWnd,IDC_F1,_T(""));
SetFocus(GetDlgItem(hWnd,IDC_E1));
}
}
break;
}
}
INT_PTR CALLBACK ProcMain(HWND hwndDlg,UINT uMsg,WPARAM wParam,LPARAM
lParam)
{
switch(uMsg) {
chHANDLE_DLGMSG(hwndDlg,WM_INITDIALOG,OnInitDialog);
chHANDLE_DLGMSG(hwndDlg,WM_COMMAND,OnCommand);
}
return FALSE;
}
int WINAPI _tWinMain(HINSTANCE hinst,HINSTANCE,PTSTR pszCmdLine,int)
{
HWND hwnd = FindWindow( _T("#32770"),_T("进程调度算法模拟") );
if (IsWindow(hwnd) ) {
SetForegroundWindow(hwnd);
} else {
DialogBoxParam(hinst,MAKEINTRESOURCE(IDD_MAIN),NULL,ProcMain,_ttoi(pszCm
dLine));
}
return 0;
}