操作系统课程设计报告进程作业调度.doc

一、课程设计题目：进程/作业调度二、实现要求：1. 建立作业的数据结构描述2. 使用两种方式产生作业/进程: (a)自动产生 (b)手工输入3. 在屏幕上显示每个作业/进程的执行情况。4. 时间的流逝可用下面几种方法模拟：(a)按键盘，每按一次可以认为过一个时间单位 (b)响应WM_TIMER (本实验采用b方法)5. 计算并显示一批作业/进程的周转时间，平均周转时间，带权周转时间，平均带权周转时间。6. 将一批作业/进程的执行情况存入磁盘文件，以后可以读出并重放。7. 支持的调度算法：先来先服务，短作业/进程优先，时间片轮转调度算法，优先权调度算法，高响应比优先调度算法，多级反馈队列调度算法。三、实验设备及环境： IBM PC及其兼容机一台、WindwosXP操作系统、Microsoft Visual C+6.0集成开发环境。四实验目的： 通过本次课程设计进一步加深对进程控制块、进程调度的理解，能够实现各种不同的进程调度算法。深入理解操作系统设计中有关进程方面的应该注意的相关事项。五实验总体设计思路：1、程序结构框架 程序中自定义了一个进程控制块PCB结构体，所有对进程的调度、进程切换等操作全都建立在PCB的基础之上。PCB中保存了进程标识符、进程到达时间、等待时间、进程调度状态、需要运行的时间等重要信息。PCB的定义如下：struct PCB /PCB结构int pid;/ID号int status;/进程状态int priority;/进程优先级数值越小，优先级越高.int start_time;/进程开始时间int need_time;/进程执行所需时间int wait_time;/进程已等待时间int end_time;/运行结束时间struct PCB *next;/PCB指针，指向下一PCB; 程序中还定义了一个正在PCB类型的指针指向正在运行的进程的进程控制块，3个就绪队列。除了多级反馈队列调度算法需要用到3个就绪队列外其他5种调度算法均只需要一个就绪队列。 本程序实现中采取产生PCB代替真实进程的方法来模拟进程。 本程序采用MFC框架构建，菜单栏主要包括了进程选项与调度算法。以task单文档视图为主题结构，mainframe实现菜单栏功能。2、程序初始化阶段 程序开始运行后首先要产生若干个进程，可以采取自动产生也可以采取手工输入进程控制块参数的方法产生进程。当用户每点击“自动产生”菜单一次，函数void CMainFrame:OnAuto()便自动产生一个进程并将其挂到就绪队列末尾，当用户点击“手工输入”菜单，便由函数void CMainFrame:OnManual()弹出输入对话框引导用户输入进程参数，之后把新产生的进程控制块挂到就绪队列末尾。以上两个函数均对进程编号pid做检查，以保证每个进程的唯一性，不允许有相同的进程。 在“调度算法”菜单中，用户选择了调度算法后，由相应的消息响应函数对调度算法标志dispatch进行赋值，然后根据dispatch值调用相关函数执行作业(进程)调度运算。/调度算法的响应函数/void CMainFrame:OnFcfs()dispatch=1;void CMainFrame:OnSpf()dispatch=2;void CMainFrame:OnTimeroll()dispatch=3;void CMainFrame:OnPriority()dispatch=4;void CMainFrame:OnHrespond()dispatch=5;void CMainFrame:OnMultifeedback()dispatch=6;/void CMainFrame:dispatch_entry() /算法入口switch(dispatch)case 1:fcfs();break;case 2:spf();break;case 3:timeRoll();break;case 4:priority();break;case 5:hirespond();break;case 6:multiFeedback();如果未选择进程调度算法，系统默认使用先来先服务的调度算法(dispatch赋值为1)。3、运行阶段 用户点击“运行”菜单后消息响应函数void CMainFrame:OnRun()设置计时器开始计时，置程序状态为运行状态，开始对各进程进行模拟调度、运行。在模拟进程调度运行的过程中由消息响应函数void CMainFrame:OnTimer(UINT nIDEvent)每秒被调用一次，在该函数中对各进程的状态进行刷新（包括进程调度）并输出到屏幕供用户观察进程的调度运行情况。 程序中还有一个free队列，该队列中保存所有运行完的进程的进程控制块，因为这些进程控制块信息要用来计算进程的周转时间，平均周转时间，带权周转时间，平均带权周转时间。 进程运行完后点击“打印运行结果”菜单，由void CMainFrame:OnPrintresult()函数计算并打印进程的周转时间，平均周转时间，带权周转时间，平均带权周转时间。 重放功能的实现较简单，在调度开始前每产生一个进程便调用void CMainFrame:store_PCB(const PCB* p)函数把该进程的PCB保存到文件pcb.txt中。当运行完后只需把文件pcb.txt中保存的PCB按系统时间先后顺序依次读出并挂到就绪队列后按之前的调度算法再开始调度运行便可。六、主要代码分析1、进程代码/* void CMainFrame:OnAuto()函数，自动产生进程控制块(PCB)状态。产生的 PCB挂接到以存在PCB的后面，其中，为了演示程序，优先级和所需时间都限定在1-10之内。*/void CMainFrame:OnAuto() /随机数产生srand(unsigned)time(NULL); /产生新的PCB指针ready_end-next=new PCB(); ready_end=ready_end-next;ready_end-next=NULL; /产生新的PCBready_end-pid=getnewpid();ready_end-status=0;ready_end-priority=(rand()%9+1);ready_end-start_time=task_timer;ready_end-need_time=(rand()%9+1);ready_end-wait_time=0;ready_end-end_time=0;/存储状态到pcb.txtstore_PCB(ready_end);/进行刷新显示操作status_print();/* void CMainFrame:OnManual()函数，点击菜单栏“手动输入”后手动创建PCB。*/void CMainFrame:OnManual()CInputDlg input;if(input.DoModal()=IDOK)if(!exist_pid(input.m_pid)ready_end-next=new PCB();ready_end=ready_end-next;ready_end-next=NULL;ready_end-pid=input.m_pid;ready_end-status=0;ready_end-priority=input.m_priority;ready_end-start_time=task_timer;ready_end-need_time=input.m_needtime;ready_end-wait_time=0;ready_end-end_time=0;store_PCB(ready_end);status_print();else MessageBox(ID号重复,请重新输入.);/* 调用SetTimer函数，以一秒钟为单位，以定时器TASK_TIMER为标志，使用OnTimer()函数做事件响应。*/void CMainFrame:OnRun()if(app_status=false)SetTimer(TASK_TIMER,1000,NULL);app_status=true;其中，void CMainFrame:OnTimer(UINT nIDEvent)为关键函数。在此函数中，确定了(1) 函数判断replay赋值情况，为真调用get_PCB_FromFile()函数，从pcb.txt文件中调用数据。(2) 调用status_print()函数进行显示操作。【void CMainFrame:status_print()函数，在创建的矩形框内每隔单位时间(此时间为1秒)进行刷新显示所有可用PCB操作。】(3) 在第一次运行OnTimer时，系统调用dispatch_entry()进行算法选择，只要用户选择过算法，dispatch值会做响应改变，dispatch_entry()根据dispatch值进入相应算法。void CMainFrame:OnTimer(UINT nIDEvent)if(TASK_TIMER & app_status=true)task_timer+;if(replay=true)get_PCB_FromFile();add_wait_time();status_print();dispatch_entry();else task_timer=0;CFrameWnd:OnTimer(nIDEvent);【UINT SetTimer( UINT nIDEvent, UINT nElapse, void (CALLBACK EXPORT* lpfnTimer)(HWND, UINT, UINT, DWORD) ); 参数含义： nIDEvent:是指设置这个定时器的iD，即身份标志，这样在OnTimer（）事件中，才能根据不同的定时器，来做不同的事件响应。这个ID是一个无符号的整型。 nElapse:是指时间延迟。单位是毫秒。这意味着，每隔nElapse毫秒系统调用一次Ontimer（）。 】周转时间：是指从作业被提交给系统开始，到作业完成为止的这段时间间隔。平均周转时间T=1/nT.带权周转时间W是指作业的周转时间T与系统为它提供服务的时间之比。平均带权周转时间W=1/nW.void CMainFrame:OnPrintresult()CRect rect;CFont font; HideCaret();CDC *pDC;pDC=GetDC();CBrushbrush;CPenpen(PS_SOLID,2,RGB(84,141,226);brush.CreateSolidBrush(RGB(84,141,226);pDC-SelectObject(pen);pDC-SelectObject(brush);CFont* pOldFont=(CFont*)pDC-SelectObject(&font); pDC-Rectangle(100,40,700,600);pDC-TextOut(200,80,PID 到达时间 服务时间 完成时间 周转时间 带权周转时间);PCB *p=free-next;int i=0,s=100;int turnover,server_time;float sum_turn=0,sum_right=0,right=0;char buffer100;while(p!=NULL) /输出显示一个队列./周转时间turnover=p-end_time - p-start_time; / 带权周转时间 right=turnover/ (float)(p-end_time - p-start_time - p-wait_time);server_time=p-end_time - p-start_time - p-wait_time;sprintf(buffer,%3d%10d%16d%18d%17d%25.3f,p-pid,p-start_time,server_time,p-end_time,turnover,right);sum_turn+=turnover;sum_right+=right;i+;pDC-TextOut(200,s,buffer);p=p-next;s=s+20;/ sum_turn/i计算平均周转时间，sum_right/i计算平均带权周转时间sprintf(buffer,平均周转时间: %0.3f,sum_turn/i);pDC-TextOut(200,s,buffer);sprintf(buffer,平均带权周转时间: %0.3f,sum_right/i);pDC-TextOut(200,s+20,buffer);ReleaseDC(pDC);ShowCaret();/释放所有PCB占用空间void CMainFrame:OnRelease().PCB *p;while(free-next!=NULL)p=free-next;free-next=p-next;delete p;free_end=free;MessageBox(释放成功);赋值replay为true，调用OnRun()函数，进行进程显示操作。具体在OnTimer()函数中已经说明void CMainFrame:OnPlayback() if(replay=false)replay=true;OnRun();2、具体算法函数 每个具体算法函数对应一个dispatch值。void CMainFrame:OnFcfs()dispatch=1;void CMainFrame:OnSpf()dispatch=2;void CMainFrame:OnTimeroll()dispatch=3;void CMainFrame:OnPriority()dispatch=4;void CMainFrame:OnHrespond()dispatch=5;void CMainFrame:OnMultifeedback()dispatch=6; 先来先服务调度算法(FCFS)。按照先来先服务调度算法定义，依次执行队列中PCB。通过task_run()函数是从PCB队列中取出一个最靠前的PCB指针，处理完成后使用pcb_recycle()函数释放run指针空间；再继续使用task_run()函数依次反复直到队列结束。void CMainFrame:fcfs()if(run!=NULL | ready-next!=NULL | blocked-next!=NULL)task_run();if(run!=NULL)run-need_time-;if(run-need_time=0)pcb_recycle();task_run();if(run!=NULL)run-wait_time+;else app_status=false;void CMainFrame:task_run()if(run=NULL & ready-next!=NULL)run=ready-next;ready-next=run-next;run-next=NULL;run-status=1;if(run=ready_end)ready_end=ready;void CMainFrame:pcb_recycle()/PCB回收机制.free_end-next=run;free_end=run;free_end-status=0;free_end-end_time=task_timer;run=NULL; 短作业进程优先调度算法(SPF)。根据短作业进程优先调度算法定义，调用task_run_spf()函数以“need_time”为比较找出需要时间最短的PCB，进行显示后调用pcb_recycle()释放run空间；而后继续调用task_run_spf()函数直到PCB队列结束。void CMainFrame:spf()if(run!=NULL | ready-next!=NULL | blocked-next!=NULL)task_run_spf();if(run!=NULL)run-need_time-;if(run-need_time=0)pcb_recycle();task_run_spf();if(run!=NULL)run-wait_time+;else app_status=false;void CMainFrame:task_run_spf()if(run=NULL & ready-next!=NULL)PCB *p,*q,*r;/r指向p前一个PCB,q为搜索指针r=ready;p=q=ready-next;while(q!=NULL)if(p-need_time q-need_time)p=q;while(r-next!=p)r=r-next;q=q-next;r-next=p-next;run=p;run-next=NULL;run-status=1;if(run=ready_end)ready_end=ready; 时间片轮转调度算法。根据时间片轮转调度算法定义，设定时间片为TIME_CHIP=3,调用task_run()函数，从PCB队列中取出一个PCB，判断此PCB能否在一个时间片内执行完毕，如果不可以，在执行完毕后调用task_exchange_timeRoll()函数切换进程，并使用task_block()函数将此进程置于PCB队列最后；如果可以，释放此PCB所占空间后，调用task_run()函数继续调入后面PCB。反复直到PCB进行完毕。void CMainFrame:timeRoll()if(run!=NULL | ready-next!=NULL | blocked-next!=NULL)task_run();if(run!=NULL)if(time_chip-)=0)/进程切换.task_exchange_timeRoll();time_chip=TIME_CHIP;else run-need_time-;if(run-need_time=0)time_chip=TIME_CHIP;pcb_recycle();task_run();if(run!=NULL)run-wait_time+;if(rand()%5=0)task_block();task_run();if(rand()%5=4)task_wake();else app_status=false;void CMainFrame:task_exchange_timeRoll()if(ready-next!=NULL)ready_end-next=run;ready_end=run;ready_end-status=0;run=NULL;task_run();void CMainFrame:task_block()if(run!=NULL)blocked_end-next=run;blocked_end=run;blocked_end-status=2;run=NULL;void CMainFrame:task_wake()if(blocked-next!=NULL)if(blocked-next=blocked_end)blocked_end=blocked;ready_end-next=blocked-next;ready_end=ready_end-next;blocked-next=ready_end-next;ready_end-next=NULL;ready_end-status=0; 优先权调度算法。根据优先权调度算法定义，此算法将最初处于最高优先权的PCB完成之后再进行第二优先权PCB，即使用非抢占式优先权算法。它使用task_run_priority()函数找出优先权最高的PCB进程，然后进行，完成后释放空间；并继续调用task_run_priority()函数，直到PCB队列结束。void CMainFrame:priority()if(run!=NULL | ready-next!=NULL | blocked-next!=NULL)task_run_priority();if(run!=NULL)run-need_time-;if(run-need_time=0)pcb_recycle();task_run_priority();if(run!=NULL)run-wait_time+;else app_status=false;void CMainFrame:task_run_priority()if(run=NULL & ready-next!=NULL)PCB *p,*q,*r;r=ready;p=q=ready-next;while(q!=NULL)if(p-priority q-priority)p=q;while(r-next!=p)r=r-next;q=q-next;r-next=p-next;run=p;run-next=NULL;run-status=1;if(run=ready_end)ready_end=ready; 高响应比优先算法。根据计算公式：R=(所需时间+已等待时间)/所需时间，调用task_run_hirespond()函数取出首个PCB进行，之后反复调用task_run_hirespond()函数直到结束。void CMainFrame:hirespond()if(run!=NULL | ready-next!=NULL | blocked-next!=NULL)task_run_hirespond();if(run!=NULL)run-need_time-;if(run-need_time=0)pcb_recycle();task_run_hirespond();if(run!=NULL)run-wait_time+;else app_status=false;void CMainFrame:task_run_hirespond()if(run=NULL & ready-next!=NULL)PCB *p,*q,*r;r=ready;p=q=ready-next;while(q!=NULL)if(p-wait_time+p-need_time)/p-need_time) wait_time+q-need_time)/q-need_time) p=q;while(r-next!=p)r=r-next;q=q-next;r-next=p-next;run=p;run-next=NULL;run-status=1;if(run=ready_end)ready_end=ready; 多级反馈队列调度算法。设置多个就绪队列(ready,ready1,ready2)并初始化，调用task_run_multiFeedback(r,r_end)函数从PCB队列中读取第一个PCB，分入第一反馈队列，执行它后判断time_chip值，当值为0时调用task_exchange_multiFeedback(i)函数进行队列切换到第二队列，调用task_run_multiFeedback(r,r_end)函数从PCB队列中读取PCB，反复进行判断；当值不为0时，继续向第一队列添加PCB并判断run-need_time值，为0调用pcb_recycle()函数进行PCB空间释放操作，并继续余下进程。void CMainFrame:multiFeedback()if(run!=NULL | ready-next!=NULL | ready2-next!=NULL | ready3-next!=NULL | blocked-next!=NULL)int i;PCB *r,*r_end;if(ready-next!=NULL) i=1; r=ready; r_end=ready_end; else if(ready2-next!=NULL ) i=2; r=ready2; r_end=ready2_end; else i=3; r=ready3; r_end=ready3_end; task_run_multiFeedback(r,r_end);if(time_chip-)=0)/进程切换.task_exchange_multiFeedback(i);time_chip=TIME_CHIP*i;else run-need_time-;if(run-need_time=0)time_chip=TIME_CHIP*i;pcb_recycle();if( ready-next!=NULL) task_run_multiFeedback(ready,ready_end);else if(ready2-next!=NULL ) task_run_multiFeedback(ready2,ready2_end);else if(ready3-next!=NULL ) task_run_multiFeedback(ready3,ready3_end);if(run!=NULL) run-wait_time+;else app_status=false;/void CMainFrame:task_run_multiFeedback(PCB *r, PCB *r_end)/产生新进程if(run=NULL & r-next!=NULL)run=r-next;r-next=run-next;run-next=NULL;run-status=1;if(run=r_end)if(r=ready)ready_end=ready;else if(r=ready2)ready2_end=ready2;else ready3_end=ready3;void CMainFrame:task_exchange_multiFeedback(int i)/进程切换.if(i=1)ready2_end-next=run;ready2_end=run;ready2_end-status=0;run=NULL;if( ready-next!=NULL) task_run_multiFeedback(ready,ready_end);else if(ready2-next!=NULL ) task_run_multiFeedback(ready2,ready2_end); else if(ready3-next!=NULL ) task_run_multiFeedback(ready3,ready3_end); else if(i=2 | i=3)ready3_end-next=run;ready3_end=run;ready3_end-status=0;run=NULL;if( ready-next!=NULL) task_run_multiFeedback(ready,ready_end);else if(ready2-next!=NULL ) task_run_multiFeedback(ready2,ready2_end); else if(ready3-next!=NULL ) task_run_multiFeedback(ready3,ready3_end);七、课程设计心得体会通过本次操作系统课程设计让我对操作系统课程中所讲授的进程调度部分的认识有了一个质的进步。通过自己动手实现了进程相关的描述信息、进程调度算法、进程切换等功能更进一步了解了如何对进程操作同时也锻炼了自己编程的的能力。八、程序中有几个不足之处：1、 使用了背景图后，在移动窗口覆盖时会调用OnDraw()函数进行重绘，有可能覆盖了输出显示。2、 时间片轮转调度算法中，有stack溢出错误，查询资料无法解决，不过不影响程序编译与执行。3、 多级反馈队列设计时有点混乱。4、 进程运行之后不能打断。九、程序运行测试的部分截图进程调度过程中的截图调度运行完成后打印的结果文件pcb.txt中保存的PCB十、程序实现的主要代码/ MainFrm.h : interface of the CMainFrame class/#if !defined(AFX_MAINFRM_H_4FD998F9_FB1D_409E_B6A1_A6CD8A6DDCC5_INCLUDED_)#define AFX_MAINFRM_H_4FD998F9_FB1D_409E_B6A1_A6CD8A6DDCC5_INCLUDED_#if _MSC_VER 1000#pragma once#endif / _MSC_VER 1000#defineMAX_NUM 50#defineTIME_CHIP 3#definePCB_FILENAMEpcb.txt#include/struct PCB /PCB结构int pid;/ID号int status;/进程状态int priority;/进程优先级数值越小，优先级越高.int start_time;/进程开始时间int need_time;/进程执行所需时间int wait_time;/进程已等待时间int end_time;/运行结束时间struct PCB *next;/PCB指针，指向下一PCB;/class CMainFrame : public CFrameWndprotected: / create from serialization onlyCMainFrame();DECLARE_DYNCREATE(CMainFrame)/ Attributespublic:/ Operationspublic:/ Overrides/ ClassWizard generated virtual function overrides/AFX_VIRTUAL(CMainFrame)virtual BOOL PreCreateWindow(CREATESTRUCT& cs);/AFX_VIRTUAL/ Implementationpublic:bool replay;void get_PCB_FromFile();void linkchar(char * s,char c);void store_PCB(constPCB*p);void task_run_multiFeedback(PCB* r,PCB* r_end);void task_exchange_multiFeedback(int i);void task_wake();void task_block();void pcb_recycle();bool exist_pid(int id);void task_run_priority();void task_run_hirespond();void task_exchange_timeRoll();void task_run_spf();void dispatch_entry();void multiFeedback();void hirespond();void priority();void timeRoll();void spf();void fcfs();int getnewpid();void status_print();void task_run();virtual CMainFrame();#ifdef _DEBUGvirtual void AssertValid() const;virtual void Dump(CDumpContext& dc) const;#endifprotected: / control bar embedded membersCStatusBar m_wndStatusBar;/ Generated message map functionsprotected:/AFX_MSG(CMainFrame)afx_msg int OnCreate(LPCREATESTRUCT lpCreateStruct);afx_msg void OnTimer(UINT nIDEvent);afx_msg void OnDestroy();afx_msg void OnManual();afx_msg void OnRun();afx_msg void OnAuto();afx_msg void OnFcfs();afx_msg void OnHrespond();afx_msg void OnMultifeedback();afx_msg void OnPriority();afx_msg void OnSpf();afx_msg void OnTimeroll();afx_msg void OnPrintresult();afx_msg void OnRelease();afx_msg void OnPlayback();/AFX_MSGDECLARE_MESSAGE_MAP()private:int ready_num;FILE*m_filein;FILE*m_fileout;void add_wait_time();bool app_status; /标志有无进程运行int dispatch; /调度算法标志int task_timer; /时间int time_chip;/时间片PCB *run,*blocked,*blocked_end,*free,*free_end;PCB *ready,*ready_end,*ready2,*ready2_end,*ready3,*ready3_end;/AFX_INSERT_LOCATION/ Microsoft Visual C+ will insert additional declarations immediately before the previous line.#endif / !defined(AFX_MAINFRM_H_4FD998F9_FB1D_409E_B6A1_A6CD8A6DDCC5_INCLUDED_)/ MainFrm.h : interface of the CMainFrame class/#if !defined(AFX_MAINFRM_H_4FD998F9_FB1D_409E_B6A1_A6CD8A6DDCC5_INCLUDED_)#define AFX_MAINFRM_H_4FD998F9_FB1D_409E_B6A1_A6CD8A6DDCC5_INCLUDED_#if _MSC_VER 1000#pragma once#endif / _MSC_VER 1000#defineMAX_NUM 50#defineTIME_CHI