进程管理及进程间通讯.ppt

第5章 进程管理及进程间通讯,本章介绍了Linux 进程的管理、调度以及 Linux 系统支持的进程间通讯机制，并对某些通信手段的内部实现机制进行了分析。本章还讨论了 Linux 核心的一些基本任务和机制，将Linux内核中为使内核其他部分能有效工作的用于同步的几种机制集中起来分析，强调了它们之间在实现和使用上的不同。,5.1 Linux 进程和线程,一个大型的应用系统，往往需要众多进程协作。进程是操作系统理论的核心与基础，许多概念都和进程相关。进程的标准定义是：进程是可并发执行的程序在一个数据集合上的运行过程。换句话说，在自身的虚拟地址空间运行的一个单独的程序称作一个进程。在Linux系统中，当一个程序开始执行后，在开始执行到执行完毕退出这段时间里，它在内存中的部分就被称作一个进程。进程与程序是有区别的，程序只是一些预先设定好的代码和数据，进程是一个随时都可能发生变化的、动态的、使用系统运行资源的程序。程序是静态的，而进程是动态的。一个程序可以启动多个进程。和进程联系在一起的不仅有进程的指令和数据，而且还有当前的指令指针、所有的 CPU 寄存器以及用来保存临时数据的堆栈等，所有这些都随着程序指令的执行在变化。,Linux操作系统包括三种不同类型的进程，每种类型的进程都有自己的特点和属性。(1)交互进程由shell启动的进程。交互进程既可以在前台运行，也可以在后台运行。(2)批处理进程这种进程和终端没有联系，是一个进程序列。(3)监控进程（也称守护进程）Linux系统启动时启动的进程，并在后台运行。上述三种进程各有各的作用，使用场合也有所不同。,5.1.1 Linux 进程管理的数据结构,Linux是一个多任务的操作系统，在同一个时间内，可以有多个进程同时执行。由于单CPU计算机实际上在一个时间片断内只能执行一条指令，Linux使用了一种称为“进程调度（process scheduling）”的机制。首先为每个进程指派一定的运行时间，然后依照某种规则，从众多进程中挑选一个投入运行，其他的进程暂时等待，当正在运行的那个进程时间耗尽，或执行完毕退出，或因某种原因暂停，Linux就会重新进行调度，挑选下一个进程投入运行。因为每个进程占用的时间片都很短，在用户的角度看，就好像多个进程同时运行一样。,进程在运行过程中，要使用许多计算机资源，例如 CPU、内存、文件等。同时可能会有多个进程使用同一个资源，因此操作系统要跟踪所有的进程及其所使用的系统资源，以便能够管理进程和资源。在Linux中，每个进程在创建时都会被分配一个数据结构，称为进程控制块（Process Control Block，PCB）。PCB中包含了很多重要的信息，供系统调度和进程本身执行使用，其中最重要的是进程ID（process ID，PID），进程ID也被称作进程标识符，是一个非负的整数，在Linux操作系统中唯一地标志一个进程。在最常使用的i386架构（即PC使用的架构）上，PID的变化范围是一个非负整数0-32767，这也是所有可能取到的进程ID。每个进程的进程ID各不相同。可使用ps命令看看当前系统中有多少进程在运行。除标题外，每一行都代表一个进程。在各列中，PID一列代表了各进程的进程ID，command一列代表了进程的名称或在shell中调用的命令行。,Linux 中的每个进程有自己的虚拟地址空间，操作系统的一个最重要的基本管理目的，就是避免进程之间的互相影响。但有时用户也希望能够利用两个或多个进程的功能完成同一任务，为此，Linux 提供许多机制，利用这些机制，进程之间可以进行通讯并共同完成某项任务，这种机制称为“进程间通讯（Interprocess Communication,IPC）”。信号和管道是常见的两种 IPC 机制，但 Linux 也提供其他 IPC 机制。一般来说，Linux下的进程包含以下几个关键要素：有一段可执行程序；有专用的系统堆栈空间；内核中有它的控制块（进程控制块），描述进程所占用的资源，这样，进程才能接受内核的调度；具有独立的存储空间。,Linux 内核利用一个数据结构task_struct来代表一个进程，代表进程的数据结构指针形成了一个 task 数组（在Linux 中，任务和进程是两个相同的术语），这种指针数组有时也成为指针向量。这个数组的大小默认为 512，表明在 Linux 系统中能够同时运行的进程最多可有 512。当建立新进程的时候，Linux 为新的进程分配一个 task_struct 结构，然后将指针保存在 task 数组中。task_struct 结构中包含了许多字段，按照字段功能，可分成如下几类：,(1)标识号。系统通过进程标识号唯一识别一个进程，但进程标识号并不是进程对应的 task_struct 结构指针在 task 数组中的索引号。另外，一个进程还有自己的用户和组标识号，系统通过这两个标识号判断进程对文件或设备的访问权。(2)状态信息。一个 Linux 进程可有如下几种状态：运行、等待、停止和僵死。(3)调度信息。调度程序利用该信息完成进程之间的切换。(4)有关进程间通讯的信息。系统利用这一信息实现进程间的通讯。(5)进程链信息。在 Linux 系统中，除初始化进程之外，任何一个进程都具有父进程。每个进程都是从父进程中“克隆”出来的。进程链则包含进程的父进程指针、和该进程具有相同父进程的兄弟进程指针以及进程的子进程指针。另外，Linux 利用一个双向链表记录系统中所有的进程，这个双向链表的根就是 init 进程。利用这个链表中的信息，内核可以很容易地找到某个进程。,(6)时间和定时器。系统在这些字段中保存进程的建立时间，以及在其生命周期中所花费的 CPU 时间，这两个时间均以 jiffies 为单位。该时间由两部分组成，一是进程在用户模式下花费的时间，二是进程在系统模式下花的时间。Linux 也支持和进程相关的定时器，应用程序可通过系统调用建立定时器，当定时器到期，操作系统会向该进程发送 sigalrm信号。(7)文件系统信息。进程可以打开文件系统中的文件，系统需要对这些文件进行跟踪。系统使用这类字段记录进程所打开的文件描述符信息。另外，还包含指向虚拟文件系统（Virtual File Systems，VFS）两个索引节点的指针，这两个索引节点分别是进程的主目录以及进程的当前目录。索引节点中有一个引用计数器，当有新的进程指向某个索引节点时，该索引节点的引用计数器会增加计数。未被引用的索引节点的引用计数为 0，因此，当包含在某个目录中的文件正在运行时，就无法删除这一目录，因为这一目录的引用计数大于0。,(8)和进程相关的上下文信息。如前所述，进程可被看成是系统状态的集合，随着进程的运行，这一集合发生变化。进程上下文就是用来保存系统状态的 task_struct 字段。当调度程序将某个进程从运行状态切换到暂停状态时，会在上下文中保存当前的进程运行环境，包括 CPU 寄存器的值以及堆栈信息；当调度程序再次选择该进程运行时，则会从进程上下文信息中恢复进程的运行环境。,5.1.2 标识符信息,和所有的 Unix 系统一样，Linux 使用用户标识符和组标识符判断用户对文件和目录的访问许可。Linux 系统中的所有文件或目录均具有所有者和许可属性，Linux 据此判断某个用户对文件的访问权限。,对一个进程而言，系统在 task_struct 结构中记录如表5.1 所示的4对标识符。,5.1.3 进程状态信息,Linux 中的进程有4种状态，如表5.2 所示。,5.1.4 文件信息,如图5.1 所示，系统中的每个进程有两个数据结构用于描述进程与文件相关的信息。其中，fs_struct 描述了上面提到的指向VFS 两个索引节点的指针，即 root 和 pwd。另外，这个结构还包含一个 umask 字段，它是进程创建文件时使用的默认模式，可通过系统调用修改这一默认模式。另一个结构为files_struct，它描述了当前进程所使用的所有文件信息。从图中可以看出，每个进程能够同时拥有 256 个打开的文件，fs0 到 fs255 就是指向这些 file 结构的指针。文件的描述符实际就是 fs 指针数组的索引号。,图5.1 进程的文件信息,在 file 结构中，f_mode 是文件的打开模式，只读、只写或读写；f_pos 是文件的当前位置；f_inode 指向 VFS 中该文件的索引节点；f_op 包含了对该文件的操作例程集。利用 f_op，可以针对不同的文件定义不同的操作函数，例如一个用来向文件中写数据的函数。Linux 利用这一抽象机制，实现了管道这一进程间通讯机制。这种抽象方法在 Linux 内核中很常见，通过这种方法，可使特定的内核对象具有类似 C+对象的多态性。Linux 进程启动时，有三个文件描述符被打开，它们是标准输入、标准输出和错误输出，分别对应 fs 数组的三个索引，即 0、1和2。如果启动时进行输入输出重定向，则这些文件描述符指向指定的文件而不是标准的终端输入/输出。每当进程打开一个文件时，就会利用files_struct 的一个空闲 file 指针指向打开的文件描述结构 file。对文件的访问通过 file 结构中定义的文件操作例程和虚拟文件系统（Virtual File System，VFS）的索引节点信息来完成。,5.1.5 虚拟内存,进程的虚拟内存包含了进程所有的可执行代码和数据。运行某个程序时，系统要根据可执行映像中的信息，为进程代码和数据分配虚拟内存；进程在运行过程中，可能会通过系统调用动态申请虚拟内存或释放已分配的内存，新分配的虚拟内存必须和进程已有的虚拟地址链接起来才能使用。Linux 进程可以使用共享的程序库代码或数据，因此，共享库的代码和数据也需要链接到进程已有的虚拟地址中。Linux系统利用了需求分页机制来避免对物理内存的过分使用。因为进程可能会访问当前不在物理内存中的虚拟内存，这时操作系统将通过对处理器的页故障处理装入内存页。系统为此需要修改进程的页表，以便标志虚拟页是否在物理内存中，同时，Linux 还需要知道进程地址空间中任何一个虚拟地址区域的来源和当前所在位置，以便能够装入物理内存。,图5.2 进程的虚拟内存示意,Linux 采用了比较复杂的数据结构跟踪进程的虚拟地址。在进程的 task_struct 结构中包含一个指向 mm_struct 结构的指针。进程的 mm_struct 则包含装入的可执行映像信息以及进程的页表指针。该结构还包含有指向 vm_area_struct 结构的几个指针，每个 vm_area_struct 代表进程的一个虚拟地址区域。图5.2 是某个进程的虚拟内存简化布局以及相应的进程数据结构。从图中可以看出，系统以虚拟内存地址降序排列 vm_area_struct。每个虚拟内存区域可能来源不同，有的可能来自映像，有的可能来自共享库，而有的则可能是动态分配的内存区。因此，Linux 利用了虚拟内存处理例程（vm_ops）来抽象对不同来源虚拟内存的处理方法。,在进程的运行过程中，Linux 要经常为进程分配虚拟地址区域，或者因为从交换文件中装入内存而修改虚拟地址信息，因此，vm_area_struct 结构的访问时间就成了性能的关键因素。除链表结构外，Linux 还利用 AVL（Adelson-Velskii and Landis）树组织 vm_area_struct。通过这种树结构，Linux 可以快速定位某个虚拟内存地址，但在该树中插入或删除节点需要花费较多的时间。当进程利用系统调用动态分配内存时，Linux 首先分配一个 vm_area_struct 结构，并链接到进程的虚拟内存链表中，当后续的指令访问这一内存区域时，因为 Linux 尚未分配相应的物理内存，因此处理器在进行虚拟地址到物理地址的映射时会产生页故障，当 Linux 处理这一页故障时，就可以为新的虚拟内存区分配实际的物理内存。,5.1.6 时间和定时器,Linux 保存一个指向当前正在运行的进程的task_struct 结构的指针，即 current。每当产生一次实时时钟中断（又称时钟周期），Linux 就会更新 current 所指向的进程的时间信息，如果内核当前代表该进程执行任务（例如进程调用系统调用时），那么系统就把进程在系统模式下花费的时间作为时间记录，否则将进程在用户模式下花费的时间作为时间记录。,除了为进程记录其消耗的 CPU 时间外，Linux 还支持和进程相关的间隔定时器。当定时器到期时，会向定时器的所属进程发送信号。进程可使用三种不同类型的定时器来给自己发送相应的信号，如表5.3 所示。,Linux 对 Virtual 和 Profile 定时器的处理是相同的，在每个时钟中断，定时器的计数值减 1，直到计数值为 0 时发送信号。Real 定时器的处理比较特殊。,5.1.7 关于线程,和进程概念紧密相关的概念是线程。线程可看成是进程中指令的不同执行路线。例如，常见的字处理程序中，主线程处理用户输入，而其他并行运行的线程在必要时可在后台保存用户的文档。与进程相关的基本要素有：代码、数据、堆栈、文件 I/O和虚拟内存信息等，因此，系统对进程的处理要花费更多的开支，尤其在进行进程调度时。利用线程则可以通过共享这些基本要素而减轻系统开支，因此，线程也被称为“轻量级进程”。许多流行的多任务操作系统均支持线程。,线程有“用户线程”和“内核线程”之分。所谓用户线程是指不需要内核支持而在用户程序中实现的线程，这种线程甚至在象 DOS 这样的操作系统中也可实现，但线程的调度需要用户程序完成，类似于 Windows 3.x 的协作式多任务。另外一种则需要内核的参与，由内核完成线程的调度。这两种模型各有其优缺点：用户线程不需要额外的内核开支，但是当一个线程因 I/O 而处于等待状态时，整个进程就会被调度程序切换为等待状态，其他线程得不到运行的机会；而内核线程则没有这个限制，但却占用了更多的系统开支。Linux 支持内核空间的多线程，读者也可以从 Internet 上下载一些用户级的线程库。,Linux 的内核线程和其他操作系统的内核实现不同。大多数操作系统单独定义线程，从而增加了内核和调度程序的复杂性；而 Linux 则将线程定义为“执行上下文”，实际只是进程的另外一个执行上下文而已。这样，Linux 内核只需区分进程，只需要一个进程/线程数组，而调度程序仍然是进程的调度程序。Linux 的克隆（clone）系统调用可用来建立新的线程。,5.1.8 会话和进程组,在Unix系统中，父进程创建子进程，子进程可以再创建新进程，形成一定的层次，称为“进程组”。一个或多个进程可以合起来构成一个进程组（process group），一个或多个进程组可以合起来构成一个会话（session）。这样，就有了对进程进行批量操作的能力，例如通过向某个进程组发送信号以实现向该组中的每个进程发送信号。Linux 内核通过维护会话和进程组而管理多用户进程。如图5.3 所示，每个进程是一个进程组的成员，而每个进程组又是某个会话的成员。一般而言，当用户在某个终端上登录时，一个新的会话就开始了。进程组由组中的领头进程标识，领头进程的进程标识符就是进程组的组标识符。类似地，每个会话也对应有一个领头进程。,同一会话中的进程通过该会话的领头进程和一个终端相连，该终端作为这个会话的控制终端。一个会话只能有一个控制终端，而一个控制终端只能控制一个会话。用户通过控制终端，可以向该控制终端所控制的会话中的进程发送键盘信号。同一会话中只能有一个前台进程组，属于前台进程组的进程可从控制终端获得输入，而其他进程均是后台进程，可能分属于不同的后台进程组。,图5.3 会话和进程、进程组,5.2 进程的创建和进程调度5.2.1 进程的创建,第一个进程在系统启动时创建，当系统启动的时候它运行在核心态，这时，只有一个进程：初始化进程。象所有其他进程一样，初始进程有一组用堆栈、寄存器等等表示的机器状态。当系统中的其他进程创建和运行的时候这些信息存在初始进程的task_struct数据结构中。在系统初始化结束的时候，系统初始化结束时，初始进程启动一个内核线程init，而自己则处于空循环状态。当系统中没有可运行的进程时，调度程序会运行这个空闲的进程。这个空闲进程的task_struct是唯一的不是动态分配而是在核心连接的时候静态定义的，为了不至于混淆，叫做init_task。,init 内核线程/进程的标识号为 1，它是系统的第一个真正进程。它负责初始的系统设置工作，例如打开控制台，挂装文件系统等。然后，init 进程执行系统的初始化程序，这一程序可能是/etc/init、/bin/init 或/sbin/init。init 程序将/etc/inittab 当作脚本文件建立系统中新的进程，这些新的进程又可以建立新进程。例如，getty 进程可建立 login 进程来接受用户的登录请求。,图5.4 父进程和子进程共享打开的文件,新的进程通过克隆旧的程序（当前程序）而建立。fork 和 clone 系统调用可用来建立新的进程。这两个系统调用结束时，内核在系统的物理内存中为新的进程分配新的 task_struct 结构，同时为新进程要使用的堆栈分配物理页。Linux 还会为新的进程分配新的进程标识符。然后，新 task_struct 结构的地址保存在 task 数组中，而旧进程的 task_struct 结构内容被复制到新进程的 task_struct 结构中。在克隆进程时，Linux 允许两个进程共享相同的资源。可共享的资源包括文件、信号处理程序和虚拟内存等。当某个资源被共享时，该资源的引用计数值会增加 1，从而只有两个进程均终止时，内核才会释放这些资源。图5.4 说明了父进程和子进程共享打开的文件。,系统对进程虚拟内存的克隆过程则更加巧妙。新的 vm_area_struct 结构、新进程自己的 mm_struct 结构以及新进程的页表必须在一开始就准备好，但这时并不复制任何虚拟内存。如果旧进程的某些虚拟内存在物理内存中，而有些在交换文件中，那么虚拟内存的复制将会非常困难和费时。Linux 采用了称为“写时复制”的技术，只有当两个进程中的任意一个向虚拟内存中写入数据时才复制相应的虚拟内存；而没有写入的任何内存页均可以在两个进程之间共享。代码页实际总是可以共享的。为实现“写时复制”技术，Linux 将可写虚拟内存页的页表项标志为只读。当进程要向这种内存页写入数据时，处理器会发现内存访问控制上的问题（向只读页中写入），从而导致页故障。于是，操作系统可捕获这一被处理器认为是“非法的”写操作而完成内存页的复制。最后，Linux 还要修改两个进程的页表以及虚拟内存数据结构。,进程终止条件有如下几种：（1）进程运行结束，正常退出（主动终止）；（2）发生可预料的错误，报错退出（主动终止）；（3）发生严重错误，进程异常终止（被动终止）；（4）被其他进程终止（被动终止）。,5.2.2 进程的管理和调度,Linux 是一个多任务操作系统，它要保证 CPU 时刻保持在使用状态，如果某个正在运行的进程等待外部设备完成工作（例如等待打印机完成打印任务），这时，操作系统就可以选择其他进程运行，从而保持 CPU 的最大利用率。这就是多任务的基本思想，进程之间的切换由调度程序完成。不同用途的系统其调度算法的目标有共性，也有各自独有的倾向。例如批处理系统的目标主要是增大每小时作业量（吞吐量），降低作业提交和终止之间的时间（周转时间），CPU利用率（保持CPU总在工作）；而交互式系统要求对用户要求做出快速反应（响应时间）和满足用户期望（均衡）；实时系统则要求不丢失数据（工作低限），在多媒体系统中避免降低媒体质量（可预见性）等。,无论是什么系统，系统共同的目标都是：（1）公平给每个进程分配相同的CPU时间；（2）坚持保证制定的策略完满执行；（3）平衡保证系统的各个部分都在工作。1.i386体系的进程管理和调度 Intel 在i386体系的设计中考虑到了进程的管理和调度，并从硬件上支持任务间的切换。为此目的，Intel在i386系统结构中增设了一种新段“任务状态段”TSS（Task Status Segment）。一个TSS虽然说像代码段、数据段等一样也是一个段，实际上却是一个104字节的数据结构，用以记录一个任务的关键性的状态信息。像其他段一样，TSS也要在段描述表中有个表项。不过TSS只能在全局描述符表GDT（Global Describtor Table）中，而不能放在任何一个局部描述符表LDT（Local Describtor Table）中或中断描述表IDT（Interrupt Describer Table）中。若通过一个段选择项访问一个TSS，而选择项中的TI位为1，就会产生一次GP异常。,另外，CPU中还增设一个任务寄存器TR,指向当前任务的TSS。相应地，还增加了一条指令LTR对TR寄存器进行装入操作。像CS和DS寄存器一样，TR也有一个程序不可见部分，每当将一个段选择码装入到TR中时，CPU就会自动找到所选择的TSS描述项并将其装入到TR的程序不可见部分，以加速以后对该TSS段的访问。在IDT表中，除了中断门、陷阱门和调用门以外，还定义了一种任务门。任务门中包含一个TSS段选择码。当CPU因中断而穿过一个任务门时，就会将任务门中的选择码自动装入TR，使TR指向新的TSS，并完成任务的切换。CPU还可以通过JMP和CALL指令实现任务切换，当跳转或调用的目标段实际上指向GDT表中的一个TSS描述项时，就会引起一次任务切换。,2.Linux系统对进程状态管理的实现机制 从系统内核的角度来看，一个进程仅仅是进程控制表（process table）中的一项。在Linux中，每个进程用一个task_struct的数据结构来表示，进程控制表中的每一项都是一个task_struct 结构，用来管理系统中的进程。在include/Linux/sched.h中定义的task_struct结构中存储各种低级和高级的信息，包括从一些硬件设备的寄存器拷贝到进程的工作目录的链接点。Task向量表是指向系统中每一个task_struct数据结构的指针的数组。这意味着系统中的最大进程数受到Task向量表的限制，默认值是512。Linux可以在这个表中查到系统中的所有的进程。操作系统初始化后，建立了第一个task_struct数据结构INIT_TASK。当新的进程创建时，从系统内存中分配一个新的task_struct，并增加到Task向量表中。为了更容易查找，用current指针指向当前运行的进程。,每个在task_struct结构中登记的进程都有相应的进程状态和进程标志，是进行进程调度的进程调度的两个重要的数据项。进程在执行了相应的进程调度操作后，会由于某些原因改变自身的状态和标志，也就是改变state和flags这两个数据项。进程的状态不同、标志位不同对应了进程可以执行不同操作。struct task_struct.volatile long state;/-1 unrunnable,0 runnable,0 stopped unsigned long flags;/per process flags,defined below.；,在及以后版本的sched.h中定义了进程的六种状态，十三种标志。各个标志位的代表着不同含义，对应着不同调用。/进程状态#define TASK_RUNNING 0#define TASK_INTERRUPTIBLE 1#define TASK_UNINTERRUPTIBLE 2#define TASK_ZOMBIE 4#define TASK_STOPPED 8#define TASK_SWAPPING 16,进程控制表既是一个数组，又是一个双向链表，同时又是一个树。其物理实现是一个包括多个指针的静态数组。此数组的长度保存在include/Linux/tasks.h 定义的常量NR_TASKS中，其默认值为128，数组中的结构则保存在系统预留的内存页中。链表是由next_task 和prev_task两个指针实现的，而树的实现则比较复杂。系统启动后，内核通常作为某一个进程的代表。一个指向task_struct的全局指针变量current用来记录正在运行的进程。变量current只能由kernel/sched.c中的进程调度改变。当系统需要查看所有的进程时，则调用for_each_task，这将比系统搜索数组的速度要快得多。,3.竞争条件，Racing Conditions 在图5.5中，一个Spooler目录下有许多槽，编号为0、1、2、3，槽中存放要打印文件的文件名。设置了两个共享变量：out指明下一个被打印的文件，in指向目录中下一个空闲槽，这两个变量保存于所有进程都可以访问的文件中。正常的进程访问过程是：读取in的值，将文件名存于相应槽中，将in的值加1。,图5.5 竞争条件（Racing Conditions）,在某一时刻，0-3号槽为空（其中的文件打印完毕），4-6号槽被占用（其中文件等待打印）。此时，有两个进程（进程A和进程B）决定要打印文件（A.txt和B.txt），这时就可能发生以下的情况。进程A处于运行态，读到in的值为7，正当进程A准备将A.txt的文件名放到7号槽时发生了进程切换，进程B开始运行；进程B运行正常，读取in的值为7（尚未被进程A更改），将文件名B.txt存入7号槽，将in的值改为8；当进程A再次运行时，in的值已经改为8，但A会从上次中止的地方继续运行，这意味着从A的角度看in的值仍为7，于是A将A.txt存入7号槽（覆盖了B.txt），然后把in的值改为8。这样，B.txt将永远不会被打印。两个或者多个进程读/写共享数据，而最后的运行结果取决于进程运行的精确时序，这样的情况称为竞争条件。在存在竞争条件时，就可能产生无法预知的错误（如上例中，A.txt和B.txt就没有正确的打印）。,4.临界区 上例的问题在于，当进程A访问共享数据的过程尚未结束时，进程B访问了数据。显然，如果在进程A访问时阻塞进程B，在进程A完成了对共享数据的访问后才允许进程B访问，就不会发生错误。凡是涉及到共享资源的情况，无论共享内存、共享文件或是其他资源，都可能引发上述错误。要避免这种错误，就必须寻找某些途径来阻止多于一个的进程同时读写共享数据。换句话说，读写必须按顺序进行。所谓互斥就是one at a time，当一个进程在访问共享数据时，其他进程无法对该数据进行任何操作。通常，把进程中访问共享数据的程序片段称为临界区。要避免竞争条件，就必须避免多个进程同时处于临界区。图5.6 是临界区的一个图示说明。,好的解决方案，需要以下4个条件：（1）任何两个进程不能同时处于临界区；（2）不应对CPU的速度和数目作任何假设；（3）临界区外的进程不得阻塞其他进程；（4）不得使进程在临界区外无休止的等待。,图5.6 临界区,5.用户进程和内核线程 一个进程只能运行在用户方式（user mode）或内核方式（kernel mode）下。用户程序运行在用户方式下，而系统调用运行在内核方式下。在这两种方式下所用的堆栈不一样：用户方式下用的是一般的堆栈，而内核方式下用的是固定大小的堆栈（一般为一个内存页的大小）。尽管Linux是一个宏内核系统，内核线程依然存在，以便并行地处理一些内核的日常工作。这些任务不占用用户空间（user memory），而仅仅使用内核空间（kernel memory）。和其他内核模块一样，它们也在高级权限（i386系统中的RING 0）下工作。内核线程是被核心线程（kernel_thread）创建的。通过调用著名的clone系统调用，例如fork系统调用的所有功能都是由它最终实现(参看arch/i386/kernel/process.c)。,5.2.3 进程的切换,虽然Intel提供了十分简洁的任务切换机制。但实际上，i386中通过JMP指令或CALL指令自动完成的任务切换的过程是一个相当复杂的过程，其执行过程长达300多个CPU时钟周期。在CPU实际上的执行过程中，有的工作在一定条件下是可以简化的；在某些条件下，一些工作则可能应按不同的方式组合。此外，任务的切换往往不是孤立的，常常与其他操作有紧密的联系。为了达到更高的效率和更大的灵活性，Linux并不直接采用i386硬件提供的任务切换机制。,Linux内核为了满足i386CPU的要求，只是在初始化的时候设置装载任务寄存器TR，使之指向一个TSS，从此以后就不再修改TR的值。也就是说，每个CPU在初始化以后就永远使用同一个TSS。同时，内核也不依靠TSS保存每个进程切换时的寄存器副本，而是将这些寄存器的副本保存在各自进程的系统空间堆栈中。Linux 中的进程有一些部分运行在用户模式，而另一些部分运行在内核模式，或称系统模式。运行模式的变化是通过系统调用完成的。Linux从用户态转移到内核态有三个途径：系统调用、中断和异常。对应的代码在entry.s中。,系统模式具有更加高级的 CPU 特权级，例如可以直接读取或写入任意的 I/O 端口，设置 CPU 关键寄存器等。Linux 中的进程无法停止当前正在运行的进程，它只能被动地等待调度程序选择它为运行进程，进程的切换操作需要高特权级的 CPU 指令，因此，只能在系统模式中进行，这样，当进行系统调用时，调度程序就有了机会进行进程切换。例如，当某个进程因为系统调用而不得不处于暂停状态时（例如等待用户键入字符），调度程序就可以选择其他的进程运行。Linux 采用抢先式的调度方法，每个进程每次最多只能运行给定的时间段，在 Linux 中为 200ms。当一个进程运行超过 200ms 时，系统选择其他的进程运行，而原有进程则等待下次运行机会。这一时间在抢先式调度中称为“时间片”。为了能够为所有的进程平等分配 CPU 资源，内核在 task_struct 结构中记录如表5.4 所示的信息。,表5.4 和进程调度相关的 task_struct 信息,当需要选择下一个运行进程时，由调度程序选择最值得运行的进程。Linux 使用了比较简单的基于优先级的进程调度算法选择新的进程。进程的切换时需要作三个层次的工作：（1）用户数据的保存：包括正文段(TEXT)、数据段(DATA，BSS)、栈段(STACK)、共享内存段(SHARED MEMORY)的保存。（2）寄存器数据的保存：包括PC(program counter，指向下一条要执行的指令的地址)、PSW(processor status word，处理机状态字)、SP(stack pointer，栈指针)、PCBP(pointer of process control block，进程控制块指针)、FP(frame pointer，指向栈中一个函数的local 变量的首地址)、AP(augument pointer，指向栈中函数调用的实参位置)、ISP(interrupt stack pointer，中断栈指针)以及其他的通用寄存器等。（3）系统层次的保存：包括proc、,虚拟存储空间管理表格和中断处理栈，以便于该进程再一次得到CPU时间片时能正常运行下去。,当调度程序选择了新的进程之后，它必须在当前进程的 task_struct 结构中保存和该进程相关的 CPU 寄存器和其他有关指令执行的上下文信息，然后从选定进程的 task_struct 结构中恢复 CPU 寄存器以及上下文信息，新的进程就可以继续在 CPU 中执行了。对于新建的进程，其 task_struct 结构被置为初始的执行上下文，当调度进程选择这一新建进程时，首先从 task_struct 结构中恢复 CPU 寄存器，CPU 的指令计数寄存器（PC）恰好是该进程的初始执行指令地址，这样，新建的进程就可以从头开始运行了。调度程序在如下几种情况下运行：当前进程处于等待状态而放入等待队列时；某个系统调用要返回到用户模式之前，这是因为系统调用结束时，当前进程的 counter 值可能刚好为 0。下面是调度程序每次运行时要完成的任务：,（1）调度程序运行底层半处理程序（bottom half handler）处理调度程序的任务队列。这些处理程序实际是一些内核线程。（2）在选择其他进程之前，必须处理当前进程。如果当前进程的调度策略为循环赛，则将当前进程放到运行队列的尾部；如果该进程是可中断的，并且自上次调度以来接收到信号，则任务状态设置为运行；如果当前进程的 counter 值为 0，则任务状态也变为运行；如果当前进程状态为运行，则继续保持此状态；如果进程既不处于运行状态，也不是可中断的，则从运行队列中移去该进程，这表明调度程序在选择最值得运行的进程时，该进程不被考虑。,（3）调度程序在运行队列中搜索最值得运行的程序。调度程序通过比较权重来选择进程。对实时进程而言，它的权重为 counter 加 1000；对一般进程而言，权重为 counter。因此，实时进程总是会被认为是最值得运行的进程。如果当前进程的优先级和其他可运行进程一致，则因为当前进程至少已花费了一个时间片，因此，总处于劣势。如果许多进程的优先级一样，则调度程序选择运行队列中最靠前的进程，这实际就是“循环赛”调度。（4）如果最值得运行的进程不是当前进程，就需要交换进程（或切换进程）。进程交换的作用是保存当前进程的运行上下文，同时恢复新进程的运行上下文。交换的具体细节和CPU 类型有关，但需要注意的是，交换进程时调度程序运行在当前进程的上下文中，另外，调度程序还需要设置某些关键的 CPU 寄存器并刷新硬件高速缓存。,Linux 内核已具备在对称多处理系统SMP（symmetric multiprocessing）上运行的能力。在多处理器系统中，每个处理器都在运行着进程。当运行在某个处理器上的进程耗尽其时间片，或者该进程处于等待状态时，该处理器将单独运行调度程序来选择新的进程。每个处理器有一个自己的空闲进程，而每个处理器也有自己的当前进程。为了跟踪每个处理器的空闲进程和当前进程，进程的 task_struct 中包含了正在运行该进程的处理器编号（processor 字段），以及上次运行该进程的处理器编号（last_processor 字段）。显然，当一个进程再次运行时，可由不同的处理器运行，但在不同处理器上的进程交换所需开支稍微大一些。为此，每个进程有一个 processor_musk 字段，如果该字段的第 N 位为 1，则该进程可以运行在第 N 个进程上，利用这一字段，就可以将某个进程限制在单个处理器上运行。,5.3 可执行程序,和 Unix 类似，Linux 中的程序和命令通常由命令解释器执行，这一命令解释器称为 shell。用户输入命令之后，shell 会在搜索路径（shell 变量PATH中包含搜索路径）指定的目录中搜索和输入命令匹配的映像名称。如果发现匹配的映像，shell 负责装载并执行该命令。shell 首先利用 fork 系统调用建立子进程，然后用找到的可执行映像文件覆盖子进程正在执行的 shell 二进制映像。可执行文件可以是具有不同格式的二进制文件，也可以是一个文本的脚本文件。可执行映像文件中包含了可执行代码及数据，同时也包含操作系统用来将映像正确装入内存并执行的信息。Linux 使用的最常见的可执行文件格式是可执行可连接格式（Executable and Linking Format，ELF）和 a.out。理论上，Linux 有足够的灵活性可以装入任何格式的可执行文件。,5.3.1 可执行可连接格式,可执行可连接格式（Executable and Linking Format，ELF）由 Unix 系统实验室制定。它是 Linux 中最经常使用的格式。和其他格式（例如 a.out 或 ECOFF 格式）比较，ELF 在装入内存时多一些系统开支，但是更为灵活。ELF 可执行文件包含了可执行代码和数据，通常也称