Linux基础教程(清华课件)1

PAGE清华大学计算机基础教育课程系列教材

汤荷美董渊李莉程志锐编著Linux基础教程（1）操作系统基础2.1作业2.2进程2.3线程2.4小结习题

第2章处理机管理提高处理机（CPU）的使用率，使它尽可能处于工作状态，是操作系统管理功能的主要目标之一。在Linux系统中，提高处理机使用率的技术措施主要是多道和分时，处理机在进程之间切换，按照一定的规则轮流执行每个进程。对于单个处理机的系统，这些进程宏观上看似并行执行，而微观上来看仍然是串行执行的，这种执行方式被称为并发执行。操作系统通过并发控制机制，对处理机进行分配、调度，在保证每个进程都得到公平合理执行的同时，使系统中的各种资源得到充分的使用。本章主要围绕处理机管理展开，着重介绍进程的概念，同时也包括相关的两个基本概念：作业和线程。2.1作业作业是用户向计算机系统提交一项工作的基本单位，是用户在一次事务处理或计算过程中要求计算机所做工作的总和。作业和程序是两个相互联系而又不同的概念。如果一次业务处理可以由某一个程序完成，就是说这个业务处理只要提交这一个程序就够了，这种情况下，这个程序就是一个作业。通常，完成一次业务需要由多个程序协同完成，这时，多个程序、这些程序需要的数据以及必要的作业说明一起构成一个作业。系统通过作业说明书或者作业控制语句(JCL)控制程序和相应的数据执行，完成整个业务处理。按照对作业的处理方式，可以分为联机、批处理等作业。Linux系统中的shell提供了操作系统和用户之间的联机命令接口。Linux的shell同时提供了程序级接口。用户通过提交一个命令或一个命令序列以批处理方式执行特定的操作（详见本书第2部分）。在Linux分时批处理系统中，也可以根据对作业执行时的响应特征分为前台作业和后台作业。在多用户系统中，多个用户、不同类型的作业可能同时请求执行，控制和管理这些作业，协调它们之间的关系，就是作业调度，作业调度是处理机调度的一部分。2.2进程计算机内存中同时存放多个相互独立的已经开始运行的程序实体，大家按照某种规则轮流使用处理器，这是现代多道操作系统实现资源共享，提高系统资源利用率的主要方式。描述这些程序实体的概念就是进程。在多道情况下，每个进程独立地拥有各种必要的资源，占有处理机，独立地运行。在多道系统中，同时存在多个进程，所以当某个进程进入等待状态时，操作系统将把处理机控制权拿过来并交给其他可以运行的进程。进程之间存在着相互制约、相互依赖的约束关系。一种最糟糕的情况是所有进程都拥有部分资源，同时在等待其他进程拥有的资源，这样，大家都无法运行，进入一种永久等待的状态，这种情况称为死锁，死锁是对系统资源极大的浪费，必须设法避免。本节着重讨论现代多道操作系统中的核心概念——进程，这是理解操作系统工作原理的基础和关键。首先介绍单个进程的状态、状态转换的条件和控制原语、进程在系统中的静态描述等，接着介绍多个进程之间的约束关系，由此引出进程间通信的概念，通信是协调、解决进程间约束关系的惟一手段，这种约束关系处理不当造成的最严重的后果就是死锁。2.2.1进程的概念进程（process）的概念最早出现在60年代中期，用于多道系统，在Linux系统中，进程也称为任务（task）。简单地讲，进程就是正在运行的程序，更为严谨的表达是，进程是一个具有一定独立功能的程序关于某个数据集合的一次运行活动。进程的概念对于理解操作系统有决定性的意义，而真正理解进程，必须了解它的基本性质。进程是操作系统分配资源和进行调度的独立单位，具有独立性。同时，具有动态性。多道系统中同时存在多个进程，这些进程拥有各自的资源，各自独立地执行，对于单处理机系统，进程宏观上同时运行而微观上是依次执行，这种情况称为并发执行。1.进程和程序进程和程序是一对相互联系的概念。程序是指令的有序集合，是一个静态的概念，描述完成某个功能的一个具体操作过程，而进程是程序针对某一组数据的一次执行过程，更强调动态特征。一个完整的进程，包括程序、执行程序所需要的数据，同时还必须包括记录进程状态的数据资料。在多道分时操作系统中，按照时间片轮流在各个进程间切换。对于单处理器系统，每一个时刻只能有一个进程在执行，当分配给该进程的时间片用完之后，不管该进程运行到什么程度，都必须立即停止，然后让出处理器资源，下一个进程进入执行状态。让出处理器的进程必须记录好正在运行的状态，包括寄存器、堆栈等各种信息，这些信息保证当处理器下次切换到这个进程的时候，进程能够正确地从上次执行到的位置继续往下执行。一个程序在处理相同或不同的操作数据时可以同时对应于多个进程。一个进程也可以包含多个程序，某个程序在运行过程中，可能同时会调用到多个其他程序，这些具有调用关系的多个程序共同构成一次完整的运行活动，即一个完整的进程。举一个直观的例子。我们在Linux系统下使用编辑器vi进行编辑，同时打开多个窗口，编辑多个不同名称的文件，vi编辑器是一个可执行程序，不同的文件就是不同的操作数据，而对应于这些文件同时打开的每一个编辑窗口就对应着一个进程，每一个进程都处于不同的状态。如果说程序是提供计算机操作的一组工作流程的话，进程就是具体的工作过程，按照同样的工作流程，针对不同的原料，可以同时开始多个工作过程，得到多种不同的成品。这种工作流程和工作过程的关系就可以类比为程序和进程的关系。2.进程和作业作业是用户向计算机系统提交一项工作的基本单位，是用户在一次事务处理或计算过程中要求计算机所做工作的总和。进程是一个具有一定独立功能的程序关于某个数据集合的一次运行活动，是操作系统分配资源和进行调度的基本单位。作业是描述用户向系统提交工作任务的实体单位，而进程是系统完成工作任务时程序执行的实体单位。从这个角度讲，他们处于不同的层次，作业描述用户和操作系统之间的任务委托关系，而进程描述操作系统内部任务的具体执行过程。一个用户的任务，即作业，由用户提交给系统，必须以进程的形式具体完成。对于批处理系统，通常，作业放在外存中专门的作业队列中等待进入内存执行，要经过一次宏观调度，由外存进入内存，以进程的形式运行。而对于UNIX/Linux这样的分时系统，没有宏观调度，作业不经过调度，直接进入内存，以进程的形式开始运行。任何一个进程，都存在于内存中，并且是已经开始运行的动态实体。2.2.2进程描述我们知道，进程是一个动态的概念，描述程序的一次运行活动。它存在于系统的内存中，是操作系统可感知、可控制的动态实体，是系统分配各种资源、进行调度的基本单位。1.进程控制块现在我们来讨论进程在内存中的静态存在方式。在多道系统中，处理机在多个进程之间来回切换，每个进程都会在暂停、运行这两种状态之间来回转换。当一个进程在处理机切换过来重新进入运行状态时，它必须严格精确地接着上次运行的位置继续进行，进程的静态描述可以保持切换现场，确保准确衔接，保证进程调度的实现，顺利完成程序所规定任务。进程切换现场称为进程上下文(context)，包含了一个进程所具有的全部信息，一般包括：进程控制块（ProcessControlBlock，PCB）、有关程序段和相应的数据集，具体组成见图2.1。程序段是某个进程执行的相关指令集合，和静态的程序段有明确的对应关系，相应数据集是这个程序段正在操作的那部分数据，PCB是记录进程各种状态的数据体，PCB是操作系统管理感知、控制进程的数据实体，通过它，就可以找到进程的程序段和数据集，系统正是通过PCB来控制进程的。一般来讲，PCB记录着进程的所有资料，是全部或部分常驻内存的，PCB记录着程序段和数据集的地址指针，通过这些指针，就可以得到具体的指令和数据。PCB记录了进程的全部控制信息，一般较庞大而复杂，它可以按照功能大概分成四个组成部分：进程描述信息、进程控制信息、进程相关的资源信息和CPU现场保护结构（如图2.1）。图2.1进程描述数据关系示意图（进程上下文）2.Linux的PCBLinux系统的进程控制块PCB用一个称为task-struct的结构体来描述。(1)进程描述信息通过进程描述信息，Linux系统可以惟一地确定某一个进程的基本情况，可以了解该进程所属的用户及用户组等信息，同时还能确定这个进程与所有其他进程之间的关系。这些描述信息包括：进程号、用户和组标识以及描述进程家族关系的连接信息。①进程号（pid，processidentifier）Linux系统为每一个进程分配一个标识号，通过这个标识号识别、控制、调度这个进程，别的进程也通过这个标识号来识别这个进程并与之通信，用户也可以使用操作命令或系统调用通过标识号来控制该进程。②用户和组标识（userandgroupidentifier）Linux系统中有四类不同的用户和组标识，主要用来控制进程对系统文件的访问权限，实现系统资源的安全访问。Linux使用组将文件和目录的访问特权授予一组用户，一个进程可以同时属于多个组，这些组都被放在进程的task-struct中的group数组中。③连接信息（Links）Linux系统中的进程之间形成树状的家族关系，连接信息记录某个进程的父进程、兄弟进程（具有相同父进程的进程）以及子进程的信息，描述一个进程在整个家族系统中的具体位置。(2)进程控制信息进程控制信息记录了进程的当前状态、调度信息、记时和时间信息以及进程间通信信息，是系统确定进程的状态、了解进程之间的关系、进行进程调度的主要依据。①进程当前状态进程的生命周期中，总是不停地在各种状态之间转换，有关进程的状态及转换规则，在下一小节讨论。②调度信息系统的调度程序利用这部分信息决定哪一个进程应该运行，包括优先级、实时优先级、计数器和调度策略。③记时信息包括时间和定时器，给出进程占有和利用CPU的情况，是调度的依据，也是进行统计、分析以及记费的依据。④通信信息多个进程之间通信的各种信息也记录在PCB中。Linux支持典型的UNIX进程间通信机制——信号、管道，也支持SystemⅤ通信机制——共享内存、信号量和消息队列。(3)进程资源信息Linux的PCB中包含大量的系统资源信息，这些信息记录了与该进程有关的存储器的各种地址和资料、文件系统以及打开文件的信息等等。通过这些资料，进程就可以得到运行需要的相关程序段以及必要的数据。(4)CPU现场信息进程的静态描述必须保证一个进程在获得处理机并重新进入运行状态时，能够精确地接着上次运行的位置继续进行。相关程序段和数据集以及处理机现场（或处理机状态）都必须保存。处理机（CPU）现场信息一般包括处理机的内部寄存器和堆栈等基本数据。task-struct是Linux系统的进程控制块（PCB），通过对PCB的操作，系统为进程分配资源并进行调度，最终完成进程的创建和撤销。系统利用PCB中的描述信息来标识一个进程，根据PCB中的调度信息决定该进程是否应该运行。如果这个进程要进入运行，首先根据其中的CPU现场信息来恢复运行现场，然后根据资源信息获取对应的程序段和数据集，接着上次的位置开始执行，同时通过PCB中的通信信息和其他进程协同工作。2.2.3进程状态及转换系统通过PCB对进程进行控制，进程不断地在不同的状态之间转换。1.进程的基本状态在分时系统中，一个进程拥有了所需要的全部资源，就可以开始执行，当分配的时间片结束，让出CPU资源，这种只要能够占有CPU就能进入执行的状态称为就绪状态。有时，多个进程之间互相制约，某个进程必须等到某个事件发生（才能够竞争CPU资源，这是等待状态，当等待的事件发生之后，这个进程被唤醒，由等待状态进入就绪状态，直到获得CPU才开始执行。等待状态、就绪状态和执行状态是一个进程所具有的最基本的三种状态，见图2.2。图2.2进程基本状态及转换示意图2.Linux系统进程状态Linux系统的2.2.16版本进程共有六种状态，包括运行状态、可中断等待状态、不可中断等待状态、僵死状态、暂停状态和交换状态，而在2.4.0版本中取消了交换状态，加入独占状态。表2.1Linux系统（2.2.X—2.4.X版本）进程状态表进程状态TASK-RUNNINGTASK-INTERRUPTIBLETASK-UNINTERRUPTIBLETASK-ZOMBIETASK-STOPPEDTASK-SWAPPINGTASK-EXCLUSIVE

值012481632

说明运行态等待态，可中断等待态，不可中断僵死态暂停态交换态（2.4.X版本已取独占态(1)运行状态（running）Linux系统中的运行状态实际包含了上述基本状态中的执行和就绪两种状态，进程到底是正在运行还是处于就绪状态准备运行，要靠当前是否占有CPU资源来区分。(2)等待状态Linux系统把基本的等待状态进一步细化为可中断的等待态和不可中断的等待态两种。处于这种状态的进程都在等待某个事件或某个资源，可中断等待状态的进程可以被信号唤醒而进入就绪状态等待调度，而不可中断等待状态的进程是因为硬件资源无法满足，不能被信号唤醒，必须等到所等待的资源得到之后由特定的方式唤醒。(3)僵死状态（zombie）由于某些原因进程被终止，这个进程所拥有的内存、文件等资源全部释放之后，还保存着PCB信息，这种占有PCB但已经无法运行的进程就处于僵死状态。(4)暂停状态处于暂停状态的进程，一般都是由运行状态转换而来，等待某种特殊处理。比如处于调试跟踪的程序，每执行到一个断点，就转入暂停状态，等待新的输入信号。(5)交换状态处于交换状态的进程正在执行内存、外存的交换工作。这个状态在2.2.X版本的内核中基本已经不使用，在2.4.X版本中没有这种状态。(6)独占状态它应该是等待状态的一种，处于独占状态的进程位于等待队列中，当等待的事件发生时，只有处于这种状态的进程被唤醒，其他处于可中断和不可中断等待状态的进程则继续等待。Linux2.4引入独占状态后，如果事件发生，只唤醒处于独占状态的那一个进程，这就可以大大提高Apache这类Web应用的效率，使Linux更适合网络服务器的角色。来看Linux系统进程的状态转换情况。采取一定的简化措施：按照进程是否占有处理机为依据，把进程的运行状态分为执行和就绪两种状态；等待状态统一考虑，不再区分是否可中断，独占状态也作为一种等待状态处理；不涉及交换状态。见图2.3。图2.3Linux系统进程状态及转换示意图图2.3同时也记录了一个进程在整个生命周期的变化过程。从图的左下方开始看，系统在某种特定的情况下，响应某个要求，首先分配各种资源，创建一个新的进程，进程进入就绪队列。所有的进程必须在就绪之后，才有资格竞争CPU，进入运行状态。这样，进程的整个生命周期中，大致的转换路径总是沿着三个闭合回路进行。就绪状态和执行状态形成第一个回路。进程进入就绪态，放入可执行队列等待，一旦被调度函数选中，就切换现场，进入运行状态，等自己的时间片耗尽之后，马上保护现场，让出CPU，转入就绪状态，等待新的调度。执行状态、等待状态和就绪状态形成第二个回路。处于执行状态的进程，有时需要等待某个事件或某种资源的发生，这时，继续占有CPU也无法开展工作，就转入等待状态，CPU由下一个被调度的进程占有。当等待进程所等待的事件发生后，等待进程被唤醒，进入就绪状态。执行状态、暂停状态和就绪状态构成第三个回路。当接收到某种特殊的信号，比如SIGSTOP（Linux的停止信号）时，处于执行状态的进程放弃CPU，保护现场之后，进入暂停状态，直到获得另外一个特殊的信号才进入就绪状态。一个处于执行状态的进程调用退出函数exit之后，进程就会进入僵死状态，这种状态下，进程释放了PCB之外的所有系统资源。也就是说，它在系统中只留下这个进程的一个PCB。僵死进程的父进程通过PCB了解到该进程所处的状态后，采取相应的处理措施，回收PCB，这个进程就完成了它的使命，从僵死走向彻底消亡，上图右上方的虚箭头表示了这种结局。2.2.4进程控制进程控制，是指对系统中的全部进程实施有效的管理，使得进程能够及时创建、撤销，正确地完成进程各状态之间的转换，使得多个进程高效率并发执行，达到系统资源高度共享的目的。进程状态之间的转换转换通常由三种不同的方式控制：进程控制原语、系统核心函数（比如调度）、和外部事件发生（比如中断）。这里说的所谓原语，指系统状态下执行的一些具有特定功能的程序段，这些程序段具有“原子性”，是执行过程中不可分割的最小单位。用于进程控制的原语有：创建原语、撤销原语、阻塞原语、唤醒原语等。(1)创建原语进程创建原语用于建立一个新的进程，这个新进程可以由内核调用进程创建原语建立，也可以由父进程执行进程创建原语生成一个子进程，子进程还可以生成子进程，以形成树形进程家族结构。进程创建原语的主要任务是形成进程的PCB，因此，调用者必须提供有关的参数，例如进程名、进程优先级、进程正文段起始地址、资源清单等。(2)撤销原语当一个进程完成了指定的任务或由于某种错误导致异常终止时，要撤销这个进程以便释放进程占用的资源。进程撤销原语根据调用者提供的信息，找到指定的进程，回收其占用的资源和PCB。(3)阻塞原语当正在运行的进程需要等待某一事件，由自己调用阻塞原语把自己阻塞起来成为等待状态。阻塞原语主要完成保护CPU现场的工作，即首先中断处理机保存该进程的CPU现场，然后把被阻塞的进程置为等待状态，插入到相应的等待队列，最后转入进程调度程序，从就绪队列中选择一个进程投入运行。(4)唤醒原语当处于等待状态的进程所等待的事件出现时，由发现者进程调用唤醒原语唤醒被阻塞的进程。进程控制原语由系统执行。同时，操作系统还提供了一些用于进程控制的系统调用和操作命令，用户可以通过程序或者命令的方式控制进程。2.2.5进程约束现代操作系统中，程序并发执行，多个进程各自独立地运行，同时竞争和共享系统中有限的资源，这种竞争与合作构成了系统进程之间的约束关系。每个进程独立地申请和释放系统资源，把申请某一类资源的进程称为该类资源的消费者，把释放同类资源的进程称为该类资源的生产者，就得到描述进程约束关系的一般模型：生产者－消费者问题，也称为有界缓冲区问题。比较简单的情况，两进程共享一个长度为N（N>0）的有界缓冲区，一个进程Pp往缓冲区中送数据，是生产者，另一个进程Pc从缓冲区中读取数据，是消费者，如图2.4，下面来讨论它们间的约束关系。图2.4简单的生产者－消费者问题首先，生产者进程Pp和消费者进程Pc共享同一个有界缓冲区，对这个缓冲区的操作必须是独占的。这种不允许多个并发进程交叉执行的资源称为临界资源，临界的程序段资源称为临界部分或临界区。临界资源是由于不同并发进程共享某个资源造成的，不可能通过增加资源的方法解决。这种因为共享某一公有资源而引起的在临界资源内不允许并发进程交叉执行的现象，称为进程间的间接约束。由于对临界资源的共享，而产生了临界区问题。对于有着临界区问题的并行进程之间必须互斥，以保证不会同时进入临界区。其次，对生产者进程Pp和消费者进程Pc访问共享有界缓冲区的顺序有严格的要求。具体来讲，这种限制为：(1)消费者进程Pc要接收数据时，有界缓冲区必须至少有一个单元是满的；(2)生产者进程Pp要发送数据时，有界缓冲区必须至少有一个单元是空的。这样存在一组相互独立的并发进程，各自的执行结果互为对方的执行条件，从而限制各进程执行速度的过程，称为进程间的直接制约。存在直接制约关系，相互发送消息进行互相合作、互相等待，各自按照一定的速度向前推进的过程称为同步。消费者进程和生产者进程之间因为共享缓冲区，相互竞争而间接制约，具有互斥关系，同时相互以对方的运行结果为条件而直接制约，也具有同步的关系，是一对同时具有竞争和合作的进程。在并发系统中，进程之间相互制约，具有同步和互斥是相当普遍的现象。这种进程之间的相互关系，依靠单个进程自身的力量是无法解决的，必须以进程间的相互通信为基础，互相发送信息，才能协调解决。具体的同步、互斥实现方案有很多种，分别基于不同的通信方式。2.2.6进程通信进程间通信是协调解决多个进程之间的约束关系，实现进程共同进展的关键技术，是多道系统中控制进程并发执行必不可少的机制。进程间的通信有两种方式：一是互相发送少量的控制信息，一般只传递一个或者几个字节的数据，进程利用这些简单的信息，实现互斥和同步，控制运行速度，这种简单的通信方式被称为进程间的低级通信；另外一种方式称为进程间的高级通信，基本不涉及进程执行速度控制，用来在进程之间传递大量的信息，由于这种通信方式主要用于交换信息，因此，在开发本地进程间通信的同时，也为远程进程间的通信，和计算机网络的开发及控制奠定了基础。1.进程通信类型按照通信进程双方的地位，可以把进程通信分为：主从式、会话式、消息或邮箱机制以及共享存储区四种类型。(1)主从式主进程一方在整个通信过程中处于绝对的控制地位，它可以直接控制从进程的动作，自由地使用从进程的资源和数据。(2)会话式一方进程提供服务，另外一方进程在得到服务方的许可之后，可以使用其提供的服务。在通信过程中，双方的连接关系固定，客户进程提出服务请求，服务进程根据情况控制服务的状态和内容。(3)消息或邮箱机制通信双方具有平等的地位，和现实生活中的邮件类似。通信双方通过缓冲区或邮箱存放被传送的数据，不需要建立双方直接的连接关系。申请通信的发起方进程不管接收方进程的状态，把信息直接送入双方共享的缓冲区（或者邮箱）中，接收进程在合适的时机去读取缓冲区（或者邮箱）以接收信息。(4)共享存储区共享存储区通信方式中，通信双方进程共享内存中的一段存储空间，共同操作这个存储区，达到数据共享的目的。通信过程中，数据一直存放在共享存储区中，不需要移动，因此特别适用于大量数据的传递。2.Linux系统的进程通信Linux系统提供了多种通信机制，利用这些机制，可以方便地进行进程之间的相互协调，实现进程的互斥和同步。(1)信号(signal)信号属于Linux系统的低级通信，主要用于在进程之间传递控制信号。信号可以发给一个或多个进程，可以是由某个进程发出，也可以由键盘中断产生，还可以是由shell程序向其子进程发送任务控制命令时产生。进程在某些系统错误环境下也会有信号产生。除了两个信号外，进程可以忽略这些信号中的绝大部分，这两个信号是引起进程终止执行的SIGSTOP信号和引起进程退出的SIGKILL信号。至于其他信号，进程可以选择处理它们的具体方式。信号没有固有的相对优先级。并不是系统中每个进程都可以向所有其他进程发送信号，只有核心和超级用户具有此权限。普通进程只能向具有相同uid和gid的进程或者在同一进程组中的进程发送信号。信号是通过设置task-struct结构中signal域里的某一位来产生的。如果进程没有阻塞信号并且处于可中断的等待状态，则可以将其状态改成running，若确认进程还处在运行队列中，就可以通过信号唤醒它。(2)管道(pipe)管道是UNIX操作系统传统的进程通信技术。Linux管道通信包括无名管道和有名管道两种，通过文件系统来实现。管道也是一种特殊的文件类型，实际上是通过文件系统的高速缓冲实现的。两个进程通过管道进行通信时，两个进程分别进行读和写操作，都指向缓冲区中同样的物理单元，一个进程写入数据，另一个进程从缓冲区中读取数据，从而实现信息传递。管道方式只能按照先进先出方式单向传递信息。管道方式可以用来进行大规模的数据传递。(3)SYSTEMⅤ进程间通信信号量、消息队列和共享内存是UNIX/Linux系统常用的通信方式。消息队列用来在进程之间传递分类的格式化数据，共享内存方式可以使不同进程共同访问一块虚拟存储空间，通过对该存储区的共同操作来实现数据传递，信号量主要用于进程之间的同步控制，通常和共享内存共同使用。这三种方式在系统中是作为一个整体实现的。共享内存是这三种方式中通信效率最高的，它在进程的虚拟空间中进行，而且不需要数据的移动也可以实现大规模的数据传递。(4)套接字(socket)套接字是用来通过网络实现运行于不同计算机上的进程之间通信的机制。它可以实现数据的双向规模传递，是整个网络通信的基础。具体的原理和实现与网络协议等有关，不做具体的介绍。2.2.7死锁死锁，是指所有并发进程都拥有部分资源，同时都在等待其他进程拥有的资源，而且在得到对方资源之前不会释放自己占有的资源，所有进程都进入永久等待状态而无法运行的情况。死锁是并发进程约束关系处理不当造成的最严重的后果，是对系统资源极大的浪费，必须设法避免。死锁出现的根本原因是系统资源的有限性。并发进程竞争资源，调度不当，就可能出现死锁的情况，因此必须采取适当的措施来消除死锁。产生死锁的必要条件有四个：并发进程之间是互斥关系，每个进程必须独占某个系统资源；进程占有的资源在未结束使用之前，不能被强行剥夺，只能由该进程自己释放；进程需要的资源采用部分分配的方式，在等待新资源的同时，继续占有已分配的资源；各占有资源的进程形成环路，每一个进程已获得的资源同时被下一个进程请求。解决死锁的方案就是破坏死锁产生的必要条件。方法分为预防、回避、检测恢复三种。预防指采取某种策略，控制并发进程对资源的请求，保证死锁的四个必要条件在系统运行的任何时刻都无法满足。避免指系统采取某种算法，对资源使用情况进行预测，使资源分配尽可能合理，避免死锁的发生。这两种方法需要大量的系统开销，而且系统的资源也无法得到充分的利用。因此，一般系统都采取检测恢复的方法，这种方法是在死锁发生之后，根据系统情况，检测死锁发生的位置和原因，使用外力，重新分配资源，破坏死锁发生的条件，系统就可以从死锁状态恢复正常运行，这样的方法只要使用少量的系统资源，尤其是CPU时间就可以排除死锁。2.3线程多道处理系统中，进程是系统调度和资源分配的基本单位，计算机的CPU不停地在不同进程之间切换，进程切换现场称为进程上下文，每一次切换过程，系统都要对换出进程的上下文做详细记录，然后恢复换入进程的上下文。因此，系统的进程管理过程要耗费相当多的系统资源和CPU时间，尤其是对于需要频繁进程切换的任务。针对进程切换的时间和资源耗费问题，为了减少系统进程切换的时间，提高整个系统的效率，引入了线程的概念。2.3.1线程的概念线程是在一个进程内的基本调度单位。线程可以看作是一个执行流，拥有记录自己状态和运行现场的少量数据（栈段和上下文），但没有单独的代码段和数据段，而是与其他线程共享。多个线程共享一个进程内部的各种资源，分别按照不同的路径执行，同时线程也是一个基本调度单位，可以在一个进程内部进行线程切换，现场保护工作量小。一方面通过共享进程的基本资源而减轻系统开销，另一方面提高了现场切换的效率，因此，线程也被称为轻权进程或轻量级进程。许多流行的多任务操作系统基本都支持线程。按照系统的管理策略，线程可以分为用户级线程和系统级线程（内核级线程）两种基本类型。用户级线程指不需要内核支持，在用户程序中实现的线程都需要用户程序自己完成。系统级线程由内核完成线程的调度并提供相应的系统调用，用户程序可以通过这些接口函数对线程进行一定的控制和管理。用户级线程不需要额外的内核开销，一般只要提供一个线程库即可，剩下的工作就主要由用户自己负责了。但是由于用户级线程与系统内核无关，当一个进程因I/O而被调度程序切换为等待状态时，属于该进程的某个执行线程可能仍然处于执行状态。系统级线程的调度由内核完成，不需要更多用户干预，但要占用更多的系统开销，效率相对低一些。线程也是系统中动态变化的实体，它描述程序的运行活动，在内存中需要记录。线程的记录信息要保证系统能够准确地进行线程切换。在线程的生命周期里，线程作为一个基本的执行单位而存在，不断地在执行和停止的状态之间转换。线程的基本状态是执行、就绪和等待。线程的同步是一个相当关键的问题。线程之间的通信相对容易，而线程间的同步问题需要更仔细地对待，特别是用户级线程，这个问题相当突出。2.3.2线程和进程进程是操作系统资源分配和系统调度的基本单位，每一个进程都有自己独立的地址空间和各种资源，线程也是一种系统调度的基本单位，多个线程可以共享一个进程的资源，在存储方面，线程占用的资源更少。进程的调度主要由操作系统完成，而线程根据其类型的不同，可以由系统调度（内核级线程），也可以由用户进行调度（用户级线程）。进程调度的过程中要进行切换，切换现场的保护与恢复要求对进程上下文做完整的记录，要消耗一定的存储资源和处理机时间；线程共享进程的资源，可以在进程内部切换，不涉及资源保存和内存地址变换等操作，可以节约大量的空间和时间资源。因此，对于切换频繁的工作任务，多线程方式比多进程方式可以提供更高的响应速度。多个线程共享同一进程的资源，线程相互间通讯容易。而进程间通讯一般必须要通过系统提供的进程间通讯机制。进程和线程都是用来描述程序的运行活动，是存在于系统存储区中的动态实体，都有自己的状态，整个生命周期都在不同的状态之间切换。2.3.3Linux系统的线程Linux可以同时支持内核级线程（也称为系统级线程）和用户级线程。Linux的系统级线程在表示格式、管理调度等方面与进程没有严格的区分，都是当作进程来统一对待。Linux系统级线程和进程的区别主要在于资源管理方面，线程可以共享父进程的部分资源（执行上下文）。在Linux系统中，线程共享资源的类型是可以控制的，系统调用clone里有五种形式的clone：CLONE-VM（存储空间），CLONE-FILES（文件描述表），CLONE-FD（文件系统信息），CLONE-SIGHAND（信号控制表），CLONE-PID（进程号）。Linux的内核级线程和其他操作系统的内核实现不同。大多数操作系统单独定义描述线程的数据结构，采用独立的线程管理方式，提供专门的线程调度，这些都增加了内核和调度程序的复杂性。而在Linux中，将线程定义为“执行上下文”，它实际只是进程的另外一个执行上下文而已，和进程采用同样的表示、管理、调度方式。这样，Linux内核并不需要区分进程和线程，只需要一个进程/线程数组，而且调度程序也只有进程的调度程序，内核的实现相对简单得多，而且节约系统的用于管理方面的时间开销。但是，Linux系统使用相对复杂的进程控制块来记录信息，而线程本身的控制信息很少，完全可以采用相当简单的线程控制块数据结构，这就造成了内存空间的一定浪费。一个值得注意的问题是，在Linux系统中，专门有一种称为kernelthreads的线程，直译为内核线程，它和我们这里讨论的系统级线程（kernellevelthreads）在Linux系统中是两个完全不同的概念，它们的区别，将在4.3节“Linux进程调度”中详细介绍。Linux支持POSIX标准定义的线程（pthreads），提供用户级线程支持。利用这样的线程库函数，用户可以方便地创建、调度和撤销线程，也可以实现线程间通信，而且这些线程还可以映射为系统级线程，由系统调度执行。实现用户级线程创建的函数是pthread-create。2.4小结进程是现代操作系统的核心概念，它用来描述程序执行的过程，是实现多道操作系统的基础。和进程联系密切的概念是程序、作业和线程，正确地区分和理解这些概念，有助于正确地理解和认识计算机操作系统本身。Linux系统中基本没有区分进程和线程，它们都使用相同的描述方法，使用相同的调度和管理策略。描述进程的静态数据是进程控制块PCB。在Linux等多道操作系统中，程序是并发执行的，进程的个数总是多于系统CPU的个数，宏观上所有进程同时都在运行，微观上这些进程轮流使用CPU，在执行、等待和就绪等基本状态之间转换，直到执行完成。习题2-1什么是作业？简述Linux系统作业的概念。2-2作业、程序和进程有什么区别？2-3进程能不能理解为由伪处理机执行的一个程序？为什么？2-4什么是进程间的互斥和同步？2-5并发进程间的制约有哪几种？引起的原因分别是什么？2-6Linux系统中的线程有哪几类？分别是如何描述和管理的？2-7访问Internet，了解Linux系统进程控制块的现状，有哪些改进，你认为改进方案如何？第3章存储管理3.1虚拟存储器3.2内存管理方式3.380386段页机制3.4Linux存储管理3.5小结习题每一个要运行的程序，必须首先进入内存，然而，每一台计算机的内存容量都是有限而宝贵的。存储管理的任务是方便用户使用存储资源，在有限的物理空间内使更多的用户进程高效地获得和使用尽可能多的存储空间，从而提高系统的整体性能。现代操作系统中普遍采用基于虚拟存储器的概念来统一管理内存和外存，实现逻辑上的大容量存储空间。本章首先介绍虚拟存储器的基本概念及使用虚拟存储器的依据和出发点——局部性原理，即在程序的运行过程中，总是集中地访问某一个程序段。根据这样的原理，可以把物理内存按照一定的规则划分为小部分，每次只装入某个进程必要的一部分内容就开始运行，在运行过程中，再根据需要装入新的内容。不同的划分规则形成不同的存储管理技术，我们简单介绍分区、页式、段式和段页式管理的基本思想。接着介绍Intel80386硬件存储管理机制，最后学习Linux系统在这种硬件平台的基本存储管理机制。3.1虚拟存储器计算机系统的存储器分为内存（主存）和外存（硬盘）。内存的价格昂贵，速度高，存储容量有限；外存价格便宜，速度慢，存储容量很大，适合于存放大量数据。为了使更多的用户进程合理、充分地使用存储资源，操作系统统一管理内存和外存，即把内存中暂时不用的内容放在硬盘上，内存中就可以腾出一部分空间，可以从硬盘装入其他迫切需要的内容。因此，从效果上看，计算机系统好像为用户提供了一个其存储容量比实际主存大得多的存储器。人们称这个存储器为虚拟存储器。3.1.1局部性原理实验证明，在几乎所有进程的执行过程中，某一个特定的时间段中，CPU不是随机地访问整个程序或数据，而是集中地访问程序或数据的某一个部分。进程的这种访问特性称为局部性原理。与CPU访问该局部内的数据和代码的次数相比，局部段的变化很缓慢，正是基于这样的原理，我们才有可能实现虚拟存储管理。把进程的所有内容划分为一个个小的部分，首先只把系统所必需的部分数据装入内存，其余部分就放在外存中，开始运行之后，再把所需要的其他部分换入内存，同时把不再需要的部分从内存中换到硬盘或者清除掉。当然，与之相配合，实际的内存也要划分为对应的小部分。这种内外存之间的数据交换对用户进程来讲是透明的。从用户进程的角度来看，系统好像提供了一个很大的内存一样，整个进程都能装进去而且正常运行，这种逻辑上的大容量存储空间就可以称为虚拟存储器。实际上，是操作系统的存储管理起了作用，用多次内外存数据交换的时间换来了大容量的并不真正存在的（虚拟的）内存。因此，可以想象，访问虚拟存储器的速度要比访问真正内存的速度要慢。3.1.2虚拟地址和虚拟地址空间内存中同时存在多个进程，每个进程的地址都是以0地址作为起始地址的虚拟地址空间，这个虚地址空间可以是线性的（一维的），也可以是多维的，这要取决于系统采用的存储管理方式。进程中的每一个指令和数据在这样的虚地址空间中都有一个惟一确定的地址，即虚拟地址。每一个进程都具有各自独立的虚拟地址空间，而整个系统只有一个物理地址空间。任何一个要执行的进程，都必须进入真正的内存中，在内存的物理空间中存在，这就需要在虚拟地址空间和物理地址空间之间建立适当的映射关系。通过这种映射关系，逐部分地把存在于虚拟地址空间中的进程要执行的部分放在物理地址空间中，而其他暂时不执行的部分放在外部存储器中，内外存动态地传递数据，最终完成整个进程所执行的任务。这种映射，也称为地址变换，是操作系统在硬件的配合下实现的。系统中的每一个进程，都有一个惟一的地址映射关系，也就是说，虚拟地址空间到物理地址空间是一个多对一的映射关系。这样，不同的进程有不同的虚拟地址空间和映射变换，可以方便地实现进程之间的存储保护，避免数据和程序遭受其他进程无意或者恶意的访问，同时，它们都映射到惟一的物理空间，可以通过多个进程同时映射同一个物理地址的方式实现数据和程序的共享。3.2内存管理方式虚拟存储的每一个要运行的程序，都必须首先进入内存，但是，每一台计算机的内存容量都是有限而宝贵的。管理技术，通常是基于局部性原理的，即把整个进程的虚拟地址空间划分为小的部分，同时把内存也划分为小的部分，在虚拟地址空间和物理地址空间之间建立特定的映射关系，进程的内容分批分期进入内存中特定的位置，其余部分在外存中，在需要的时候再传递到内存，用内存和外存的统一管理来实现内存扩充。在虚拟存储技术的发展过程中，使用了不同的地址空间划分方法和映射关系，这些不同的划分和映射对应于不同的存储管理方式，本节介绍几种能够实现虚拟存储的地址空间划分方式。3.2.1页把进程的虚拟地址空间划分为相等大小的部分，每个部分称为页（page），同时把物理内存空间也按照页的大小划分为小的部分，称为页面（pageframe，也称为页架或页框）。对于80386体系，页和页面的大小都为4K字节。在页和页面之间建立一一映射关系，连续的一维虚拟地址空间可以分别存放在不同物理空间中，因此，物理存储中，每个页面内部地址连续，而页面之间的地址可以是不连续的。页和页面之间的映射关系记录在一个表格中，这样的表称为页表。每一个进程使用惟一的页表，页表的每一项数据称为页表项，表示虚拟空间中某一页和实际物理空间中某一页面的对应关系，页表也存储在物理空间内，如图3.1所示。图3.1页式管理:页表（左）及相应的页、页面对应关系（右）示意图从上图可以看出，连续的一维虚拟空间经过变换，映射到物理空间中不连续的页面中。利用分页机制实现虚拟存储管理称为页式存储管理。管理过程中，内外存的数据传递是以页为单位。页式管理采用请求调页或者预调页技术实现内外存的统一管理，内存中同时只存放少量经常执行或者即将执行的页，而其他不经常使用或暂时不会执行的页，存放在外存中，等需要的时候再调入内存。利用分页技术将一维连续虚拟空间划分为一个个页，进程的虚拟地址由两个部分组成：页号P和页内地址（偏移量）W。这两个部分的虚拟地址经过地址变换后，映射到物理内存的对应单元。具体的地址变换过程如图3.2所示。图3.2页式内存管理地址变换示意图操作系统为每一个进程维护一个独立的页表，进程正在执行的时候，页表信息记录在页表控制寄存器中，系统根据寄存器的值得到该进程对应页表的地址，同时利用页号，就可以得到该页对应的页表项。查找页表，获得了页表所映射的页面号，由页面号和页内地址，就可以直接找到内存中的对应存储单元。在整个变换过程中，需要两次访问物理内存，第一次是查找页表，第二次是获取数据。为了提高效率，硬件一般提供一个高速的联想寄存器，构成一个快表（translationlookasidebuffer），把当前进程中经常使用的页表项放在快表中，地址变换过程中，首先访问快表，如果该页表项存在于快表中，就可以直接得到对应的页面号，如果不在快表中，再去查找页表得到页面号，快表的访问速度要比内存快得多，这样就可以提高内存的访问速度。采用页式管理，实现了进程的程序和数据非连续存放，对内存和外存统一管理，得到更大的虚拟存储空间，可以同时容纳和运行更多的进程，有利于系统整体性能的提高。缺点是增加了系统开销，而且需要一定的硬件支持。由于虚拟空间是连续的，整个进程按照一维地址顺序排列，同一个程序段在分页的过程中，可能分别位于不同的页中，代码和数据的共享比较困难。3.2.2段段式管理的基本思想是把整个程序按照逻辑结构划分为不同的段，每个段可以是一个函数（过程）或者数据，有自己的名称，段大小是不相等的，段与段之间不存在顺序关系。这样，进程具有一个二维的虚拟空间。内存的管理以段为单位，把正在执行的段放在内存中，其他段暂时放在外存中，当需要执行时再传递到内存中。这样，也可以实现大容量的虚拟存储器。段式管理中，进程的虚拟地址是二维的，由段号和段内偏移地址构成。与页式管理的区别在于，段号是不连续的，段的大小是可变的。在二维虚拟空间与物理空间之间需要建立一一映射关系，即地址变换，这种变换关系记录在一个称为段表的表格中，系统为每一个进程维护一张段表，通过查找段表，就可以得到虚拟地址所对应的物理单元。段式存储管理的优点在于使用了大小可变的虚拟地址空间划分方法，按照程序的固有逻辑关系来分段，便于进程之间存储共享。但是，地址变换关系更为复杂，需要更多的硬件支持，实现起来更为麻烦，同时也带来了更大的系统开销。3.2.3段页段页式存储管理，综合利用段式和页式管理的思想，把整个二维虚拟空间先分段，然后在段内分页。以页为最小的存储管理单位来实现虚拟存储。一方面可以按照程序的逻辑关系来划分进程空间的段，另一方面使用页来存放每一个段的内容，内外存交换以统一格式和大小的页来进行。这种管理模式下，虚拟地址要包括三个部分：段号、页号和页内偏移地址，地址变换也要经过两层次映射才能够实现，首先从二维虚拟空间映射到一个线性虚拟空间，然后再从线性空间映射到物理空间。可以想象，整个变换过程更为复杂，需要大量的硬件支持和系统开销。3.380386段页机制上一节，我们介绍了不同的存储管理方法：页式、段式和段页式。这些方法的依据都是局部性原理，区别在于存储空间的划分和映射方法。这些管理方法都需要一定的硬件支持。本节，针对Linux系统的主要平台之一Intel80386（简称I386）系统，介绍该系统的段页式硬件支持机制。3.3.1实模式与保护模式80386是Intel公司推出的32位CISC芯片，此后，该公司又相继推出80486、Pentium(P5)、PentiumPro、PⅡ、PⅢ等一系列向下兼容的32位芯片。本节讨论的特点是针对以I386为代表的整个芯片系列。I386有两种工作模式，实地址模式和虚拟地址模式，后者又称保护模式。实地址模式与早期的8086兼容，不能启用分页机制，不区分特权级，分段机制也受到限制，直接寻址方式，只能寻址1MB。I386的保护模式支持分段机制，整个虚拟空间可以划分为16K个段，每个段的大小可变，最大能够达到4GB，每个段可以提供独立的段内保护，支持二级分页机制，每个页面4KB，提供段页式存储管理的硬件支持。同时，在同一个任务内部，还提供4种（0~3）保护特权级，某一级特权i只可以访问所有其他大于等于这一特权级（≥i）的程序段。3.3.2地址空间在I386体系结构中，提供段页式存储管理的硬件支持，和内存管理有关的地址空间包括逻辑地址空间、线性地址空间和物理地址空间，在存储过程中，要经过相对独立的两级地址变换。第一级使用分段机制，把包含段地址和段内偏移地址的二维虚拟地址空间转换为一个线性地址空间（也是虚拟地址空间），第二级使用分页机制，把线性地址空间转换为物理地址空间。这种转换关系可以用图3.3来描述。图3.3地址映射关系示意图虚拟地址空间到线性地址空间的转换关系由段描述符表（简称段表）来描述，段表的每一个数据项记录一个段到线性地址的关系，段表存放在线性地址空间中。线性地址空间到物理空间的转换关系由页表描述，页表存放在物理地址空间中。每个虚拟地址空间（16K个段）可以分为相等的两个部分，一半称为全局虚拟地址空间，由全局段描述符表（GlobalDescriptorLabel，GDT）映射，另一半称为局部虚拟地址空间，由局部段描述符表（LocalDescriptorLabel，LDT）映射。系统中所有进程共享一个全局段表（GDT），而每一个进程都有自己的局部段表（LDT）。当进程发生切换时，GDT不变，而LDT更新为正在执行进程的LDT，因此，所有进程共享GDT所映射的物理地址空间，每一个进程都有自己单独的地址空间（由LDT描述）。线性地址空间划分为大小相等的页，每页为4KB，与之对应的物理地址空间划分为大小相等的页面，页面的大小也是4KB。I386体系结构采用二级分页机制，线性地址到物理地址的映射使用一个二级页表，二级表中的第一级称为页目录，每个页目录项指向一个二级表，这个二级表就是一个页表，每一个表项记录该表对应的表架的基地址，这个基地址和偏移量一起就构成整个物理地址。3.4Linux存储管理Linux系统本身采用段页式存储管理，使用最小限度的段机制和三级分页机制。在I386保护模式下，系统可以获得大容量的虚拟存储，并且在各进程之间实现有效的存储共享和保护。3.4.1段页设置Linux系统最低限度地使用I386体系的分段机制，把整个虚拟地址空间直接映射为线性地址空间，一个虚拟空间只包含一个段，段的大小为4GB。也就是说，一个进程最大可以占有4GB的空间。Linux2.2.16及以前的版本，在全局段表（GDT）中，每一个进程（每一个虚拟地址空间）有两个静态的表项，其中一项是进程的任务状态段（TaskStatusSegment，TSS），这项记录着进程切换过程中的CPU现场状态，另外一项是局部段表（LDT），LDT项是这个进程对应的局部段表的入口。而每个进程的局部段表中只有三个表项，一个空表项、一个用户数据段和一个用户代码段，用户数据和代码都从地址0开始，大小为3GB，称为用户空间。所有进程的3GB～4GB线性空间，都由系统共享，存放系统数据段和系统代码段，称为内核空间。Linux系统使用I386提供的四级保护机制中的两级，0级由系统内核使用，而3级由用户程序使用。Linux内核存储在内核空间。用户进程有各自的虚拟地址空间，都使用从0～3GB的线性空间，而内核空间映射到每一个用户线性空间的3GB～4GB的地方，由所有进程共享。根据硬件提供的保护机制，处于内核空间的内核代码可以访问正在执行进程的用户空间。用户空间的代码只能访问本空间的内容，不能直接访问内核空间的内容，用户进程只能通过中断或者系统调用访问内核空间，这时，触发硬件的特权级转换（由3级转换为0级），操作系统转入内核空间中执行，执行完毕后，依靠硬件设置实现再次切换，重新进入用户空间。用户空间之间除了特定的共享空间之外，不可以相互访问，这就比较方便地实现了存储共享和保护。整个线性空间通过分页的方式映射到物理空间。每页大小为4KB，因此整个4GB的线性空间可以分为1K（1024）个页（page），Linux系统采用三级分页机制，对页建立三级索引，分别称为页目录（pagedirectory）页中间目录（pagemiddledirectory）和页表（pagetable）。由于I386体系结构的限制，在I386平台上的Linux系统采用两级页索引，页目录和页中间目录合二为一。3.4.2地址映射Linux系统的虚拟空间分为连续的段，分别为用户空间和内核空间，直接映射到线性空间中。在地址变换过程中，主要考虑线性空间到物理空间的映射关系。在I386平台上的Linux系统采用两级页索引，为页目录和页表。线性空间的页和物理空间的基本单位页面（pageframe）之间存在对应关系，这种关系用页表（pagetable）来描述，每个页在页表中占一项，每一项为4字节，要描述整个线性空间，页表要4MB。把所有页表也划分为4KB为单位的页，共有1K个这样的页，这些页的地址采用页目录（pagedirectory）来记录，页目录的每一项描述存放页表的一个页与实际页面的对应关系，每一项也占用4字节。这样，描述整个线性地址空间需要的页目录占用一页。线性地址由三个部分组成，分别为页目录索引、页表索引和页内偏移地址。第一部分页目录索引描述要访问地址在页目录表中的位置，通过这个索引，就可以得到一个记录页表的内存单元；第二部分页表索引描述待访问地址在页表中的位置，通过查找页表，就得到待访问地址所在的页面；第三个部分页内偏移地址，描述待访问地址相对于页面基地址的偏移量。根据这三部分资料，就可以访问到内存中相应的内容。整个线性地址包括32位，其中页目录索引和页表索引各占10位，寻址范围为1K，正好是页表和页目录表的大小，而页内偏移地址占12位，寻址范围为4K，等于页的大小。这种地址变换可以参看图3.4。图3.4Linux在I386平台的地址变换从上面的描述可以看到，要访问内存中的某一内容，通过地址变换，首先查找页目录表，接着查找页表，最后才能访问到真正存放的数据，整个过程要三次访问物理内存，因此，记录一个进程中经常访问页的地址的快表（translationlookasidebuffer）是必不可少的。地址变换过程中，首先访问快表，如果该页表项存在于快表中，就可以直接得到对应的页面号，如果不在快表中，再去查找页目录表和页表。3.4.3共享与保护Linux系统的每一个进程拥有4GB的虚拟空间，这个空间也就是线性空间，在I386系统下，对应为1K个大小为4KB的页。其中0~767个页对应的3GB空间为用户空间。而3GB～4GB的区域映射为系统空间。实际上，整个物理内存被映射到从3G（0xc0000000）开始的一段线性空间中，在启动过程中，这个区域的页目录和页表首先建立，也就是说，整个物理内存从启动开始就处于内核态，由系统所控制。所有物理内存可以由内核页目录和内核页表来寻址，这种关系是固定不变的，而且对于每一个虚拟空间都相同，这一方面保证了系统对物理内存的快速访问和有效控制，另一方面也保证了所有进程可以共享系统空间。进程对系统空间的共享是在严格的限制下进行的，这种限制利用了I386提供的特权级保护机制。进程的虚拟空间包括了系统（内核）空间和用户空间两个部分，它们分别处于不同的特权级。内核空间特权级为0，进程执行这个空间的指令，称为处于内核态（或者系统态）；用户空间的特权级为3，进程执行这个空间的指令，称为处于用户态。用户态和核心态是同一进程的两种不同运行模式，进程在用户态和核心态执行时分别访问位于用户空间和核心空间的堆栈和数据结构。处于内核态的进程可以访问同一进程的用户空间，反之则不可以访问。一个进程可以在这两种不同的特权级之间切换，用户态通过中断或函数调用就可以转入系统态，执行内核空间的指令。而从系统态切换到用户态，则需要一定的硬件支持。在进程建立之后，首先建立页目录，然后系统根据实际需要，动态地分配一部分物理内存，建立用户页表、页表项以及相应的页目录项，进程在用户空间中将根据这些值来寻址，访问物理内存。在获得一部分内存之后，用户进程即可以开始执行，执行的过程中，当进程访问到还没有映射在内存中的页时，进程发出页面请求，操作系统才根据需要把放在外存中的页的内容传送到内存，同时建立内存页面与进程页的映射关系。每个进程虚拟空间中的0~3GB分别采用不同的映射关系，映射到不同的物理空间，虚拟空间之间是不可以互相访问的，这就起到对进程内的数据和程序保护的作用。进程之间的共享是必不可少的，如果我们同时开两个vi的编辑窗口，它们都运行同样的程序代码，分别属于两个不同的进程，对应于不同的编辑文本（操作数据），如果分别给两个进程开两块存储空间，存放同样的程序代码，显然是对有限内存资源的极大浪费，不同的进程共享使用相同的内存代码是最好的解决办法。Linux进程间的共享是通过把不同虚拟空间中不同的页映射到物理空间中同一页面来实现的，参看图3.5。图3.5Linux页面共享结构示意图在图3.5中，两个进程分别拥有自己的页目录和页表，而页表中，对应于不同进程的页号指向内存中同样的页面，这样，同一个物理页面映射为不同虚拟空间中不同的页，两个进程都可以根据自己的地址映射关系访问同一块内存，实现了内存的共享。这样的共享方式实现简单，易于理解，也不占额外的物理内存，但是，一旦共享页面的状态或者内容发生变化，所有共享该页面的进程的页表都要修改，这就需要多次访问内存，影响系统的效率。Linux系统还采用保护技术，实现进程用户空间内部不同存储段之间的保护。在系统运行期间，进程之间存储共享可以节约大量的存储空间，同时可以提高系统的整体效率，但是，共享必须在保证安全的前提下进行，这就需要必要的保护措施。虚拟空间划分为系统空间和用户空间，按照一定的映射规则与物理空间建立联系，系统多个进程之间共享整个系统空间，多个用户进程也可以共享一段物理内存。在Linux系统中，用户空间和系统空间的共享、不同进程用户空间之间的共享以及进程用户空间的虚拟存储段，都可以得到有效的保护。3.4.4分配与回收系统开始运行时，整个物理内存都映射到内核空间，由内核根据需要进行物理内存页面的分配或释放。用户进程建立时，分配相应的内存页面并建立用户进程虚拟空间与所分配页面的映射关系，在进程执行过程中，还要针对实际情况，动态地分配和回收页面，进程进入僵死状态后，除了进程控制块（PCB）所占据的页面之外的所有内存都释放，最后PCB释放，进程终止。因此，物理页面的分配和释放机制及其相关数据结构是操作系统虚拟存储管理的关键部分。在执行过程中，每一个进程要记录自己使用的所有页面以及它们的映射关系（页表和页目录），这些信息以指针的形式记录在进程的PCB中。同时，系统对所有内存的使用情况也要做精确的记录，这是内存进一步分配和回收的依据。1.空闲页面表示Linux主要采用Buddy（伙伴）算法有效分配和释放物理页面。系统的页面分配和回收都是以2的k次幂（0≤k≤NR-MEM-LISTS-1，整数）个页面为单位，称为页块，也就是说以1页、2页，直到2NR-MEM-LISTS-1页大小的页块为单位连续分配。具体来讲，对于I386系统，在2.2.16版本中，NR-MEM-LISTS默认值等于10，在文件mm/alloc.c中定义，每个页面大小固定（为4KB），所以，内存分配的最小单位是4KB，最大为2MB（29×4KB）。Linux的空闲物理页面分配采用链表和位图结合的记录方法。系统定义了一个称为free-area的数组，数组的大小为NR-MEM-LISTS。free-area数组的每一个元素都包含一个空闲页块双向链表的头指针和一个位图map，描述某一种页块的空闲情况。每一个数组元素对应的链表，记录2k大小页块的信息，k为数组元素的下标。具体来讲，第一个元素（下标为0）描述单个空闲页的信息，第二个元素（下标为1）则描述以2个页为一个块的空闲页块，第三个元素（下标为2）描述以4个页为一个块的页块信息。free-area数组的元素记录双向链表的头指针，而双向链表的每个节点包含空闲页块的起始物理页帧编号。free-area数组的元素中包含的位图map记录这种页块的具体分配使用情况，位图中的某一位置1，则表示对应的页块被使用。这样，所有单个空闲页面组成的双向链表挂在free-area数组的0号元素之后，所有2k页面大小的空闲块组成的双向链表挂在free-area数组的k号元素之后，同时，每一个空闲块的使用情况可以通过对应的位图描述。这种关系示意性地描述在图3.6的左半部分。图3.6Linux系统空闲内存示意图在图3.6中，如果物理内存中某一部分的空闲情况如图右半部分所示，free-area数组的0号元素描述大小为1页的空闲页块，那么第8号页面就是free-area数组的0号元素所对应的双向链表的头接点。同理，第5号和第0号页面分别是free-area数组的1号元素和2号元素所对应的双向链表的头接点。free-area数组的k号元素所对应的第N位为1，则表明该元素对应的链表中第N个页块是空闲的，这个页块的大小就是2k个页面。从图中也可以看到，free-area数组的各元素所记录的页块大小各不相同，从小到大依次是两倍的关系，同时对应用来记录页块分配情况的位图大小也各不相同，free-area数组元素号越大，页块越大，页块的数目就越小，而相应的位图也越小。2.页面分配与回收Linux采用Buddy算法来分配和回收物理页面，每次处理都是以2k（0≤k≤NR-MEM-LISTS-1，整数）个页面为单位。分配页面采用最先适应算法，当要分配一块内存时，首先确定需要内存的大小，如果需要的内存在2k到2k+1（0≤k≤NR-MEM-LISTS-1，整数）个页面大小之间时，系统要为它分配的页面就是2k+1个，系统在free-area数组中搜索从第k+1个元素对应的双向链表中开始搜索，找不到时再搜索第k+2个元素对应的双向链表，直到找到大于或等于要求尺寸的最小块的信息。如果找到的空闲块正好是2k+1个页面时，直接从free-area删除该块，返回首地址，如果找到的空闲块大于所需要的页面，则把空闲块一分为二，前半部分插入free-area数组前一个元素所指的链表中，取后半部分，如果后半部分还大，继续对半划分，直到分得的后半部分等于需要的页面为止。页面分配之后，对应的各位图的位也要相应设置。Linux采用的这种分配算法称为最先适应算法。随着页块的不断分配，系统的内存逐步被划分为一个个小的块，这些块有些正在使用，而另外一部分则是空闲块，但是连续可用的块却越来越少，这种情况称为内存的碎片化。因此，物理页块使用完之后要及时回收，而在回收空闲块的同时，还应当将小的空闲页块重新组合成大的页块。Linux系统回收空闲块时，根据位图表对应的值判断回收块相邻位置的页块是否空闲，如果和回收的页块大小相等的相邻页块刚好是空闲的，则可以把这两个页块组合成一个大的页块，这一过程一直继续，直到这个大页块的相邻块不等于这个块或者正在使用为止，这时还要修改对应的位图值，并把这个大的页块插入到free-area数组对应元素所指的链表中。Linux采用的Buddy算法可以实现内存的快速分配和回收，同时也能够有效地处理内存碎片化问题，总体效率比较高。但是，它对内存的快速分配是建立在内存需求量是2的整数幂个页面的基础上的，如果很不巧，我们需要的内存量是33KB，根据Buddy算法，在I386系统中，实际分配的是16个连续的页面（64KB），大约50%的内存就浪费掉了。在整个分配过程中，这样隐性的内存浪费量是相当惊人的。因此，可以说，这种算法内存分配和回收的高效率是通过牺牲系统内存资源的利用率换来的。3.5小结Linux操作系统可以统一管理内存和外存，实现逻辑上的大容量虚拟存储空间。利用这样的技术，系统有限的物理存储区域中可以存放更多的进程，这些进程轮流使用处理机，实现系统整体效率的大幅度提高。进程的执行过程中，某一个特定的时间段中，CPU总是集中地访问程序或数据的某一个部分，这种规律称为局部性原理，这个原理是虚拟存储实现的依据。根据这一原理，把进程的虚拟空间划分为一个个小的部分，首先只把系统所必需的部分数据装入内存，其余部分就放在外存中，开始运行之后，再根据进程执行情况把所需要的其他部分换入内存，同时把不再需要的部分从内存中换到硬盘或者清除掉。与这样的方式相配合，物理内存也划分为对应的小部分。不同的虚拟空间和物理空间划分方法得到不同的存储管理方法，常用的能够实现虚拟存储的划分方法有页式、段式和段页式。页式管理把虚拟空间和物理空间划分为大小相等的部分，分别称为页和页面，以页和页面为单位进行存储管理；段式管理把虚拟空间按照程序固有的逻辑关系划分为大小不等的段，每一个段对应程序的一个逻辑单位，以段为单位进行存储管理；段页式管理对虚拟空间先分段，再分页，最小单位是页，同时具有段式和页式管理的优点，但是整个管理的系统开销增大，而且还需要有硬件的支持。以I386为代表的向下兼容的一系列芯片在保护模式下，提供段页式存储管理的硬件支持。一个虚拟空间可以划分为16个段，最大的段可以达到4GB，同时支持分页功能，页面大小为4K，提供两级页表。同时提供0~3四个特权级，对不同特权级运行的进程实现保护。Linux最低限度地使用I386系统的分段机制，使用0（系统级）和3（用户级）两个特权级。每个虚拟空间是线性的，大小为4GB，分成用户空间0~3GB和系统空间3GB~4GB两个部分。所有系统空间都映射到同一段物理内存，实现系统段共享，操作系统位于系统空间，以0级特权运行，用户进程位于用户空间，以3级特权运行，使用页目录、页表这两级分页机制。利用I386提供的硬件机制，Linux系统可以方便地实现系统空间和用户空间之间、不同进程用户空间之间以及同一进程用户空间不同虚拟存储段之间的共享和保护。Linux系统的空闲物理内存的管理采取Buddy算法，管理内存的最小单位是2的整数次幂个页面大小，利用位图和链表相结合的办法记录空闲内存信息，内存分配采用最先适应算法，可以快速分配和回收空闲内存页面，同时也能够有效处理内存碎片化问题。以此为基础，下一章我们进一步学习虚拟存储管理中内存外存之间数据传递——交换调度的基本算法与过程。习题3-1计算机系统中，虚拟地址空间和物理地址空间分别对应着什么？3-2分页和分段式内存管理有什么区别？3-3为什么提出段页式管理?它与页式、段式管理有何区别？3-4段页式管理的主要缺点是什么？有什么改进办法？3-5Linux系统中如何利用I386的段页机制？3-6Linux中，系统空间和用户空间之间、不同进程用户空间之间以及同一进程用户空间不同虚拟存储段之间如何实现共享和保护？各需要什么硬件支持？3-7Linux系统的内存分配与回收采用什么算法？有什么优点？有什么缺点？提出你的改进思路。3-8考虑如下的程序段：#include<stdlib.h>#include<stdio.h>intmain(void){printf("AAA");sleep(6);return1;}在Linux系统中，运行这个程序所建立的进程的虚拟空间为多大？其中系统空间、用户空间各多大？进程实际占用的物理内存是多少？分别用来存储什么内容？运行这个程序，利用系统命令查看实际使用的内存量。第4章调4.1调度的层次4.2Linux交换调度4.3Linux进程调度4.4小结习题

度设计操作系统的主要目标是充分利用硬件资源使其发挥最大的效能。处理机（CPU）资源，又是其中最重要的一项，让它尽可能处于工作状态，是操作系统管理功能的关键。调度针对的主要是处理机资源的分配问题，因而处理机管理的核心是调度。处理机调度的主要指标有：周转时间、吞吐量、响应时间和设备利用率等。根据不同的使用场合、不同的系统需求，选取合适的调度算法，采用不同的管理侧重点，使系统达到预期的性能指标是调度管理的主要任务。本章首先介绍处理机调度的层次和目标，然后，以单处理机微机系统为背景，具体讨论Linux系统交换调度和进程调度的基本原理和实现方法。4.1调度的层次处理机调度也是分层次的，按照调度发生频率依次是：作业调度、交换调度、进程调度和线程调度。作业调度，是针对用户提交的作业，在已经输入的作业中，按照某种策略，选取合适的作业投入运行。交换调度，又称中级调度。针对系统中已经开始运行的进程，把内存中暂时不会执行的内容交换到外部存储器的特定区域中，而把外存中处于就绪状态的进程交换到内存中，准备投入执行。进程调度，控制进程在执行、就绪、等待等各种状态之间转换经历的过程。特别是从就绪到执行的转换，系统从处于就绪状态的所有进程中选择合适的一个，分配处理机资源，投入执行。线程调度，系统内核针对线程的调度情况，选中就绪线程并占有处理机，转入执行状态。参看图4.1。图4.1Linux系统调度层次示意图Linux系统高级调度非常简洁，或者也可以说没有作业调度的概念，作业一旦输入，就直接进入内存，建立相应的进程，进入下一级的调度。交换调度主要涉及系统存储管理的内容，一方面根据正在执行进程的要求，把所需要的页换入内存，同时按照一定的规则保证系统总是有足够的空闲内存页面，一旦发现系统空闲页面低于某一个临界值，就把内存中的页面按照一定的算法清除掉一部分，直接丢弃或者是交换到外部存储器中。Linux系统中的内核级线程和进程在表示、管理调度方面没有差别，系统也没有专门的线程调度，采用进程调度统一处理进程和内核级线程。因此，本章主要讨论Linux系统中的交换调度和进程调度的内容。4.2Linux交换调度Linux系统的内存主要采用称为请求页式管理的动态管理方法。当某一个程序开始运行时，一个新的进程创建，整个可执行文件映像和该程序引用的所有相关共享库同时装入进程的虚拟地址空间中。Linux在建立进程的时候，整个执行文件映像并没有装入物理内存，只是链接到进程的虚拟地址空间中，进程只分配到极少的内存页面，占用很少的物理空间。在整个进程生命周期中，进程所拥有的内存页面总是动态变化的。管理好内存页面和外部存储器，正确地模拟内存特殊区域的工作，保证系统有足够的内存，让尽可能多的进程并发执行，是Linux交换调度的主要任务。请求页式管理被认为是按照进程执行的需要而分配和使用内存的，因此也称为按需调页。为了解决进程执