进程∕作业调度系统课程设计报告.pdf

一、课程设计题目：进程/作业调度二、实现要求：1.建立作业的数据结构描述2.使用两种方式产生作业/进程:（a）自动产生（b）手工输入3.在屏幕上显示每个作业/进程的执行情况。4.时间的流逝可用下面几种方法模拟:Ja）按键盘，每按一次可以认为过一个时 间单位（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=l;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;lllllllllllllllllllllllllllllllllllllllllllllllllllllllllvoid CMainFrame:dispatch_entry()算法入 口(switch(dispatch)(case l:fcfs();break;case 2:spf();break;case 3:timeRollQ;break;case 4:priority();break;case 5:hirespond();break;case 6:multiFeedback();)如果未选择进程调度算法，系统默认使用先来先服务的调度算法(dispatch赋 值为l)o3、运行阶段用户点击“运行”菜单后消息响应函数void CMainFrame:OnRun()设置计时 器开始计时，置程序状态为运行状态，开始对各进程进行模拟调度、运行。在模 拟进程调度运行的过程中由消息响应函数void CMainFrame:OnTimer(UINT nIDEvent)每秒被调用一次，在该函数中对各进程的状态进行刷新(包括进程调 度)并输出到屏幕供用户观察进程的调度运行情况。程序中还有一个free队列，该队列中保存所有运行完的进程的进程控制块，因为这些进程控制块信息要用来计算进程的周转时间，平均周转时间，带权周转 时间，平均带权周转时间。进程运行完后点击“打印运行结果”菜单，由void CMainFrame:OnPrintresult()函数计算并打印进程的周转时间，平均周转时间，带权周转时间，平均带权周转 时间。重放功能的实现较简单，在调度开始前每产生一个进程便调用voidCMainFrame: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=O;ready_end-end_time=O;/存储状态到pcb.txtstore_PCB(ready_end);进行刷新显示操作status_print();)/*voidCMainFrame:OnManual(涵数，点击菜单栏“手动输入”后手动创建PCBo*/void CMainFrame:OnManual()(ClnputDlg 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=O;ready _end-priority=input.m_priority;ready _end-start_time=task_timer;ready_end-need_time=input.m_needtime;ready_end-wait_time=O;ready_end-end_time=O;store_PCB(ready_end);status_print();)else MessageBox(HID号重复，请重新输入.”)；)/*调用SetTimer函数，以一秒钟为单位，以定时器TASKJTIMER为标志，使 用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()函数，在创建的矢f形框内每隔单位时间(此时间为1秒)进行刷新显示所有可用PCB 操作。】在第一次运行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=O;CFrameWnd:OnTimer(nIDEvent);)UINT SetTimer(UINT nIDEvent,UINT nElapse,void(CALLBACK EXPORT*lpfnTimer)(HWND,UINT,UINT,DWORD);参数含义：nIDEvent:是指设置这个定时器的迫，即身份标志，这样在OnTimer O事件 中，才能根据不同的定时器，来做不同的事件响应。这个ID是一个无符号的 整型。nElapse:是指时间延迟。单位是毫秒。这意味着，每隔nElapse毫秒系统调用一次 Ontimer O。周转时间：是指从作业被提交给系统开始，到作业完成为止的这段时间间隔。平均周转时间T=l/nET.带权周转时间W是指作业的周转时间T与系统为它提供服务的时间之比。平均带权周转时间W=l/nEW.void CMainFrame:OnPrintresult()(CRect rect;CFont font;HideCaret();CDC*pDC;pDC=GetDC();CBrush brush;CPen pen(PS_SOLID,2,RGB(84,141,226);brush.CreateSolidBrush(RGB(84,141,226);pDC-SelectObj ect(pen);pDC-SelectObject(brush);CFont*pOldFont=(CFont*)pDC-SelectObject(&font);pDC-Rectangle(l 00,40,700,600);pDC-TextOut(200,80,nPID 到达时间 服务时间 完成时间 周转时间带权周转时间”)；PCB*p=free-next;int i=0,s=100;int turnover,server_time;float sum_turn=O,sum_right=O,right=O;char buffer 100;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,n%3d%10d%16d%18d%17d%25.3fn,p-pid,p-start_time,server_time,p-end_time,turnover,right);sum_turn+=tumover;sum_right+=right;i+；pDC-T extOut(200,s,buffer);p=p-next;s=s+20;)/sum_tum/i计算平均周转时间,sum_right/i计算平均带权周转时间sprintf(buffer,”平均周转时间：%0.3fn,sum_turn/i);pDC-TextOut(200,s,buffer);sprintf(buffer,”平均带权周转时间：%0.3fn,sum_right/i);pDC-TextOut(200,s+20,buffer);ReleaseDC(pDC);ShowCaretQ;)释放所有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)。按照先来先服务调度算法定义，依次执行队 列中PCBo通过task_nm()函数是从PCB队列中取出一个最靠前的PCB指针，处理完成后使用pcb_recycle()函数释放run指针空间；再继续使用task_nm()函 数依次反复直到队列结束。void CMainFrame:fcfs()(if(run!=NULL II ready-next!=NULL II blocked-next!=NULL)task_run();if(run!=NULL)run-need_time;if(run-need_time=O)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=l;if(run=ready_end)ready_end=ready;)void CMainFrame:pcb_recycle()/PCB 0 收机制.(free_end-next=run;free_end=run;free_end-status=O;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 II ready-next!=NULL II blocked-next!=NULL)task_run_spf();if(run!=NULL)run-need_time;if(run-need_time=O)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=l;if(run=ready_end)ready_end=ready;)时间外轮转调度算法。根据时间外轮转调度算法定义，设定时间片为 TIME_CHIP=3,调用task_nm()函数，从PCB队列中取出一个PCB,判断止匕PCB 能否煮一个时间片而执行完毕，如果不可以，在执行完毕后调用 task_exchange_timeRoll()函数切换进程，并使用task_block()函数将此进程置于 PCB队列最后；如果可以，释放此PCB所占空间后，调用task_nm()函数继续调 入后面PCB。反复直到PCB进行完毕。void CMainFrame:timeRoll()(if(run!=NULL II ready-next!=NULL II blocked-next!=NULL)task_run();if(run!=NULL)if(time_chip-)=O)进程切换.task_exchange_timeRoll();time_chip=TIME_CHIP;)else run-need_time;if(run-need_time=O)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=O;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=O;优先权调度算法。根据优先权调度算法定义，此算法将最初处于最高优先 权的PCB完成之后再进行第二优先权PCB,即使用非抢占式优先权算法。它使 用task_nm_priorityO函数找出优先权最高的PCB进程，然后进行，完成后释放 空间；并继续调用task_nm_priorityO函数，直到PCB队列结束。void CMainFrame:priority()(if(run!=NULL II ready-next!=NULL II blocked-next!=NULL)task_run_priority();if(run!=NULL)run-need_time;if(run-need_time=O)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=l;if(run=ready_end)ready_end=ready;)高响应比优先算法。根据计算公式：R=(所需时间+已等待时间)/所需时间，调用task_run_hirespond()函数取出首个PCB进行，之后反复调用 task_run_hirespond()函数直到结束。void CMainFrame:hirespond()(if(run!=NULL II ready-next!=NULL II blocked-next!=NULL)task_run_hirespond();if(run!=NULL)run-need_time;if(run-need_time=O)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=l;if(run=ready_end)ready_end=ready;)多级反馈队列调度算法。设置多个就绪队列(ready,readyl,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值，为。调用 pcbecycle()函数进行PCB空间释放操作，并继续余下进程。void CMainFrame:multiFeedback()(if(run!=NULL II ready-next!=NULL II ready 2-next!=NULL IIready3-next!=NULL II blocked-next!=NULL)int i;PCB*r,*r_end;if(ready-next!=NULL)i=l;r=ready;r_end=ready_end;else if(ready 2-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-)=O)进程切换.task_exchange_multiFeedback(i);time_chip=TIME_CHIP*i;)else run-need_time;if(run-need_time=O)time_chip=TIME_CHIP*i;pcb_recycle();if(ready-next!=NULL)task_run_multiFeedback(ready,ready_end);else if(ready 2-next!=NULL)task_run_multiFeedback(ready2,ready 2_end);else if(ready 3-next!=NULL)task_run_multiFeedback(ready3,ready3_end);if(run!=NULL)run-wait_time+;)else app_status=false;)IIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIHvoid 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=l;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=l)(ready 2_end-next=run;ready2_end=run;ready 2_end-status=0;run=NULL;if(ready-next!=NULL)task_run_multiFeedback(ready,ready_end);else if(ready 2-next!=NULL)task_run_multiFeedback(ready2,ready 2_end);else if(ready 3-next!=NULL)task_run_multiFeedback(ready3,ready3_end);)else if(i=2 II i=3)(ready3_end-next=run;ready3_end=run;ready 3_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(ready 3-next!=NULL)task_run_multiFeedback(ready3,ready3_end);)七、课程设计心得体会通过本次操作系统课程设计让我对操作系统课程中所讲授的进程调度部分 的认识有了一个质的进步。通过自己动手实现了进程相关的描述信息、进程调度 算法、进程切换等功能更进一步了解了如何对进程操作同时也锻炼了自己编程的 的能力。八、程序中有几个不足之处：1、使用了背景图后，在移动窗口覆盖时会调用OnDraw()函数进行重绘，有可能 覆盖了输出显示。2、时间片轮转调度算法中，有stack溢出错误，查询资料无法解决，不过不影响 程序编译与执行。3、多级反馈队列设计时有点混乱。4、进程运行之后不能打断。九、程序运行测试的部分截图进程调度过程中的截图PID状态优先级开始时间所需时间已等待时间4561101092905049818050495970504912303089调度运行完成后打印的结果PID到达时间服务时间完成时间周转时间蒂权周转时间45601010101.0001230818182.2509290A22225.5008180A26266.5005970A30307.500平均周传时间：21.200平均带权周转时间：4.550文件pcb.txt中保存的PCB文件(F)编辑(E)格式(。)查看(V)帮助(H)040929500004081850000405975000080123300001004561000十、程序实现的主要代码/MainFrm.h:interface of the CMainFrame class/#if!defined(AFX_MAINFRM_H_4FD998F9_FBlD_409E_B6Al_A6CD8A6DDC C5_INCLUDED_)#defineAFX_MAINFRM_H_4FD998F9_FB1D_4O9E_B6A1_A6CD8A6DDCC5_INCLU DED_#if_MSC_VER 1000#pragma once#endif/_MSC_VER 1000#define MAX_NUM 50#define TIME_CHIP 3#define PCB_FILENAME#includepcb.txt”llllllllllllllllllllllllllllllllllllllllllllllllllllllllllllllllllllllllllllllstruct PCB int pid;int status;int priority;int start_time;int need_time;int wait_time;int end_time;struct PCB*next;/PCB结构/ID 号进程状态进程优先级数值越小，优先级越高.进程开始时间进程执行所需时间进程已等待时间运行结束时间/PCB指针，指向下一 PCB)；llllllllllllllllllllllllllllllllllllllllllllllllllllllllllllllllllllllllllllll class CMainFrame:public CFrameWnd protected:/create from serialization onlyCMainFrame();DECLARE_DYNCREATE(CMainFrame)/Attributespublic:/Operations public:/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(const PCB*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 fcfsQ;int getnewpid();void status_print();void task_run();virtual-CMainFrame();#ifdef.DEBUGvirtual void AssertValid()const;virtual void Dump(CDumpContext&de)const;#endifprotected:/control bar embedded members CStatusBar m_wndStatusBar;/Generated message map functionsprotected:/AFX_MSG(CMainFrame)afx_msg int OnCreate(LPCREATESTRUCT IpCreateStruct);afx_msg void OnTimer(UINT nIDEvent);afx_msg void OnDestroyO;afx_msg void OnManual();afx_msg void OnRun();afx_msg void OnAuto();afx_msg void OnFcfsQ;afx_msg void OnHrespondQ;afx_msg void OnMultifeedback();afx_msg void OnPriorityO;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;)；lllllllllllllllllllllllllllllllllllllllllllllllllllllllllllllllllllllllllllll AFXNSERT_LOCATION/Microsoft Visual C+will insert additional declarations immediately before the previous line.#endif/!defined(AFX_MAINFRM_H_4FD998F9_FBlD_409E_B6Al_A6CD8A6DDCC 5_INCLUDED_)/MainFrm.h:interface of the CMainFrame class/#if!defined(AFX_MAINFRM_H_4FD998F9_FBlD_409E_B6Al_A6CD8A6DDC C5_INCLUDED_)#defineAFX_MAINFRM_H_4FD998F9_FB1D_4O9E_B6A1_A6CD8A6DDCC5_INCLUDED_#if_MSC_VER 1000#pragma once#endif/_MSC_VER 1000#define MAX_NUM 50#define TIME_CHIP 3#define PC