处理机调度算法的实现.docx

《处理机调度算法的实现.docx》由会员分享，可在线阅读，更多相关《处理机调度算法的实现.docx（23页珍藏版）》请在淘文阁 - 分享文档赚钱的网站上搜索。

1、处理机调度算法的实现一、核心算法思想1 .先来先服务调度算法先来先服务调度算法是一种最简单的调度算法，该算法既可以用于作业调度，也可用 于进程调度。当在作业调度中采用该算法时，每次调度都是从后备作业队列中选择一个或多 个最先进入该队列的作业，将他们调入内存，为它们分配资源、创建进程，然后放入就绪队 列。在进程调度中采用FCFS算法时，则每次调度是从就绪队列中选择一个最先进入该队列 的进程，为之分配处理机，使之投入运行。该进程一直运行到完成或发生某事件而阻塞后才 放弃处理机。FCFS算法比较有利于长作业（进程），而不利于短作业（进程）。2 .短作业（进程）优先调度算法短作业（进程）优先调度算法S

2、J （P） F,是指对短作业或短进程优先调度的算法。它 们可以分别用于作业调度和进程调度。短作业优先（SJF）的调度算法是从后备队列中选择 一个或若干个估计运行时间最短的作业，将它们调入内存运行。而短进程（SPF）调度算法 则是从就绪队列中选出一个估计运行时间最短的进程，将处理机分配给它，使它立即执行并 一直执行到完成，或发生某事件而被阻塞放弃处理机再重新调度。SJ（P）F调度算法能有效地 降低作业（进程）的平均等待时间，提高系统存吐量。该算法对长作业不利，完全未考虑作 业的紧迫程度。3 .高响应比优先调度算法在批处理系统中，短作业优先算法是一种比较好的算法，其主要不足之处是长作业的 运行得不

3、到保证。如果我们能为每个作业引人动态优先权，并使作业的优先级随着等待时间 的增加而以速率a提高，则长作业在等待一定的时间后，必然有机会分配到处理机。该优先 权的变化规律可描述为：优先权=（等待时间+要求服务时间）/要求服务时间即优先权=响应时间/要求服务时间如果作业的等待时间相同，则要求服务的时间越短，其优先权越高，因而该算法有利 于短作业。当要球服务的时间相同时、作业的优先权决定于其等待时间，等待时间越长，优先权 越高，因而它实现的是先来先服务对于长作业，作业的优先级可以随着等待时间的增加而提高，当其等待时间足够长时, 其优先级便可以升到很高，从而也可获得处理机。4 .时间片轮转算法在时间片

4、轮转算法中，系统将所有的就绪进程按先来先服务的原则排成一个队列，每 次调度时，把CPU分配给队首进程，并令其执行一个时间片。当执行的时间片用完时，由 一个计数器发出时钟中断请求，调度程序便据此信号来停止该进程的执行，并将它送往就绪 队列的末尾；然后，再把处理机分配给就绪队列中新的队首进程，同时也让它执行一个时间 片。这样就可以保证就绪队列中的所有进程在一给定的时间内均能获得一时间片的处理机执return pr;五、运行结果1.先来先服务算法运行结果n n n n n n0 00 00 0w w w w w w1 ii i i is proc s proc s proc s proc s pro

5、c s proc:ess 0:ess 0:ess 0:ess 0:ess 0:ess 0n n n n n n n0 00 00 00w w w w w w wi i i i i i is proc s proc s proc s proc s proc s proc s proc:ess 3:ess 3:ess 3:ess 3:ess 3:ess 3:ess 3n n n n n n0 00 00 0w w w w w wi i i i i is proc s proc s proc s proc s proc s proc:ess 2:ess 2:ess 2:ess 2:ess 2:ess

6、 2process 0 needtime process 0 needtime process 0 needtime process 0 needtime process 0 needtimethe process 0 is (is is is is is end54321process 3 needtimeisprocess 3 needtimeisprocess 3 needtimeisprocess 3 needtimeisprocess 3 needtimeisprocess 3 needtimeisthe process 3 is endprocess 2 needtimeis5pr

7、ocess 2 needtimeis4process 2 needtimeis3process 2 needtimeis2process 2 needtimeis1the process 2 is endnow is process 1 the process 1 is end短进程优先算法运行结果2name of processl state 0 cputime 0 name of process2 state 0 cputime 0 name of processO state 0 cputime 0 now is process 1needtime 6 arrivetime 5needt

8、ime 7 arrivetime 0pri 0pri 2222222sssssSwwwwwwoooooonnnnnnprocess 2 needtime is 5process 2 needtime is 4process 2 needtime is 3process 2 needtime is 2process 2 needtime is 1the process 2 is endthe process 1 is endnow is process 0now is process 0now is process 0now is process 0now is process 0now is

9、process 0now is process 0IS is is is is is end6543213.高相应比优先算法运行结果name of state 0 name of state 0 please 1 FCFS 3processlcputime 0process2cputime 0 choose the whatneedtime 1needtime 6arriuetime 6arrivetime 5pri 1pri 02 SJFyou want toHRRN 4 RRusenow now now now now now nowprocess process process proc

10、ess process process process0 0000 00process process process process process process0 000 00needtime needtime needtime needtime needtime needtimethe process 0 is end222222process process process process processneedtime needtime needtime needtime needtimethe process 2 is endnow is process 1 the proces

11、s 1 is end4 .时间片轮转算法运行结果54321name of state 0 name of state 0 name of state 0 now is now is now is00021021needtimeneedtimeprocess 0 needtimeprocess 2 needtimearrivetimearrivetimeis 6is 5the process 1 is endpnpriOOOOOOOOOO0202020202process process process process process process process process proces

12、s020202020needtime needtime needtime needtime needtime needtime needtime needtime needtimeis is isis is isis is is544332211the process 2 is endthe process 0 is end六、心得体会课程设计结束了，在这次的课程设计中不仅检验了我所学习的知识，也培养了我如何去做一 件事情，又如何完成一件事情的能力。通过模拟进程的调度问题，更加深了我对于操作系统理论的理解,在自己的动手操作过程中, 能够体会成功的喜悦和遇到问题自己解决的能力，对于我来说是一次提

13、高，让自己多多的在 实践中可以加深对理论的理解，也让我明白了以后应该如何更好，更高效的学习。进程调度算法工.实验目的调度的实质是操作系统按照某种预定的策略来分配资源。进程调度的目的是分配 CPU资源。由于进程调度程序执行的频率很高，因此调度算法的好坏直接影响 到操作系统的性能。本实验的目的是编程模拟实现几种常用的进程调度算法，通 过对几组进程分别使用不同的调度算法，计算进程的平均周转时间和平均带权周 转时间，比较各种算法的性能优劣。2.实验原理L进程调度算法描述进程调度算法包括先来先服务调度算法、优先数调度算法、时间片轮转算法和分 级调度算法4种。先来先服务（FCFS）调度算法本算法在进行调度

14、时，总是把处理机分配给最先进入就绪队列的进程，一个进程 一旦分得处理机，便一直执行下去，直到该进程完成或阻塞时，才释放处理机。优先数调度算法基于优先级的调度算法给每个进程分配一个优先级，在每次进程调度时，调度器 总是调度那个具有最高优先级的任务来执行。如果就绪队列中出现优先数相同的进程，则对这些有相同优先数的进程采用FCFS算法调度。对于占有处理机的进程，系统可以使用“抢占式”或“非抢占式”的策略。“非 抢占式”指进程一旦占用处理机，除非自己愿意，否则操作系统不能将处理机强 行夺走，即使该进程的优先数已经小于就绪队列中的某个进程。“抢占式”则相 反，一旦就绪队列中的某个进程优先数大于正在执行的

15、进程，立刻进行进程切换。基于优先级的调度算法可以分为如下两种类型：静态优先级调度算法,这种调度算法给那些系统中得到运行的所有进程都静态地分配一个优先级;动态优先级调度算法,这种调度算法根据任务的资源需求来动态地分配任务的优先级，其目的 就是在资源分配和调度时有更大的灵活性。本实验的基本要求是实现固定优先数 的调度算法，实验者可以在这个基础上添加动态优先数功能。时间片轮转（RR）调度算法前几种算法主要用于批处理系统中，不能作为分时系统中的主调度算法，在分 时系统中，都采用时间片轮转法。简单轮转法：系统将所有就绪进程按F/F。规 则排队，按一定的时间间隔把处理机分配给队列中的进程。这样，就绪队列中

16、所 有进程均可获得一个时间片的处理机而运行。时间片用完，调度程序自动停止该 进程的执行，将它放到进程就绪队列的末尾，等待下一次执行，然后将处理机分 配给就绪队列中新的队首进程，也让它执行一个时间片。重复这个过程，直到所 有的进程执行完毕。2.衡量算法性能的参数下面引入两个衡量调度算法性能的参数。设作业的提交时间为tsi,执行时间为土片，作业完成时间为亡。i,则作业Ji的周转时间77和周转系数Wi可定义为Ti=toi-tsL i二工2)八1 nn =1 VJi-Ti/tn, i=l,2,M1 nw =zwn谆|平均带权周转时间：3 .实验内容(1)编程实现本实验的程序，要求：1 .建立进程的进程

17、控制块，进程控制块至少包括：i .进程名称；H进程需要执行时间；iii .进入就绪队列时间；iv .进程执行开始时间s 进程执行结束时间vi.进程的优先数2 .编程实现FCFS算法、优先数调度算法和RR算法。3 .进程及相关信息的输入。这些信息可以直接从键盘上输入，也可以 从文件读取。4 .时间片与时间流逝的模拟。本实验需要对算法的执行计时，程序应 该提供计算时间的方法。一种最简单的方法是使用键盘，比如每敲一次 空格代表一个时间片的流逝。另一种方法是使用系统时钟，对于MC+的MFC型程序，可响应窗口的WM-T/MER消息，对于Borland C/C+程序，可截获WT1CH或WTO2H时钟中断。

18、5 . 一组进程序列执行完毕，打印出结果信息。程序需要计算出每个进 程的开始执行时间、结束时间、周转时间和带权周转时间，并为整个进 程序列计算平均周转时间和平均带权周转时间。程序将计算结果按一定的格式显示在计算机屏幕上或输出到文件中。6 .实现数据在磁盘文件上的存取功能。(2)对下列就绪进程序列分别使用上面的几种算法进行调度，计算每种 算法下的平均周转时间和平均带权周转时间。进程号到达时间要求执行时间OO工工工3S22工。3354(Oq5722(Oq3S7IX2382242q13工1472120512233X324221425IS2614.实验步骤I.下面是本实验程序的一个简单实现，请把它输入

19、到计算机里。（已输入，见程序文件PCBCPP）a.调试、运行此程序。m.注意此程序没有最后完成，只有程序的主体结构，有些重要 的函数还没有实现，以空函数的形式出现。请实现这些空函数。iv.调试这些新实现的函数。s 运行整个程序，使用实验内容（2）中数据作为测试，记录 测试结果。vi注意此程序没有任何错误处理能力，如果输入错误的数据怎 么处理？请添加必要的错误处理功能。vii.事实上，本实验的程序可以有多种实现方式，有兴趣的实验 者不妨不依据现有程序，自己独立设计。实验结束后，上交书面实验报告。实验报告内容： 实验题目与要求 总的设计思想，及环境语言、工具等 数据结构与模块说明（功能与框图） 源

20、程序 运行结果与运行情况 自我评析与总结 总的自我打分。 你认为你完成的作业哪些地方做得比较好或比较出色。 差距与局限，什么地方做得不太好，或什么地方可以做得更进一 步的工作。.从本作业得到的收获。对编写与调试过程中经验教训的总结。 完成本题的其他方法。 对实验题的评价和改进意见。5,代码忆。八io.k/KEYEXIT typedef struct ckair ck;char 为(abd;void(关八c)(); MeibdteiDef;void c/cadcrOc。仅 八八八八八八八八八八;int waitkcg。return gctck。;class Me八Def public:ict八C

21、。八t;Menu/temPef i/vc八”24;public:McnuPef()八Co八t=O;public:void 4isp(ag() for(iit i=O;i八Co”八t;i+)coutnHmenui.chn.nmenui.labelendl;coutnnKEY_EXITn.nnExitncndl; void run() int ch;do clearscr();displayO;ch=waitkey ();for(int i=0;i; 是否空白 PCBint IsFinish() return tmSumtmCPU;是否执行完毕void Run() tmSum+;执行一个时间片(段

22、)void SetNull()/name0=0；tmCPU=tmArrive=tmEnd=tmSum=priority=0;nPointer=-l;double T() return tmEnd-tmArrive; 周转时间double Ti()return (tmEnd-tmArrive)* 1.0/tmCPU; 带权周转时间 public:friend istream& operator(istream& stream,PCB &b)return stream;friend ostream& operator(ostream& stream,PCB &b) return stream;);

23、class Kernel public:Kernel() SetNull();public:调度算法ID定义时钟是否允许抢占CPU 0：否1：是调度算法ID进程控制块数组运行、就绪、等待队列的头指针/主程序/输入新的进程信息/是否所有进程已经执行完毕enum kFCFS=0,kPriority,kRR;int tmClick;int bGrab;int nAlgID;PCB pcbs32;int queRun,queRead,queWait;public:void Run();void Process();int IsFinish();void SetAlgorithm(int kAlgld)

24、 nAlgID=kAlgId;行时间。换言之，系统能在给定的时间内响应所有用户的请求。二、核心算法流程图1 .先来先服务算法流程图2 .短进程优先算法void SetNull() tmClick=bGrab=O;nAlgID=kFCFS;queRun=queRead=queWait=-l;for (int i=0;isizeof(pcbs)/sizeof(pcbs0);i+) pcbsi.SetNull();)；/ functions should by implemented int New2Ready(int tmClick) return 1; 将新进程状态转换为就绪状态void Cre

25、ate(PCB &pcb) void Terminate(int pid) void FCFS() void PriorityO void RR() void Schedule() void Display()void DisplayAlgO void Input() double T() doubleTi() 创建新进程终止进程的执行/先来先服务调度算法优先权调度算法时间片轮转调度算法调度程序/显示状态信息/显示算法执行信息/输入所有信息/平均周转时间平均带权周转时间public:friend istream &operator(istream &stream, Kernel &k) ret

26、urn stream; friend ostream &operator(ostream &stream,Kernel &k) return stream;）；int Kemel:IsFinish() for(int i=0;i=0) pcbsqueRun.Run();/运行一个时间段if(pcbsqueRun.IsFinish() Terminate(queRun);Schedule(); else if (nAlgID=kRR)Schedule();)int bNew=New2Ready( tmClick);有新进程进入就绪队列？if(bNew& bGrab)Schedule();Disp

27、layAlgO;tmClick+;)/MenuDef menu;Kernel kernel;/call-back functions for menuvoid input() clearscr();kernel.SetNull();kernel.InputQ;void process() clearscr();kernel.Process();)void display() clearscr();kernel.DisplayO;)void setalg 1 () kernel.SetAlgorithm(Kernel:kFCFS);void setalg2() kernel.SetAlgorit

28、hm(Kernel:kPriority);)void setalg3()kernel.SetAlgorithm(Kernel:kRR);void run()clearscrQ;kernel.Run();void load()char fname128;coutnn Load From file:;cinfname;ifstream inFile;inFile.open(fname);kernel.SetNull();inFilekernel;)void save()char fname128;coutnSave to file:；cinfname;ofstream outFile;outFil

29、e.open(fname);outFilekernel;)void main(int args,char *argv)menu.add(T,Input from key board,input);menu.add(2JInput process,process);menu.add(13nSet Algorithm l:FCFSn,setalg 1);menu.add(4,Set Algorithm 2:Priorityn,setalg2);menu.add(5,Set Algorithm 3:RRH,setalg3);menu.addCVisplay1*,display);menu.add(7

30、nRunH,run);menu.add(,8nLoad from filen,load);menu.add(9JSave to filen,save);menu.run();3 .时间片轮转算法4 .高响应比优先算法首先进行第一个进程计算剩余进程的响应比按优先级排序运行优先级最高的进程结束四、源代码下面给出的是用C实现程序的源代码：#include#include #include typedef struct pcb int name;int needtime;int arrivetime;int pri;int state;int cputime;plist;void action(pli

31、st * nowpro);void action(plist * nowpro) (delay(lOOO);printf(Hnow is process %d n,nowpro-name);nowpro-needtime;if(nowpro-needtime=0) (printf(u the process %d is endn,nowpro-name);/* nowpro-state= 1; */printf(nnn);) else (printf(process %d needtime is %dnn,nowpro-name,nowpro-needtime); printf(unn);)v

32、oid creatpro(int n,plist * process )intj;for(j=0;jn;j+)process1.name二 j;process j . needtime=rand()% 10+1;processj.arrivetime=rand()% 10;processj.pri=rand()%4;processj.state=0;process j J.cputime=0;)void show( int n,plist * process)(intj;for (j=0 ；jn;j+)(printf(Hname of process%dtn,processj.name); p

33、rintf(nneedtime %dt,processj.needtime); printf(Harrivetime %dtn,processj.arrivetime);printf(Hpri %dnH,processj.pri);printf(nstate %dtn,processj.state);printf(Hcputime %dn,process1.cputime);)void main()(void creatpro(int n,plist * process );void show( int n,plist * process);void fcfs(int n,plist * pr

34、ocess);void sjf(int n,plist * process);void rr(int n,plist * prol);void hrrn(int n,plist * prol);int n; /*the number of process*/int k;plist processl 10;printf(nplease input the number of process from 0 to 10nn);scanf(H%dn,&n);creatpro(n,process);show(n,process);printf(nplease choose the what you wa

35、nt to usenn);printf(nl FCFSt 2 SJFt 3 HRRNt 4 RRnn);scanf(u%dn,&k);switch(k)case 1:fcfs(n,process);break;case 2: sjf(n,process);break;case 3: hrrn(n,process);break;case 4: rr(n,process);break;default: break;getch();)void fcfs(int n,plist * prol)(void show( int n,plist * process);int i,j,k;int m=0;in

36、t time;plist temp;plist pro210;for(i=0;in;i+4-)(k=0;while(pro 1 k.state= 1)k+;temp二prol k;for(j=k+l;jprol j.arrivetime&prol j.state!=l) (temp=prol j;k=j;)pro2m+=temp;prolk.state=l;)show(n,pro2);for(i=0;i0)(action(&pro2i);void sjf(int n,plist * prol)(void show( int n,plist * process);int i,j,k;int m=

37、0;plist temp;plist pro210;for(i=0;in;i4-+)(k=0;while(pro lk .state二二 1)(k+;)temp=prolk;for(j=k+l;jpro 1 j .needtime&pro l|j . state!=1) (temp=prol j;k=j;)pro2m+=temp;prolk.state=l;)show(n,pro2);for(i=0;i0)action(&pro2i);)void rr(int n,plist * prol)(void show( int n,plist * process);int i,j,k;int m=0

38、;int time;plist temp;plist pro210J;for(i=0;in;i+)k=0;while(prol k.state=l)(k+;)temp=prolkj;for(j=k+l;jpro 1 j.arrivetime&pro 1 j.state!=l) (temp=pro 11;k=j;)pro2m+=temp;prolk.state=l;)show(n,pro2);time=pro20.needtime;for(i=0;in;i+)(if(time0)for(i=0;i0)(action(&pro2i);)time;)void hrrn(int n,plist * p

39、rol)int cal(int a ,plist * pro2);intint curtime=O;plist temp;for(i=0;in;i+)(k=0;while(pro lk .state=l)k+；temp=prolk;m=cal(curtime,&temp);for(j=0;jprolj.pri)(temp=prol j;m=prolj.pri;k=j；)while(prol k.needtime0)(action(&prolk);curtime+;prolk.state=l;)int cal(int a ,plist * pro2)(int pr;if(a-pro2-arrivetime)arrivetime+pro2-needtime)/pro2-needtime;