1、第二章第二章 进程与线程进程与线程n现代操作系统在管理处理机资源时，在执行层面的基本单位是进程，即进程是独立运行和拥有资源的基本单位。而进程是随着现代操作系统必然遵循的多道程序设计技术的出现而提出的。n为此，本章首先从多道程序设计的角度引入进程概念；然后，围绕进程在内存的演变过程，逐步说明进程的控制、组织与通信，以对单个进程以及它们之间的相互作用有一整体性的了解；最后，由于线程是进程的一种发展与细化，线程的基本知识也在本章的最后给出了简单的阐述。2.1 多道程序设计与进程概念多道程序设计与进程概念2.1.1多道程序设计技术多道程序设计技术2.1.2程序的顺序执行与并发执行程序的顺序执行与并发执
2、行2.1.3进程的概念进程的概念2.1.4进程的特征进程的特征2.1.1多道程序设计技术多道程序设计技术多道程序设计的引入多道程序设计的引入n操作系统从单道方式发展到多道方式是一次巨大的飞跃。n在单道批处理操作系统中，内存中至多只有一个作业；从用户的角度来看，用户的一个程序从提交系统到最终完成的整个过程不会受到其它程序的任何影响；同时，多个程序在内存的执行是顺序的，即所有程序依次独占内存、处理机等资源执行。n而在多道批处理操作系统中，多个作业一次性装入到内存中。从系统管理的角度来看，内存中多个作业的执行是并发的。同时，各程序由于同时存在于内存中，它们之间必定会存在相互依赖、相互制约的关系。n显
3、然，相对于单道批处理系统，在多道批处理系统中，多个作业在内存中的工作过程的管理将更加困难。多道程序设计技术正是解决这一问题的专门技术。2.1.1多道程序设计技术多道程序设计技术n可以看出，在多道批处理操作系统中，从用户编写一个程序开始、可以看出，在多道批处理操作系统中，从用户编写一个程序开始、组织成作业的形式放在外存、一直到装入内存执行这样一个完整组织成作业的形式放在外存、一直到装入内存执行这样一个完整的过程中，程序在不同的阶段其组成和特性是各不相同的。的过程中，程序在不同的阶段其组成和特性是各不相同的。处理机用户1用户2用户n外存内存 作业提交 作业装入作业进程图2.1 程序、作业与进程2.
4、1.2程序的顺序执行与并发执行程序的顺序执行与并发执行 2.1.2.1前趋图n程序在单道运行方式和多道运行方式下，具有不同的执行次序。为准确描述多个程序之间的执行次序，采用图形工具是最自然的。n前趋图（Procedence Graph）就是用来描述程序执行先后次序关系的一个图形工具。n注意：前趋图中不可能存在循环。因此，前趋图一定是一个有向无循环图（DAG:Directed Acyclic Graph）。P1P3P2P4图2.2 前趋图示例2.1.2程序的顺序执行与并发执行程序的顺序执行与并发执行 2.1.2.2程序的顺序执行（一）（一）程序顺序执行过程程序顺序执行过程n在单道方式下，程序处在
5、一个顺序的执行环境中，多个程序在这一环境中是顺序执行的。顺序的执行环境意指：在计算机系统中，只有一个程序在运行；该程序独占系统中所有资源；其执行不受外界影响。P1P2P3Pn图2.3 程序的顺序执行过程2.1.2程序的顺序执行与并发执行程序的顺序执行与并发执行 2.1.2.2程序的顺序执行（二）（二）程序顺序执行的特征程序顺序执行的特征（1）程序执行的顺序性）程序执行的顺序性(Sequential)n程序依次分别装入内存；一个程序在内存中执行时，其它程序只能在外存等待。因为进入内存的唯一的一个程序独占处理机，所以该程序的各部分能够严格地按程序所确定的逻辑次序顺序地执行下去。（2）程序执行的封闭
6、性）程序执行的封闭性(Closeness)n在内存中的程序只有一个，该程序执行时独占全部系统资源；同时，程序在封闭的环境下运行，资源的状态除初始状态外，只有该程序才能改变它；所以，程序一旦开始运行，其执行结果不受外界因素的影响。（3）程序运行结果的确定性）程序运行结果的确定性(Recurrence)n程序运行的结果与程序的执行速度、执行时间与方式无关。只要程序执行时的环境和初始条件相同，当程序多次运行时，不论它的运行方式如何，是从头到尾连续执行，还是走走停停式地执行，都将获得相同的结果。也称程序运行结果的可再现性。2.1.2程序的顺序执行与并发执行程序的顺序执行与并发执行 2.1.2.3程序的
7、并发执行（一）（一）程序并发执行过程程序并发执行过程I1I2I3图2.4 程序的并发执行过程C1C2C32.1.2程序的顺序执行与并发执行程序的顺序执行与并发执行 2.1.2.3程序的并发执行（二）（二）程序并发执行的特征程序并发执行的特征（1）程序并发执行是间断性的）程序并发执行是间断性的n这就是并发执行的程序具有“执行-暂停-执行”的活动规律，它与程序执行的顺序性明显不同。（2）程序并发执行是开放性的）程序并发执行是开放性的n在并发环境下，程序的并发执行否定了封闭性，而体现出开放性的特征。n资源共享性n相互制约性n程序与执行不再一一对应（3）程序执行结果的可能不再现性）程序执行结果的可能不
8、再现性n显然，程序执行结果的可能不再现性是并发方式下的一个不良的后果，有必要引入专门的处理策略加以解决。2.1.2程序的顺序执行与并发执行程序的顺序执行与并发执行例如，现有两个循环程序P、Q。程序P每执行一次循环都要对变量n做加1操作；程序Q每隔一定时间打印变量n的值，然后将n清成0。显然P、Q共享一个变量n。int n=0;cobegin void P(void)while(TRUE)n=n+1；remainder of P；void Q(void)while(TRUE)print(n)；n=0；remainder of Q；coend2.1.2程序的顺序执行与并发执行程序的顺序执行与并发执
9、行nP、Q这些不同的并发执行次序可能导致不同的结果：1)nn1在print（n）和n0之前，此时得到的n值分别为1，1，02)nn1在print（n）和n0之后，此时得到的n值分别为0，0，13)nn1在print（n）和n0之间，此时得到的n值分别为0，1，0n并发（并发（Concurrency）与并行（）与并行（parallel）两个概念）两个概念的区别。的区别。n并行性是指多个程序真正各自占有处理机并同时运行，所以严格地说，它只会出现在多处理机系统中；n而并发是出现在单处理机系统中的概念，可以认为并发是“逻辑上并行、物理上串行”。2.1.3进程的概念进程的概念n本质上，进程是具有独立功能
10、的程序关于某个数据集合上的一次运行活动，是系统进行资源分配和调度的独立单位。至今，人们提出了各式各样的进程定义，它们在实质上是一致的。例如：n进程是程序在内存的一次执行；n进程是可以并发执行的计算；n进程是一个抽象的实体，当它执行某个任务时，将要分配和释放各种资源；n进程是一个具有独立功能的程序，是对某个数据集在处理机上的执行过程和分配资源的基本单位；n进程是一个独立的可以调度的活动。n上述定义分别从不同的角度揭示了进程的本质。我们没有必要死记硬背这些定义，而应该关注于对进程概念本质的理解。n进程概念主要出现在Unix操作系统系列中，在Linux中将之称为任务（Task）。2.1.4进程特征进
11、程特征（1）动态性）动态性n动态性是进程最重要的一个特征。进程的动态性表现在它具有一定的生命周期性。即它“由创建而产生，由调度而执行，因得不到资源而阻塞，最后由撤销而消亡”；进一步，进程的“生”（产生）、“死”（消亡）只有一次，而在其生命期中间的“执行”、“阻塞”等状态可以多次反复。n与进程的动态性对应，程序是静态的，即程序只是始终存储在外存中的一个静态实体。（2）并发性）并发性n进程的并发性是指多个进程可以同时装入到内存，并能在一段时间内同时运行。引入进程的目的也正是为了使其程序能和其他进程的程序在内存中通过分时共享处理机等资源的方式，并发执行。n与进程的并发性对应，程序始终处于外存中，因此
12、没有并发的性质。2.1.4进程特征进程特征（3）独立性）独立性n进程的独立性是指进程是操作系统完成工作的基本单元。进程的独立性同时体现在如下几个方面：1）进程是一个能独立运行的基本单元。即只有进程才能作为一个独立的单元，去占有处理机运行；2）进程是申请、拥有系统资源的基本单位。即只有进程才能发出资源申请并拥有资源；3）进程是独立参与调度的基本单位。即在处理机空闲时，只有进程才能作为一个独立的单元去参与竞争并获得处理机资源。n与进程的独立性对应，而程序作为一个静态实体，既不可能去独立运行，也不可能去申请资源、拥有资源或参与调度。2.1.4进程特征进程特征（4）异步性）异步性n进程的异步性是指并发
13、的进程各自以其相对独立的、不可预知的速度向前推进。而程序既然没有动态执行，当然也就不存在异步性。在进程并发执行时，进程间的相互作用（包括直接作用和间接作用）导致了进程间的相互制约性，相互制约性导致了进程执行的间断性，间断性又导致了进程的异步性；正是异步性导致了进程执行的可能不再现性。n而程序既然没有动态执行，当然也就不存在异步性。（5）结构性）结构性n进程是一个在内存中的实体，遵循数据结构的规范，它必须要有自己的数据结构描述部分。n因此，从结构上看，每个进程除对应的程序段（对应程序的操作部分）、数据段（对应程序执行需要的数据部分）以外，还应该有一个自己的数据结构部分。这一数据结构称为进程控制块
14、（PCB：Process Controlling Block）。因此，进程的结构性是指进程是由程序段、数据段和PCB等组成的一个实体，有时也称为“进程映像”。n与进程的结构性对应，程序没有这种结构描述，它主要程序只是进程中的程序段一部分。2.2 进程的状态与转换进程的状态与转换2.2.1三状态模型及其转换三状态模型及其转换2.2.2五状态模型及其转换五状态模型及其转换2.2.3七状态模型及其转换七状态模型及其转换2.2.1三状态模型及其转换三状态模型及其转换（一）三种基本状态（一）三种基本状态（二）三种基本状态的转换（二）三种基本状态的转换就绪图2.5 进程的三种基本状态内存执行阻塞进程调度时
15、间片到完成I/O请求或等待事件I/O完成或事件发生2.2.2五状态模型及其转换五状态模型及其转换（一）五种基本状态（一）五种基本状态（二）五种基本状态的转换（二）五种基本状态的转换图2.6 进程的五种基本状态就绪内存执行阻塞进程调度时间片到完成I/O请求或等待事件I/O完成或事件发生新接收衰亡2.2.3七七状态模型及其转换状态模型及其转换（略）（略）（二）七种基本状态（二）七种基本状态（三）七种基本状态的转换（三）七种基本状态的转换图2.7 进程的七种基本状态就绪内存执行进程调度时间片到完成I/O请求或等待事件I/O完成或事件发生新接收衰亡阻塞就 绪挂起I/O完成或事件发生阻 塞挂起挂起挂起激
16、活激活挂起外存2.3 进程组织进程组织2.3.1进程控制块进程控制块2.3.2进程的组织方式进程的组织方式2.3.1进程控制块进程控制块（一）进程控制块概念（一）进程控制块概念n进程作为内存中的一种实体，在对其进行各种管理时，首先需要为之设置一个专门的数据结构，然后操作系统才能利用这一数据结构来控制与管理进程，这是数据结构规范的要求。n进程控制块（PCB：Process Controlling Block）就是操作系统为进程设置的专门的数据结构，用它来描述进程的特征以及控制进程运行需要的全部信息。n系统在控制和管理进程时，都是基于PCB进行的。可以说，进程在内存的一切活动都基于PCB进行；所以
17、，PCB是系统感知进程存在的唯一标志。n进程与PCB是一一对应的。即一个进程被创建，就有与之对应的PCB；一直到该进程消亡，相应的PCB也被收回。nPCB应常驻内存，因为它是进程的数据结构描述，同时也因为它被访问的频率很高（例如被运行频率很高的进程调度程序所访问）。2.3.1进程控制块进程控制块（二）进程控制块的内容（二）进程控制块的内容n进程描述信息：进程描述信息：进程标识符(Process ID)即内部标识符、进程名即外部标识符、用户标识符n进程调度信息：进程调度信息：当前状态、优先级、运行统计信息、阻塞原因n进程控制信息：进程控制信息：数据段与程序段地址、同步与通信、链接指针、资源n进程
18、状态信息：进程状态信息：寄存器、栈指针2.3.2进程的组织方式进程的组织方式（一）（一）PCB的逻辑组织的逻辑组织n遵循数据结构的规范，进程作为内存中的一种遵循数据结构的规范，进程作为内存中的一种实体，对其组织实际上就是针对进程的数据结实体，对其组织实际上就是针对进程的数据结构构PCB进行的。进行的。n在逻辑上，系统可以将所有进程的在逻辑上，系统可以将所有进程的PCB组织在组织在一起，并把它们放在内存的固定区域，就构成一起，并把它们放在内存的固定区域，就构成了了PCB表。表。PCB表的大小决定了系统中最多可表的大小决定了系统中最多可同时存在的进程个数，称为系统的并发度。同时存在的进程个数，称为
19、系统的并发度。n进一步，对进一步，对PCB表中的进程，可以根据进程的表中的进程，可以根据进程的状态，将具有相同状态的进程组织在一起，形状态，将具有相同状态的进程组织在一起，形成相应的进程队列。成相应的进程队列。2.3.2进程的组织方式进程的组织方式完成阻塞原因n阻塞原因2阻塞原因1时间片到进程就绪队列进程阻塞队列1进程阻塞队列2进程阻塞队列n占有处理机执行 图2.10 进程多队列组织2.3.2进程的组织方式进程的组织方式（二）（二）PCB的存储组织的存储组织（1）链接方式）链接方式执行进程指针就绪链表头指针阻塞链表头指针空闲链表头指针PCB14PCB23PCB30PCB48PCB50PCB67
20、PCB79PCB80PCB912 图2.11 PCB链接组织方式示意图PCB表2.3.2进程的组织方式进程的组织方式（二）（二）PCB的存储组织的存储组织（1）索引方式）索引方式PCB表空闲索引表阻塞索引表就绪索引表执行进程指针就绪索引表指针阻塞索引表指针空闲索引表指针PCB1PCB2PCB3PCB4PCB5PCB6PCB7PCB8PCB9 图2.12 PCB索引组织方式示意图 2.4 进程通信进程通信2.4.1进程通信概述进程通信概述（一）进程通信方式（一）进程通信方式（1）直接通信方式）直接通信方式n这种方式要求发送进程和接收进程都显式地提供给对方自己的地址或标识符；然后，发送进程利用操作
21、系统提供的发送指令，直接把信息传递给接收进程。n在发送时，指定接收方的地址或标识，也可以指定多个接收方或广播式地址；n在接收时，允许接收来自任意发送方的信息，并同时获取发送方的地址。（2）间接通信方式）间接通信方式n这种方式要求借助于收发双方进程之外的某种中间实体作为通信中转。这种中间实体是某种可共享的数据结构，用来暂存发送进程传递给接收进程的信息。2.4.1进程通信概述进程通信概述（二）进程通信类型（二）进程通信类型（1）共享存储系统（Shared Memory System）n在共享存储系统中，为了传送大量数据，首先在内存中划出一块共享存储区；然后，需要通信的进程可通过对此共享存储区进行读
22、或写数据来实现通信。即：一组进程向该共享内存中写，另一组进程从共享内存中读，通过这种方式实现两组进程间的信息交换。n采用共享存储系统的进程通信过程大致为：STEP1：申请共享存储区。进程在通信之前，向系统申请共享存储区中的一个分区，并为它指定一个分区关键字。若该分区已被系统分配给了其它进程，系统将该分区的关键字返回给申请者，然后继续申请直至成功；STEP2：合并分配的存储分区。申请者把获得的共享存储区的该分区链接到本进程上。STEP3：读写公用存储分区。进程可像读、写普通存储器一样，读、写这一共享的存储分区，完成进程信息的传递。2.4.1进程通信概述进程通信概述（二）进程通信类型（二）进程通信
23、类型（2）消息传递系统（Message Passing System）n消息传递系统首先对待传递的信息规定了一定的格式，按照这一格式组织的信息称为“消息”（Message），进程间的数据交换就以消息为单位。然后，消息传递系统提供了一组支持指令来实现进程通信，使进程通信无需用户考虑通信的管理细节。因而，消息传递系统是目前单机系统、多机系统包括计算机网络中最主要的一种进程高级通信方式。2.4.1进程通信概述进程通信概述（二）进程通信类型（二）进程通信类型（3）管道通信系统（Pipe System）n管道通信方式首先出现于Unix系统。管道（Pipe）是指用于连接一个发送进程和一个接收进程，以实现它
24、们间通信的共享文件，又称pipe文件。在这种进程通信方式中，发送进程向管道写入待传递的信息，而接收进程从此管道中读出信息。管道通信属于进程的直接通信方式。n为了协调发送和接收双方的通信，管道通信机制必须提供以下三方面的协调功能：1）互斥。当一个进程正在对pipe文件进行读或写操作时，另一个进程必须等待。2）同步。当发送进程把一定数量的数据写入pipe文件后，该进程便等待（阻塞）；直到接收进程取走数据后，再把它唤醒。同样，当接收进程从pipe文件中取走数据后，该进程也将等待（阻塞）；直到发送进程又向pipe文件写入数据后，才把它唤醒。3）确认对方是否存在。只有确认对方已存在时，才能进行管道通信；
25、否则，会造成因对方不存在而无限制地等待。2.5 线程基础线程基础2.5.1线程引入线程引入2.5.2线程定义与特征线程定义与特征2.5.2线程实现线程实现2.5.1线程引入线程引入n线程的引入可以从进程的独立性入手。n进程的独立性包括三重含义，即：n1）进程是一个能独立运行的基本单元；n2）进程是申请、拥有系统资源的基本单位；n3）进程是独立参与调度的基本单位。其中，后两点是第1）点的前提条件，使进程可以独立地参与并发执行。2.5.1线程引入线程引入n独立性导致不必要的负重而行n为此，一个可行的改进策略是：将进程的独立运行性和独立拥有资源性分开。具体做法是：作为独立参与调度的基本单位，不同时作
26、为独立拥有资源的基本单位，使之能够在拥有最少必要资源的前提下，独立地参加进程调度；同时，对拥有资源的基本单位，尽可能不频繁地对之进行进程切换。n遵循上述策略，我们可以将进程概念保留，作为独立拥有资源的基本单位；同时，又引入线程概念，作为独立参与调度的基本单位。2.5.2线程的定义与特征线程的定义与特征（一）线程的定义（一）线程的定义n线程（Thread）是进程中的一个实体，是可独立参与调度的基本单位。一个进程可以有一个或多个线程，它们共享所属进程所拥有的资源。n线程具有如下属性：（）多个线程可以并发执行。（）一个线程可以创建、撤消另一个线程。（）线程具有动态性。一个线程被创建后便开始了它的生命
27、周期，可能处于不同的状态，直至衰亡。（）每个线程同样有自己的数据结构即线程控制块TCB（Thread Controlling Block），其中记录了该线程的标识符、线程执行时的寄存器和栈等现场状态信息。（）在同一进程内，各线程共享同一地址空间（即所属进程的存储空间）。（）一进程中的线程在另一进程中是不可见的。2.5.2线程的定义与特征线程的定义与特征（二）线程与进程的对应（二）线程与进程的对应PCB用户地址空间用户栈核心栈线程控制块TCB（寄存器映像、线程优先数和线程状态信息等）图2.14 单线程进程模型2.5.2线程的定义与特征线程的定义与特征（二）线程与进程的对应（二）线程与进程的对应P
28、CB用户地址空间用户栈核心栈图2.15 多线程进程模型TCB1用户栈核心栈TCB2用户栈核心栈TCB32.5.2线程的定义与特征线程的定义与特征（三）线程的特征（三）线程的特征n线程具有许多类似于进程的特征，有时称线程为轻量级进程。（1）拥有资源方面拥有资源方面n不管是在以进程为基本单位的操作系统，还是在引入线程的操作系统中，进程都是独立拥有资源的一个基本单位；它可以申请并拥有自己的资源，也可以访问其所属进程的资源。而线程只拥有一点在运行中必要的资源，如程序计数器、寄存器和栈；当然，它可以访问其所属进程的资源（注意：资源仍然是分给进程的）。（2）调度方面调度方面n在引入线程的操作系统中，进程作
29、为独立拥有资源的基本单位，而线程是独立参与调度的基本单位。这样，引入线程的操作系统中存在着两级调度：同一进程内线程之间的调度、不同进程之间的调度（由分属于不同进程的线程之间的调度引起）。同一个进程内的线程切换不会引起进程切换；而在由一个进程内的线程切换到另一进程内的线程时，将引起进程切换。2.5.2线程的定义与特征线程的定义与特征（三）线程的特征（三）线程的特征（3）并发性方面n在引入线程的操作系统中，不仅不同进程的线程之间可以并发执行，而且在同一个进程的多个线程间亦可并发执行，因而使系统具有更好的并发性。（4）系统开销方面n相比于没有引入线程的操作系统，引入线程的系统其系统开销将显著降低。例
30、如，在创建或撤销线程时，系统只需分配与回收很少的资源，而无需像进程创建或撤消那样，花费开销来分配或回收如内存空间、I/O设备等资源；又如，在线程切换时，只需保存和设置少量的寄存器的内容，而无需像进程切换那样，花费开销来保存和设置很多的现场信息。另外，同一个进程内线程之间的通信由于共享所属进程的存储空间，也比进程通信更加容易。2.6 本章小结本章小结n进程管理是处理机管理最主要的部分。本章全面介绍了进程管理覆盖的基础知识，可以看作是操作系统中处理机管理的一个总领，也是后续重点介绍的进程同步、处理机调度等的基础。n本章的内容大致可以分为两个层次的知识：n一是对进程的认识，包括进程的引入、进程的概念与特征、以及进程在内存中的状态及转换。n另一是对进程的管理，包括进程控制、进程组织与进程通信。n另外，由于线程是进程的一种发展与细化，线程的基本知识也在本章的最后给出了简单的阐述。
