西安电子科技大学出版社操作系统第2章进程管理.ppt

《西安电子科技大学出版社操作系统第2章进程管理.ppt》由会员分享，可在线阅读，更多相关《西安电子科技大学出版社操作系统第2章进程管理.ppt（152页珍藏版）》请在金锄头文库上搜索。

1、计算机操作系统计算机操作系统Operating System 第二章第二章 进程管理进程管理 2.1 2.1 进程的基本概念进程的基本概念 2.2 2.2 进程控制进程控制 2.3 2.3 进程同步进程同步 2.4 2.4 经典进程的同步问题经典进程的同步问题 2.5 2.5 管程机制管程机制 2.6 2.6 进程通信进程通信 2.7 2.7 线程线程 本章主要内本章主要内容容2024/7/222024/7/22计算机科学系计算机科学系计算机操作系统计算机操作系统Operating System 2.1 进程的基本概念进程的基本概念 2.1.1 程序的顺序执行及其特征程序的顺序执行及其特征 1

2、. 程序的顺序执行程序的顺序执行 仅当前一操作(程序段)执行完后，才能执行后继操作。例如，在进行计算时，总须先输入用户的程序和数据，然后进行计算，最后才能打印计算结果。2024/7/222024/7/22计算机科学系计算机科学系计算机操作系统计算机操作系统Operating System 图 2-1 程序的顺序执行 S1: a=x+y; S2: b=a-5; S3: c=b+1;2024/7/222024/7/22计算机科学系计算机科学系计算机操作系统计算机操作系统Operating System 2. 程序顺序执行时的特征程序顺序执行时的特征 (1)顺序性：(2)(2) 封闭性： (3)(3

3、) 可再现性： 2024/7/222024/7/22计算机科学系计算机科学系计算机操作系统计算机操作系统Operating System 2.1.2 前趋图前趋图 前趋图(Precedence Graph)是一个有向无循环图，记为DAG(Directed Acyclic Graph)，用于描述进程之间执行的前后关系。图中的每个结点可用于描述一个程序段或进程，乃至一条语句；结点间的有向边则用于表示两个结点之间存在的偏序(Partial Order)或前趋关系(Precedence Relation)“”。 =(Pi, Pj)|Pi must complete before Pj may star

4、t, 如果(Pi, Pj),可写成PiPj，称Pi是Pj的直接前趋，而称Pj是Pi的直接后继。在前趋图中，把没有前趋的结点称为初始结点(Initial Node)，把没有后继的结点称为终止结点(Final Node)。2024/7/222024/7/22计算机科学系计算机科学系计算机操作系统计算机操作系统Operating System 每个结点还具有一个重量(Weight)，用于表示该结点所含有的程序量或结点的执行时间。 图 2-2 前趋图 2024/7/222024/7/22计算机科学系计算机科学系计算机操作系统计算机操作系统Operating System 对于图 2-2(a)所示的前趋

5、图， 存在下述前趋关系： P1P2, P1P3, P1P4, P2P5, P3P5, P4P6, P4P7, P5P8, P6P8, P7P9, P8P9或表示为： P=P1, P2, P3, P4, P5, P6, P7, P8, P9 = (P1, P2), (P1, P3), (P1, P4), (P2, P5), (P3, P5), (P4, P6), (P4, P7), (P5, P8), (P6, P8), (P7, P9), (P8, P9) 应当注意，前趋图中必须不存在循环，但在图2-2(b)中却有着下述的前趋关系： S2S3, S3S2 2024/7/222024/7/22计

6、算机科学系计算机科学系计算机操作系统计算机操作系统Operating System 2.1.3 程序的并发执行及其特征程序的并发执行及其特征 1. 程序的并发执行程序的并发执行 图 2-3 并发执行时的前趋图 2024/7/222024/7/22计算机科学系计算机科学系计算机操作系统计算机操作系统Operating System 在该例中存在下述前趋关系： IiCi，IiIi+1, CiPi, CiCi+1，PiPi+1而Ii+1和Ci及Pi-1是重迭的，亦即在Pi-1和Ci以及Ii+1之间，可以并发执行。2024/7/222024/7/22计算机科学系计算机科学系计算机操作系统计算机操作系统

7、Operating System 图 2-4 四条语句的前趋关系对于具有下述四条语句的程序段： S1: a=x+2 S2: b=y+4 S3: c=a+b S4: d=c+b 2024/7/222024/7/22计算机科学系计算机科学系计算机操作系统计算机操作系统Operating System 2. 程序并发执行时的特征程序并发执行时的特征 1)间断性2)2) 失去封闭性 3)3) 不可再现性 例如，有两个循环程序A和B，它们共享一个变量N。程序A每执行一次时，都要做N=N+1操作；程序B每执行一次时， 都要执行Print(N)操作，然后再将N置成“0”。程序A和B以不同的速度运行。 (1)

8、 N=N+1在Print(N)和N=0之前，此时得到的N值分别为n+1, n+1, 0。 (2) N=N+1在Print(N)和N=0之后，此时得到的N值分别为n, 0, 1。 (3) N=N+1在Print(N)和N=0之间，此时得到的N值分别为n, n+1, 0。 2024/7/222024/7/22计算机科学系计算机科学系计算机操作系统计算机操作系统Operating System 2.1.4 进程的特征与状态进程的特征与状态 1. 进程的特征和定义进程的特征和定义结构特征结构特征(程序段、数据段和进程控制块PCB)动态性动态性 （最基本的特征，与程序的区别）并发性并发性（重要特征）独立

9、性独立性 （运行，分配资源，调度）异步性异步性2024/7/222024/7/22计算机科学系计算机科学系计算机操作系统计算机操作系统Operating System 较典型的进程定义有： (1) 进程是程序的一次执行。 (2) 进程是一个程序及其数据在处理机上顺序执行时所发生的活动。 (3) 进程是程序在一个数据集合上运行的过程，它是系统进行资源分配和调度的一个独立单位。 在引入了进程实体的概念后，本书把传统OS中的进程定义为：“进程是进程实体的运行过程，是系统进行资源分配和调度的一个独立单位”。 2024/7/222024/7/22计算机科学系计算机科学系计算机操作系统计算机操作系统Ope

10、rating System 进程与程序的区别： (1) 程序是指令的有序集合，其本身没有任何运行的含义，程序是指令的有序集合，其本身没有任何运行的含义，是一个是一个静态静态的概念。而进程是程序在处理机上的一次执行的概念。而进程是程序在处理机上的一次执行过程，它是一个过程，它是一个动态动态的概念。的概念。(2) 程序可以作为一种软件资料长期存在，而进程是有一程序可以作为一种软件资料长期存在，而进程是有一定生命期的。程序是定生命期的。程序是永久永久的，进程是的，进程是暂时暂时的。的。(3) 进程更能真实地描述并发，而程序不能进程更能真实地描述并发，而程序不能(4) 程序是进程的组成部分程序是进程的

11、组成部分(5) 进程具有创建其他进程的功能，而程序没有进程具有创建其他进程的功能，而程序没有(6) 同一程序同时运行于若干个数据集合上，它将属于若同一程序同时运行于若干个数据集合上，它将属于若干个不同的进程。也就是说干个不同的进程。也就是说同一程序可以对应多个进程同一程序可以对应多个进程 2024/7/222024/7/22计算机科学系计算机科学系计算机操作系统计算机操作系统Operating System 思考？思考？为什么引入进程？为什么引入进程？2024/7/222024/7/22计算机科学系计算机科学系计算机操作系统计算机操作系统Operating System 2. 进程的三种基本状

12、态进程的三种基本状态 (1)就绪(Ready)状态 (2)执行状态 (3) 阻塞状态 2024/7/222024/7/22计算机科学系计算机科学系计算机操作系统计算机操作系统Operating System 图 2-5 进程的三种基本状态及其转换 2024/7/222024/7/22计算机科学系计算机科学系计算机操作系统计算机操作系统Operating System 3. 挂起状态挂起状态 1)引入挂起状态的原因：引入挂起状态的原因： (1)终端用户的请求；(2)父进程请求；(3)负荷调节的需要；(4)操作系统的需要；(5)对换需要。(6)挂起状态实际是暂时从内存中被淘汰出去的进程。2024/

13、7/222024/7/22计算机科学系计算机科学系计算机操作系统计算机操作系统Operating System 2) 进程状态的转换 (1)活动就绪静止就绪。 (2)(2) 活动阻塞静止阻塞。 (3)(3) 静止就绪活动就绪。 (4)(4) 静止阻塞活动阻塞。 2024/7/222024/7/22计算机科学系计算机科学系计算机操作系统计算机操作系统Operating System 具有挂起状态的进程状态图 2024/7/222024/7/22计算机科学系计算机科学系计算机操作系统计算机操作系统Operating System 2 2五状态进程模型五状态进程模型 引入创建状态和终止状态 （1）创

14、建状态作用 （2）终止状态作用等待条件满足2024/7/222024/7/22计算机科学系计算机科学系计算机操作系统计算机操作系统Operating System 3 3挂起状态进程模型（挂起状态进程模型（）单挂起状态进程模型单挂起状态进程模型2024/7/222024/7/22计算机科学系计算机科学系计算机操作系统计算机操作系统Operating System 3 3挂起状态进程模型（挂起状态进程模型（）双挂起状态进程模型双挂起状态进程模型2024/7/222024/7/22计算机科学系计算机科学系计算机操作系统计算机操作系统Operating System 思考？思考？1如果系统中有如果系

15、统中有N个进程，运行的进程最多几个，最个进程，运行的进程最多几个，最少几个；就绪进程最多几个最少几个；等待进程最少几个；就绪进程最多几个最少几个；等待进程最多几个，最少几个？多几个，最少几个？2. 有没有这样的状态转换，为什么？有没有这样的状态转换，为什么？ 等待等待运行；运行； 就绪就绪等待等待2024/7/222024/7/22计算机科学系计算机科学系计算机操作系统计算机操作系统Operating System 课堂练习课堂练习l当某个作业被作业调度程序选中，进入内存开始运行时，作业的状态为：.提交状态.完成状态.执行状态.就绪状态l进程在发出I/O请求后，可能导致下列哪种进程状态演变？A

16、.就绪执行B.执行就绪C.阻塞执行D.执行阻塞l单处理机系统中，可并行的是I进程与进程II处理机与设备III处理机与通道IV设备与设备AI、II和IIIB.I、II和IVC.I、III和IVD.II、III和IV2024/7/222024/7/22计算机科学系计算机科学系计算机操作系统计算机操作系统Operating System 2.1.5 进程控制块进程控制块 1. 进程控制块的作用进程控制块的作用 进程控制块的作用是使一个在多道程序环境下不能独立运行的程序(含数据)，成为一个能独立运行的基基本本单单位位，一个能与其它进程并发执行的进程。或者说，OS是根据PCB来对并发执行的进程进行控制和

17、管理的。 为了描述一个进程和其它进程以及系统资源的关系，为了刻画一个进程在各个不同时期所处的状态，人们采用了一个与进程相联系的数据块，称为进程控制块（进程控制块（PCB）。）。系统利用PCB来控制和管理控制和管理进程，所以PCB是系统感知进感知进程存在的唯一标志。程存在的唯一标志。 进程与进程与PCB是一一对应的。是一一对应的。2024/7/222024/7/22计算机科学系计算机科学系计算机操作系统计算机操作系统Operating System 2. 进程控制块中的信息进程控制块中的信息 1) 进程标识符进程标识符 进进程程标标识识符符用于惟惟一一地地标标识识一个进程。一个进程通常有两种标识

18、符： (1) 内部标识符。在所有的操作系统中，都为每一个进 程赋予一个惟一的数字标识符，它通常是一个进程的序号。 设置内部标识符主要是为了方便系统使用。 (2) 外部标识符。它由创建者提供，通常是由字母、数字组成，往往是由用户(进程)在访问该进程时使用。为了描述进程的家族关系， 还应设置父进程标识及子进程标识。此外，还可设置用户标识，以指示拥有该进程的用户。 2024/7/222024/7/22计算机科学系计算机科学系计算机操作系统计算机操作系统Operating System 2) 处理机状态处理机状态 处理机状态信息主要是由处理机的各种寄存器中的内容组成的。 通通用用寄寄存存器器，又称为用

19、户可视寄存器，它们是用户程序可以访问的，用于暂存信息， 在大多数处理机中，有 832 个通用寄存器，在RISC结构的计算机中可超过 100 个； 指指令令计计数数器器，其中存放了要访问的下一条指令的地址； 程程序序状状态态字字PSW，其中含有状态信息，如条件码、执行方式、 中断屏蔽标志等； 用用户户栈栈指指针针， 指每个用户进程都有一个或若干个与之相关的系统栈，用于存放过程和系统调用参数及调用地址。栈指针指向该栈的栈顶。 2024/7/222024/7/22计算机科学系计算机科学系计算机操作系统计算机操作系统Operating System 3) 进程调度信息进程调度信息 在PCB中还存放一些

20、与进程调度和进程对换有关的信息，包括： 进进程程状状态态，指明进程的当前状态， 作为进程调度和对换时的依据； 进进程程优优先先级级，用于描述进程使用处理机的优先级别的一个整数， 优先级高的进程应优先获得处理机； 进进程程调调度度所所需需的的其其它它信信息息，它们与所采用的进程调度算法有关，比如，进程已等待CPU的时间总和、 进程已执行的时间总和等； 事事件件，是指进程由执行状态转变为阻塞状态所等待发生的事件，即阻塞原因。 2024/7/222024/7/22计算机科学系计算机科学系计算机操作系统计算机操作系统Operating System 4) 进程控制信息进程控制信息 进程控制信息包括：

21、程程序序和和数数据据的的地地址址， 是指进程的程序和数据所在的内存或外存地(首)址，以便再调度到该进程执行时，能从PCB中找到其程序和数据； 进进程程同同步步和和通通信信机机制制，指实现进程同步和进程通信时必需的机制， 如消息队列指针、信号量等，它们可能全部或部分地放在PCB中； 资资源源清清单单，是一张列出了除CPU以外的、进程所需的全部资源及已经分配到该进程的资源的清单； 链链接接指指针针， 它给出了本进程(PCB)所在队列中的下一个进程的PCB的首地址。 2024/7/222024/7/22计算机科学系计算机科学系计算机操作系统计算机操作系统Operating System 3. 进程控

22、制块的组织方式进程控制块的组织方式 1) 链接方式 PCB链接队列示意图 2024/7/222024/7/22计算机科学系计算机科学系计算机操作系统计算机操作系统Operating System 2) 索引方式 按索引方式组织PCB 2024/7/222024/7/22计算机科学系计算机科学系计算机操作系统计算机操作系统Operating System 2.2 进进 程程 控控 制制 进程控制是进程管理中最基本的功能。它用于创建一个新进程，终止一个已完成的进程，或终止一个因出现某事件而使其无法运行下去的进程，还可负责进程运行中的状态转换。进程控制就是对系统中的所有进程实施管理，进程控制一般有原

23、语来实现。 所谓原语所谓原语是一种特殊的系统功能调用，它可以完成一个特定的功能，其特点其特点是原语执行是原语执行时不可被中断，时不可被中断，其作用是为了实现进程的其作用是为了实现进程的通信和控制。通信和控制。 常用原语：常用原语：创建原语创建原语终止原语终止原语阻塞原语、唤醒原语阻塞原语、唤醒原语2024/7/222024/7/22计算机科学系计算机科学系计算机操作系统计算机操作系统Operating System 2.2 进进 程程 控控 制制 2.2.1 进程的创建进程的创建 1. 进程图(Process Graph) 进程树 2024/7/222024/7/22计算机科学系计算机科学系计

24、算机操作系统计算机操作系统Operating System 2. 引起创建进程的事件引起创建进程的事件 (1)用户登录。 (2)(2) 作业调度。 (3)(3) 提供服务。 （文件打印）(4)(4) 应用请求。 （输入，处理，打印）系统内核用户自己2024/7/222024/7/22计算机科学系计算机科学系计算机操作系统计算机操作系统Operating System 3. 进程的创建进程的创建(Creation of Progress) (1)申请空白PCB。 (2) 为新进程分配资源。 (3) 初始化进程控制块。 (4) 将新进程插入就绪队列，如果进程就绪队列能够接纳新进程， 便将新进程插入

25、就绪队列。 2024/7/222024/7/22计算机科学系计算机科学系计算机操作系统计算机操作系统Operating System 2.2.2 进程的终止进程的终止 1. 引起进程终止引起进程终止(Termination of Process)的事件的事件 1) 正常结束 在任何计算机系统中，都应有一个用于表示进程已经运行完成的指示。例如，在批处理系统中，通常在程序的最后安排一条Halt指令或终止的系统调用。当程序运行到Halt指令时，将产生一个中断，去通知OS本进程已经完成。2024/7/222024/7/22计算机科学系计算机科学系计算机操作系统计算机操作系统Operating Syst

26、em 2) 异常结束 在进程运行期间，由于出现某些错误和故障而迫使进程终止。这类异常事件很多，常见的有：l越界错误l保护错l非法指令l特权指令错l运行超时l等待超时l算术运算错lI/O故障2024/7/222024/7/22计算机科学系计算机科学系计算机操作系统计算机操作系统Operating System 3) 外界干预 外界干预并非指在本进程运行中出现了异常事件，而是指进程应外界的请求而终止运行。这些干预有： l 操作员或操作系统干预l 父进程请求l父进程终止 2024/7/222024/7/22计算机科学系计算机科学系计算机操作系统计算机操作系统Operating System 2. 进

27、程的终止过程进程的终止过程 (1) 根据被终止进程的标识符，从PCB集合中检索出该进程的PCB，从中读出该进程的状态。 (2) 若被终止进程正处于执行状态，应立即终止该进程的执行，并置调度标志为真，用于指示该进程被终止后应重新进行调度。 (3) 若该进程还有子孙进程，还应将其所有子孙进程予以终止，以防他们成为不可控的进程。 (4) 将被终止进程所拥有的全部资源，或者归还给其父进程， 或者归还给系统。 (5) 将被终止进程(它的PCB)从所在队列(或链表)中移出， 等待其他程序来搜集信息。 2024/7/222024/7/22计算机科学系计算机科学系计算机操作系统计算机操作系统Operating

28、 System 2.2.3 进程的阻塞与唤醒进程的阻塞与唤醒1. 引起进程阻塞和唤醒的事件引起进程阻塞和唤醒的事件 1)请求系统服务2) 启动某种操作3)新数据尚未到达4)无新工作可做 2024/7/222024/7/22计算机科学系计算机科学系计算机操作系统计算机操作系统Operating System 2. 进程阻塞过程进程阻塞过程 正在执行的进程，当发现上述某事件时，由于无法继续执行，于是进程便通过调用阻塞原语block把自己阻塞。可见，进程的阻塞是进程自身的一种主动行为。进入block过程后，由于此时该进程还处于执行状态，所以应先立即停止执行，把进程控制块中的现行状态由“执行”改为阻塞

29、，并将PCB插入阻塞队列。如果系统中设置了因不同事件而阻塞的多个阻塞队列，则应将本进程插入到具有相同事件的阻塞(等待)队列。 最后，转调度程序进行重新调度，将处理机分配给另一就绪进程，并进行切换，亦即，保留被阻塞进程的处理机状态(在PCB中)，再按新进程的PCB中的处理机状态设置CPU的环境。 2024/7/222024/7/22计算机科学系计算机科学系计算机操作系统计算机操作系统Operating System 3. 进程唤醒过程进程唤醒过程 当被阻塞进程所期待的事件出现时，如I/O完成或其所期待的数据已经到达，则由有关进程(比如，用完并释放了该I/O设备的进程)调用唤醒原语wakeup(

30、)，将等待该事件的进程唤醒。唤醒原语执行的过程是：首先把被阻塞的进程从等待该事件的阻塞队列中移出，将其PCB中的现行状态由阻塞改为就绪，然后再将该PCB插入到就绪队列中。 2024/7/222024/7/22计算机科学系计算机科学系计算机操作系统计算机操作系统Operating System 2.2.4 进程的挂起与激活进程的挂起与激活 1. 进程的挂起进程的挂起 当出现了引起进程挂起的事件时，比如，用户进程请求将自己挂起，或父进程请求将自己的某个子进程挂起， 系统将利用挂起原语suspend( )将指定进程或处于阻塞状态的进程挂起。挂起原语的执行过程是：首先检查被挂起进程的状态，若处于活动就

31、绪状态，便将其改为静止就绪；对于活动阻塞状态的进程，则将之改为静止阻塞。 为了方便用户或父进程考查该进程的运行情况而把该进程的PCB复制到某指定的内存区域。最后，若被挂起的进程正在执行，则转向调度程序重新调度。 2024/7/222024/7/22计算机科学系计算机科学系计算机操作系统计算机操作系统Operating System 2. 进程的激活过程进程的激活过程 当发生激活进程的事件时，例如，父进程或用户进程请求激活指定进程，若该进程驻留在外存而内存中已有足够的空间时，则可将在外存上处于静止就绪状态的进程换入内存。这时，系统将利用激活原语active( )将指定进程激活。 激活原语先将进程

32、从外存调入内存，检查该进程的现行状态，若是静止就绪，便将之改为活动就绪；若为静止阻塞便将之改为活动阻塞。假如采用的是抢占调度策略，则每当有新进程进入就绪队列时，应检查是否要进行重新调度，即由调度程序将被激活进程与当前进程进行优先级的比较，如果被激活进程的优先级更低，就不必重新调度；否则，立即剥夺当前进程的运行，把处理机分配给刚被激活的进程。 2024/7/222024/7/22计算机科学系计算机科学系计算机操作系统计算机操作系统Operating System 课堂练习课堂练习l24、下列选项中，导致创进新进程的操作是（C）I用户成功登陆II设备分配III启动程序执行A：仅I和IIB：仅II和

33、IIIC：仅I和IIID：I，II，III2024/7/222024/7/22计算机科学系计算机科学系计算机操作系统计算机操作系统Operating System 思考？思考？为什么创建进程要用原语来为什么创建进程要用原语来实现？实现？ 2 阻塞进程在什么情况下会被唤醒？谁来唤阻塞进程在什么情况下会被唤醒？谁来唤醒它？醒它？2024/7/222024/7/22计算机科学系计算机科学系计算机操作系统计算机操作系统Operating System 2.3 进进 程程 同同 步步 2.3.1 进程同步的基本概念进程同步的基本概念 1. 两种形式的制约关系两种形式的制约关系 (1)间接相互制约关系。

34、(2)(2) 直接相互制约关系。 2024/7/222024/7/22计算机科学系计算机科学系计算机操作系统计算机操作系统Operating System 2. 临界资源临界资源(Critical Resouce) 生产者-消费者(producer-consumer)问题是一个著名的进程同步问题。它描述的是：有一群生生产产者者进进程程在生产产品，并将这些产品提供给消消费费者者进程进程去消费。 为使生产者进程与消费者进程能并发执行，在两者之间设置了一个具有n个个缓缓冲冲区区的的缓缓冲冲池池，生产者进程将它所生产的产品放入一个缓冲区中； 消费者进程可从一个缓冲区中取走产品去消费。 尽管所有的生产者

35、进程和消费者进程都是以异步方式运行的，但它们之间必必须须保保持持同同步步，即不允许消费者进程到一个空缓冲区去取产品；也不允许生产者进程向一个已装满产品且尚未被取走的缓冲区中投放产品。 2024/7/222024/7/22计算机科学系计算机科学系计算机操作系统计算机操作系统Operating System 我们可利用一个数组来表示上述的具有n个(0，1，n-1)缓冲区的缓冲池。用输输入入指指针针in来指示下一个可投放产品的缓冲区，每当生产者进程生产并投放一个产品后，输入指针加1；用一个输输出出指指针针out来指示下一个可从中获取产品的缓冲区，每当消费者进程取走一个产品后，输出指针加1。 由于这里

36、的缓冲池是组织成循循环环缓缓冲冲的，故应把输入指针加1表示成 in=(in+1)mod n；输出指针加1表示成out=(out+1) mod n。当(in+1) mod n=out时表示缓冲池满；而in=out则表示缓冲池空。2024/7/222024/7/22计算机科学系计算机科学系计算机操作系统计算机操作系统Operating System 此外，还引入了一个整型变量counter,其初始值为0。每当生产者进程向缓冲池中投放一个产品后，使counter加1；反之，每当消费者进程从中取走一个产品时，使counter减1。2024/7/222024/7/22计算机科学系计算机科学系计算机操作系

37、统计算机操作系统Operating System 生产者和消费者两进程共享下面的变量：var n, integer; type item=; var buffer:array0, 1, , n-1 of item; in, out: 0, 1, , n-1; counter: 0, 1, , n; 指针in和out初始化为1。在生产者和消费者进程的描述中，no-op是一条空操作指令，while condition do no-op语句表示重复的测试条件(condication)，重复测试应进行到该条件变为false(假)，即到该条件不成立时为止。在生产者进程中使用一局部变量nextp，用于暂时

38、存放每次刚生产出来的产品；而在消费者进程中，则使用一个局部变量nextc,用于存放每次要消费的产品。 2024/7/222024/7/22计算机科学系计算机科学系计算机操作系统计算机操作系统Operating System producer: repeat produce an item in nextp; while counter=n do no-op; bufferin:=nextp; in= in+1 mod n; counter: = counter+1; until false; consumer: repeat while counter=0 do no-op; nextc =b

39、ufferout; out =(out+1) mod n; counter =counter-1; consumer the item in nextc; until false; 2024/7/222024/7/22计算机科学系计算机科学系计算机操作系统计算机操作系统Operating System 虽然上面的生产者程序和消费者程序，在分别看时都是正确的，而且两者在顺序执行时其结果也会是正确的，但若并发执行时，就会出现差错，问题就在于这两个进程共享变量counter。生产者对它做加1操作，消费者对它做减1操作，这两个操作在用机器语言实现时， 常可用下面的形式描述：register 1=cou

40、nter; register1=register 1+1; counter=register 1;register 2=counter;register 2=register 2-1; counter=register 2; 2024/7/222024/7/22计算机科学系计算机科学系计算机操作系统计算机操作系统Operating System 假设：counter的当前值是5。如果生产者进程先执行左列的三条机器语言语句，然后消费者进程再执行右列的三条语句， 则最后共享变量counter的值仍为5；反之，如果让消费者进程先执行右列的三条语句，然后再让生产者进程执行左列的三条语句，counter

41、值也还是5，但是，如果按下述顺序执行： register1=counter; (register1=5) register1=register1+1; (register1=6) register2=counter; (register2=5) register2 =register2-1; (register2=4) counter=register1; (counter=6) counter=register2; (counter=4) 2024/7/222024/7/22计算机科学系计算机科学系计算机操作系统计算机操作系统Operating System 3. 临界区临界区(critic

42、al section) 可把一个访问临界资源的循环进程描述如下： repeat critical section; remainder section; until false; entry sectionexit section2024/7/222024/7/22计算机科学系计算机科学系计算机操作系统计算机操作系统Operating System 4. 同步机制应遵循的规则同步机制应遵循的规则 (1)空闲让进。(2)(2) 忙则等待。 (3)(3) 有限等待。 (4)(4) 让权等待。 2024/7/222024/7/22计算机科学系计算机科学系计算机操作系统计算机操作系统Operating

43、 System 2.3.2 信号量机制信号量机制 1. 整型信号量整型信号量 最初由Dijkstra把整型信号量定义为一一个个整整型型量量，除初始化外，仅能通过两个标准的原原子子操操作作(Atomic Operation) wait(S)和和signal(S)来来访访问问。这两个操作一直被分别称为P、V操作。 wait和signal操作可描述为： wait(S): while S0 do no-op S=S-1; signal(S): S=S+1; (1) 原子操作(2) 忙等待2024/7/222024/7/22计算机科学系计算机科学系计算机操作系统计算机操作系统Operating Syst

44、em 2. 记录型信号量记录型信号量 在整型信号量机制中的wait操作，只要是信号量S0， 就会不断地测试。因此，该机制并并未未遵遵循循“让让权权等等待待”的准则， 而是使进程处于“忙忙等等”的状态。记录型信号量机制，则是一种不存在“忙等”现象的进程同步机制。但在采取了“让让权权等等待待”的策略后，又会出现多个进程等待访问同一临界资源的情况。为此，在信号量机制中，除了需要一个用于代表资源数目的整整型型变变量量value外，还应增加一个进进程程链链表表L，用于链接上述的所有等待进程。记录型信号量是由于它采用了记录型的数据结构而得名的。它所包含的上述两个数据项可描述为： 2024/7/222024

45、/7/22计算机科学系计算机科学系计算机操作系统计算机操作系统Operating System type semaphore=record value:integer; L:list of process; end 相应地，wait(S)和signal(S)操作可描述为： procedure wait(S) var S: semaphore; begin S.value =S.value-1; if S.value0 then block(S,L) end procedure signal(S) var S: semaphore; begin S.value =S.value+1; if S.

46、value0 then wakeup(S,L); end 2024/7/222024/7/22计算机科学系计算机科学系计算机操作系统计算机操作系统Operating System 在记录型信号量机制中，S.value的初值表示系统中某类资源的数目， 因而又称为资源信号量资源信号量。对它的每次wait操作，意味着进程请求一个单位的该类资源，因此描述为S.value=S.value-1；当S.value0时，表示该类资源已分配完毕，因此进程应调用block原语，进行自我阻塞，放弃处理机，并插入到信号量链表S.L中。可见，该机制遵循了“让权等待”准则。 此时S.value的绝对值表示在该信号量链表中

47、已阻塞进程的数目。 对信号量的每次signal操作，表示执行进程释放一个单位资源，故S.value=S.value+1操作表示资源数目加1。若加1后仍是S.value0，则表示在该信号量链表中，仍有等待该资源的进程被阻塞，故还应调用wakeup原语，将S.L链表中的第一个等待进程唤醒。如果S.value的初值为1，表示只允许一个进程访问临界资源，此时的信号量转化为互斥信号量。2024/7/222024/7/22计算机科学系计算机科学系计算机操作系统计算机操作系统Operating System 3. AND型信号量型信号量 在两个进程中都要包含两个对Dmutex和Emutex的操作， 即pro

48、cess A: process B: wait(Dmutex); wait(Emutex); wait(Emutex); wait(Dmutex); 若进程A和B按下述次序交替执行wait操作： process A: wait(Dmutex); 于是Dmutex=0 process B: wait(Emutex); 于是Emutex=0 process A: wait(Emutex); 于是Emutex=-1 A阻塞 process B: wait(Dmutex); 于是Dmutex=-1 B阻塞 2024/7/222024/7/22计算机科学系计算机科学系计算机操作系统计算机操作系统Oper

49、ating System AND同步机制的基基本本思思想想是：将进程在整个运行过程中需要的所有资源，一次性全部地分配给进程，待进程使用完后再一起释放。只要尚有一个资源未能分配给进程，其它所有可能为之分配的资源，也不分配给他。亦即，对若若干干个个临临界界资资源源的的分分配配，采采取取原原子子操操作作方方式式：要要么么全全部部分分配配到到进进程程，要要么么一一个个也也不不分分配配。 由死锁理论可知，这样就可避免上述死锁情况的发生。为此，在wait操作中，增加了一个“AND”条件，故称为AND同步，或称为同时wait操作， 即Swait(Simultaneous wait)定义如下： 2024/7/

50、222024/7/22计算机科学系计算机科学系计算机操作系统计算机操作系统Operating System Swait(S1, S2, , Sn) if Si1 and and Sn1 then for i =1 to n do Si=Si-1; endfor else place the process in the waiting queue associated with the first Si found with Si1, and set the program count of this process to the beginning of Swait operation en

51、dif Ssignal(S1, S2, , Sn) for i =1 to n do Si=Si+1; Remove all the process waiting in the queue associated with Si into the ready queue. endfor; 2024/7/222024/7/22计算机科学系计算机科学系计算机操作系统计算机操作系统Operating System 4. 信号量集信号量集 Swait(S1, t1, d1, , Sn, tn, dn) if Sit1 and and Sntn then for i=1 to n do Si=Si-di

52、; endfor else Place the executing process in the waiting queue of the first Si with Siti and set its program counter to the beginning of the Swait Operation. endif signal(S1, d1, , Sn, dn) for i=1 to n do Si =Si+di; Remove all the process waiting in the queue associated with Si into the ready queue

53、endfor; 2024/7/222024/7/22计算机科学系计算机科学系计算机操作系统计算机操作系统Operating System 一般“信号量集”的几种特殊情况： (1) Swait(S, d, d)。 此时在信号量集中只有一个信号量S， 但允许它每次申请d个资源，当现有资源数少于d时，不予分配。 (2) Swait(S, 1, 1)。 此时的信号量集已蜕化为一般的记录型信号量(S1时)或互斥信号量(S=1时)。 (3) Swait(S, 1, 0)。这是一种很特殊且很有用的信号量操作。当S1时，允许多个进程进入某特定区；当S变为0后，将阻止任何进程进入特定区。换言之，它相当于一个可控

54、开关。 2024/7/222024/7/22计算机科学系计算机科学系计算机操作系统计算机操作系统Operating System 2.3.3 信号量的应用信号量的应用 1. 利用信号量实现进程互斥利用信号量实现进程互斥 利用信号量实现进程互斥的进程可描述如下： Var mutex:semaphore =1; begin parbegin process 1: begin repeat wait(mutex); critical section signal(mutex); remainder seetion until false; end 2024/7/222024/7/22计算机科学系计算

55、机科学系计算机操作系统计算机操作系统Operating System process 2: begin repeat wait(mutex); critical section signal(mutex); remainder section until false; end parend 2024/7/222024/7/22计算机科学系计算机科学系计算机操作系统计算机操作系统Operating System 2. 利用信号量实现前趋关系利用信号量实现前趋关系 图 2-10 前趋图举例 2024/7/222024/7/22计算机科学系计算机科学系计算机操作系统计算机操作系统Operating

56、System Var a,b,c,d,e,f,g; semaphore=0,0,0,0,0,0,0; begin parbegin begin S1; signal(a); signal(b); end; begin wait(a); S2; signal(c); signal(d); end; begin wait(b); S3; signal(e); end; begin wait(c); S4; signal(f); end; begin wait(d); S5; signal(g); end; begin wait(e); wait(f); wait(g); S6; end; pare

57、nd end 2024/7/222024/7/22计算机科学系计算机科学系计算机操作系统计算机操作系统Operating System 2.3.4 管管 程程 机机 制制 1. 管程的定义管程的定义 管程由四部分组成：l 局部于管程的共享变量说明；l 对该数据结构进行操作的一组过程；l 对局部于管程的数据设置初始值的语句;l还须为管程赋予一个名字2024/7/222024/7/22计算机科学系计算机科学系计算机操作系统计算机操作系统Operating System 图 2-11 管程的示意图 2024/7/222024/7/22计算机科学系计算机科学系计算机操作系统计算机操作系统Operati

58、ng System 管程的语法如下： type monitor-name=monitor variable declarations procedure entry P1(); begin end; procedure entry P2(); begin end; procedure entry Pn(); begin end; begin initialization code; end 2024/7/222024/7/22计算机科学系计算机科学系计算机操作系统计算机操作系统Operating System 2. 条件变量条件变量 管程中对每个条件变量，都须予以说明，其形式为：Var x,

59、y:condition。该变量应置于wait和signal之前，即可表示为X.wait和X.signal。例如，由于共享数据被占用而使调用进程等待，该条件变量的形式为：nonbusy:condition。此时， wait原 语 应 改 为 nonbusy.wait， 相 应 地 ， signal应 改 为nonbusy.signal。 应当指出，X.signal操作的作用，是重新启动一个被阻塞的进程，但如果没有被阻塞的进程，则X.signal操作不产生任何后果。这与信号量机制中的signal操作不同。因为，后者总是要执行s =s+1操作，因而总会改变信号量的状态。 2024/7/222024/

60、7/22计算机科学系计算机科学系计算机操作系统计算机操作系统Operating System 接收进程接收进程就绪队列就绪队列1 1就绪队列就绪队列2 2.就绪队列就绪队列n n超时超时事件事件1 1发生发生事件事件2 2发生发生等事件等事件1 1等事件等事件2 2.处理机处理机终止进程终止进程事件事件m m发生发生等事件等事件m m2024/7/222024/7/22计算机科学系计算机科学系计算机操作系统计算机操作系统Operating System 如果有进程Q处于阻塞状态， 当进程P执行了X.signal操作后，怎样决定由哪个进行执行，哪个等待，可采用下述两种方式之一进行处理： (1)

61、P等待，直至Q离开管程或等待另一条件。 (2) Q等待，直至P离开管程或等待另一条件。 采用哪种处理方式， 当然是各执一词。 但是Hansan却采用了第一种处理方式。 2024/7/222024/7/22计算机科学系计算机科学系计算机操作系统计算机操作系统Operating System 2.4 经典进程的同步问题经典进程的同步问题 生产者1生产者2生产者n消费者1消费者2消费者n2024/7/222024/7/22计算机科学系计算机科学系计算机操作系统计算机操作系统Operating System 生生产产者者消消费费者者缓冲池缓冲池共享N个缓冲区P1 P2 Pm C1 C2 Cn2024/

62、7/222024/7/22计算机科学系计算机科学系计算机操作系统计算机操作系统Operating System 1. 利用记录型信号量解决生产者利用记录型信号量解决生产者消费者问题消费者问题 假定在生产者和消费者之间的公用缓冲池中，具有n个缓冲区，这时可利用互互斥斥信信号号量量mutex实现诸进程对缓冲池的互互斥斥使用；同同步步：利用信号量empty和full分别表示缓冲池中空缓冲区和满缓冲区的数量。又假定这些生产者和消费者相互等效，只要缓冲池未满，生产者便可将消息送入缓冲池；只要缓冲池未空，消费者便可从缓冲池中取走一个消息。对生产者消费者问题可描述如下： 2024/7/222024/7/22

63、计算机科学系计算机科学系计算机操作系统计算机操作系统Operating System Var mutex, empty, full:semaphore=1,n,0; buffer:array0, , n-1 of item; in, out: integer=0, 0; begin parbegin proceducer:begin repeat producer an item nextp; wait(empty); wait(mutex); buffer(in)=nextp; in=(in+1) mod n; signal(mutex); signal(full); until false

64、; end 2024/7/222024/7/22计算机科学系计算机科学系计算机操作系统计算机操作系统Operating System consumer:begin repeat wait(full); wait(mutex); nextc =buffer(out); out =(out+1) mod n; signal(mutex); signal(empty); consumer the item in nextc; until false; end parend end wait(empty)和wait(mutex)位置是否可以互换会？signal(full)和signal(mutex)位

65、置是否可以互换会？2024/7/222024/7/22计算机科学系计算机科学系计算机操作系统计算机操作系统Operating System 在生产者消费者问题中应注意：1.在 每每 个个 程程 序序 中中 用 于 实 现 互 斥 的 wait(mutex)和signal(mutex)必须成对地出现必须成对地出现； 2.对用于同同步步的资源信号量empty和full的wait和signal操作，同样需要成成对对地地出出现现，但它们分别处于不不同同的的程程序序 中中 。 例 如 ， wait(empty)在 计 算 进 程 中 ， 而signal(empty)则在打印进程中，计算进程若因执行wai

66、t(empty)而阻塞， 则以后将由打印进程将它唤醒；在每个程序中的多个wait操作顺序不能颠倒。应应先先执执行行对对资资源源信信号号量量的wait操作，然然后后再再执执行行对对互互斥斥信信号号量量的的wait操作操作，否则可能引起进程死锁。2024/7/222024/7/22计算机科学系计算机科学系计算机操作系统计算机操作系统Operating System 2. 利用利用AND信号量解决生产者信号量解决生产者消费者问题消费者问题 ar mutex, empty, full:semaphore =1, n, 0; buffer:array0, , n-1 of item; in out:in

67、teger =0, 0; begin parbegin producer:begin repeat produce an item in nextp; Swait(empty, mutex); buffer(in) =nextp; in =(in+1)mod n; Ssignal(mutex, full); until false; end 2024/7/222024/7/22计算机科学系计算机科学系计算机操作系统计算机操作系统Operating System consumer:begin repeat Swait(full, mutex); nextc =buffer(out); out =

68、(out+1) mod n; Ssignal(mutex, empty); consumer the item in nextc; until false; end parend end 如果缓冲区无限大，生产者-消费者问题又该如何解决？2024/7/222024/7/22计算机科学系计算机科学系计算机操作系统计算机操作系统Operating System 3 利用管程解决生产者利用管程解决生产者-消费者问题消费者问题 在利用管程方法来解决生产者-消费者问题时， 首先便是为它们建立一个管程，并命名为Producer-Consumer, 或简称为PC。其中包括两个过程： 2024/7/22202

69、4/7/22计算机科学系计算机科学系计算机操作系统计算机操作系统Operating System (1) put(item)过程。 生产者利用该过程将自己生产的产品投放到缓冲池中， 并用整型变量count来表示在缓冲池中已有的产品数目，当countn时，表示缓冲池已满，生产者须等待。 (2) get(item)过程。消费者利用该过程从缓冲池中取出一个产品，当count0时，表示缓冲池中已无可取用的产品， 消费者应等待。 2024/7/222024/7/22计算机科学系计算机科学系计算机操作系统计算机操作系统Operating System type producer-consumer=moni

70、tor Var in,out,count:integer; buffer:array0,n-1 of item; notfull, notempty:condition; procedure entry put(item) begin if countn then notfull.wait; buffer(in) =nextp; in =(in+1) mod n; count =count+1; if notempty.queue then notempty.signal; end 2024/7/222024/7/22计算机科学系计算机科学系计算机操作系统计算机操作系统Operating Sy

71、stem procedure entry get(item) begin if count0 then notempty.wait; nextc= buffer(out); out =(out+1) mod n; count =count-1; if notfull.quene then notfull.signal; end begin in := out := 0; count :=0; end 2024/7/222024/7/22计算机科学系计算机科学系计算机操作系统计算机操作系统Operating System 在利用管程解决生产者-消费者问题时， 其中的生产者和消费者可描述为： pr

72、oducer:begin repeat produce an item in nextp; PC.put(item); until false; end consumer:begin repeat PC.get(item); consume the item in nextc; until false; end 2024/7/222024/7/22计算机科学系计算机科学系计算机操作系统计算机操作系统Operating System 2.4.2 哲学家进餐问题哲学家进餐问题 41123543522024/7/222024/7/22计算机科学系计算机科学系计算机操作系统计算机操作系统Operati

73、ng System 哲学家筷子盘子哲学家1号哲学家5号哲学家4号哲学家2号哲学家3号15324计算机科学系计算机科学系计算机操作系统计算机操作系统Operating System 哲学家1号哲学家4号哲学家2号哲学家3号15324哲学家5号先拿左,拿到后再拿右,成功后进餐.吃完后先放左再放右.虽可保证不会有相邻的同时进餐,但可能死锁,如动画所示.此时没有一个哲学家可以完成进餐.2024/7/222024/7/22计算机科学系计算机科学系计算机操作系统计算机操作系统Operating System 哲学家1号哲学家4号哲学家2号哲学家3号15324哲学家5号此时5号哲学家被禁止拿筷子.1号哲学家

74、拿起他右边即5号哲学家左边的筷子.1号哲学家开始进餐,完成后放下筷子,其它哲学家开始进餐2024/7/222024/7/22计算机科学系计算机科学系计算机操作系统计算机操作系统Operating System 哲学家1号哲学家4号哲学家2号哲学家3号哲学家5号设1号进餐,则3,4两位哲学家可以拿筷子1号进餐完毕,放下筷子,先左后右.1号放下左边筷子的同时,3号可拿起右边筷子3号开始进餐,同时1号放下右边的筷子此时4号条件不再满足,放下筷子.此时5号条件满足,可在下一时钟周期拿左筷子2024/7/222024/7/22计算机科学系计算机科学系计算机操作系统计算机操作系统Operating Sys

75、tem 哲学家4号哲学家1号哲学家2号哲学家3号1524哲学家5号这种方法将出现1,2号哲学家单键1号筷子,3,4号哲学家竞争3号筷子的情况.而5号没有人与他竞争,得到左边的筷子若4号在与3号的竞争中得到筷子,则与5号竞争4号筷子.无论无论4号号5号谁得号谁得到到4号筷子号筷子,都有都有一个可以进餐一个可以进餐若4号在与3号的竞争中没有得到筷子,则5号得到4号筷子,进餐2024/7/222024/7/22计算机科学系计算机科学系计算机操作系统计算机操作系统Operating System 1. 利用记录型信号量解决哲学家进餐问题利用记录型信号量解决哲学家进餐问题 经分析可知，放在桌子上的筷子是

76、临界资源，在一段时间内只允许一位哲学家使用。为了实现对筷子的互斥使用，可以用一个信号量表示一只筷子，由这五个信号量构成信号量数组。其描述如下： Var chopstick: array0, , 4 of semaphore;2024/7/222024/7/22计算机科学系计算机科学系计算机操作系统计算机操作系统Operating System 所有信号量均被初始化为1， 第i位哲学家的活动可描述为： repeat wait(chopsticki); wait(chopstick(i+1) mod 5); eat; signal(chopsticki); signal(chopstick(i+1

77、) mod 5); think; until false; 是否存在问题？是否存在问题？如何解决？如何解决？2024/7/222024/7/22计算机科学系计算机科学系计算机操作系统计算机操作系统Operating System 2. 利用利用AND信号量机制解决哲学家进餐问题信号量机制解决哲学家进餐问题 在哲学家进餐问题中，要求每个哲学家先获得两个临界资源(筷子)后方能进餐，这在本质上就是前面所介绍的AND同步问题，故用AND信号量机制可获得最简洁的解法。Var chopsiick array 0, , 4 of semaphore=(1,1,1,1,1); processi repeat

78、think; Sswait(chopstick(i+1) mod 5, chopstick i); eat; Ssignat(chopstick(i+1) mod 5, chopstick i); until false; 2024/7/222024/7/22计算机科学系计算机科学系计算机操作系统计算机操作系统Operating System 可采取以下几种解决方法： (1) 至多只允许有四四位位哲学家同时去拿左边的筷子，最终能保证至少有一位哲学家能够进餐，并在用毕时能释放出他用过的两只筷子，从而使更多的哲学家能够进餐。 (2) 仅当哲学家的左左、右右两两只只筷筷子子均可用时，才允许他拿起筷子

79、进餐。 (3) 规定奇数号哲学家先拿他左边的筷子，然后再去拿右边的筷子；而偶数号哲学家则相反。（自己思考如何用信号量解决）2024/7/222024/7/22计算机科学系计算机科学系计算机操作系统计算机操作系统Operating System 2.4.3 读者读者-写者问题写者问题 1. 利用记录型信号量解决读者利用记录型信号量解决读者-写者问题写者问题 为实现Reader与Writer进程间在读或写时的互斥而设置了一个互斥信号量Wmutex。 另外，再设置一个整型变量Readcount表示正在读的进程数目。由于只要有一个Reader进程在读，便不允许Writer进程去写。 因此，仅当Read

80、count=0, 表示尚无Reader进程在读时，Reader进程才需要执行Wait(Wmutex)操作。若wait(Wmutex)操作成功，Reader进程便可去读，相应地，做Readcount+1操作。同理，仅当Reader进程在执行了Readcount减1操作后其值为0时，才须执行signal(Wmutex)操作，以便让Writer进程写。又因为Readcount是一个可被多个Reader进程访问的临界资源，因此，应该为它设置一个互斥信号量rmutex。 2024/7/222024/7/22计算机科学系计算机科学系计算机操作系统计算机操作系统Operating System Var rm

81、utex, wmutex:semaphore =1,1; Readcount:integer =0; begin parbegin Reader:begin repeat wait(rmutex); if readcount=0 then wait(wmutex); Readcount =Readcount+1; signal(rmutex); perform read operation; wait(rmutex); readcount =readcount-1; if readcount=0 then signal(wmutex); signal(rmutex); until false;

82、 end 2024/7/222024/7/22计算机科学系计算机科学系计算机操作系统计算机操作系统Operating System writer:begin repeat wait(wmutex); perform write operation; signal(wmutex); until false; end parend end 2024/7/222024/7/22计算机科学系计算机科学系计算机操作系统计算机操作系统Operating System 2. 利用信号量集机制解决读者利用信号量集机制解决读者-写者问题写者问题 Var RN integer; L, mx:semaphore =

83、RN,1; begin parbegin reader:begin repeat Swait(L,1,1); Swait(mx,1,0); perform read operation; 2024/7/222024/7/22计算机科学系计算机科学系计算机操作系统计算机操作系统Operating System Ssignal(L,1); until false; end writer:begin repeat Swait(mx,1,1; L,RN,0); perform write operation; Ssignal(mx,1); until false; end parend end 202

84、4/7/222024/7/22计算机科学系计算机科学系计算机操作系统计算机操作系统Operating System l1.有三个进程PA，PB，PC协作解决文件打印问题：PA将文件记录从磁盘读入内存的缓冲区1中，每执行一次读一个记录；PB将缓冲区1中的内容复制到缓冲区2中，每执行一次复制一个记录；PC将缓冲区2中的内容打印出来，每执行一次打印一个记录。缓冲区的大小与记录大小一样。清用信号量来保证文件的正确打印。经典进程同步问题经典进程同步问题2024/7/222024/7/22计算机科学系计算机科学系计算机操作系统计算机操作系统Operating System l2、有两个生产者进程A,B和一

85、个消费者进程C，共享一个无限大仓库，可以存放A、B两种产品，生产者每次生产一个产品放入仓库宫消费者消费，消费者每次取一个产品消费，要求：l每次只能存入一种产品（A或B）；lA产品数量B产品数量M；lB产品数量A产品数量0）个单元的缓冲区。P1每次用produce（）生成一个正整数并用put（）送入缓冲区某一空单元中；P2每次用getodd（）从该缓冲区中取出一个奇数并用countodd（）统计奇数个数；P3每次用geteven（）从该缓冲区中取出一个偶数并用counteven（）统计偶数个数。请用信号量机制实现这三个进程的同步与互斥活动，并说明所定义的信号量的含义。要求用伪代码描述。作业作业2

86、024/7/222024/7/22计算机科学系计算机科学系计算机操作系统计算机操作系统Operating System 2.某银行提供1个服务窗口和10个供顾客等待的座位。顾客到达银行时，若有空座位，则到取号机上领取一个号，等待叫号。取号机每次仅允许一位顾客使用。当营业员空闲时，通过叫号选取一位顾客，并为其服务。顾客和营业员的活动过程描述如下：process顾客i从取号机获得一个号码；等待叫号；获得服务；请添加必要的信号量和P、V（或wait()、signal()）操作，实现上述过程中的互斥与同步。要求写出完整的过程，说明信号量的含义并赋初值。process营业员while(TRUE)叫号；为

87、顾客服务；2024/7/222024/7/22计算机科学系计算机科学系计算机操作系统计算机操作系统Operating System 2.5 进进 程程 通通 信信 2.5.1 进程通信的类型进程通信的类型 1. 共享存储器系统共享存储器系统(Shared-Memory System) (1)基于共享数据结构的通信方式。(信号量) (2)(2) 基于共享存储区的通信方式。 (共享硬盘)2024/7/222024/7/22计算机科学系计算机科学系计算机操作系统计算机操作系统Operating System 2. 消息传递系统消息传递系统(Message passing system) 不论是单机系

88、统、多机系统，还是计算机网络，消息传递机制都是用得最广泛的一种进程间通信的机制。在消息传递系统中，进程间的数据交换，是以格式化的消息(message)为单位的；在计算机网络中，又把message称为报文。程序员直接利用系统提供的一组通信命令(原语)进行通信。操作系统隐藏了通信的实现细节，大大减化了通信程序编制的复杂性，而获得广泛的应用。消息传递系统的通信方式属于高级通信方式。又因其实现方式的不同而进一步分成直接通信方式和间接通信方式两种。 2024/7/222024/7/22计算机科学系计算机科学系计算机操作系统计算机操作系统Operating System 3. 管道管道(Pipe)通信通信

89、 所谓“管道”，是指用于连接一个读进程和一个写进程以实现他们之间通信的一个共享文件，又名pipe文件。向管道(共享文件)提供输入的发送进程(即写进程)， 以字符流形式将大量的数据送入管道；而接受管道输出的接收进程(即读进程)，则从管道中接收(读)数据。由于发送进程和接收进程是利用管道进行通信的，故又称为管道通信。这种方式首创于UNIX系统，由于它能有效地传送大量数据，因而又被引入到许多其它操作系统中。 2024/7/222024/7/22计算机科学系计算机科学系计算机操作系统计算机操作系统Operating System 为了协调双方的通信，管道机制必须提供以下三方面的协调能力： 互互斥斥，即

90、当一个进程正在对pipe执行读/写操作时，其它(另一)进程必须等待。 同同步步，指当写(输入)进程把一定数量(如4 KB)的数据写入pipe，便去睡眠等待， 直到读(输出)进程取走数据后，再把他唤醒。当读进程读一空pipe时，也应睡眠等待，直至写进程将数据写入管道后，才将之唤醒。 确确定定对对方方是是否否存存在在，只有确定了对方已存在时，才能进行通信。 2024/7/222024/7/22计算机科学系计算机科学系计算机操作系统计算机操作系统Operating System 2.5.2 消息传递通信的实现方法消息传递通信的实现方法 1. 直接通信方式直接通信方式 这是指发送进程利用OS所提供的发

91、送命令，直接把消息发送给目标进程。此时，要求发送进程和接收进程都以显式方式提供对方的标识符。通常，系统提供下述两条通信命令(原语)： Send(Receiver, message); 发送一个消息给接收进程； Receive(Sender, message); 接收Sender发来的消息；例如，原语Send(P2, m1)表示将消息m1发送给接收进程P2; 而原语Receive(P1，m1)则表示接收由P1发来的消息m1。 2024/7/222024/7/22计算机科学系计算机科学系计算机操作系统计算机操作系统Operating System 在某些情况下，接收进程可与多个发送进程通信，因此，

92、它不可能事先指定发送进程。例如，用于提供打印服务的进程，它可以接收来自任何一个进程的“打印请求”消息。对于这样的应用，在接收进程接收消息的原语中的源进程参数，是完成通信后的返回值，接收原语可表示为： Receive (id, message); 2024/7/222024/7/22计算机科学系计算机科学系计算机操作系统计算机操作系统Operating System 我们还可以利用直接通信原语，来解决生产者-消费者问题。当生产者生产出一个产品(消息)后，便用Send原语将消息发送给消费者进程；而消费者进程则利用Receive原语来得到一个消息。如果消息尚未生产出来，消费者必须等待，直至生产者进程

93、将消息发送过来。生产者-消费者的通信过程可分别描述如下： repeat produce an item in nextp; send(consumer, nextp); until false; repeat receive(producer, nextc); consume the item in nextc; until false; 2024/7/222024/7/22计算机科学系计算机科学系计算机操作系统计算机操作系统Operating System 2. 间接通信方式间接通信方式 (1) 信箱的创建和撤消。进程可利用信箱创建原语来建立一个新信箱。创建者进程应给出信箱名字、信箱属性(公

94、用、私用或共享)；对于共享信箱， 还应给出共享者的名字。当进程不再需要读信箱时，可用信箱撤消原语将之撤消。 (2) 消息的发送和接收。当进程之间要利用信箱进行通信时，必须使用共享信箱，并利用系统提供的下述通信原语进行通信。 Send(mailbox, message); 将一个消息发送到指定信箱； Receive(mailbox, message); 从指定信箱中接收一个消息； 2024/7/222024/7/22计算机科学系计算机科学系计算机操作系统计算机操作系统Operating System 信箱可由操作系统创建，也可由用户进程创建，创建者是信箱的拥有者。据此，可把信箱分为以下三类。 1

95、) 私用信箱 用户进程可为自己建立一个新信箱，并作为该进程的一部分。信箱的拥有者有权从信箱中读取消息，其他用户则只能将自己构成的消息发送到该信箱中。这种私用信箱可采用单向通信链路的信箱来实现。 当拥有该信箱的进程结束时，信箱也随之消失。 2024/7/222024/7/22计算机科学系计算机科学系计算机操作系统计算机操作系统Operating System 2) 公用信箱 它由操作系统创建，并提供给系统中的所有核准进程使用。核准进程既可把消息发送到该信箱中，也可从信箱中读取发送给自己的消息。显然，公用信箱应采用双向通信链路的信箱来实现。通常，公用信箱在系统运行期间始终存在。 3) 共享信箱 它

96、由某进程创建，在创建时或创建后，指明它是可共享的，同时须指出共享进程(用户)的名字。信箱的拥有者和共享者，都有权从信箱中取走发送给自己的消息。 2024/7/222024/7/22计算机科学系计算机科学系计算机操作系统计算机操作系统Operating System 在利用信箱通信时，在发送进程和接收进程之间，存在以下四种关系： (1) 一对一关系。这时可为发送进程和接收进程建立一条两者专用的通信链路，使两者之间的交互不受其他进程的干扰。 (2) 多对一关系。允许提供服务的进程与多个用户进程之间进行交互，也称为客户/服务器交互(client/server interaction)。 (3) 一对

97、多关系。允许一个发送进程与多个接收进程进行交互，使发送进程可用广播方式，向接收者(多个)发送消息。 (4) 多对多关系。允许建立一个公用信箱，让多个进程都能向信箱中投递消息；也可从信箱中取走属于自己的消息。 2024/7/222024/7/22计算机科学系计算机科学系计算机操作系统计算机操作系统Operating System 2.6.3 消息传递系统实现中的若干问题消息传递系统实现中的若干问题 1. 通信链路通信链路(communication link) 为使在发送进程和接收进程之间能进行通信，必须在两者之间建立一条通信链路。有两种方式建立通信链路。第一种方式是：由发送进程在通信之前，用显

98、式的“建立连接”命令(原语)请求系统为之建立一条通信链路；在链路使用完后，也用显式方式拆除链路。 这种方式主要用于计算机网络中。第二种方式是发送进程无须明确提出建立链路的请求，只须利用系统提供的发送命令(原语)，系统会自动地为之建立一条链路。这种方式主要用于单机系统中。 2024/7/222024/7/22计算机科学系计算机科学系计算机操作系统计算机操作系统Operating System 根据通信链路的连接方法，又可把通信链路分为两类： 点点连接通信链路，这时的一条链路只连接两个结点(进程)； 多点连接链路，指用一条链路连接多个(n2)结点(进程)。而根据通信方式的不同，则又可把链路分成两种

99、： 单向通信链路，只允许发送进程向接收进程发送消息； 双向链路，既允许由进程A向进程B发送消息，也允许进程B同时向进程A发送消息。 2024/7/222024/7/22计算机科学系计算机科学系计算机操作系统计算机操作系统Operating System 2. 消息的格式消息的格式 在某些OS中，消息是采用比较短的定长消息格式，这减少了对消息的处理和存储开销。这种方式可用于办公自动化系统中，为用户提供快速的便笺式通信；但这对要发送较长消息的用户是不方便的。在有的OS中，采用另一种变长的消息格式，即进程所发送消息的长度是可变的。系统在处理和存储变长消息时，须付出更多的开销，但方便了用户。 这两种消

100、息格式各有其优缺点，故在很多系统(包括计算机网络)中，是同时都用的。 2024/7/222024/7/22计算机科学系计算机科学系计算机操作系统计算机操作系统Operating System 3. 进程同步方式进程同步方式 (1)发送进程阻塞、 接收进程阻塞。(2)(2) 发送进程不阻塞、 接收进程阻塞。 (3)(3) 发送进程和接收进程均不阻塞。 2024/7/222024/7/22计算机科学系计算机科学系计算机操作系统计算机操作系统Operating System 2.6.4 消息缓冲队列通信机制消息缓冲队列通信机制 1. 消息缓冲队列通信机制中的数据结构消息缓冲队列通信机制中的数据结构

101、(1) 消息缓冲区。在消息缓冲队列通信方式中，主要利用的数据结构是消息缓冲区。它可描述如下： type message buffer=record sender; 发送者进程标识符 size; 消息长度 text; 消息正文 next; 指向下一个消息缓冲区的指针 end 2024/7/222024/7/22计算机科学系计算机科学系计算机操作系统计算机操作系统Operating System (2) PCB中有关通信的数据项。在利用消息缓冲队列通信机制时，在设置消息缓冲队列的同时，还应增加用于对消息队列进行操作和实现同步的信号量，并将它们置入进程 的 PCB中 。 在 PCB中 应 增 加 的

102、 数 据 项 可 描 述 如 下 ： type processcontrol block=record mq; 消息队列队首指针 mutex; 消息队列互斥信号量 sm; 消息队列资源信号量 end 2024/7/222024/7/22计算机科学系计算机科学系计算机操作系统计算机操作系统Operating System 2. 发送原语发送原语 发送进程在利用发送原语发送消息之前，应先在自己的内存空间，设置一发送区a，见图 2 - 12 所示，把待发送的消息正文、发送进程标识符、消息长度等信息填入其中，然后调用发送原语，把消息发送给目标(接收)进程。发送原语首先根据发送区a中所设置的消息长度a.

103、size来申请一缓冲区i，接着，把发送区a中的信息复制到缓冲区i中。为了能将i挂在接收进程的消息队列mq上，应先获得接收进程的内部标识符j，然后将i挂在j.mq上。由于该队列属于临界资源， 故在执行insert操作的前后，都要执行wait和signal操作。 2024/7/222024/7/22计算机科学系计算机科学系计算机操作系统计算机操作系统Operating System 图 2 - 12 消息缓冲通信 2024/7/222024/7/22计算机科学系计算机科学系计算机操作系统计算机操作系统Operating System procedure send(receiver, a) begi

104、n getbuf(a.size,i); 根据a.size申请缓冲区； i.sender =a.sender; 将发送区a中的信息复制到消息缓冲区之中； i.size =a.size; i.text =a.text; i.next =0; getid(PCB set, receiver.j); 获得接收进程内部标识符； wait(j.mutex); insert(j.mq, i); 将消息缓冲区插入消息队列； signal(j.mutex); signal(j.sm); end 2024/7/222024/7/22计算机科学系计算机科学系计算机操作系统计算机操作系统Operating Syste

105、m 3. 接收原语接收原语 接收原语描述如下： procedure receive(b) begin j =internal name; j为接收进程内部的标识符； wait(j.sm); wait(j.mutex); remove(j.mq, i); 将消息队列中第一个消息移出； signal(j.mutex); b.sender =i.sender; 将消息缓冲区i中的信息复制到接收区b; b.size =i.size; b.text =i.text; end 2024/7/222024/7/22计算机科学系计算机科学系计算机操作系统计算机操作系统Operating System 2.6

106、线线 程程 2.6.1 线程的基本概念线程的基本概念 为使程序能并发执行，系统还必须进行以下的一系列操作。 1) 创建进程 2) 撤消进程 3) 进程切换 进程操作，系统要付出较大的时空开销。2024/7/222024/7/22计算机科学系计算机科学系计算机操作系统计算机操作系统Operating System 2. 线程的属性线程的属性 (1)轻型实体。 (2)(2) 独立调度和分派的基本单位。 (3)(3) 可并发执行。 (4)(4) 共享进程资源。 2024/7/222024/7/22计算机科学系计算机科学系计算机操作系统计算机操作系统Operating System 3. 线程的状态线

107、程的状态 (1) 状态参数。 在OS中的每一个线程都可以利用线程标识符和一组状态参数进行描述。状态参数通常有这样几项： 寄存器状态， 它包括程序计数器PC和堆栈指针中的内容； 堆栈， 在堆栈中通常保存有局部变量和返回地址； 线程运行状态， 用于描述线程正处于何种运行状态； 优先级， 描述线程执行的优先程度； 线程专有存储器， 用于保存线程自己的局部变量拷贝； 信号屏蔽， 即对某些信号加以屏蔽。 2024/7/222024/7/22计算机科学系计算机科学系计算机操作系统计算机操作系统Operating System (2) 线程运行状态。 如同传统的进程一样，在各线程之间也存在着共享资源和相互合

108、作的制约关系，致使线程在运行时也具有间断性。 相应地，线程在运行时，也具有下述三种基本状态： 执行状态，表示线程正获得处理机而运行； 就绪状态， 指线程已具备了各种执行条件，一旦获得CPU便可执行的状态； 阻塞状态，指线程在执行中因某事件而受阻，处于暂停执行时的状态。 2024/7/222024/7/22计算机科学系计算机科学系计算机操作系统计算机操作系统Operating System 4. 线程的创建和终止线程的创建和终止 在多线程OS环境下，应用程序在启动时，通常仅有一个线程在执行，该线程被人们称为“初始化线程”。它可根据需要再去创建若干个线程。在创建新线程时，需要利用一个线程创建函数(

109、或系统调用)，并提供相应的参数，如指向线程主程序的入口指针、堆栈的大小，以及用于调度的优先级等。在线程创建函数执行完后，将返回一个线程标识符供以后使用。 终止线程的方式有两种：一种是在线程完成了自己的工作后自愿退出；另一种是线程在运行中出现错误或由于某种原因而被其它线程强行终止。 2024/7/222024/7/22计算机科学系计算机科学系计算机操作系统计算机操作系统Operating System 5. 多线程多线程OS中的进程中的进程 在多线程OS中，进程是作为拥有系统资源的基本单位，通常的进程都包含多个线程并为它们提供资源，但此时的进程就不再作为一个执行的实体。 多线程OS中的进程有以下

110、属性： (1) 作为系统资源分配的单位。 (2) 可包括多个线程。 (3) 进程不是一个可执行的实体。 2024/7/222024/7/22计算机科学系计算机科学系计算机操作系统计算机操作系统Operating System 线程线程线程线程线程线程进程进程1 1进程进程2 2进程进程3 3进进程程与与线线程程关关系系图图2024/7/222024/7/22计算机科学系计算机科学系计算机操作系统计算机操作系统Operating System 2.6.2 线程间的同步和通信线程间的同步和通信 1. 互斥锁互斥锁(mutex) 互斥锁是一种比较简单的、用于实现进程间对资源互斥访问的机制。由于操作互

111、斥锁的时间和空间开锁都较低， 因而较适合于高频度使用的关键共享数据和程序段。互斥锁可以有两种状态， 即开锁(unlock)和关锁(lock)状态。 相应地，可用两条命令(函数)对互斥锁进行操作。其中的关锁lock操作用于将mutex关上，开锁操作unlock则用于打开mutex。 2024/7/222024/7/22计算机科学系计算机科学系计算机操作系统计算机操作系统Operating System 2. 条件变量条件变量 每一个条件变量通常都与一个互斥锁一起使用，亦即，在创建一个互斥锁时便联系着一个条件变量。单纯的互斥锁用于短期锁定，主要是用来保证对临界区的互斥进入。而条件变量则用于线程的长

112、期等待， 直至所等待的资源成为可用的。 线程首先对mutex执行关锁操作，若成功便进入临界区，然后查找用于描述资源状态的数据结构，以了解资源的情况。 只要发现所需资源R正处于忙碌状态，线程便转为等待状态， 并对mutex执行开锁操作后，等待该资源被释放； 若资源处于空闲状态，表明线程可以使用该资源，于是将该资源设置为忙碌状态，再对mutex执行开锁操作。2024/7/222024/7/22计算机科学系计算机科学系计算机操作系统计算机操作系统Operating System 下面给出了对上述资源的申请(左半部分)和释放(右半部分)操作的描述。 Lock mutex Lock mutex chec

113、k data structures; mark resource as free; while(resource busy); unlock mutex; wait(condition variable); wakeup(condition variable); mark resource as busy; unlock mutex; 2024/7/222024/7/22计算机科学系计算机科学系计算机操作系统计算机操作系统Operating System 3. 信号量机制信号量机制 (1) 私用信号量(private samephore)。 当某线程需利用信号量来实现同一进程中各线程之间的同步

114、时，可调用创建信号量的命令来创建一私用信号量，其数据结构是存放在应用程序的地址空间中。私用信号量属于特定的进程所有，OS并不知道私用信号量的存在，因此，一旦发生私用信号量的占用者异常结束或正常结束，但并未释放该信号量所占有空间的情况时，系统将无法使它恢复为0(空)， 也不能将它传送给下一个请求它的线程。 2024/7/222024/7/22计算机科学系计算机科学系计算机操作系统计算机操作系统Operating System (2) 公用信号量(public semaphort)。 公用信号量是为实现不同进程间或不同进程中各线程之间的同步而设置的。由于它有着一个公开的名字供所有的进程使用，故而把

115、它称为公用信号量。其数据结构是存放在受保护的系统存储区中，由OS为它分配空间并进行管理，故也称为系统信号量。如果信号量的占有者在结束时未释放该公用信号量，则OS会自动将该信号量空间回收，并通知下一进程。可见，公用信号量是一种比较安全的同步机制。 2024/7/222024/7/22计算机科学系计算机科学系计算机操作系统计算机操作系统Operating System 2.6.3 内核支持线程和用户级线程内核支持线程和用户级线程 1. 内核支持线程内核支持线程 这里所谓的内核支持线程，也都同样是在内核的支持下运行的，即无论是用户进程中的线程，还是系统进程中的线程，他们的创建、撤消和切换等，也是依靠

116、内核实现的。此外，在内核空间还为每一个内核支持线程设置了一个线程控制块， 内核是根据该控制块而感知某线程的存在的，并对其加以控制。 2024/7/222024/7/22计算机科学系计算机科学系计算机操作系统计算机操作系统Operating System 2. 用户级线程用户级线程 用户级线程仅存在于用户空间中。对于这种线程的创建、 撤消、线程之间的同步与通信等功能，都无须利用系统调用来实现。对于用户级线程的切换，通常是发生在一个应用进程的诸多线程之间，这时，也同样无须内核的支持。由于切换的规则远比进程调度和切换的规则简单，因而使线程的切换速度特别快。可见，这种线程是与内核无关的。2024/7/

117、222024/7/22计算机科学系计算机科学系计算机操作系统计算机操作系统Operating System 2.6.4 线程控制线程控制 1. 内核支持线程的实现内核支持线程的实现 图 2 - 13 任务数据区空间 PTDA进程资源TCB#1TCB#2TCB#32024/7/222024/7/22计算机科学系计算机科学系计算机操作系统计算机操作系统Operating System 2. 用户级线程的实现用户级线程的实现 1) 运行时系统(Runtime System) 所谓“运行时系统”，实质上是用于管理和控制线程的函数(过程)的集合， 其中包括用于创建和撤消线程的函数、 线程同步和通信的函数

118、以及实现线程调度的函数等。正因为有这些函数，才能使用户级线程与内核无关。运行时系统中的所有函数都驻留在用户空间，并作为用户级线程与内核之间的接口。 2024/7/222024/7/22计算机科学系计算机科学系计算机操作系统计算机操作系统Operating System 2) 内核控制线程 这 种 线 程 又 称 为 轻 型 进 程 LWP(Light Weight Process)。 每一个进程都可拥有多个LWP， 同用户级线程一样， 每个LWP都有自己的数据结构(如TCB)，其中包括线程标识符、优先级、 状态， 另外还有栈和局部存储区等。 它们也可以共享进程所拥有的资源。LWP可通过系统调用来获得内核提供的服务，这样，当一个用户级线程运行时，只要将它连接到一个LWP上，此时它便具有了内核支持线程的所有属性。 2024/7/222024/7/22计算机科学系计算机科学系计算机操作系统计算机操作系统Operating System 图 2 - 14 利用轻型进程作为中间系统 2024/7/222024/7/22计算机科学系计算机科学系计算机操作系统计算机操作系统Operating System 谢谢!2024/7/222024/7/22计算机科学系计算机科学系