进程调度算法的设计.doc
网络操作系统课程设计报告题 目 进程调度算法设计 姓 名 _凌乐乐_ 学 号 _12103463_ 同 组 者 _徐守保_ 专 业 12103352 指导教师 陈卫 成 绩 网络工程系2014年 12 月26日操作系统课程设计任务书学生姓 名凌乐乐徐守保学 号1210346312103352专业班级网络工程1班设计题目 进程调度算法的设计 内容概要:设计进程控制块PCB表结构,适用于多级队列反馈调度算法。建立进程就绪队列,编制入链子程序。编制多级队列反馈调度算法文献资料:计算机操作系统网络操作系统C语言设计要求: 本程序用多级队列反馈调度算法对五个进程进行调度,每个进程可有三个状态,并假设初始状态为就绪状态。为了便于处理,程序中的某进程运行时间以时间片为单位计算。各进程的优先数或轮转时间数以及进程需运行的时间片数的初始值均由用户给定。在优先数算法中,优先数的值为50与运行时间的差值,即P_TIME-process->needtime。进程每执行一次,优先数减3,CPU时间片数加1,进程还需要的时间片数减1。在轮转算法中,采用固定时间片(即:每执行一次进程,该进程的执行时间片数为已执行了2个单位),这时,CPU时间片数加2,进程还需要的时间片数减2,并排列到就绪队列的尾上。对于遇到优先数一致的情况,采用FIFO策略解决。 目 录一. 设计目的二. 设计内容1. 设计要求2. 设计技术参数三设计过程1. 实现功能2. 设计思路3. 算法和流程图四源程序五. 操作界面截图六. 设计总结七.个人遇到的困难与获得的主要成果(分人写) 正文一、 设计目的:通过课程设计, 加深对操作系统各资源管理模块的理解,掌握操作系统的基本原理及功能, 具有初步分析实际操作系统、设计、构造和开发现代操作系统的基本能力。二、 设计内容: 进程调度算法的设计1. 设计要求:设计进程控制块PCB表结构,适用于多级队列反馈调度算法。建立进程就绪队列,编制入链子程序。编制多级队列反馈调度算法 开发环境:VC+6.02. 设计技术参数:本程序用两种算法对五个进程进行调度,每个进程可有三个状态,并假设初始状态为就绪状态。为了便于处理,程序中的某进程运行时间以时间片为单位计算。各进程的优先数或轮转时间数以及进程需运行的时间片数的初始值均由用户给定。在优先数算法中,优先数的值为50与运行时间的差值,即P_TIME-process->needtime。进程每执行一次,优先数减3,CPU时间片数加1,进程还需要的时间片数减1。在轮转算法中,采用固定时间片(即:每执行一次进程,该进程的执行时间片数为已执行了2个单位),这时,CPU时间片数加2,进程还需要的时间片数减2,并排列到就绪队列的尾上。对于遇到优先数一致的情况,采用FIFO策略解决。三、 设计过程1. 实现功能通过操作者输入选择0、1、2(输入非法,则报错并显示可重新输入)来确定要进行的操作。选择0表示退出程序。选择1,进入进程就绪队列的创建,创建完5个进程后通过优先级调度算法对5个进程进行调度并显示结果。选择2,也是进入进程就绪队列的创建,创建完5个进程后通过时间片轮转调度算法对5个进程进行调度并显示结果。2. 设计思路优先级算法调度的设计分析:给每一个进程确定一个优先数,优先数的值为50与运行时间的差值,即P_TIME-process->needtime。处理器调度每次选择就绪进程中优先数最大者,让它占有处理器运行。接下来,进程每执行一次,优先数减3,CPU时间片数加1,进程还需要的时间片数减1。对于优先数的插入算法,每一个进来都按序排放,再需要插入时就只需按序查找,就能找到确定位置,查找时需要用到两个指针,一个是前去指针,一个为当前指针,方便数据的插入。具体算法如下:priority_insert(PCB *q) PCB *p1,*s,*prior; int n; s=q; /*待插入的PCB指针*/ p1=ready; /*就绪队列头指针*/ prior=p1; /*prior做p1的前驱指针*/ n=1; while(p1!=NULL)&&n) /*根据优先数确定插入位置*/ if(p1->prio>=s->prio) prior=p1; p1=p1->next; else n=0; if(prior!=p1) /*如果条件成立说明插入在prior与p1之间*/ prior->next=s; s->next=p1; else s->next=p1; /*否则插入在就绪队列的头*/ ready=s; 轮转法调度的设计分析:在轮转算法中,采用固定时间片(即:每执行一次进程,该进程的执行时间片数为已执行了2个单位),这时,CPU时间片数加2,进程还需要的时间片数减2,并排列到就绪队列的尾上。新的进程到来时也是直接插到就绪队列的队尾,具体算法如下:roundrun_insert(PCB *p2) tail->next=p2; /*将新的PCB插入在当前就绪队列的尾*/ tail=p2; p2->next=NULL;3. 算法和流程图在优先数算法中,优先数的值为50与运行时间的差值,即P_TIME-process->needtime。进程每执行一次,优先数减3,CPU时间片数加1,进程还需要的时间片数减1。在轮转算法中,采用固定时间片(即:每执行一次进程,该进程的执行时间片数为已执行了2个单位),这时,CPU时间片数加2,进程还需要的时间片数减2,并排列到就绪队列的尾上。对于遇到优先数一致的情况,采用FIFO策略解决的工作状态初始化pcb,创建进程先对其按优先级数排列就绪队列空?YN就绪队列首过程投入入进行运行进程所需时间减1,占用cpu加1,优先级减3进程完成?Y撤销进程采用优先级调度算法N选择0、1、212运行进程已占用cpu时间达到时间片?开始结束Y初始化pcb,创建进程就绪队列空?N就绪队列首过程投入进行时间片到,进程已占用cpu时间+2撤销进程进程所需时间数减2,把该进程插入到就绪队列YN采用时间片轮转调度算法0四、 源程序#include<iostream>#include<string>using namespace std;class Process /创建一个进程 public:string ProcessName; / 进程名字 int Time; / 进程运行需要的时间 int leval; / 进程的优先级 int LeftTime; / 进程运行一段时间后还需要的时间;/void Copy ( Process proc1, Process proc2); / 把proc2赋值给proc1void Sort( Process pr, int size) ; / 此排序后暗优先级从大到小排序void TimeTurn( Process process, int num, int Timepice); / 时间片轮转算法void Priority( Process process, int num, int Timepice); / 优先级算法/int main() int a; cout<<endl; cout<<" 选择调度算法:"<<endl; cout<<" 1: 时间片轮换 2: 优先级调度 "<<endl; cin>>a; const int Size =30; Process processSize ; int num; int TimePice; cout<<" 输入进程个数:"<<endl; cin>>num; cout<<" 输入此进程时间片大小: "<<endl; cin>>TimePice; for( int i=0; i< num; i+) string name; int CpuTime; int Leval; cout<<" 输入第 "<< i+1<<" 个进程的名字、cpu时间和优先级:"<<endl; cin>>name; cin>> CpuTime>>Leval; processi.ProcessName =name; processi.Time =CpuTime; processi.leval =Leval; cout<<endl; for ( int k=0;k<num;k+) processk.LeftTime=processk.Time ;/对进程剩余时间初始化 cout<<" (说明:在本程序所列进程信息中,优先级一项是指进程运行后的优先级! )" cout<<endl; cout<<endl; cout<<"进程名字 "<<"共需占用cpu时间 "<<" 还需要占用时间 "<<" 优先级 "<<" 状态 "<<endl; if(a=1) TimeTurn( process,num,TimePice);else if(a=2) Sort( process, num); Priority( process , num, TimePice);/ void Copy ( Process proc1, Process proc2) proc1.leval =proc2.leval ; proc1.ProcessName =proc2.ProcessName ; proc1.Time =proc2.Time ;/void Sort( Process pr, int size) /以进程优先级高低排序 / 直接插入排序 for( int i=1;i<size;i+) Process temp; temp = pri; int j=i; while(j>0 && temp.leval<prj-1.leval) prj = prj-1; j-; prj = temp; / 直接插入排序后进程按优先级从小到大排列 for( int d=size-1;d>size/2;d-) Process temp; temp=pr d; pr d = pr size-d-1; pr size-d-1=temp; / ´此排序后按优先级从大到小排列/ 时间片轮转调度算法实现/void TimeTurn( Process process, int num, int Timepice) while(true) if(num=0) cout<<" 所有进程都已经执行完毕!"<<endl; exit(1); if(process0.LeftTime=0) cout<<" 进程 "<<process0.ProcessName<< " 已经执行完毕 !"<<endl; for (int i=0;i<num;i+) processi=processi+1; num-; if( processnum-1.LeftTime =0 ) cout<<" 进程 " << processnum-1.ProcessName <<" 已经执行完毕! "<<endl; num-; else if(process0.LeftTime > 0) cout<<endl; /输出正在运行的进程 if(process0.LeftTime>1) process0.LeftTime=process0.LeftTime- Timepice; elseprocess0.LeftTime=process0.LeftTime-1; process0.leval =process0.leval-1; cout<<" "<<process0.ProcessName <<" "<<process0.Time <<" " cout<<process0.LeftTime <<" "<<process0.leval<<" 运行" cout<<endl; for(int s=1;s<num;s+) cout<<" "<<processs.ProcessName <<" "<<processs.Time <<" " cout<<processs.LeftTime <<" "<<processs.leval; if(s=1) cout<<" 就绪 "<<endl; else cout<<" 等待 "<<endl; Process temp; temp = process0; for( int j=0;j<num;j+) processj = processj+1; processnum-1 = temp; / else cout<<endl; system(" pause"); cout<<endl; / while/ 优先级调度算法的实现/void Priority( Process process, int num, int Timepice) while( true) if(num=0) cout<< "所有进程都已经执行完毕!"<<endl; exit(1); if(process0.LeftTime=0) cout<<" 进程 " << process0.ProcessName <<" 已经执行完毕! "<<endl; for( int m=0;m<num;m+) processm = processm+1; /一个进程执行完毕后从数组中删除 num-; / 此时进程数目减少一个 if( num!=1 && processnum-1.LeftTime =0 ) cout<<" 进程 " << processnum-1.ProcessName <<" 已经执行完毕! "<<endl; num-; if(process0.LeftTime > 0) cout<<endl; /输出正在运行的进程 if(process0.LeftTime>1) process0.LeftTime=process0.LeftTime- Timepice; else process0.LeftTime=process0.LeftTime-1; process0.leval =process0.leval-1; cout<<" "<<process0.ProcessName <<" "<<process0.Time <<" " cout<<process0.LeftTime <<" "<<process0.leval<<" 运行" cout<<endl; / 输出其他进程 for(int s=1;s<num;s+) cout<<" "<<processs.ProcessName <<" "<<processs.Time <<" " cout<<processs.LeftTime <<" "<<processs.leval ; if(s=1) cout<<" 就绪"<<endl; else cout<<" 等待"<<endl; / else Sort(process, num); cout<<endl; system(" pause"); cout<<endl; 五、 操作界面部分截图六、 设计总结:通过这次的课程设计,加深了我对操作系统中不少概念的理解(因为初期还没想好要做哪一个题目,所以在选择做这一题之前,也把其他题中的知识也顺便了解了一下),最后选择了做调度算法这个题目,更使我对调度算法有了一个更加全面的认识,因为平时就只是上课有听讲,课后都没怎么去好好复习,看透。这也教了我们一个道理,要想更好地掌握课本的知识,就要下功夫去研究、读懂,不然就会有“书到用时方恨少”的时候。七. 个人遇到的困难与获得的主要成果(分人写)凌乐乐:设计的时候一开始不知道选哪个作为课程设计的题目,页面置换算法做过,没成功,还是有很多错误,后来看了书,仔细的分析了进程调度算法的原理,开始理解,后来就选了这个,也遇到了不少问题,但后来经过各种方法查资料,时间有限,总算完成了。徐守保:选题是凌乐乐选的,我主要负责算法的实现和帮助一起找资料,困难的确有不少,比如,一个语句错了,我们也不知道哪错了,还问了计算机专业的人,拼拼凑凑还是弄完了。