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

进程管理 调度 进程管理任务进程管理与其他模块的依赖关系进程描述符及任务队列进程的创建 FORK copy on write 线程实现进程的终止进程调度 进程管理的任务 允许进程复制自己 真正作到一个应用多进程 确定哪个进程能够拥有CPU接受中断并将中断导向相应的内核子系统向用户进程发送信号管理时钟硬件当一个进程结束时 释放其资源动态装载执行模块 进程模块与其他模块的依赖关系在整个内核中的功能位置和源码依赖关系 进程模块与其他模块的依赖关系进程调度模块的内外界面 对用户进程提供了一组简单的系统调用接口 对内核的其他模块提供了丰富的接口功能 进程模块与其他模块的依赖关系进程调度模块和其他模块的相互依赖关系 内存管理模块 当一个进程被调度的时候 为它建立内存映射 IPC子模块 bottom half处理使用了其中的信号量队列 文件系统模块 在装载module的时候为进程调度提供实际设备的访问途径 所有的其他模块都依赖于进程调度模块 因为当要进行硬件访问的时候它们需要CPU挂起用户进程 切换到系统态进行处理 进程描述符及任务队列 分配进程描述符 http lxr linux no 预分配描述符 SLAB机制 把动态分配的过程省略掉一部分 不需要频繁调用内存管理响应功能 相当于一种高级缓存 提高效率 最后的操作主要是直接填写结构 进程描述符的存放PID 为兼容原来的PID为unsignedshort 最大32767 可以通过 proc修改设置 获得当前进程描述符的指针 CURRENT宏 专门寄存器 进程描述符及任务队列 进程状态 defineTASK RUNNING0 进程是可执行的或正在执行 defineTASK INTERRUPTIBLE1 进程睡眠或阻塞 等待某一事件到来中断它 defineTASK UNINTERRUPTIBLE2 进程睡眠或阻塞 不能其他进程的信号打断 直接等待硬件条件 defineTASK ZOMBIE4 僵尸 呆傻状态 已结束 但其父进程未接到通知 描述符未释放 defineTASK STOPPED8 进程停止 接受到SIGSTP信号 defineTASK SWAPPING16 进程页面被兑换出内存 进程描述符及任务队列 进程状态转换图 见书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 UNINTERRUPTIBLEcopy flagsget 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 thislocationinparentprocess n if pid fork 0 printf thislocationinchildprocess n 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中 就绪队列定义为一个复杂得多的数据结构structrunqueue 并且 尤为关键的是 每一个CPU都将维护一个自己的就绪队列 这将大大减小竞争 1 prio array t active expired arrays 2 每个CPU的就绪队列按时间片是否用完分为两部分 分别通过active指针和expired指针访问 active指向时间片没用完 当前可被调度的就绪进程 expired指向时间片已用完的就绪进程 每一类就绪进程都用一个structprio 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进行一次对调 重新开始下一轮的时间片递减过程 进程调度 structprio array intnr active 本进程组中的进程数 structlist headqueue MAX PRIO 以优先级为索引的HASH表 见下 unsignedlongbitmap BITMAP SIZE 加速以上HASH表访问的位图 见下 进程调度 2 spinlock tlockrunqueue的自旋锁 当需要对runqueue进行操作时 仍然应该锁定 但这个锁定操作只影响一个CPU上的就绪队列 因此 竞争发生的概率要小多了 3 task t curr本CPU正在运行的进程 4 tast t idle指向本CPU的idle进程 相当于2 4中init tasks this cpu 的作用 5 intbest expired prio记录expired就绪进程组中的最高优先级 数值最小 该变量在进程进入expired队列的时候保存 6 unsignedlongexpired 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 structmm struct prev mm保存进程切换后被调度下来的进程 称之为prev 的active mm结构指针 因为在2 6中prev的active mm是在进程切换完成之后释放的 mmdrop 而此时prev的active mm项可能为NULL 所以有必要在runqueue中预先保留 8 unsignedlongnr running本CPU上的就绪进程数 该数值是active和expired两个队列中进程数的总和 是说明本CPU负载情况的重要参数 9 unsignedlongnr switches记录了本CPU上自调度器运行以来发生的进程切换的次数 10 unsignedlongnr uninterruptible记录本CPU尚处于TASK UNINTERRUPTIBLE状态的进程数 和负载信息有关 进程调度 11 atomic tnr iowait记录本CPU因等待IO而处于休眠状态的进程数 12 unsignedlongtimestamp last tick本就绪队列最近一次发生调度事件的时间 在负载平衡的时候会用到 13 intprev cpu load NR 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 代入各个宏的值后 结果如下图所示 核心将100 139的优先级映射到200ms 10ms的时间片上去 优先级数值越大 则分配的时间片越小 和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 函数甚至要更加复杂 它考虑的CPUCache失效开销和内存切换的开销这里都已经不再考虑 2 6的动态优先级算法的实现关键在sleep avg变量上 在effective prio 中 sleep avg的范围是0 MAX SLEEP AVG 经过以下公式转换后变成 MAX BONUS 2 MAX 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 详见