操作系统分析.pptx

Linux的进程的进程xlanchen2007.9.18xlanchen2007.9.25Linux Operating Systems Analysis2主要内容主要内容l进程描述符l进程切换l进程的创建和删除l进程调度xlanchen2007.9.25Linux Operating Systems Analysis3进程的概念进程的概念l进程是执行程序的一个实例l进程和程序的区别l几个进程可以并发的执行一个程序l一个进程可以顺序的执行几个程序xlanchen2007.9.25Linux Operating Systems Analysis4进程描述符进程描述符l为了管理进程，内核必须对每个进程进行清晰的描述。l进程描述符提供了内核所需了解的进程信息linclude/linux/sched.hstruct task_structl数据结构很庞大l基本信息l管理信息l控制信息xlanchen2007.9.25Linux Operating Systems Analysis5xlanchen2007.9.25Linux Operating Systems Analysis6Linux进程的进程的状态状态l可运行状态(TASK_RUNNING)l可中断的等待状态(TASK_INTERRUPTIBLE)l不可中断的等待状态(TASK_UNINTERRUPTIBLE)l暂停状态(TASK_STOPPED)l僵死状态(TASK_ZOMBIE)l状态值的改变通常是一个简单的赋值l内核也提供set_task_state 和set_current_state 宏xlanchen2007.9.25Linux Operating Systems Analysis7进程状态转换图进程状态转换图xlanchen2007.9.25Linux Operating Systems Analysis8标识一个进程标识一个进程l使用进程描述符地址l进程和进程描述符之间有非常严格的一一对应关系，使得用32位进程描述符地址标识进程非常方便l使用PID(Process ID，PID)l每个进程的PID都存放在进程描述符的pid域中l032767l新pid的产生：get_pidl+1l循环xlanchen2007.9.25Linux Operating Systems Analysis9获得一个进程的获得一个进程的pidl系统调用getpidsys_getpidl关于进程组l使用组链表l所有进程共享组内第一个进程的pidl数据：tgpidl单独一个进程可以看成只有一个进程的组lgetpid返回组pidxlanchen2007.9.25Linux Operating Systems Analysis10进程描述符和进程的进程描述符和进程的内核内核堆栈堆栈lLinux为每个进程分配一个8KB大小的内存区域，用于存放该进程两个不同的数据结构：l进程描述符l进程的内核堆栈进程处于内核态时使用，不同于用户态堆栈内核控制路径所用的堆栈很少，因此对栈和描述符来说，8KB足够了xlanchen2007.9.25Linux Operating Systems Analysis11Task_unionlC语言允许用如下的一个union结构来方便的表示这样的一个混合体l进程描述符的分配/回收/访问lalloc_task_structlfree_task_struct lget_task_struct=2048xlanchen2007.9.25Linux Operating Systems Analysis12current宏进程描述符宏进程描述符l从刚才看到的进程描述符和内核态堆栈之间的配对，内核可以很容易的从esp寄存器的值获得当前在CPU上运行的进程的描述符指针l因为这个内存区是8KB=213大小，内核必须做的就是让esp有13位的有效位，以获得进程描述符的基地址l这个工作由current宏来完成8191=8192-1=0 x2000-1=0 x1fff取反：0 xffffe000（最后13位为0）xlanchen2007.9.25Linux Operating Systems Analysis13Current宏的使用宏的使用lCurrent宏可以看成当前进程的进程描述符指针，在内核中直接使用l比如current-pid返回在CPU上正在执行的进程的PIDxlanchen2007.9.25Linux Operating Systems Analysis14进程链表进程链表l为了对给定类型的进程(比如所有在可运行状态下的进程)进行有效的搜索，内核维护了几个进程链表l所有进程链表在进程描述符中：xlanchen2007.9.25Linux Operating Systems Analysis15lSET_LINKS和REMOVE_LINKS宏用来分别在进程链表中插入和删除一个进程描述符。xlanchen2007.9.25Linux Operating Systems Analysis16lfor_each_task宏扫描整个进程链表xlanchen2007.9.25Linux Operating Systems Analysis17TASK_RUNNING状态的进程链表状态的进程链表l当内核调度程序寻址一个新的进程在cpu上运行时，必须只考虑可运行进程，因为扫描整个进程链表效率很低l引入了可运行状态的双向循环链表，也叫运行队列l进程描述符使用用来实现运行队列xlanchen2007.9.25Linux Operating Systems Analysis18对可运行队列的一些操作函数对可运行队列的一些操作函数增加/删除一个可运行进程可运行队列的长度，可运行进程的个数唤醒一个进程，使一个进程可运行xlanchen2007.9.25Linux Operating Systems Analysis19pidhash表及链接表表及链接表l在一些情况下，内核必须能从进程的PID得出对应的进程描述符指针。例如kill系统调用l为了加速查找，引入了pidhash散列表l用pid_hashfn宏把PID转换成表的索引xlanchen2007.9.25Linux Operating Systems Analysis20pidhash表及链接表表及链接表xlanchen2007.9.25Linux Operating Systems Analysis21进程之间的亲属关系进程之间的亲属关系l程序创建的进程具有父子关系，在编程时往往需要引用这样的父子关系。进程描述符中有几个域用来表示这样的关系xlanchen2007.9.25Linux Operating Systems Analysis22等待队列等待队列l当要把除了TASK_RUNNING状态之外的进程组织在一起时，linux使用了等待队列lTASK_STOPPED和TASK_ZOMBIE不在专门的链表中lTASK_INTERRUPTIBLE和TASK_UNINTERRUPTIBLE状态的进程再分成很多类，每一类对应一个特定的事件。在这种情况下，进程状态提供的信息满足不了快速检索，因此，内核引进了另外的进程链表，叫做等待队列l等待队列在内核中有很多用途，尤其是对中断处理、进程同步和定时用处很大xlanchen2007.9.25Linux Operating Systems Analysis23l等待队列使得进程可以在事件上的条件等待，并且当等待的条件为真时，由内核唤醒它们l等待队列由循环链表实现l在等待队列上内核实现了一些操作函数Add_wait_queueremove_wait_queuexlanchen2007.9.25Linux Operating Systems Analysis24等待队列的链表等待队列的链表xlanchen2007.9.25Linux Operating Systems Analysis25进程等待进程等待l等待一个特定事件的进程能调用下面几个函数中的任一个lsleep_onlsleep_on_timeoutlinterruptible_sleep_onlinterruptible_sleep_on_timeoutl进程等待由需要等待的进程自己进行（调用）xlanchen2007.9.25Linux Operating Systems Analysis26sleep_onxlanchen2007.9.25Linux Operating Systems Analysis27进程的进程的唤醒唤醒l利用wake_up或者wake_up_interruptible等一系列的宏，都让插入等待队列中的进程进入TASK_RUNNING状态xlanchen2007.9.25Linux Operating Systems Analysis28进程切换进程切换(process switching)l为了控制进程的执行，内核必须有能力挂起正在CPU上执行的进程，并恢复以前挂起的某个进程的执行，这叫做进程切换，任务切换，上下文切换xlanchen2007.9.25Linux Operating Systems Analysis29进程上下文进程上下文l包含了进程执行需要的所有信息l用户地址空间包括程序代码，数据，用户堆栈等l控制信息进程描述符，内核堆栈等l硬件上下文xlanchen2007.9.25Linux Operating Systems Analysis30硬件上下文硬件上下文l尽管每个进程可以有自己的地址空间，但所有的进程只能共享CPU的寄存器。l因此，在恢复一个进程执行之前，内核必须确保每个寄存器装入了挂起进程时的值。这样才能正确的恢复一个进程的执行l硬件上下文：进程恢复执行前必须装入寄存器的一组数据l包括通用寄存器的值以及一些系统寄存器l通用寄存器如eax，ebx等l系统寄存器如eip，esp，cr3等等xlanchen2007.9.25Linux Operating Systems Analysis31l在linux中l一个进程的硬件上下文主要保存在thread_struct中l其他信息放在内核态堆栈中xlanchen2007.9.25Linux Operating Systems Analysis32thread_structxlanchen2007.9.25Linux Operating Systems Analysis33上下文切换上下文切换lswitch_to宏执行进程切换，schedule()函数调用这个宏一调度一个新的进程在CPU上运行l在schedule()中找到调用switch_to宏的位置lswitch_to利用了prev和next两个参数：lprev：指向当前进程lnext：指向被调度的进程xlanchen2007.9.25Linux Operating Systems Analysis34当前进程仍然是prev这个push操作针对的是当前进程的堆栈保存esi，edi，ebp保存esp到%0中嵌入式汇编中用这种方法表示输入、输出参数，可以从0开始编号%0是什么？保存esp到当前进程的上下文中从next的上下文中取出堆栈的位置，将其作为当前堆栈堆栈被切换在prev进程的上下文中设置返回地址，返回到下面标号为1处从next进程的上下文中取得该进程的返回地址，放入堆栈中调用_switch_to函数xlanchen2007.9.25Linux Operating Systems Analysis35进程切换的关键语句进程切换的关键语句l堆栈的切换从此，内核对next的内核态堆栈操作，因此，这条指令执行从prev到next真正的上下文切换，因为进程描述符和内核态堆栈紧密联系在一起，改变内核态堆栈就意味改变当前进程xlanchen2007.9.25Linux Operating Systems Analysis36l什么时候next进程真正开始执行呢？lcall=保存返回地址+跳转到target处执行lret=从堆栈上获得返回地址，并跳转到该返回地址处执行l？当_switch_to正常返回时，发生了什么事情？xlanchen2007.9.25Linux Operating Systems Analysis37标号为标号为1的执行代码处的执行代码处l一个进程被正常切换出时，保存的eip总是标号为1的那个位置l当这个进程再次被调度运行时，恢复在堆栈上的返回地址总是这个11:popl%ebppopl%edipopl%esixlanchen2007.9.25Linux Operating Systems Analysis38_switch_tol_switch_to用来处理其他上下文的切换l此时，使用的堆栈是next进程的堆栈，这个堆栈上没有_switch_to需要的参数prev和nextl怎么传参呢？l找到_switch_to的函数定义和函数声明l找到FASTCALL的定义xlanchen2007.9.25Linux Operating Systems Analysis39_switch_to的关键操作的关键操作lunlazy_fpu()处理数学协处理器l保存和恢复fs、gsl等等xlanchen2007.9.25Linux Operating Systems Analysis40？哪里切换了进程的地址空间？哪里切换了进程的地址空间l从执行switch_to的位置往前找xlanchen2007.9.25Linux Operating Systems Analysis41Project：进程的切换：进程的切换l对Linux中进程的切换过程进行分析，提交分析报告xlanchen2007.9.25Linux Operating Systems Analysis42进程的创建进程的创建l许多进程可以并发的运行同一程序，这些进程共享内存中程序正文的单一副本，但每个进程有自己的单独的数据和堆栈区l一个进程可以在任何时刻可以执行新的程序，并且在它的生命周期中可以运行几个程序l又如，只要用户输入一条命令，shell进程就创建一个新进程xlanchen2007.9.25Linux Operating Systems Analysis43l传统的UNIX操作系统采用统一的方式来创建进程l子进程复制父进程所拥有的资源l缺点：l创建过程慢、效率低l事实上，子进程复制的很多资源是不会使用到的l现代UNIX内核通过引入三种不同的机制来解决这个问题xlanchen2007.9.25Linux Operating Systems Analysis44l1、写时复制技术，Copy-On-Writing，COW写时复制技术允许父子进程能读相同的物理页。l只要两者有一个进程试图写一个物理页，内核就把这个页的内容拷贝到一个新的物理页，并把这个新的物理页分配给正在写的进程xlanchen2007.9.25Linux Operating Systems Analysis45l2、轻量级进程允许父子进程共享许多数据结构l页表l打开的文件列表l信号处理l3、vforkl使用vfork创建的新进程能够共享父进程的内存地址空间。父进程在这个过程中被阻塞，直到子进程退出或者执行一个新的程序xlanchen2007.9.25Linux Operating Systems Analysis46Linux的进程创建的进程创建lLinux提供了几个系统调用来创建和终止进程，以及执行新程序lFork，vfork和clone系统调用创建新进程l其中，clone创建轻量级进程，必须指定要共享的资源lexec系统调用执行一个新程序lexit系统调用终止进程（进程也可以因收到信号而终止）xlanchen2007.9.25Linux Operating Systems Analysis47forklfork系统调用创建一个新进程l调用fork的进程称为父进程l新进程是子进程l子进程几乎就是父进程的完全复制。它的地址空间是父进程的复制，一开始也是运行同一程序。lfork系统调用为父子进程返回不同的值xlanchen2007.9.25Linux Operating Systems Analysis48execl很多情况下，子进程从fork返回后很多会调用exec来开始执行新的程序l这种情况下，子进程根本不需要读或者修改父进程拥有的所有资源。l所以fork中地址空间的复制依赖于Copy On Write技术，降低fork的开销xlanchen2007.9.25Linux Operating Systems Analysis49使用使用fork和和exec的例子的例子If(result=fork()=0)/*子进程代码*/if(execve(“new_program”,)0)perror(“execve failed”);exit(1);else if(result0)perror(“fork failed”)/*result=子进程的pid，父进程将会从这里继续执行*/xlanchen2007.9.25Linux Operating Systems Analysis50l分开这两个系统调用是有好处的l比如服务器可以fork许多进程执行同一个程序l有时程序只是简单的exec，执行一个新程序l在fork和exec之间，子进程可以有选择的执行一系列操作以确保程序以所希望的状态运行l重定向输入输出l关闭不需要的打开文件l改变UID或是进程组l重置信号处理程序l若单一的系统调用试图完成所有这些功能将是笨重而低效的l现有的fork-exec框架灵活性更强l清晰，模块化强xlanchen2007.9.25Linux Operating Systems Analysis51do_forkl不论是fork，vfork还是clone，在内核中最终都调用了do_forkxlanchen2007.9.25Linux Operating Systems Analysis52xlanchen2007.9.25Linux Operating Systems Analysis53l阅读do_fork，了解大致程序流程l？子进程从哪里开始执行，它的返回值是什么？l观察子进程的初始上下文是怎么设置的l内核堆栈的内容lThread_struct的内容xlanchen2007.9.25Linux Operating Systems Analysis54注意：childregs指针指向哪里eax寄存器用作返回值，这里强制为0在上下文中，设置用户态堆栈指针设置内核态堆栈指针被调度后，执行入口强制从ret_from_fork返回用户态此后，由于子进程处于调度队列上，因此在合适的时候会被调度，调度时根据这里设置的上下文返回用户态xlanchen2007.9.25Linux Operating Systems Analysis55子进程的内核态堆栈子进程的内核态堆栈进程描述符子进程的8K unionesp返回值eax被强制写0用户态堆栈esp的值用户态下eip的值子进程恢复到用户态时需要的上下文eipesp子进程的硬件上下文ret_from_fork低地址高地址xlanchen2007.9.25Linux Operating Systems Analysis56子进程的执行子进程的执行lfork后，子进程处于可运行状态，由调度器决定何时把CPU交给这个子进程l进程切换后因为eip指向ret_from_fork，所以CPU立刻跳转到ret_from_fork()去执行。l接着这个函数调用ret_from_sys_call()，此函数用存放在栈中的值装载所有寄存器，并强迫CPU返回用户态xlanchen2007.9.25Linux Operating Systems Analysis57内核线程内核线程l系统把一些重要的任务委托给周期性执行的进程l刷新磁盘高速缓存l交换出不用的页框l维护网络链接等待l内核线程与普通进程的差别l每个内核线程执行一个单独指定的内核函数l只运行在内核态l只使用大于PAGE_OFFSET的线性地址空间xlanchen2007.9.25Linux Operating Systems Analysis58线程和进程的比较线程和进程的比较lLinux内核中没有线程的概念l没有针对所谓线程的调度策略l没有数据结构用来表示一个线程l一般线程的概念在linux中只是表现为一组共享资源的进程(每个这样的进程都有自己的进程描述符)l在其他系统中(比如windows)l线程是实实在在的一种运行抽象，提供了比进程更轻更快的调度单元l在linux中“线程”仅仅是表示多个进程共享资源的一种说法xlanchen2007.9.25Linux Operating Systems Analysis59创建内核线程创建内核线程lKerenl_thread()创建一个内核线程，并且只能由另一个内核线程来执行这个调用xlanchen2007.9.25Linux Operating Systems Analysis60进程树进程树l进程0l进程1lxlanchen2007.9.25Linux Operating Systems Analysis61进程进程0l所有进程的祖先叫做进程0l在系统初始化阶段由start_kernel()函数从无到有手工创建的一个内核线程l存放在init_task_union变量中的一个进程描述符和一个内核态堆栈（回忆一下启动时，堆栈的初始化）l用INIT_MM,INIT_MMAP,INIT_FS,INIT_FILES,INIT_SIGNALS宏初始化进程描述符的各个对应域l页全局目录，swapper_pg_dir变量l进程0最后的初始化工作创建init内核线程，此后运行cpu_idle，成为idle进程xlanchen2007.9.25Linux Operating Systems Analysis62进程进程1l又称为init进程l由进程0在start_kernel调用rest_init创建linit进程PID为1，当调度程序选择到init进程时，init进程开始执行init()函数xlanchen2007.9.25Linux Operating Systems Analysis63linit()为常规内核任务初始化一些必要的内核线程，如:lkflushd 刷新脏缓冲区中的内容到磁盘以归还内存lkswapd执行内存回收功能的线程l最后init()函数调用execve()系统调用装入可执行程序init。从此，init内核线程变成一个普通的进程。但init进程从不终止，因为它创建和监控操作系统外层的所有进程的活动xlanchen2007.9.25Linux Operating Systems Analysis64撤销进程撤销进程l进程终止l进程终止的一般方式是exit()系统调用。l这个系统调用可能由编程者明确的在代码中插入l另外，在控制流到达主过程C中的main()函数的最后一条语句时，执行exit()系统调用l内核可以强迫进程终止l当进程接收到一个不能处理或忽视的信号时l当在内核态产生一个不可恢复的CPU异常而内核此时正代表该进程在运行xlanchen2007.9.25Linux Operating Systems Analysis65l进程终止使用exit系统调用l删除进程在父进程调用wait()类系统调用检查子进程是否合法终止以后，就可以删除这个进程xlanchen2007.9.25Linux Operating Systems Analysis66Project：进程的创建：进程的创建l使用C语言编写一段用户程序l调用fork创建一个子进程l然后让子进程和父进程分别输出fork的返回值l目的：从用户态体验进程的创建l对Linux中进程的创建进行分析，提交分析报告xlanchen2007.9.25Linux Operating Systems Analysis67进程调度进程调度l调度策略l调度算法xlanchen2007.9.25Linux Operating Systems Analysis68调度策略（调度策略（scheduling policy）l决定什么时候以怎样的方式选择一个新进程运行的一组规则lLinux的调度基于分时技术l允许多个进程“并发”运行lCPU的时间被划分成“片”，给每个可运行进程分配一片l在单处理器上，任何时刻只能运行一个进程，当一个并发执行的进程时间片用完时（到期）还没有终止，就可以进行进程调度l分时依赖于时钟中断，对进程透明xlanchen2007.9.25Linux Operating Systems Analysis69lLinux进程的优先级l根据特定的算法计算出进程的优先级，用一个值表示l这个值表示把进程如何适当的分配给CPUlLinux中进程的优先级是动态的l调度程序会根据进程的行为周期性的调整进程的优先级l较长时间未分配到CPU的进程，通常l已经在CPU上运行了较长时间的进程，通常xlanchen2007.9.25Linux Operating Systems Analysis70进程的分类进程的分类l不同类型的进程有不同的调度需求l第一种分类：lI/O-boundl频繁的进行I/Ol通常会花费很多时间等待I/O操作的完成lCPU-boundl计算密集型l需要大量的CPU时间进行运算xlanchen2007.9.25Linux Operating Systems Analysis71l第二种分类l交互式进程（interactive process）l需要经常与用户交互，因此要花很多时间等待用户输入操作l响应时间要快，平均延迟要低于50150msl典型的交互式程序：shell、文本编辑程序、图形应用程序等xlanchen2007.9.25Linux Operating Systems Analysis72l批处理进程（batch process）l不必与用户交互，通常在后台运行l不必很快响应l典型的批处理程序：编译程序、科学计算l实时进程（real-time process）l有实时需求，不应被低优先级的进程阻塞l响应时间要短、要稳定l典型的实时进程：视频/音频、机械控制等xlanchen2007.9.25Linux Operating Systems Analysis73与调度相关的系统调用与调度相关的系统调用lnicelgetpriority/setprioritylsched_getscheduler/sched_setschedulerlsched_getparam/sched_setparamlsched_yieldlsched_get_priority_min/sched_get_priority_maxlsched_rr_get_intervalxlanchen2007.9.25Linux Operating Systems Analysis74时间片时间片的选择的选择l时间片的长短对系统性能非常关键，它既不能太长也不能太短l太短：l频繁的切换会造成系统开销过大l假如切换时间为1ms，时间片设置为1ms，那就没空执行进程了xlanchen2007.9.25Linux Operating Systems Analysis75l太长l几乎每个进程都一次运行完l并发的概念基本消失l普通进程需要等待很长时间才能运行l时间片大小的选择总是一种折衷。Linux采取单凭经验的方法，即选择尽可能长的时间片，同时能保持良好的响应时间xlanchen2007.9.25Linux Operating Systems Analysis76调度算法调度算法lepochllinux调度算法把CPU时间划分为时期（epoch）l在一个单独的时期内，每个进程有一个指定的时间片l一个进程用完它的时间片时，就会被强占l只要进程的时间片没有用完，就可以被多次调度运行l当所有的进程用完它的时间片的时候，一个时期才结束，此时要重新计算所有进程的时间片，并重新开始一个新的时期xlanchen2007.9.25Linux Operating Systems Analysis77基本时间片基本时间片l基本时间片（base time quantum）l每个进程有一个基本时间片，通过nice计算l时间片/epoch到期时，新时间片的计算公式：nice缺省为0（在-20到19之间选择）通常，基本时间片的值 为6，由于时钟中断大约10ms左右，因此基本时间片的长度大约60msxlanchen2007.9.25Linux Operating Systems Analysis78l可以通过nice、setpriority系统调用调整进程的基本时间片xlanchen2007.9.25Linux Operating Systems Analysis79当前剩余时间片当前剩余时间片l每个进程使用counter表示当前时期内的剩余时间片l每当一个tick过去，就会从当前进程的counter上-1l在某个时期内创建的一个新进程，在该时期内的剩余时间片将从父进程那里继承一半xlanchen2007.9.25Linux Operating Systems Analysis80进程进程0（INIT_TASK）的时间片：）的时间片：HZ代表了1秒内的tick数因此一个tick就是1/100秒即10ms可以计算出DEF_COUNTER=10个tick即100ms(实际上约105ms)MAX_COUNTER=20个tick即200msxlanchen2007.9.25Linux Operating Systems Analysis81调度程序使用的数据结构调度程序使用的数据结构l进程描述符中：lneed_resched：是否需要调度lpolicy：调度策略先入先出的实时进程循环轮转的实时进程普通的分时进程当一个进程自动放弃运行时设置xlanchen2007.9.25Linux Operating Systems Analysis82lrt_priority：实时进程的静态优先级（199），普通进程不用（设为0）lcounter：当前剩余时间片l新时期开始时根据上述计算公式计算l每次时钟中断发生，时间片都会-1，直到为0（则请求调度）l创建一个新的进程时，子进程会继承父进程的一半剩余时间片lnice：基本时间片参数，可以调节xlanchen2007.9.25Linux Operating Systems Analysis83schedule函数函数lschedule函数实现调度l目的：在运行队列中找到一个进程，把CPU分配给它l调用方法：l直接调用，如sleep_onl松散调用，根据need_resched标记l阅读schedulexlanchen2007.9.25Linux Operating Systems Analysis84调度算法的性能调度算法的性能l不适合进程数量很大的情况l重新计算所有进程的动态优先级很耗时l对高负载系统来说，预定义的时间片太长l对于I/O密集型的程序不是很有利l对实时应用的支持是微弱的