linux内核源代码分析-进程管理及调度.ppt

进程管理、调度,进程管理任务进程管理与其他模块的依赖关系进程描述符及任务队列进程的创建(FORK,copy-on-write)线程实现进程的终止进程调度,进程管理的任务,允许进程复制自己（真正作到一个应用多进程）确定哪个进程能够拥有CPU接受中断并将中断导向相应的内核子系统向用户进程发送信号管理时钟硬件 当一个进程结束时，释放其资源动态装载执行模块,进程模块与其他模块的依赖关系在整个内核中的功能位置和源码依赖关系,进程模块与其他模块的依赖关系进程调度模块的内外界面,对用户进程提供了一组简单的系统调用接口；对内核的其他模块提供了丰富的接口功能。,进程模块与其他模块的依赖关系进程调度模块和其他模块的相互依赖关系,内存管理模块：当一个进程被调度的时候，为它建立内存映射。IPC子模块：bottom-half处理使用了其中的信号量队列。文件系统模块：在装载module的时候为进程调度提供实际设备的 访问途径。所有的其他模块都依赖于进程调度模块，因为当要进行硬件访问的时候它们需要CPU挂起用户进程，切换到系统态进行处理。,.,进程描述符及任务队列,分配进程描述符（http:/）预分配描述符（SLAB机制），把动态分配的过程省略掉一部分（不需要频繁调用内存管理响应功能），相当于一种高级缓存，提高效率。最后的操作主要是直接填写结构。,进程描述符的存放PID(为兼容原来的PID为unsigned short,最大32767，可以通过/proc修改设置)获得当前进程描述符的指针（CURRENT宏、专门寄存器）,进程描述符及任务队列,进程状态#define TASK_RUNNING 0（进程是可执行的或正在执行）#define TASK_INTERRUPTIBLE 1（进程睡眠或阻塞，等待某一事件到来中断它）#define TASK_UNINTERRUPTIBLE 2（进程睡眠或阻塞，不能其他进程的信号打断，直接等待硬件条件）#define TASK_ZOMBIE 4（僵尸，呆傻状态，已结束，但其父进程未接到通知，描述符未释放）#define TASK_STOPPED 8（进程停止，接受到SIGSTP信号）#define TASK_SWAPPING 16（进程页面被兑换出内存）,进程描述符及任务队列,进程状态转换图（见书17页）设置当前进程状态（有很多情况会设置进程状态（思考）set_task_state(task,state)）进程的上下文（进程环境：用户、资源等）系统调用时，内核“代表进程”执行，上下文有效进程之间的联系也属进程的环境（INIT为第一个进程，描述符中Parent,Children指针将这种环境连接起来，可以从任一个进程出发遍历系统的所有进程）,进程描述符及任务队列,索引组织形式之一：队列,进程描述符及任务队列,索引组织形式之二：树,进程的创建(FORK,copy-on-write),进程创建过程描述Linux中，进程的创建是通过拷贝已存在进程来实现的。在Linux内核启动的时候，首先由start_kernel()初始化各个系统数据结构，同时生成了和系统共存亡的后台进程：init。init进程通过拷贝自身，产生了若干内核子进程。然后这些进程就可以通过系统调用fork()生成它们的子进程，当然这些子进程的原始数据都是他们的父亲的副本。进程的终止是通过系统调用_exit()实现的。,LINUX中的进程创建FORK()：进程复制自身产生其子进程EXEC()：加载可执行代码模块覆盖自身代码COPY_ON_WRITE：写时copy,进程的创建(FORK,copy-on-write),FORK()FORK（）、VFORK（）、_CLONE()=CLONE()=DO_FORK()(在kernel/fork.c中)=COPY_PROCESS(),并执行dup_task_struct(建内核栈、thread_info、task_struct);检查进程数目限制；描述符设置，以区别于父进程；子进程状态设置为TASK_UNINTERRUPTIBLE copy_flags get_pid 资源引用复制 父子进程平分剩余时间片 返回指向子进程的指针（一般子进程先执行）（注意：此时并未复制代码）,进程的创建(FORK,copy-on-write),EXEC()对应内核中一族函数：execve(),execv(),execlp(),execvp()负责加载可执行的代码，覆盖本进程的代码、数据。,COPY_ON_WRITE：写时copyLINUX的FORK()过程并未为新生成的进程马上复制代码，开始的进程仅仅读共享父进程代码。直到进程第一次要对进程空间有写请求时，再复制代码。这样做的好处：效率高（一般新进程要有自己的代码，第一条就是EXEC()）,进程的创建(FORK,copy-on-write),FORK()应用实例main()pid_tpid;pintf(“this location in parent processn”);if(pid=fork()=0)printf(“this location in child processn”);execlv(.);,进程的创建(FORK,copy-on-write),VFORK()除不拷贝父进程的页表项和FORK（）完全相同。目前已基本不用。体会一下书上20页有关VFORK（）主要过程的描述,线程实现,Linux没有真正的线程（线程与进程的比较）仅仅是进程之间资源直接共享的一种机制通过CLONE时参数实现：请看一下书21页的有关描述（有些参数标明共享打开文件）。相当于实现了线程概念的一部分（资源共享）。内核线程独立运行在内核的标准进程（后面章节再做讨论）,进程的终止,进程运行结束时要释放相应的资源，通过EXIT()调用实现（显式或隐式）EXIT()实现时调用了do_exit()完成以下工作Task_struct中标志成员设为：PF_EXITING调用_exit_mm()调用sem_exit()调用_exit_files(),_exit_fs(),exit_name_space,exit_sighand退出代码替换为EXIT()提供的代码调用Exit_notify()向父进程发信号，（标为ZOOMBIE)调用shedule切换到其他进程,进程的终止,删除进程描述符父进程得知子进程终止的消息后才能删除子进程的描述符。（思考：若父进程异常终止，将会发生什么情况）父进程WAIT()，返回时可以根据代码做相应动作（或者IGNORE），动作完成后真正释放描述符（调用release_task）调用free_uid:进程记数Unhash_process()：删除pidhash中的项同时删除task_list中的项若有trace删除ptrace_list对应项调用put_task_struct释放描述符，（内核栈、threadinfo所占的页、slab高速缓存。,进程调度,抢占式（preemtive）和非抢占式（cooprative）进程调度的策略IO消耗型和CPU消耗型进程UNIX系列的倾向于IO消耗型优先进程的优先级动态优先级（调度程序根据情况增或减其优先数-20-19）时间片长短定义是个很矛盾的事情（默认一个值）LINUX提供可变长的时间片进程抢占LINUX用抢占式调度（一个新的进程进入时，要看优先级别）调度策略的活动（一个编辑程序和一个后台程序比较）,进程调度,调度算法-LINUX调度在2.5以后的实现目标O(1)调度 SMP的可扩展性强化SMP的亲和力（尽量将相关的一组任务分配给一个CPU）加强交互性保证公平对多CPU的支持增强（忙时每个CPU都有进程执行）主要问题：怎样实现了O(1)调度？,进程调度,LINUX围绕以下几个方面对调度算法进行改进运行队列在 2.4 内核中，就绪进程队列是一个全局数据结构，调度器对它的所有操作都会因全局自旋锁而导致系统各个处理机之间的等待，使得就绪队列成为一个明显的瓶颈。在 2.6 中，就绪队列定义为一个复杂得多的数据结构 struct runqueue，并且，尤为关键的是，每一个 CPU 都将维护一个自己的就绪队列，-这将大大减小竞争。1）prio_array_t*active,*expired,arrays2 每个 CPU 的就绪队列按时间片是否用完分为两部分，分别通过 active 指针和 expired 指针访问，active 指向时间片没用完、当前可被调度的就绪进程，expired 指向时间片已用完的就绪进程。每一类就绪进程都用一个 struct prio_array 的结构表示：,进程调度,图中的 task 并不是 task_struct 结构指针，而是 task_struct:run_list，这是一个小技巧，详见下面 run_list 的解释。2.4版本里选择最佳侯选进程是schedule（）进行的（O(n)）,在新的 O(1)调度中，这一查找过程分解为 n 步，每一步所耗费的时间都是 O(1)量级的。prio_array 中包含一个就绪队列数组，数组的索引是进程的优先级（共 140 级，详见下“static_prioqueue 中。调度时直接给出就绪队列 active 中具有最高优先级的链表中的第一项作为候选进程（参见”调度器“），而优先级的计算过程则分布到各个进程的执行过程中进行”属性的说明），相同优先级的进程放置在相应数组元素的链表。为了加速寻找存在就绪进程的链表，2.6 核心又建立了一个位映射数组来对应每一个优先级链表，如果该优先级链表非空，则对应位为 1，否则为 0。核心还要求每个体系结构都构造一个 sched_find_first_bit()函数来执行这一搜索操作，快速定位第一个非空的就绪进程链表。采用这种将集中计算过程分散进行的算法，保证了调度器运行的时间上限，同时在内存中保留更加丰富的信息的做法也加速了候选进程的定位过程。这一变化简单而又高效，是 2.6 内核中的亮点之一。arrays 二元数组是两类就绪队列的容器，active 和 expired 分别指向其中一个。active 中的进程一旦用完了自己的时间片，就被转移到 expired 中，并设置好新的初始时间片；而当 active 为空时，则表示当前所有进程的时间片都消耗完了，此时，active 和 expired 进行一次对调，重新开始下一轮的时间片递减过程,进程调度,struct prio_array int nr_active;/*本进程组中的进程数*/struct list_head queueMAX_PRIO;/*以优先级为索引的 HASH 表，见下*/unsigned long bitmapBITMAP_SIZE;/*加速以上 HASH 表访问的位图，见下*/;,进程调度,2）spinlock_t lock runqueue 的自旋锁，当需要对 runqueue 进行操作时，仍然应该锁定，但这个锁定操作只影响一个 CPU 上的就绪队列，因此，竞争发生的概率要小多了。3）task_t*curr本 CPU 正在运行的进程。4）tast_t*idle 指向本 CPU 的 idle 进程，相当于 2.4 中 init_tasksthis_cpu()的作用。5）int best_expired_prio 记录 expired 就绪进程组中的最高优先级（数值最小）。该变量在进程进入 expired 队列的时候保存。6）unsigned long expired_timestamp 当新一轮的时间片递减开始后，这一变量记录着最早发生的进程耗完时间片事件的时间（jiffies 的绝对值，在 schedule_tick()中赋），它用来表征 expired 中就绪进程的最长等待时间。它的使用体现在 EXPIRED_STARVING(rq)宏上。,上面已经提到，每个 CPU 上维护了两个就绪队列，active 和 expired。一般情况下，时间片结束的进程应该从 active 队列转移到 expired 队列中（schedule_tick()），但如果该进程是交互式进程，调度器就会让其保持在 active 队列上以提高它的响应速度。这种措施不应该让其他就绪进程等待过长时间，也就是说，如果 expired 队列中的进程已经等待了足够长时间了，即使是交互式进程也应该转移到 expired 队列上来，排空 active。这个阀值就体现在EXPIRED_STARVING(rq)上：在 expired_timestamp 和 STARVATION_LIMIT 都不等于 0 的前提下，如果以下两个条件都满足，则 EXPIRED_STARVING()返回真：（当前绝对时间-expired_timestamp）=（STARVATION_LIMIT*队列中所有就绪进程总数+1），也就是说 expired 队列中至少有一个进程已经等待了足够长的时间；正在运行的进程的静态优先级比 expired 队列中最高优先级要低（best_expired_prio，数值要大），此时当然应该尽快排空 active 切换到expired 上来。,进程调度,7）struct mm_struct*prev_mm保存进程切换后被调度下来的进程（称之为 prev）的 active_mm 结构指针。因为在 2.6 中 prev 的 active_mm 是在进程切换完成之后释放的（mmdrop()），而此时 prev 的 active_mm 项可能为 NULL，所以有必要在 runqueue 中预先保留。8）unsigned long nr_running 本 CPU 上的就绪进程数，该数值是 active 和 expired 两个队列中进程数的总和，是说明本 CPU 负载情况的重要参数。9）unsigned long nr_switches 记录了本 CPU 上自调度器运行以来发生的进程切换的次数。10）unsigned long nr_uninterruptible记录本 CPU 尚处于 TASK_UNINTERRUPTIBLE 状态的进程数，和负载信息有关。,进程调度,11）atomic_t nr_iowait记录本 CPU 因等待 IO 而处于休眠状态的进程数。12）unsigned long timestamp_last_tick本就绪队列最近一次发生调度事件的时间，在负载平衡的时候会用到。13）int prev_cpu_loadNR_CPUS记录进行负载平衡时各个 CPU 上的负载状态（此时就绪队列中的 nr_running 值），以便分析负载情况。,进程调度,运行时间片的计算 老版本的LINUX的计算for(系统中的每个任务)重新计算优先级 重新计算时间片 新版本不用这样计算。（见书32页图）1)time_slice 基准值和 counter 类似，进程的缺省时间片与进程的静态优先级（在 2.4 中是 nice 值）相关，使用如下公式得出：MIN_TIMESLICE+(MAX_TIMESLICE-MIN_TIMESLICE)*(MAX_PRIO-1-(p)-static_prio)/(MAX_USER_PRIO-1)代入各个宏的值后，结果如下图所示：,核心将 100139 的优先级映射到 200ms10ms 的时间片上去，优先级数值越大，则分配的时间片越小。和 2.4 中进程的缺省时间片比较，当 nice 为 0 时，2.6 的基准值 100ms 要大于 2.4 的 60ms。,2)time_slice 的变化进程的 time_slice 值代表进程的运行时间片剩余大小，在进程创建时与父进程平分时间片，在运行过程中递减，一旦归 0，则按 static_prio 值重新赋予上述基准值，并请求调度。时间片的递减和重置在时钟中断中进行（sched_tick()），除此之外，time_slice 值的变化主要在创建进程和进程退出过程中：a)进程创建和 2.4 类似，为了防止进程通过反复 fork 来偷取时间片，子进程被创建时并不分配自己的时间片，而是与父进程平分父进程的剩余时间片。也就是说，fork 结束后，两者时间片之和与原先父进程的时间片相等。b)进程退出进程退出时（sched_exit()），根据 first_time_slice 的值判断自己是否从未重新分配过时间片，如果是，则将自己的剩余时间片返还给父进程（保证不超过 MAX_TIMESLICE）。这个动作使进程不会因创建短期子进程而受到惩罚（与不至于因创建子进程而受到奖励相对应）。如果进程已经用完了从父进程那分得的时间片，就没有必要返还了（这一点在 2.4 中没有考虑）。,3）time_slice 对调度的影响在 2.4 中，进程剩余时间片是除 nice 值以外对动态优先级影响最大的因素，并且休眠次数多的进程，它的时间片会不断叠加，从而算出的优先级也更大，调度器正是用这种方式来体现对交互式进程的优先策略。但实际上休眠次数多并不表示该进程就是交互式的，只能说明它是 IO 密集型的，因此，这种方法精度很低，有时因为误将频繁访问磁盘的数据库应用当作交互式进程，反而造成真正的用户终端响应迟缓。2.6 的调度器以时间片是否耗尽为标准将就绪进程分成 active、expired 两大类，分别对应不同的就绪队列，前者相对于后者拥有绝对的调度优先权-仅当active 进程时间片都耗尽，expired 进程才有机会运行。但在 active 中挑选进程时，调度器不再将进程剩余时间片作为影响调度优先级的一个因素，并且为了满足内核可剥夺的要求，时间片太长的非实时交互式进程还会被人为地分成好几段（每一段称为一个运行粒度，定义见下）运行，每一段运行结束后，它都从 cpu 上被剥夺下来，放置到对应的 active 就绪队列的末尾，为其他具有同等优先级的进程提供运行的机会。,优先级计算方法 在 2.4 内核中，优先级的计算和候选进程的选择集中在调度器中进行，无法保证调度器的执行时间，这一点在前面介绍 runqueue 数据结构的时候已经提及。2.6 内核中候选进程是直接从已按算法排序的优先级队列数组中选取出来的，而优先级的计算则分散到多处进行。这一节分成两个部分对这种新的优先级计算方法进行描述，一部分是优先级计算过程，一部分是优先级计算（以及进程入队）的时机。1）优先级计算过程 动态优先级的计算主要由 effect_prio()函数完成，该函数实现相当简单，从中可见非实时进程的优先级仅决定于静态优先级（static_prio）和进程的sleep_avg 值两个因素，而实时进程的优先级实际上是在 setscheduler()中设置的（详见“调度系统的实时性能”，以下仅考虑非实时进程），且一经设定就不再改变。相比较而言，2.4 的 goodness()函数甚至要更加复杂,它考虑的 CPU Cache 失效开销和内存切换的开销这里都已经不再考虑。2.6 的动态优先级算法的实现关键在 sleep_avg 变量上，在 effective_prio()中，sleep_avg 的范围是 0MAX_SLEEP_AVG，经过以下公式转换后变成-MAX_BONUS/2MAX_BONUS/2 之间的 bonus：(NS_TO_JIFFIES(p)-sleep_avg)*MAX_BONUS/MAX_SLEEP_AVG)-MAX_BONUS/2 如下图所示：,再用这个 bonus 去减静态优先级就得到进程的动态优先级（并限制在 MAX_RT_PRIO和MAX_PRIO 之间），bonus 越小，动态优先级数值越大，优先级越低。也就是说，sleep_avg 越大，优先级也越高。2)优先级计算时机优先级的计算不再集中在调度器选择候选进程的时候进行了，只要进程状态发生改变，核心就有可能计算并设置进程的动态优先级：,a)创建进程在wake_up_forked_process()中，子进程继承了父进程的动态优先级，并添加到父进程所在的就绪队列中。如果父进程不在任何就绪队列中（例如它是 IDLE 进程），那么就通过 effect_prio()函数计算出子进程的优先级，而后根据计算结果将子进程放置到相应的就绪队列中。b)唤醒休眠进程核心调用 recalc_task_prio()设置从休眠状态中醒来的进程的动态优先级，再根据优先级放置到相应就绪队列中。c)调度到从 TASK_INTERRUPTIBLE 状态中被唤醒的进程实际上此时调度器已经选定了候选进程，但考虑到这一类型的进程很有可能是交互式进程，因此此时仍然调用 recalc_task_prio()对该进程的优先级进行修正（详见进程平均等待时间 sleep_avg），修正的结果将在下一次调度时体现。d)进程因时间片相关的原因被剥夺 cpu在 schedule_tick()中（由时钟中断启动），进程可能因两种原因被剥夺 cpu，一是时间片耗尽，一是因时间片过长而分段。这两种情况都会调用effect_prio()重新计算优先级，重新入队。e)其它时机这些其它时机包括 IDLE 进程初始化（init_idle()）、负载平衡（move_task_away()，详见调度器相关的负载平衡）以及修改 nice 值（set_user_nice()）、修改调度策略（setscheduler()）等主动要求改变优先级的情况。由上可见，2.6 中动态优先级的计算过程在各个进程运行过程中进行，避免了类似 2.4 系统中就绪进程很多时计算过程耗时过长，从而无法预计进程的响应时间的问题。同时，影响动态优先级的因素集中反映在 sleep_avg 变量上。,进程调度,睡眠和唤醒DECLARE_WAITQUEUE(wait,current);add_wait_queue(q,看书36页图。,进程调度,负载平衡为SMP体系结构的硬件准备为每个CPU单独提供锁和可执行队列函数load_balance()在kernel/sched.c中 主要完成的是进程在处理机等待队列的迁移（37页图）相应的代码看起来比较复杂，主要完成的步骤如下：调用find_busiest_queue从找到的队列中选优先级数组（先过期队列，后活动队列）找有进程且优先级较高的链表找进程（不执行，不在高速缓存中优先），调用pulltask从繁忙队列抽取到当前队列若还不平衡则重复刚才的过程。,进程调度,抢占和上下文切换从一个可执行进程转到另一个可执行进程（定义在sched.c中的context_switch()函数负责处理）调用switch_mm()负责把虚拟进程从一个进程切换到新进程中调用switch_to()(保存、恢复栈信息，寄存器信息)内核提供了一个need_resched标志,进程调度,用户抢占从系统调用返回用户空间时从中断处理程序返回用户空间时内核抢占(LINUX完整地支持，其他UNIX大部分不支持)，抢占的条件（没持有锁）从中断处理程序返回内核空间时内核代码再一次具有可抢占性时显式调用schedule()内核中的任务阻塞,进程调度,实时2.4中SCHED_RR和SCHED_FIFO两种实时调度策略在2.6中未作改变，两类实时进程都会保持在active就绪队列中运行，只是因为2.6内核是可抢占的，实时进程（特别是核心级的实时进程）能更迅速地对环境的变化（比如出现更高优先级进程）做出反应。,进程调度,与调度相关的系统调用见书40-41页,有关2.6的一些变化,LINUX内核2.6的编译,