Linux操作系统分析与实践第三讲：进程管理.ppt

Linux操作系统分析与实践 第三讲：进程管理 Linux操作系统分析与实践课程建设小组 北京大学 二零零八年春季 *致谢：感谢Intel对本课程项目的资助 本讲主要内容 Linux中的进程 Linux进程控制 Linux的进程调度 Linux源代码阅读示例: 进程调度schedule部分的阅读 一、Linux中的进程 进程 是程序执行时的一个实例 从内核的观点来看，进程的目的是担当 分配系统资源(CPU 时间，存储器等)的 实体 Linux中的关于进程的代码大部分是如 何管理进程的代码 每个进程运行的是程序的代码 轻量级进程 线程代表进程的一个执行流，内核无法 感知 Linux使用轻量级进程对多线程应用程 序提供更好的支持 轻量级进程可以共享资源 通过将轻量级进程与线程相关联，内核可 以独立调度线程 进程描述符task_struct (include/linux/sched.h ） 进程描述符(续) Task_struct结构的描述： n 进程标识 n 进程状态(State) n 进程调度信息和策略 n 标识号(Identifiers) n 进程通信有关的信息(IPC) n 进程链接信息(Links) n 时间和定时器信息(Times and Timers) n 文件系统信息(Files System) n 处理器相关的上下文信息 进程描述符(续) Linux中每一个进程由一个task_struct 数据结构来描述（进程控制块PCB） 进程描述符放在动态内存中而且和内核 态的进程栈放在一个独立的8KB的内存 区中 好处：通过esp就能引用进程描 述符 current宏 current宏 current宏获取当前正在运行的进程描述符 的指针，current宏经常作为进程描述符出 现在内核代码里，例如current-pid返回当 前正在运行的进程的PID值 进程的状态 task_struct 中的state 表示进程当前的状态 Linux中的进程有5个状态: (include/linux/sched.h) #define TASK_RUNNING0 #define TASK_INTERRUPTIBLE1 #define TASK_UNINTERRUPTIBLE2 #define TASK_ZOMBIE4 #define TASK_STOPPED8 状态之间的转换 进程链表 task_struct中的 struct task_struct *next_task, *prev_task; TASK_RUNNING状态的进程链表 task_struct中的 struct list_head run_list; list_head是Linux内核当中定义的一个数据结构 用来实现双向链表，Linux内核中使用上百个向 链表来存放各种数据结(includelist.h) struct list_head struct list_head *next, *prev; ; 进程PID hash task_struct中的pid 为了快速的从pid值获得进程描述符。需要 有hash表 hash_pid(),unhashpid()在pidhash表中分别 插入和删除一个进程 find_task_by_pid()查找散列表并返回给定 PID的进程描述符指针 进程之间的父子关系 task_struct中的 struct task_struct *p_opptr, *p_pptr, *p_cptr, *p_ysptr, *p_osptr; p_opptr : original parent (process 1 或者创 建它的父进程) p_pptr: parent (父进程，有时候是调试时的 调试监管进程) p_cptr: child (指向自己最年轻的子进程) p_ysptr：指向比自己年轻的兄弟进程 p_osptr：指向比自己老的兄弟进程 进程之间的父子关系(续) 进程之间的父子关系(续) Linux中的0号进程,通常称为swapper进 程，是所有进程的祖先。由它执行 cpu_idle()函数，当没有其他进程处于 TASK_RUNNING的时候，调度程序会 选择0号进程运行 0号进程创建1号进程，通常称为init进 程。它创建和监控其他进程的活动 进程的地址空间 Linux把进程的线性地址空间组织为一 个个线性区 每一个线性区对应一组连续的页 线性区之间不重叠 进程的地址空间(续) task_struct struct mm_struct *mm; 内存描述符 mm_struct 里面有一个字段mmp 指向内存线性区链表的首部。 进程的地址空间(续) 每个线性区有一定的访问权限 在增加或删除线性区时，Linux尽量合 并访问权限相同且相邻的线性区 进程的地址空间(续) 进程堆的管理 每个进程都拥有一个特殊的线形区：堆 内存描述符里面的start_brk和brk字段 限定了这个区的开始地址和结束地址 常用的C库函数：malloc(),free() 系统调用brk()用于直接修改堆大小 二、LINUX进程控制 Linux进程的创建和执行 相关的数据结构和系统调用 进程的创建 程序的执行 Linux进程的撤消 相关的数据结构 系统创建进程时，Linux为新进程分配 一task_struct结构，进程结束时收回其 task_struct结构 Linux在内存空间中分配了一块空间来 存放进程的task_struct结构，并将所有 的task_struct结构的指针放在一个task 数组中，该数组是在操作系统内核中专 门开辟的一块区域，数组大小也就是系 统中所能容纳的进程的数目 相关的数据结构(续) Task数组的结构： struct task_struct *taskNR_TASKS = NR_TASKS是数组的大小，默认是512 相关的数据结构(续) Task_struct结构的描述： n 进程标识 n 进程状态(State) n 进程调度信息和策略 n 标识号(Identifiers) n 进程通信有关的信息(IPC) n 进程链接信息(Links) n 时间和定时器信息(Times and Timers) n 文件系统信息(Files System) n 处理器相关的上下文信息 相关的系统调用 Fork() 通过复制调用进程来建立新的进程 ，是最基本的进程建立过程 Exec 包括一系列系统调用，它们都是通过 用一个新的程序覆盖原来的内存空间，实现 进程的转变 Wait() 提供初级的进程同步措施，能使一 个进程等待，直到另外一个进程结束为止。 Exit() 该系统调用用来终止一个进程的运行 如何区分父进程和子进程的功能？ 父子进程怎样被调度执行？ 父子进程在内存中如何存放？ 子进程如何继承父进程的资源？ 进程的创建过程 新的进程通过克隆旧的进程来建立，当前进 程是通过fork()系统调用来建立新的进程 当系统调用结束时，内核在系统的物理内存 中为新进程分配新的task_struct结构，并为 新进程要使用的堆栈分配物理页和进程标志 符 父进程和子进程共享打开的文件 fork()的简单流程 Fork调用执行示意 如上图所示，分别使fork调用前后的两个部 分 PC指向当前执行的语句，fork之前，它指向 第一个printf语句，fork调用之后进程A、B 一起运行，A是父进程，B是子进程进程A 的副本，执行与A一样的程序。两个pc都指 向第二个printf语句。也就是AB从程序的相 同点开始执行 Fork内存的变动 Fork()执行的内存变动如下： 分配1页给task_struct结构 分配1页给内核堆栈 分配1页给pg_dir并且给page_tables分配一些 页 Fork硬件相关的变化 硬件相关的变化 SS被置为内核堆栈(0x10) ESP被置为新分配栈的顶端 (kernel_stack_page) CR3指向新分配的页目录 (由copy_page_table()完成) Idt=_LDT(task_nr)建立新的局部描述符 为新的任务状态段(tss)和局部描述符表(ldt) 装入gdt 从父进程继承剩下的寄存器 Fork系统调用 Pid_t fork(void); 由fork创建的新进程称为子进程。该函数被调 用一次，会返回两次。给子进程的返回值是0 ，给父进程的返回值是子进程的进程ID。然 后子进程和父进程继续执行fork之后的指令 。子进程拥有父进程数据空间，堆和栈的拷 贝，但是它们并不是共享这些存储空间。这 里就用到了 “写时复制”技术 写时复制 写时复制技术(copy_on_write) Linux通过写时复制技术来调入执行的程序 Linux将可写虚拟内存页的页表项标志为只读， 当进程向该内存页写入数据时，处理器会发现内存 访问中的问题(向只读页中写入)，然后会导致操作系 统可以捕获的页故障，由操作系统来完成内存页的 复制 一个给定的物理页面可以代表多个逻辑页面，当 这个页被一个进程从另一个进程处得到共享时，它 是逻辑上的拷贝 如前面的fork调用，逻辑拷贝整个进程的地址空 间，仅当试图修改页面(产生写错误)才真正的拷贝 程序的执行 用fork创建子进程之后，为了让父进程和子 进程执行不同的任务，经常需要调用一种 exec函数以执行另一个程序。当进程调用 exec函数时，该进程完全由新程序替代。新 程序从main开始执行 exec并不创建新进程，前后进程ID是不变的 。它是用另外一个程序替代了当前进程的正 文，数据，堆和栈 exec函数 exec执行时的内存变化 1页分配给可执行文件头 1页或者多页分配给堆栈 硬件相关的变化： clear_page_tables()移去旧页 在新的LDT中设置描述符 包含argv和envp的“脏”页被分配 设置调用者的指针 设置调用者的堆栈指针指向建立的堆栈 更新内存段的边界 Fork VS Exec 因为fork只能建立相同程序的副本，如果 它是程序员唯一可以使用的建立进程的手段 ，会影响linux的性能 exec系列系统调用把新进程装入调用进程 的地址空间，改变调用进程的代码。如果 exec成功，调用者进程将被覆盖，从新进程 的入口地址开始执行。exec只用新进程取代 了原来的进程。并且没有返回数据 进程的撤销 撤销时机 主动撤销：执行完代码，通知内核释放进 程的资源 被动：内核有选择地强迫进程死掉。e.g内 核代表进程运行时在内核态产生不可恢复 的异常 进程的撤销 进程可能已死，但必须保存它的描述符 ，在你进程得到通知后才可以删除 僵死状态：表明进程已死，但需要等待 父进程删除 撤销过程分为 进程终止：释放进程占有的大部分资源 进程删除：彻底删除进程的所有数据结构 系统调用_exit() C编译程序总是把exit()插入到main()的 最后一条语句之后，exit()调用_exit()系 统调用 _exit() 调用do_exit()释放进程所占资源 ，终止进程 进程终止：do_exit() 删除内核对终止进程的大部分引用： 信号量队列中的进程描述符 删除进程描述符中与分页、文件系统、打开文件 描述符和信号处理相关数据结构 减小进程所用模块的引用计数 将进程描述符的exit_code字段设置为终止代 号 更新父子进程的亲属关系，强制将自己的子 进程作为其它某个进程的子进程，以等待该 父进程进行删除 调用schedule()进行调度 进程删除 父进程调用wait()类系统调用检查子进 程是否终止 若子进程包含终止代号，则父进程通过 release()释放僵死进程的描述符 释放进程id 从进程链表中删除进程描述符 释放存放进程描述符的内存区 三、Linux的进程调度 schedule() 决定是否进行进程切换，若要切换，切 换到哪个进程 Linux的调度时机 调度策略 1、进程调度的依据 选择一个权值（weight）最大的进程 权值的计算goodness()： 综合policy，priority，rt_priority和counter四项计算 步骤： 1、区分实时进程和普通进程 实时进程的权值：rt_priority 普通进程的权值：与counter有关 2、权值： 普通进程：weight = p-counter 实时进程：weight = 1000 + rt_priority task_struct policy priority rt_priority counter 实时进程SCHED_RR SCHED_FIFO 普通进程SCHED_OTHER 普通进程 动态优先调度 周期性地修改进程的优先级（避免饥饿） 根据进程的counter值 实时进程的优先级是静态优先级 counter 剩余的时间片 时间单位：时钟滴答（10ms） 初值200ms do_fork()同时设置父进程和子进程的counter 域 把父进程的剩余时间片分成相等的两份，父 子进程各占一份 对于普通进程，counter起作用 与priority的关系 当时间片用完后，用priority重新对counter赋 值 何时重新赋值所有处于可运行状态的普 通进程的时间片都用完 时间片确定 CPU时间的两个层次：时间段，时间段中 时间片 基本时间片 need_resched 此标志若为1，调用调度程序schedule() 选择下一个应该运行的进程 调用ret_from_sys_call()恢复所选进程的环境 时钟中断：最频繁的调度时机 下一次调度将基本时间片指定为 进程的运行时间片 可以通过nice()和set priority() 改变进程的时间片 子进程继承父进程的基本时间片 INIT_TASK宏中初始化 DEF_COUNTER 2、Linux调度的时机 进程状态转换时刻 如，进程终止、进程睡眠（进程调用sleep()， exit()等） 可运行队列中增加新的进程时 系统调用add_to_runqueue()，会比较进程时间片 计数，符合条件则调度标志置1 当前进程时间片用完时 进程从系统调用返回到用户态时 内核处理完中断，进程返回到用户态时 后三种，调用ret_from_sys_call()，检测调度标志 ，若调度标志为1，此刻也为时机 3、调度程序源代码分析 可运行队列 双向循环队列，task_struct中的next_run和prev_run 两个特殊进程：当前进程current和空进程（ idle_task） 新出现的进程被插入到idle_task-next处（为什么？ ） 队列长度：nr_running（为1时，表示队列中只有空 进程） 实时进程时间片用完后，重新赋值，并放到队列末 尾 从就绪队列的队首开始，遍历队列，寻找权值最大 的进程 如果所有普通进程的时间片都用完了，则给所有进 程的counter重新赋值 如果当前进程被调度，则其继续执行 Linux源代码阅读-示例 进程调度schedule部分的阅读 1.如何入手 2.结构分析 入手 涉及到的主要入口文件： kernelsched.c kernelcontex.c kernelsoftirq.c includelinuxsched.h archprocess.c includeasm-system.h 入手 如何认定以上就是主要内容的所在？ l 从sched.c依据主要的导出过程（即此模块希望被别 人使用的接口）的实现和其中关键对外调用依赖的 分布情况。（通过简单的代码扫描即可获得这个信 息，通过代码阅读工具将更加便于引用的查找） l 忽略大多数本地函数的实现和对外依赖，只关注组 织模块代码流程的关键函数，这个可以从系统调用 接口的实现看出来，例如sys_fork()、sys_clone()等 都通过调用do_fork()实现，显然后者负责组织fock模 块的主体功能和程序流程。这里可以透过调用关系 分析以及名字的敏感性发现schedule()函数是这一模 块组织形态的核心。并且，可以预见到这个函数将 完成一些“主动”的功能 l 这里的划分基于对代码树构成和代码功能分布的一 般认识，这是一个前提 入手-统计主要的代码符号 鉴别本地使用和意图导出的符号：找到模块 的主要对外功能接口。查看sched.h对比 sched.c，可以发现下面的函数是在其中实现 的： extern void sched_init(void); extern void init_idle(void); extern void show_state(void); extern signed long FASTCALL(schedule_timeout(signed long timeout); asmlinkage void schedule(void); 入手 在contex.c中实现了： l extern int schedule_task(struct tq_struct *task); l extern void flush_scheduled_tasks(void); l extern int start_context_thread(void); l extern int current_is_keventd(void); 此外，该头文件也定义了下面几个函数。 extern void cpu_init (void); = arch.kernel. extern void trap_init(void); = arch.kernel. 入手 下面是和计时相关的函数： extern void update_process_times(int user); extern void update_one_process(struct task_struct *p, unsigned long user, unsigned long system, int cpu); 还有相当数量的内核调用实现，例如和 信号相关的内容等 入手 通过对头文件的观察还可以发现几组重 要的系统变量，下面是几个主要部分 l全局锁 l跟踪变量 l全局唯一的结构单体和表 l全局参数 l全局常量 入手 这里罗列的符号实质上给出了调度模块的模糊的组织轮廓： l 通过系统知识可以判断调度器模块是一个主动模块：它的代 码被激活执行主要不是由用户调用引发，而直接受系统机制 的影响，例如定时机制、系统调用机制、异常处理机制等。 因此需要关注这些系统机制如何触发调度器的运行的问题 l 主动性和功能特征意味着调度器本身的初始化必须在系统正 常运转起来之前完成，它的初始化和系统其它部分的初始化 有逻辑上的关联，这是值得考虑的又一个问题 l 同时，作为一个系统功能和服务的提供者，也有被动服务。 有两类：为内核实现功能而提供的调用以及实现的系统调用 l 在“假象”的模块边界上除了调用形态的依赖，还有数据关联 ：全局的数据以及它们的格式（数据结构） l 到目前为止，我们关心的仍旧是结构问题而非实现问题 结构分析-调度器何时被激活？ 主要想法是首先将scheduler看作一个实体，考察它 在何时被激活：可以通过查找对schedule()函数的引 用来考察这个问题，当然这一点很可能是不完全的 ，心里要有数。这里列出了部分典型的对schedule() 的调用（此处列表不包括驱动程序中存在的调用） ： l Apm.c (archi386kernel):schedule(); l Buffer.c (fs):schedule(); l Exit.c (kernel):schedule(); l Filemap.c (mm):schedule(); l 等等 结构分析 通过对这些引用简单的浏览可以发现几个值得注意的地方： 1、这些调用中的大部分在调用点是因为需要等待一个尚未发生的 事件（通常是由调用者自身产生了一个去做这件事的执行线序 ），而主动放弃处理器。其中一部分出现在实际实现某些系统 调用的内部函数中，例如do_signal()。有较多的存在于非通常 意义的kernel部分，例如文件系统驱动程序中：ext3_ioctl() 2、一部分调用具有如下的形式： if (current-need_resched) 改变当前状态; schedule(); 这里的全局变量current以及对应的need_resched值得关注 3、处在无限循环中的调用，典型的就是softirq.c中的调用，由对 linux中断处理机制的了解，可以想象，这里将是系统调度得以 不断进行的一个关键点 结构分析 4、sched.c自己产生的调用。这关系到调度机制的实现问 题 5、由汇编代码产生的调用 6、以上的第2点提到的need_resched在那些地方被改变呢 ？通过查找发现，下面这些地方会设置这个变量的值 （也可能不完全）。比较明显的可以看到，除了 sched.c其它部分基本上只会将当前进程的该标志设置 为1，即需要调度，而sched.c中则会将某个进程（刚退 下处理器）的该标志复位为零。还需要注意的是有两 处被设置为1的情况：fork.c和mian.c，这两处均涉及 到产生新的进程之后设置此值，后者更是系统的第一 个进程的实现 结构分析数据结构和全局数据 调度的核心结构就是task_struct，在includelinuxsched.h中定义： 这个结构相当长，其内容大致可以分为如下几个部分： l调度时刻需要跟踪的信息 跟踪状态 是否需要调度 上下文 多处理器支持等 l进程结构之间的组织 队列前后指向指针 父进程 子进程 l进程属性 优先级 进程号 对应的程序等等 l用户以及资源配置 计时：跟踪记录各种时间信息 文件相关：掌握的文件资源 内存相关：撞我的内存资源，包括页映射等 配额、用户信息 l进程间通信、扩展点以及异常处理 信号以及处理的挂钩 各种锁 信号量等 结构分析 从数据结构看到的结构互联的组织： 系统队列：双链表，通过 next_task和 prev_task两个指针相互勾连 进程家族：通过p_opptr、p_pptr、 p_cptr、p_ysptr和p_osptr五个指针连 接，如下图 父进程 最老的进程子进程最新的进程 p_pptr p_cptr p_pptr p_pptr p_osptr p_ysptr p_osptr p_ysptr 下一级结构 结构分析状态转换部分 状态转换 进程的状态由state跟踪，取值可为： #define TASK_RUNNING0 #define TASK_INTERRUPTIBLE1 #define TASK_UNINTERRUPTIBLE2 #define TASK_ZOMBIE4 #define TASK_STOPPED8 当state的值小于零（-1），表示不可运行，为零势正 在运行，而大于零则是处于暂停阶段。 简单分析调用关系之后，可以看出状态变化，具体 的方法就是查找使用上述状态常量进行赋值的点。 经过分析有如下的图： 结构分析 结构分析调度流程 从schedul()函数入手：这个函数有 asmlinkage void schedule(void) struct schedule_data * sched_data; struct task_struct *prev, *next, *p; struct list_head *tmp; int this_cpu, c; spin_lock_prefetch( 将锁变量runqueue_lock 取到一级cache中，此处尚未加锁，为了避免下面加锁的同时发 生cache失效而导致可能的加锁失败。 BUG_ON(!current-active_mm); need_resched_back: prev = current; prev就是当前进程结构 结构分析调度流程 this_cpu = prev-processor; if (unlikely(in_interrupt() 在中断的处理过程中不应该 有对此函数的调用 printk(“Scheduling in interruptn“); BUG(); release_kernel_lock(prev, this_cpu); 释放内核锁：有什么作用 ？ /* * sched_data is protected by the fact that we can run * only one process per CPU. */ sched_data = spin_lock_irq( 此处正式加锁，以下部 分由于修改重要全局数据而进行保护性操作，主要为了防止代 码的重入 /* move an exhausted RR process to be last */ if (unlikely(prev-policy = SCHED_RR) 对于使用RR 算法的进程，如果到时了，就重置时间片，并移动到队 列的末尾。 if (!prev-counter) prev-counter = NICE_TO_TICKS(prev- nice); move_last_runqueue(prev); switch (prev-state) 这里根据状态调整队列，这句话由于 case和default的顺序颠倒而显得比较 怪异，仔细观察会发现后两个分支的 颠倒可以节约一个break，是否是一个 优化，就不得而知了。 case TASK_INTERRUPTIBLE: 可被打断 if (signal_pending(prev) 有信号 prev-state = TASK_RUNNING; 置为运 行态 break; default: del_from_runqueue(prev); 其他状况：从运行队列 删除 case TASK_RUNNING:; 运行状态：不做操作 prev-need_resched = 0; 重置调度标记：不需要调度 /* * this is the scheduler proper: */ repeat_schedule: 一个重要的地址标签 /* * Default process to select */ next = idle_task(this_cpu); 将下一个要被调度的进程设为idle c = -1000; c用来跟踪权重最大的进程，这里用的 初始值是-1000，在调度的权重计算中， 这个值相当于负无穷，因为goodness函 数的值域远大于它 list_for_each(tmp, 这就 是其中的一项 if (can_schedule(p, this_cpu) 判定可被调度 int weight = goodness(p, this_cpu, prev- active_mm); 计算权重 if (weight c) 跟踪、记录循环中发现的 最大权重以及对应的进程 c = weight, next = p; 结构分析 这个点上，next就是指向下一个要运行的进 程的结构的指针，c就是权重 考虑c区各种值的含义： l c=0，这代表某个调度（普通以及RR）时间 片到时，要更新全部进程的权重 l c=-1，运行队列上的都有SCHED_YIELD标 志，他们都想让位不引发计时器更新 l c1000，实时进程 /* Do we need to re-calculate counters? */ if (unlikely(!c) 如果c为0，重新计算 struct task_struct *p; spin_unlock_irq( 更新过程不对运行队列 操作，可以解锁 read_lock( 不过要禁止对任务列表的读 for_each_task(p) 重新计算权值（优先数，越大越优 先） p-counter = (p-counter 1) + NICE_TO_TICKS(p- nice); read_unlock( 更新完毕、解锁 spin_lock_irq( 继续对运行队列操作，加 锁，这里主要是因为有循环的发生，转移点上是加锁的，为了保持 一致。 goto repeat_schedule; 因为时间片到时，所以重新选一个 /* * from this point on nothing can prevent us from * switching to the next task, save this fact in * sched_data. */ 选定了，从这里开始，切换到“下”一个进程的动作将必然发生 sched_data-curr = next; task_set_cpu(next, this_cpu); spin_unlock_irq( 不再对运行队列保护 if (unlikely(prev = next) 选出来的和原来的是一个， /* We wont go through the normal tail, so do this by hand */ 这时候让贤已经没有必要，清除该标记 prev-policy goto same_process; 不做上下文切换，直接返回断点 上下文切换 kstat.context_swtch+; prepare_to_switch(); 准备上下文切换主要是更换内存映射 struct mm_struct *mm = next-mm; struct mm_struct *oldmm = prev-active_mm; if (!mm) BUG_ON(next-active_mm); next-active_mm = oldmm; atomic_inc( enter_lazy_tlb(oldmm, next, this_cpu); else BUG_ON(next-active_mm != mm); switch_mm(oldmm, mm, next, this_cpu); if (!prev-mm) prev-active_mm = NULL; mmdrop(oldmm); /* * This just switches the register state and the * stack. */ switch_to(prev, next, prev); 切换在这个函数里发生：关注 运行到这里，已经是再次被调度执行了 _schedule_tail(prev); same_process: reacquire_kernel_lock(current); 为当前进程获得一 个内核锁，对于单处理器，这是一个空操作。 不幸又需要调度 if (current-need_resched) 再来一次 goto need_resched_back; return; 结构分析 需要跟踪的宏：switch_to(prev, next, prev) 注意：下面的一段代码应该视作在不同 的进程之间“共享”