C课程设计论文.doc

辽 宁 工 业 大 学 课 程 设 计 说 明 书（论 文）第2章 课程设计内容2.1程序功能介绍在多道程序环境下，进程数目往往多于处理机数目，致使他们争用处理机。这就要求系统能按某种算法，动态地把处理机分配给就绪队列中的一个进程，使之运行。分配处理机的任务是由进程调度程序完成的。一个进程被建立后，系统为了便于对进程进行管理，将系统中的所有进程按其状态，将其组织成不同点进程队列。于是系统中有运行进程队列、就绪队列和各种事件的进程等待队列。进程调度的功能就是从就绪队列中挑选一个进程到处理机上运行。本课题模拟实现进程调度算法，选用了优先数调度算法和时间片轮转算法。2.2程序整体设计说明2.2.1设计思路PCB结构通常包括以下信息：进程名，进程优先数，轮转时间片，进程已占用的CPU时间，进程还需要的CPU时间，进程的状态，当前队列指针等。可根据实验的不同，PCB结构的内容可以作适当的增删。 本程序用两种算法对五个进程进行调度，每个进程可有三个状态：就绪、执行、完成。并假设初始状态为就绪状态。 为了便于处理，程序中的某进程运行时间以时间片为单位计算。各进程的优先数或轮 转时间数以及进程需运行的时间片数的初始值均由用户给定。在优先数算法中，优先数可以先取值为一个常数减去进程所需要的时间片数目，进程每执行一次，优先数减3，CPU时间片数加1，进程还需要的时间片数减1。在轮转算法中，采用固定时间片（即：每执行一次进程，该进程的执行时间片数为已执行了2个单位），这时，CPU时间片数加2，进程还需要的时间片数减2，并排列到就绪队列的尾上。对于遇到优先数一致的情况，采用FIFO策略解决。2.2.2数据结构设计及用法说明 共用体类型：使几个不同的变量占用同一个内存空间的结构类型。结构体：是一种类型。指针：C语言中广泛使用的一种数据类型。nice( ) 改变一个普通进程的静态优先级getpriority( ) 获得一组普通进程的最大优先级setpriority( ) 设置一组普通进程的静态优先级sched_getscheduler( ) 获得一个进程的调度策略sched_setscheduler( ) 设置一个进程的调度策略和实时优先级sched_getparam( ) 获得一个进程的实时优先级sched_setparam( ) 设置一个进程的实时优先级sched_yield( ) 自愿放弃处理器而不阻塞sched_get_ priority_min( ) 获得一种策略的最小实时优先级sched_get_ priority_max( ) 获得一种策略的最大实时优先级sched_rr_get_interval( ) 获得时间片轮转策略的时间片值sched_setaffinity( ) 设置进程的 CPU 亲合力掩码sched_getaffinity( ) 获得进程的 CPU 亲合力掩码2.2.3程序结构（流程图）程序调度流程图如图2.1：图2.1 2.2.4各模块的功能及程序说明真正执行调度的函数是schedule(void)，它选择一个最合适的进程执行，并且真正进行上下文切换，使得选中的进程得以执行。而reschedule_idle(struct task_struct *p)的作用是为进程选择一个合适的CPU来执行，如果它选中了某个CPU，则将该CPU上当前运行进程的need_resched标志置为1，然后向它发出一个重新调度的处理机间中断，使得选中的CPU能够在中断处理返回时执行schedule函数，真正调度进程p在CPU上执行。在schedule()和reschedule_idle()中调用了goodness()函数。goodness()函数用来衡量一个处于可运行状态的进程值得运行的程度。此外，在schedule()函数中还调用了schedule_tail()函数；在reschedule_idle()函数中还调用了reschedule_idle_slow()。这些函数的实现对理解SMP的调度非常重要，下面一一分析这些函数。先给出每个函数的主要流程图，然后给出源代码，并加注释。goodness()函数分析goodness()函数计算一个处于可运行状态的进程值得运行的程度。一个任务的goodness是以下因素的函数：正在运行的任务、想要运行的任务、当前的CPU。goodness返回下面两类值中的一个：1000以下或者1000以上。1000或者1000以上的值只能赋给“实时”进程，从0到999的值只能赋给普通进程。实际上，在单处理器情况下，普通进程的goodness值只使用这个范围底部的一部分，从0到41。在SMP情况下，SMP模式会优先照顾等待同一个处理器的进程。不过，不管是UP还是SMP，实时进程的goodness值的范围是从1001到1099。goodness()函数其实是不会返回-1000的，也不会返回其他负值。由于idle进程的counter值为负，所以如果使用idle进程作为参数调用goodness，就会返回负值，但这是不会发生的。goodness()是个简单的函数，但是它是linux调度程序不可缺少的部分。运行队列中的每个进程每次执行schedule时都要调度它，因此它的执行速度必须很快。/在/kernel/sched.c中static inline int goodness(struct task_struct * p， int this_cpu， struct mm_struct *this_mm) int weight；if (p-；policy ！= SCHED_OTHER) /*如果是实时进程，则*/weight = 1000 + p-；rt_priority；goto out；/* 将counter的值赋给weight，这就给了进程一个大概的权值，counter中的值表示进程在一个时间片内，剩下要运行的时间.*/weight = p-；counter；if (！weight) /* weight=0，表示该进程的时间片已经用完，则直接转到标号out*/goto out；#ifdef _SMP_/*在SMP情况下，如果进程将要运行的CPU与进程上次运行的CPU是一样的，则最有利，因此，假如进程上次运行的CPU与当前CPU一致的话，权值加上PROC_CHANGE_PENALTY，这个宏定义为20。*/if (p-；processor = this_cpu)weight += PROC_CHANGE_PENALTY；#endifif (p-；mm = this_mm) /*进程p与当前运行进程，是同一个进程的不同线程，或者是共享地址空间的不同进程，优先选择，权值加1*/weight += 1；weight += p-；priority； /* 权值加上进程的优先级*/out：return weight； /* 返回值作为进程调度的唯一依据，谁的权值大，就调度谁运行*/schedule()函数分析schedule()函数的作用是，选择一个合适的进程在CPU上执行，它仅仅根据goodness来工作。对于SMP情况，除了计算每个进程的加权平均运行时间外，其他与SMP相关的部分主要由goodness()函数来体现。2.2.5程序结果CHOOSETHEALGORITHM: 1PRIORITY 2ROUNDROBIN 3EXIT 1 inputnameandtime P12 P24 P33 P45 P52 cputime:1 namecputimeneedtimeprioritystate P11145execute P20446ready P30347ready P40545ready P50248ready cputime:2 namecputimeneedtimeprioritystate P11145ready P20446ready P30347ready P40545ready P51145execute cputime:3 namecputimeneedtimeprioritystate P11145ready P20446ready P31244execute P40545ready P51145ready cputime:4 namecputimeneedtimeprioritystate P11145ready P21343execute P31244ready P40545ready P51145ready cputime:5 namecputimeneedtimeprioritystate P12042execute P21343ready P31244ready P40545ready P51145ready cputime:6 namecputimeneedtimeprioritystate P12042finish P21343ready P31244ready P41442execute P51145ready cputime:7 namecputimeneedtimeprioritystate P12042finish P21343ready P31244ready P41442ready P52042execute 若选择了ROUNDROBIN（时间片轮转算法），则进一步显示： CHOOSETHEALGORITHM: 1PRIORITY 2ROUNDROBIN 3EXIT 2 inputnameandtime P15 P23 P34 P46 P58 cpu2 NAMECPUTIMENEEDTIMEROUNDSTATE P1231execute P2030ready P3040ready P4060ready P5080rea NAMECPUTIMENEEDTIMEROUNDSTATE 2.3程序源代码及注释#include stdio.h#include stdlib.h#include string.htypedef struct node char name10; /*进程标识符*/ int prio; /*进程优先数*/ int round; /*进程时间轮转时间片*/ int cputime; /*进程占用CPU时间*/ int needtime; /*进程到完成还要的时间*/ int count; /*计数器*/ char state; /*进程的状态*/ struct node *next; /*链指针*/PCB;PCB *finish,*ready,*tail,*run; /*队列指针*/int N; /*进程数*/*将就绪队列中的第一个进程投入运行*/firstin() run=ready; /*就绪队列头指针赋值给运行头指针*/ run-state=R; /*进程状态变为运行态*/ ready=ready-next; /*就绪对列头指针后移到下一进程*/*标题输出函数*/void prt1(char a) if(toupper(a)=P) /*优先数法*/ printf( name cputime needtime priority staten); else printf( name cputime needtime count round staten);/*进程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/*轮转法的输出*/ printf( %-10s%-10d%-10d%-10d%-10d %-cn,q-name, q-cputime,q-needtime,q-count,q-round,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; getch(); /*压任意键继续*/*优先数的插入算法*/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; else s-next=p1; /*否则插入在就绪队列的头*/ ready=s; /*轮转法插入函数*/insert2(PCB *p2) tail-next=p2; /*将新的PCB插入在当前就绪队列的尾*/ tail=p2; p2-next=NULL;/*优先数创建初始PCB信息*/void create1(char alg) PCB *p; int i,time; char na10; ready=NULL; /*就绪队列头指针*/ finish=NULL; /*完成队列头指针*/ run=NULL; /*运行队列指针*/ printf(Enter name and time of processn); /*输入进程标识和所需时间创建PCB*/ for(i=1;iname,na); p-cputime=0; p-needtime=time; p-state=w; p-prio=50-time; if(ready!=NULL) /*就绪队列不空调用插入函数插入*/insert1(p); else p-next=ready; /*创建就绪队列的第一个PCB*/ready=p; clrscr(); printf( output of priority:n); printf(*n); prt(alg); /*输出进程PCB信息*/ 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; printf(Enter name and time of round processn); 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; clrscr(); printf( output of roundn); printf(*n); prt(alg); /*输出进程PCB信息*/ run=ready; /*将就绪队列的第一个进程投入运行*/ ready=ready-next; run-state=R;/*优先数调度算法*/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;insert1(run);firstin(); /*将就绪队列的第一个进程投入运行*/prt(alg); /*输出进程PCB信息*/ /*时间片轮转法*/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); /*输出进程信息*/ /*主函数*/main() char algo; /*算法标记*/ clrscr(); printf(type the algorithm:P/R(priority/roundrobin)n); scanf(%c,&algo); /*输入字符确定算法*/ printf(Enter process numbern); scanf(%d,&N); /*输入进程数*/ if(algo=P|algo=p) create1(algo); /*优先数法*/ priority(algo); else if(algo=R|algo=r) create2(algo); /*轮转法*/roundrun(algo); 第3章 课程设计总结通过这次课程设计使我懂得了理论与实际相结合是很重要的，只有理论知识是远远不够的，只有把所学的理论知识与实践相结合起来，从理论中得出结论，才能真正为社会服务，从而提高自己的实际动手能力和独立思考的能力。在设计的过程中遇到问题，可以说得是困难重重，这毕竟第一次做的，难免会遇到过各种各样的问题，同时在设计的过程中发现了自己的不足之处，对一些前面学过的知识理解得不够深刻，掌握得不够牢固，比如说结构体，指针通过这次课程设计之后，我们把前面所学过的知识又重新温故了一遍。特别是结构体，指针的部分，几乎是一片空白。不过经过几天的努力，大体上把课本上的知识点看了一遍，知识点也都基本是撑握了，所以一下一步就是开始正式的编程序了。不过毕竟是个新手，还是不知如何下手，于是就在网上下了一篇类似的程序，经过仔细的研究，终于读懂了C语言编程的基本过程和方法。 经过一波三折，终于开始正式编程。开始的时候真的感觉编程是一件很无聊的事情，不过当一个程序运行成功的时候那种喜悦是无法言语的，那种成就感是无法比拟的。又经过几天的努力，终于把程序完成了，尽管程序还是有很多错误和漏洞，不过还是很高兴的。无论如何是自己的劳动成果，是自己经过努力得到的成绩，同时也是学习C语言的一次实践作业，自己进步的证明。通过这次课程设计，使我对C语言有了更进一步的认识和了解，要想学好它要重在实践，要通过不断的上机操作才能