CH2-1进程管理

1、1第第2 2章章 进程管理进程管理v 程序并发执行时，产生了一些新特征，所以一般的程序是不能并程序并发执行时，产生了一些新特征，所以一般的程序是不能并发执行的。为了使程序在多道程序环境下能并发执行，并能对并发发执行的。为了使程序在多道程序环境下能并发执行，并能对并发执行的程序加以控制和描述，引入执行的程序加以控制和描述，引入“进程进程”的概念。的概念。v 现在，现在，“进程进程”已经成为操作系统乃至并发程序设计中最核心的已经成为操作系统乃至并发程序设计中最核心的概念，它是对正在运行的程序的抽象，操作系统的其他所有内容都概念，它是对正在运行的程序的抽象，操作系统的其他所有内容都是围绕着进程展开的

2、。掌握进程的概念对于理解操作系统的实质以是围绕着进程展开的。掌握进程的概念对于理解操作系统的实质以及分析、设计操作系统都有非常重要的意义及分析、设计操作系统都有非常重要的意义 22.1 2.1 进程的基本概念进程的基本概念 2.1.1 2.1.1 程序的顺序执行及其特征程序的顺序执行及其特征 1. 1. 程序的顺序执行程序的顺序执行 仅当前一操作(程序段)执行完后，才能执行后继操作。例如在进行计算时：输入程序和数据进行计算打印计算结果。 S1: a=x+y; S2: b=a-5; S3: c=b+1;(a) 程序的顺序执行(b) 三条语句的顺序执行I1C1P1I2C2P2S1S2S32. 2.

3、 程序顺序执行时的特征：程序顺序执行时的特征：顺序性、封闭性、可再现性。32.1.2 2.1.2 前趋图前趋图 前趋图(Precedence Graph)是一个有向无循环图，用于描述进程之间执行的前后关系。图中的每个结点可用于描述一个程序段或进程，乃至一条语句；结点间的有向边则用于表示两个结点之间存在的前趋关系 “”。 =(Pi, Pj)|Pi must complete before Pj may start, 称Pi是Pj的直接前趋，而称Pj是Pi的直接后继。在前趋图中，把没有前趋的结点称为初始结点(Initial Node)，把没有后继的结点称为终止结点(Final Node)。4 每个

4、结点还具有一个重量(Weight)，用于表示该结点所含有的程序量或结点的执行时间。 IiCiPi和S1S2S3 P1P3P8P9P4P2P5P6P7S1S2S3(a) 具有九个结点的前趋图(b) 具有循环的前趋图52.1.3 2.1.3 程序的并发执行及其特征程序的并发执行及其特征 1. 1. 程序的并发执行程序的并发执行 图 2-3 并发执行时的前趋图 P1P2P3P4I1I2I3I4C1C2C3C46在该例中存在下述前趋关系： IiCi，IiIi+1, CiPi, CiCi+1，PiPi+1而Ii+1和Ci及Pi-1是重迭的，亦即在Pi-1和Ci以及Ii+1之间，可以并发执行。 对于具有下

5、述四条语句的程序段： S1: a=x+2 S2: b=y+4 S3: c=a+b S4: d=c+b S1S2S3S42. 2. 程序并发执行时的特征程序并发执行时的特征 1) 间断性 2) 失去封闭性 3) 不可再现性72.1.4 2.1.4 进程的特征与状态进程的特征与状态 “进程进程”这一术语，在这一术语，在6060年代初期，首先在美国年代初期，首先在美国MITMIT的的MULTICSMULTICS系统系统和和IBMIBM公司的公司的CTSS/360CTSS/360系统中引入。其中能反映进程实质的定义有：系统中引入。其中能反映进程实质的定义有： （1 1）进程是程序的一次执行。）进程是程

6、序的一次执行。 （2 2）进程是可以和其他计算并发执行的计算。）进程是可以和其他计算并发执行的计算。 （3 3）进程是一个程序及其数据在处理器上顺序执行时发生的活动。）进程是一个程序及其数据在处理器上顺序执行时发生的活动。 （4 4）进程是程序在一个数据集合上的运行过程，是系统进行资源）进程是程序在一个数据集合上的运行过程，是系统进行资源分配和调度的一个独立单位。分配和调度的一个独立单位。 （5 5）进程是进程实体的一次活动。）进程是进程实体的一次活动。 一、进程的定义一、进程的定义 8 我国我国19781978年在庐山召开的全国年在庐山召开的全国OSOS研讨会上研讨会上将将“进程进程”定义为

7、：定义为：进程是一个具有一定独立功能的程序关进程是一个具有一定独立功能的程序关于某个数据集合的一次运行活动。于某个数据集合的一次运行活动。 一个程序为实现不同的任务可以同时一个程序为实现不同的任务可以同时有多次运行活动，每个运行活动分别有多次运行活动，每个运行活动分别作为不同的进程作为不同的进程9二、进程的特性及与程序的区别二、进程的特性及与程序的区别 1. 1. 进程的五个特性进程的五个特性 (1)(1)动态性动态性：生命周期。即它由系统“创建”而诞生，因被“调度”而执行，因得不到资源而暂停，最后因被“撤消”而消亡。 (2)(2)并发性并发性：是指不同进程的动作在时间上可以重叠，即系统内的多

8、个进程是可以并发执行的。 (3)(3)独立性独立性：指进程实体是一个能独立运行的基本单位，同时也是系统中独立获得资源和独立调动的基本单位。 (4)(4)异步性异步性：指进程按各自独立的、不可预知的速度向前推进 (5)(5)结构特性结构特性：从结构上看，每个进程都由程序段、数据段和一个PCB三部分组成。 2. 2. 进程与程序的区别进程与程序的区别 (1)(1)从定义上看，进程是程序处理数据的过程，而程序是从定义上看，进程是程序处理数据的过程，而程序是一组指令的有序集合；一组指令的有序集合； (2)(2)进程具有动态性、并发性、独立性和异步性等，而程进程具有动态性、并发性、独立性和异步性等，而程

9、序不具有这些特性；序不具有这些特性； (3)(3)从进程结构特性上看，它包含程序（以及数据和从进程结构特性上看，它包含程序（以及数据和PCBPCB）；）； (4)(4)进程和程序并非一一对应。进程和程序并非一一对应。 11 在操作系统中引入在操作系统中引入“进程进程”概念的主要目的是概念的主要目的是（ ）。）。 A. A. 改善用户编程环境改善用户编程环境 B. B. 描述程序动态执行过程的性质描述程序动态执行过程的性质 C. C. 使程序与计算过程一一对应使程序与计算过程一一对应 D. D. 提高程序的运行速度提高程序的运行速度12三、进程的基本状态及其转换三、进程的基本状态及其转换 1 1

10、进程的三种基本状态进程的三种基本状态 （1 1）就绪（）就绪（ReadyReady）状态：）状态：当进程已分配到除当进程已分配到除CPUCPU以外的所有必要以外的所有必要的资源，只要能再获得处理器，便可立即执行的资源，只要能再获得处理器，便可立即执行 （2 2）执行（）执行（RunningRunning）状态）状态：当进程已获得处理器，其程序正在处当进程已获得处理器，其程序正在处理器上执行，理器上执行， （3 3）阻塞（）阻塞（BlockedBlocked）状态：）状态：正在执行的进程，由于等待某事件发正在执行的进程，由于等待某事件发生而无法执行时，便放弃处理器而处于暂停状态。生而无法执行时，

11、便放弃处理器而处于暂停状态。 在不少系统中，又增加了两种基本状态：在不少系统中，又增加了两种基本状态： 新建（新建（NewNew）状态）状态 终止（终止（TerminatedTerminated）状态）状态 13引入新建态和终止状态的原因：引入新建态和终止状态的原因： 由于由于OSOS在建立一个新进程时，通常分为在建立一个新进程时，通常分为2 2步：第一步是为步：第一步是为新登录的用户程序（分时系统）创建进程，并为他分配新登录的用户程序（分时系统）创建进程，并为他分配资源，此时进程即处于资源，此时进程即处于新建态新建态。第二步是把新创建的进。第二步是把新创建的进程送入就绪队列，一旦进程进入就绪

12、队列，它便由新建程送入就绪队列，一旦进程进入就绪队列，它便由新建态变为就绪状态。态变为就绪状态。 一个结束了的进程，其退出系统的过程也分为两步：第一个结束了的进程，其退出系统的过程也分为两步：第一步是将该进程从就绪队列中移出，使之成为一个不可一步是将该进程从就绪队列中移出，使之成为一个不可能再运行的进程，相应的进程处于能再运行的进程，相应的进程处于终止状态终止状态。此时系统。此时系统并不立即撤销它，而是将它暂时留在系统中，以便其它并不立即撤销它，而是将它暂时留在系统中，以便其它进程去收集该进程的有关信息。进程去收集该进程的有关信息。 14创建创建就绪就绪执行执行终止终止阻塞阻塞接纳接纳完成完成

13、I/OI/O完成完成或等待的或等待的事件发生事件发生I/OI/O请求或请求或等待某事件等待某事件2 2进程三种基本状态间的转换进程三种基本状态间的转换进程调度进程调度时间片完时间片完153.3.挂起状态挂起状态 在有的系统中，为了暂时缓和内存的紧张状态，或为了调节系统负荷，又引入了挂起功能。即暂时挂起一部分进程，把它们从内存临时换出到辅存，使它们暂时和系统脱离联系，起到平滑系统操作负荷的目的。 这样，就需要把进程的就绪状态进一步细分为活动就绪活动就绪状态状态（未被挂起的就绪进程）和静止就绪状态静止就绪状态（被挂起的就绪进程）两种。把进程的阻塞状态也细分为活动活动阻塞状态阻塞状态（未被挂起的阻塞

14、进程）和静止阻塞状态静止阻塞状态（被挂起的阻塞进程）。 16活动就绪静止就绪执行挂起激活释放挂起活动阻塞静止阻塞挂起激活释放请求I/O具有挂起状态的进程状态转换图具有挂起状态的进程状态转换图172.1.5 2.1.5 进程控制块进程控制块PCBPCB PCB PCB ( Process Control Block )( Process Control Block )是系统为了描述和控制进是系统为了描述和控制进程的运行而为进程定义的一种数据结构。程的运行而为进程定义的一种数据结构。 它是进程实体的一部分，它是进程实体的一部分，是进程存在的唯一标志是进程存在的唯一标志，也是，也是操作系统中最重要的

15、结构体类型的数据结构。操作系统中最重要的结构体类型的数据结构。 PCBPCB中存放着操作系统所需的用于描述进程的当前情况中存放着操作系统所需的用于描述进程的当前情况以及控制进程运行的全部信息。以及控制进程运行的全部信息。181 1PCBPCB的作用的作用（1 1）标识进程的存在：标识进程的存在：系统创建进程时，就为之创建一个系统创建进程时，就为之创建一个PCBPCB；进；进程结束时，系统又回收其程结束时，系统又回收其PCBPCB，进程便随之消亡，进程便随之消亡。 （2 2）为系统提供可并发执行的独立单位为系统提供可并发执行的独立单位：PCBPCB使一个在多道程使一个在多道程序环境下不能独立运行

16、的程序成为一个能独立运行的基本单位，一个序环境下不能独立运行的程序成为一个能独立运行的基本单位，一个能与其他进程并发执行的进程。没有为之建立能与其他进程并发执行的进程。没有为之建立PCBPCB的程序是不能并发的程序是不能并发执行的。执行的。 （3 3）为系统控制和管理进程提供所需的一切信息为系统控制和管理进程提供所需的一切信息。 192 2PCBPCB中的信息中的信息 （1 1）进程标识符）进程标识符( (内部：数字，系统；外部：字符，内部：数字，系统；外部：字符， 用户用户) )： （2 2）处理器状态）处理器状态：通用寄存器、指令计数器、通用寄存器、指令计数器、PSWPSW，用户栈指针；用

17、户栈指针； （3 3）进程调度信息：）进程调度信息：进程的现行状态、进程优先级、进程的现行状态、进程优先级、 与进程有关的其他信息、事件即阻塞原因；与进程有关的其他信息、事件即阻塞原因； （4 4）进程控制信息：）进程控制信息：进程相应的程序和数据地址：进程相应的程序和数据地址： 进程同步与通信机制：进程资源清单：进程所进程同步与通信机制：进程资源清单：进程所在在PCBPCB的链接字的链接字 。 203.PCB3.PCB的组织方式的组织方式 PCBPCB的组织方式指的是把具有相同状态的若干的组织方式指的是把具有相同状态的若干进程按照某种原则适当组织在一起的一种形式。进程按照某种原则适当组织在一

18、起的一种形式。 因为因为PCBPCB是系统中最重要也是被频繁访问的数据结构，是系统中最重要也是被频繁访问的数据结构，系统中的许多模块，如调度程序、资源分配程序、中断系统中的许多模块，如调度程序、资源分配程序、中断处理程序以及监督和分析程序等，特别是运行频率很高处理程序以及监督和分析程序等，特别是运行频率很高的进程分派程序，都要对它进行读或写操作，所以的进程分派程序，都要对它进行读或写操作，所以PCBPCB常常驻内存的系统区中，系统将所有的驻内存的系统区中，系统将所有的PCBPCB以数组形式连续存以数组形式连续存放组织成若干个链表（或队列），存放在操作系统中专放组织成若干个链表（或队列），存放在

19、操作系统中专门开辟的门开辟的PCBPCB区内。区内。 21空闲空闲PCB队列头指针队列头指针阻塞进程队列头指针阻塞进程队列头指针就绪进程队列头指针就绪进程队列头指针执行进程指针执行进程指针PCB1PCB2PCB3PCB4PCB5PCB6PCB7PCB8PCB9430879015.1 1）链接方式）链接方式 系统按照进程的状态将进程的系统按照进程的状态将进程的PCBPCB组组成队列，将同一状态的成队列，将同一状态的PCBPCB用链接字用链接字链接成一个队列，从而形成就绪队链接成一个队列，从而形成就绪队列、阻塞队列、运行队列等。列、阻塞队列、运行队列等。 222) 2) 索引方式：索引方式：系统按

20、照进程的状态分别建立就绪索引表、阻塞索系统按照进程的状态分别建立就绪索引表、阻塞索 引表等。引表等。 执行指针就绪索引表PCB1PCB2PCB3PCB4PCB5PCB6PCB7阻塞索引表就绪表指针阻塞表指针3) 3) 线性表方式线性表方式 不论进程的状态如何，将所有的不论进程的状态如何，将所有的PCBPCB连续地存放在内存的系统区。连续地存放在内存的系统区。这种方式适用于系统中进程数目不多的情况。这种方式适用于系统中进程数目不多的情况。232.2 2.2 进程控制进程控制v 进程控制是进程管理中最基本的功能；进程控制是进程管理中最基本的功能；v 进程控制一般是由进程控制一般是由OSOS的内核来

21、实现的。的内核来实现的。v 原语操作：原语操作： 本身是由若干条指令构成、用于完成特定功能的一个过程。本身是由若干条指令构成、用于完成特定功能的一个过程。为了保证操作的正确性，原语在执行期间是不允许分割的，也就是为了保证操作的正确性，原语在执行期间是不允许分割的，也就是说，原语的执行不能被中断。说，原语的执行不能被中断。 ：一个操作中的所有动作。与一般过程的区别：要么全：一个操作中的所有动作。与一般过程的区别：要么全作，要么全不作。即：原子操作是不可分割的，在管态下执行，常作，要么全不作。即：原子操作是不可分割的，在管态下执行，常驻内存。驻内存。 原语的作用是为了实现进程的通信和控制，习题对进

22、原语的作用是为了实现进程的通信和控制，习题对进程的控制如不适用原语，就会造成其这台的不确定性，程的控制如不适用原语，就会造成其这台的不确定性，从而达不到进程控制的目的。从而达不到进程控制的目的。241.进程创建原语Creat()引起创建进程的事件：引起创建进程的事件： 用户登录用户登录 作业调度作业调度 提供服务提供服务 应用请求应用请求（进程自身创建）（进程自身创建）进程创建的主要步骤：进程创建的主要步骤： 申请空白申请空白PCBPCB 为新进程分配资源为新进程分配资源 初始化初始化PCBPCB的内容的内容 将新进程插入就绪队列将新进程插入就绪队列系统内核系统内核创建创建252.进程撤销原语

23、Terminate()引起撤销进程的事件：引起撤销进程的事件： 正常结束正常结束 异常结束异常结束 外界干扰外界干扰进程撤销的过程：进程撤销的过程： 检索进程当前的状态，结检索进程当前的状态，结束并置调度标志，撤销其束并置调度标志，撤销其所有的子进程，归还资源，所有的子进程，归还资源，移出队列。移出队列。v应由父进程调用进程撤销原语来撤销，以便及时的释放其应由父进程调用进程撤销原语来撤销，以便及时的释放其所占的资源。所占的资源。263.进程阻塞原语Block()引起进程阻塞的事件：引起进程阻塞的事件： 请求系统服务请求系统服务 启动某种操作启动某种操作 新数据尚未到达新数据尚未到达 无新工作可

24、作无新工作可作进程堵塞的过程：进程堵塞的过程： 发现堵塞事件，调用阻塞发现堵塞事件，调用阻塞原语把自己阻塞，停止进原语把自己阻塞，停止进程的执行，修改程的执行，修改PCBPCB的的，将其插入到自己，将其插入到自己的堵塞队列。最后转调度的堵塞队列。最后转调度程序，将处理器分配给另程序，将处理器分配给另一个就绪进程一个就绪进程。v进程的阻塞是进程自身的一进程的阻塞是进程自身的一种主动行为种主动行为274.进程唤醒原语Wakeup()引起进程唤醒的事件：引起进程唤醒的事件： 当被阻塞进程所期待的事当被阻塞进程所期待的事件出现时，或者所期待的件出现时，或者所期待的数据已经到达。由该有关数据已经到达。由

25、该有关进程调用进程唤醒原语，进程调用进程唤醒原语，将等待该资源而阻塞的一将等待该资源而阻塞的一个进程唤醒成个进程唤醒成进程唤醒的过程：进程唤醒的过程： 把被阻塞进程从等待该把被阻塞进程从等待该事件的阻塞队列中移出，事件的阻塞队列中移出，将其将其PCBPCB的现行状态，由的现行状态，由阻塞改为就绪，再将该阻塞改为就绪，再将该进程插入到进程插入到PCBPCB就绪队列就绪队列中。中。285.挂起原语Suspend( ): 当出现了引起挂起的事件时，如为了暂时缓和内存当出现了引起挂起的事件时，如为了暂时缓和内存的紧张状态，用户进程请求将自己挂起或者当父进程请的紧张状态，用户进程请求将自己挂起或者当父进

26、程请求将自己的某个子进程挂起时，系统将利用挂起原语求将自己的某个子进程挂起时，系统将利用挂起原语suspend( )suspend( )将制定的进程或处于阻塞状态的进程挂起。将制定的进程或处于阻塞状态的进程挂起。 6.激活原语Active( ): 将进程从外存调入内存，检查该进程的状态，改为将进程从外存调入内存，检查该进程的状态，改为相应的活动状态相应的活动状态( (只能由其它进程调用只能由其它进程调用) )29 多道程序的并发执行改善了资源利用率、提高了系统多道程序的并发执行改善了资源利用率、提高了系统吞吐量，但由于进程的异步性，给系统带来了新的问题，吞吐量，但由于进程的异步性，给系统带来了

27、新的问题，如资源共享、进程合作等问题，使的进程间的制约成为如资源共享、进程合作等问题，使的进程间的制约成为可能。可能。 进程之间的关系包括：竞争关系进程之间的关系包括：竞争关系( (互斥互斥) )、协作关系、协作关系( (同步同步) )；进程间数据传送方法；进程间数据传送方法( (通信通信) )；资源资源( (临界区临界区) )竞竞争的两个控制问题：死锁、饥饿等。争的两个控制问题：死锁、饥饿等。 重点和难点：重点和难点：信号量与信号量与P P、V V操作；死锁操作；死锁。30多道程序设计带来的问题多道程序设计带来的问题 ： 并发执行的多个进程可能产生互斥或同步的相互制并发执行的多个进程可能产生

28、互斥或同步的相互制约关系，不采取措施，可能导致结果的不可再现性。影约关系，不采取措施，可能导致结果的不可再现性。影响系统效率，而且还可以导致系统崩溃。响系统效率，而且还可以导致系统崩溃。 为此为此，现代操作系统都在内核中设有进程的互斥，现代操作系统都在内核中设有进程的互斥同步机制，以控制并发执行的诸进程能有效的共享资源同步机制，以控制并发执行的诸进程能有效的共享资源和相互合作，同时使并发程序的执行仍具有可再现性。和相互合作，同时使并发程序的执行仍具有可再现性。2.3 2.3 进程同步进程同步312.3.1 2.3.1 进程同步的基本概念进程同步的基本概念 进程的同步进程的同步synchroni

29、smsynchronism你等我，我也等你你等我，我也等你 多道程序系统中，系统中可能有许多进程，在这些进程多道程序系统中，系统中可能有许多进程，在这些进程之间可能存在以下两种关系：之间可能存在以下两种关系： 1 1. .资源共享关系资源共享关系 2.2.相互合作关系相互合作关系 这实际上都是一种合作进程在独自并发执行过程中的某这实际上都是一种合作进程在独自并发执行过程中的某些确定的时序点些确定的时序点( (协调点协调点) )上上“你等我，我也等你你等我，我也等你”的同步约的同步约束束321.1.资源共享关系资源共享关系 多个进程之间彼此无关，他们并不知道其它进程的存多个进程之间彼此无关，他们

30、并不知道其它进程的存在。例如在分时系统中，系统分别为每个用户（终端）在。例如在分时系统中，系统分别为每个用户（终端）建立一个进程。但这些进程既然同处于一个系统中，也建立一个进程。但这些进程既然同处于一个系统中，也就必然存在着资源共享的关系，如共享就必然存在着资源共享的关系，如共享CPUCPU和和I/OI/O设备等。设备等。此时，进程的主要任务，是保证各个进程能互斥地访问此时，进程的主要任务，是保证各个进程能互斥地访问临界资源。所以，系统中的资源应该不允许用户进程直临界资源。所以，系统中的资源应该不允许用户进程直接使用，而应该由系统同一分配。例如：在仅有一台打接使用，而应该由系统同一分配。例如：

31、在仅有一台打印机的系统中，两个进程提出打印请求。印机的系统中，两个进程提出打印请求。2.2.相互合作关系相互合作关系 例如输入进程、计算进程、打印进程三者之间就是相例如输入进程、计算进程、打印进程三者之间就是相互合作的关系。互合作的关系。 33一、同步的定义一、同步的定义 进程同步：进程同步：指的是两个或多个进程为了合作完成同一个指的是两个或多个进程为了合作完成同一个任务，在执行速度或某些个确定的时序点上必须相互协任务，在执行速度或某些个确定的时序点上必须相互协调，即一个进程的执行依赖于另一个进程调，即一个进程的执行依赖于另一个进程其合作伙其合作伙伴的消息，当一个进程到达了某一确定点而没有得到

32、合伴的消息，当一个进程到达了某一确定点而没有得到合作伙伴发来的作伙伴发来的“已完成某些操作已完成某些操作”的消息时必须等待，的消息时必须等待，直到该消息到达被唤醒后，才能继续向前推进。直到该消息到达被唤醒后，才能继续向前推进。v进程同步是多道程序系统中进程之间存在的一种主要源于进程同步是多道程序系统中进程之间存在的一种主要源于进程间合作的制约关系，也称进程间合作的制约关系，也称直接制约关系直接制约关系。 34 直接制约关系：进程间的相互联系是有意进程间的相互联系是有意识的安排的，直接作用只发生在相交进程间。识的安排的，直接作用只发生在相交进程间。 间接制约关系：进程间要通过某种中介发进程间要通

33、过某种中介发生联系，是无意识安排的，可发生在相交进程生联系，是无意识安排的，可发生在相交进程之间，也可发生在无关进程之间之间，也可发生在无关进程之间 。35二、互斥的定义二、互斥的定义 所谓所谓，指的是对某个系统资源，一个进，指的是对某个系统资源，一个进程正在使用它，另外一个想用它的进程就必须等程正在使用它，另外一个想用它的进程就必须等待，而不能同时使用待，而不能同时使用 。 进程互斥是多道程序系统中进程间存在的一种源进程互斥是多道程序系统中进程间存在的一种源于资源共享的制约关系，也称于资源共享的制约关系，也称间接制约关系间接制约关系，主，主要是由被共享资源的使用性质所决定的。要是由被共享资源

34、的使用性质所决定的。36 这种限定进程只能互斥地访问它的资源叫这种限定进程只能互斥地访问它的资源叫临界资源（临界资源（指一次仅允许一个进程使用的资源 ）。 临界资源限定了使用者只能互斥地使用它。临界资源限定了使用者只能互斥地使用它。 操作系统也不能中途从抢先者手中把临界资源抢来给其他操作系统也不能中途从抢先者手中把临界资源抢来给其他进程用。因此，临界资源也是不可剥夺性资源。进程用。因此，临界资源也是不可剥夺性资源。例：例：计算机计算机系统中可剥夺性使用的资源主要有系统中可剥夺性使用的资源主要有CPUCPU、内存内存和和磁盘磁盘等。等。三、临界资源和临界区三、临界资源和临界区37程 序 段1程

35、序 段2程 序 段n共 享 变量38：进程中访问临界资源的那段程序代码称为临界：进程中访问临界资源的那段程序代码称为临界区或临界段。区或临界段。使用同一临界资源的不同进程中的临界区称为使用同一临界资源的不同进程中的临界区称为区区或或。为实现对临界资源的互斥访问，应保证诸进程为实现对临界资源的互斥访问，应保证诸进程地进地进入各自的临界区。入各自的临界区。 但无论采用何种方法，都应但无论采用何种方法，都应遵循临界区的使用原则遵循临界区的使用原则，即，即“空则让进，忙则等待，等则有限，等则让权空则让进，忙则等待，等则有限，等则让权”。 39进程同步和互斥间的关系：进程同步和互斥间的关系：相似处：相似

36、处：进程的互斥实际上是进程同步的一种特殊进程的互斥实际上是进程同步的一种特殊 情况；情况； 进程的互斥和同步统称为进程同步。进程的互斥和同步统称为进程同步。差别：差别：是进程间共享资源的使用权是进程间共享资源的使用权 ，这种竞争没，这种竞争没有固定的必然联系，哪个进程竞争到使用权就归那个进程有固定的必然联系，哪个进程竞争到使用权就归那个进程使用，直到不需要使用时再归还；而使用，直到不需要使用时再归还；而则涉及共享则涉及共享资源的并发进程间有一种必然的联系，当进程必须同步时，资源的并发进程间有一种必然的联系，当进程必须同步时，即使无进程在使用共享资源时，那么尚未得到同步消息的即使无进程在使用共享

37、资源时，那么尚未得到同步消息的进程也不能去使用这个资源。进程也不能去使用这个资源。402.3.2 2.3.2 信号量机制信号量机制 荷兰著名科学家，后来的计算机图灵奖获得荷兰著名科学家，后来的计算机图灵奖获得者，者，E.W.DijkstraE.W.Dijkstra于于19651965年提出了用作进程同年提出了用作进程同步工具的步工具的信号量信号量（semaphoresemaphore）机制机制，这是一种，这是一种卓有成效的进程互斥同步工具，已被广泛应用卓有成效的进程互斥同步工具，已被广泛应用于现代计算机系统中。于现代计算机系统中。 两个信号量操作原语，即两个信号量操作原语，即P P，V V操作

38、。操作。 41信号量机制的基本原理是：信号量机制的基本原理是： v两个或多个进程可以利用彼此间收发的简单的信号来实两个或多个进程可以利用彼此间收发的简单的信号来实现现“正确的正确的”并发执行，一个进程在收到一个指定信号并发执行，一个进程在收到一个指定信号前，会被迫在一个确定的或者需要的地方停下来，从而前，会被迫在一个确定的或者需要的地方停下来，从而保持同步或互斥。保持同步或互斥。42一、信号量的概念一、信号量的概念 信号量信号量，也叫，也叫信号灯信号灯，一般是由两个成员组成的数据结，一般是由两个成员组成的数据结构，是一个确定的二元组构，是一个确定的二元组（S S，Q Q）S S是个具有非负初值

39、的是个具有非负初值的整型变量整型变量，表示该信号量的值，表示该信号量的值，且且S S的值只能由定义在信号量上的的值只能由定义在信号量上的P P操作原语和操作原语和V V操作原操作原语来改变；语来改变；Q Q是个初始状态为是个初始状态为空的空的等待队列指针等待队列指针 （一个是指向（一个是指向PCBPCB的指针，当多个进程都等待同一信号量时，它们就排成的指针，当多个进程都等待同一信号量时，它们就排成一个队列，由信号量的指针项指出该队列的头）。一个队列，由信号量的指针项指出该队列的头）。43另一定义：另一定义：v信号量类型是个复合类型，其一个分量是个整型分量信号量类型是个复合类型，其一个分量是个整

40、型分量S S，另一个分量是个等待队列指针另一个分量是个等待队列指针Q Q （一个是指向（一个是指向PCBPCB的指的指针，当多个进程都等待同一信号量时，它们就排成一个针，当多个进程都等待同一信号量时，它们就排成一个队列，由信号量的指针项指出该队列的头。）队列，由信号量的指针项指出该队列的头。） 44* * *信号量整型分量信号量整型分量S S的值的物理含义：的值的物理含义： v当当S0S0时，表示某类可用资源的数目，或者说表示可以时，表示某类可用资源的数目，或者说表示可以执行执行P P操作而不会被阻塞的进程的数目；操作而不会被阻塞的进程的数目；v当当S S0 0时，其绝对值表示信号量时，其绝对

41、值表示信号量S S的阻塞队列中的进程的阻塞队列中的进程数，即系统中因请求该类资源而被阻塞的进程的数目，数，即系统中因请求该类资源而被阻塞的进程的数目，亦即被信号灯挡住的进程数目，这些进程需要别的进程亦即被信号灯挡住的进程数目，这些进程需要别的进程发出相应的信号灯来唤醒。发出相应的信号灯来唤醒。 v另外，另外，S S的值只能由的值只能由P P、V V操作来改变。操作来改变。 45二、二、P P、V V操作原语操作原语 通常通常P P操作意味着请求一个资源，在一定条件下，操作意味着请求一个资源，在一定条件下， P P操作代表挂起进程操作；操作代表挂起进程操作；通常通常V V操作意味着释放一个资源，

42、在一定条件下，操作意味着释放一个资源，在一定条件下， V V操作代表唤醒被挂起进程的操作；操作代表唤醒被挂起进程的操作； 原语是操作系统内核中执行时不可中断的过程，即原语是操作系统内核中执行时不可中断的过程，即原子操作。信号量机制中，除赋值外，信号量仅能由原子操作。信号量机制中，除赋值外，信号量仅能由原语对其进行操作。原语对其进行操作。 信号量通常可以简单反映出相应资源的使用情况，它信号量通常可以简单反映出相应资源的使用情况，它与与P P，V V操作原语一起使用可实现进程的同步和互斥。操作原语一起使用可实现进程的同步和互斥。 461.1.定义在信号量定义在信号量S S上的上的P(S)P(S)原

43、语操作的算法描述为：原语操作的算法描述为： 1 1）S S减减1 1； 2 2）若）若S0S0，则调用，则调用P P（S S）的进）的进程返回，继续执行程返回，继续执行; ; 3 3）若）若S0SSS0 Block(Q) 返回YN472.2.定义在信号量定义在信号量S S上的上的V(S)V(S)原语操作的算法描述为：原语操作的算法描述为： （1 1）S S加加1 1；（2 2）若）若S0 S0 ，则调用，则调用V V（S S）的进程继续执行，返回；的进程继续执行，返回；（3 3）若）若S0 SS S0 Wakeup(Q) 返回YN48注意注意P P（S S）操作和）操作和V V（S S）操作的

44、物理含义：）操作的物理含义： P P（S S）操作表示）操作表示“等信号等信号”，即测试一个要等的信号是，即测试一个要等的信号是否到达；否到达；V V（S S）操作表示）操作表示“发信号发信号”。这个信号在实现同步时就。这个信号在实现同步时就是是“合作者的伙伴进程已完成前趋任务合作者的伙伴进程已完成前趋任务”，在实现互斥，在实现互斥时就是时就是“临界资源可用临界资源可用”。另外，在互斥问题中，每执行一次另外，在互斥问题中，每执行一次P P（S S）操作的含义，）操作的含义，也可理解为进程请求一个单位的也可理解为进程请求一个单位的S S类资源；每执行一次类资源；每执行一次V V（S S）操作的含

45、义，也可理解为进程释放一个单位的）操作的含义，也可理解为进程释放一个单位的S S类类资源。资源。 49 P,V操作是两个过程，由他们两个来控制一个信号S，假设S是红灯的个数。 每个进程进入临界区前都要先执行P操作。退出临界区时执行V操作。用下面的比喻很容易理解: 临界区门前有棵树（S） 用来挂红灯 进程想进CPU的门 先得上树取盏灯（调用一次P操作） 取下一个去敲门(S=S-1) 如果树上没灯取(S0) 树说欠你一盏灯(S为负时) 没辙只好外边排队等( Wait (S) 得灯进程续运行 运行完了要出门（调用一次V操作） 马上还回一盏灯(S=S+1) 若有进程在催债(S0) 放个进去事完成( R

46、elease (S)50 P、V操作也都是配对出现，但对操作也都是配对出现，但对同一个信号量同一个信号量的的P、V操作却不是操作却不是同时出现在每一个进程的程序里，而是分别出现在同时出现在每一个进程的程序里，而是分别出现在一个进程和它的合一个进程和它的合作伙伴的代码中作伙伴的代码中。 而且而且P、V操作的出现位置都在各个合作进程中确定的时序点，即操作的出现位置都在各个合作进程中确定的时序点，即一个生产者进程在完成了前趋的生产任务后，应立即给合作伙伴一个生产者进程在完成了前趋的生产任务后，应立即给合作伙伴消费者进程发送一条消费者进程发送一条“已完成前趋生产任务已完成前趋生产任务”的消息，这要执行

47、的消息，这要执行V操作；操作；而后继的消费者进程在消费前，应该执行对同一个信号量的而后继的消费者进程在消费前，应该执行对同一个信号量的P操作，以操作，以测试其合作伙伴测试其合作伙伴生产者进程生产者进程“已完成前趋生产任务已完成前趋生产任务”的消息是否的消息是否到来，如果到来就开始消费，否则就阻塞自己。到来，如果到来就开始消费，否则就阻塞自己。 三、用三、用P P、V V操作原语实现进程的同步操作原语实现进程的同步51解答这类进程同步问题的主要步骤也是三大步：解答这类进程同步问题的主要步骤也是三大步： (1)(1)分析清楚题目涉及的进程间的制约关系；分析清楚题目涉及的进程间的制约关系； (2)(

48、2)设置信号量（包括信号量的个数和初值及其物理含设置信号量（包括信号量的个数和初值及其物理含义），合作进程间需要收发几条消息相应就设置几个信义），合作进程间需要收发几条消息相应就设置几个信号量，同步信号量的初值一般为号量，同步信号量的初值一般为0 0； (3)(3)给出进程相应程序的算法描述或流程控制，并把给出进程相应程序的算法描述或流程控制，并把P P、V V操作加到程序的适当处。操作加到程序的适当处。 52例例3.13.1有两个进程有两个进程P1P1和和P2P2，P1P1的功能是计算的功能是计算x=a+bx=a+b的值，的值，a a和和b b是常量（在是常量（在P1P1的前面代码中能得到）

49、；的前面代码中能得到）； P2P2的功能的功能是计算是计算y=x+1y=x+1的值。的值。P1 P2 x=a+b; y=x+1; P1 P2 P(S);x=a+b; y=x+1;V(S); 53例例3.23.2 生产者生产者消费者问题消费者问题 公用缓冲池，公用缓冲池，有有n个缓冲区个缓冲区一组生产者生产产品一组生产者生产产品一组消费者取走产品一组消费者取走产品54生产者消费者问题是相互合作进程关系生产者消费者问题是相互合作进程关系的一种抽象的一种抽象 输入输入计算计算打印打印 生产者生产者 消费者消费者 生产者生产者 消费者消费者系统中使用资源的进程系统中使用资源的进程消费者消费者系统中释放

50、同类资源的进程系统中释放同类资源的进程生产者生产者55问题分析： 生产者生产者消费者之间的同步关系表现为：消费者之间的同步关系表现为：一旦一旦缓冲池中所有缓冲区均装满产品时，生产者必须缓冲池中所有缓冲区均装满产品时，生产者必须等待消等待消费者提供空缓冲区费者提供空缓冲区；一旦缓冲池中所有缓冲区全为空时，；一旦缓冲池中所有缓冲区全为空时，消费者必须消费者必须等待生产者提供满缓冲区等待生产者提供满缓冲区。 生产者生产者消费者之间还有互斥关系：消费者之间还有互斥关系：由于缓冲池由于缓冲池是临界资源，所以任何进程在对缓冲区进行存取操作时是临界资源，所以任何进程在对缓冲区进行存取操作时都必须和其他进程互

51、斥进行。都必须和其他进程互斥进行。 56问题解答： 所用信号量设置如下：所用信号量设置如下： ）同步信号量同步信号量empty，初值为，初值为n，表示消费者已把缓，表示消费者已把缓冲池中全部产品取走，有冲池中全部产品取走，有n个空缓冲区可用。个空缓冲区可用。 ）同步信号量同步信号量full，初值为，初值为0，表示生产者尚未把产品，表示生产者尚未把产品放入缓冲池，有放入缓冲池，有0个满缓冲区可用。个满缓冲区可用。 ）互斥信号量互斥信号量mutex，初值为，初值为1，以保证同时只有一，以保证同时只有一个进程能够进入临界区，访问缓冲池。个进程能够进入临界区，访问缓冲池。 57用信号量机制解决生产者用

52、信号量机制解决生产者消费者问题的消费者问题的算法描述如下：算法描述如下： 生产出一产品； P（full）； P（empty）； P（mutex）； P（mutex）； 从缓冲区取出一产品； 将该产品放入缓冲区； V（mutex）； V（mutex）； V（empty）； V（full）； 消费该产品； 58小结:用信号量机制解这类题的三个步骤 （1）分析进程间的制约关系）分析进程间的制约关系 （2）设置信号量）设置信号量 （3）实施）实施P、V操作。操作。 第一步是基础、关键，第三步是核心。第一步是基础、关键，第三步是核心。 掌握实现进程互斥与进程同步的第三步在形式上差异：即掌握实现进程互斥与

53、进程同步的第三步在形式上差异：即P、V操作总是操作总是配对配对出现的。出现的。 但但P,VP,V在在互斥问题互斥问题中总是出现在同一个进程的代码中，且紧中总是出现在同一个进程的代码中，且紧紧夹着临界区；而在紧夹着临界区；而在同步问题同步问题中，却是分别出现在两个合中，却是分别出现在两个合作进程的代码中，需要等消息的一方用作进程的代码中，需要等消息的一方用P操作，相应的对同操作，相应的对同一信号量的一信号量的V操作则在发出此消息的另一方中。操作则在发出此消息的另一方中。 59三、用三、用P P、V V操作原语实现进程的互斥操作原语实现进程的互斥 用用P P、V V操作原语实现进程的互斥也一样简单

54、，只需在相关操作原语实现进程的互斥也一样简单，只需在相关进程的临界区的前后分别施以进程的临界区的前后分别施以P P操作和操作和V V操作即可，即在相操作即可，即在相关进程的程序里由关进程的程序里由P P操作和操作和V V操作原语紧夹着临界区，就能操作原语紧夹着临界区，就能保证这些进程互斥地进入各自的临界区。保证这些进程互斥地进入各自的临界区。这里所用信号量的初值一般为这里所用信号量的初值一般为1 1，表示临界资源未被占用，表示临界资源未被占用，且其可用数目为且其可用数目为1 1。 用用P P、V V操作原语实现进程互斥的效率更高一些，因为操作原语实现进程互斥的效率更高一些，因为P P操操作中引入了阻塞机制，所以消除了作