操作系统课程设计报告 进程调度算法.doc

操作系统课程设计报告题 目: 进程调度算法 Minix操作系统实践 姓 名: * 学 号: * 专 业: 计算机科学与技术 指导教师: * 实验一1实验目的通过优先权法和轮转算法的模拟加深对进程概念和进程调度过程的理解，掌握进程状态之间的切换，同时掌握进程调度算法的实现方法和技巧。2实验内容1用C+语言来实现对n个进程采用优先权优先算法以及轮转算法的进程调度。2每个用来标识进程的进程控制块PCB用结构来描述，包括以下字段：（1）进程标识ID，其中0为闲逛进程，用户进程的标识数为1，2，3。（2）进程优先级Priority，闲逛进程（idle）的优先级为0，用户进程的优先级大于0，且随机产生，标识数越大，优先级越高。（3）进程占用的CPU时间CPUtime，进程每运行一次，累计值等于4。（4）进程总共需要运行时间Alltime，利用随机函数产生。（5）进程状态，0就绪态；1运行态；2阻塞态。（6）队列指针next，用来将多个进程控制块PCB链接为队列。3优先数改变的原则（1）进程在就绪队列中每呆一个时间片，优先数增加1。（2）进程每运行一个时间片，优先数减3。4在调度前，系统中拥有的进程数PCB_number由键盘输入，经初始化后，所有的进程控制块PCB链接成就绪队列。5为了清楚地观察诸进程的调度过程，程序应将每个时间片内的进程的情况显示出来， 3实验步骤n 进程调度的思想（1）当系统空闲（就绪队列为空）时，系统运行闲逛进程，否则运行其他进程，发生变迁1（就绪运行）。（2）在运行进程（包括闲逛进程）的过程中，可能发生变迁2（运行阻塞），即将运行进程插入到阻塞队列（闲逛进程不能被阻塞），可能有其他新的进程创建PCB，还可能唤醒阻塞队列中的某些进程PCB，发生变迁3（阻塞就绪），即从阻塞队列中移出并插入就绪队列中。（3）时间片运行结束后，若进程累计占用CPU时间大于等于进程需要运行的时间，则进程执行结束，释放其PCB。若进程累计占用CPU时间小于进程需要运行时间，发生变迁4（运行就绪），即将当前运行的进程插入就绪队列中。n 程序流程图1 动态优先权的进程调度算法模拟流程创建n个PCB并加入ready_queue中输入开始进程个数n各进程按优先级从高到低排列Yready_queue为空?NRunning=逐个将ready_pc中PCBRunning=idle阻塞running?NYYrunning=idle?N将running从 ready_queue中删除,再将running 加入block_queuebN是否创建新PCB?Y创建新进程并加入到ready_queue中对ready_queue中的进程PCB进行优先级排序随机对block_queue中的进程PCB询问是否要唤醒？Y处理完了吗？NN是否要唤醒？YNY将其从 block_queue队列中删除,再将其加入ready_queue队列中并进行优先级排序2轮转法进程调度算法模拟流程输入开始进程个数n创建n个PCB并加入ready_queue中Yready_queue为空?NRunning=逐个将ready_pc中PCBRunning=idle阻塞running?NYYrunning=idle?N将running从 ready_queue中删除,再将running 加入block_queuebN是否创建新PCB?Y创建新进程并加入到ready_queue中随机对block_queue中的进程PCB询问是否要唤醒？Y处理完了吗？NN是否要唤醒？Y将其从 block_queue队列中删除,再将其加入ready_queue队列中n 程序代码/*以下程序在C+环境调试通过*/#define NULL 0#include #include #includeusing namespace std;/*以下仅列出动态优先权的进程调度算法模拟*/*进程PCB结构*/struct Pcbint ID;/进程标识ID，其中0为闲逛进程，用户进程的标识数为1，2，3int priority;/进程优先级Priority，闲逛进程（idle）的优先级为0，用户进程的优先级大于0，且随机产生，标识数越大，优先级越高。int CPUtime;/进程占用的CPU时间CPUtime，进程每运行一次，累计值等于4int ALLtime;/进程总共需要运行时间Alltimeint State;/进程状态，0就绪态；1运行态；2阻塞态。struct Pcb *next;/队列指针next，用来将多个进程控制块PCB链接为队列;typedef struct Pcb PCB;void init(); /*产生idle进程，输入用户进程数目，调用insert()*/void print(PCB *pcb); /*输出进程属性信息*/void print_init(PCB *pcb); /*输出所有PCB的初始值*/void insert_queue(PCB *queue,PCB *item); /*动态优先权调试算法将item插入到队列中,使得插入后，队列中按照优先级从高到低有序*/void insert_queue1(PCB *queue,PCB *item); /*轮转法将item插入到队列末尾*/void pushback_queue(PCB *queue,PCB *item); /*将item插入到队列的尾部*/void insert(); /*动态优先权的进程调度算法生成进程属性信息，插入进程就绪队列*/void insert1(); /*轮转法的进程调度算法生成进程属性信息，插入进程就绪队列*/void run(PCB *pcb); /*运行进程，随机阻塞进程、产生新进程，插入就绪队列，唤醒阻塞进程*/void run1(PCB *pcb); /*轮转法试运行参数PCB所指的进程*/void block(PCB *pcb); /*调用destroy()，将进程插入阻塞队列*/void wakeup(); /*动态优先权的进程调度算法唤醒进程，插入就绪队列*/void wakeup1(); /*轮转法的进程调度算法唤醒进程，插入就绪队列*/void proc_priority(); /*优先权调度算法模拟*/void proc_loop(); /*轮转法调度算法模拟*/void update(PCB *pcb); /*更新进程信息*/PCB *ready_queue,*block_queue,*idleprocess; /*就绪队列，阻塞队列及闲逛进程指针变量*/void main()int i=0;while(1)cout(n Please select a number (1,2,0) );cout(n 1- priority );cout(n 2- loop);couti;if(i=1)cout(nThis is an example for priority processing:n);init();:proc_priority();else if (i=2)coutnext;cout(n ID priority CPUtime ALLtime Staten);while(temp!=NULL)coutn ID priority CPUtime ALLtime;if (temp-State=0)coutState=1)cout( running);elsecoutnext;/*输出进程属性信息*/void print(PCB *pcb)PCB *temp;temp=pcb;if (pcb-ID=0) cout(ntThe idle process is running!);elsecoutn ID priority CPUtime ALLtime;if (temp-State=0)coutState=1)cout( running);elsecoutnext;while(p!=0 &p-priority=item-priority )q=p;p=p-next;if(p=0)/在队尾插入item-next=0;q-next=item;else/在q之后、p之前插入item-next=p;q-next=item;void insert_queue1(PCB *queue,PCB *item)/轮转法将item插入到队列末尾PCB *p,*q;q=queue;p=q-next;item-next=0;q-next=item;void pushback_queue(PCB *queue,PCB *item)/将item插入到队列的尾部PCB *p,*q;q=queue;p=q-next;while(p!=0 )q=p;p=p-next;item-next=q-next;q-next=item;void sort_queue(PCB *&queue)/对queue中的结点进行排序，按照优先级从大到小PCB *temp=new PCB;temp-next=0;while(queue-next)PCB *p;p=queue-next;queue-next=p-next;:insert_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;newp-CPUtime=0;newp-priority=rand()%3+1;newp-ALLtime=rand()%3+1;newp-next=NULL;:pushback_queue(ready_queue,newp);/将新生成进程插入到就绪队列尾部print(newp);cout readyn);/*轮转法的进程调度生成进程属性信息，插入进程就绪队列,显示进程信息*/void insert1()PCB *newp=0;static long id=0;newp=new PCB;id+;newp-ID=id;newp-State=0;newp-CPUtime=0;newp-ALLtime=rand()%3+1;newp-next=NULL;:pushback_queue(ready_queue,newp);/将新生成进程插入到就绪队列尾部print(newp);cout readyn);/*生成n个进程属性信息，插入进程就绪队列,显示进程信息*/void insert(int n)for(int i=1;inext=0;ready_queue=new PCB;ready_queue-next=0;int i,pcb_number=-1;idleprocess=NULL; /*设置闲逛进程PCB各字段值*/idleprocess=(PCB *)malloc(sizeof(PCB);idleprocess-ID=0;idleprocess-State=0;idleprocess-CPUtime=0;idleprocess-priority=0;idleprocess-ALLtime=1;idleprocess-next=NULL;/闲逛进程放入就绪队列idleprocess-next=ready_queue-next;ready_queue-next=idleprocess; /也可假定初始时系统中只有一个idle进程/输入初始时进程的个数/while (pcb_number0)/coutpcb_number;/cout(n ID priority CPUtime ALLtime State);/for (i=0;ipcb_number;i+)/insert();cout就绪队列初始化成功endl;:print_init(ready_queue);coutState=2; /*将PCB所指进程的状态设置为阻塞*/pcb-CPUtime-=2; /*设进程执行半个时间片单位后被阻塞*/*pcb-next=NULL;*/print(pcb);cout blockedn);/将pcb插入到阻塞队列/按照什么方式插入呢，需要参考唤醒条件/因为是随机唤醒一个进程，所以我们就简单地把它放置在阻塞队列的头部pcb-next=block_queue-next;block_queue-next=pcb;void update(PCB *pcb)/就绪队列中进程的优先级均增加1PCB *temp=ready_queue-next;while(temp & temp-next )/就绪队列的最后一个是闲逛进程temp-priority+;temp=temp-next;/*动态优先权调度试运行参数PCB所指的进程*/void run(PCB *pcb) /如果pcb是闲逛进程，则不做处理，再次放入就绪队列ready_queueif(pcb-ID=0):insert_queue(ready_queue,pcb);print(pcb);cout runningn;else/如果不是闲逛进程，则进行如下处理pcb-State=1;/*设置该进程的状态为运行*/pcb-CPUtime+=4;/*累计该进程占用CPU的时间*/pcb-priority=pcb-priority-3; /*每运行一个时间片，其优先数减3*/if(pcb-prioritypriority=1;print(pcb);printf( 变迁1：ready - runningn);if (rand()%3=1 ) /*PCB不是闲逛进程，满足条件则阻塞此进程*/if(pcb-CPUtime-2ALLtime) block(pcb);else/已经执行完毕，应该销毁进程coutendl;coutt the process no IDDestroyCPUtime=pcb-ALLtime)/释放coutendl;coutt the process no IDDestroyID=0):insert_queue1(ready_queue,pcb);print(pcb);cout runningn;else/如果不是闲逛进程，则进行如下处理pcb-State=1;/*设置该进程的状态为运行*/pcb-CPUtime+=4;/*累计该进程占用CPU的时间*/if(pcb-prioritypriority=1;/print(pcb);/ printf( 变迁1：ready - runningn);if (rand()%3=1 ) /*PCB不是闲逛进程，满足条件则阻塞此进程*/if(pcb-CPUtime-2ALLtime) block(pcb);else/已经执行完毕，应该销毁进程coutendl;coutt the process no IDDestroyCPUtime=pcb-ALLtime)/释放coutendl;coutt the process no IDDestroynext=0)/此时没有被阻塞的进程，无所谓唤醒return;PCB *q,*p;/下面遍历阻塞队列，q永远指向p的前驱while(true)q=block_queue;p=q-next;while(p & rand()%20!=1)q=p;p=p-next;if(p!=0)/p就是要唤醒的进程q-next=p-next;break;p-State=0;coutendl;:print(p);coutreadynext=0)/此时没有被阻塞的进程，无所谓唤醒return;PCB *q,*p;/下面遍历阻塞队列，q永远指向p的前驱while(true)q=block_queue;p=q-next;while(p & rand()%20!=1)q=p;p=p-next;if(p!=0)/p就是要唤醒的进程q-next=p-next;break;p-State=0;coutendl;:print(p);coutreadyendl;:insert_queue1(ready_queue,p);/*优先权优先调度算法*/void proc_priority():sort_queue(ready_queue);/对queue中的结点进行排序，按照优先级从大到小PCB *temp=0,*running=0; /*running的PCB指针*/int times;for(times=0;times10;times+)/找到优先级最高的进程，并且从队列中删除cout本次调度前：next; /*running指向就绪队列队首PCB*/ready_queue-next=running-next;coutendl;cout本次调度开始endl;:run(running);coutn本次调度结束。endl;/*轮转法进程调用算法*/void proc_loop()PCB *temp=0,*running=0; /*running的PCB指针*/int times;for(times=0;times10;times+)cout本次调度前：next; /*running指向就绪队列队首PCB*/ready_queue-next=running-next;coutendl;cout本次调度开始endl; :run1(running); coutn本次调度结束。endl;图0 输入实现调度的方法图1 输入1 在动态优先级调度算法下执行图2图3 输入2 在轮转法调度算法下执行图44实验过程中遇到的问题及解决方案对进程调度的思想理解不够深刻，不知道如何实现对进程优先级的排序，以及进程控制块如何配置信息。在翻阅在大量书箱和同学的帮助下，解决了用动态优先级在方法实现进程调度模拟算法。在对C+语言的使用尤其是在编写代码方面很欠缺，在组织语言时出错不断。经过自己的多次修改之后，程序才得以运行。在做轮转法实现的过程中，参考动态优先级在方法，便很容易实现。5课程设计总结通过本次的课程设计，使我能够正确运用操作系统课程中所学的基本理论和知识，加深了对进程调度基本概念的理解，还有让我感受很深的是对C+语言的应用，由于对C+语言在平时运用的不够，在对C+语言的使用尤其是在编写代码方面很欠缺，在组织语言时出错不断。在设计过程中，需要大量的相关资料，为了本次课程设计我在网上和图书馆查阅了大量资料，不断的发现问题、提出问题、解决问题。在编程和调试的过程中，经常会出现意想不到的问题，并非每个问题都可以从相关资料中找到解决方法，有些问题是无法预料到的，这就需要通过自己理性的分析得出问题的解决方案。我还希望我们可以有更多这样的学习机会，使我们的知识体系变的更加牢固。实验二在Windows操作系统上安装Bochs虚拟机。配置Bochs虚拟机，并完成Minix操作系统的运行。1实验目的阅读并理解Bochs虚拟机的基本概念，成功安装Bochs虚拟机。阅读Minix操作系统相关技术资料，理解Minix操作系统的安装过程和Minix操作系统的模块结构，实现Minix操作系统的运行；2实验内容Minix操作系统的安装、运行及退出3实验步骤步骤一、在地址下载Bochs-2.0.2虚拟机软件Bochs-2.0.2.Win32-bin.zip，大小为2.55MB，将其安装在C:bochs-2.0.2目录下（安装目录可以是任意硬盘分区，本处为C盘分区）；步骤二、下载Minix操作系统镜像Minix204.zip，大小为6.84MB，并用WINRAR解压缩软件解压缩镜像文件，将镜像文件复制到C:bochs-2.0.2Minix204目录下；步骤三、配置Minix操作系统的启动文件C:bochs-2.0.2Minix204run.bat，配置内容如下：#设置BXSHARE环境变量SET BXSHARE=C:bochs-2.0.2#将当前目录换到C:Bochs-2.0.2minix204cd C:Bochs-2.0.2minix204#使用当前目录下的minix.bxrc配置文件运行bochs.bochs -q -f minix.bxrc步骤四、在C:b