Linux操作系统课程设计

上由也2心与饬SHANGHAI DSANJ1 UNIVERSITY操作系统原理课程设计报告姓 名：吴沛儒班 级：BX0907学 号：9指导老师：胡静二0年十二月十二日目录一、操作系统原理课程设计的目的与要求31、目的32、要求3二、简述课程设计内容、主要功能和实现环境31.课程设计内容3三、任务的分析、设计、实现和讨论31、任务的分析32、任务的设计与实现4五、附录12进程调度一优先数法与简单轮转法一、操作系统原理课程设计的目的与要求1、目的进程是操作系统最重要的概念之一，进程调度又是操作系统核心的主要内容。本实习要 求学生独立地用高级语言编写和调试一个简单的进程调度程序。调度算法可任意选择或自行 设计。任务一采用简单轮转法，任务二采用优先数法等。本课题可以加深对进程调度和各种 调度算法的理解。2、要求(1) 设计一个有n个进程并发的进程调度程序。每个进程由一个进程控制块(PCB)表示。 进程控制块一般应该包含下述信息：进程名、进程优先数、进程需要运行的时间、占用CPU 的时间以及进程的状态等，且可按调度算法的不同而增删。(2) 调度程序应包含2种不同的调度算法，运行时可任意选一种，以利于各种算法的分 析比较。(3) 算法应能显示或打印各个进程的PID、状态(运行状态R、等待状态W等)和参数 (已运行时间等)的变化情况，便于观察诸进程的调度过程进程是操作系统最重要的概念之一，进程调度又是操作系统核心的主要内容。本实习要 求学生独立地用高级语言编写和调试一个简单的进程调度程序。调度算法可任意选择或自行 设计。任务一采用简单轮转法，任务二采用优先数法等。本课题可以加深对进程调度和各种 调度算法的理解。二、简述课程设计内容、主要功能和实现环境1. 课程设计内容进程调度是处理机管理的核心内容。本实验要求用C语言编写和调试一个简单的进程调 度程序。选用优先数法或简单轮转法对五个进程进行调度。每个进程处于运行R(run)、就绪 W(wait)和完成F(finish)三种状态之一，并假设起始状态都是就绪状态可。为了便于处理，程 序进程的运行时间以时间片为单位计算。各进程的优先数或轮转时间片数、以及进程需要运 行的时间片数，均由伪随机数发生器产生。通过本实验可以加深理解有关进程控制块、进程 队列的概念，并体会和了解优先数和时间片轮转调度算法的具体实施办法。2. 主要功能本程序可选用优先数法或简单轮转法对五个进程进行调度。每个进程处于运行R(run)、 就绪W(wait)和完成F(finish)三种状态之一，并假设起始状态都是就绪状态W。为了便于处理， 程序进程的运行时间以时间片为单位计算。3. 实现环境本次课程设计结合算法的特点，采用Windows操作系统平台。开发工具为Microsoft Visual C+6.0O三、任务的分析、设计、实现和讨论1、任务的分析本程序可选用优先数法或简单轮转法对五个进程进行调度。每个进程处于运行R(run)、 就绪W(wait)和完成F(finish)三种状态之一，并假设起始状态都是就绪状态W。为了便于处理， 程序进程的运行时间以时间片为单位计算。各进程的优先数或轮转时间片数、以及进程需要 运行的时间片数，均由伪随机数发生器产生。下面介绍优先数法和简单轮转法两种进程调度算法：(1) 优先数法。进程就绪链按优先数大小从高到低排列，链首进程首先投入运行。每过 一个时间片，运行进程所需运行的时间片数减1，说明它已运行了一个时间片，优先数也减3, 理由是该进程如果在一个时间片中完成不了，优先级应该降低一级。接着比较现行进程和就 绪链链首进程的优先数，如果仍是现行进程高或者相同，就让现行进程继续进行，否则，调 度就绪链链首进程投入运行。原运行进程再按其优先数大小插入就绪链，且改变它们对应的 进程状态，直至所有进程都运行完各自的时间片数。(2) 简单轮转法。进程就绪链按各进程进入的先后次序排列，进程每次占用处理机的轮 转时间按其重要程度登入进程控制块中的轮转时间片数记录项(相当于优先数法的优先数记 录项位置)。每过一个时间片，运行进程占用处理机的时间片数加1，然后比较占用处理机的 时间片数是否与该进程的轮转时间片数相等，若相等说明已到达轮转时间，应将现运行进程 排到就绪链末尾，调度链首进程占用处理机，且改变它们的进程状态，直至所有进程完成各 自的时间片。进程控制块结构如下：进程ID链指针一 优先数/轮转时间片数 占用CPU时间片数 进程所需时间片数 进程状态进程控制块链结构如下:其中：RUN一当前运行进程指针；HEAD-进程就绪链链首指针;TAID-进程就绪链链尾指针。2、任务的设计与实现算法流程图:生成并按优先数大小 排列进程控制块链生成并按进入次序排 列进程控制块链t链首进程投入运行链首进程投入运行时间片到，进程时间片数B 7E减1，优先数减3程时间数为口否否链首进程是时间片到，进程时间片数减 1,占用CFU时间加1先数大链首进程撤销该进程运行进程退出，按优先数插入进程链运行进程退出， 排到进程链尾部撒销该进程从链首取一个 进程投入运行*从链首取一个 A进程投入运行是结束3、操作过程和结果分析优先数调度算法测试数据:优先数调度算法程序运行结果截图:法法 周周羊 .1 -L- - .1 -L-1J 董选 进进符 零应 优篇 .高间.A 曰爵输 2.请J 土海行地、进给调度奂bu gkes he. exeXXXXXXXXXX x j青诜 j 羊要扣!的畀汁 XXXXXXXXXXXXXXXP请输入进程调度个数请输入进程名称1A1请输入进程运行时间请输入进程名称2f!2请输入进程运行时间请输入进程名称3A3请输入进程运行时间请输入进程名称4A4请输入进程运行时间请输入进程名称SA5请输入进程运行时间I- J地、进程调度0北u gkes he. exe最高优先级进程调度模拟：namecput imeneedt imeprioritystateA50149VJA40248VJAl0347VJA20347VJA30446wnamecputimeneedtimeprioritystateA40248RAl0347VJA20347VJA30446VJA51046FnamecputimeneedtimeprioritystateAl0347RA20347VJA30446VJA41145UA51046FnamecputimeneedtimeprioritystateA20347RA30446VJA41145UAl1244UA51046FJ 行地进程调度奂bugkes he. exe豆namecputimeneedtimeprioritystateA30446RA41145UAl1244UA21244UA51046FnamecputimeneedtimeprioritystateA41145RAl1244UA21244UA31343UA51046FnamecputimeneedtimeprioritystateAl1244RA21244UA31343UA42042FA51046FnamecputimeneedtimeprioritystateA21244RA31343UAl2141UA42042FA51046FnamecputimeneedtimeprioritystateA31343RAl2141UA22141UA42042FA51046FJ :庞行地、进程调度De! bu gkes he.exenamecputimeneedtimeprioritystateAl2141RA22141UA32240UA42042FA51046Fnamecput imeneedt imeprioritystateA22141RA32240UAl3038FA42042FA51046FnamecputimeneedtimeprioritystateA32240RA23038FAl3038FA42042FA51046FnamecputimeneedtimeprioritystateA33137RA23038FAl3038FA42042FA51046Fnamecput ime图1.2结果截图stateA34034FA23038FAl3038FA42042FA51046F简单轮转调度算法测试数据:NNNNNNNNNN 可青 j 先 j 羊要=|.1 的畀汁 NNNNNNNNNNNNNNNI进程b u gkes he. exe简单轮转调度算法程序运行结果截图:周周羊 .1 1F - .1 lr1J 进进符 套子 鲁应 高间入 曰秒输 1.2.请岸输入进程调度个数请输入进程名称1A1请输入进程运行时间请输入进程名称2A2请输入进程运行时间请输入进程名称3A3请输入进程运行时间请输入进程名称4A4请输入进程运行时间请输入进程名称SA5请输入进程运行时间图2.1结果截图A3A4图2.2结果截图图2.3结果截图4、思考题的解答和讨论通过以上的调度算法测试数据,得出以下不同算法的不同调度性能结果:一算法比较项（时间轮转法）RR（最高优先数）HRP调度方式抢占式（按时间片）非抢占式响应时间对于短进程提供 良好的响应时间提供良好的响应 时间开销低可能高对待进程的作法公平对待良好的均衡（进程）四、操作系统课程设计小结当我在回首这一个星期的时候，不因虚度光阴而悔恨，也不因碌碌无为而羞耻。我想， 这可能是我一学期中最丰富而有意义的一个星期了。从大一开始我的理论知识就比实践知识好的多，每门课都如此，实训是我最头疼的一件 事。课本上记得很牢的东西到了实际操作的时候感觉都用不上，做个实验就手忙脚乱的。所 以我感觉，这个星期的课设不仅学到了在理论课上学不到的知识，更是让我对自己的实践操 作有了信心。本次课程设计的题目之一是进程调度优先数法与简单轮转法。在多任务系统中，进 程调度是CPU管理的一项核心工作。根据调度模式的不同，多任务系统有两种类型，即非抢 占式和抢占式。其中，优先数法是非抢占式调度策略，而简单轮转法是抢占式调度策略。进 程调度算法是系统效率的关键，它确定了系统对资源，特别是对CPU资源的分配策略，因而 直接决定着系统最本质的性能指标，如相应速度和吞吐量等。常用的调度算法有：先进先出 法，短进程优先法，时间片轮转法（时间片轮转法还分为可变时间片轮转法和简单循环轮转 法），优先级调度法。简单循环轮转法中的时间片q是一个十分重要的因素，它的计算公式为 q=t/n。q的选择对进程调度有很大的影响。q取的太大，轮转法就会退化成先进先出算法；而 取的太小，则会导致系统开销增加，将时间浪费在进程切换上。所以q必须取值适中，使就 绪队列中的所有进程都能得到同样的服务。但我们这次的实验中暂时还没有考虑到时间片q 对算法的影响，只是测试了这个调度策略的算法。这次我们的实验测试并比较了简单轮转法和优先数法这两种调度策略的性能。不同的算 法有它自己不同的长处，简单轮转法虽然能够使每个进程可以以相等的速度向前进展，但对 于紧急进程的处理就显然不及优先数法。可是优先数法的开销较高，而且可能对于较短而且 优先级低的进程会花较长的时间等待。不过它还是具有良好的均衡性。实际应用中，经常是 多种策略结合使用。如时间片轮转法中也可以适当考虑优先级因素，对于紧急的进程可以分 配一个长一点的时间片，或连续运行多个时间片等。这样取长补短，合理利用各种不同算法 的优势，让CPU的运行效率大大提高。人们总是在寻找更好的解决方案，让算法的性能和开销得到一个相对较好的平衡。我在 寻找这样的一个解决方案时，同学对我说虽然老师没有在课上讲过这个策略，但其实书上有 关于更好的调度策略。也就是多级反馈队列调度。这种算法可以先用较小的时间片处理完那 些用时较短的进程，而给那些用时较长的进程分配较大的时间片，以免较长的进程频繁被中 断而影响处理机的效率。这也就是上面所提到的“多种策略结合使用，如时间片轮转法中也 可以适当考虑优先级因素”。温故而知新，可以为师矣。这次编程中所用到的C语言正是我们大一就学过的计算机语 言。在平时的学习中和实训中我们总能用到它。这样反复的运用和考核，让我对C语言的认 识更进了一步。路漫漫其修远兮，吾将上下而求索。我们对操作系统的学习还有很长的路要走，死锁只 是其中的一小部分。重要的是，我在实训的这种里学到了这样的一种精神，一种知难而上， 相信努力和付出能够带来好的结果的精神。这种精神比刻板的知识点更加重要，能够指引我 走向更宽阔的明天。五、附录#include stdio.h”#include stdlib.h”#include string.htypedef struct nodechar name10; /* 进程标识符 */int prio;/*进程优先数*/int round; /*进程时间轮转时间片*/int cputime; /*进程占用CPU时间*/int needtime; /*进程到完成还要的时间*/int count; /* 计数器 */char state; /*进程的状态*/struct node *next; /* 链指针 */PCB;PCB *finish,*ready=NULL,*tail,*run,*pfcfs,*pfcfs1; /* 队列指针*/int N; /*进程数*/*将就绪队列中的第一个进程投入运行*/void firstin()run=ready;/*就绪队列头指针赋值给运行头指针*/run-state=R;/*进程状态变为运行态*/ready=ready-next; /*就绪对列头指针后移到下一进程*/ /*标题输出函数*/void prt1(char a)if(toupper(a)=P) /* 优先数法*/printf(namecputimeneedtimeprioritystaten);else if(toupper(a)=R)printf(namecputimeneedtimecountroundstaten);/*进程PCB输出*/void prt2(char a,PCB *q)if(toupper(a)=P) /* 优先数法的输出 */printf(%-10s%-10d%-10d%-10d%cn”,q-name,q-cputime,q-needtime,q-prio,q-state);else if(toupper(a)=R)/* 轮转法的输出 */printf(%-10s%-10d%-10d%-10d%-10d%-cn”,q-name,q-cputime,q-needtime,q-count,q-roun d,q-state);/*输出函数*/void prt(char algo)PCB *p;prt1(algo); /* 输出标题*/if(run!=NULL) /*如果运行指针不空*/prt2(algo,run); /*输出当前正在运行的PCB*/p=ready; /*输出就绪队列PCB*/while(p!=NULL)prt2(algo,p);p=p-next;p=finish; /*输出完成队列的PCB*/while(p!=NULL)prt2(algo,p);p=p-next;getchar(); /*压任意键继续*/*优先数的插入算法*/void insert1(PCB *q)PCB *p1,*s,*r;int b;s=q; /*待插入的PCB指针*/p1=ready; /*就绪队列头指针*/r=p1; /*r做p1的前驱指针*/b=1;while(p1!=NULL)&b) /*根据优先数确定插入位置*/if(p1-prio=s-prio) r=p1;p1=p1-next;elseb=0;if(r!=p1) /*如果条件成立说明插入在r与p1之间*/r-next=s;s-next=p1;elses-next=p1; /*否则插入在就绪队列的头*/ready=s;/*轮转法插入函数*/void insert2(PCB *p2)tail-next=p2; /*将新的PCB插入在当前就绪队列的尾*/ tail=p2;p2-next=NULL;void insert3()/* 先来先服务 */if (ready=NULL) ready=pfcfs;ready-next=NULL;pfcfs1=pfcfs;elsepfcfs1-next=pfcfs;pfcfs1=pfcfs1-next;/*优先数创建初始PCB信息*/void create1(char alg)PCB *p;int i,time;char na10;ready=NULL; /*就绪队列头指针*/finish=NULL; /*完成队列头指针*/run=NULL; /*运行队列指针*/for(i=1;iname,na);p-cputime=0;p-needtime=time;p-state=w;p-prio=50-time;if(ready!=NULL) /*就绪队列不空调用插入函数插入*/ insert1(p);elsep-next=ready; /*创建就绪队列的第一个PCB*/ ready=p; printf（最高优先级进程调度模拟:n）;printf(*n);prt(alg); /*输出进程PCB信息*/ printf(*n);run=ready; /*将就绪队列的第一个进程投入运行*/ ready=ready-next;run-state=R;/*轮转法创建进程PCB*/ void create2(char alg) PCB *p;int i,time;char na10;ready=NULL;finish=NULL;run=NULL;for(i=1;iname,na);p-cputime=0; p-needtime=time;p-count=0; /* 计数器 */ p-state=w;p-round=2; /*时间片 */ if(ready!=NULL) insert2(p);else p-next=ready; ready=p;tail=p; printf(时间轮转法进程调度模拟n);printf(*n);prt(alg);/*输出进程PCB信息*/ printf(*n);run=ready; /*将就绪队列的第一个进程投入运行*/ ready=ready-next;run-state=R;/*优先数调度算法*/void priority(char alg)while(run!=NULL) /*当运行队列不空时，有进程正在运行*/run-cputime=run-cputime+1;run-needtime=run-needtime-1;run-prio=run-prio-3; /*每运行一次优先数降低3个单位*/if(run-needtime=0) /*如所需时间为0将其插入完成队列*/ run-next=finish;finish=run;run-state=F; /*置状态为完成态*/run=NULL; /*运行队列头指针为空*/if(ready!=NULL) /*如就绪队列不空*/firstin(); /*将就绪对列的第一个进程投入运行*/else /*没有运行完同时优先数不是最大，则将其变为就绪态插入到就绪列*/ if(ready!=NULL)&(run-prioprio)run-state=W;insertl(run);firstin(); /*将就绪队列的第一个进程投入运行*/prt(alg); /*输出进程PCB信息*/*时间片轮转法*/void roundrun(char alg)while(run!=NULL)run-cputime=run-cputime+1;run-needtime=run-needtime-1;run-count=run-count+1;if(run-needtime=0)/*运行完将其变为完成态，插入完成队列*/run-next=finish;finish=run;run-state=F;run=NULL;if(ready!=NULL)firstin(); /*就绪对列不空，将第一个进程投入运行*/elseif(run-count=run-round) /*如果时间片到 */run-count=0; /*计数器置 0*/if(ready!=NULL) /*如就绪队列不空*/run-state=W;/*将进程插入到就绪队列中等待轮转*/insert2(run);firstin(); /*将就绪对列的第一个进程投入运行*/prt(alg); /*输出进程信息*/int check_char(char algo)/*判断输入的字符是否有效*/if (algo=Fllalgo=fllalgo=Rllalgo=rllalgo=Pllalgo=p)return 1;elsereturn 0;/*主函数*/ void main() char algo; /* 算法标记*/int len,h=0;char ch/*接收换行字符*/;printf(n* 请选择要模拟的算法 *nn);printf(1.最高优先数进程调度算法模拟(P/p)n);printf(2 .时间轮转法进程调度算法模拟(R/r)n);printf(请输入相应字符选择nn);scanf(%c”,&algo); /*输入字符确定算法*/if(check_char(algo)/*判断输入的字符是否合法*/printf(请输入进程调度个数n);scanf(%d”,&N); /*输入进程数 */ if(algo=P|algo=p)create1(algo); /* 优先数法*/priority(algo);printf(nn进程已经完成.n);else if(algo=R|algo=r)create2(algo); /*轮转法*/roundrun(algo);printf(nn进程已经完成.n); else if(!check_char(algo) printf(你输入的字符有误，请重新运行程序!”);