作者：孟庆昌
这一讲将深入到Linux内核中探讨其主要结构和算法，主要介绍进程和内存管理，包括进程的结构、对进程的操作、进程调度、Shell基本工作原理、进程通信、请求分页机制和存储交换等。
进程是动态的实体，每个进程在其生存期间会处于不同的状态，对系统中的资源有不同的需求，彼此间会发生直接或间接的联系。因此，系统必须有一套机制记载和管理它们的状态。
进程的结构
1．task_struct结构
Linux系统中每一个进程都包括一个名为task_struct的数据结构，它相当于“进程控制块”。每一个task_struct结构都有一个指针指向它，所有的这种指针组成系统中的一个进程向量数组task，该数组的默认值是512。在创建新进程时，Linux就从系统内存中分配一个task_struct结构，并把它加入task数组。当前正在运行的进程的task_struct结构用current指针指示。
task_struct结构包含下列几方面的信息：
◆进程状态。
◆调度信息。调度算法利用这个信息来决定系统中的哪一个进程需要执行。
◆标识符。系统中每个进程都有惟一的一个进程标识符(PID)。PID并不是指向进程向量的索引，仅仅是一个数字而已。每个进程同时还包括用户标志符（UID）和用户组标识符(GID)，用来确定进程对系统中文件和设备的存取权限。
◆内部进程通信。Linux系统支持信号、管道、信号量等内部进程通信机制。
◆链接信息。在Linux系统中，每个进程都和其它进程存在联系。除初始化进程外，每个进程都有父进程。该链接信息包括指向父进程、兄弟进程和子进程的指针。
◆时间和计时器。内核要记录进程的创建时间和进程运行所占用CPU的时间。Linux 系统支持进程的时间间隔计时器。
◆文件系统。进程在运行时可以打开和关闭文件。task_struct结构中包括指向每个打开文件的文件描述字的指针，并且包括两个指向VFS(虚拟文件系统)索引节点的指针。第一个索引节点是进程的根目录，第二个节点是当前的工作目录。两个VFS索引节点都有一个计数字段用来指向节点的进程数。
◆虚拟内存。大多数进程都使用虚拟内存空间。Linux系统必须了解如何将虚拟内存映射到系统的物理内存。
◆处理器信息。每个进程运行时都要使用处理器的寄存器及堆栈等资源。当一个进程挂起时，所有有关处理器的内容都要保存到进程的task_struct中。当进程恢复运行时，所有保存的内容再装入到处理器中。
秦靖 于 2005-10-07 00:05:42发表:
支持
artiomgy 于 2005-10-06 18:47:39发表:
System V IPC机制
为了和其它Unix系统保持兼容，Linux系统也支持Unix System V版本中的三种进程间通信机制，它们是消息通信、共享内存和信号量。这三种通信机制使用相同的授权方法。进程只有通过系统调用将标识符传递给核心之后，才能存取这些资源。
(1)一个进程可以通过系统调用建立一个消息队列，然后任何进程都可以通过系统调用向这个队列发送消息，或者从队列中接收消息，从而实现进程间的消息传递。
(2)一个进程可以通过系统调用设立一片共享内存区，然后其它进程就可以通过系统调用将该存储区映射到自己的用户地址空间中。随后，相关进程就可以像访问自己的内存空间那样读/写该共享区的信息。
(3)信号量机制可以实现进程间的同步，保证若干进程对共享的临界资源的互斥操作。简单说来，信号量是系统内的一种数据结构，它的值代表着可使用资源的数量，可以被一个或多个进程进行检测和设置。对于每个进程来说，检测和设置操作是不可中断的，分别对应于操作系统理论中的P和V操作。
System V IPC中的信号量机制是对传统信号量机制的推广，实际是“用户空间信号量”。它由内核支持，在系统空间实现，但可由用户进程直接使用。
artiomgy 于 2005-10-06 18:47:15发表:
管道文件
管道是Linux中最常用的IPC机制。与Unix系统一样，一个管道线就是连接两个进程的一个打开文件。例如：
ls | more
在执行这个命令行时要创建一个管道文件和两个进程：“|”对应管道文件，命令ls对应一个进程，它向该文件中写入信息，称作写进程；命令more对应另一个进程，它从文件中读出信息，称作读进程。
由系统自动处理二者间的同步、调度和缓冲。管道文件允许两个进程按先入先出（FIFO）的方式传送数据，而它们可以彼此不知道对方的存在。管道文件不属于用户直接命名的普通文件，它是利用系统调用pipe( )创建的、在同族进程间进行大量信息传送的打开文件。图11示出管道的实现机制。
图11 管道文件的实现机制
每个管道只有一个页面用作缓冲区，该页面是按环形缓冲区的方式来使用的。就是说，每当读或写到页面的末端就又回到页面的开头。
由于管道的缓冲区只限于一个页面，所以，当写进程有大量数据要写时，每当写满了一个页面就要睡眠等待；等到读进程从管道中读走一些数据而腾出一些空间时，读进程会唤醒写进程，写进程就会继续写入数据。对读进程来说，缓冲区中有数据就读出，如果没有数据就睡眠，等待写进程向缓冲区中写数据；当写进程写入数据后，就唤醒正在等待的读进程。
Linux系统也支持命名管道，也就是FIFO管道，因为它总是按照先入先出的原则工作。FIFO管道与一般管道不同，它不是临时的，而是文件系统的一部分。当用mkfifo命令创建一个命名管道后，只要有相应的权限，进程就可以打开FIFO文件，对它进行读或写。
artiomgy 于 2005-10-06 18:46:23发表:
3. 进程对信号可采取的处理方式
当发生上述事件后，系统可以产生信号并向有关进程传送。进程彼此间也可用系统提供的系统调用（如kill( ) ）发送信号。
除了内核和超级用户外，并不是每个进程都可以向其它进程发送信号，普通进程只能向具有相同uid和gid的进程发送信号，或者向相同进程组中的其它进程发送信号。信号要记入相应进程的task_struct结构中signal的适当位，以备接收进程检测和处理。
进程接到信号后，在一定时机（如中断处理末尾）做相应处理，可采取以下处理方式：
(1)忽略信号。进程可忽略收到的信号，但SIGKILL和SIGSTOP信号不能被忽略。
(2)阻塞信号。进程可以选择对某些信号予以阻塞。
(3)由进程处理该信号。用户在trap命令中可以指定处理信号的程序，从而进程本身可在系统中标明处理信号的处理程序的地址。当发出该信号时，就由标明的处理程序进行处理。
(4)由系统进行默认处理。如上所述，系统内核对各种信号(除用户自定义之外)都规定了相应的处理程序。在默认情况下，信号就由内核处理，即执行内核预定的处理程序。
每个进程的task_struct结构中都有一个指针sig，它指向一个signal_struct结构。该结构中有一个数组action[ ],其中的元素确定了当进程接收到一个信号时应执行什么操作。
4. 对信号的检测和处理流程
对信号的检测和响应是在系统空间进行的。通常进程检测信号的时机是，第一，从系统空间返回用户空间之前，即当前进程由于系统调用、中断或异常而进入系统空间以后，进行相应的处理工作。处理完后，要从系统空间中退出，在退出之前进行信号检测。第二，进程刚被唤醒的时候，即当前进程在内核中进入睡眠以后刚被唤醒，要检测有无信号，如存在信号就会提前返回到用户空间。
信号的检测与处理的过程如图10所示，图中的①～⑤标出处理流程的顺序。从图中可以看出，信号的检测是在系统空间中进行，而对信号的处理却是在用户空间中执行。
图10 信号的检测与处理流程示意
artiomgy 于 2005-10-06 18:45:37发表:
进程通信
系统中的进程和系统内核之间，以及各个进程之间需要相互通信，以便协调彼此间的活动。Linux系统支持多种内部进程通信机制(IPC),最常用的方式是信号、管道及Unix系统支持的System V IPC机制(即消息通信、共享数据段和信号量)。
限于篇幅，这里主要介绍其基本的实现思想。
1．信号机制
信号(Signal，亦称作软中断)机制是在软件层次上对中断机制的一种模拟。异步进程可以通过彼此发送信号来实现简单通信。系统预先规定若干个不同类型的信号（如x86平台中Linux内核设置了32种信号，而现在的Linux和POSIX.4定义了64种信号），表示发生了不同的事件，每个信号对应一个编号。
运行进程当遇到相应事件或出现特定要求时（如进程终止或运行中出现非法指令、地址越界等某些错误），就把一个信号写到相应进程task_struct结构的signal位图(表示信号的整数)中。接收信号的进程在运行过程中要检测自身是否收到了信号，如果已收到信号，则转去执行预先规定好的信号处理程序。处理之后，再返回原先正在执行的程序。进程之间利用信号机制实现通信的过程如图9所示。
图9 利用信号实现进程间通信
这种处理方式与硬件中断的处理方式有不少相同之处，但是二者又是不同的。因为信号的设置、检测等都是软件实现的。信号处理机构是系统中围绕信号的产生、传送和处理而构成的一套机构。该机构通常包括三部分：
(1)信号的分类、产生和传送；
(2)对各种信号预先规定的处理方式；
(3)信号的检测和处理。
2. 信号分类
如上所述，信号分类随系统而变，可多可少。通常可分为进程终止、进程执行异常（如地址越界、写只读区、用户执行特权指令或硬件错误）、系统调用出错（如所用系统调用不存在、pipe文件有写者无读者等）、报警信号及与终端交互作用等。系统一般也给用户自己留出定义信号的编号。
artiomgy 于 2005-10-06 18:44:57发表:
当系统启动时，交换守护进程由内核的init(初始化)进程启动。它在一些简单的初始化操作之后便进入无限循环，在每次循环的末尾会进入睡眠。内核在一定时间以后又会唤醒并调度它继续运行，这时它就又回到该无限循环开始的地方。
通常间隔时间是1秒钟，但在有些情况下内核也会在不到1秒钟的时间内就把它唤醒，从而kswapd会提前返回，而开始新的一轮循环。
交换守护进程所做的工作主要分为两部分。第一部分是在发现可用的内存页面已经短缺的情况下，则找出若干不常用的内存页面，使它们从活跃状态(至少有一个进程的页表项指向该页面)变为不活跃状态(不再有任何进程的页表项指向该页面)，为页面换出作好准备。
第二部分是每次都要执行的工作，把那些已经处于不活跃状态的“脏”页面(即内存页的内容与盘上页面的内容不一致)写入交换设备，使它们成为不活跃“干净”页面(内存页内容与盘上页面内容一致)继续缓冲，或者进一步回收一些内存页，使之成为空闲的内存页。
为了决定是否需要回收一些内存页，系统中设置两个量分别表示上限值和下限值。如果空闲的内存页数量大于上限值，则交换守护进程就不做任何事情，而进入睡眠状态；如果系统中的空闲内存页数量低于上限值、甚至低于下限值，则交换进程将用以下三种办法减少系统正在使用的内存页数：
（1）减少缓冲区和页高速缓存的大小。如果这些缓存中包含的某些页面不再需要，则把它们释放，使之成为空闲的内存页。
（2）把System V的共享内存页(实际是一种进程间通信机制)换到交换文件中，从而释放出物理内存。
（3）将页面换出物理内存或直接将它们抛弃。kswapd进程首先选择可交换的进程，然后把该进程一部分页面换出内存(如果它们是“脏”的)，大部分页面可直接抛弃--因为其中的内容可从磁盘文件中直接获取。
上述两种情况下的那些物理页面都成为可供进程分配使用的空闲内存页。作为交换空间的交换文件实际就是普通文件，但它们所占的磁盘空间必须是连续的，即文件中不能存在“空洞”(其中没有任何数据，但也无法写入)。
因为进程使用交换空间是临时性的，速度是关键性问题，系统一次进行多个盘块I/O传输比每次一块、多次传输的速度要快，所以核心在交换设备上是分配一片连续空间，而不管碎片的问题。另外，交换文件必须保存在本地硬盘上。
交换分区和其它分区没有本质区别，可像建立其它分区一样建立交换分区，但交换分区中不能包含任何文件系统。通常，最好将交换分区的类型设置为Linux Swap。
artiomgy 于 2005-10-06 18:44:38发表:
free_area数组的每项有两个成分：一个是双向链表list的指针，链表中的每个节点包含对应的空闲页组的起始内存页编号；另一个是指向map位图的指针，map中记录相应页组的分配情况。
如图所示，free_area数组的项0中包含一个空闲内存页；而项2中包含两个空闲内存页组(该链表中有两个节点)，每个页组包括四个连续的内存页，第一个页组的起始内存页编号是4，另一个页组的起始内存页编号是100。
图8 空闲内存的组织示意图
在分配内存页组时，对于分配请求如果系统有足够的空闲内存页，则Linux的页面分配程序首先在free_area数组中搜索等于要求数量的最小页组的信息，然后在对应的list双向链表中查找空闲页组；如果没有与所需数量相同的空闲内存页组，则继续查找下一个空闲页组(其大小为上一个页组的2倍)。
如果找到的页组大于所要求的页数，则把该页组分为两部分：满足所请求的部分，把它返回给调用者；剩余的部分，按其大小插入到相应的空闲页组队列中。
当释放一个页面组时，页面释放程序就会检查其上下是否存在与它邻接的空闲页组。如果有的话，则把该释放的页组与所有邻接的空闲页组合并成一个大的空闲页组，并修改有关的队列。上述内存页分配算法也称作“伙伴算法”。
内存交换
当系统中出现内存不足时，Linux内存管理子系统就需要释放一些内存页，从而增加系统中空闲内存页的数量。此任务是由内核的交换守护进程kswapd完成的。
kswapd有自己的进程控制块task_struct结构，它与其它进程一样受内核的调度。但是，它没有自己独立的地址空间，只使用系统空间，所以也把它称作线程。它的任务就是保证系统中有足够的空闲内存页。
artiomgy 于 2005-10-06 18:43:55发表:
图7中PGD表示页面目录，PMD表示中间目录，PT表示页表。一个线性的虚拟地址在逻辑上从高位到低位划分成4个位段，分别用作页面目录PGD中的下标、中间目录PMD中的下标、页表PT中的下标和物理页面(即内存块)内的位移。
这样，把一个线性地址映射成物理地址分为以下四步：
(1) 以线性地址中最高位段作下标，在PGD中找到相应的表项，该表项指向相应的PMD。
(2) 以线性地址中第二个位段作下标，在PMD中找到相应的表项，该表项指向相应的PT。
(3) 以线性地址中第三个位段作下标，在PT中找到相应的表项，该表项指向相应的物理页面(即该物理页面的起始地址)。
(4) 线性地址中的最低位段是物理页面内的相对位移量，此位移量与该物理页面的起始地址相加就得到相应的物理地址。
地址映射是与具体的CPU和MMU(内存管理单元)相关的。对于i386来说，CPU只支持两级模型，所以，实际上跳过了中间的PMD这一级。从Pentium Pro开始，允许将地址从32位提高到36位，并且在硬件上支持三级映射模型。
4. 内存页的分配与释放
当一个进程开始运行时，系统要为其分配一些内存页；而当该进程结束运行时，要释放其所占用的内存页。一般说来，Linux系统采用位图和链表两种方法来管理内存页。
利用位图可以记录内存单元的使用情况。用一个二进制位(bit)记录一个内存页的使用情况：如果该内存页是空闲的，则对应的位是1；如果该内存页已经分配出去，则对应的位是0。例如有1024KB的内存，内存页的大小是4KB，则可以用32个字节构成的位图来记录这些内存的使用情况。
分配内存时就检测该位图中的各个位，找到所需个数的连续位值为1的位图位置，进而就获得所需的内存空间。
利用链表可以记录已分配的内存单元和空闲的内存单元。采用双向链表结构将内存单元链接起来，从而可以加速空闲内存的查找或链表的处理。
Linux系统的物理内存页分配采用链表和位图相结合的方法，如图8所示。图8中，数组free_area的每一项描述某一种内存页组(即由相邻的空闲内存页构成的组)的使用状态信息。
其中，头一个元素描述孤立出现的单个内存页的信息，第二个元素描述以两个连续内存页为一组的页组的信息，第三个元素描述以四个内存页为一组的页组的信息，依此类推，页组中内存页的数量依次按2的倍数递增。
artiomgy 于 2005-10-06 18:43:35发表:
3. Linux的多级页表
在x86平台的Linux系统中，地址码采用32位，因而每个进程的虚存空间可达4GB。Linux内核将这4GB的空间分为两部分：最高地址的1GB是“系统空间”，供内核本身使用；而较低地址的3GB是各个进程的“用户空间”。
系统空间由所有进程共享。虽然理论上每个进程的可用用户空间都是3GB，但实际的存储空间大小要受到物理存储器 (包括内存及磁盘交换区或交换文件) 的限制。进程的虚存空间如图6所示。
由于Linux系统中页面大小为4KB，因此进程虚存空间要划分为1M个页面。如果直接用页表描述这种映射关系，那么每个进程的页表就要有1M个表项。很显然，用大量的内存资源来存放页表的办法是不可取的。为此，Linux系统采用三级页表的方式，如图7所示。
图6 linux进程的虚存空间
图7 三级页表地址映射示意图
artiomgy 于 2005-10-06 18:42:30发表:
(5)页表
在分页系统中允许将作业或进程的各页面离散地装入内存的任何空闲块中，这样一来就出现作业的页号连续、而块号不连续的情况。怎样找到每个页面在内存中对应的物理块呢？为此，系统又为每个进程设立一张页面映像表，简称页表。
在进程地址空间内的所有页（0～n－1）依次在页表中有一个页表项，其中记载了相应页面在内存中对应的物理块号、页表项有效标志，以及相应内存块的访问控制属性(如只读、只写、可读写、可执行)。进程执行时，按照逻辑地址中的页号去查找页表中的对应项，可从中找到该页在内存中的物理块号。然后，将物理块号与对应的页内位移拼接起来，形成实际的访问内存地址。所以，页表的作用是实现从页号到物理块号的地址映射。
2. 请求分页的基本思想
请求分页存储管理技术是在简单分页技术基础上发展起来的，二者根本区别在于请求分页提供虚拟存储器。
它的基本思想是，当要执行一个程序时才把它换入内存；但并不把全部程序都换入内存，而是用到哪一页时才换入它。这样，就减少了对换时间和所需内存数量，允许增加程序的道数。
为了表示一个页面是否已装入内存块，在每一个页表项中增加一个状态位，Y表示该页对应的内存块可以访问；N表示该页不对应内存块，即该页尚未装入内存，不能立即进行访问。
如果地址转换机构遇到一个具有N状态的页表项时，便产生一个缺页中断，告诉CPU当前要访问的这个页面还未装入内存。操作系统必须处理这个中断：它装入所要求的页面，并相应调整页表的记录，然后再重新启动该指令。
由于这种页面是根据请求而被装入的，所以这种存储管理方法叫做请求分页存储管理。通常在作业最初投入运行时，仅把它的少量几页装入内存，其它各页是按照请求顺序动态装入的，这样就保证用不到的页面不会被装入内存。
图5 请求分页存储管理示意
artiomgy 于 2005-10-06 18:41:46发表:
这种策略就使进程的虚拟地址空间映射到机器物理空间时，具有更大的灵活性，通常允许进程的大小可大于可用内存的总量，并允许更多进程同时在内存中执行。
1．请求分页机制
分页存储管理的基本方法如下：
(1)逻辑空间分页
将一个进程的逻辑地址空间划分成若干个大小相等的部分，每一部分称作页面或页。每页都有一个编号，叫做页号，页号从0开始依次编排，如0、1、2……
(2)内存空间分页
把内存也划分成与页面相同大小的若干个存储块，称作内存块或内存页面。同样，它们也进行编号，内存块号从0开始依次顺序排列：0#块、1#块、2#块……
页面和内存块的大小是由硬件确定的，它一般选择为2的若干次幂。不同机器中页面大小是有区别的。在x86平台上的Linux系统的页面大小为4KB。
(3)逻辑地址表示
在一般的分页存储管理方式中，表示地址的结构如图4所示。
地址由两个部分组成，前一部分表示该地址所在页面的页号p；后一部分表示页内位移d，即页内地址。图4中所示两部分构成的地址长度为32位，其中0～11为页内位移，即每页的大小为4KB；12～31位为页号，表示地址空间中最多可容纳1M个页面。
图4 分页技术的地址结构
(4)内存分配原则
在分页情况下，系统以内存块为单位把内存分给作业或进程，并且一个进程的若干页可分别装入物理上不相邻的内存块中。
artiomgy 于 2005-10-06 18:40:58发表:
(5)如果命令末尾有&号（后台命令符号），则终端进程不用系统调用wait4( )等待，立即发提示符，让用户输入下一个命令，转⑴。如果命令末尾没有&号，则终端进程要一直等待，当子进程（即运行命令的进程）完成处理后终止，向父进程（终端进程）报告，此时终端进程醒来，在做必要的判别等工作后，终端进程发提示符，让用户输入新的命令，重复上述处理过程。
Shell基本执行过程及父子进程之间的关系如图3所示。
图3 Shell命令执行过程
内存管理
在计算机系统中，对内存如何管理在很大程度上将影响整个系统的性能，所以，它也是关键资源。近年来，随着硬件技术和生产水平的迅速发展，内存的成本迅速下降，而容量一直不断扩大，但是，仍不能满足各种软件对存储空间急剧增长的需求。因此，对内存的有效管理仍是现代操作系统中十分重要的问题。
Linux系统采用了虚拟内存管理机制，就是交换和请求分页存储管理技术。这样，当进程运行时，不必把整个进程的映像都放在内存中，只需在内存保留当前用到的那一部分页面。当进程访问到某些尚未在内存的页面时，就由核心把这些页面装入内存。
artiomgy 于 2005-10-06 18:40:10发表:
3．调度时机
核心进行进程调度的时机有以下几种情况：(1)当前进程调用系统调用nanosleep( )或pause( )使自己进入睡眠状态，主动让出一段时间的CPU使用权；(2)进程终止，永久地放弃对CPU的使用；(3)在时钟中断处理程序执行过程中，发现当前进程连续运行的时间过长；(4)当唤醒一个睡眠进程时，发现被唤醒的进程比当前进程更有资格运行；(5)一个进程通过执行系统调用来改变调度策略或降低自身的优先权(如nice命令)，从而引起立即调度。
4．调度算法
进程调度的算法应该比较简单，以便减少频繁调度时的系统开销。Linux执行进程调度时，首先查找所有在就绪队列中的进程，从中选出优先级最高且在内存的一个进程。如果队列中有实时进程，那么实时进程将优先运行。
如果最需要运行的进程不是当前进程，那么当前进程就被挂起，并且保存它的现场所涉及的一切机器状态，包括程序计数器和CPU寄存器等，然后为选中的进程恢复运行现场。
Shell基本工作原理
Linux系统提供给用户的最重要的系统程序是Shell命令语言解释程序。它不属于内核部分，而是在核心之外，以用户态方式运行。其基本功能是解释并执行用户打入的各种命令，实现用户与Linux核心的接口。系统初启后，核心为每个终端用户建立一个进程去执行Shell解释程序。它的执行过程基本上按如下步骤：
(1)读取用户由键盘输入的命令行。
(2)分析命令，以命令名作为文件名，并将其它参数改造为系统调用execve( )内部处理所要求的形式。
(3)终端进程调用fork( )建立一个子进程。
(4)终端进程本身用系统调用wait4( )来等待子进程完成（如果是后台命令，则不等待）。当子进程运行时调用execve( )，子进程根据文件名（即命令名）到目录中查找有关文件（这是命令解释程序构成的文件），将它调入内存，执行这个程序（解释这条命令）。
artiomgy 于 2005-10-06 18:39:48发表:
进程调度
一般说来，进程既可在用户模式下运行，又可在内核模式下运行。内核模式的权限高于用户模式的权限。进程每次调用一个系统调用时，进程的运行方式都发生变化：从用户模式切换到内核模式，然后继续执行。
任何进程要想占有CPU，从而真正处于执行状态，就必须经由进程调度。进程调度机制主要涉及到调度方式、调度时机和调度策略。
1．调度方式
Linux内核的调度方式基本上采用“抢占式优先级”方式，即当进程在用户模式下运行时，不管是否自愿，在一定条件下(如时间片用完或等待I/O)，核心就可以暂时剥夺其运行而调度其它进程进入运行。但是，一旦进程切换到内核模式下运行，就不受以上限制而一直运行下去，直至又回到用户模式之前才会发生进程调度。
Linux系统中的调度策略基本上继承了Unix的以优先级为基础的调度。就是说，核心为系统中每个进程计算出一个优先权，该优先权反映了一个进程获得CPU使用权的资格，即高优先权的进程优先得到运行。
核心从进程就绪队列中挑选一个优先权最高的进程，为其分配一个CPU时间片，令其投入运行。在运行过程中，当前进程的优先权随时间递减，这样就实现了“负反馈”作用：经过一段时间之后，原来级别较低的进程就相对“提升”了级别，从而有机会得到运行。当所有进程的优先权都变为0时，就重新计算一次所有进程的优先权。
2．调度策略
Linux系统针对不同类别的进程提供了三种不同的调度策略，即SCHED_FIFO、SCHED_RR及SCHED_OTHER。其中，SCHED_FIFO适合于实时进程，它们对时间性要求比较强，而每次运行所需的时间比较短，一旦这种进程被调度开始运行后，就要一直运行到自愿让出CPU，或者被优先权更高的进程抢占其执行权为止。
SCHED_RR对应“时间片轮转法”，适合于每次运行需要较长时间的实时进程。一个运行进程分配一个时间片(如200毫秒)，当时间片用完后，CPU被另外进程抢占，而该进程被送回相同优先级队列的末尾。
SCHED_OTHER是传统的Unix调度策略，适合于交互式的分时进程。这类进程的优先权取决于两个因素，一个因素是进程剩余时间配额，如果进程用完了配给的时间，则相应优先权为0；另一个是进程的优先数nice，这是从Unix系统沿袭下来的方法，优先数越小，其优先级越高。
nice的取值范围是19～－20。用户可以利用nice命令设定进程的nice值。但一般用户只能设定正值，从而主动降低其优先级；只有特权用户才能把nice的值置为负数。进程的优先权就是以上二者之和。核心动态调整用户态进程的优先级。
这样，一个进程从创建到完成任务后终止，需要经历多次反馈循环。当进程再次被调度运行时，它就从上次断点处开始继续执行。
对于实时进程，其优先权的值是(1000＋设定的正值)，因此，至少是1000。所以，实时进程的优先权高于其它类型进程的优先权。
另外，时间配额及nice值与实时进程的优先权无关。如果系统中有实时进程处于就绪状态，则非实时进程就不能被调度运行，直至所有实时进程都完成了，非实时进程才有机会占用CPU。
后台命令（在命令末尾有&符号，如gcc f1.c& )对应后台进程（又称后台作业），后台进程的优先级低于任何交互（前台）进程的优先级。所以，只有当系统中当前不存在可运行的交互进程时，才调度后台进程运行。后台进程往往按批处理方式调度运行。
artiomgy 于 2005-10-06 18:39:17发表:
4．进程映像的更换
子进程被创建后，通常处于“就绪态”，以后被调度选中才可运行。由于创建子进程过程中，是把父进程的映像复制给子进程，所以子进程开始执行的入口地址就是父进程调用fork( )系统调用建立子进程映像时的返回地址，此时二者的映像基本相同。
如果子进程不改变其映像，就必然重复父进程的过程。为此，要改变子进程的映像，使其执行另外的特定程序（如命令所对应的程序）。
改换进程映像的工作很复杂，是由系统调用execve( )实现的，它用一个可执行文件的副本来覆盖该进程的内存空间。
可执行文件格式ELF(Executable and Linkable Format)是各种Unix系统中最为常用的可执行文件的格式。ELF可执行文件包括可执行代码和数据及文件头，如图2所示。文件头分为文件描述头和物理头，前者描述可执行文件的类别、程序的第一条指令在虚拟内存的地址、物理头的起始位移、物理头的个数等。
图2 ELF可执行文件格式示意图
物理头1描述了可执行代码的信息，如起始地址、字节数、权限标志等；物理头2描述了程序中的数据--起始地址、字节数、权限标志等。可见，可执行文件与有执行权限的文件是不同的。
execve( )系统调用的基本算法如下：
◆验证文件的可执行性，即用户有权执行它。
◆读文件头，检查它是一个可装入模块。
◆释放原有的内存空间。
◆按照可执行文件的要求分配新的内存空间，并装入内存。
artiomgy 于 2005-10-06 18:38:29发表:
在Linux操作系统中，除初始化进程外，其它进程都是用系统调用fork()和clone()创建的。调用fork()和clone()的进程是父进程，被生成的进程是子进程。
新进程是通过复制老进程或当前进程而创建的。但是，fork()和clone()二者间还存在区别：fork()是全部复制，即父进程所有的资源全部通过数据结构的复制“传”给子进程；而clone()可以将资源有选择地复制给子进程，没有被复制的数据结构则通过指针的复制让子进程共享。所以，系统调用fork()是无参数的，而clone()要有参数。
创建新进程时，系统从物理内存中为它分配一个task_struct数据结构和进程系统栈，新的task_struct结构加入到进程向量中，并为该进程指定一个惟一的PID号；然后进行基本资源复制，如task_struct数据结构、系统空间栈、页表等，对父进程的代码及全局变量不需要复制，仅通过只读方式实现资源共享。
2．进程的等待
父进程创建子进程往往让子进程替自己完成某项工作。因此，父进程创建子进程之后，通常等待子进程运行终止。父进程用系统调用wait3( )等待它的任何一个子进程终止；也可以用wait4( )等待某个特定子进程终止。
wait3( )算法如下：
◆ 如果父进程没有子进程，则出错返回。
◆ 如果发现有一个终止的子进程，则取出子进程的进程号，把子进程的CPU使用时间等加到父进程上，释放子进程占用的task_struct和系统空间栈，以供新进程使用。
◆ 如果发现有子进程，但都不处于终止态，则父进程睡眠，等待由相应信号唤醒。
3．进程的终止
在Linux系统中，进程主要是作为执行命令的单位运行的，这些命令的代码都以系统文件形式存放。当命令执行完进程希望终止时，可在其程序末尾使用系统调用exit ()。
用户进程也可使用exit来终止自己。其实现算法如下：
◆ 撤销所有的信号量。
◆ 释放其所有的资源，包括存储空间、已打开的文件、工作目录、信号处理表等。
◆ 置进程状态为“终止态”(TASK_ZOMBIE)；向它的父进程发送子进程终止的信。
◆ 执行进程调度。
artiomgy 于 2005-10-06 18:38:03发表:
2. 进程系统栈
在Linux系统中，每个进程都有一个系统栈，用来保存中断现场信息和进程进入内核模式后执行子程序(函数)嵌套调用的返回现场信息。每个进程的系统栈和task_struct数据结构之间存在紧密联系，因而二者在物理存储空间中也连在一起。如图1所示。
图1 进程的系统栈和task_struct结构
由图1中可以看出，内核在为每个进程分配task_struct结构的内存空间时，实际上是一次就分配两个连续的内存页面(共8KB)，其底部大约1KB的空间用于存放task_struct结构，而上面的大约7KB的空间用于存放进程系统空间栈。
另外，系统空间栈的大小是静态确定的，而用户空间栈可以在运行时动态扩展。
对进程的操作
进程是有“生命期”的动态过程，核心能对它们实施操作，主要包括创建进程、撤消进程、挂起进程、恢复进程、改变进程优先级、封锁进程、唤醒进程、调度进程等。
1．进程的创建
与Unix操作系统对进程的管理相似，Linux系统中各个进程构成了树型的进程族系。当系统刚刚启动时，系统运行在内核方式，内核在引导并完成了基本的初始化以后就有了系统的第一个进程(即初始化进程，实际上是内核线程)。
除此之外，所有其它的进程和内核线程都由这个原始进程或其子孙进程所创建，如系统为每个终端生成一个注册进程和一个Shell进程，分别管理用户注册和执行Shell命令解释程序。用户和系统交互作用过程中，由Shell进程为输入的命令创建若干进程，每个子进程执行一条命令。
执行命令的子进程也可再创建子进程。这棵进程树除了同时存在的进程数受到限制外，树型结构的层次也可以不断延伸。