我们毕业啦PPT课件

1、我们毕业啦其实是答辩的标题地方 操作系统原理 第三章 进程管理主讲人院系温 静信息工程学院PURSUING EXCELLENCE / TOWARD SUCCESSWUCHANG UNIVERSITY OF TECHNOLOGY武昌理工学院武昌理工学院CONTANTS主要内容主要内容程序执行方式进程的基本概念进程控制进程互斥进程同步123456进程通信7线程程序执行方式程序执行方式 程序的执行方式可分为两类：程序的执行方式可分为两类：1.1. 顺序执行顺序执行2.2. 并发执行并发执行程序的顺序执行程序的顺序执行例例1. 1. 在处理一个作业时，总是首先输入用户的程序和在处理一个作业时，总是首先

2、输入用户的程序和数据，然后进行计算，最后将所得的结果打印出来。数据，然后进行计算，最后将所得的结果打印出来。在早期的计算机中，输入、计算、打印这三个程序在早期的计算机中，输入、计算、打印这三个程序段的执行只能是一个一个地顺序执行。段的执行只能是一个一个地顺序执行。程序的顺序执行程序的顺序执行 例例2. 对于一个程序段中的多条语句来说，也有一个执对于一个程序段中的多条语句来说，也有一个执行顺序问题，如行顺序问题，如: S1: b=a+2; S2: c=b-5; S3: x=c+b; S4: y=x+10;S1S2S3S4程序顺序执行的特征程序顺序执行的特征(1) (1) 顺序性顺序性： 处理机的

3、操作必须严格按照程序所规定的顺序执行。处理机的操作必须严格按照程序所规定的顺序执行。(2) (2) 封闭性封闭性： 程序在执行时独占系统的全部资源，因此，机器资源状态的程序在执行时独占系统的全部资源，因此，机器资源状态的 改变只与执行的程序有关，而与外界环境无关。改变只与执行的程序有关，而与外界环境无关。(3) (3) 可再现性可再现性： 只要初始条件相同，一个程序的多次重复执行，将得到相同只要初始条件相同，一个程序的多次重复执行，将得到相同 的结果（不论它是从头到尾不停顿地执行，还是的结果（不论它是从头到尾不停顿地执行，还是“停停走走停停走走” 地执行，地执行，“可再现可再现”即可再次出现，

4、结果重复出现）。即可再次出现，结果重复出现）。前趋图前趋图前趋图是一个前趋图是一个有向无环图有向无环图，简称，简称DAGDAG。图中每个结点表示一个程序段、一条语句或一个进图中每个结点表示一个程序段、一条语句或一个进程。程。结点之间的有向边表示两个结点之间存在的偏序或结点之间的有向边表示两个结点之间存在的偏序或前趋关系前趋关系 “” “”。前趋图的例子前趋图的例子具有具有6 6个结点的前趋图个结点的前趋图: : 存在下述前趋关系存在下述前趋关系: : S1S1S2S2，S1S1S3S3，S1S1S4S4，S2S2S5S5，S3S3S5S5，S4S4S6S6，S5S5S6S6S S1 1S S4

5、 4S S3 3S S2 2S S5 5S S6 6前趋图的例子前趋图的例子 按照前趋图的定义分析，上图不是一个前趋图，按照前趋图的定义分析，上图不是一个前趋图，因为前趋图是一种有向无环图，而上图中因为前趋图是一种有向无环图，而上图中S2S3，S3S2，构成了一个环，所以不是前趋图。构成了一个环，所以不是前趋图。S1S2S3程序的并发执行程序的并发执行让我们再回到图让我们再回到图3-13-1的例子，对于的例子，对于n n个程序的处理，个程序的处理，每个程序都有输入、计算和打印三个步骤：每个程序都有输入、计算和打印三个步骤： 对作业对作业1 1的处理的处理: I1, C1, P1: I1, C1

6、, P1 对作业对作业2 2的处理的处理: I2, C2, P2: I2, C2, P2 对作业对作业n n的处理的处理: In, : In, CnCn, , PnPn程序的并发执行程序的并发执行当系统中存在着大量的操作时当系统中存在着大量的操作时, ,就可以进行并发处理就可以进行并发处理 并发执行时的前趋图并发执行时的前趋图: :I1I1I2I2I3I3I4I4C1C1C2C2C3C3C4C4P1P1P2P2P3P3P4P4程序的并发执行程序的并发执行两类前趋关系：两类前趋关系：（1 1）I1I1I2I2I3I3InIn（对输入机的竞争）（对输入机的竞争） C1 C1C2C2C3C3CnCn

7、（对（对CPUCPU的竞争）的竞争） P1 P1P2P2P3P3PnPn（对打印机的竞争）（对打印机的竞争） 原因是竞争资源原因是竞争资源（2 2）I1I1C1C1P1P1 I2 I2C2C2P2P2 In InCnCnPnPn 原因是程序内部的逻辑关系原因是程序内部的逻辑关系程序的并发执行程序的并发执行还有一些结点之间是没有还有一些结点之间是没有“”“”相连的。相连的。下标满足下标满足i+1i+1，i i和和i-1i-1关系的结点是可以关系的结点是可以并发并发的。的。如如I3I3、C2C2和和P1P1，I4I4、C3C3和和P2P2，而又因为这些操，而又因为这些操作作分别占用不同的物理部件，

8、因此可以达到真正的分别占用不同的物理部件，因此可以达到真正的并并行行操作。操作。程序的并发执行程序的并发执行程序的并发执行是指程序的并发执行是指: : 若干个程序段同时在系统中运行若干个程序段同时在系统中运行, ,这些程序段的执行在时这些程序段的执行在时间上是间上是重叠重叠的的, ,一个程序段的执行尚未结束一个程序段的执行尚未结束, ,另一个程序段另一个程序段的执行已经开始的执行已经开始, ,即使这种重叠是很小的一部分即使这种重叠是很小的一部分, ,也称这几也称这几个程序段是并发执行的个程序段是并发执行的。如如: : PQRP,Q,R这三个程序段就是并发执行的程序段这三个程序段就是并发执行的程

9、序段程序的并发执行程序的并发执行程序并发执行时的特征程序并发执行时的特征(1) (1) 间断性间断性： 多个并发程序共享系统资源，互相制约，因此产生多个并发程序共享系统资源，互相制约，因此产生间断性。间断性。(2) (2) 失去封闭性失去封闭性： 程序之间会产生关联，彼此之间会受到影响，不再程序之间会产生关联，彼此之间会受到影响，不再是在一个封闭环境中运行了。是在一个封闭环境中运行了。(3) (3) 不可再现性不可再现性： 程序的运行结果不能再次出现。程序的运行结果不能再次出现。程序的并发执行程序的并发执行例如：两个并发执行的程序例如：两个并发执行的程序A A和和B B，它们共享一个公共变量，

10、它们共享一个公共变量n n。 A A：n=1n=1； B B：n=2n=2； print print（n n）；）；程序程序A A和和B B并发执行时，可能会出现以下三种情况：并发执行时，可能会出现以下三种情况： print print（n n）在）在n=1n=1与与n=2n=2之后执行，则打印结果为之后执行，则打印结果为2 2； print print（n n）在）在n=2n=2与与n=1n=1之间执行，则打印结果为之间执行，则打印结果为2 2； print print（n n）在）在n=2n=2与与n=1n=1之后执行，则打印结果为之后执行，则打印结果为1 1；这种现象说明程序并发执行时会

11、发生这种现象说明程序并发执行时会发生与时间有关的错误与时间有关的错误。进程的基本概念进程的基本概念进程的基本概念进程的基本概念在多道程序环境下，在多道程序环境下，程序的并发执行程序的并发执行破坏了程序的封破坏了程序的封闭性和可再现性，使得程序的运行不再处于一个封闭闭性和可再现性，使得程序的运行不再处于一个封闭的环境中，从而导致出现了的环境中，从而导致出现了与时间有关的错误与时间有关的错误。但操作系统最重要的特征就是但操作系统最重要的特征就是并发并发，而程序又不能描，而程序又不能描述并发，因此需要引入一个新的概念述并发，因此需要引入一个新的概念进程进程。进程的定义进程的定义进程是程序在处理机上的

12、一次执行过程。进程是程序在处理机上的一次执行过程。（强调动态性）（强调动态性）进程是可以和别的计算并发执行的计算。进程是可以和别的计算并发执行的计算。（强调并发性）（强调并发性）进程是程序在一个数据集合上的运行过程，是系统进行资源分进程是程序在一个数据集合上的运行过程，是系统进行资源分配和调度的一个独立单位。配和调度的一个独立单位。（强调独立性）（强调独立性）进程是一个具有一定功能的程序关于某个数据集合的一次运行进程是一个具有一定功能的程序关于某个数据集合的一次运行活动。活动。（描述进程的数据结构）（描述进程的数据结构）19781978年在庐山召开的全国操作系统学术会议上，计算机学者给年在庐山

13、召开的全国操作系统学术会议上，计算机学者给出的定义：出的定义：进程是具有独立功能的程序关于某个数据集合的一进程是具有独立功能的程序关于某个数据集合的一次执行过程，是系统资源分配和调度的基本单位。次执行过程，是系统资源分配和调度的基本单位。进程的特征进程的特征1. 1. 结构性结构性 进程包含进程包含: :程序程序, ,数据数据, ,进程控制块进程控制块(PCB).(PCB).数据结构数据结构( (表格表格),),描述程序执行过程中的动态信息描述程序执行过程中的动态信息, ,是进程存在的唯一标志是进程存在的唯一标志,OS,OS通过通过PCBPCB管理程序管理程序, ,它是它是OSOS唯一能感知的

14、唯一能感知的. .程序程序数据数据PCBPCB用户编制用户编制加工对象加工对象描述程序执行状态描述程序执行状态PCBPCB是进程存在的唯一标志是进程存在的唯一标志进程的特征进程的特征2. 2. 动态性动态性动态性是进程的最基本特征。动态性是进程的最基本特征。进程的动态性具体体现在两个方面：进程的动态性具体体现在两个方面：u进程的运行过程是进程的运行过程是“执行执行暂停暂停执行执行”，这个过，这个过程具有动态性；程具有动态性；u进程具有一定的生命周期，在其生命期内是一种动进程具有一定的生命周期，在其生命期内是一种动态的特性。态的特性。进程的特征进程的特征3. 3. 并发性并发性 多个进程实体同时

15、存在于内存之中，能在一段时多个进程实体同时存在于内存之中，能在一段时间内都得到运行。引入进程的目的就是为了使程序能间内都得到运行。引入进程的目的就是为了使程序能与其它程序并发执行，以提高资源利用率和系统效率。与其它程序并发执行，以提高资源利用率和系统效率。4. 4. 独立性独立性 一是独立运行单位（没有引入线程的情况下）；一是独立运行单位（没有引入线程的情况下）；二是资源分配和调度的单位。二是资源分配和调度的单位。5. 5. 异步性异步性 进程按各自不可预知的速度向前推进。进程按各自不可预知的速度向前推进。进程与程序的区别进程与程序的区别程序是程序是静态静态的，而进程是的，而进程是动态动态的。

16、的。程序是程序是永久永久的，而进程是的，而进程是暂时暂时的。的。进程和程序并不是一一对应的。进程和程序并不是一一对应的。进程在执行过程中，根据需要可以创建其它进程，进程在执行过程中，根据需要可以创建其它进程，而程序不具有这个功能。而程序不具有这个功能。进程的状态进程的状态（不论哪种操作系统，三种基本状态不可少）（不论哪种操作系统，三种基本状态不可少）1. 1. 就绪状态（就绪状态（ReadyReady）：）：进程除了进程除了CPUCPU之外所有的资源之外所有的资源都得到了满足。（万事具备，只欠都得到了满足。（万事具备，只欠CPUCPU），处于就绪），处于就绪状态的进程可能有多个，通常将它们排成

17、一个队列，状态的进程可能有多个，通常将它们排成一个队列，称为就绪队列。称为就绪队列。2. 2. 执行状态（执行状态（RunRun）：）：进程正在使用进程正在使用CPUCPU。3. 3. 阻塞状态（阻塞状态（Block/Wait/SleepBlock/Wait/Sleep）：）：进程因缺少某种进程因缺少某种资源而放弃资源而放弃CPUCPU，根据阻塞原因不同而把处于阻塞状，根据阻塞原因不同而把处于阻塞状态的进程排成多个队列。态的进程排成多个队列。进程的状态进程的状态执行执行就绪就绪阻塞阻塞进程进程调度调度时间时间片完片完事件发生事件发生等待等待事件事件进程的三种基本状态及其转换进程的三种基本状态及

18、其转换进程控制块进程控制块进程控制块的作用进程控制块的作用 为了描述和控制进程的执行，系统为每个进程定为了描述和控制进程的执行，系统为每个进程定义了一个数据结构义了一个数据结构进程控制块（进程控制块（PCBPCB）。）。 它是进程的组成部分之一，是操作系统用来记录它是进程的组成部分之一，是操作系统用来记录进程状态及相关信息的数据结构。进程状态及相关信息的数据结构。 操作系统通过操作系统通过PCBPCB来了解和掌握进程的状态。来了解和掌握进程的状态。 PCBPCB是进程存在的唯一标志。是进程存在的唯一标志。进程控制块进程控制块进程控制块中的信息：进程控制块中的信息： 标识信息标识信息 处理机状态

19、信息处理机状态信息 进程调度信息进程调度信息 进程控制信息进程控制信息进程控制块进程控制块进程控制块的组织方式常见的有三种：进程控制块的组织方式常见的有三种：线性方式线性方式：把所有不同状态的进程的：把所有不同状态的进程的PCBPCB组织在组织在一个线性表中。一个线性表中。链接方式链接方式：把具有同一状态的进程的：把具有同一状态的进程的PCBPCB，通过，通过指针链接成一个队列。指针链接成一个队列。索引方式索引方式：系统根据所有进程的状态建立几张索：系统根据所有进程的状态建立几张索引表。引表。进程控制进程控制进程控制包含控制和管理进程的一些原语：进程控制包含控制和管理进程的一些原语： 进程创建

20、原语进程创建原语 进程撤销原语进程撤销原语 进程阻塞原语进程阻塞原语 进程唤醒原语进程唤醒原语 进程挂起原语进程挂起原语 进程激活原语进程激活原语进程创建进程创建进程创建的原因：进程创建的原因： 用户登录用户登录 提交作业提交作业 操作系统提供服务操作系统提供服务 应用请求应用请求进程创建进程创建进程的创建过程：进程的创建过程：1.1.申请空闲申请空闲PCBPCB。2.2.为新进程分配资源。为新进程分配资源。3.3.初始化新进程的初始化新进程的PCBPCB。4.4.将新进程的将新进程的PCBPCB插入就绪队列。插入就绪队列。进程撤销进程撤销进程撤销的原因：进程撤销的原因： 进程正常结束进程正常

21、结束 进程异常结束进程异常结束 外界干预外界干预进程撤销进程撤销进程的撤销过程：进程的撤销过程：1.1.根据被撤销进程的标识符，从根据被撤销进程的标识符，从P PCB集合中找到集合中找到该进程的该进程的PCB，从中读出该进程的状态。，从中读出该进程的状态。2.2.如果该进程的状态为执行，则首先应暂停该进如果该进程的状态为执行，则首先应暂停该进程的执行，转进程调度程序，在就绪队列中选程的执行，转进程调度程序，在就绪队列中选择一个新的进程占用择一个新的进程占用CPU运行。运行。3.3.检查该进程是否还有子孙进程，若有则应首先检查该进程是否还有子孙进程，若有则应首先撤销其所有的子孙进程，以防止它们成

22、为不可撤销其所有的子孙进程，以防止它们成为不可控的进程。控的进程。4.4.将被撤销进程所拥有的资源，或归还给父进程，将被撤销进程所拥有的资源，或归还给父进程，或归还给系统。或归还给系统。5.5.系统回收该被撤销进程的系统回收该被撤销进程的PCB，并将之放入，并将之放入PCB资源池，以便创建新进程时申请使用。资源池，以便创建新进程时申请使用。进程的阻塞与唤醒进程的阻塞与唤醒进程阻塞与唤醒的原因：进程阻塞与唤醒的原因： 请求系统服务请求系统服务 启动某种操作启动某种操作 新数据尚未到达新数据尚未到达 系统进程无新工作可做系统进程无新工作可做进程的阻塞与唤醒进程的阻塞与唤醒进程的阻塞过程：进程的阻塞

23、过程：1.1.停止当前进程的执行。停止当前进程的执行。2.2.保存该进程的保存该进程的CPU现场信息。现场信息。3.3.将进程状态改为阻塞，并插入到阻塞队列中。将进程状态改为阻塞，并插入到阻塞队列中。进程的唤醒过程：进程的唤醒过程：1.1.将被唤醒的进程从相应的阻塞队列中移出。将被唤醒的进程从相应的阻塞队列中移出。2.2.将进程状态由阻塞改为就绪，并将该进程插入将进程状态由阻塞改为就绪，并将该进程插入到就绪队列。到就绪队列。3.3.在某些抢占式系统中，若被唤醒进程的优先级在某些抢占式系统中，若被唤醒进程的优先级比当前运行进程高时，可能需要设置调度比当前运行进程高时，可能需要设置调度标志。标志。

24、注意注意：进程的阻塞和唤醒是一对作用刚好相反的原：进程的阻塞和唤醒是一对作用刚好相反的原语。语。问题问题过独木桥：过独木桥：P1P2P1（）（） 由西向东过独木桥；由西向东过独木桥；P2（）（） 由东向西过独木桥；由东向西过独木桥；进程间的间接相互制约关系进程间的间接相互制约关系 这种制约是由于这种制约是由于共享资源共享资源引起的，若某一进程引起的，若某一进程要求使用某一资源，而该资源正被另一进程使用，要求使用某一资源，而该资源正被另一进程使用，并且这一资源不允许两个进程同时使用，那么该进并且这一资源不允许两个进程同时使用，那么该进程只有等待已占用资源的进程释放后才能使用。程只有等待已占用资源

25、的进程释放后才能使用。进程进程资源资源进程进程进程互斥的概念进程互斥的概念进程进程互斥互斥当多个进程之间存在互斥关系当多个进程之间存在互斥关系时，这些进程之间本身没有逻时，这些进程之间本身没有逻辑关系，而是因为都要使用同辑关系，而是因为都要使用同一个一个临界资源临界资源而引起的。而引起的。 ExplanationExplanation进程之间因为竞争资源所导致进程之间因为竞争资源所导致的的间接相互制约关系间接相互制约关系ConceptConcept设备、表格、数据、程序段、变量、队列等设备、表格、数据、程序段、变量、队列等临界资源临界资源在一段时间内只允许一个进程访问的资源在一段时间内只允许一

26、个进程访问的资源交叉访问，容易产生交叉访问，容易产生与时间有关的错误与时间有关的错误概念概念举例举例错误错误 例例1 1 进程共享公共变量进程共享公共变量在一个银行系统的两个终端上，分别运行着两个进程P1和P2，它们共享同一账户变量count，进程P1、P2的功能都是从该账户中取款，部分程序段如下：P1： P2： M=count； N=count；M=M-200； N=N-300；count=M； count=N； 方式一：P1：M=count；M=M-200；count=M；P2： N=count；N=N-300；count=N；方式一是正确的；但方式二出现了与时间有关的错误，因为对共享变量

27、count采取了交叉访问。方式二：P1：M=count； P2： N=count；N=N-300；count=N；P1： M=M-200；count=M；临界区（临界区（ Critical Section Critical Section，CS CS ）进程中访问临界资源的那一段代码进程中访问临界资源的那一段代码临界区临界区如果一个进程正在如果一个进程正在访问临界资源，我访问临界资源，我们就说该进程进入们就说该进程进入了临界区。了临界区。如果能够保证各进程互如果能够保证各进程互斥地进入自己的临界区，斥地进入自己的临界区，便可以实现多个进程对便可以实现多个进程对临界资源的互斥访问。临界资源的互斥

28、访问。问题问题例例1中的进程中的进程p1和和p2的临界区是什么？的临界区是什么？M=count；M=M-200；count=M；N=count；N=N-300；count=N；进程进程p1的的临界区临界区进程进程p2的的临界区临界区临界临界资源资源count访问临界资源的格式访问临界资源的格式一个访问临界资源的进程描述如下：一个访问临界资源的进程描述如下：entry sectioncritical sectionexit sectionremainder section进入区进入区: 提出申请提出申请,并进行检查并进行检查临界区临界区: 访问临界资源访问临界资源退出区退出区: 恢复为未访问标志

29、恢复为未访问标志(访问之前的标志访问之前的标志)剩余剩余区：进程中的剩余代码区：进程中的剩余代码访问临界资源应遵循的规则访问临界资源应遵循的规则规则空闲让进空闲让进有有限限等等待待让让权权等等待待忙忙则则等等待待当无进程处于临界当无进程处于临界区时，可让要求进区时，可让要求进入临界区的进程进入临界区的进程进入临界区。入临界区。空闲让进空闲让进进程进入临界区只进程进入临界区只能停留有限的时间，能停留有限的时间，以免死锁。以免死锁。有限等待有限等待不能进入临界区时，不能进入临界区时，应立即释放处理机，应立即释放处理机，进入进入“等待队列等待队列”，以免陷入以免陷入“忙等忙等”。让权等待让权等待当已

30、有进程处于临当已有进程处于临界区时，其他进程界区时，其他进程则等待。则等待。忙则等待忙则等待问题问题生活中：道路资源少，行人车辆多，如何维持正常交通秩序？交通信交通信号灯号灯计算机系统中：系统资源少，进程多，如何确保进程间合理地竞争资源？信号量信号量信信号号量机制的量机制的诞诞生生Dijkstra，1930年5月11日2002年8月6日，荷兰人。 计算机科学家，毕业就职于荷兰Leiden大学，早年钻研物理及数学，而后转为计算学。曾在1972年获得过素有计算机科学界的诺贝尔奖之称的图灵奖。1965年，由荷兰学者Dijkstra提出的。一种进程同步工具一种进程同步工具引自交通管理中引自交通管理中其

31、基本思想是在多个相互合作的进程之其基本思想是在多个相互合作的进程之间使用简单的信号来同步间使用简单的信号来同步信信号号量量信号量的定义信号量的定义信号信号量量包含两个成员：包含两个成员：代表资源数目的整型变量代表资源数目的整型变量进程队列进程队列 StructureStructure信号量是一种结构体类型的变量ConceptConcept信号量定义实例信号量定义实例struct semaphore int value； queue L； 信号量结信号量结构体类型构体类型定义定义struct semaphore S；信号量类信号量类型变量定型变量定义义 信号量的取值含义信号量的取值含义整型值当S

32、.value=0时，代表系统中当前可用的资源数目。当S.value0时，其绝对值代表因为请求资源而被阻塞的进程个数。S.value的初始值只能取大于等于0的整数。S.value代表因为请求资源而被阻塞的进程队列。由于初始状态下，没有任何进程因为请求资源而被阻塞，所以S.L的初始值为空。S.L信号量的三种操作信号量的三种操作将信号量将信号量S初始化初始化为非负数，即系统初为非负数，即系统初始状态下信号量始状态下信号量S所代表的资源的数目。所代表的资源的数目。信号量信号量Swait操作操作使信号量使信号量的的value减减1。若为。若为负数，则执行负数，则执行wait操作的进程被阻塞，操作的进程被

33、阻塞，否则进程继续执行。否则进程继续执行。signal操作操作使信号量使信号量的的value加加1。如果值。如果值小于或等于小于或等于0，则唤，则唤醒一个因请求资源醒一个因请求资源而被阻塞的进程。而被阻塞的进程。原语原语wait(s)：每调用一次，代表申请一个资源：每调用一次，代表申请一个资源即原子操作，执行时不可中断即原子操作，执行时不可中断signal(s)：每调用一次，代表释放一个资源：每调用一次，代表释放一个资源原语原语waitwaitsignalsignalwaitwait原语原语wait（S）原语的程序）原语的程序描述如下：描述如下：void wait（semphore S） S.

34、value-； if（S.value0） block（S.L）；）； 流程图流程图 wait（s）s.value=s.value-1s.value0？本进程获得一本进程获得一个资源个资源本进程进入本进程进入s.L队列，被阻塞队列，被阻塞临界区临界区NYsignalsignal原语原语signal（S）原语的程）原语的程序描述如下序描述如下：void signal（semphore S） S.value+； if（S.value=0） wakeup（S.L）；）； 流程图流程图 signal（s）s.value=s.value+1s.value=0申请成功申请成功中断中断执行进执行进程程p20-

35、1=-10阻塞阻塞转去执行转去执行p1-1+1=0=0唤醒进程唤醒进程p2p1执行完毕，执行完毕，转去执行转去执行p20+1=1恢复到初始值恢复到初始值互斥信号量的取值范围互斥信号量的取值范围对于两个并发进程，互斥信号量的值仅能取对于两个并发进程，互斥信号量的值仅能取到到1，0和和-1三个值三个值 表示没有进表示没有进程进入临界程进入临界区区mutex=1 表示有一个表示有一个进程进入临进程进入临界区界区mutex=0 表示一个进表示一个进程进入临界程进入临界区，另一个区，另一个进程等待进进程等待进入入mutex=-1由于由于mutex为整型变量，所以取值范围为：为整型变量，所以取值范围为：-

36、1,1互斥信号量的取值范围互斥信号量的取值范围进一步推广，如果有进一步推广，如果有n n个并发进程访问同一个临个并发进程访问同一个临界资源，那么界资源，那么mutexmutex的取值范围应为的取值范围应为1-n1-n，11；如果如果n n个并发进程访问个并发进程访问m m个临界资源，则个临界资源，则mutexmutex的的取值范围为取值范围为m-nm-n，mm。互斥信号量的取值范围互斥信号量的取值范围semaphore mutex=60；void studenti（）（） while（true） wait（mutex）；）； 进入自习室；进入自习室； 自习；自习； 离开自习室；离开自习室； s

37、ignal（mutex）；）；void main（）（） parbegin student1（）；（）； student2（）；（）； studentn（）；（）； parend 当有当有100个学生都想要进入自习室时，则个学生都想要进入自习室时，则mutex的取值范围的取值范围为为-40，60。进程同步进程同步进程之间因为相互合作所导致的直接相互制约关系进程之间因为相互合作所导致的直接相互制约关系就是进程的同步。就是进程的同步。同步意味着两个或多个进程之间根据它们一致同意同步意味着两个或多个进程之间根据它们一致同意的协议进行相互作用。的协议进行相互作用。同步的实质是使各合作进程的行为保持某种

38、一致性同步的实质是使各合作进程的行为保持某种一致性或不变关系。或不变关系。要实现同步，一定存在着必须遵循的同步规则。要实现同步，一定存在着必须遵循的同步规则。进程同步的概念进程同步的概念AB数据数据读读进程进程存存缓冲区缓冲区取取进程进程加工加工进程进程A、B必须遵循以下同步规则：必须遵循以下同步规则：（1）进程）进程A把一个数据存入缓冲区后，应该向进程把一个数据存入缓冲区后，应该向进程B发送发送“缓冲区中有缓冲区中有等待处理的数据等待处理的数据”的消息。的消息。（2）进程）进程B从缓冲区取出一个数据后，应该向进程从缓冲区取出一个数据后，应该向进程A发送发送“缓冲区中的缓冲区中的数据已取走数据

39、已取走”的消息。的消息。（3）进程）进程A只有在得到进程只有在得到进程B发来的发来的“缓冲区中的数据已取走缓冲区中的数据已取走”的消息的消息后，才能把下一个数据存入缓冲区，否则进程后，才能把下一个数据存入缓冲区，否则进程A等待，直到消息到达。等待，直到消息到达。（4）进程）进程B只有在得到进程只有在得到进程A发来的发来的“缓冲区中有等待处理的数据缓冲区中有等待处理的数据”的的消息后，才能从缓冲区中取出数据并加工，否则进程消息后，才能从缓冲区中取出数据并加工，否则进程B等待，直到消息等待，直到消息到达。到达。用信号量机制实现进程同步用信号量机制实现进程同步一般同步问题可以分为两类：一般同步问题可

40、以分为两类：保证一组合作进程按逻辑需要所确定的执行次序来保证一组合作进程按逻辑需要所确定的执行次序来执行；执行；保证共享缓冲区（或共享数据）的合作进程的同步。保证共享缓冲区（或共享数据）的合作进程的同步。合作进程的执行次序合作进程的执行次序S1S3S6S4S5S2abcdefgsemaphore a，b，c，d，e，f，g；a=0；b=0；c=0；d=0；e=0；f=0；g=0；void S1（）（） signal（a）；）；signal（b）；）；void S2（）（）wait（a）；）； signal（c）；）； signal（d）；）；void S3（）（）wait（b）；）； sign

41、al（e）；）；void S4（）（）wait（c）；）； signal（f）；）；void S5（）（）wait（d）；）； signal（g）；）；void S6（）（）wait（e）；）； wait（f）；）； wait（g）；）； void main（）（）parbeginS1（）；（）；S2（）；（）；S3（）；（）；S4（）；（）；S5（）；（）；S6（）；（）；parend共享缓冲区的合作进程的同步共享缓冲区的合作进程的同步AB数据数据读读进程进程存存缓冲区缓冲区取取进程进程加工加工semaphore s1，s2；s1=1；s2=0；void A（）（） while（true）

42、产生一个数据；产生一个数据； wait（s1）；）； 存入缓冲区中；存入缓冲区中； signal（s2）；）；void B（）（） while（true） wait（s2）；）； 从缓冲区中取出一个数据；从缓冲区中取出一个数据； signal（s1）；）； 加工该数据；加工该数据；void main（）（） parbegin A（）；（）； B（）；（）； parend 进程同步与进程互斥的区别与联系进程同步与进程互斥的区别与联系进程的互斥与进程的同步又是有区别的。进程的互斥与进程的同步又是有区别的。进程的互斥是进程之间竞争临界资源的使用权。进程的互斥是进程之间竞争临界资源的使用权。进程同步更

43、多强调的是进程之间的合作，而共进程同步更多强调的是进程之间的合作，而共享资源只是为了实现合作而使用的一种工具。享资源只是为了实现合作而使用的一种工具。生产者生产者- -消费者问题消费者问题.0n-1pmc1c2ckp1p2生产者：多个产生数据的进程；生产者：多个产生数据的进程；消费者：多个从缓冲区取数据的进程。消费者：多个从缓冲区取数据的进程。生产者生产者- -消费者问题消费者问题1. 生产者正在往里放数据时，消费者不能取，其它进程也不能放数据生产者正在往里放数据时，消费者不能取，其它进程也不能放数据（互斥）应设互斥信号量（互斥）应设互斥信号量mutex；2. 假设缓冲区满了，送数据没地方装假

44、设缓冲区满了，送数据没地方装,应设信号量阻塞放数据，若缓冲应设信号量阻塞放数据，若缓冲区为空，则对消费者阻塞。区为空，则对消费者阻塞。一一.生产者和消费者的同步关系生产者和消费者的同步关系1. 禁止生产者向满的缓冲区送产品禁止生产者向满的缓冲区送产品(数据数据);2. 禁止消费者从空的缓冲区取产品禁止消费者从空的缓冲区取产品(数据数据).二二. 同步的信号量同步的信号量(灯灯)1. empty: 说明空缓冲区的数目说明空缓冲区的数目, 初初值值:n;2. full: 表示满缓冲区的数目表示满缓冲区的数目, 初初值值:0.三三. 缓冲区是临界资源缓冲区是临界资源,故应故应设设 一一 个互斥个互斥

45、 信号量信号量(灯灯)mutex 初值初值:1 实现对缓冲区的互斥操作实现对缓冲区的互斥操作.生产者生产者- -消费者问题消费者问题item Bnitem Bn； /定义有界缓冲区定义有界缓冲区B Bsemaphore empty=nsemaphore empty=n； /可用的空缓冲区数可用的空缓冲区数semaphore full =0semaphore full =0； /缓冲区内可用的产品数缓冲区内可用的产品数semaphore semaphore mutexmutex=1=1； /互斥信号量互斥信号量intint in=0 in=0； /放入缓冲区指针放入缓冲区指针intint out

46、=0 out=0； /取出缓冲区指针取出缓冲区指针void void produceriproduceri（）（） /i i=1,2,3, ,m=1,2,3, ,m while while（生产未完成）（生产未完成） 生产一件产品生产一件产品nextpnextp； wait wait（emptyempty）；）； /检测缓冲区中是否有空位检测缓冲区中是否有空位 wait wait（mutexmutex）；）； /检测有界缓冲区是否可用检测有界缓冲区是否可用 Bin= Bin=nextpnextp； /将产品放入缓冲区中将产品放入缓冲区中 in=(in+1)%n in=(in+1)%n； /将缓

47、冲区下标后移将缓冲区下标后移 signal signal（mutexmutex）；）； /释放有界缓冲区释放有界缓冲区 signal signal（fullfull）；）； /释放缓冲区填满一个空位的信号量释放缓冲区填满一个空位的信号量 生产者生产者- -消费者问题消费者问题void consumerj（）（） /j=1,2,3, ,k while（还需继续消费）（还需继续消费） wait（full）；）； /检测缓冲区中是否有产品检测缓冲区中是否有产品 wait（mutex）；）； /检测有界缓冲区是否可用检测有界缓冲区是否可用 nextc=Bout； /从缓冲区中取出一件产品从缓冲区中取出

48、一件产品 out=(out+1)%k； /将缓冲区下标后移将缓冲区下标后移 signal（mutex）；）； /释放有界缓冲区释放有界缓冲区 signal（empty）；）； /释放取空一个缓冲区的信号量释放取空一个缓冲区的信号量 消费一个产品；消费一个产品； void main（）（） parbegin produceri（）；（）； consumerj（）；（）； parend 生产者生产者- -消费者问题消费者问题生产者生产者- -消费者问题是一个典型的同步与互斥的混合问消费者问题是一个典型的同步与互斥的混合问题。题。在这一问题中应注意：在这一问题中应注意：在每个进程中用于实现互斥的在每

49、个进程中用于实现互斥的waitwait（mutexmutex）和）和signalsignal（mutexmutex）必须成对地出现，夹在两者之间的）必须成对地出现，夹在两者之间的代码段是进程的临界区；代码段是进程的临界区；对同步信号量对同步信号量emptyempty和和fullfull的的waitwait和和signalsignal操作，同操作，同样需要成对地出现，但它们分别处于不同的进程中；样需要成对地出现，但它们分别处于不同的进程中；在每个进程中的多个在每个进程中的多个waitwait操作的次序不能随便颠倒，操作的次序不能随便颠倒，一般来说，用于互斥的一般来说，用于互斥的waitwait操

50、作总是在后面执行，操作总是在后面执行，而而signalsignal操作的次序则无关紧要。操作的次序则无关紧要。哲学家进餐问题哲学家进餐问题盘盘P0P1P2P3P4S0S1S2S3S4哲学家只有拿到了左边哲学家只有拿到了左边和右边的筷子才能用餐和右边的筷子才能用餐.设信号量设信号量S0, S1, S2, S3, S4分别表示桌上的五支分别表示桌上的五支筷子筷子,初始值均为初始值均为1.S0=1; S1=1; S2=1; S3=1; S4=1.哲学家进餐问题哲学家进餐问题semaphore chopstick5 ;int i；for（ i=0；i5；i+） chopsticki=1；void ph

51、ilosopheri( ) /i=0,1,2,3,4 while（true） think； hungry； wait（chopsticki）；）； wait（chopstick(i+1)%5）；）； eat； signal（chopsticki）；）； signal（chopstick(i+1)%5）；）； void main（）（） parbeginphilosopher0（）；（）； philosopher1（）；（）； ； philosopher4（）；（）； parend 哲学家进餐问题哲学家进餐问题 在上述解法中，如果五位哲学家同时拿起左在上述解法中，如果五位哲学家同时拿起左边（或右

52、边）的筷子，则桌上的五支筷子全边（或右边）的筷子，则桌上的五支筷子全部分完了，当每位哲学家企图再拿起其右边部分完了，当每位哲学家企图再拿起其右边（或左边）的筷子时，将出现（或左边）的筷子时，将出现死锁死锁。 哲学家进餐问题哲学家进餐问题为了防止死锁的发生，可以采取以下一些措施：为了防止死锁的发生，可以采取以下一些措施：至多允许四位哲学家同时进餐至多允许四位哲学家同时进餐 奇数号哲学家先取左边的筷子，然后再取右边的筷奇数号哲学家先取左边的筷子，然后再取右边的筷子；偶数号哲学家先取右边的筷子，然后再取左边子；偶数号哲学家先取右边的筷子，然后再取左边的筷子。的筷子。 每位哲学家必须取到左右两边的筷子

53、才能进餐，否每位哲学家必须取到左右两边的筷子才能进餐，否则，一支筷子也不取。则，一支筷子也不取。 进程通信进程通信进程之间互相交换信息的工作称为进程通信。进程之间互相交换信息的工作称为进程通信。高级通信机制是指用户可以直接利用操作系统高级通信机制是指用户可以直接利用操作系统所提供的一组通信原语高效地传送大量数据的所提供的一组通信原语高效地传送大量数据的一种通信方式。一种通信方式。 进程通信的类型进程通信的类型消息传递通信机制消息传递通信机制管道通信机制管道通信机制共享内存通信机制共享内存通信机制消息传递通信机制消息传递通信机制消息传递通信机制是实现进程通信的常用方式。消息传递通信机制是实现进程

54、通信的常用方式。这种通信方式既可以实现进程间的信息交换，这种通信方式既可以实现进程间的信息交换，也可以实现进程间的同步。也可以实现进程间的同步。消息传递通信机制可分为直接通信和间接通信消息传递通信机制可分为直接通信和间接通信两种类型。两种类型。直接直接通信方式通信方式所谓直接通信方式，是指发送进程利用操作系统所提供所谓直接通信方式，是指发送进程利用操作系统所提供的发送原语，直接将消息发送给接收进程，中间不经过的发送原语，直接将消息发送给接收进程，中间不经过任何第三方媒介。任何第三方媒介。 系统提供两条通信原语，分别用于发送和接收消息。系统提供两条通信原语，分别用于发送和接收消息。sendsen

55、d（receiverreceiver，messagemessage）：）：表示将消息表示将消息messagemessage发送给接收进程发送给接收进程receiverreceiver。receivereceive（sendersender，messagemessage）：）：表示接收由发送进程表示接收由发送进程sendersender发来的信息发来的信息messagemessage。 直接通信方式直接通信方式（1 1）消息缓冲通信机制中的数据结构）消息缓冲通信机制中的数据结构 structstruct message buffer message buffer sender sender； /

56、消息发送者进程标识符消息发送者进程标识符 size size； /消息长度消息长度 text text； /消息正文消息正文 next next； /指向下一个消息缓冲区的指针指向下一个消息缓冲区的指针 structstruct process control block process control block mqmq； /消息队列队首指针消息队列队首指针 mutexmutex； /消息队列互斥信号量消息队列互斥信号量 smsm； /消息队列资源信号量消息队列资源信号量 直接通信方式直接通信方式（2 2）发送原语）发送原语void sendvoid send（receiverreceiv

57、er，a a） getbufgetbuf（a.sizea.size，i i）；）； /根据消息长度根据消息长度a.sizea.size申请一个消息缓冲区申请一个消息缓冲区i i i.senderi.sender= =a.sendera.sender； /将发送区将发送区a a中的消息复制到消息缓冲区中的消息复制到消息缓冲区i i中中 i.sizei.size= =a.sizea.size； i.texti.text= =a.texta.text； i.nexti.next=0=0； /设置消息缓冲区指针域为空设置消息缓冲区指针域为空 getidgetid（PCB setPCB set，rece

58、iver.jreceiver.j）；）；/获得接收进程内部标识符获得接收进程内部标识符j j wait wait（j.mutexj.mutex）；）； /消息队列是临界资源，必须互斥访问消息队列是临界资源，必须互斥访问 insert insert（j.mqj.mq，i i）；）； /将消息缓冲区将消息缓冲区i i插入消息队列的队尾插入消息队列的队尾 signal signal（j.mutexj.mutex）；）； /释放消息队列的互斥信号量释放消息队列的互斥信号量 signal signal（j.smj.sm）；）； /释放发送一条消息的资源信号量释放发送一条消息的资源信号量 直接通信方式直接

59、通信方式（3 3）接收原语）接收原语void receivevoid receive（b b） j=internal name j=internal name； /获得接收进程的内部标识符获得接收进程的内部标识符 wait wait（j.smj.sm）；）； /申请一条消息申请一条消息 wait wait（j.mutexj.mutex）；）； /对消息队列采取互斥访问对消息队列采取互斥访问 remove remove（j.mqj.mq，i i）；）； /将消息将消息i i从消息队列中移出从消息队列中移出 signal signal（j.mutexj.mutex）；）； /释放消息队列的互斥信号

60、量释放消息队列的互斥信号量 b.senderb.sender= =i.senderi.sender；/将消息缓冲区将消息缓冲区i i中的消息复制到接收区中的消息复制到接收区b b中中 b.sizeb.size= =i.sizei.size； b.textb.text= =i.texti.text； 直接通信方式直接通信方式进程进程A进程进程BPCB(B)第一消息缓冲区第一消息缓冲区send(B,a)发发送送区区aasender:Asize: 5text: Hellomqmutexsmsender:Asize: 5text:Hellonext:0receive(b)sender:Asize: 5