操作系统进程调度算法模拟__MFC实现

尾部插入node结点 */ void InsertNode(ProcInfo* node) { if (startProc == NULL) { startProc = endProc = node; } else { endProc->next = 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; }