操作系统 处理机调度 课程设计报告.docx

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

1、中南大学操作系统课程设计报告设计报告题目：处理机调度模拟程序 学院：信息科学与工程学院专业：电子信息0802姓名：王昊学号：学09080925 指导教师：张晓 完成时间：2011年7月12日Prtl()结束四.操作截图:主界面设计：（1,2,3算法4退出）K：S作系统课程设HSb理机选良.exeCOMPUTER OS BORKBy wanghao(Class 2 c Hoose one oF f o Ho v/in sr :1-PRIORITY.2.ROUNDROBIN.3-SHORTTASK-4 . EX I T - please enter* yom cHo ice ;七工算法L动态优先级

2、算法算法2：时间片轮转法算法3：短作业优先法s五.程序源代码#include #include #include #include typedef struct node(char name10;int prio;int round;int cputime;int needtime;int count;char state;struct node *next;PCB;PCB *Enish,*ready,*tail,*run;int N;firstin()(run=ready;run-state=R,; ready=ready-next;)int timesj(void)(int i,xt;ti

3、me 11;srand(unsigned) time(&t);xt 二 rand() % 10 +1;return xt;void prt l(char a)(if(toupper(a)=,r)printf(n name cputime needtime priority statenn);elseif(toupper(a)=21)printf(n name cputime needtime priority statenn);elseprintf(H name cputime needtime priority statenH); )void prt2(char a,PCB *q)(if(t

4、oupper(a)=,r)printf(n %-l Os%-1 Od%-1 Od%-1 Od %cnn,q-name,q-cputime,q-needtime,q-prio,q-state);elseif(toupper(a)=,2,)printf(n %-l Os%-1 Od%-1 Od%-1 Od %cnq-name,q-cputime,q-needtime,q-prio,q-state);elseprintf(n %-lOs%-1 Od%-1 Od%-1 Od %cnH,q-name,q-cputime,q-needtime,q-prio,q-state);)void prt(char

5、algo)(PCB *p;prtl(algo);if(run!=NULL)prt2(algo,run);p = ready;while(p!=NULL)(prt2(algo,p);p=p-next;)p=finish;while(p!=NULL)prt2(algo,p); p=p-next;getch();return;)insert 1(PCB *q)(PCBint b;s=q；pl=ready;r=pl；b=l;while(pl!=NULL)&b) if(p 1 -prio=s-prio) (r=pl;pl=pl-next;)elseb=0;if(r!=pl)r-next=s; s-nex

6、t=pl;)else(s-next=pl; ready=s;)insert2(PCB *p2)(tail-ncxt=p2;tail=p2;p2-next=NULL;) insert3(PCB *q)PCB *pl,*s,*r;int b;s=q；pl=ready;r=pl;b二l；while(pl!=NULL)&b)if(p 1 -needtimeneedtime)(r=pl;pl=pl-next;)elseb=0;if(r!=pl)(r-next=s;s-next=pl;else(s-next=pl;ready=s;)void create 1 (char alg)(PCB *p;int i

7、,time,sjt,priost;char na10;ready=NULL;finish=NULL;run=NULL;printf(nEnter name and time of process。);printf(Hnn);for(i=l;iname,na);p-cputime=O;p-needtime=sjt;p-state=,w,;p-prio=20-sjt;if(ready!=NULL)insert l(p);elsep-next=ready;ready=p;printf(HDisplay Process Of Priority :nH);printf(H-nn);prt(alg);ru

8、n=ready;ready=ready-next;run-state=R,;)void create2(char alg)PCB *p;int i,time,sjt;char na10;ready=NULL;finish=NULL;run=NULL;printf(HEnter name and time of round processnH);printf(n-nn);for(i=l;iname,na);p-cputime=O;p-needtime=sjt;p-round=l;p-state=,w,;p-count=0;p-prio=20-sjt;if(ready!=NULL)insert2(

9、p);else(p-next=ready;ready二p;tail=p;)printf(nDisplay Process Of Roundrobinnn);printf(n-nn);prt(alg);run=ready;ready=ready-next;run-state=R,;)void create3(char alg)(PCB *p;int i,time,sjt;char na10;ready二NULL;finish=NULL;run=NULL;printf(nEnter name and time of processnH);printf(nnn);for(i=l;iname,na);

10、p-cputime=O;p-needtime=sjt;p-state=,w,;p-prio=20-sjt;if(ready!=NULL)insert l(p);elsep-next=ready;ready=p;)printf(HDisplay Process Of Priority :nH);printf(H-nn);prt(alg);run=ready;ready=ready-next;run-state=R;)priority(char alg)(while(run! =NULL)(run-cputime=run-cputime+1; run-nccdtimc=run-nccdtimc-l

11、;run-prio=run-prio-l;if(run-needtime=O) (run-next=finish;finish=run;run-state=,C,;run二NULL;if(ready!=NULL) firstinQ;)elseif(ready! =NULL)&(run-prioprio) (run-state=,W,;insert! (run); firstin();) prt(alg);)roundrun(char alg)(while(run!=NULL)(run-cputime=run-cputime+1;run-needtime=run-needtime-1;run-c

12、ount=run-count+l; run-prio=run-prio-l;if(run-needtime=O) run-next=finish;finish=run;run-state=,C,;run=NULL;if(ready!=NULL) firstin();elseif(run-count=run-round)run-count=0;if(ready!=NULL)(run-state=,W,;insert2(run);firstin();目录一、课程设计题目3二、基本概念及思想3三、部分程序主要流程图9四、操作截图11五、程序源代码12六、心得体会及总结21prt(alg);)shor

13、ttask(char alg)(while(run! =NULL)(run-cputime=run-cputime+l;run-needtime=run-needtime-1;run-prio=run-prio-1;if(run-needtime=O) (run-next=finish;finish=run;run-state=C,;run=NULL;if(ready!=NULL)firstin();)elseif(ready !=NULL)&(run-needtimeready-needtime)(run-state=,W,;insert 1 (run);firstin();) prt(al

14、g);) return;)menu() char algo;printf(nnnCOMPUTER OS WORKnnf);printf(HnnBy wanghao(Class 2) nnnn);printf(n choose one of following:nn);printf(nnl.PRIORITY.nnn);printf(n2.ROUNDROBIN.nnH);printf(n3.SHORTTASK.nnn);printf(n4.EXIT.nnnn);printf(Hn please enter your choice:)； scanf(n%cn,&algo);if(algo= 1)(p

15、rintf(nEnter process numbernn);scanf(d”,&N);create 1 (algo);priority(algo);)elseif(algo=t2,)(printf(HEnter process numbernn);scanf(n%dn,&N);create2(algo);roundrun(algo);)elseif(algo=3)(printf(nEnter process numbernH);scanf(d”,&N);create3 (algo);shorttask(algo);return;)else if(algo=,4,)exit(O);)main(

16、)while(l)(menu();)六.心得体会及总结：处理机调度问题实际上是处理机分配问题。只有那些参与竞争处理机所必须的资源都 已得到满足的进程才能享受竞争处理机的资格，这时它们处于内存就绪状态。这些必须的资 源包括内存、外设及有关数据结构等。作业调度程序必须先调用存储管理、外设管理，分配 资源，让它们能有竞争资格。为了提高资源利用率，一部分在内存中处于就绪、等待状态而短期内不能执行进程、作 业换出内存，所以外存中除了处于后备状态的作业，还有处于就绪状态的作业。这就需要一 定的方法和策略来为这部分作业分配空间。学习完操作系统原理课程后，进行的这次全面的综合训练，通过课程设计，使我更 好地掌

17、握操作系统的原理及实现方法，加深对操作系统基础理论和重要算法的理解，加强学 生的动手能力，并与编程相结合应用于实际中。一.课程设计题目：课题1:理机调度模拟程序：选择一个调度算法，实现处理机调 度。设计目的：在多道程序和多任务系统中，系统内同时处于就绪状 态的进程可能有若干个。也就是说能运行的进程数大于处理机个数。 为了使系统中的进程能有条不紊地工作，必须选用某种调度策略，选 择一进程占用处理机。要求学生设计一个模拟处理机调度算法，以巩 固和加深处理机调度的概念。设计要求：1）进程调度算法包括：时间片轮转法，短作业优先算法，最高响应 比优先算法。2）可选择进程数量3）本程序包括三种算法，可用C

18、语言实现，执行时在主界面选择算 法（可用函数实现），进入子页面后输入进程数及每个进程的运行时 间，每个进程的优先数由随机函数产生且优先数随等待时间而变化， 执行，显示结果。二.基本概念及思想:（1）进程的创建：由系统为某个进程设置一个进程控制块PCB,用于对进程 进行控制和管理。进程任务完成，由系统收回其PCB,该进程便消亡。（2）进程的三种状态：运行、就绪、完成。进程的三种状态可以通过设计三 个链队列来实现：finish为完成队列的头指针，ready为就绪队列的头指针，tail 为循环轮转法队列的尾指针。因为每一时刻，CPU只能运行一个进程，所以运 行队列只有一个run指针指向当前运行进程。

19、（3）进程调度的功能：按照一定的策略从就绪队列的多个进程中选取一个进 程，使其获得CPU而运行。动态优先数调度算法：思想：为每一个进程设一个优先数，它总是把处理机给就绪队列中具有最高优 先级的进程。初始的进程优先数是随机产生的，随着进程的运行对优先数 进行调整，每次运行时都是从就绪队列中选取优先数最大的进程运行，所 以将就绪队列按照优先数的大小从高到低排序，这样，每次取对首进程即 可。将进程按优先数的大小排列在就绪队列中，每次选取就绪队列中优先 权最高的进程首先占用处理机。优先数由随机函数产生进程最初的优先 数。优先数的动态变化：进程每执行一次优先数-1。优先数随着进程的执 行进行调整，每次执

20、行时都从就绪队列中选取优先数最大的进程投入运 行。时间片轮转调度算法：思想：将所有进程按照先来先服务的规则排成一个队列，把CPU分配给就绪队 列的队首进程，并规定它的执行时间（称此时间为时间片），当时间片用 完但并未执行结束时，剥夺该进程的执行，将其链接到就绪队列的队尾, 等待下一次的选择。将就绪队列的队首指针投入运行。短作业优先调度算法（不可剥夺式的）思想：根据估计运行时间的长短，将各个进程排成一个就绪队列（估计运行时间 最短的进程排在队首），每次运行将队首进程投入运行，直到运行结束，将 此进程连接到完成队列的队尾。然后，再将下一个队首进程投入运行，直到 所有的进程都运行完毕。-结束PCB结

21、构体：typedef struct node char name 10;int pid;int prio;int round;int cputime;int runtime;int waittime;intlength;int count;char state;/*进程时间轮转时间片*/*进程的标号*/*优先级*/*时间片*/*进程占用cpu的时间*/*进程运行所用的时间*/*进程的等待时间*/*进程的长度*/*计数器*/*进程的状态*/struct node *next;/*链指针*/PCB ; PCB结构体用于标识进程的创建与撤消。链指针：PCB finish,*ready,*tail,*

22、nin；.Finish：完成队列的首指针，用于标识完成队列；Ready：就绪队列的首指针，用于标识就绪队列；Run：运行队列的首指针，用于标识运行队列；Tail：循环轮转队列的尾指针；2.3 Create 1 (), create2 (), create3 ()分别为创建进程的函数Create 1 ()：按照优先级调度算法创建进程，用户输入进程名及进程所 需的时间后，创建每个进程的PCB,将每个进程的PCB调用函数insertlO按照优先数从高到低排列到就绪队列中。create2 ()：按照时间片调度算法创建进程，用户输入进程名及进程所需 的时间后，创建每个进程的PCB,将每个进程的PCB调用

23、函数insert2 () 将每个进程PCB按照输入的先后顺序插入到就绪队列的末尾。creates ()：按照短作业优先调度算法创建进程，用户输入进程名及进程 所需的时间后，创建每个进程的PCB,将每个进程的PCB调用函数insert3 ()：按照作业估计执行时间的长短从高到低排列到就绪队列中。就绪队列创建好后，将队列当中的第一个PCB变为运行态“R”，将run指针指 向它，ready指针后移，作为就绪队列的新头指针，然后调用调度算法。注意每 个时刻只能有一个进程处于运行态。2.4 insertl ( ), insert2 (), insert3 ()分别为插入函数这三个函数完成的是就绪队列的创

24、建和管理。insertl ()的功能是将未完成且优先数小于其它进程的PCB按进程优先数 的顺序插入到就绪队列中去。insert2 ()的功能是将执行了一个时间片且还未完成的进程的PCB插入到 就绪队列的队尾。inserts ()的功能是将未完成且作业的执行时间小于其它进程的PCB按进 程的作业的执行时间的长短插入到就绪队列中去。2.5 priority ()优先数调度算法假定系统有三个进程，每一个进程用一个进程控制块PCB来代表，进程 控制块的格式为： typedef struct node (int pid;/*进程的标号*/int prio;/* 优先级*/int cputime;/*进程

25、占用cpu的时间*/int runtime;/*进程运行所用的时间*/char state;/*进程的状态*/struct node *next;/*链指针*/PCB;进程名，优先数，进程占用cpu的时间，进程到完成还需的时间，状态进程名：作为进程的标识，假设三个进程的进程名分别为Pl, P2, P3O进程占用cpu的时间；假设进程已经运行的单位时间数，初始值为“0”。优先数：赋予进程的优先数，调度时总是选取优先数大的进程先执行。状态；有三种状态，“就绪”状态，“运行”状态和“完成”状态。三个进程的初 始状态都为“就绪”，用“w”表示，当一个进程运行结束后，它的状态为“完 成，用“F”表示，当

26、一个进程正在占用cpu ,它的状态为“运行”状态。在每次运行所设计的优先数调度程序之前，为每个进程随机确定它的 “优先数”和“要求运行时间”。为了调度方便，把三个进程按随机产生的优先数从大到小连成队列。用一 单元指出队首进程，用指针指出队列的连接情况。优先数调度总是选队首进程运行。采用动态改变优先数的办法，进程每 运行一次优先数就减“1”。而是执行：优先数-1要求运行时间-1进程占用cpu的时间+1, 来模拟进程的一次运行。进程运行一次后，若要求运行时间0,则再将它插入就绪队列（按优先 数大小插入，且置队首标志）；若要求运行时间=0,则把它的状态修改成“完成” （F）,且退出队列。 若“就绪”

27、状态的进程队列不为空，则重复上面（4）和（5）的步骤， 直到所有进程都成为“完成”状态。在设计的程序中有显示或打印语句，能显示或打印每次被选中进程的进程 名以及运行一次后进程队列的变化及状态。为三个进程随机确定一组“优先数”和“要求运行时间”，启动所设计的 处理器调度程序，显示或打印逐次被选中进程的进程名以及进程控制块的动态变 化过程。注意：进程的优先数值越小，则代表其优先权越高。2.6 roundrun 0时间片轮转法调度算法 假定系统有三个进程，每一个进程用一个进程控制块PCB来代表。进程 控制块的格式为：进程名，进程占用cpu的时间，进程到完成还需的时间，时间片，计数器， 状态进程名一一

28、作为进程的标识，假设三个进程的进程名分别是pl, p2, p3o时间片一一时间片轮转循环所需的时间总数。计数器一一对进程执行时间进行计数。进程占用cpu的时间一一假设进程已经运行的单位时间数，初始值为“0”。状态一一有三种状态，“就绪”状态，“运行”状态和“完成”状态。三个进 程的初始状态都为“就绪”，用“w”表示，当一个进程运行结束后，它的状态 为“完成”，用“F”表示，当一个进程正在占用cpu时，它的状态为“运行” 状态。每次运行所设计的时间片轮转调度程序之前，为每个进程任意确定它的 “要求运行时间”。 把三个进程按先来先服务的顺序排成循环队列，用指针指出队列连接情 况。时间片轮转调度总是

29、选择ready指针指示的进程运行。而是执行：进程到完成还需的时间一1进程占用cpu的时间+1计数器+1来模拟进程的一次运行，表示进程已经运行过一个单位的时间。2.7 shortjob 0短作业优先法调度算法假定系统有三个进程，每一个进程用一个进程控制块PCB来代表，进程 控制块的格式为：进程名，进程占用cpu的时间，进程到完成还需的时间，状态进程名一一作为进程的标识，假设三个进程的进程名分别为Pl, P2, P3o进程占用cpu的时间一一假设进程已经运行的单位时间数，初始值为“0”。状态一一有三种状态，“就绪”状态，“运行”状态和“完成”状态。三个进 程的初始状态都为“就绪”，用“w”表示，当

30、一个进程运行结束后，它的状态 为“完成”，用“F”表示，当一个进程正在占用cpu时，它的状态为“运行” 状态。在每次运行所设计的短作业优先调度程序之前，为每个进程任意确定它 的“要求运行时间”。 为了调度方便，把三个进程按任意给定的作业长短进行排序。用一单 元指出队首进程，用指针指出队列的连接情况。每次取对首进程即可。短作业调度总是选队首进程运行。进程每运行一次，要求运行时间-1进程占用cpu的时间+1来模拟进程的一次运行。进程运行一次后，若要求运行时间0,则再将它插入就绪队列(按作 业长短插入，目置队首标志)；若要求运行时间=0,则把它的状态修改成“完成” (F),且退出队列。若“就绪”状态的进程队列不为空，则重复上面(4)和(5)的步骤,直到所有进程都成为“完成”状态。在设计的程序中有显示或打印语句，能显示或打印每次被选中进程的进程名以及运行一次后进程队列的变化及状态。为三个进程随机确定“要求运行时间”，启动所设计的处理器调度程序, 显示或打印逐次被选中进程的进程名以及进程控制块的动态变化过程。2.8 界面设计：主界面：选择调度算法；子界面：输入进程数，进程名及进程所需的时间；利用c语言中的画图函数及清屏函数设计界面。三.部分程序主要流程图:main