进程调度算法操作系统课程设计

1、计算机科学与应用系操作系统原理课程设计报告题目进程调度算法班级：0510074姓名：lee hve专业：计算机科学与技术指导老师：_hhh操作系统课程设计进程调度算法一、实验目的通过优先权法与轮转调度算法的模拟加深对进程概念和进程调度过程的理 解，掌握进程状态之间的切换，同时掌握进程调度算法的实现方法和技巧。二、实验内容1用C语言或C+语言来实现对N个进程采用优先算法以及轮转算法的进程 调度。2 、每个用来标示进程的进程控制块 PCB用结果来描述，包括以下字段（1）进程标识ID，其中0为闲逛进程，用户进程的标识数为1、2、3、（2）进程优先级Priority ，闲逛进程（idle ）的优先级为

2、0，用户有进 程的优先级大于0,且随机产生，标识数越大，优先级越高。（3）进程占用的CPU时间CPUtime进程每运一次，累积等于4.（4）进程总共需要运行时间 Alltime，利用随机函数产生。（5）进程状态，0就绪态，1 运行态，2阻塞态。（6）队列指针next，用来将多个进程控制块PCB链接为队列。3 、优先数改变的原则（1） 进程在就绪队列中每呆一个时间片，优先数增加1.（2）进程每运行一个时间片，优先数增加 1.4、在调度前，系统中拥有的进程数 PCB_numbe有键盘输入，进初始化后， 所有的进程控制块PCB连接成就绪队列。5、为了清楚的观察诸进程的调度过程，程序应将每个时间片内的

3、进程的情 况显示出来。三、实验步骤1、进程管理程序调式好后，运行进程管理程序3操作系统课程设计4操作系统课程设计输入开始进程数n1创建n个PCB并加入ready queue中=:_ready-queue 是否为nYNTRunnin g<=idRu nnin g< =逐个将redy_pc 中的 PCB1TN阻塞 RunningYRunnin g=idleN将 Running 从 ready_queue 中删除，再将 running 加入 block_queueb更新新进程就绪队列进程优先数，优先数加1是否创建新PCBY创建新进程并加入到ready_queue中随机对block_que

4、ue中的进程PCB询问是否要唤醒?处理完了吗N是否要唤醒将其从blick_queuek队列是中删除，再将其加入ready_queuek5操作系统课程设计2、优先权调度（1）输入1选择优先权调度算法模拟。（2）输入开始进程个数n,创建n个PCB并加入就绪队列ready_queue中。（3）就绪队列ready_queue不为空，调度就绪队列中第一个进程运行，否 则，从闲逛队列idleprocess中调度闲逛进程运行。（4） 在运行过程中，当遇到阻塞，则该进程插入到阻塞队列block_queue 中，且将该进程从ready_queue中删除。（5）如果运行时间CPUtime大于等于Alltime，该

5、进程运行完毕，释放该 进程；否则插入到就绪队列中。（6）更新就绪队列中的优先级数。（7）随机对阻塞队列block_queue中的进程PCB旬问是否要唤醒，唤醒，即从唤醒队列中选择第一个进程，且插入就绪队列中；阻塞队列中没有阻塞进程返回。（8）重复上述步骤，直到本次调度结束。z *Di processDtsibugpEocess- eieleas c sc lcct a nhln ' 1This Jis a example For pi'ioritp process： ingInput the numbei* oF PCB to be start 3ID pr*TL«i

6、i*i1ty CPUt7xnie ALLlr inte Stzalze吐就绪限列初始化成功D priorityI Bi323碉D priorityCPU tineHLLtineState ready ready ready recitlyS ready ready ready ready6操作系统课程设计#操作系统课程设计1143tunn xnsrThe process no 1 if conpletedt 销昱殳running -> Destsrory 期度开始变迁 1 = ready -> lunninrhe process： nu 3 if cumplet-edfrunnxn

7、gi: Funitiriigf -> Destriory开始* ircad. > mnn insf2142runningThe pracess no2 is complelbedlf 销空殳匚 runniinsf>DeEti*oy ”调度开始The idle Docess id runningTiil : peadj/ > running开始变迁 1 = ready -> lunnin:1弓3runninghts process nu 4 if cumplet-edf 乍肖艮殳： Funniiriigf DestriOiry，本次调度结束。leas c selcc

8、t a mLE =3、轮转调度（1）输入2选择优先权调度算法模拟。（2）输入开始进程个数n,创建n个PCB并加入就绪队列ready_queue中。（3）就绪队列ready_queue不为空，调度就绪队列中第一个进程运行，否 则，从闲逛队列idleprocess中调度闲逛进程运行。（4） 在运行过程中，当遇到阻塞，则该进程插入到阻塞队列block_queue 中，且将该进程从ready_queue中删除。（5）如果运行时间CPUtime大于等于Alltime，该进程运行完毕，释放该 进程；否则插入到就绪队列中。（6）随机对阻塞队列block_queue中的进程PCB旬问是否要唤醒，唤醒，即从唤醒

9、队列中选择第一个进程，且插入就绪队列中；阻塞队列中没有阻塞进程返回。（7）如果时间到，本次调度结束，否则重复上述步骤，直到本次调度结束。GFUL jLineCPU time00Q1D priority30调度前=ID ppioity k> 0变迁3L= eady runnjmg变迁i = ready -> runmipff1F1 = ready Funffii iwig口00g "D:processDebugprocess.exeHLLt ime032ALLt ineStateveady r*c chdyState ready renady ready penadyhe

10、id le peocess Id mnn Ing （变迁丄二 ady "> running333he process nol is bluckedf3132Z2he process no 2 if completed?hep护曲te：生雪nu 3 If cornipleiedfrtainningfbilocked.i Funning > blockedFanning- running > Destroryrunn ingr销毁土 runningf Destoi*he idle peocess id r-imning! +1: peadv 一running变迁 1 异

11、 redjy -> ruvuniiog12he process nu4 Is blockedT12ronn ing*blocked变迁running > blocked5487584574389574 fgffffgfgfgfg389S43?89543758943?8954375变迁 1 二 readjy -> runniog311iruinn mg*he pFoiCB&s no 6 if CDimpleitKdfrunnIng' DestiOFy已x四、实验过程中遇到的问题及解决方案1、请仔细阅读动态优先权的进程调度算法的模拟实现代码 ，说明该算法与教 材中

12、介绍的算法做了哪些简单化处理优先权模拟时优先权是随机产生，在实际的系统中，系统进程的优先权高于 一般用户进程的优先权。2、为什么对进程的优先数可按上述原则进行修改 ？最高优先权调度算法仅照顾了优先权高的进程， 当不断有优先权高的进程需 调度时，而优先权低的进程将很难得到处理机的调度， 所以进程在就绪队列中每 呆一个时间片，优先数增加1,使优先权低的进程不总是忙等。3、请给出设计实现的轮转发进程调度算法的设计思想 .时间轮转调度算法：系统将所有的就像进程按先来先服务的原则， 排成一个 队列，每次调度时，把CPU分配给首进程，并令其执行一个时间片。当执行的时 间片用完时，发出中断请求，调度程序便据

13、此信号来停止该进程的执行，并将其 送到就绪队列的末尾，如此反复，就可以保证就绪队列中的所有进程在一个给定 的时间内，均能获得一时间片处理机执行时间。4、在实际的进程调度中，除了按调度算法选择下一个执行的进程外，还应处 理哪些工作？最高优先权调度算法，常用于批处理系统中，作为作业调度算法，也作为多 种操作系统中的进程调度算法，还可以用于实时系统中：时间轮转调度算法，一般用于分时系统中。五、课程设计总结1、当把该算法用于作业调度时，系统将从后备队列中选择若干个优先权最高的作业，装入内存，当用于进程调度算法时，该算法是把处理及分配给就绪队 列中优先权最高的进程。2、当系统空闲（就绪队列为空）时，系统

14、运行闲逛进程，否则运行其他进 程，发生变迁（就绪 运行）3、在运行进程（包括闲逛进程）的过程中，可能发生变迁 2（运行 阻塞），即将运行进程插入到阻塞队列（闲逛进程不能不被阻塞），可能有其他的进程创建PCB还可能唤醒阻塞队列中的某些进程 PCB发生变迁3 （阻塞 就绪），即 从阻塞队列中插入就绪队列中。4、时间片运行结束后，若进程累积占用 CPU时间大于等于进程需要运行时 间，则进程执行结束，释放其 PCB若进程累积占用CPU时间小于进程需要运行 时间，发生变迁4 （运行 就绪），即将当前运行的进程插入就绪队列中。附：进程调度算法代码/ process.cpp : Defines the en

15、try point for the con sole applicati on./#include "stdafx.h"#include "stdio.h"#include "stdlib.h"#i nclude "iostream.h"#defi ne NULL 0#defi ne false 0#defi ne true 1 bool _state=0; struct PCB int ID;int priority; int CPUtime;int ALLtime; int State; PCB* next;v

16、oid init();/* 产生idle进程，输入用户进程数目，调用insert()*/void prin t(PCB *pcb);/*输出进程属性信息 */void print_init(PCB *pcb);/*输出所有 PCB的初始值 */void in sert();/*生成进程属性信息，插入进程就绪队列*/void Run_priority(PCB *pcb);/*运行进程，随机阻塞进程、产生新进程，插入就绪队列，唤醒阻塞进程*/void block(PCB *pcb);/* 调用destroy() 将进程插入阻塞队列 */void wakeup();/*唤醒进程，插入就绪队列 */v

17、oid proc_priority();/*优先权调度算法模拟 */void Runo op(PCB *pcb);void proc_loop();/* 轮转法调度算法模拟 */void update(PCB *pcb);/* 更新进程信息 */void pushback_queue(PCB *queue,PCB *item);/* 将 item 插入到队列的尾部 */void insert_queue(PCB *queue,PCB *item);/*将 item 插入到队列中，使得插入后，队列中按照优先级从高到低有序*/void sort_queue(PCB *&queue);/*对

18、queue中的结点进行排序，按照优先级从大到小*/PCB *ready_queue,*block_queue,*idleprocess;/*就绪队列，阻塞队列及闲逛进程指针变量*/int main (i nt argc, char* argv) int i=0;while(1)cout<<"*PROCESS* */"cout<<("n Please select a num in (1,2,0)"); cout<<("n 1-priority ");cout<<("n 2-lo

19、op ");cout<<("n 0- exitn");cout<<"Please select a nu m:"cin >>i;while(i)if(i=1)cout<<("n This is a example for priority process ing: n "); in it();proc_priority();else if (i=2)cout<<("n This is a example for round rob in process i

20、ng: n "); in it();proc_loop();elsecout<<"Please select a num in (1,2,0)n"cout<<"Please select a nu m:"cin> >i;return 0;/ 输出所有PCB的初始值void print_in it(PCB *pcb)PCB* temp=pcb-> next ;cout<<("nlD priority CPUtime ALLtime State"); while(temp!=

21、NULL)cout<<"n"< <temp_>ID<<""<<temp_>priority<<""<<temp->CPUtime<<" "<<temp->ALLtime;if(temp->State=O)cout<<(" ready");else if(temp->State =1)cout<<(" runnin g");

22、elsecout<<(" blocked");temp=temp->n ext;/ 输出进程属性信息void prin t(PCB *pcb)PCB *temp;temp=pcb;if(pcb->ID=0)cout<<("nThe idle peocess id running!");elsecout<<"n"< <temp_>ID<<""<<temp->priority<<""<&

23、lt;temp->CPUtime<<" "<<temp->ALLtime;if(temp->State=0)cout<<(" ready");else if(temp->State =1)cout<<("runnin g");elsecout<<(" blocked");/ 将item插入到队列中，使得插入后，队列中按照优先级从高到低有序void in sert_queue(PCB *queue,PCB *item)PCB *p,*

24、q;q=queue;p=q _>n ext;while(p!=0&&p->priority>=item->priority)q=p;p=p->n ext;if(p=0)item->next =0;q->n ext=item;elseitem->next =p;q->n ext =item;/ 将item插入到阻塞队列的尾部void pushback_queue(PCB *queue,PCB *item)PCB *p,*q;q=queue,p=q _>n ext;while(p!=0)q=p;p=p->n ext;

25、item->n ext =q->n ext ;q->next =item;/ 对queue中的结点进行排序，按照优先级从大到小void sort_queue(PCB *&q ueue)PCB *temp=new PCB;temp->n ext =0;while(queue->n ext )PCB *p;p=queue->n ext;queue->n ext =p->n ext ;in sert_queue(temp,p);queue->next =temp->n ext ;delete temp;/生成进程属性信息，插入进程就

26、绪队列，显示进程信息void in sert()PCB *n ewp=0;static long id =0;n ewp=new PCB;id+;n ewp->ID =id;n ewp->State=O;newp->CPUtime=O;n ewp_>priority=ra nd()%3+1;newp->ALLtime=ra nd()%3+1;n ewp->n ext =NULL; pushback_queue(ready_queue ,n ewp);print(n ewp);cout<<(”建立：Creating -> ready'

27、n");/ 生成n个进程属性信息，插入进程就绪队列，显示进程信息void in sert(i nt n)for(i nt i=0;i <n ;i+)in sert();/ 产生idle进程，输入用户进程数目，调用insert()void in it()block_queue=new PCB;block_queue->n ext=0;ready_queue=new PCB;ready_queue->n ext=0;int i=0,pcb_ number=-1;闲逛进程放入就绪队列idleprocess=NULL;idleprocess=(PCB *)malloc(si

28、zeof(PCB); idleprocess->ID=0;idleprocess->State=0;idleprocess->CPUtime=0;idleprocess->priority=0;idleprocess->ALLtime=0;idleprocess->n ext=NULL;idleprocess->n ext=ready_queue->n ext;/闲逛进程放入就绪队歹Uready_queue->n ext=idleprocess;/也可以假定初始时系统中只有一个 idle进程/输入初始进程的个数while(pcb_ nu m

29、ber<0)cout<<("I nput the number of PCB to be start:"); cin> >pcb_ nu mber;cout<<("nID priority CPUtime ALLtime State'n");for(;i<pcb_ nu mber;i+)in sert();cout<<"*就绪队列初始化成功 "<<endl;:pri nt_in it(ready_queue);cout<<e ndl;/ 调用d

30、estroy()将进程插入阻塞队列void block(PCB *pcb)pcb->State=2;pcb->CPUtime-=2;if(pcb->CPUtime<=0)pcb->CPUtime+=2;cout<<"nThe process no" <<pcb->ID<<" is blocked!"prin t(pcb);cout<<("变迁 2： running -> blockedn");pcb->n ext=block_queue-&

31、gt;n ext; block_queue->n ext =pcb;/更新进程信息，就绪队列中进程的优先级均增加1void update(PCB *pcb)PCB *temp=pcb-> next; while(temp&&temp->next )temp_>priority+;temp=temp->n ext;/唤醒进程，插入就绪队列void wakeup()if(block_queue-> next=0)/*此时没有阻塞的进程，无所谓的唤醒*/return ;PCB *q,*p;while(true)q=block_queue;p=q _

32、>n ext;while(p&&ran d()%20!=1)q=p;p=p->n ext;if(p!=O)q_>n ext =p->n ext ;break;p->State=O;cout<<e ndl;prin t(p);cout<<" 变迁 3: blocked -> ready"<<endl;in sert_queue(ready_queue,p); 运行进程，随机阻塞进程、产生新进程，插入就绪队列，唤醒阻塞进程void Run_priority(PCB *pcb)if(pcb-&

33、gt;ID=0)in sert_queue(ready_queue,pcb);prin t(pcb);cout<<"变迁 1: ready -> running'n"elsepcb->State=1;pcb->CPUtime+=4;pcb->priority=pcb->priority -3;/*每运行一个时间片，其优先数减3*/if(pcb->priority <1)pcb->priority=1;prin t(pcb);printf(”变迁 1: ready -> running'n ”)

34、；if(ran d()%3=1)/*PCB不是闲逛进程，满足条件侧阻塞此进程*/if(pcb->CPUtime-2<pcb->ALLtime)block(pcb);else/*已执行完毕，应该销毁进程*/cout<<'n'cout<<"The process no"<<pcb->ID<<" is completed! 销毁runnin g->Destroy"<<e ndl;delete pcb;else/*否则看该进程是否执行完毕，如果执行完，则释放

35、，否则再次放入就绪队列*/if(pcb->CPUtime>=pcb->ALLtime)/* 释放 */running ->cout<<'n：cout<<"The process no "<<pcb->ID<<" if completed! 销毁: Destrory"<<e ndl;delete pcb;else:i nsert_queue(:ready_queue,pcb);update(ready_queue);/*更新就绪队列的优先级数*/if(ran

36、d()%5=1)in sert(3);:sort_queue(ready_queue);if(ran d()%7=1)wakeup();/运行进程，随机阻塞进程、产生新进程，插入就绪队列，唤醒阻塞进程void Run_loop(PCB *pcb)if(pcb->ID=0)in sert_queue(ready_queue,pcb);prin t(pcb);cout<<"变迁 1: ready -> runningn"elsepcb->State=1;pcb->CPUtime=pcb->ALLtime;prin t(pcb);prin

37、tf(”变迁 1: ready -> runningn ”)；if(ran d()%3=1)/*PCB不是闲逛进程，满足条件侧阻塞此进程 */_state=1;block(pcb);else销毁:running ->cout<<'n：cout<<"The process no "<<pcb->ID<<" if completed! Destrory"<<e ndl;delete pcb;if(ran d()%5=1)in sert(3);if(ran d()%7=1)w

38、akeup();/优先权调度算法模拟void proc_priority()sort_queue(ready_queue);PCB *temp=0,*ru nnin g=0;int times=0;cout<<"* 调度前:":pri nt_in it(ready_queue);for(;times<5;times+)runnin g=ready_queue->n ext;ready_queue->n ext =running->n ext ;cout<<e ndl;cout<<"* 调度开始"

39、<<endl;Run _priority(r unnin g);cout<<"n* 本次调度结束。"<<endl;/ 轮转调度算法模拟void proc_loop()PCB *temp=0,*ru nnin g=0;int times=10;cout<<"* 调度前:":pri nt_in it(ready_queue);while(1)runnin g=ready_queue->n ext;ready_queue->n ext =running->n ext ;cout<<e

40、 ndl;if(times>0)times=times-ru nnin g->ALLtime;每次运行一个进程减去ALLtime;if(times>=0)Runoop(r unnin g);else if(_state)/如果运行时被阻塞，则运行 2个时间单位times=times+2;_state=0;cout<<"5487584574389574fgfgfgfgfgfgfg38954378954375894378954375"elsepushback_queue(block_queue,ru nnin g);时间不过，则阻塞该进程，放到阻塞

41、队列else if(times<=0)cout<<"n*本次调度时间片到!"break;cout<<"n* 本次调度结束。"<<endl;21操作系统课程设计Linux进程管理一、实验目的进程描述符即为进程控制块。Linux的进程控制块由task_struct结果表示， 其结构在sched.h里定义。主要进城标识、调度相关信息、进程虚拟空间信息、 文件相关信息、信号处理信息、记账信息及统计信息、描述进程间关系的指针等。加深对进程概念的理解，明确进程和程序的区别，进一步认识并发的实质， 通过分析进程争用资源的现象，

42、学习解决进程互斥的方法，了解Linux系统中进 程通信的基本原理。二、实验内容阅读Linux的sched.h源码文件，加深对进程管理概念的理解。阅读 Linux 的fork.c源码文件，分析进程的创建过程。学习Linux系统进行C程序的编译调式方法。GCC是GNU project Cand C+compiler宿写，是C/C+语言的编译器。因其后来可以多种语言的开发，现 在改变为 GNC Compiler Collection 。使用 gcc hello.c-o hello 可以生成执行 的文件hello。Linux的进程状态有五种：TASK_RUNNING行)：无论进程是否正在占用CPU只要

43、具备运行条件，都处于该状态。Linux把处于该状态的所有PCB组织成一个可运行队列run_queue, 调度程序从这个队列只中选择进程运行。TASK_INTERRUPTIBLE可中断阻塞)：Linux 将阻塞态划分成 TASK_UNINTERRUPTIBLETASK_STOPPEDTASK_ZOMBILEE 种不同的状态： TASK_UNINTERRUPTIBL不可中断唤醒)：处于该状态的进程只有当资源有效时 被唤醒，不能通过信号或定时中断唤醒；task_stoppeDT停)：处于该状态的进程只能通过其他进程的信号才能唤醒；TASK_ZOMBILE僵死)：进程已结束但尚未消亡，已经释放了大部分

44、资源，PCB仍未被释放。处于TASK_UNINTERRUPTIBLE 状态的进程资源有效时被唤醒，也可以通过信号或定时中断唤醒。三、实验步骤1、进程的创建编写一段程序，使用系统调用 fork ()创建两个进程。当此程序运行 时，在系统中有一个父进程和两个子进程活动。 让每个进程在屏幕上显示一个字 符：父进程显示字符“ A” ,子进程分别显示字符“ B”和字符“ C”。#i nclude<stdio.h>void mai n()in t p1,p2;while(p1=fork()=-1);/创建子进程if(p1=O)putchar('b');else while(p2

45、=fork()=-1); 创建子进程 if(p2=0)putchar('c');else putchar('a');/ 父进程2、进程的控制#in clude<stdio.h>void mai n()in t p1,p2;while(p 仁fork()=-1);创建子进程if(p1=0)for(int i;i<10;i+)prin tf("daugheter%dn",i);elsewhile(p2=fork()=-1);创建子进程if(p2=0)for(int i;i<10;i+)prin tf("so n%

46、dn",i);elsefor(int i;i<10;i+)prin tf("pare nt%dn",i); #in clude<stdio.h>#in clude< un istd.h>#in clude<sys/wait.h> #i nclude<sys/stat.h>#in clude<sys/types.h>#in clude<fc ntl.h> void mai n()int fd,spid,ppid;char str80;fd=ope n( "myfile"

47、,O_RDWR|O_CREAT,0644);if(cpid=fork()=-1)lseek(fd,0,0);exit(1);else if(cpid>0) lseek(fd,0,0);if(lockf(fd,0,0)=-1)perror("lock failure");exit(1);prin tf("I am a pare nt process,my pid is %dn ",getid();prin tf("Please in put a stri ng: n");sca nf("%s",str);lse

48、ek(fd,0,0);write(fd,str,sizeof(str);lseek(fd,0,0);if(lockf(fd,0,0)=-1)perror("u nlock failure");exit(1);elsesleep(1);lseek(fd,0,0);if(lockf(fd,0,0)=-1)perror("lock failure");exit(1);lseek(fd,0,0);read(fd,str,sizeof(str);lseek(fd,0,0);if(lockf(fd,0,0)=-1)perror("u nlock failu

49、re");exit(1);prin tf("nI am apare nt process,my pid is %dn ",getid();prin tf("Please in put a stri ng:n");prin tf("%sn",str);3、软中断通信编制一段程序，使其实现进程的软中断通信。使用系统调度fork ()创建两个子进程，再用系统调用signal ()让父进程捕捉键盘上来的中断信号(即按 Del键)；当捕捉到中断信号后，父进程 用系统调用kill ()向两个子进程发出信号，子进程捕捉到信号后分别输出下

50、列信息后中止。Child Process 1 is killed by Pare nt!Child Process 2 is killed by Pare nt!#i nclude<stdio.h>#in clude<sig nal.h>#i ncludev un istd.h>void stop();int wait_mark;void mai n()int p1,p2,stdout;while(p1=fork()=-1);if(p1>0)while(p2=fork()=-1);if(p2>0)wait_mark=1;prin tf("I nput any char to stop:");getchar(); kill(p1,16);kill(p2, 17)；wait(0);wait(0);printf(&q