第二章进程和线程

1、第第2章章 进程和线程进程和线程 第第2章章 进程和线程进程和线程 现代操作系统的重要特性是现代操作系统的重要特性是程序的程序的并发性和资源的共享性并发性和资源的共享性。这二者相互联。这二者相互联系、相互依赖。为了满足多用户并发计系、相互依赖。为了满足多用户并发计算的要求，现代操作系统是围绕算的要求，现代操作系统是围绕进程进程这这个概念设计和构造的。个概念设计和构造的。 传统的操作系统中，程序不能独立运行，作传统的操作系统中，程序不能独立运行，作为为资源分配资源分配和和独立运行独立运行的基本单位都是进程的基本单位都是进程 操作系统所具有的三大特征也是基于进程而操作系统所具有的三大特征也是基于进

2、程而形成的，应从形成的，应从进程的角度进程的角度来研究操作系统来研究操作系统 在操作系统中，进程是一个极其重要的概念在操作系统中，进程是一个极其重要的概念2.1 进程概念进程概念n2.1.1 多道程序设计多道程序设计n2.1.2 进程概念进程概念2.1.1 多道程序设计多道程序设计 在早期的单道程序或单用户系统中，计算在早期的单道程序或单用户系统中，计算机机按顺序执行按顺序执行程序，各个用户程序也是顺序执程序，各个用户程序也是顺序执行的。行的。I1C1P1P2I2C2 程序的顺序执行程序的顺序执行 1顺序程序活动的特点顺序程序活动的特点n程序执行的程序执行的顺序性顺序性n程序运行环境的程序运行

3、环境的封闭性封闭性 n程序执行结果的程序执行结果的可再现性可再现性 顺序程序的封闭性和可再现性，为程顺序程序的封闭性和可再现性，为程序员调试程序带来了很大方便。但由序员调试程序带来了很大方便。但由于资源独占，使于资源独占，使系统资源利用率非常系统资源利用率非常低。低。n2 多道程序设计多道程序设计n内存中同时存放多道程序内存中同时存放多道程序n程序并发执行（下页图）程序并发执行（下页图）n提高资源利用率和系统吞吐量提高资源利用率和系统吞吐量 多道批处理系统多道批处理系统 3程序并发执行的特征程序并发执行的特征 失去封闭性。失去封闭性。 由于程序的并发执行，系统中的资源不再为一个程序独占，由于程

4、序的并发执行，系统中的资源不再为一个程序独占，因此资源的状态也不再由一个程序决定，而是由并发执行的因此资源的状态也不再由一个程序决定，而是由并发执行的多道程序决定。多道程序决定。 失去对应性：程序与计算不再一一对应。失去对应性：程序与计算不再一一对应。 并发程序在执行期间相互制约。并发程序在执行期间相互制约。 程序并发执行时，由于资源共享，使得一些逻辑上相互独立程序并发执行时，由于资源共享，使得一些逻辑上相互独立的几道程序之间发生了相互制约关系。相互制约将导致并发的几道程序之间发生了相互制约关系。相互制约将导致并发程序具有程序具有“执行执行暂停暂停执行执行”这种间断性的活动规律。这种间断性的活

5、动规律。2.1.2 进程概念进程概念 1引入：用引入：用程序这个静态概念已经不能如实反映程程序这个静态概念已经不能如实反映程序并发执行过程中的这些特征序并发执行过程中的这些特征。2进程概念进程概念n进程定义为进程定义为：程序在并发环境中的执行过程程序在并发环境中的执行过程(p29) n进程进程最根本的属性是最根本的属性是动态性动态性和和并发性并发性。 最早使用进程最早使用进程(process)(process)概念进行操作概念进行操作系统设计的是美国的麻省理工学院在系统设计的是美国的麻省理工学院在MULTICSMULTICS系统和系统和IBMIBM公司的公司的CTSS/360CTSS/360系

6、统上系统上实现的。只是实现的。只是IBM/360IBM/360使用了另一个术语使用了另一个术语任务任务(task)(task)，但两者的实际含义是相同的。，但两者的实际含义是相同的。 “进程进程”是操作系统中最基本、最是操作系统中最基本、最重要的概念之一，重要的概念之一，它对理解、描述和它对理解、描述和设计操作系统都有非常重要的意义设计操作系统都有非常重要的意义。进程和程序的区别进程和程序的区别（1）动态性）动态性n进程进程是程序的一次执行，它是一个是程序的一次执行，它是一个动态的概动态的概 念念；程序程序是完成某个特定功能的指令的有序序是完成某个特定功能的指令的有序序列，它是一个列，它是一个

7、静态的概念静态的概念。n程序可以作为一种软件资源长期保存。进程是程序可以作为一种软件资源长期保存。进程是把程序作为它的运行实体，没有程序，也就没把程序作为它的运行实体，没有程序，也就没有进程。有进程。 （2）并发性）并发性n进程是可以并发执行的进程是可以并发执行的系统中的多进程可以按照自己独立的、不可系统中的多进程可以按照自己独立的、不可预知的速度推进。预知的速度推进。n程序通常不能作为一个独立运行的单位而并程序通常不能作为一个独立运行的单位而并发执行发执行 （3）非对应性）非对应性 程序和进程无一一对应关系程序和进程无一一对应关系（4）异步性）异步性n 各进程在并发执行过程中相互制约，造成各

8、进程在并发执行过程中相互制约，造成各自前进速度的不可预测性。各自前进速度的不可预测性。n 程序是静态的，不具备异步特征程序是静态的，不具备异步特征 3进程的基本特征进程的基本特征 （1）动态性）动态性 进程是程序的一次执行过程，它是临时的、有生命期进程是程序的一次执行过程，它是临时的、有生命期的。表现在它由创建而产生，完成任务后被撤消。的。表现在它由创建而产生，完成任务后被撤消。（2）并发性）并发性 进程是可以并发执行的。系统中的各个进程可以按照进程是可以并发执行的。系统中的各个进程可以按照自己独立的、不可预知的速度推进。自己独立的、不可预知的速度推进。（3）调度性）调度性 进程是系统进行资源

9、分配和调度的一个独立单位进程是系统进行资源分配和调度的一个独立单位2.2 进程的状态和组成进程的状态和组成2.2.1 进程的状态及其转换进程的状态及其转换2.2.2 进程描述进程描述2.2.3 进程队列进程队列2.2.1 进程的状态及其转换进程的状态及其转换1进程的基本状态进程的基本状态(1)(1)就绪（就绪（ReadyReady）状态：）状态：一个进程已经具备运行条件，但由于无一个进程已经具备运行条件，但由于无CPUCPU暂暂时不能运行的状态（当调度给其时不能运行的状态（当调度给其CPUCPU时，立即时，立即可以运行）可以运行）(2)(2)执行状态执行状态(Running)(Running)

10、 进程占有进程占有CPU，并在，并在CPU上运行上运行(3)(3)阻塞状态阻塞状态(blocked) (blocked) 又称等待态。又称等待态。 指进程因等待某种事件的发生而暂时不指进程因等待某种事件的发生而暂时不能运行的状态。能运行的状态。 （即使（即使CPUCPU空闲，该进程也不可运行）空闲，该进程也不可运行） 上述三种状态是进程上述三种状态是进程最基本最基本的状态，在实际的的状态，在实际的操作系统实现中，进程远不止这三种状态。进操作系统实现中，进程远不止这三种状态。进程从无到有是由创建而产生，故它的起点应为程从无到有是由创建而产生，故它的起点应为新建状态（新建状态（NewNew） ，当

11、进程运行完成时要消亡，当进程运行完成时要消亡，此时的状态为此时的状态为终止状态（终止状态（TerminatedTerminated）运行运行状态状态就绪就绪状态状态阻塞阻塞状态状态等待某事件发生等待某事件发生（如等待（如等待I/O）所等待事件发生所等待事件发生（如（如I/O完成）完成）分到分到CPU时间片到时间片到 三种状态的相互转换如下图所示：三种状态的相互转换如下图所示：图图2-1 进程状态及其转换进程状态及其转换图图2-2 2-2 进程的进程的5 5种基本状态及其转换种基本状态及其转换2进程状态的转换进程状态的转换 在进程运行过程中，由于进程自身进展情况及外界环境在进程运行过程中，由于进

12、程自身进展情况及外界环境的变化，进程的状态可以依据一定的条件相互转换：的变化，进程的状态可以依据一定的条件相互转换：新建新建就绪就绪就绪就绪运行运行运行运行阻塞阻塞阻塞阻塞就绪就绪运行运行就绪就绪运行运行终止终止n就绪就绪 - - 运行运行n调度程序选择一个新的进程运行调度程序选择一个新的进程运行n运行运行 - - 就绪就绪n运行进程用完了时间片运行进程用完了时间片n运行进程被中断，因为一高优先级进程处于运行进程被中断，因为一高优先级进程处于就绪状态就绪状态n运行运行 - - 阻塞阻塞n当一进程必须等待时当一进程必须等待时nOS尚未完成服务尚未完成服务n对一资源的访问尚不能进行对一资源的访问尚

13、不能进行n初始化初始化I/O 且必须等待结果且必须等待结果n等待某一进程提供输入等待某一进程提供输入n阻塞阻塞 - - 就绪就绪n当所等待的事件发生时当所等待的事件发生时【思考题思考题】1 1如果系统中有如果系统中有N N个进程，运行的进程最多几个，个进程，运行的进程最多几个，最少几个；就绪进程最多几个最少几个；等待最少几个；就绪进程最多几个最少几个；等待进程最多几个，最少几个？进程最多几个，最少几个？2. 2. 有没有这样的状态转换，为什么？有没有这样的状态转换，为什么？ 阻塞阻塞运行；运行； 就绪就绪阻塞阻塞3. 3. 一个状态转换的发生，是否一定导致另一个转一个状态转换的发生，是否一定导

14、致另一个转换发生，列出所有的可能换发生，列出所有的可能2.2.2 进程描述进程描述1进程映像进程映像n进程映像进程映像由它的由它的（用户）地址空间（用户）地址空间内容、硬件寄存器内容、硬件寄存器内容和与该进程有内容和与该进程有关的核心数据结构关的核心数据结构组成组成。 图图2-3 进程映像模型进程映像模型 2进程控制块的组成进程控制块的组成n进程控制块进程控制块（PCB）有时也称进程描述块）有时也称进程描述块（Process Descriptor），它是进程组成），它是进程组成中中最关键最关键的部分，其中含有进程的描述信的部分，其中含有进程的描述信息和控制信息，是进程动态特性的集中反息和控制信

15、息，是进程动态特性的集中反映，是系统对进程施行识别和控制的依据映，是系统对进程施行识别和控制的依据。进程控制块一般包括以下内容：进程控制块一般包括以下内容：n进程名进程名n特征信息特征信息n进程状态信息进程状态信息n调度优先权调度优先权n通信信息通信信息n现场保护区现场保护区n资源需求资源需求n进程实体信息进程实体信息n族系关系族系关系n其他信息其他信息3进程控制块的作用进程控制块的作用n每个进程有每个进程有惟一惟一的进程控制块的进程控制块n系统利用系统利用PCB来控制和管理进程来控制和管理进程nPCB是进程存在的唯一标志是进程存在的唯一标志2.2.3 进程队列进程队列 为了便于查找，系统把所

16、有的为了便于查找，系统把所有的PCBPCB用用适当的方式组织起来，一般大概有以下三适当的方式组织起来，一般大概有以下三种形式：种形式：(1) (1) 线性方式线性方式 (2) (2) 链接方式链接方式(3) (3) 索引方式索引方式 1线性方式线性方式 图图2-4 PCB线性队列示意图线性队列示意图 优点是简单，容易实现。缺点是系统开销大优点是简单，容易实现。缺点是系统开销大。查找查找一个指定的一个指定的PCB较费时间，较费时间，平均要花费半个平均要花费半个PCB表表长的时间长的时间。早期的早期的UNIX系统就是采用这种形式的表。系统就是采用这种形式的表。2链接方式链接方式l把处于把处于同一状

17、态同一状态的进程按照一定方式链接成一个的进程按照一定方式链接成一个队列队列。就绪队列就绪队列阻塞队列：根据阻塞的原因不同组织成多个阻塞队列阻塞队列：根据阻塞的原因不同组织成多个阻塞队列等待磁盘等待磁盘I/OI/O队列队列等待磁带等待磁带I/OI/O队列队列l每一个队列有一个每一个队列有一个专用队列指针专用队列指针指出该队列中第指出该队列中第一个进程一个进程PCBPCB所在位置。所在位置。图图2-5 PCB链接队列示意图链接队列示意图 3、索引方式、索引方式 l用用索引表索引表记载进程的记载进程的PCBPCB地址地址l对具有对具有相同状态相同状态的进程，分别设置各自的的进程，分别设置各自的PCB

18、PCB索引表索引表就绪索引表就绪索引表阻塞索引表阻塞索引表图图2-6 PCB索引结构示意图索引结构示意图l由于由于单单CPUCPU的计算机系统中，任何时候只有一个的计算机系统中，任何时候只有一个进程处于运行状态。进程处于运行状态。l系统专门设置系统专门设置一个指针一个指针指向当前运行进程的指向当前运行进程的PCBPCB。lUNIXUNIX系统中就有一个系统中就有一个CURPROCURPRO指针，指向现运行进指针，指向现运行进程的程的PCBPCB。2.3 进程管理进程管理n2.3.1 进程图进程图n2.3.2 进程创建进程创建n2.3.3 进程终止进程终止n2.3.4 进程阻塞进程阻塞n2.3.

19、5 进程唤醒进程唤醒2.3.1 进程图进程图 进程图进程图（进程家族图）进程家族图）-Process Graph 描述进程描述进程家族关系家族关系的有向树的有向树一棵进程树表示一个家族，根结点是祖先。一棵进程树表示一个家族，根结点是祖先。一个子进程只有一个父进程一个子进程只有一个父进程AB ： A是是B的父进程的父进程 B是是A的子进程。的子进程。 图图2-7 进程创建的层次关系进程创建的层次关系2.3.2 进程创建进程创建1、引起创建进程的事件：、引起创建进程的事件： （1）用户登录：）用户登录：分时系统分时系统用户在终端上登用户在终端上登录录（2）作业调度：）作业调度：批处理系统批处理系统

20、中为每个提交的作业创中为每个提交的作业创建一个进程；建一个进程； （3）OS提供服务：运行中的用户提出某种请求提供服务：运行中的用户提出某种请求（4）派生新进程）派生新进程：应用进程自己创建一个进程，：应用进程自己创建一个进程，使新进程以并发方式完成特定任务。使新进程以并发方式完成特定任务。 2、进程的创建（创建原语）、进程的创建（创建原语） PCB是进程存在的唯一标识，所以创建一个进程是进程存在的唯一标识，所以创建一个进程的主要任务是为其的主要任务是为其建立一个建立一个PCB。 使用使用创建原语创建原语创建进程的过程：创建进程的过程：（1）申请一个空闲的）申请一个空闲的PCB（2）为新进程分

21、配资源：）为新进程分配资源：（3）初始化）初始化PCB：（4）将新进程）将新进程插入就绪队列。插入就绪队列。UNIX/Linux中的中的fork()系统调用实现进程创建功能。系统调用实现进程创建功能。下面这个下面这个C程序展示了程序展示了UNIX系统中父进程创建子进程及各系统中父进程创建子进程及各自分开活动的情况自分开活动的情况#include void main(int argc,char *argv) int pid; pid = fork(); /* fork another process */ if (pid 0) /* error occurred */ fprintf(stder

22、r, Fork Failed); exit(-1); else if (pid = 0) /* child process */ execlp( /bin/ls, ls,NULL); else /* parent process */ /* parent will wait for the child to complete */ wait(NULL); printf( Child Complete ); exit(0); 2.3.3 进程终止进程终止（撤消原语）（撤消原语） 1、引起进程终止的事件、引起进程终止的事件（1）正常终止）正常终止（2）异常终止）异常终止（3）外部干扰：进程应外界的

23、请求而终止运行）外部干扰：进程应外界的请求而终止运行所谓撤消，是指撤消进程存在的标志所谓撤消，是指撤消进程存在的标志进程控制块进程控制块，从而使其从系统中消亡。，从而使其从系统中消亡。2、终止进程的主要操作过程、终止进程的主要操作过程n找到指定进程的找到指定进程的PCB，终止该进程的运行，终止该进程的运行n回收该进程所占用的全部资源回收该进程所占用的全部资源n终止其所有子孙进程，回收它们所占用的全终止其所有子孙进程，回收它们所占用的全部资源。部资源。n将被终止进程的将被终止进程的PCB从原来队列中摘走从原来队列中摘走2.3.4 进程阻塞（进程阻塞（阻塞原语阻塞原语）1 1、引起进程阻塞的事件、

24、引起进程阻塞的事件 处于运行状态的进程，在其运行过程中期待某一处于运行状态的进程，在其运行过程中期待某一事件发生，事件发生，当被等待的事件还没有发生时当被等待的事件还没有发生时，由进程，由进程自自己己执行阻塞原语，使自己由运行态变为阻塞态。执行阻塞原语，使自己由运行态变为阻塞态。等待键盘输入；等待键盘输入；等待磁盘的数据传输完成；等待磁盘的数据传输完成；等待其它进程发送一个信息等待其它进程发送一个信息当某进程期待的事件已经到来时，唤醒进程。当某进程期待的事件已经到来时，唤醒进程。2 2、进程阻塞的过程、进程阻塞的过程n立即停止当前进程的执行立即停止当前进程的执行n将现行进程的将现行进程的CPU

25、现场保存现场保存n将该进程的现行状态由将该进程的现行状态由“运行运行”改为改为“阻塞阻塞”n转到进程调度程序转到进程调度程序2.3.5 进程唤醒进程唤醒 （唤醒原语）（唤醒原语）n处于阻塞状态的进程处于阻塞状态的进程不能唤醒自己不能唤醒自己，必须由它的合作，必须由它的合作进程用唤醒原语唤醒它。进程用唤醒原语唤醒它。n唤醒原语执行过程如下：唤醒原语执行过程如下： 把阻塞进程从相应的阻塞队列中摘下。把阻塞进程从相应的阻塞队列中摘下。 将现行状态改为就绪状态，然后把该进程插入就将现行状态改为就绪状态，然后把该进程插入就绪队列中。绪队列中。 如果被唤醒的进程比当前运行进程的优先级更高，如果被唤醒的进程

26、比当前运行进程的优先级更高，则设置重新调度标志。则设置重新调度标志。 2.4 线线 程程n2.4.1 线程概念线程概念n2.4.2 线程的实现线程的实现2.4.1 线程概念线程概念n现代操作系统中，进程现代操作系统中，进程只只作为资源拥有作为资源拥有者，而调度和运行的属性赋予新的实者，而调度和运行的属性赋予新的实体体线程线程。n线程（线程（Thread）是进程中实施调度和分是进程中实施调度和分派的基本单位派的基本单位补充：线程引入补充：线程引入 进程的两个基本属性：进程的两个基本属性：n资源的拥有者：资源的拥有者： 给每个进程分配一虚拟地址空间，保存进程映给每个进程分配一虚拟地址空间，保存进程

27、映像，控制一些资源（文件，像，控制一些资源（文件，I/OI/O设备），有状态、设备），有状态、优先级、调度优先级、调度n调度单位：调度单位： 进程是一个执行轨迹进程是一个执行轨迹 以上两个属性构成进程并发执行的基础以上两个属性构成进程并发执行的基础系统必须完成的操作：系统必须完成的操作： n创建进程创建进程n撤消进程撤消进程n进程切换进程切换缺点：缺点： 时间空间开销大，限制并发度的提高时间空间开销大，限制并发度的提高将进程的上述两个属性分开，线程因而产将进程的上述两个属性分开，线程因而产生。生。线程的引入（续线程的引入（续1）n引入进程的目的引入进程的目的是为了使多个程序并发是为了使多个程序

28、并发执行，以改善资源利用率、提高系统吞执行，以改善资源利用率、提高系统吞吐量。吐量。n线程的引入是为了线程的引入是为了减少程序并发执行时减少程序并发执行时的所付出的时空开销。的所付出的时空开销。线程的引入（续线程的引入（续2）1线程的组成线程的组成n每个线程有一个每个线程有一个thread结构，即结构，即线程控制块，用线程控制块，用于保存自己私有于保存自己私有的信息，主要由的信息，主要由以下以下4个基本部分个基本部分组成：组成：图图2-8 thread结构示意图结构示意图n线程必须在某个进程内执行线程必须在某个进程内执行n一个进程可以包含一个线程或多个线程一个进程可以包含一个线程或多个线程图图

29、2-9 单线程和多线程的进程模型单线程和多线程的进程模型 2线程的状态线程的状态与进程相似，线程也有若干种状态：与进程相似，线程也有若干种状态：n运行状态：线程在运行状态：线程在CPU上执行上执行n就绪状态：具备运行条件，一旦分到就绪状态：具备运行条件，一旦分到CPU，可，可 以马上投入运行以马上投入运行 n阻塞状态：线程在等待某个事件发生阻塞状态：线程在等待某个事件发生n终止状态：线程完成任务后终止状态：线程完成任务后线程的状态转换是在一定的条件下实现的线程的状态转换是在一定的条件下实现的 3线程的管理线程的管理n线程创建：调用thread_create创建新线程，建立 thread结构，分

30、配栈结构等，设置为 就绪状态，放入就绪队列n线程终止：线程完成工作后，调用thread_exit终 止自身n线程等待：调用thread_wait等待指定线程终止， 此时该线程处于阻塞状态，指定线程 终止时转为就绪态n线程让权：调用thread_yield放弃CPU，让给另外 的线程运行4线程和进程的关系线程和进程的关系 一个进程可以有多个线程，但至少要有一个线程；而一个进程可以有多个线程，但至少要有一个线程；而一个线程只能在一个进程的地址空间内活动。一个线程只能在一个进程的地址空间内活动。 资源分配给进程资源分配给进程，同一进程的所有线程共享该进程的，同一进程的所有线程共享该进程的所有资源。所

31、有资源。 处理机分配给线程处理机分配给线程，即真正在处理机上运行的是线程。，即真正在处理机上运行的是线程。 线程在执行过程中需要协作同步。不同进程的线程间线程在执行过程中需要协作同步。不同进程的线程间要利用消息通信的办法实现同步。要利用消息通信的办法实现同步。由于线程拥有较少的资源，但又具有传统进程由于线程拥有较少的资源，但又具有传统进程的许多特性，有的把线程叫做的许多特性，有的把线程叫做轻型进程轻型进程（light light weight processweight process，LWPLWP），而把传统的进程叫做），而把传统的进程叫做重重型进程型进程(heavy weight proc

32、ess,HWP)(heavy weight process,HWP)，可把它看，可把它看成拥有一个线程的进程。成拥有一个线程的进程。5引入线程的好处引入线程的好处 易于调度。易于调度。 提高并发性。提高并发性。 开销少。开销少。 利于充分发挥多处理器的功能。利于充分发挥多处理器的功能。 线程的引用使系统设计变得复杂。线程的引用使系统设计变得复杂。无论是采用多进程还是一个进程的多线无论是采用多进程还是一个进程的多线程来实现其并发性都是合理的。用哪一程来实现其并发性都是合理的。用哪一种结构更有效，则取决于应用程序的要种结构更有效，则取决于应用程序的要求。求。n很多系统中已经实现线程，如很多系统中已

33、经实现线程，如Solaris2,Windows 2000,Linux,Java语言语言n实现线程的方式主要有：实现线程的方式主要有：n在用户空间实现在用户空间实现n在核心空间实现在核心空间实现n组合方式：将用户级线程和核心级线程结合组合方式：将用户级线程和核心级线程结合 在一起，取长补短在一起，取长补短2.4.2 线程的实现线程的实现1、在用户空间实现线程、在用户空间实现线程把线程库整个地放在用户空间，核心对线程一无所知。把线程库整个地放在用户空间，核心对线程一无所知。在用户空间实现线程的优点在用户空间实现线程的优点 线程切换速度很快。线程切换速度很快。 调度算法可以是应用程序专用的。调度算法

34、可以是应用程序专用的。 用户级线程可以运行在任何操作系统用户级线程可以运行在任何操作系统 上，包括不支持线程机制的操作系统。上，包括不支持线程机制的操作系统。用户级线程的主要缺点用户级线程的主要缺点 系统调用的阻塞问题。系统调用的阻塞问题。 在单纯用户级线程方式中，多线程应用在单纯用户级线程方式中，多线程应用程序不具有多处理器的优点。程序不具有多处理器的优点。2. 在核心空间实现线程在核心空间实现线程 核心知道线程存在，并对它核心知道线程存在，并对它们实施管理们实施管理在多处理器系统中，核心可在多处理器系统中，核心可以同时调度同一进程的多个以同时调度同一进程的多个线程线程如果一个进程的某个线程

35、阻如果一个进程的某个线程阻塞了，核心可以调度同一个塞了，核心可以调度同一个进程的另一个线程。进程的另一个线程。n优点：核心线程本身也可以优点：核心线程本身也可以是多线程的。是多线程的。n缺点：控制转移开销大缺点：控制转移开销大3. 组合方式组合方式n把用户级线程和核心级线程两种方式结合把用户级线程和核心级线程两种方式结合在一起，吸收二者优点，克服各自不足在一起，吸收二者优点，克服各自不足n核心只知道核心级线程，也只对它们实施核心只知道核心级线程，也只对它们实施调度调度n实现组合方式有不同的模型：实现组合方式有不同的模型：n多对一模型多对一模型n一对一模型一对一模型n多对多模型多对多模型2.5

36、进程的同步和通信进程的同步和通信n2.5.1 进程的同步与互斥进程的同步与互斥n2.5.2 临界资源和临界区临界资源和临界区n2.5.3 互斥实现方式互斥实现方式n2.5.4 信号量信号量n2.5.5 信号量的一般应用信号量的一般应用 由于进程的由于进程的异步性异步性，在争用资源时，常会，在争用资源时，常会出现以下的问题：出现以下的问题：1、系统混乱；、系统混乱；2、数据处理的不可再现性。、数据处理的不可再现性。为了使并发执行的诸进程之间能有效地为了使并发执行的诸进程之间能有效地共享资共享资源和相互合作源和相互合作，从而使程序的执行具有，从而使程序的执行具有可再现可再现性性，必须提供进程同步机

37、制。，必须提供进程同步机制。进程的相互关系主要分为如下三种形式：进程的相互关系主要分为如下三种形式： 互斥：竞争关系互斥：竞争关系 同步：协作关系同步：协作关系 通信：信息交流通信：信息交流2.5.1 进程的同步与互斥进程的同步与互斥1同步（书中例子）同步（书中例子）n定义：定义：进程间共同完成一项任务时直接发进程间共同完成一项任务时直接发生相互作用的关系，这些进程在执行时间生相互作用的关系，这些进程在执行时间次序上必须遵循确定的规律次序上必须遵循确定的规律(有一定约束有一定约束)。n相互合作关系相互合作关系n直接相互制约直接相互制约在现实生活中，同步的例子：在现实生活中，同步的例子：例如，在

38、一辆公共汽车上，例如，在一辆公共汽车上，司机的职责司机的职责是驾是驾驶车辆；驶车辆；售票员的工作售票员的工作是售票、开关车门，是售票、开关车门，各有各的职责范围。但两者的工作又需要相各有各的职责范围。但两者的工作又需要相互配合、协调。当汽车到站时，司机将车辆互配合、协调。当汽车到站时，司机将车辆停稳后，售票员才能将车门打开让乘客上下停稳后，售票员才能将车门打开让乘客上下车，然后关车门，只有在得到车门已经关好车，然后关车门，只有在得到车门已经关好的信号后，司机才能开动汽车继续前进。所的信号后，司机才能开动汽车继续前进。所以，以，在司机停止、启动汽车和售票员开关门在司机停止、启动汽车和售票员开关门

39、之间有两个同步的过程。之间有两个同步的过程。 到站停车到站停车 开开 车车 开开 车车 门门 关关 车车 门门 售售 票票 正常行车正常行车。售票员售票员司机司机n定义：定义：逻辑上本来完全独立的若干进程，由于竞逻辑上本来完全独立的若干进程，由于竞争同一个资源而产生的相互制约关系。争同一个资源而产生的相互制约关系。n它们的它们的运行不具有时间次序的特征运行不具有时间次序的特征：谁先向系统：谁先向系统提出申请，谁就先执行提出申请，谁就先执行n相互竞争关系相互竞争关系n间接相互制约间接相互制约 2互斥（书中例子）互斥（书中例子） 同步和互斥的实质都是对进程在执行时同步和互斥的实质都是对进程在执行时

40、序上的某种限制序上的某种限制 ，广，广 义上，义上，互斥是一种特互斥是一种特殊的同步。殊的同步。 进程同步进程同步：指多个相关进程在执行次序：指多个相关进程在执行次序上协调。用于保证这种关系的相应机制称为上协调。用于保证这种关系的相应机制称为进程同步机制进程同步机制。2.5.2 临界资源和临界区临界资源和临界区1临界资源和临界区临界资源和临界区n一次仅允许一个进程使用的资源称为一次仅允许一个进程使用的资源称为临界资源临界资源（Critical Resource）。n如：进程、共享一台打印机，若让它们交替使如：进程、共享一台打印机，若让它们交替使用用, , 则得到的结果肯定不是我们希望的。则得到

41、的结果肯定不是我们希望的。n临界资源可能是硬件，也可能是软件临界资源可能是硬件，也可能是软件：变量，数据，：变量，数据，表格，队列等。表格，队列等。n并发进程对临界资源的访问必须作某种限制，否则并发进程对临界资源的访问必须作某种限制，否则就可能出就可能出与时间有关的错误与时间有关的错误，如：联网售票。，如：联网售票。临界区临界区 在每个进程中访问临界资源的在每个进程中访问临界资源的那段程序那段程序叫做叫做临界临界区（区（Critical Section），简称，简称CS区区。各进程要互斥地进入自己的临界区。各进程要互斥地进入自己的临界区。【注意注意】：临界区是对某一临界资源而言的，临界区是对某

42、一临界资源而言的，对于不对于不同临界资源的临界区，它们之间不存在互斥同临界资源的临界区，它们之间不存在互斥。例如：例如：有程序段有程序段A、B是关于变量是关于变量X的临界区，而的临界区，而C、D是关于变量是关于变量Y的临界区，那么，的临界区，那么，A、B之间需要互斥之间需要互斥执行，执行，C、D之间也要互斥执行，而之间也要互斥执行，而A与与C、B与与D之间之间不用互斥执行。不用互斥执行。 2进程的一般结构进程的一般结构图图2-10 典型进程的一般结构典型进程的一般结构 进程互斥进入临界区都要进程互斥进入临界区都要遵循一种通用模式：遵循一种通用模式：进入前要申请，进入前要申请，获准后方可进入；获

43、准后方可进入；执行后要退出执行后要退出 (释放释放) ，然后才可以执行其他代码然后才可以执行其他代码3临界区进入准则（安全使用临界资源）临界区进入准则（安全使用临界资源） 如果若干进程要求进入空闲的临界区，一次仅如果若干进程要求进入空闲的临界区，一次仅允许一个进程进入。允许一个进程进入。（空闲让进）（空闲让进） 任何时候，处于临界区内的进程不可多于一个。任何时候，处于临界区内的进程不可多于一个。 （忙则等待）（忙则等待） 进入临界区的进程要在有限时间内退出。进入临界区的进程要在有限时间内退出。 （有限等待）（有限等待） 如果进程不能进入自己的临界区，则应让出如果进程不能进入自己的临界区，则应让

44、出CPU，避免进程出现，避免进程出现“忙等忙等”现象。现象。（让权等待）（让权等待） 图图2-11 互斥使用临界区互斥使用临界区2.5.3 互斥实现方式互斥实现方式n从实现机制方面来说，分为：从实现机制方面来说，分为：n硬件方法硬件方法n软件方法软件方法1利用硬件方法解决进程互斥问题利用硬件方法解决进程互斥问题（1）禁止中断：进程进入临界区后关闭中）禁止中断：进程进入临界区后关闭中 断，离开后开放中断。断，离开后开放中断。（2）专用机器指令：利用）专用机器指令：利用TSL指令解决进指令解决进程互斥进入临界区问题程互斥进入临界区问题2原语原语n是机器指令的延伸，往往是为完成某些特定是机器指令的延

45、伸，往往是为完成某些特定的功能而编制的一段系统程序。原语操作也的功能而编制的一段系统程序。原语操作也称做称做“原子操作原子操作”（atomic action），），即一即一个操作中的所有动作要么全做，要么全不做。个操作中的所有动作要么全做，要么全不做。n执行原语操作时，要屏蔽中断，以保证其操执行原语操作时，要屏蔽中断，以保证其操作的不可分割性。作的不可分割性。n如如P、V操作等。操作等。3利用软件方法解决进程互斥问题利用软件方法解决进程互斥问题 为每类临界区设置一把锁，该锁有打开和关为每类临界区设置一把锁，该锁有打开和关闭两种状态闭两种状态。n关锁原语关锁原语lock (W): while (

46、W=1); W=1;n开锁原语开锁原语unlock (W): W =0;W=1表示关锁表示关锁W=0表示开锁表示开锁 A、B两个进程互斥使用一台打印机，两个进程互斥使用一台打印机，W初值为初值为02.5.4 信号量信号量1965年，荷兰学者年，荷兰学者E.W.Dijkstra提出。提出。 整型信号量整型信号量 （多用于进程互斥（多用于进程互斥, 忙则等待忙则等待） 结构型信号量结构型信号量（多用于进程同步（多用于进程同步,让权等待让权等待） 二值信号量二值信号量（只有（只有0、1两个值两个值) 现在，信号量机制已广泛应用于现在，信号量机制已广泛应用于单处理机、多单处理机、多处理机及计算机网络处

47、理机及计算机网络中中.1整型信号量整型信号量 除初始化外，仅能通过两个标准的原子操作来访问。除初始化外，仅能通过两个标准的原子操作来访问。n两个原子操作为：两个原子操作为：P操作、操作、 V操作操作nP操作操作最初源于荷兰语最初源于荷兰语proberen，表示测试；，表示测试；V操操作作源于荷兰语源于荷兰语verhogen，表示增加。，表示增加。n有些书上将有些书上将P操作称做操作称做wait或者或者DOWN操作，将操作，将V操作称做操作称做signal或者或者UP操作。操作。n典型的典型的P和和V操作的伪代码如下操作的伪代码如下 P(s) while s=0 ； s- ； V(s) s+;

48、n以上操作均为以上操作均为不可中断不可中断的原语操作的原语操作 设置一互斥信号量设置一互斥信号量mutex，初值为初值为1，然后，然后将各进程的将各进程的CS置于置于P(mutex) 和和V(mutex)之间即可。之间即可。 do P(mutex); 临界区临界区 V(mutex); 其他代码区其他代码区while(1);利用信号量实现互斥利用信号量实现互斥2结构型信号量（记录型信号量）结构型信号量（记录型信号量）n因其采用了因其采用了结构型的数据结构结构型的数据结构而得名。而得名。n整型信号机制使进程处于整型信号机制使进程处于“忙式等待忙式等待”状态，消耗状态，消耗CPU时间。结构型信号量采

49、时间。结构型信号量采取取“让权等待让权等待”策略策略n以后没有特殊说明，凡称信号量就指结以后没有特殊说明，凡称信号量就指结构型信号量。构型信号量。n结构型信号量结构型信号量一般是由两个成员组成的数一般是由两个成员组成的数据结构。其中一个成员是整型变量，表示据结构。其中一个成员是整型变量，表示该信号量的值；另一个是指向该信号量的值；另一个是指向PCB的指针。的指针。 typedef struct int value; struct PCB *list; semaphore;P操作的定义如下：操作的定义如下： void P(semaphore S) S.value- ; if(S.value0)

50、把这个进程加到把这个进程加到S.list队列；队列； block( )； nV操作的定义如下：操作的定义如下： void V(semaphore S) S.value+； if(S.value0: 某类资源可用单元数。某类资源可用单元数。 P(S)：请求分配一个单元的资源。请求分配一个单元的资源。S.Value=0: 无资源可用，无资源可用，|S.Value|表示等待队列表示等待队列 中的进程数。中的进程数。 V(S)：释放一个单位资源、激活等待队中的进程。释放一个单位资源、激活等待队中的进程。信号量的值与相应资源的使用情况有关信号量的值与相应资源的使用情况有关图图2-17 信号量的一般结构及

51、信号量的一般结构及PCB队列队列 对信号量的操作有如下严格限制：对信号量的操作有如下严格限制：1. 信号量可以赋初值，且初值为非负数。信号量可以赋初值，且初值为非负数。2. 信号量的值可以修改，但只能由信号量的值可以修改，但只能由P和和V操作来访问操作来访问 3二值信号量二值信号量n结构型信号量的取值可以是正数、结构型信号量的取值可以是正数、0或者负数或者负数n二值信号量的值只能是二值信号量的值只能是0或或12.5.5 信号量的一般应用信号量的一般应用 1用信号量实现进程互斥用信号量实现进程互斥 Pa: Pb: P(mutex) P(mutex) 分配打印机分配打印机 释放打印机释放打印机 （

52、读写分配表）（读写分配表） （读写分配表）（读写分配表） V(mutex) V(mutex) 打印机分配表的互斥使用情况打印机分配表的互斥使用情况 利用信号量实现互斥的一般模型是：利用信号量实现互斥的一般模型是： 进程进程P1 进程进程P2 进程进程Pn P(mutex); P(mutex); P(mutex); 临界区临界区 临界区临界区 临界区临界区 V(mutex); V(mutex); V(mutex); 其中，其中，信号量信号量mutex用于互斥，初值为用于互斥，初值为1使用使用P, V操作实现互斥时应注意两点：操作实现互斥时应注意两点： 在每个程序中用于实现互斥的在每个程序中用于实

53、现互斥的P(mutex)和和V(mutex)必须成对出现必须成对出现，即先做，即先做P，进，进入临界区；后做入临界区；后做V，退出临界区。，退出临界区。 互斥信号量互斥信号量mutex的的初值一般为初值一般为1。2用信号量实现进程简单用信号量实现进程简单同步同步图图2-18 简单供者和用者对缓冲区的使用关系简单供者和用者对缓冲区的使用关系n供者和用者间要交换两个消息：缓冲区空和供者和用者间要交换两个消息：缓冲区空和缓冲区满的状态。缓冲区满的状态。n设置两个信号量：设置两个信号量：nS1表示缓冲区是否空（表示缓冲区是否空（0表示不空，表示不空，1表示空）。表示空）。nS2表示缓冲区是否满（表示缓

54、冲区是否满（0表示不满，表示不满，1表示满）。表示满）。n规定规定S1和和S2的初值分别为的初值分别为1和和0 供者进程供者进程 用者进程用者进程 L1: P(S1) L2: 启动读卡机启动读卡机 P(S2) ; 从缓冲区取出信息从缓冲区取出信息 收到输入结束中断收到输入结束中断 V(S1); V(S2); 加工并且存盘加工并且存盘 goto L1; goto L2;用用P和和V操作实现同步时应注意如下三点：操作实现同步时应注意如下三点： 分析进程间的制约关系，确定信号量种类。分析进程间的制约关系，确定信号量种类。 信号量的初值与相应资源的数量有关，也与信号量的初值与相应资源的数量有关，也与P

55、, V操操作在程序代码中出现的位置有关。作在程序代码中出现的位置有关。 同一信号量的同一信号量的P, V操作要操作要“成对成对”出现，但是，它出现，但是，它们分别出现在不同的进程代码中。们分别出现在不同的进程代码中。2.6 经典进程同步问题经典进程同步问题1生产者生产者-消费者问题消费者问题n如果一个进程能产生并释放资源，则该进如果一个进程能产生并释放资源，则该进程称做程称做生产者生产者；如果一个进程单纯使用；如果一个进程单纯使用（消耗）资源，则该进程称做（消耗）资源，则该进程称做消费者消费者。生产者生产者-消费者问题表述如下消费者问题表述如下:n一组一组生产者进程和生产者进程和一组一组消费者

56、进程（设每组消费者进程（设每组有多个进程）通过缓冲区发生联系。生产者有多个进程）通过缓冲区发生联系。生产者进程将生产的产品（数据、消息等统称为产进程将生产的产品（数据、消息等统称为产品）送入缓冲区，消费者进程从中取出产品。品）送入缓冲区，消费者进程从中取出产品。假定缓冲区共有假定缓冲区共有N个，可把它们设想成一个个，可把它们设想成一个环形缓冲池。环形缓冲池。 生产者生产者-消费者问题环形缓冲池消费者问题环形缓冲池它们应满足如下它们应满足如下同步条件同步条件： 任一时刻所有生产者存任一时刻所有生产者存放产品的单元数不能超过放产品的单元数不能超过缓冲区的总容量（缓冲区的总容量（N ）。）。 所有消

57、费者取出产品的所有消费者取出产品的总量不能超过所有生产者总量不能超过所有生产者当前生产产品的总量。当前生产产品的总量。在此问题中：在此问题中：（1）生产者之间要）生产者之间要互斥互斥使用缓冲区；使用缓冲区； 消费者之间要消费者之间要互斥互斥使用缓冲区；使用缓冲区； 生产者、消费者之间要生产者、消费者之间要互斥互斥使用缓冲区。使用缓冲区。（2） 生产者、消费者之间有生产者、消费者之间有的关系。的关系。1.设缓冲区的编号为设缓冲区的编号为0N-1，in和和out分别是生产者进程和分别是生产者进程和消费者进程使用的指针，指消费者进程使用的指针，指向下面可用的缓冲区，初值向下面可用的缓冲区，初值都是都

58、是0。2.设置三个信号量：设置三个信号量： full：表示放有产品的缓冲区数，其初值为表示放有产品的缓冲区数，其初值为0。empty：表示可供使用的缓冲区数，其初值为表示可供使用的缓冲区数，其初值为N。mutex：互斥信号量，初值为互斥信号量，初值为1，表示各进程互斥进，表示各进程互斥进入临界区，保证任何时候只有一个进程使用缓冲区。入临界区，保证任何时候只有一个进程使用缓冲区。生产者进程生产者进程Producer： 消费者进程消费者进程Consumer： while(TRUE) while(TRUE) P(empty); P(full); P(mutex); P(mutex); 产品送往产品送

59、往buffer(in); 从从buffer(out)中取出产品；中取出产品； in=(in+1)mod N; out=(out+1)mod N; /*以以N为模为模*/ /*以以N为模为模*/ V(mutex); V(mutex); V(full); V(empty); P(mutex);P(full);P(mutex);P(empty); 读者读者-写者问题也是一个著名的进程写者问题也是一个著名的进程互斥互斥访问访问有限资源的同步问题。例如，一个航班预订系统有有限资源的同步问题。例如，一个航班预订系统有一个大型数据库，很多竞争进程要对它进行读、写。一个大型数据库，很多竞争进程要对它进行读、写

60、。允许多个进程允许多个进程同时读同时读该数据库，但是在任何时候如该数据库，但是在任何时候如果果有一个进程写有一个进程写（即修改）数据库，那么就（即修改）数据库，那么就不允许不允许其他进程访问它其他进程访问它 既不允许写，也不允许读。既不允许写，也不允许读。2读者读者-写者问题写者问题 设置两个信号量：读互斥信号量设置两个信号量：读互斥信号量rmutex和写和写互斥信号量互斥信号量wmutex。另外设立一个读计数。另外设立一个读计数器器readcount，它是一个整型变量，初值为，它是一个整型变量，初值为0。nrmutex：用于读者互斥地访问：用于读者互斥地访问readcount，初值为初值为1