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

《进程调度算法操作系统课程设计.pdf》由会员分享，可在线阅读，更多相关《进程调度算法操作系统课程设计.pdf（25页珍藏版）》请在淘文阁 - 分享文档赚钱的网站上搜索。

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

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

3、应将每个时间片内的进程的情况显示出来。三、实验步骤1、进程管理程序调式好后，运行进程管理程序操作系统课程设计3 Y N N Y Y N N Y Y N N Y ready-queue 是否为将 Running 从 ready_queue中删除，再将 running 加入 block_queueb 将其从 blick_queuek 队列是中删除，再将其加入ready_queuek 输入开始进程数n 随机对 block_queue 中的进程PCB 询问是否要唤醒？创建新进程并加入到ready_queue中Running 逐个将 redy_pc 中的 PCB 创建 n 个 PCB 并加入 ready

4、queue 中处理完了吗阻塞 Running 是否要唤醒是否创建新PCB Running=idle 更新新进程就绪队列进程优先数，优先数加1 Running=id 操作系统课程设计4 2、优先权调度（1）输入 1 选择优先权调度算法模拟。（2）输入开始进程个数n，创建 n 个 PCB并加入就绪队列 ready_queue 中。（3）就绪队列 ready_queue 不为空，调度就绪队列中第一个进程运行，否则，从闲逛队列idleprocess中调度闲逛进程运行。（4）在运行过程中，当遇到阻塞，则该进程插入到阻塞队列block_queue中，且将该进程从ready_queue 中删除。（5）如果运

5、行时间CPUtime大于等于 Alltime，该进程运行完毕，释放该进程；否则插入到就绪队列中。（6）更新就绪队列中的优先级数。（7）随机对阻塞队列block_queue 中的进程 PCB询问是否要唤醒，唤醒，即从唤醒队列中选择第一个进程，且插入就绪队列中；阻塞队列中没有阻塞进程返回。（8）重复上述步骤，直到本次调度结束。操作系统课程设计5 3、轮转调度（1）输入 2 选择优先权调度算法模拟。（2）输入开始进程个数n，创建 n 个 PCB并加入就绪队列 ready_queue 中。（3）就绪队列 ready_queue 不为空，调度就绪队列中第一个进程运行，否则，从闲逛队列idleproces

6、s中调度闲逛进程运行。（4）在运行过程中，当遇到阻塞，则该进程插入到阻塞队列block_queue中，且将该进程从ready_queue 中删除。（5）如果运行时间CPUtime大于等于 Alltime，该进程运行完毕，释放该进程；否则插入到就绪队列中。（6）随机对阻塞队列block_queue 中的进程 PCB询问是否要唤醒，唤醒，即从唤醒队列中选择第一个进程，且插入就绪队列中；阻塞队列中没有阻塞进程返回。（7）如果时间到，本次调度结束，否则重复上述步骤，直到本次调度结束。操作系统课程设计6 Y N N Y Y N N Y Y N N Y Y ready-queue 是否为将 Running

7、 从 ready_queue中删除，再将 running 加入 block_queueb 将其从 blick_queuek 队列是中删除，再将其加入ready_queuek 输入开始进程数n 随机对 block_queue 中的进程PCB 询问是否要唤醒？创建新进程并加入到ready_queue中Running 逐个将 redy_pc 中的 PCB 创建 n 个 PCB 并加入 readyqueue 中处理完了吗阻塞 Running 是否要唤醒是否创建新PCB Running=idle Running=id 操作系统课程设计7 四、实验过程中遇到的问题及解决方案1、请仔细阅读动态优先权的进程调

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

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

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

11、he entry point for the console application./#include stdafx.h#include stdio.h#include stdlib.h#include iostream.h#define NULL 0#define false 0#define true 1 bool _state=0;struct PCB int ID;int priority;int CPUtime;int ALLtime;int State;PCB*next;void init();/*产生 idle进程，输入用户进程数目，调用insert()*/void print

12、(PCB*pcb);/*输出进程属性信息*/void print_init(PCB*pcb);/*输出所有PCB的初始值*/void insert();/*生成进程属性信息，插入进程就绪队列*/void Run_priority(PCB*pcb);/*运行进程，随机阻塞进程、产生新进程，插入就绪队列，唤醒阻塞进程*/void block(PCB*pcb);/*调用 destroy()将进程插入阻塞队列*/void wakeup();/*唤醒进程，插入就绪队列*/void proc_priority();/*优先权调度算法模拟*/void Run_loop(PCB*pcb);void proc_

13、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);/*对 queue 中的结点进行排序，按照优先级从大到小*/PCB*ready_queue,*block_queue,*idleprocess;/*就绪队列，阻塞队列及闲逛

14、进程指针变量*/操作系统课程设计9 int main(int 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-loop);cout(n 0-exitn);couti;while(i)if(i=1)cout(n This is a example for priority processing:n);init();proc_priority();else if(i=2)cout(n This is a example for

15、 round robin processing:n);init();proc_loop();else coutPlease select a num in(1,2,0)n;couti;return 0;/输出所有PCB的初始值void print_init(PCB*pcb)PCB*temp=pcb-next;cout(nID priority CPUtime ALLtime State);while(temp!=NULL)操作系统课程设计10 coutnID priority CPUtime ALLtime;if(temp-State=0)coutState=1)cout(running);e

16、lse coutnext;/输出进程属性信息void print(PCB*pcb)PCB*temp;temp=pcb;if(pcb-ID=0)cout(nThe idle peocess id running!);else coutnID priority CPUtime ALLtime;if(temp-State=0)coutState=1)cout(running);else coutnext;while(p!=0&p-priority=item-priority)q=p;p=p-next;if(p=0)item-next=0;q-next=item;操作系统课程设计11 else ite

17、m-next=p;q-next=item;/将 item 插入到阻塞队列的尾部void pushback_queue(PCB*queue,PCB*item)PCB*p,*q;q=queue,p=q-next;while(p!=0)q=p;p=p-next;item-next=q-next;q-next=item;/对 queue 中的结点进行排序，按照优先级从大到小void sort_queue(PCB*&queue)PCB*temp=new PCB;temp-next=0;while(queue-next)PCB*p;p=queue-next;queue-next=p-next;insert

18、_queue(temp,p);queue-next=temp-next;delete temp;/生成进程属性信息，插入进程就绪队列,显示进程信息void insert()PCB*newp=0;static long id=0;newp=new PCB;id+;newp-ID=id;newp-State=0;操作系统课程设计12 newp-CPUtime=0;newp-priority=rand()%3+1;newp-ALLtime=rand()%3+1;newp-next=NULL;pushback_queue(ready_queue,newp);/print(newp);/cout rea

19、dyn);/生成 n 个进程属性信息，插入进程就绪队列，显示进程信息void insert(int n)for(int i=0;inext=0;ready_queue=new PCB;ready_queue-next=0;int i=0,pcb_number=-1;/闲逛进程放入就绪队列idleprocess=NULL;idleprocess=(PCB*)malloc(sizeof(PCB);idleprocess-ID=0;idleprocess-State=0;idleprocess-CPUtime=0;idleprocess-priority=0;idleprocess-ALLtime=

20、0;idleprocess-next=NULL;idleprocess-next=ready_queue-next;/闲逛进程放入就绪队列ready_queue-next=idleprocess;/也可以假定初始时系统中只有一个idle进程/输入初始进程的个数 while(pcb_number0)coutpcb_number;cout(nID priority CPUtime ALLtime Staten);for(;ipcb_number;i+)insert();操作系统课程设计13 cout*就绪队列初始化成功endl;:print_init(ready_queue);coutState=

21、2;pcb-CPUtime-=2;if(pcb-CPUtimeCPUtime+=2;coutnThe process noID is blocked!;print(pcb);cout blockedn);pcb-next=block_queue-next;block_queue-next=pcb;/更新进程信息,就绪队列中进程的优先级均增加1 void update(PCB*pcb)PCB*temp=pcb-next;while(temp&temp-next)temp-priority+;temp=temp-next;/唤醒进程，插入就绪队列void wakeup()if(block_queu

22、e-next=0)/*此时没有阻塞的进程，无所谓的唤醒*/return;PCB*q,*p;while(true)q=block_queue;p=q-next;while(p&rand()%20!=1)q=p;p=p-next;操作系统课程设计14 if(p!=0)q-next=p-next;break;p-State=0;coutendl;print(p);cout readyID=0)insert_queue(ready_queue,pcb);print(pcb);cout runningn;else pcb-State=1;pcb-CPUtime+=4;pcb-priority=pcb-p

23、riority-3;/*每运行一个时间片，其优先数减3*/if(pcb-priority priority=1;print(pcb);printf(变迁 1:ready-runningn);if(rand()%3=1)/*PCB不是闲逛进程，满足条件侧阻塞此进程*/if(pcb-CPUtime-2ALLtime)block(pcb);else/*已执行完毕，应该销毁进程*/coutn;coutThe process noIDDestroyCPUtime=pcb-ALLtime)/*释放*/coutn;coutThe process no ID DestroryID=0)insert_queue

24、(ready_queue,pcb);print(pcb);cout runningn;else pcb-State=1;pcb-CPUtime=pcb-ALLtime;print(pcb);printf(变迁 1:ready-runningn);if(rand()%3=1)/*PCB不是闲逛进程，满足条件侧阻塞此进程*/_state=1;block(pcb);操作系统课程设计16 else coutn;coutThe process no ID Destroryendl;delete pcb;if(rand()%5=1)insert(3);if(rand()%7=1)wakeup();/优先权

25、调度算法模拟void proc_priority()sort_queue(ready_queue);PCB*temp=0,*running=0;int times=0;cout*调度前:;:print_init(ready_queue);for(;timesnext;ready_queue-next=running-next;coutendl;cout*调度开始 endl;Run_priority(running);coutn*本次调度结束。endl;/轮转调度算法模拟void proc_loop()PCB*temp=0,*running=0;int times=10;coutnext;操作系

26、统课程设计17 ready_queue-next=running-next;cout0)times=times-running-ALLtime;/每次运行一个进程减去ALLtime;if(times=0)Run_loop(running);else if(_state)/如果运行时被阻塞，则运行2 个时间单位 times=times+2;_state=0;cout5487584574389574 fgfgfgfgf gfgfg38954378954375894378954375;else pushback_queue(block_queue,running);/时间不过，则阻塞该进程，放到阻塞

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

28、验内容阅读 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，只要具备运行条件，都处于该状态。Linux 把处于该状态的

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

30、未被释放。处于 TASK_UNINTERRUPTIBLE状态的进程资源有效时被唤醒，也可以通过信号或定时中断唤醒。三、实验步骤1、进程的创建编写一段程序，使用系统调用fork（）创建两个进程。当此程序运行时，在系统中有一个父进程和两个子进程活动。让每个进程在屏幕上显示一个字符：父进程显示字符“A”,子进程分别显示字符“B”和字符“C”。#include void main()int p1,p2;while(p1=fork()=-1);/创建子进程if(p1=0)putchar(b);else 操作系统课程设计20 while(p2=fork()=-1);/创建子进程if(p2=0)putcha

31、r(c);else putchar(a);/父进程 2、进程的控制#include void main()int p1,p2;while(p1=fork()=-1);/创建子进程if(p1=0)for(int i;i10;i+)printf(daugheter%dn,i);else while(p2=fork()=-1);/创建子进程if(p2=0)for(int i;i10;i+)printf(son%dn,i);else for(int i;i10;i+)printf(parent%dn,i);#include#include#include#include#include#include

32、 void main()int fd,spid,ppid;char str80;fd=open(myfile,O_RDWR|O_CREAT,0644);if(cpid=fork()=-1)lseek(fd,0,0);操作系统课程设计21 exit(1);else if(cpid0)lseek(fd,0,0);if(lockf(fd,0,0)=-1)perror(lock failure);exit(1);printf(I am a parent process,my pid is%dn,getid();printf(Please input a string:n);scanf(%s,str);

33、lseek(fd,0,0);write(fd,str,sizeof(str);lseek(fd,0,0);if(lockf(fd,0,0)=-1)perror(unlock failure);exit(1);else sleep(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(unlock failure);exit(1);printf(nI am a p

34、arent process,my pid is%dn,getid();printf(Please input a string:n);printf(%sn,str);操作系统课程设计22 3、软中断通信编制一段程序，使其实现进程的软中断通信。使用系统调度fork（）创建两个子进程，再用系统调用signal（）让父进程捕捉键盘上来的中断信号（即按Del 键）；当捕捉到中断信号后，父进程用系统调用kill（）向两个子进程发出信号，子进程捕捉到信号后分别输出下列信息后中止。Child Process 1 is killed by Parent!Child Process 2 is killed by

35、 Parent!#include#include#include void stop();int wait_mark;void main()int p1,p2,stdout;while(p1=fork()=-1);if(p10)while(p2=fork()=-1);if(p20)wait_mark=1;printf(Input any char to stop:);getchar();kill(p1,16);kill（p2，17）；wait(0);wait(0);printf(Parent process is killed!n);exit(0);else wait_mark=1;signa

36、l(17,stop);while(wait_mark!=0)lockf(stdout,1,0);printf(Child process 2 is killed by parent!n);locf(stdout,0,0);exit(0);操作系统课程设计23 else wait_mark=1;while(wait_mark!=0)lockf(stdout,1,0);printf(Child process 1 is killed by parent!n);lockf(std,0,0);exit(0);void stop()wait_mark=0;4、进程的管道通信编制一段通信，实现进程的管道通

37、信。使用系统调用pipe（）建立一条管道线；两个子进程P1和 P2 分别向管道写一句话：Child1 is senging a message!Child2 is sending a messaga！而父进程则从管道中读出来自于两个子进程的消息，显示在屏幕上。要求父进程先收集子进程P1发来的消息，然后在接受子进程P2 发来的消息。#include#include#include int pid1,pid2;void main()int fd2,n1,n2;char outpipe100,inpipe100;pipe(fd);while(pid1=fork()=-1);if(pid!=0)loc

38、kf(fd1,0,0);sprintf(outpipe,child1 process is sending message!n);write(fd1,outpipe,36);sleep(5);lockf(fd1,0,0);exit(0);操作系统课程设计24 else while(pid2=fork()=-1);if(pid2=0)sprintf(outpipe,child1 process is sending message!n);write(fd1,outpipe,36);sleep(5);lockf(fd1,0,0);exit(0);else wait(0);write(1,inpip

39、e,n1);wait(0);n2=read(fd0,inpipe,50);write(1,inpipe,n2);exit(0);四、实验过程中遇到的问题及解决方案1、系统调用 fork（）可以创建一个新进程，其声明格式为：#include#include Pid_t int fork();调用成功时，该调用对父进程返回子进程的PID，对子进程返回 0.调用失败时，对父进程返回-1，没有创建子进程。2、在对可执行文件加载时进行了加锁和解锁，实现进程间的互斥。函数 lockf用于锁定文件的某些段或者整个文件。3、在进程的控制中，调用fork函数创建一个父进程，用cpid 返回其值，if（cpid0）,父进程的调用。4、进程间用 kill向其他进程发送信号，可以向任何进程或进程组发送任何信号；用 signal接收并设置对信号的处理方法。五、课程设计总结进程描述符即为进程控制块。Linux 的进程控制块由 task_struct结果表示，其结构在 sched.h 里定义。主要进城标识、调度相关信息、进程虚拟空间信息、文件相关信息、信号处理信息、记账信息及统计信息、描述进程间关系的指针等。Linux 中的进程或任务由一个task_struct数据结构表示。操作系统课程设计25 阻塞就绪执行僵死Linux 进程模型：信号信号调度创建时间片到终止