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

LinuxLinux操作系统分析与实践操作系统分析与实践第三讲：进程管理第三讲：进程管理LinuxLinux操作系统分析与实践课程建设小组操作系统分析与实践课程建设小组北京大学北京大学二零零八年春季二零零八年春季*致谢：感谢致谢：感谢IntelIntel对本课程项目的资助对本课程项目的资助本讲主要内容本讲主要内容Linux中的进程中的进程Linux进程控制进程控制Linux的进程调度的进程调度Linux源代码阅读示例源代码阅读示例:进程调度进程调度schedule部分的阅读部分的阅读一、一、Linux中的进程中的进程进程进程 是程序执行时的一个实例是程序执行时的一个实例从内核的观点来看，进程的目的是担当从内核的观点来看，进程的目的是担当分配系统资源分配系统资源(CPU 时间，存储器等时间，存储器等)的实的实体体Linux中的关于进程的代码大部分是如何中的关于进程的代码大部分是如何管理进程的代码管理进程的代码每个进程运行的是程序的代码每个进程运行的是程序的代码轻量级进程轻量级进程线程代表进程的一个执行流，内核无法线程代表进程的一个执行流，内核无法感知感知Linux使用轻量级进程对多线程应用程序使用轻量级进程对多线程应用程序提供更好的支持提供更好的支持轻量级进程可以共享资源轻量级进程可以共享资源通过将轻量级进程与线程相关联，内核可以通过将轻量级进程与线程相关联，内核可以独立调度线程独立调度线程进程描述符进程描述符task_struct(include/linux/sched.h）进程描述符进程描述符(续续)Task_struct结构的描述：结构的描述：1.进程标识进程标识2.进程状态进程状态(State)3.进程调度进程调度信息信息和和策略策略4.标识号标识号(Identifiers)5.进程通信有关的信息进程通信有关的信息(IPC)6.进程链接信息进程链接信息(Links)7.时间和定时器信息时间和定时器信息(Times and Timers)8.文件系统信息文件系统信息(Files System)9.处理器相关的上下文信息处理器相关的上下文信息进程描述符进程描述符(续续)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_INTERRUPTIBLE 1#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 hashtask_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=&init_task;NR_TASKS是数组的大小，默认是是数组的大小，默认是512相关的数据结构相关的数据结构(续续)Task_struct结构的描述：结构的描述：1.进程标识进程标识2.进程状态进程状态(State)3.进程调度进程调度信息信息和和策略策略4.标识号标识号(Identifiers)5.进程通信有关的信息进程通信有关的信息(IPC)6.进程链接信息进程链接信息(Links)7.时间和定时器信息时间和定时器信息(Times and Timers)8.文件系统信息文件系统信息(Files System)9.处理器相关的上下文信息处理器相关的上下文信息相关的系统调用相关的系统调用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被置为内核堆栈被置为内核堆栈(0 x10)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_prioritytask_struct policy priority rt_priority counter实时进程实时进程SCHED_RRSCHED_FIFO普通进程普通进程SCHED_OTHER普通进程普通进程动态优先调度动态优先调度周期性地修改进程的优先级（避免饥饿）周期性地修改进程的优先级（避免饥饿）根据进程的根据进程的counter值值实时进程的优先级是静态优先级实时进程的优先级是静态优先级 counter剩余的时间片剩余的时间片时间单位：时钟滴答（时间单位：时钟滴答（10ms）初值初值200msdo_fork()同时设置父进程和子进程的同时设置父进程和子进程的counter域域把父进程的剩余时间片分成相等的两份，父子把父进程的剩余时间片分成相等的两份，父子进程各占一份进程各占一份对于普通进程，对于普通进程，counter起作用起作用与与priority的关系的关系当时间片用完后，用当时间片用完后，用priority重新对重新对counter赋赋值值何时重新赋值何时重新赋值所有处于可运行状态的普通所有处于可运行状态的普通进程的时间片都用完进程的时间片都用完时间片确定时间片确定CPU时间的两个层次：时间段，时间段中时时间的两个层次：时间段，时间段中时间片间片基本时间片基本时间片need_resched 此标志若为此标志若为1，调用调度程序，调用调度程序schedule()选择下一个应该运行的进程选择下一个应该运行的进程调用调用ret_from_sys_call()恢复所选进程的环境恢复所选进程的环境时钟中断：最频繁的调度时机时钟中断：最频繁的调度时机下一次调度将基本时间片指定为下一次调度将基本时间片指定为 进程的运行时间片进程的运行时间片可以通过可以通过nice()和和set priority()改变进程的时间片改变进程的时间片子进程继承父进程的基本时间片子进程继承父进程的基本时间片INIT_TASK宏中初始化宏中初始化 DEF_COUNTER2、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.ckernelcontex.ckernelsoftirq.cincludelinuxsched.harch.process.cincludeasm-system.h入手入手如何认定以上就是主要内容的所在？如何认定以上就是主要内容的所在？1.从从sched.c依据主要的导出过程（即此模块希望被别依据主要的导出过程（即此模块希望被别人使用的接口）的实现和其中关键对外调用依赖的人使用的接口）的实现和其中关键对外调用依赖的分布情况。（通过简单的代码扫描即可获得这个信分布情况。（通过简单的代码扫描即可获得这个信息，通过代码阅读工具将更加便于引用的查找）息，通过代码阅读工具将更加便于引用的查找）2.忽略大多数忽略大多数本地本地函数的实现和对外依赖，只关注组函数的实现和对外依赖，只关注组织模块代码流程的关键函数，这个可以从系统调用织模块代码流程的关键函数，这个可以从系统调用接口的实现看出来，例如接口的实现看出来，例如sys_fork()、sys_clone()等等都通过调用都通过调用do_fork()实现，显然后者负责组织实现，显然后者负责组织fock模模块的主体功能和程序流程。这里可以透过调用关系块的主体功能和程序流程。这里可以透过调用关系分析以及名字的敏感性发现分析以及名字的敏感性发现schedule()函数是这一模函数是这一模块组织形态的核心。并且，可以预见到这个函数将块组织形态的核心。并且，可以预见到这个函数将完成一些完成一些“主动主动”的功能的功能3.这里的划分基于对代码树构成和代码功能分布的一这里的划分基于对代码树构成和代码功能分布的一般认识，这是一个前提般认识，这是一个前提入手入手-统计主要的代码符号鉴别鉴别本地本地使用和意图导出的符号：找到模块的使用和意图导出的符号：找到模块的主要对外功能接口。查看主要对外功能接口。查看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中实现了：中实现了：1.extern int schedule_task(struct tq_struct*task);2.extern void flush_scheduled_tasks(void);3.extern int start_context_thread(void);4.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);还有相当数量的内核调用实现，例如和还有相当数量的内核调用实现，例如和信号相关的内容等信号相关的内容等入手入手通过对头文件的观察还可以发现几组重通过对头文件的观察还可以发现几组重要的系统变量，下面是几个主要部分要的系统变量，下面是几个主要部分1.全局锁全局锁2.跟踪变量跟踪变量3.全局唯一的结构单体和表全局唯一的结构单体和表4.全局参数全局参数5.全局常量全局常量入手入手这里罗列的符号实质上给出了调度模块的模糊的组织轮廓：这里罗列的符号实质上给出了调度模块的模糊的组织轮廓：1.通过系统知识可以判断调度器模块是一个主动模块：它的代通过系统知识可以判断调度器模块是一个主动模块：它的代码被激活执行主要不是由用户调用引发，而直接受系统机制码被激活执行主要不是由用户调用引发，而直接受系统机制的影响，例如定时机制、系统调用机制、异常处理机制等。的影响，例如定时机制、系统调用机制、异常处理机制等。因此需要关注这些系统机制如何触发调度器的运行的问题因此需要关注这些系统机制如何触发调度器的运行的问题2.主动性和功能特征意味着调度器本身的初始化必须在系统正主动性和功能特征意味着调度器本身的初始化必须在系统正常运转起来之前完成，它的初始化和系统其它部分的初始化常运转起来之前完成，它的初始化和系统其它部分的初始化有逻辑上的关联，这是值得考虑的又一个问题有逻辑上的关联，这是值得考虑的又一个问题3.同时，作为一个系统功能和服务的提供者，也有被动服务。同时，作为一个系统功能和服务的提供者，也有被动服务。有两类：为内核实现功能而提供的调用以及实现的系统调用有两类：为内核实现功能而提供的调用以及实现的系统调用4.在在“假象假象”的模块边界上除了调用形态的依赖，还有数据关的模块边界上除了调用形态的依赖，还有数据关联：全局的数据以及它们的格式（数据结构）联：全局的数据以及它们的格式（数据结构）5.到目前为止，我们关心的仍旧是结构问题而非实现问题到目前为止，我们关心的仍旧是结构问题而非实现问题结构分析结构分析-调度器何时被激活？主要想法是首先将主要想法是首先将scheduler看作一个实体，考察它在看作一个实体，考察它在何时被激活：可以通过何时被激活：可以通过查找对查找对schedule()函数的引用函数的引用来考察这个问题，当然这一点很可能是不完全的，心来考察这个问题，当然这一点很可能是不完全的，心里要有数。这里列出了部分典型的对里要有数。这里列出了部分典型的对schedule()的调的调用（此处列表不包括驱动程序中存在的调用）：用（此处列表不包括驱动程序中存在的调用）：1.Apm.c(archi386kernel):schedule();2.Buffer.c(fs):schedule();3.Exit.c(kernel):schedule();4.Filemap.c(mm):schedule();5.等等等等结构分析结构分析通过对这些引用简单的浏览可以发现几个值得注意的地方：通过对这些引用简单的浏览可以发现几个值得注意的地方：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中定义：中定义：这个结构相当长，其内容大致可以分为如下几个部分：这个结构相当长，其内容大致可以分为如下几个部分：1.调度时刻需要跟踪的信息调度时刻需要跟踪的信息跟踪状态跟踪状态是否需要调度是否需要调度上下文上下文多处理器支持等多处理器支持等2.进程结构之间的组织进程结构之间的组织队列前后指向指针队列前后指向指针父进程父进程子进程子进程3.进程属性进程属性优先级优先级进程号进程号对应的程序等等对应的程序等等4.用户以及资源配置用户以及资源配置计时：跟踪记录各种时间信息计时：跟踪记录各种时间信息文件相关：掌握的文件资源文件相关：掌握的文件资源内存相关：撞我的内存资源，包括页映射等内存相关：撞我的内存资源，包括页映射等配额、用户信息配额、用户信息5.进程间通信、扩展点以及异常处理进程间通信、扩展点以及异常处理信号以及处理的挂钩信号以及处理的挂钩各种锁各种锁信号量等信号量等结构分析结构分析从数据结构看到的结构互联的组织：从数据结构看到的结构互联的组织：系统队列：双链表，通过系统队列：双链表，通过 next_task和和prev_task两个指针相互勾连两个指针相互勾连进程家族：通过进程家族：通过p_opptr、p_pptr、p_cptr、p_ysptr和和p_osptr五个指针连接，五个指针连接，如下图如下图父进程父进程最老的进程最老的进程子进程子进程最新的进程最新的进程p_pptrp_cptrp_pptrp_pptrp_osptrp_ysptrp_osptrp_ysptr下一级结构下一级结构结构分析结构分析状态转换部分状态转换部分状态转换 进程的状态由进程的状态由state跟踪，取值可为：跟踪，取值可为：#define TASK_RUNNING0#define TASK_INTERRUPTIBLE1#define TASK_UNINTERRUPTIBLE 2#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);将锁变量将锁变量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);释放内核锁：有什么作用？释放内核锁：有什么作用？/*