进程调度副本

单击此处编辑母版标题样式,单击此处编辑母版文本样式,第二级,第三级,第四级,第五级,*,1,进程调度,2,进程调度基本概念,多进程系统，多个进程在逻辑上均可运行的情况下，操作系统决定运行哪个进程的操作称为进程调度。,操作系统中作出这种决定和进行调度的部分称作调度程序,(scheduler),。,进行调度的算法称为调度算法,(scheduling algorithm),。,进程调度的基本要求,公平：每个进程应该获得合理的,CPU,份额,有效：使,CPU,百分之百地忙碌,响应时间：使交互用户的响应时间尽可能短,周转时间：使批处理用户等待输出的时间尽可能短,吞吐量：使单位时间内处理的作业数量最多,3,调度算法,时间片轮转法,每个进程被分配一个时间片,时间片长度的确定,优先级调度,不同进程的重要程度不同,动态优先级和静态优先级,多重队列,通过设立优先级类减少进程切换次数,最短作业优先,适用于运行时间可以预知的批作业的调度算法,保证调度算法,可以保证某种性能明确实现,彩票调度算法,进程使用各种资源的机会通过持有的彩票获得,特性：反应迅速，彩票交换,实时调度,在可调度条件下满足各种时间要求,两级调度,分别用于内存中的进程和交换到磁盘上的进程的调度,4,Linux,进程分类,进程分类,交互进程,各种,I/O,操作,鼠标，键盘，串口，磁盘读写，,.,批作业进程,很少或没有,I/O,操作，以,CPU,运算为主,计算程序，图像处理程序，,.,实时进程,有各种严格的时间需求,机器人控制，音视频播放，,.,5,进程状态的转换,阻塞态,运行态,就绪态,6,Preemption,：进程,vs,内核,进程,进程在用户空间运行时可随时被剥夺,进程在内核空间运行时,可剥夺：,Solaris,Mach,.,实时操作系统,不可剥夺：,Linux 2.4,.,非实时操作系统,内核,实时内核,内核过程可以被打断并进行调度,非实时内核,内核过程可以被打断，但不能进行调度。,7,选择时间片大小,进程切换时间决定时间片的基本大小,快速响应和高,CPU,效率是一对相互矛盾的需求,Linux,选择时间片的标准,时间片尽量长,同时保证系统良好的响应时间,8,进程的优先级,优先级,静态优先级,动态优先级,相关参数,进程描述符,int prio,static_prio;,prio_array_t*array;,unsigned long rt_priority;,相关常数,MAX_USER_RT_PRIO,MAX_RT_PRIO,MAX_PRIO,9,nice,值和优先级,对于非实时调度的进程，用户的优先级用变量,nice,表示。,nice,取值范围：,-20-+19,nice,相关操作,NICE_TO_PRIO(nice),PRIO_TO_NICE(prio),TASK_NICE(p),其他操作函数,USER_PRIO(p),TASK_USER_PRIO(p),MAX_USER_PRIO,10,调度的实现方式,直接调度,(direct invocation),进程执行的代码中直接使用,schedule(),进行调度,sleep_on(),wait_event(),.,被动调度,(lazy invocation),当进程的时间片用尽后被系统剥夺运行权利而进行的调度,在系统时钟中断处理函数中进行调度,11,schedule(),进程调度的主要实现函数。进程调度的算法体现在这个函数的实现过程中。,由它来决定是否要进行进程的切换，如果要切换的话，切换到哪个进程等等。,进程调度函数,schedule(),是一个不断改进和变化的函数。进程调度算法一直是操作系统研究的主要课题。,调度函数的效率是首要因素。,针对特定应用可以使用特定的调度算法。,我们基于,Linux 2.4.20,内核研究调度函数。,调度函数的最主要目标是如何确定下一个需要运行的进程。,那么当,我们要执行调度程序,时,，我们把这种情况叫做调度时机。,12,Linux,调度时机,Linux,调度时机主要有：,1,、进程状态转换的时刻：进程终止、进程睡眠；,进程要调用,sleep,（）或,exit,（）等函数进行状态转换，这些函数会主动调用调度程序进行进程调度；,13,2,、进程从中断、异常及系统调用返回到用户态时；,不管是从中断、异常还是系统调用返回，最终都调用,ret_from_sys_call,（）,从系统调用返回意味着要离开内核态而返回到用户态，而状态的转换要花费一定的时间，因此，在返回到用户态前，系统把在内核态该处理的事全部做完。,14,3,、设备驱动程序主动调用,schedule,；,当设备驱动程序执行长而重复的任务时，直接调用调度程序。在每次反复循环中，驱动程序都检查,need_resched,的值，如果必要，则调用调度程序,schedule(),主动放弃,CPU,。,15,4,、当前进程的时间片用完时（,current-counter=0,）；,由于进程的时间片是由时钟中断来更新的，因此，这种情况和时机,2,是一样的。,16,17,进程调度小结,每个进程都有一个优先级,进程的优先级共分成,140,个等级，最高为,0,级，最低为,139,级。,0,到,99,级的进程为实时进程,100,到,139,级的进程为普通进程,优先级的动态变化,实时进程的优先级不会动态变化,普通进程的优先级会随着运行情况而动态变化,但普通进程的优先级最高不会达到实时进程的优先级，即不会小于,100,。,进程运行的时间片由称为静态优先级的参数决定,子进程继承父进程的静态优先级,静态优先级可以通过相关系统调用而改变,调度函数总是选择,active,表中的优先级最高的进程运行,active,表中的进程全部运行完后，互换,active,表和,expired,表,如果整个运行队列中都没有进程等待运行，则选择,idle,进程。,调度函数根据进程的调度策略采用不同的调度算法,只要有实时进程就绪，它永远都会得到运行。,优先级高的进程,-,更快的响应时间,时间片长的进程,-,更多的运行时间,只有在没有实时进程就绪的情况下，普通进程才能得到运行。,18,进程调度相关系统调用,nice(),getpriority(),setpriority(),sched_getscheduler(),sched_setscheduler(),sched_getparam(),sched_setparam(),sched_yield(),