第2章操作系统之进程管理

1、第二章进程管理第二章进程管理目目 录录 2.1 进程的基本概念进程的基本概念 2.2 进程控制进程控制 2.3 进程同步进程同步 2.4 经典进程的同步问题经典进程的同步问题 2.5 管程机制管程机制 2.6 进程通信进程通信 2.7 线程线程第二章 进 程 管 理 2.1 进程的基本概念进程的基本概念 2.1.1 程序的顺序执行及其特征程序的顺序执行及其特征 1. 程序的顺序执行程序的顺序执行 仅当前一操作(程序段)执行完后，才能执行后继操作。例如，在进行计算时，总须先输入用户的程序和数据，然后进行计算，最后才能打印计算结果。 S1: a =x+y; S2: b =a-5; S3: c =b

2、+1;第二章 进 程 管 理 图图 2-1 程序的顺序执行程序的顺序执行 S1 S2 S3(b)三条语句的顺序执行 I1 C1 P1(a)程序的顺序执行第二章 进 程 管 理 2. 程序顺序执行时的特征程序顺序执行时的特征 顺序性：(2) 封闭性： (3) 可再现性： 第二章 进 程 管 理 2.1.2 前趋图前趋图 前趋图是一个有向无循环图无循环图，用于描述进程之间执行的前后关系。 P1P4P3P2P6P5P7第二章 进 程 管 理 每个结点还具有一个重量(Weight)，用于表示该结点所含有的程序量或结点的执行时间。 IiCiPi和S1S2S3 图 2-2 前趋图 P1P3P8P9P4P2

3、P5P6P7S1S2S3(a) 具有九个结点的前趋图(b) 具有循环的前趋图第二章 进 程 管 理 应当注意，前趋图中必须不存在循环，但在图2-2(b)中却有着下述的前趋关系：S2S3, S3S2 第二章 进 程 管 理 2.1.3 程序的并发执行及其特征程序的并发执行及其特征 程序的并发执行程序的并发执行对于具有下述四条语句的程序段： S1: a =x+2 S2: b =y+4 S3: c =a+b S4: d =c+b 第二章 进 程 管 理 S2 S3 S4 S1图 2-4 四条语句的前趋关系第二章 进 程 管 理 2. 程序并发执行时的特征程序并发执行时的特征 第二章 进 程 管 理

4、举例说明举例说明n=5;第二章 进 程 管 理 (1) N =N+1在Print(N)和N =0之前，此时得到的N值分别为6, 6, 0。 (2) N =N+1在Print(N)和N =0之后，此时得到的N值分别为5, 0, 1。 (3) N =N+1在Print(N)和N =0之间，此时得到的N值分别为5, 6, 0。 三种可能的结果三种可能的结果第二章 进 程 管 理 2.1.4 进程的特征与状态进程的特征与状态 程序的并发执行，产生了一些新的程序的并发执行，产生了一些新的特征，如特征，如不可再现性不可再现性，原有程序的概念原有程序的概念不能充分描述并发执行问题，产生了进不能充分描述并发执

5、行问题，产生了进程的概念。程的概念。 问题问题1答案答案第二章 进 程 管 理 较典型的进程定义有较典型的进程定义有： (1) 进程是程序的一次执行。进程是程序的一次执行。 (2) 进程是一个程序及其数据在处理机上顺序执行时进程是一个程序及其数据在处理机上顺序执行时所发生的活动。所发生的活动。 (3) 进程是程序在一个数据集合上运行的过程，它是进程是程序在一个数据集合上运行的过程，它是系统进行资源分配和调度的一个独立单位。系统进行资源分配和调度的一个独立单位。（4）功能完整的程序在处理机上执行的过程）功能完整的程序在处理机上执行的过程） 第二章 进 程 管 理 在引入了进程实体的概念后，我们可

6、以把传统在引入了进程实体的概念后，我们可以把传统OS中中的进程定义为：的进程定义为：“进程是进程实体的运行过程，是系统进程是进程实体的运行过程，是系统进行资源分配和调度的一个独立单位进行资源分配和调度的一个独立单位”。 进程定义进程定义第二章 进 程 管 理 2.1.4 进程的特征与状态进程的特征与状态 进程的特征进程的特征第二章 进 程 管 理 p结构特征结构特征 进程结构进程结构动态特征的集中反映动态特征的集中反映描述要完成的功能描述要完成的功能操作对象及工作区操作对象及工作区第二章 进 程 管 理 p动态性动态性 进程最基本的特征是动态性进程最基本的特征是动态性 进程的生命周期：进程的生

7、命周期： 进程由创建而产生，由调度而执行，由撤销进程由创建而产生，由调度而执行，由撤销而消亡的过程而消亡的过程第二章 进 程 管 理 p并发性并发性p独立性独立性进程是一个能独立运行、独立分配资进程是一个能独立运行、独立分配资源、独立接受调度的基本单位源、独立接受调度的基本单位p异步性异步性进程按进程按各自各自独立的不可预知的速度向前推独立的不可预知的速度向前推进进第二章 进 程 管 理 进程与程序的区别：进程与程序的区别：1、进程是动态的，程序是静态的，如如os教材叫程序，讲教材叫程序，讲课的过程叫进程课的过程叫进程2、 进程是一个暂时的概念，而程序是永久的3、进程有自己的数据结构进程控制块

8、PCB4、进程和 程序并不一定是一一对应的。可能多个进程对应一个程序，或一个程序对应多个进程第二章 进 程 管 理 进程进程程序程序动态静态暂时永久并行串行PCB一个多个多个一个第二章 进 程 管 理 思考题思考题 进程和程序的最根本区别是（）单选 A、对资源的占有类型和数量 B、进程是动态的，而程序是静态的 C、看他们能否并发执行 D、进程规模较小、程序规模较大第二章 进 程 管 理 进程举例第二章 进 程 管 理 2. 进程的三种基本状态进程的三种基本状态 就绪就绪(Ready)状态状态 ：获得了除处理机之外的所获得了除处理机之外的所有资源有资源2) 执行状态：执行状态：单处理机该状态的进

9、程只有一个单处理机该状态的进程只有一个3) 阻塞状态阻塞状态 ：除处理机外，尚有其他资源没有得除处理机外，尚有其他资源没有得到满足到满足第二章 进 程 管 理 就绪阻塞执行时间片完进程调度I/O完成I/O请求第二章 进 程 管 理 执行状态执行状态p已经获得已经获得CPU，正在运行。，正在运行。p在单处理机系统中，只有一个进程处于在单处理机系统中，只有一个进程处于执行状态，多处理机系统则有多个处于执行状态，多处理机系统则有多个处于执行状态。执行状态。第二章 进 程 管 理 阻塞状态阻塞状态p正在执行的进程由于发生某事件而暂时正在执行的进程由于发生某事件而暂时无法继续执行时，放弃处理机而进入的无

10、法继续执行时，放弃处理机而进入的状态，又称等待状态。状态，又称等待状态。p引起阻塞的事件有：引起阻塞的事件有：p请求请求I/Op申请缓存申请缓存第二章 进 程 管 理 就绪状态就绪状态p进程已经分配了除处理机以外的所有必进程已经分配了除处理机以外的所有必要资源，只要再获得处理机就能够运行要资源，只要再获得处理机就能够运行的状态。的状态。p这样的进程可能有多个，通常排成一个这样的进程可能有多个，通常排成一个队列，称就绪队列。队列，称就绪队列。第二章 进 程 管 理 进程状态变迁图 进程的状态不是固定不变的，而是在不断变换。如下图所示：第二章 进 程 管 理 第二章 进 程 管 理 图 2-5 进

11、程的三种基本状态及其转换 创建撤销就绪阻塞执行进程调度进程调度时间片完时间片完I/O请求请求I/O完成完成第二章 进 程 管 理 图 2-5 进程的三种基本状态及其转换 就绪阻塞执行时间片完进程调度I/O完成I/O请求创建撤销第二章 进 程 管 理 3. 挂起状态挂起状态挂起：让进程暂时不参与资源竞争。挂起：让进程暂时不参与资源竞争。引入挂起状态的原因引入挂起状态的原因 （1）终端用户的请求（调试程序）。）终端用户的请求（调试程序）。 (2) 父进程请求。父进程请求。 (3) 负荷调节的需要（系统负荷过重）。负荷调节的需要（系统负荷过重）。 (4) 操作系统的需要。操作系统的需要。1) （5）

12、某些设备故障）某些设备故障 第二章 进 程 管 理 2) 进程状态的转换进程状态的转换 活动就绪readya静止就绪readys。 (2) 活动阻塞blocka静止阻塞blocks。 (3) 静止就绪readys活动就绪readya。 (4) 静止阻塞blocks活动阻塞blocka。 第二章 进 程 管 理 图图 2-6 具有挂起状态的进程状态图具有挂起状态的进程状态图 执行执行活动活动就绪就绪活动活动阻塞阻塞静止静止阻塞阻塞静止静止就绪就绪挂起挂起激活激活挂起挂起激活激活挂起挂起释放释放释放释放请求请求I/O第二章 进 程 管 理 图图 2-6 具有挂起状态的进程状态图具有挂起状态的进程状

13、态图 活动就绪静止就绪执行挂起激活释放挂起活动阻塞静止阻塞挂起激活释放请求I/O第二章 进 程 管 理 练习练习 一个进程被唤醒，意味着（） A、该进程的优先数变为最大 B、该进程获得了CPU C、该进程从阻塞状态变为就绪状态 D、该进程排在了就绪队列队首理解：唤醒指的是阻塞到就绪激活指的是静止到活动（挂起的反义词）第二章 进 程 管 理 练习练习 进程的三种基本状态之间，下列（）转换是不能进行的 A、就绪状态到执行状态 B、执行状态到阻塞状态 C、阻塞状态到执行状态 D、阻塞状态到就绪状态第二章 进 程 管 理 进程控制块的特征进程控制块的特征uPCB是是OS中最重要的记录型结构中最重要的记

14、录型结构uOS用用PCB对并发进程进行管理和控制对并发进程进行管理和控制uPCB是进程存在的唯一标志是进程存在的唯一标志uPCB常驻内存常驻内存uOS专门开辟专门开辟PCB区将所有的区将所有的PCB组织成组织成若干个链表或队列若干个链表或队列第二章 进 程 管 理 2.1.5 进程控制块进程控制块 1. 进程控制块的作用进程控制块的作用 进程控制块的作用是使一个在多道程序环境下不能独立运行的程序(含数据)，成为一个能独立运行的基本单位，一个能与其它进程并发执行的进程。或者说，OS是根据PCB来对并发执行的进程进行控制和管理的。PCB的作用：的作用：1、标志进程的存在、标志进程的存在2、记录进程

15、信息、记录进程信息第二章 进 程 管 理 2. 进程控制块中的信息进程控制块中的信息 u 进程标识符进程标识符u处理机状态处理机状态u进程调度信息进程调度信息u进程控制信息进程控制信息第二章 进 程 管 理 1) 进程标识符进程标识符 进程标识符用于惟一惟一地标识一个进程。一个进程通常有两种标识符： (1) 内部标识符。内部标识符。在所有的操作系统中，都为每一个进 程赋予一个惟一的数字数字标识符，它通常是一个进程的序号。 设置内部标识符主要是为了方便系统使用。 (2) 外部标识符。外部标识符。它由创建者提供，通常是由字母、数字组成，往往是由用户(进程)在访问该进程时使用。为了描述进程的家族关系

16、， 还应设置父进程标识及子进程标识。此外，还可设置用户标识，以指示拥有该进程的用户。 第二章 进 程 管 理 2) 处理机状态处理机状态处理机状态信息主要是由处理机的各种寄存器中的内容组成的。 通用寄存器通用寄存器，又称为用户可视寄存器，用于暂存信息， 在大多数处理机中，有有 832 个通用寄存器； 指令计数器指令计数器，其中存放了要访问的下一条指令的地址； 程序状态字程序状态字PSWPSW，其中含有状态信息，如条件码、执行方式、 中断屏蔽标志等； 用户栈指针用户栈指针， 指每个用户进程都有一个或若干个与之相关的系统栈，用于存放过程和系统调用参数及调用地址。栈指针指向该栈的栈顶。 第二章 进

17、程 管 理 3) 进程调度信息进程调度信息 在PCB中还存放一些与进程调度和进程对换有关的信息，包括： 进程状态进程状态，指明进程的当前状态， 作为进程调度和对换时的依据； 进程优先级进程优先级，用于描述进程使用处理机的优先级别的一个整数， 优先级高的进程应优先获得处理机； 进程调度所需的其它信息进程调度所需的其它信息，它们与所采用的进程调度算法有关，比如，进程已等待CPU的时间总和、 进程已执行的时间总和等； 事件事件，是指进程由执行状态转变为阻塞状态所等待发生的事件，即阻塞原因即阻塞原因。 第二章 进 程 管 理 4) 进程控制信息进程控制信息 程序和数据的地址程序和数据的地址， 是指进程

18、的程序和数据所在的内存或外存地(首)址，以便再调度到该进程执行时，能从PCB中找到其程序和数据； 进程同步和通信机制进程同步和通信机制，指实现进程同步和进程通信时必需的机制， 如消息队列指针、信号量等，它们可能全部或部分地放在PCB中； 资源清单资源清单，是一张列出了除CPU以外的、进程所需的全部资源及已经分配到该进程的资源的清单； 链接指针链接指针， 它给出了本进程(PCB)所在队列中的下一个进程的PCB的首地址。 第二章 进 程 管 理 3. 进程控制块的组织方式进程控制块的组织方式 1) 链接方式链接方式 图 2-7 PCB链接队列示意图 PCB14PCB2PCB3PCB4PCB5PCB

19、6PCB7PCB8PCB93087901执行指针就绪队列指针阻塞队列指针空闲队列指针只有一个只有一个不同的事件不同的事件可有多个可有多个线性线性表表第二章 进 程 管 理 第二章 进 程 管 理 2) 索引方式索引方式 图 2-8 按索引方式组织PCB 执行指针就绪索引表PCB1PCB2PCB3PCB4PCB5PCB6PCB7阻塞索引表就绪表指针阻塞表指针Unix中对多中对多可以有多少可以有多少个进程呢？个进程呢？第二章 进 程 管 理 2.2 进进 程程 控控 制制 概念概念进程控制：进程控制：就是系统使用一些具有特定功能的就是系统使用一些具有特定功能的程序段来创建、撤销进程以及完成进程各种

20、状程序段来创建、撤销进程以及完成进程各种状态间的转换，从而达到多进程高效率并发执行态间的转换，从而达到多进程高效率并发执行和协调，实现资源共享的目的。和协调，实现资源共享的目的。 原语：原语：系统态下执行的某些具有特定功能的程序段称为原系统态下执行的某些具有特定功能的程序段称为原语。语。即不可中断的过程。即不可中断的过程。 第二章 进 程 管 理 进程控制进程控制 进程控制包括进程控制包括： 进程创建进程创建、 进程撤消进程撤消、 进程阻塞进程阻塞、 进程唤醒进程唤醒。 这些操作都要对应地执行一个特殊的这些操作都要对应地执行一个特殊的程序段（操作系统核心程序），同时系程序段（操作系统核心程序）

21、，同时系统也通过系统调用给用户提供进程控制统也通过系统调用给用户提供进程控制的功能。教材上叫的功能。教材上叫原语原语（一种特殊的系（一种特殊的系统调用）。统调用）。第二章 进 程 管 理 2.2 进进 程程 控控 制制 原语（原语（Atomic Operation）：）：特点：特点：原子性，原语本身有若干条指令组成，要原子性，原语本身有若干条指令组成，要么全做，要么全不做，不允许中断，不可分割，不么全做，要么全不做，不允许中断，不可分割，不允许并发执行允许并发执行缺点：缺点：希望原语越小越好希望原语越小越好分类：分类：创建原语创建原语撤销原语撤销原语阻塞原语阻塞原语挂起原语挂起原语唤醒原语唤醒

22、原语激活原语。激活原语。 图 2-9 进程树 第二章 进 程 管 理 2.2 进进 程程 控控 制制 2.2.1 进程的创建进程的创建 1. 进程图(Process Graph) 图 2-9 进程树 DEFGHBCIJKLMA第二章 进 程 管 理 2. 引起创建进程的事件引起创建进程的事件 用户登录。 (2) 作业调度。 (3) 提供服务。 (4) 应用请求。 系统内核创建系统内核创建第二章 进 程 管 理 3. 进程的创建进程的创建(Creation of Progress) (1)申请空白申请空白PCB。 (2) 为新进程分配资源。为新进程分配资源。 (3) 初始化进程控制块。初始化进程

23、控制块。 (4) 将新进程插入就绪队列，如果进程就绪队列能将新进程插入就绪队列，如果进程就绪队列能够接纳新进程，够接纳新进程， 便将新进程插入就绪队列。便将新进程插入就绪队列。 创建原语创建原语create（）（）第二章 进 程 管 理 1 1）申请空白申请空白PCBPCB 2 2）为新进程分配资源为新进程分配资源（为进程的程序和数据（为进程的程序和数据，以及用户栈分配内存，以及用户栈分配内存资源）资源） 3 3）初始化进程控制块初始化进程控制块（包括初始化标识符信（包括初始化标识符信息、处理机状态信息以息、处理机状态信息以及处理机控制信息）及处理机控制信息） 4 4）将新进程插入就绪将新进程

24、插入就绪队列（如就绪队列能够队列（如就绪队列能够接纳新进程，则插入）接纳新进程，则插入）。第二章 进 程 管 理 第二章 进 程 管 理 练习题 下列步骤中，（）不是创建进程所必须的。 A、建立一个进程控制块 B、为进程分配内存 C、为进程分配CPU D、将其PCB放入就绪队列第二章 进 程 管 理 2.2.2 进程的终止进程的终止 1. 引起进程终止引起进程终止(Termination of Process)的事件的事件正常结束正常结束异常结束异常结束外界干预外界干预第二章 进 程 管 理 2.2.2 进程的终止进程的终止 1) 1) 正常结束正常结束 在任何计算机系统中，都应有一个用于表示

25、进在任何计算机系统中，都应有一个用于表示进程已经运行完成的指示。程已经运行完成的指示。例如，在批处理系统中，例如，在批处理系统中，通常在程序的最后安排一条通常在程序的最后安排一条Holt指令或终止的系统指令或终止的系统调用。当程序运行到调用。当程序运行到Holt指令时，将产生一个中断，指令时，将产生一个中断，去通知去通知OS本进程已经完成。本进程已经完成。 在分时系统中，用户在分时系统中，用户可利用可利用Logs off去表示进程运行完毕，去表示进程运行完毕， 此时同样可此时同样可产生一个中断，去通知产生一个中断，去通知OS进程已运行完毕。进程已运行完毕。 第二章 进 程 管 理 2) 2)

26、异常结束异常结束 在进程运行期间，由于出现某些错误和故障而迫使进程在进程运行期间，由于出现某些错误和故障而迫使进程终止。这类异常事件很多，常见的有：终止。这类异常事件很多，常见的有： 越界错误。越界错误。这是指程序所访问的存储区，已越出该进程的这是指程序所访问的存储区，已越出该进程的区域；区域； 保护错。保护错。进程试图去访问一个不允许访问的资源或文件，进程试图去访问一个不允许访问的资源或文件，或者以不适当的方式进行访问，例如，进程试图去写一个只或者以不适当的方式进行访问，例如，进程试图去写一个只读文件；读文件； 非法指令非法指令。程序试图去执行一条不存在的指令。出现该错。程序试图去执行一条不

27、存在的指令。出现该错误的原因，可能是程序错误地转移到数据区，把数据当成了误的原因，可能是程序错误地转移到数据区，把数据当成了指令；指令；第二章 进 程 管 理 2) 2) 异常结束异常结束 特权指令错。特权指令错。用户进程试图去执行一条只允许用户进程试图去执行一条只允许OS执行的指执行的指令；令； 运行超时。运行超时。进程的执行时间超过了指定的最大值；进程的执行时间超过了指定的最大值； 等待超时。等待超时。进程等待某事件的时间，进程等待某事件的时间， 超过了规定的最大值；超过了规定的最大值； 算术运算错。算术运算错。进程试图去执行一个被禁止的运算，例如，进程试图去执行一个被禁止的运算，例如，被

28、被0除；除； I/O故障。故障。这是指在这是指在I/O过程中发生了错误等。过程中发生了错误等。 第二章 进 程 管 理 3) 3) 外界干预外界干预 外界干预并非指在本进程运行中出现了异常事件，外界干预并非指在本进程运行中出现了异常事件，而是指进程应外界的请求而终止运行。这些干预有：而是指进程应外界的请求而终止运行。这些干预有： 操作员或操作系统干预。操作员或操作系统干预。 由于某种原因，例如，发由于某种原因，例如，发生了死锁，生了死锁， 由操作员或操作系统终止该进程；由操作员或操作系统终止该进程； 父进程请求。父进程请求。 由于父进程具有终止自己的任何子孙由于父进程具有终止自己的任何子孙进程

29、的权利，进程的权利， 因而当父进程提出请求时，系统将终止该因而当父进程提出请求时，系统将终止该进程；进程； 父进程终止。父进程终止。 当父进程终止时，当父进程终止时，OS也将他的所有子也将他的所有子孙进程终止。孙进程终止。 第二章 进 程 管 理 2. 进程的终止过程进程的终止过程 (1) 根据被终止进程的标识符，从队列根据被终止进程的标识符，从队列中读出该进程中读出该进程 (2) 终止该进程的执行，将处理机分配终止该进程的执行，将处理机分配给其他进程给其他进程 (3) 终止其所有子孙进程，以防他们成终止其所有子孙进程，以防他们成为不可控的进程。为不可控的进程。 (4) 回收其占的全部资源，或

30、者归还给回收其占的全部资源，或者归还给其父进程，其父进程， 或者归还给系统。或者归还给系统。 (5) 将被终止进程的将被终止进程的PCB从所在队列从所在队列(或或链表链表)中移出。中移出。 相当于某人相当于某人死亡后，就死亡后，就要去派出所要去派出所消户口消户口第二章 进 程 管 理 2.2.3 进程的阻塞与唤醒进程的阻塞与唤醒1. 引起进程阻塞和唤醒的事件引起进程阻塞和唤醒的事件 第二章 进 程 管 理 223 进程的阻塞与唤醒 2 2进程的阻塞过程进程的阻塞过程(block)(block) 进程的阻塞是主动行为，其过程为：进程的阻塞是主动行为，其过程为： 停止进程运行，让出停止进程运行，让

31、出CPUCPU 将将PCBPCB插入阻塞队列插入阻塞队列3 3进程的唤醒过程进程的唤醒过程(wakeup)(wakeup) 当阻塞进程所期待的事件发生时，则由其它当阻塞进程所期待的事件发生时，则由其它进程唤醒该进程。唤醒是被动行为，所谓进程唤醒该进程。唤醒是被动行为，所谓“阻塞阻塞自己、唤醒别人自己、唤醒别人”。其过程如下：。其过程如下： 从阻塞队列中移出该进程从阻塞队列中移出该进程 将将PCBPCB状态更改为就绪。状态更改为就绪。第二章 进 程 管 理 2 22 24 4 进程的挂起与激活进程的挂起与激活 1 1进程挂起过程进程挂起过程当有引起挂起事件发生当有引起挂起事件发生时，执行下列过程

32、：时，执行下列过程： 检查被挂起进程的检查被挂起进程的状态状态 更改其状态更改其状态 2 2进程激活过程进程激活过程当有引起激活事件发当有引起激活事件发生时，执行下列过程：生时，执行下列过程： 检查被激活进程检查被激活进程的状态的状态 更改其状态更改其状态第二章 进 程 管 理 进程挂起与激活 挂起：suspend（） 由活动变为静止 进程调入外存，但PCB仍在内存中，PCB常驻内存。 激活：active（） 由静止变为活动 进程调入内存第二章 进 程 管 理 注意注意 挂起和阻塞的区别挂起和阻塞的区别 激活和唤醒的区别激活和唤醒的区别第二章 进 程 管 理 练习练习 一个进程的基本状态可以从

33、其他两种基本状态转变过去，这个基本的状态一定是（） A、执行状态 B、阻塞状态 C、完成状态 D、就绪状态第二章 进 程 管 理 练习练习 通常用户进程被建立后（） A、边一直存在于系统中，直到被操作人员撤销 B、随着进程运行的正常或不正常结束而撤销 C、随着时间片轮转而撤销与监理 D、随着进程的阻塞或者唤醒而撤销与建立第二章 进 程 管 理 2.3 进程同步进程同步第二章 进 程 管 理 2.3 进进 程程 同同 步步 2.3.1 进程同步的基本概念进程同步的基本概念 1. 两种形式的制约关系两种形式的制约关系 间接相互制约关系竞争关系。 (2) 直接相互制约关系协作关系。 资源共享资源共享

34、进程合作进程合作第二章 进 程 管 理 进程同步举例第二章 进 程 管 理 进程同步的基本概念 多道系统中，进程与进程之间存在多道系统中，进程与进程之间存在着着资源共享和相互合作资源共享和相互合作关系，因而出现关系，因而出现了同步关系。进程同步的主要任务是使了同步关系。进程同步的主要任务是使并发执行的诸进程之间能有效的共享资并发执行的诸进程之间能有效的共享资源和相互合作，从而使程序执行具有可源和相互合作，从而使程序执行具有可再现性。再现性。第二章 进 程 管 理 2、临界资源引例：引例：宿舍固定电话宿舍固定电话火车上的公共厕所火车上的公共厕所打印机打印机火车票售票系统中的剩余票量火车票售票系统

35、中的剩余票量1.还有内存变量、指针、数组等等也是临界资还有内存变量、指针、数组等等也是临界资源。源。第二章 进 程 管 理 临界资源临界资源第二章 进 程 管 理 什么是临界资源？ 以前的课程也讲到了以前的课程也讲到了与时间有关与时间有关的错误，的错误，其实就是因为其实就是因为共享变量共享变量，这个共享的变，这个共享的变量就是量就是临界资源临界资源。 如果不对临界资源加以控制，那么就可如果不对临界资源加以控制，那么就可能出现错误，这就是本节要解决的问题。能出现错误，这就是本节要解决的问题。第二章 进 程 管 理 3. 临界区临界区(critical section) 可把一个访问临界资源的循环

36、进程描述如下：repeat until false; 在每个进程中，在每个进程中，访问访问临界资源的临界资源的那段代码那段代码，称为，称为临界区或临界段。临界区或临界段。第二章 进 程 管 理 进程应进程应互斥互斥的进入临界区的进入临界区 例如例如上图所示：上图所示：进程进程A A正在执行正在执行csa csa 段时，段时，进程进程B B就不能进入就不能进入csbcsb段执行。段执行。第二章 进 程 管 理 同步机制应遵循的准则：同步机制应遵循的准则：进入临界区的准则：进入临界区的准则： 空闲让进空闲让进 忙则等待：每次至多有一个忙则等待：每次至多有一个进程处于临界区进程处于临界区 有限等待：

37、当有进程欲进入有限等待：当有进程欲进入临界区时，应在有限的时间临界区时，应在有限的时间内使其进入；内使其进入； 让权等待：进程若不能进入让权等待：进程若不能进入临界区，则释放临界区，则释放CPUCPU，进入阻，进入阻塞状态，避免塞状态，避免“忙等忙等”。l空闲让进空闲让进l忙则等待忙则等待l有限等待有限等待l让权等待让权等待第二章 进 程 管 理 使用互斥区的原则 前提：任何进程无权停止其他进程的运前提：任何进程无权停止其他进程的运行行 进程之间相对运行速度无硬性规定进程之间相对运行速度无硬性规定 进程互斥的解决有两种做法：进程互斥的解决有两种做法： 具体方法：具体方法： 硬件：当一个进程进入

38、临界区，就屏蔽所有中断硬件：当一个进程进入临界区，就屏蔽所有中断（成本高）（成本高） 软件：用编程解决但往往忙等待。软件：用编程解决但往往忙等待。第二章 进 程 管 理 2.3.2信号量机制信号量机制前面介绍的方法虽能保证互斥，可正确解决临界前面介绍的方法虽能保证互斥，可正确解决临界区调度问题，但有明显缺点区调度问题，但有明显缺点将测试能否进入临界区的责任推给各个竞争的进将测试能否进入临界区的责任推给各个竞争的进程会削弱系统的可靠性，加重了用户编程负担。程会削弱系统的可靠性，加重了用户编程负担。第二章 进 程 管 理 信号量的概念 1965年荷兰的计算机科学家Dijkstra提出了新的同步工具

39、信号量和P、V操作。 他将交通管制交通管制中多种颜色的信号灯管理交通的方法引入操作系统，让两个或多个进程通过信号量(Semaphore) 展开交互。 进程在某一特殊点上停止执行直到得到一个对应的信号量，通过信号量这一设施，任何复杂的进程交互要求可得到满足，这种特殊的变量就是信号量。Dijkstra（荷兰）1、程序设计（、程序设计（goto语句）语句）2、操作系统、操作系统3、网络（最短路径算法）、网络（最短路径算法）第二章 进 程 管 理 信号量第二章 进 程 管 理 整型信号量整型信号量 信号量信号量S是整型变量。是整型变量。 变量值变量值 0 时，表示绿灯，进程执行。时，表示绿灯，进程执行

40、。 变量值变量值 0 时，表示红灯，进程停止执行。时，表示红灯，进程停止执行。 S除初始化外，仅能通过两个标准的原子操作wait(S)和signal(S)来访问。这两个操作一直被分别称为P、V操作。 wait(S): while S0 do no-opwait(S): while S0 do no-op S=S-1; S=S-1; signal(S): S signal(S): S：=S+1;=S+1; CPU忙等待第二章 进 程 管 理 整型信号量存在的问题整型信号量存在的问题 在整型信号量机制中，在在整型信号量机制中，在S0S0时，需要时，需要不断测试，处于不断测试，处于“忙等忙等”状态，

41、因而违状态，因而违背了背了“让权等待让权等待”的准则。的准则。第二章 进 程 管 理 什么是记录型变量？type semaphore=record value：integer； L：list of process； End第二章 进 程 管 理 对于记录型信号量机制，对于记录型信号量机制，wait和和signal原语就可描述为：原语就可描述为： procedure wait（S）var S：semaphore； begin S.value：=S.value-1； if S.value0：S表示可用资源的个数表示可用资源的个数S=0：S表示无资源，也无等待进程表示无资源，也无等待进程S0：S表示

42、可用资源的个数 S=0：S表示无资源，也无等待进程 S管理线程开销 进程切换开销线程切换开销 由于具有相同地址空间，线程同步通信容易，也不需要内核干预第二章 进 程 管 理 三、线程的实现机制 用户级线程 核心级线程 二者结合的线程第二章 进 程 管 理 三、线程的实现机制 用户级线程 由应用程序完成所有线程的管理 通过通过 线程库 一组管理线程的过程 特点：特点： 核心不知道线程的存在 线程切换不需要核心态特权 调度是应用特定的第二章 进 程 管 理 三、线程的实现机制 用户级线程 线程库 创建撤销线程 在线程之间传递消息和数据 调度线程执行 保护和恢复线程上下文第二章 进 程 管 理 三、

43、线程的实现机制 用户级线程的核心活动 核心不知道线程的存在，但管理线程所在的进程的活动 当线程调用系统调用时，整个进程阻塞 但对线程库来说，线程仍然是运行状态，即线程状态和进程状态是独立的。 线程库独立于系统内核，可以运行在不同的操作系统之上，使用户级线程可以得到不同操作系统的支持，而无须修改操作系统内核。第二章 进 程 管 理 三、线程的实现机制 用户级线程的优点 进程切换不调用核心 调度是应用程序特定的，故可以选择最好的算法 ULT可以运行在任何操作系统上（只需要线程库） 缺点 大多数系统调用是阻塞的，核心阻塞进程，故进程中所有线程都将被阻塞 核心只将处理机分配给进程，同一进程中的两个线程

44、不能同时运行于两个处理器上。 由于内核不知道ULT的存在，可能会强行中断某个正在执行的线程 很难实现不同进程的线程的并发第二章 进 程 管 理 三、线程的实现机制 核心级线程（KLT) 所有线程管理由核心完成 没有线程库，但对核心线程工具提供API 核心维护进程和线程的上下文 线程之间的切换需要核心完成 以线程为基础进行调度 例如：Windows NT OS/2第二章 进 程 管 理 三、线程的实现机制 核心级线程（KLT) 优点 对多处理器，核心可以同时调度同一进程的多个线程 阻塞是在线程一级完成 核心例程是多线程的 缺点 在同一进程内的线程切换需要调用内核，导致速度下降第二章 进 程 管

45、理 三、线程的实现机制 核心级线程和用户级线程二者分析：1、针对不同的OS2、开销和性能（线程的调度和切换速度）3、系统调用（阻塞）4、线程执行时间5、灵活性6、可扩充性7、抢占CPU8、共享进程的资源第二章 进 程 管 理 三、线程的实现机制 核心级线程和用户级线程二者分析：1、针对不同的OS2、开销和性能（线程的调度和切换速度）3、系统调用（阻塞）4、线程执行时间5、灵活性6、可扩充性7、抢占CPU8、共享进程的资源第二章 进 程 管 理 三、线程的实现机制 核心级线程和用户级线程结合方法线程创建在用户空间完成（开销小）大量线程调度和同步也在用户空间完成（开销小）程序员可以适当调整KLT的

46、数量可以取二者中最好的第二章 进 程 管 理 第二章 进 程 管 理 实例：Solaris 进程 用户地址空间 用户栈 进程控制块第二章 进 程 管 理 实例：Solaris 用户级线程（线程库） 可在应用进程中建多个ULT 每个ULT需要：栈、程序计数器 不受调度程序的调度，线程切换快 对OS不可见 提供应用程序并行性接口第二章 进 程 管 理 实例：Solaris 核心级线程 设置了大量的KLT 有一个小的数据结构和栈 完成内核的所有工作 其结构由核心维护第二章 进 程 管 理 实例：Solaris 核心级线程 设置了大量的KLT 有一个小的数据结构和栈 完成内核的所有工作 其结构由核心维

47、护第二章 进 程 管 理 实例：Solaris 轻型进程（LWP) 每个ULT利用LWP和内核通信 每个LWP支持一个或多个ULT，并映射到一个KLT 每个LWP对应用程序可见，内核看到的是多个LWP而不是ULT第二章 进 程 管 理 实例：Solaris 轻型进程（LWP) 每个ULT利用LWP和内核通信 每个LWP支持一个或多个ULT，并映射到一个KLT 每个LWP对应用程序可见，内核看到的是多个LWP而不是ULT第二章 进 程 管 理 实例：Solaris第二章 进 程 管 理 第二章 进 程 管 理 名词解释 1、程序、作业和进程 2、进程控制块 3、进程控制块PCB第二章 进 程 管 理 填空题 1、程序顺序执行时的特点是（） 2、进程是由程序、数据和（）组成的。 3、进程的（）和并发性是进程的两个最重要的属性 4、计算机处于用户态时，不能执行（）指令 5、进程是一个程序对某个数据集（）第二章 进 程 管 理 填空题 6、进程的基本状态有执行、（）和（） 7、进程创建时处于（）态，运行中的进程因时钟中断而处于（）态。 8、某程序运行时经常需要打印中间结果，计算时，该进程处于（）态，打印时处于（）态，打印结束时处于（）态。 9、操作系统中，可以并行工作的基本单位是（）。 10、操作系统通过（）对进程进行管理和控制。 11、进程在运行过程中