湘潭大学操作系统课件第3章课件定稿.ppt

1、第3章 进程与线程,3.1 进程概念 3.2 进程控制 3.3 线程 3.4 互斥和同步,1,3.1 进程概念,3.1.1 程序的顺序执行及其特征 1. 程序的顺序执行 通常可以把一个应用程序分成若干个程序段，各程序段之间必须按照某种先后次序顺序执行，仅当前一程序段（操作）执行完后，才能执行后继程序段（操作）。,2,3.1.1 程序的顺序执行及其特征,1. 程序的顺序执行,3,图 3.1 多道程序的顺序执行,3.1.1 程序的顺序执行及其特征,2. 程序顺序执行的特征 （1）顺序性：处理机的操作严格按照程序所规定的顺序执行，即每一操作必须在上一个操作结束之后开始。 （2）封闭性：程序是在封闭的

2、环境下执行的，即程序运行时独占整个系统资源，资源的状态（除初始状态外）只有本程序可以改变。 （3）可再现性：只要程序执行时的环境和初始条件相同，当程序重复执行时，不论它的执行方式如何，是连续执行，还是“走走停停”的执行，其结果都是相同的。,4,3.1.2 程序的并发执行及其特征,1. 程序的并发执行 为了提高计算机的利用率、处理速度和系统的吞吐量，并行处理技术和并发程序设计技术在计算机中已经得到了广泛应用，成为了现代操作系统的基本特征之一。,5,图 3.2 多道程序并发执行,3.1.2 程序的并发执行及其特征,前趋图的引入：前趋图是一个有向无环图（Directed Acyclic Graph,

3、 DAG） 考虑具有以下四条语句的一个程序段： S1: a:=x+2; S2: b:=y+4; S3: c:=a+b; S4: d:=c+b;,6,图 3.3 四条语句的前趋图,3.1.2 程序的并发执行及其特征,2. 程序并发执行的特征 （1）间断（异步）性：程序在并发执行时，由于它们共享系统资源，以及为了完成同一任务而相互合作，致使这些并发程序之间形成了相互制约的关系。 （2）失去封闭性：程序在并发执行时，多个程序共享系统中的各种资源，因此，系统资源的状态将由多个程序来改变，致使程序失去了封闭性。 （3）不可再现性：程序在并发执行时，由于失去了封闭性，也将导致其失去执行的可再现性。,7,使

4、程序能够并发执行，并能够对并发执行的程序进行描述和控制 进程 已有的进程定义： 进程是程序的一次执行； 进程是可以和别的计算并发执行的计算； 进程是定义在一个数据结构上，并能够在其上进行操作的一个程序； 进程是程序在一个数据集合上运行的过程，它是系统进行资源分配和调度的一个独立单位。,3.1.3 进程的概念及其特征,8,我们将进程定义为： 进程是进程实体的运行过程，是系统进行资源分配和调度的一个独立单位。,3.1.3 进程的概念及其特征,9,程序和进程之间的区别与联系： 程序是完成特定任务的一组指令的结合，可以永久保存，具有静态性； 进程是程序在某一数据结构上的一次执行过程，是系统进行资源分配

5、和调度的基本单位，具有动态性； 一个进程可以包含多个程序，一个程序也可以被多个进程执行。,3.1.3 进程的概念及其特征,10,1. 两状态模型 包含运行态（Running）和非运行态（Not running）两种进程状态 创建了一个新进程之后，它会以非运行态加入到系统中，等到操作系统为其分派处理器 当前处于运行态的进程会不时地中断，由系统中的分派器选择处于非运行状中的某一个进程运行,3.1.4 进程状态,11,（a） 状态变迁图,3.1.4 进程状态,12,（b） 排队图,3.1.4 进程状态,13,2.五状态模型 包括就绪态（Ready）、运行态（Running）、阻塞态（Blocked）

6、、新建态（New）和终止态（Terminate） 进程状态描述： （1）新建态：刚刚创建的新进程，通常是指进程控制块已经创建，但还没有加载到系统内存中的进程。 （2）就绪态：进程等待系统为其分派处理器，而此时处理器被其它进程占据，所以该状态进程不能执行，但已经具备了除处理器之外的进程执行所需要的所有条件。,3.1.4 进程状态,14,（3）运行态：进程已获得所需资源并占据处理器，处理器正在执行该进程。 （4）阻塞态：也称为等待态、挂起态或睡眠态，进程在等待某个事情的发生而暂时不能运行，例如等待某个I/O操作的完成。 （5）终止态：进程或者因为执行结束或者因为被撤销而从可执行进程组中退出。,3.

7、1.4 进程状态,15,图3.5 五状态模型,3.1.4 进程状态,16,进程状态间可能的转换及原因有： 新建就绪：系统纳入一个新进程。 就绪运行：进程被调度程序选中，占据处理器而进入运行状态。 运行终止：进程运行结束或被撤销则退出系统进入终止态。 运行就绪：进程分配的占据处理器的时间片已经用完，或者是具有更高优先级的进程进入系统，当前正在运行的进程被抢占了处理器，此时进程从运行态转换到就绪态。 运行阻塞：进程在等待系统分配资源或者等待某些事件的发生，进程让出处理器由运行态转入阻塞态。 阻塞就绪：处于阻塞队列中的进程等待的资源可用或者等待的事件发生之后，进程从阻塞态转换到就绪态，等待处理器选中

8、它运行。,17,挂起状态的引入 对于内存中的多个进程，处理器依次选中运行，当一个进程正在等待I/O事件发生时，处理器转移到另一个进程。但是，处理器的速度比I/O要快很多，有可能内存中所有进程都在等待I/O事件的完成，导致处理器处于空闲状态。 引入挂起（Suspend）的概念：内存中没有就绪的进程时，系统将内存中处于阻塞的进程换出到外存中的挂起队列，而将外存中的就绪进程激活，换入到内存,3.1.4 进程状态,18,图3.6 引入挂起的进程状态转换模型,3.1.4 进程状态,19,进程控制块（Process control block, PCB）是操作系统用来记录进程状态和相关信息，控制进程运行的

9、数据结构，是进程的唯一标识符 在PCB中，主要包含如下的信息:,3.1.5 进程控制块,20,进程标识符 进程状态 调度信息 程序计数器,上下文数据 内存指针 I/O状态信息,进程控制是进程管理中最基本的功能 在操作系统中，不同功能都是通过执行各种原语（Primitive）操作实现 原语是由若干条指令构成、可完成特定功能的程序段,3.2 进程控制,21,引起进程创建的事件： （1）批处理作业 （2）用户登录 （3）提供服务 （4）进程派生,3.2.1 进程创建,22,创建一个新进程的具体步骤： （1）系统为新建进程申请一个空白的进程控制块，获得一个唯一的进程标识符。 （2）系统为新建进程分配运

10、行所需的资源，包括：内存、处理器时间、I/O设备等。 （3）进程控制块（PCB）初始化。 （4）设置链接，如果就绪队列允许新进程插入，则将新进程插入就绪队列。,3.2.1 进程创建,23,引起进程终止的事件： （1） 正常完成 （2） 运行超时 （3） 等待超时 （4） 内存不足 （5） 越界错误 （6） 保护错误 （7） 算术错误,3.2.2 进程终止,24,（8） I/O错误 （9） 无效指令 （10）特权指令 （11）操作员或操作系统干涉 （12）父进程请求 （13）父进程终止,终止原语的具体步骤： （1）根据需要终止进程的进程标识符，从PCB集合中查找对应的进程，从中读出该进程的状态。

11、 （2）若被终止进程正处在执行状态，则应立即终止该进程的执行，并设置相应的调度信息，用于指示该进程被终止后应重新进行调度。 （3）将被终止进程所拥有的所有资源归还给其父进程，或者归还给系统。,3.2.2 进程终止,25,（3）若被终止进程还拥有子孙进程，则将其所有子孙进程一并终止。 （4）归还PCB所占据的空间。,3.2.2 进程终止,26,1. 进程阻塞 进程阻塞是指进程在执行过程中因等待某个事件的发生或等待某个操作的完成而不得不让出处理器。 引起进程阻塞的主要事件有： （1）请求系统服务。 （2）启动某种操作。 （3）新数据尚未到达。 （4）无新工作可做。,3.2.3 进程阻塞和唤醒,27

12、,阻塞原语（Block primitive）的具体步骤： （1）正在执行的进程立即终止执行，把PCB中的进程状态由执行改为阻塞，并将处理机状态写入PCB中。 （2）将PCB插入阻塞队列中，等到事件的发生或操作的完成。 （3）系统将处理机重新分派给另一就绪进程，按照新进程的处理机状态更新处理机环境，就绪进程开始执行。 （4）当被阻塞进程等待的事件发生或者等待的操作完成时，则操作系统会通过唤醒原语将等待该事件的进程唤醒。,3.2.3 进程阻塞和唤醒,28,阻塞,3.2.3 进程阻塞和唤醒,29,执行态,阻塞态,阻塞队列,Px,Px,Px,Pz,Py,就绪队列,调度程序,执行态,Py,阻塞事件,2.

13、 进程唤醒 当被阻塞进程等待的事件发生，如等待的I/O操作已完成，或者等待的操作完成时，则操作系统会通过唤醒原语将等待该事件的进程唤醒。 唤醒原语（Wakeup primitive）的具体步骤： （1）根据进程标识符从等待该事件的阻塞队列中找到需要唤醒的进程PCB。 （2）将PCB中的进程状态阻塞改成就绪，并将该进程插入到就绪队列中。,3.2.3 进程阻塞和唤醒,30,唤醒,3.2.3 进程阻塞和唤醒,阻塞队列,Px,Pz,将PCB由现行 的阻塞态改为 就绪态,就绪队列,Px,Px,Pa,Pb,1. 进程挂起 当系统中出现了引起挂起的事件，如内存资源不足时，操作系统将利用挂起原语将处于阻塞状态

14、的进程挂起。 挂起原语（Suspend primitive）的具体步骤： （1）根据进程标示符，在PCB集合中找到需要挂起的进程。 （2）检查挂起进程的状态。,3.2.4 进程挂起和激活,32,2. 进程激活 激活，对应于挂起，是让被挂起的进程重新活跃起来，也就是把进程从外存调入到内存中。当系统中出现了引起激活的事件时，操作系统会利用激活原语将挂起进程激活。 激活原语（Active primitive）的具体步骤： （1）根据进程标示符，在PCB集合中找到需要激活的进程。 （2）检查激活进程的状态。,3.2.4 进程挂起和激活,33,早期的计算机操作系统中，进程既是资源分配的基本单位，又是调度

15、的基本单位 操作系统发展至今，进程在调度中会存在许多问题，增加了调度的难度和开销 例如：现代操作系统很重要的一方面是进程的并发执行，然而进程的并发执行使得进程调度的开销日益增大，系统效率明显降低,3.3 线 程,34,进程包含两方面的特点： （1）资源所有权，进程是一个可拥有资源的独立单位。 （2）调度，进程同时又是一个可独立调度和分派的基本单位。一个进程沿着通过一个或多个程序的一条执行路径执行。执行中可能与其它进程的执行过程交替进行，所以，一个进程具有一个执行状态和一个分派的优先级，同时又是一个能被操作系统调度和分派的实体。,3.3.1 线程简介,35,在操作系统中引入进程的目的，是为了使多

16、个程序能并发执行，以提高资源利用率和系统吞吐量。 在操作系统中再引入线程，则是为了减少程序在并发执行时所付出的时空开销，使操作系统具有更好的并发性。 通常把调度和分派的基本单位称做线程或轻量级进程（Light weight process, LWP）,而把资源分配的基本单位称做进程或者任务。,3.3.1 线程简介,36,1.多线程概念 进程在任一时刻只有一个执行控制流，通常将这种结构的进程称为单线程进程（Single threaded process）。 多线程进程（Multiple threaded process）同一进程中设计出多条控制流，并且满足： （1）多控制流之间可以并行执行； （

17、2）多控制流切换不需通过进程调度； （3）多控制流之间可以通过内存直接通信联系，从而降低通信开销。,3.3.2 多线程,37,图3.7 进程和线程,3.3.2 多线程,38,2.多线程环境下的进程和线程 （1）多线程环境下的进程 在多线程环境中，进程被定义为资源分配的基本单位，与进程相关的有： 存放进程映象的虚拟地址空间 受保护地对处理器、其他进程、文件和I/O资源的访问,3.3.2 多线程,39,（2）多线程环境下的线程 一个进程内包含一个或者多个线程，每个线程都包含： 线程执行状态 当线程处于非运行状态时，有一个受保护的线程上下文，用于存储现场信息 一个执行堆栈 容纳每个线程的局部变量的存

18、储空间 与进程内的其它线程共享访问进程的内存空间和资源,3.3.2 多线程,40,图3.8 单线程和多线程环境下的进程模型,3.3.2 多线程,41,线程的主要特性： （1）并发性：同一进程的多个线程可在一个或者多个处理机上并发或并行地执行 （2）共享性：同一个进程中的所有线程共享但不拥有进程的状态和资源 （3）动态性：生命周期中经历各种状态的变化 （4）结构性：线程是操作系统中的调度和分派的基本单位，具有唯一的标识符和线程控制块,3.3.2 多线程,42,3.线程状态 线程的关键状态有：运行态、就绪态和阻塞态 与线程状态转换相关的操作： 派生 阻塞 解除阻塞 结束,3.3.2 多线程,43,

19、1.线程实现 （1）用户级线程（User level thread, ULT） 线程管理的所有工作都由应用程序完成，内核意识不到线程的存在。,3.3.3 线程实现与线程模型,44,用户级线程方式优点： 因为所有线程的管理数据结构都在该进程的用户空间中，因此，线程切换不需要转换到内核空间，从而节省了模式切换的开销。 调度算法可以是基于不同进程量身定做。不同进程可以根据自身需要，为自己量身定做适合自身的调度算法对线程进行管理和调度。 用户级线程的实现与操作系统平台无关，即可以在任何操作系统中运行。,3.3.3 线程实现与线程模型,45,用户级线程方式缺点： 许多系统调用会引起阻塞，当用户级线程执行

20、一个系统调用时，不仅该线程会被阻塞，而且该线程所在进程内的所有线程都会被阻塞。但是，如果在内核级线程方式中，一个线程被阻塞，进程中的其它线程仍然可以运行。 在纯粹的用户级线程实现方式中，多线程应用不能利用多处理机技术进行多重处理。内核一次只为每个进程分配一个处理器，即进程每次只有一个线程处于运行状态，其它线程此时只能等待。,3.3.3 线程实现与线程模型,46,（2）内核级线程（Kernel level thread, KLT） 线程管理的所有工作都是由内核完成，应用程序并没有参与其中。即无论是用户进程中的线程，还是系统进程中的线程，他们的创建、终止和切换等也是依靠内核，在内核空间实现的。,3

21、.3.3 线程实现与线程模型,47,内核级线程方式优点： 内核能够同时为同一进程中的多个线程分配多个处理器，即能让多个线程并行执行。 如果进程中的一个线程被阻塞了，内核可以为该进程中的其它线程分派处理器资源使其运行，当然也可以调度其它进程中的线程运行。 内核本身也可以采用多线程技术，可以提高系统的执行速度和效率。,3.3.3 线程实现与线程模型,48,内核级线程方式缺点： 因为线程调度和管理是在内核实现，而用户进程的线程却是在用户态下运行。因此在进行线程与同一进程内其它线程切换时，需要从用户态转到内核态进行，从而导致较大的系统开销。,3.3.3 线程实现与线程模型,49,（3）组合方式 同一个

22、进程内的多个线程可以同时在多处理器上并行执行，而且一个线程被阻塞时，同一进程内的其它线程可以调度运行，并不需要阻塞整个进程。所以，组合方式多线程机制能够结合KLT和ULT两者的优点，并克服了其各自的不足。,3.3.3 线程实现与线程模型,50,图3.9 线程实现方式,3.3.3 线程实现与线程模型,51,2.线程模型 （1）多对一模型,3.3.3 线程实现与线程模型,52,图3.10 多对一模型,（2）一对一模型,3.3.3 线程实现与线程模型,53,图3.11 一对一模型,（3）多对多模型,3.3.3 线程实现与线程模型,54,图3.12 多对多模型,操作系统设计中的核心问题是关于进程和线程

23、的管理，例如： 采用多道程序设计技术管理单处理器系统中的多个进程 采用多处理技术管理多处理器系统中的多个进程 采用分布式处理技术管理多台分布式计算机系统中的多个进程 并发是上述管理问题实现的基础，也是操作系统设计的核心,3.4 互斥和同步,55,并发涉及的术语： （1）临界区（Critical section） （2）竞争（Competition） （3）同步（Synchronization） （4）互斥（Mutual exclusion） （5）死锁（Deadlock） （6）饥饿（Starvation）,3.4.1 并发原理,56,是一段程序代码，进程将在此代码中访问共享的资源，当另一个进

24、程已经在该代码中运行时，则该进程不能在这段代码中执行,多个进程在访问一个共享数据时，结果依赖于它们执行的相对时间，这种关系称为竞争,系统中有一些相互合作、协同工作的进程，它们之间的相互联系称为进程的同步,多个进程因争用临界区内的共享资源而互斥的执行，即当一个进程在临界区访问共享资源时，其它进程不能进入该临界区访问任何共享资源,两个或两个以上的进程因其中的每个进程都在等待其它进程执行完毕而不能继续执行，这样的情形称为死锁,是指一个可运行的进程虽然能继续执行，但被调度程序无限期的忽视而不能执行的情况,1.两种制约关系 （1）直接相互制约关系 （2）间接相互制约关系,3.4.1 并发原理,57,并发

25、执行的多个进程需要相互协作共同完成一个任务，在此期间，多个进程需要在一些动作上进行同步，即一个进程的某个动作与协作进程的某些动作之间在时序上有一定的关系。这些进程间的直接相互制约关系为进程同步，这都源自于多个进程间的相互合作。,当两个或两个以上的进程在同时竞争每次只允许被一个进程使用的资源时，通过互斥协调多个进程对该资源的使用顺序。这些进程间的间接相互制约关系为进程互斥，这都源自于多个进程间的相互竞争。,2.临界区和临界资源 进程间竞争资源产生如下的几个控制问题 （1）互斥 （2）死锁 （3）饥饿 临界资源（Critical resouce），多个进程间采取互斥的方式实现对临界资源的共享访问

26、使用临界资源的程序代码称为临界区（Critical section）,3.4.1 并发原理,58,多个进程共享临界区，需遵循如下的调度原则： 空闲让进 忙则等待 有限等待 让权等待,3.4.1 并发原理,59,当临界资源处于空闲状态，临界区没有进程进入时，允许一个请求进入临界区的进程立即进入自己的临界区,当已有进程进入临界区时，临界资源正在被访问，因此其它试图进入临界区的进程必须等待，实现对临界资源的互斥访问,对于要求访问临界资源的进程，应保证其在有限的时间内能够进入自己的临界区访问临界资源，以免产生“死等”现象,当进程不能进入自己的临界区访问临界资源时，应当立即释放处理机，以免进程陷入“忙等

27、”状态,1.关中断 2.TestAndSet指令 TestAndSet指令描述如下： boolean TestAndSet(boolean *lock) boolean temp = *lock; *lock = TRUE; return temp; ,3.4.2 硬件同步,60,临界区问题看成是一个简单的锁工具（避免竞争）。开始时锁是开着的，一个进程进入临界区后便把锁锁上，此时其它进程就不能进入临界区。直至进程离开临界区，再把锁打开允许其它进程进入临界区。,一个进程将一直运行，直到它调用了一个系统服务或被中断。为保证互斥，只需保证一个进程不被中断就可以了。换句话说，对于临界区的管理可以看成在

28、进入锁测试之前关闭中断，直到完成锁测试并上锁之后才能打开中断。,TestAndSet指令实现互斥的示例如下： do while(TestAndSet(,3.4.2 硬件同步,61,3.Swap指令 Swap指令为对换指令，定义如下： void Swap(boolean *a, boolean *b) Boolean temp = *a; *a = *b; *b = temp; ,3.4.2 硬件同步,62,使用Swap指令实现互斥的示例如下： do data = TRUE; while(data = TRUE) Swap(,3.4.2 硬件同步,63,1.整型信号量 Dijkstra把整型信号

29、量s定义成一个用于表示资源数目的整型变量。进程通过信号量传送信号，利用两个特殊的操作发送和接收信号。 signal(s)：通过信号量s传送信号 wait(s)： 通过信号量s接收信号 如果相应的信号仍然没有发送，则进程被挂起，直到发送完为止。,3.4.3 信号量机制,64,wait()操作定义如下 void wait(s) while(s=0) ; /do nothing s-; signal()操作定义如下 void signal(s) s+; ,3.4.3 信号量机制,65,2.记录型信号量 整型信号量机制没有满足让权等待的原则，可能使进程处于饥饿的忙等状态。 假设s为一个记录型数据结构，

30、其中一个分量为整形量value，另一个为信号量队列queue。value通常是一个具有非负初值的整型变量，queue是一个初始状态为空的进程队列，当一个进程必须等待信号量时，就加入到进程队列中去。,3.4.3 信号量机制,66,wait和signal操作定义如下： wait(s)：信号量s减l，若结果小于0，则调用wait(s)的进程被设置成等待信号量s的状态。 signal(s)：将信号量s加1，若结果不大于0，则释放一个等待信号量s的进程。 记录型信号量数据结构定义如下： typedef struct int value; QueueType queue; semaphore;,3.4.3

31、 信号量机制,67,wait( )操作定义如下： void wait(semaphore *s) s.value-; if(s.value 0) block(s.queue); / add this process into s.queue signal( )操作定义如下： void signal(semaphore *s) s.value+; if(s.value = 0) wakeup(s.queue); / remove a process from s.queue ,3.4.3 信号量机制,68,分析得出以下结论： （1）若信号量s.value值为正，则该值表示在对进程进行阻塞之前对信

32、号量s可以实施的wait()操作个数，即系统中某类资源实际可用数目； （2）若信号量s.value值为负，则其绝对值表示阻塞队列s.queue中等待的进程个数； （3）每次wait()操作，意味着进程请求一个单位的该类资源，使系统中可供分配的该类资源数减少一个，每次signal()操作，表示执行进程释放一个单位资源，使系统中可供分配的该类资源数增加一个。,3.4.3 信号量机制,69,3.二元信号量 假设s为一个记录型数据结构，其中一个分量为value，它仅能取值0和1，另一个分量为信号量队列queue。 一个二元信号量的值只能是0或者1 typedef struct enum zero, o

33、ne value; QueueType queue; binary_semaphore;,3.4.3 信号量机制,70,void waitB(binary_semaphore *s) if(s.value = one) s.value = zero; else block(s.queue); / add this process into s.queue void signalB(binary_semaphore *s) if(s.queue is empty() s.value = one; else wakeup(s.queue); / remove a process from s.qu

34、eue ,3.4.3 信号量机制,71,信号量的应用,1. 利用信号量实现进程互斥多个进程互斥地访问某临界资源，只需为该资源设置互斥信号量mutex，并设其初始值为1，然后将各进程访问该资源的临界区置于wait(mutex)和signal(mutex)操作之间即可。,Semaphore mutex = 1; PA() while(1) wait(mutex); 临界区 signal(mutex); 剩余区 ,PB () while(1) wait(mutex); 临界区 signal(mutex); 剩余区 ,2. 利用信号量实现前趋关系还可利用信号量来描述程序或语句之间的前趋关系。设有两个并

35、发执行的进程P1和P2。P1中有语句S1；P2中有语句S2。我们希望在S1执行后再执行S2。为实现这种前趋关系，只需使进程P1和P2共享一个公用信号量S，并赋予其初值为0，将signal(S)操作放在语句S1后面，而在S2语句前面插入wait(S)操作，即 在进程P1中，用S1；signal(S)；在进程P2中，用wait(S)；S2；,信号量的应用,由于S被初始化为0，这样，若P2先执行必定阻塞，只有在进程P1执行完S1； signal(S)；操作后使S增为1时，P2进程方能成功执行语句S2。同样，我们可以利用信号量按照语句间的前趋关系(见下图)，写出一个更为复杂的可并发执行的程序。,代码框

36、架： p1()S1;signal(a);signal(b); p2()wait(a);S2;signal(c);signal(d); p3()wait(b);S3;signal(e); p4()wait(c);S4;signal(f); p5()wait(d);S5;signal(g); p6()wait(e);wait(f);wait(g); S6; main() semaphore a,b,c,d,e,f,g; a.value = b.value = c.value = 0; d.value = e.value = f.value =0; g.value = 0; parbegin(p1,

37、p2,p3,p4,p5,p6); ,(1) 设置信号量a,b保证S1S2和S1S3的前趋关系；(2) 设置信号量c,d,e,f,g保证S2S4 、S2S5 、S3S6、 S4S6 和S5S6的前趋关系。(3) 以上信号量初始设为0。,1.管程的定义 管程是由一个或多个过程、一个初始化序列和数据组成的软件模块，是一种程序设计语言结构成分，具有和信号量同等的表达能力。进程可以通过调用管程实现对资源的请求和释放。,3.4.4 管程,76,管程的主要特点： 共享性：一个进程通过调用管程的一个过程进入管程，管程中的移出过程可被所有要调用管程的过程的进程所共享。 安全性：管程的局部数据变量只能被管程的过程

38、访问，任何其它外部过程都不能访问，一个管程的过程也不能访问任何非局部于它的变量。 互斥性：在任一时刻，只能有一个进程能够进入管程执行，调用管程的其它任何进程都将被阻塞，只能等待直到当前访问进程退出管程。,3.4.4 管程,77,2.管程的条件变量 在管程的调用过程中，存在如下的现象：一个进程调用了管程，并且它在管程中处于阻塞或挂起状态，当进程解除阻塞或挂起的条件满足后才能恢复执行。 引入条件变量（Condition variables）的同步机制，以及对应的两个原语操作cwait和csignal。,3.4.4 管程,78,cwait和csignal操作意义： （1）cwait(c)操作：正在调

39、用管程过程的进程因条件c没有满足而被阻塞或者挂起，则调用cwait操作将自己插入到条件变量c的等待进程队列中。与此同时，被阻塞进程释放管程，直到条件c发生改变，其它进程可以调用管程。 （2）csignal(c)操作：正在调用管程的进程检测到条件c发生了改变，则调用csignal操作重新唤醒一个因条件c而被阻塞或者挂起的进程。如果等待进程队列中有多个进程，则选择其中一个唤醒，否则继续执行原进程。,3.4.4 管程,79,1.生产者-消费者问题 （1）问题描述 假设有n个生产者和m个消费者，连接在一个有k个公用缓冲区的有界缓冲上，pi表示生产者进程，cj表示消费者进程。 满足： 只要缓冲区未满，生

40、产者pi即可将生产的产品放 入空闲缓冲区中 只要缓冲区不为空，消费者进程cj就可从缓冲区从取走并消耗产品,3.4.5 经典同步问题,80,（2） 用信号量解决生产者-消费者问题 利用互斥信号量mutex实现多个进程对公用缓冲区的互斥使用，初始化为1 利用信号量empty和full分别记录公用缓冲区中空缓冲区和满缓冲区的个数，分别初始化为k和0。,3.4.5 经典同步问题,81,void consumer() while(TRUE) wait(full); wait(mutex); nextc = buffernextout; nextout = (nextout + 1) % k; signa

41、l(mutex); signal(empty); /consume the item in nextc; void main() parbegin (producer, consumer); ,int nextin = 0, nextout = 0; item bufferk; semaphore mutex = 1, empty = k, full = 0; void producer() while(TRUE) /produce an item in nextp; wait(empty); wait(mutex); buffernextin = nextp; nextin = (nexti

42、n + 1) % k; signal(mutex); signal(full); ,（2） 用信号量解决生产者-消费者问题,void consumer() while(TRUE) wait(full); wait(mutex); nextc = buffernextout; nextout = (nextout + 1) % k; signal(mutex); signal(empty); /consume the item in nextc; void main() parbegin (producer, consumer); ,int nextin = 0, nextout = 0; it

43、em bufferk; semaphore mutex = 1, empty = k, full = 0; void producer() while(TRUE) /produce an item in nextp; wait(empty); wait(mutex); buffernextin = nextp; nextin = (nextin + 1) % k; signal(mutex); signal(full); ,（2） 用信号量解决生产者-消费者问题,等待空闲的缓冲区,互斥使用缓冲池,等待满的缓冲区,互斥使用缓冲池, wait(empty)能否和 wait(mutex)交换位置？

44、wait(full)能否和 wait(mutex)交换位置？,注意： 每个程序中控制对资源的互斥访问的wait(mutex)和signal(mutex)的操作原语必须成对出现。 对记录资源的信号量empty和full的wait和signal操作也必须成对出现，并且它们出现在不同的过程中。 为避免死锁，控制互斥访问和记录资源的信号量的wait操作顺序不能乱，必须先执行wait(empty)，再执行wait(mutex)。,3.4.5 经典同步问题,84,（3） 用管程解决生产者-消费者问题 首先需要建立一个管程ProducerConsumer，控制着用于保存和取回产品的公用缓冲区 定义变量cou

45、nt用于记录缓冲区中已有的产品数目 生产者通过append过程往缓冲区中保存产品，消费者通过take过程从缓冲区中取出产品消费 当缓冲区中产品已满时，生产者必须等待，当缓冲区中没有产品时，消费者必须等待,3.4.5 经典同步问题,85,void take(char x) if (count = 0) cwait(notempty); x = buffernextout; nextout = (nextout + 1) % k; count-; csignal(notfull); nextin = 0; nextout = 0; count = 0; ,管程模块PC描述如下： Monitor P

46、roducerConsumer char bufferk; int nextin, nextout; int count; condition notfull, notempty; void append(char x) if (count = k) cwait(notfull); buffernextin = x; nextin = (nextin + 1) % k; count+; csignal(notempty); ,（3） 用管程解决生产者-消费者问题,生产者和消费者分别描述如下： void producer() char x; while(TRUE) / produce an it

47、em in nextp; append(x); ,void consumer() char x; while(TRUE) take(x); / consume the item in nextc; void main() parbegin (producer,consumer); ,2.读者-写者问题 （1）问题描述 有一个多个进程共享的数据区，我们把只要读该数据区的进程记为Reader进程（读者），把只要往数据区中写数据的进程记为Writer进程（写者）。满足： 允许多个读者同时执行读操作 一次只能有一个写者可以执行写操作 如果一个写者在执行写操作，则其它任何读者都不能执行读操作,3.4.5

48、 经典同步问题,88,（2） 用信号量解决读者-写者问题 利用互斥信号量wmutex实施读者与写者在读写时的互斥， 设置整型变量readercount用于记录正在读的进程个数 计数变量readercount本身是可以被多个读者访问的临界资源，设置互斥信号量mutex控制多个读者对readercount的修改,3.4.5 经典同步问题,89,if (readcount = 0) signal(wmutex); signal(mutex); void writer() while(TRUE) wait(wmutex); / write operation signal(wmutex); void

49、main() parbegin (reader, writer); ,读者-写者问题描述如下 semaphore mutex = 1, wmutex = 1; int readercount = 0; void reader() while(TRUE) wait(mutex); if (readcount = 0) wait(wmutex); readercount+; signal(mutex); / read operation wait(mutex); readercount-;,表示来的是第一个读者，需要等待用于控制读写互斥的wmutex信号量。,表示最后一个读者离开，需要释放用于控制

50、读写互斥的wmutex信号量。,（2） 用信号量解决读者-写者问题,3.哲学家就餐问题,3.4.5 经典同步问题,91,图3.13 哲学家就餐问题,（1）问题描述 有五位哲学家，用一生来思考和吃饭。他们围坐在一张圆桌旁边，桌子中央有一大碗米饭，桌上还有五个碗和五只筷子，他们的生活方式是交替地进行思考和进餐。平时，当某位哲学家进行思考时，他不与其它哲学家交互。当他感觉到饥饿时，便试图拿起与其左右最靠近他的筷子。满足： 一个哲学家每次只能拿起一只筷子，且他不能从其他哲学家手里拿筷子 只有在他拿到两只筷子时才能进餐,3.4.5 经典同步问题,92,（2） 用信号量解决哲学家就餐问题 每一只筷子的使用

51、都必须是互斥的，在某一时刻只允许一个哲学家使用 利用一个信号量表示一只筷子，五只筷子的信号量数组定义为semaphore chopstick5,3.4.5 经典同步问题,93,信号量解决哲学家就餐问题描述如下： semaphore chopstick5 = 1,1,1,1,1; int i; void philosopher (int i) while(TRUE) / think wait(chopsticki); wait(chopstick(i+1) % 5); / eat signal(chopstick(i+1) % 5); signal(chopsticki); void main(

52、) parbegain (philosopher(0), philosopher(1), philosopher(2), philosopher(3), philosopher(4);,94,可能出现死锁： 当五位哲学家都感到饥饿并都同时拿起了自己左边的筷子，又都伸手去拿右边的筷子的时，会发现右边的筷子都没有了。 一种解决方法是仅当哲学家左、右两边的筷子都能拿时才允许该哲学家拿起筷子就餐； 另一种解决方法是增加一位服务员，他最多只允许四位哲学家同时进入餐厅就餐，这就至少能保证有一位哲学家能同时拿起左、右两根筷子。,3.4.5 经典同步问题,95,补充：AND型信号量 前面我们所介绍的问题针对的

53、是多个并发进程仅共享一个临界资源的情况。在有些应用场合，一个进程往往需要获得两个或两个以上的共享资源后方能继续执行。 AND型同步机制的基本思想：将进程在整个运行过程中所需要的所有资源一次性全部分配给进程，待进程使用完之后再一起释放。只要尚有一个资源未能分配给进程，其它所有可能为之分配的资源也不分配给它。,3.4.5 经典同步问题,96,补充：AND型信号量 这样，对若干个临界资源的分配采取原子操作方式：要么，把它所请求的资源全部分配给进程；要么一个也不分配。 在wait操作中增加了一个“AND”条件，故称为AND同步，或称为同时wait操作。Swait(Simultaneous wait)定

54、义为：,3.4.5 经典同步问题,97,Swait(S1,S2,Sn) while(TRUE) if(Si=1 else place the process in the waiting queue associated with the first Si found with Si 1, and set the program count of this process to the beginning of Swait operation ,98,Ssignal(S1,S2,Sn) while(TRUE) for(i=1; i=n; i+) Si+; Remove all the proc

55、ess waiting in the queue associated with Si into the ready queue ,利用AND信号量机制解决哲学家进餐问题，避免死锁,99,semaphore chopstick chopstick5 = 1,1,1,1,1; do /think Swait(chopsticki , chopstick(i+1) % 5); /eat Ssignal(chopstick(i+1) % 5, chopsticki); while(TRUE);,semaphore chopstick5 = 1,1,1,1,1; semaphore room = 4;

56、 int i; void philosopher (int i) while(TRUE) / think wait(room); wait(chopsticki); wait(chopstick(i+1) % 5); / eat signal(chopstick(i+1) % 5); signal(chopsticki); signal(room); void main() parbegain (philosopher(0), philosopher(1), philosopher(2), philosopher(3), philosopher(4);,100,利用服务员限制进入人数解决哲学家

57、进餐问题，避免死锁,1.消息传递的概念 消息传递（Message passing）作为当前应用最为广泛的一种进程间通信机制，为进程间信息传递和交换的实现提供了很好的保障 消息是一组信息，由消息头和消息体组成。 send(destination, message) receive(source, message),3.4.6 消息传递,101,2.同步 阻塞send：发送进程阻塞，直到消息被接收进程接收 非阻塞send：发送进程发送消息并再继续操作 阻塞receive：接收者阻塞直到请求的消息到达 非阻塞receive：接收者收到一条有效消息或一条空消息 组合形式： 阻塞send，阻塞receive 非阻塞send，阻塞receive 非阻塞send，非阻塞receive,3.4.6 消息传递,102,3.寻址方式 （1）直接寻址（Direct addressing）方式 （2）间接寻址（Indirect addressing）方式 在间接选址方式下，消息传递并不是在发送进程和接收进程之间直接进行，而是通过一个被称为信箱（Mail