操作系统第2章进程管理.ppt

《操作系统第2章进程管理.ppt》由会员分享，可在线阅读，更多相关《操作系统第2章进程管理.ppt（153页珍藏版）》请在三一办公上搜索。

1、操作系统第2章进程管理,操作系统第2章进程管理,2.1 进程的基本概念,2.1.1 程序的顺序执行及其特征,1.程序的顺序执行 仅当前一操作(程序段)执行完后，才能执行后继操作。例如，在进行计算时，总须先输入用户的程序和数据，然后进行计算，最后才能打印计算结果。,2023/1/8,计算机科学系,2.1 进程的基本概念 2.1.1 程序的顺序执行及其特征,图 2-1 程序的顺序执行,S1:a=x+y;S2:b=a-5;S3:c=b+1;,2023/1/8,计算机科学系,图 2-1 程序的顺序执行 S1:a=x+y;202,2.程序顺序执行时的特征,顺序性：(2)封闭性：(3)可再现性：,2023

2、/1/8,计算机科学系,2.程序顺序执行时的特征 顺序性：2022/9/19计算机,2.1.2 前趋图,前趋图(Precedence Graph)是一个有向无循环图，记为DAG(Directed Acyclic Graph)，用于描述进程之间执行的前后关系。图中的每个结点可用于描述一个程序段或进程，乃至一条语句；结点间的有向边则用于表示两个结点之间存在的偏序(Partial Order)或前趋关系(Precedence Relation)“”。=(Pi,Pj)|Pi must complete before Pj may start,如果(Pi,Pj),可写成PiPj，称Pi是Pj的直接前趋，

3、而称Pj是Pi的直接后继。在前趋图中，把没有前趋的结点称为初始结点(Initial Node)，把没有后继的结点称为终止结点(Final Node)。,2023/1/8,计算机科学系,2.1.2 前趋图 前趋图(Preceden,每个结点还具有一个重量(Weight)，用于表示该结点所含有的程序量或结点的执行时间。,图 2-2 前趋图,2023/1/8,计算机科学系,每个结点还具有一个重量(Weight)，用于表,对于图 2-2(a)所示的前趋图，存在下述前趋关系：,P1P2,P1P3,P1P4,P2P5,P3P5,P4P6,P4P7,P5P8,P6P8,P7P9,P8P9或表示为：P=P1,

4、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,2023/1/8,计算机科学系,对于图 2-2(a)所示的前趋图，存在下述前趋关系：,2.1.3 程序的并发执行及其特征,1.程序的并发执行,图 2-3 并发执行时的前趋图,2023/1/8,计算机科学系,2.1.3 程序的并发执行及其特征 1.程序的并发执行 图,在该例中存在下述

5、前趋关系：IiCi，IiIi+1,CiPi,CiCi+1，PiPi+1而Ii+1和Ci及Pi-1是重迭的，亦即在Pi-1和Ci以及Ii+1之间，可以并发执行。,2023/1/8,计算机科学系,在该例中存在下述前趋关系：2022/9/19计算机科学系,图 2-4 四条语句的前趋关系,对于具有下述四条语句的程序段：S1:a=x+2 S2:b=y+4 S3:c=a+b S4:d=c+b,2023/1/8,计算机科学系,图 2-4 四条语句的前趋关系对于具有下述四条语句的程序段：,2.程序并发执行时的特征,间断性2)失去封闭性 3)不可再现性,例如，有两个循环程序A和B，它们共享一个变量N。程序A每执

6、行一次时，都要做N=N+1操作；程序B每执行一次时，都要执行Print(N)操作，然后再将N置成“0”。程序A和B以不同的速度运行。(1)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。,2023/1/8,计算机科学系,2.程序并发执行时的特征 间断性 例如，有两个,2.1.4 进程的特征与状态,1.进程的特征和定义结构特征(程序段、数据段和进程控制块PCB)动态性（最基本的特征，与程序的区别）并发

7、性（重要特征）独立性（运行，分配资源，调度）异步性,2023/1/8,计算机科学系,2.1.4 进程的特征与状态 1.进程的特征和定义2022,较典型的进程定义有：(1)进程是程序的一次执行。(2)进程是一个程序及其数据在处理机上顺序执行时所发生的活动。(3)进程是程序在一个数据集合上运行的过程，它是系统进行资源分配和调度的一个独立单位。在引入了进程实体的概念后，本书把传统OS中的进程定义为：“进程是进程实体的运行过程，是系统进行资源分配和调度的一个独立单位”。,2023/1/8,计算机科学系,较典型的进程定义有：2022/9/19计算机科,进程与程序的区别：(1)程序是指令的有序集合，其本身

8、没有任何运行的含义，是一个静态的概念。而进程是程序在处理机上的一次执行过程，它是一个动态的概念。(2)程序可以作为一种软件资料长期存在，而进程是有一定生命期的。程序是永久的，进程是暂时的。(3)进程更能真实地描述并发，而程序不能(4)程序是进程的组成部分(5)进程具有创建其他进程的功能，而程序没有(6)同一程序同时运行于若干个数据集合上，它将属于若干个不同的进程。也就是说同一程序可以对应多个进程,2023/1/8,计算机科学系,进程与程序的区别：2022/9/19计算机科学系,思考？,为什么引入进程？,2023/1/8,计算机科学系,思考？为什么引入进程？2022/9/19计算,2.进程的三种

9、基本状态,(1)就绪(Ready)状态(2)执行状态(3)阻塞状态,2023/1/8,计算机科学系,2.进程的三种基本状态(1)就绪(Ready)状态 20,图 2-5 进程的三种基本状态及其转换,2023/1/8,计算机科学系,图 2-5 进程的三种基本状态及其转换 2022/9/19计,3.挂起状态 引入挂起状态的原因：终端用户的请求；父进程请求；负荷调节的需要；操作系统的需要；对换需要。挂起状态实际是暂时从内存中被淘汰出去的进程。,2023/1/8,计算机科学系,3.挂起状态 2022/9/19计算机科学系,2)进程状态的转换,活动就绪静止就绪。(2)活动阻塞静止阻塞。(3)静止就绪活动

10、就绪。(4)静止阻塞活动阻塞。,2023/1/8,计算机科学系,2)进程状态的转换 活动就绪静止就绪。2022/9/1,具有挂起状态的进程状态图,2023/1/8,计算机科学系,具有挂起状态的进程状态图 2022/9/19计算机科学系,2五状态进程模型 引入创建状态和终止状态（1）创建状态作用（2）终止状态作用,等待条件满足,2023/1/8,计算机科学系,2五状态进程模型 引入创建状态和终止状态,3挂起状态进程模型（）,单挂起状态进程模型,2023/1/8,计算机科学系,3挂起状态进程模型（）单挂起状态进程模型2022/9/1,3挂起状态进程模型（）,双挂起状态进程模型,2023/1/8,计

11、算机科学系,3挂起状态进程模型（）双挂起状态进程模型2022/9/1,思考？,1如果系统中有N个进程，运行的进程最多几个，最少几个；就绪进程最多几个最少几个；等待进程最多几个，最少几个？2.有没有这样的状态转换，为什么？等待运行；就绪等待,2023/1/8,计算机科学系,思考？1如果系统中有N个进程，运行的进程最,课堂练习,当某个作业被作业调度程序选中，进入内存开始运行时，作业的状态为：.提交状态.完成状态.执行状态.就绪状态进程在发出I/O请求后，可能导致下列哪种进程状态演变？A.就绪 执行 B.执行 就绪C.阻塞 执行 D.执行 阻塞单处理机系统中，可并行的是I 进程与进程 II 处理机与

12、设备III 处理机与通道 IV 设备与设备 AI、II和III B.I、II和IV C.I、III和IV D.II、III和IV,2023/1/8,计算机科学系,课堂练习当某个作业被作业调度程序选中，进入内存开始运行时，作,2.1.5 进程控制块,1.进程控制块的作用 进程控制块的作用是使一个在多道程序环境下不能独立运行的程序(含数据)，成为一个能独立运行的基本单位，一个能与其它进程并发执行的进程。或者说，OS是根据PCB来对并发执行的进程进行控制和管理的。,为了描述一个进程和其它进程以及系统资源的关系，为了刻画一个进程在各个不同时期所处的状态，人们采用了一个与进程相联系的数据块，称为进程控制

13、块（PCB）。系统利用PCB来控制和管理进程，所以PCB是系统感知进程存在的唯一标志。进程与PCB是一一对应的。,2023/1/8,计算机科学系,2.1.5 进程控制块 1.进程控制块的作用,2.进程控制块中的信息 1)进程标识符 进程标识符用于惟一地标识一个进程。一个进程通常有两种标识符：(1)内部标识符。在所有的操作系统中，都为每一个进 程赋予一个惟一的数字标识符，它通常是一个进程的序号。设置内部标识符主要是为了方便系统使用。(2)外部标识符。它由创建者提供，通常是由字母、数字组成，往往是由用户(进程)在访问该进程时使用。为了描述进程的家族关系，还应设置父进程标识及子进程标识。此外，还可设

14、置用户标识，以指示拥有该进程的用户。,2023/1/8,计算机科学系,2.进程控制块中的信息2022/9/19计算机科学系,2)处理机状态 处理机状态信息主要是由处理机的各种寄存器中的内容组成的。通用寄存器，又称为用户可视寄存器，它们是用户程序可以访问的，用于暂存信息，在大多数处理机中，有 832 个通用寄存器，在RISC结构的计算机中可超过 100 个；指令计数器，其中存放了要访问的下一条指令的地址；程序状态字PSW，其中含有状态信息，如条件码、执行方式、中断屏蔽标志等；用户栈指针，指每个用户进程都有一个或若干个与之相关的系统栈，用于存放过程和系统调用参数及调用地址。栈指针指向该栈的栈顶。,

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

16、括：程序和数据的地址，是指进程的程序和数据所在的内存或外存地(首)址，以便再调度到该进程执行时，能从PCB中找到其程序和数据；进程同步和通信机制，指实现进程同步和进程通信时必需的机制，如消息队列指针、信号量等，它们可能全部或部分地放在PCB中；资源清单，是一张列出了除CPU以外的、进程所需的全部资源及已经分配到该进程的资源的清单；链接指针，它给出了本进程(PCB)所在队列中的下一个进程的PCB的首地址。,2023/1/8,计算机科学系,4)进程控制信息 2022/9/19计算机科学系,3.进程控制块的组织方式,1)链接方式,PCB链接队列示意图,2023/1/8,计算机科学系,3.进程控制块的

17、组织方式 1)链接方式 PCB链接队列示,2)索引方式,按索引方式组织PCB,2023/1/8,计算机科学系,2)索引方式 按索引方式组织PCB 2022/9/19计算,2.2 进 程 控 制,进程控制是进程管理中最基本的功能。它用于创建一个新进程，终止一个已完成的进程，或终止一个因出现某事件而使其无法运行下去的进程，还可负责进程运行中的状态转换。进程控制就是对系统中的所有进程实施管理，进程控制一般有原语来实现。所谓原语是一种特殊的系统功能调用，它可以完成一个特定的功能，其特点是原语执行时不可被中断，其作用是为了实现进程的通信和控制。常用原语：创建原语终止原语阻塞原语、唤醒原语,2023/1/

18、8,计算机科学系,2.2 进 程 控 制 进程控制是进程管理中最,2.2 进 程 控 制,2.2.1 进程的创建,1.进程图(Process Graph),进程树,2023/1/8,计算机科学系,2.2 进 程 控 制 2.2.1 进程的创建 1.进程图,2.引起创建进程的事件,用户登录。(2)作业调度。(3)提供服务。（文件打印）(4)应用请求。（输入，处理，打印）,系统内核,用户自己,2023/1/8,计算机科学系,2.引起创建进程的事件 用户登录。系统内核用户自己202,3.进程的创建(Creation of Progress),(1)申请空白PCB。(2)为新进程分配资源。(3)初始化

19、进程控制块。(4)将新进程插入就绪队列，如果进程就绪队列能够接纳新进程，便将新进程插入就绪队列。,2023/1/8,计算机科学系,3.进程的创建(Creation of Progress),2.2.2 进程的终止,1.引起进程终止(Termination of Process)的事件 1)正常结束 在任何计算机系统中，都应有一个用于表示进程已经运行完成的指示。例如，在批处理系统中，通常在程序的最后安排一条Halt指令或终止的系统调用。当程序运行到Halt指令时，将产生一个中断，去通知OS本进程已经完成。,2023/1/8,计算机科学系,2.2.2 进程的终止 1.引起进程终止(T,2)异常结束

20、 在进程运行期间，由于出现某些错误和故障而迫使进程终止。这类异常事件很多，常见的有：越界错误保护错非法指令特权指令错运行超时等待超时算术运算错I/O故障,2023/1/8,计算机科学系,2)异常结束 2022/9/19计算机科学,3)外界干预 外界干预并非指在本进程运行中出现了异常事件，而是指进程应外界的请求而终止运行。这些干预有：操作员或操作系统干预 父进程请求父进程终止,2023/1/8,计算机科学系,3)外界干预 2022/9/19计算机科学系,2.进程的终止过程(1)根据被终止进程的标识符，从PCB集合中检索出该进程的PCB，从中读出该进程的状态。(2)若被终止进程正处于执行状态，应立

21、即终止该进程的执行，并置调度标志为真，用于指示该进程被终止后应重新进行调度。(3)若该进程还有子孙进程，还应将其所有子孙进程予以终止，以防他们成为不可控的进程。(4)将被终止进程所拥有的全部资源，或者归还给其父进程，或者归还给系统。(5)将被终止进程(它的PCB)从所在队列(或链表)中移出，等待其他程序来搜集信息。,2023/1/8,计算机科学系,2.进程的终止过程 2022/9/19计算机,2.2.3 进程的阻塞与唤醒,1.引起进程阻塞和唤醒的事件,请求系统服务 启动某种操作新数据尚未到达无新工作可做,2023/1/8,计算机科学系,2.2.3 进程的阻塞与唤醒1.引起进程阻塞和唤醒的事件,

22、2.进程阻塞过程 正在执行的进程，当发现上述某事件时，由于无法继续执行，于是进程便通过调用阻塞原语block把自己阻塞。可见，进程的阻塞是进程自身的一种主动行为。进入block过程后，由于此时该进程还处于执行状态，所以应先立即停止执行，把进程控制块中的现行状态由“执行”改为阻塞，并将PCB插入阻塞队列。如果系统中设置了因不同事件而阻塞的多个阻塞队列，则应将本进程插入到具有相同事件的阻塞(等待)队列。最后，转调度程序进行重新调度，将处理机分配给另一就绪进程，并进行切换，亦即，保留被阻塞进程的处理机状态(在PCB中)，再按新进程的PCB中的处理机状态设置CPU的环境。,2023/1/8,计算机科学

23、系,2.进程阻塞过程 2022/9/19计算机,3.进程唤醒过程 当被阻塞进程所期待的事件出现时，如I/O完成或其所期待的数据已经到达，则由有关进程(比如，用完并释放了该I/O设备的进程)调用唤醒原语wakeup()，将等待该事件的进程唤醒。唤醒原语执行的过程是：首先把被阻塞的进程从等待该事件的阻塞队列中移出，将其PCB中的现行状态由阻塞改为就绪，然后再将该PCB插入到就绪队列中。,2023/1/8,计算机科学系,3.进程唤醒过程 2022/9/19计算机,2.2.4 进程的挂起与激活,1.进程的挂起 当出现了引起进程挂起的事件时，比如，用户进程请求将自己挂起，或父进程请求将自己的某个子进程挂

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

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

26、II B：仅II和IIIC：仅I和III D：I，II，III,2023/1/8,计算机科学系,课堂练习24、下列选项中，导致创进新进程的操作是（C）202,思考？,为什么创建进程要用原语来实现？2 阻塞进程在什么情况下会被唤醒？谁来唤醒它？,2023/1/8,计算机科学系,思考？为什么创建进程要用原语来实现？20,2.3 进 程 同 步,2.3.1 进程同步的基本概念,1.两种形式的制约关系,间接相互制约关系。(2)直接相互制约关系。,2023/1/8,计算机科学系,2.3 进 程 同 步 2.3.1 进程同步的基本概念 1.,2.临界资源(Critical Resouce),生产者-消费者

27、(producer-consumer)问题是一个著名的进程同步问题。它描述的是：有一群生产者进程在生产产品，并将这些产品提供给消费者进程去消费。为使生产者进程与消费者进程能并发执行，在两者之间设置了一个具有n个缓冲区的缓冲池，生产者进程将它所生产的产品放入一个缓冲区中；消费者进程可从一个缓冲区中取走产品去消费。尽管所有的生产者进程和消费者进程都是以异步方式运行的，但它们之间必须保持同步，即不允许消费者进程到一个空缓冲区去取产品；也不允许生产者进程向一个已装满产品且尚未被取走的缓冲区中投放产品。,2023/1/8,计算机科学系,2.临界资源(Critical Resouce),我们可利用一个数组

28、来表示上述的具有n个(0，1，n-1)缓冲区的缓冲池。用输入指针in来指示下一个可投放产品的缓冲区，每当生产者进程生产并投放一个产品后，输入指针加1；用一个输出指针out来指示下一个可从中获取产品的缓冲区，每当消费者进程取走一个产品后，输出指针加1。由于这里的缓冲池是组织成循环缓冲的，故应把输入指针加1表示成 in=(in+1)mod n；输出指针加1表示成out=(out+1)mod n。当(in+1)mod n=out时表示缓冲池满；而in=out则表示缓冲池空。,2023/1/8,计算机科学系,我们可利用一个数组来表示上述的具有n个(0，1，,此外，还引入了一个整型变量counter,其

29、初始值为0。每当生产者进程向缓冲池中投放一个产品后，使counter加1；反之，每当消费者进程从中取走一个产品时，使counter减1。,2023/1/8,计算机科学系,此外，还引入了一个整型变量counter,其初始值为0。每,生产者和消费者两进程共享下面的变量：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语句表示重复的测试条件(co

30、ndication)，重复测试应进行到该条件变为false(假)，即到该条件不成立时为止。在生产者进程中使用一局部变量nextp，用于暂时存放每次刚生产出来的产品；而在消费者进程中，则使用一个局部变量nextc,用于存放每次要消费的产品。,2023/1/8,计算机科学系,生产者和消费者两进程共享下面的变量：2022/9/19计算机,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;consum

31、er:repeat while counter=0 do no-op;nextc=bufferout;out=(out+1)mod n;counter=counter-1;consumer the item in nextc;until false;,2023/1/8,计算机科学系,producer:repeat 2022/9/19计算机科,虽然上面的生产者程序和消费者程序，在分别看时都是正确的，而且两者在顺序执行时其结果也会是正确的，但若并发执行时，就会出现差错，问题就在于这两个进程共享变量counter。生产者对它做加1操作，消费者对它做减1操作，这两个操作在用机器语言实现时，常可用下面的

32、形式描述：register 1=counter;register1=register 1+1;counter=register 1;register 2=counter;register 2=register 2-1;counter=register 2;,2023/1/8,计算机科学系,虽然上面的生产者程序和消费者程序，在分别看时,假设：counter的当前值是5。如果生产者进程先执行左列的三条机器语言语句，然后消费者进程再执行右列的三条语句，则最后共享变量counter的值仍为5；反之，如果让消费者进程先执行右列的三条语句，然后再让生产者进程执行左列的三条语句，counter值也还是5，但

33、是，如果按下述顺序执行：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),2023/1/8,计算机科学系,假设：counter的当前值是5。如果生产者进,3.临界区(critical section),可把一个访问临界资源的循环进程描述如下：repeat critic

34、al section;remainder section;until false;,entry section,exit section,2023/1/8,计算机科学系,3.临界区(critical section)可把一个访,4.同步机制应遵循的规则,空闲让进。(2)忙则等待。(3)有限等待。(4)让权等待。,2023/1/8,计算机科学系,4.同步机制应遵循的规则 空闲让进。2022/9/19计算,2.3.2 信号量机制,1.整型信号量 最初由Dijkstra把整型信号量定义为一个整型量，除初始化外，仅能通过两个标准的原子操作(Atomic Operation)wait(S)和signal

35、(S)来访问。这两个操作一直被分别称为P、V操作。wait和signal操作可描述为：wait(S):while S0 do no-op S=S-1;signal(S):S=S+1;(1)原子操作(2)忙等待,2023/1/8,计算机科学系,2.3.2 信号量机制 1.整型信号量,2.记录型信号量 在整型信号量机制中的wait操作，只要是信号量S0，就会不断地测试。因此，该机制并未遵循“让权等待”的准则，而是使进程处于“忙等”的状态。记录型信号量机制，则是一种不存在“忙等”现象的进程同步机制。但在采取了“让权等待”的策略后，又会出现多个进程等待访问同一临界资源的情况。为此，在信号量机制中，除了

36、需要一个用于代表资源数目的整型变量value外，还应增加一个进程链表L，用于链接上述的所有等待进程。记录型信号量是由于它采用了记录型的数据结构而得名的。它所包含的上述两个数据项可描述为：,2023/1/8,计算机科学系,2.记录型信号量 2022/9/19计算,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

37、)end procedure signal(S)var S:semaphore;begin S.value=S.value+1;if S.value0 then wakeup(S,L);end,2023/1/8,计算机科学系,type semaphore=record 2022/9/1,在记录型信号量机制中，S.value的初值表示系统中某类资源的数目，因而又称为资源信号量。对它的每次wait操作，意味着进程请求一个单位的该类资源，因此描述为S.value=S.value-1；当S.value0时，表示该类资源已分配完毕，因此进程应调用block原语，进行自我阻塞，放弃处理机，并插入到信号量链

38、表S.L中。可见，该机制遵循了“让权等待”准则。此时S.value的绝对值表示在该信号量链表中已阻塞进程的数目。对信号量的每次signal操作，表示执行进程释放一个单位资源，故S.value=S.value+1操作表示资源数目加1。若加1后仍是S.value0，则表示在该信号量链表中，仍有等待该资源的进程被阻塞，故还应调用wakeup原语，将S.L链表中的第一个等待进程唤醒。如果S.value的初值为1，表示只允许一个进程访问临界资源，此时的信号量转化为互斥信号量。,2023/1/8,计算机科学系,在记录型信号量机制中，S.value的初值表示,3.AND型信号量,在两个进程中都要包含两个对D

39、mutex和Emutex的操作，即process 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阻塞,2023/1/8,计算机科学系,3.AND型信号量 在两个进程中都要包含两个对Dmut

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

41、i1 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 endif Ssignal(S1,S2,Sn)for i=1 to n do Si=Si+1;Remove all the process waiting in th

42、e queue associated with Si into the ready queue.endfor;,2023/1/8,计算机科学系,Swait(S1,S2,Sn)2022/9/19,4.信号量集,Swait(S1,t1,d1,Sn,tn,dn)if Sit1 and and Sntn then for i=1 to n do Si=Si-di;endfor else Place the executing process in the waiting queue of the first Si with Siti and set its program counter to the

43、 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 endfor;,2023/1/8,计算机科学系,4.信号量集 Swait(S1,t1,d1,S,一般“信号量集”的几种特殊情况：(1)Swait(S,d,d)。此时在信号量集中只有一个信号量S，但允许它每次申请d个资源，当现有资源数少于d时，不予分配。(2)Swa

44、it(S,1,1)。此时的信号量集已蜕化为一般的记录型信号量(S1时)或互斥信号量(S=1时)。(3)Swait(S,1,0)。这是一种很特殊且很有用的信号量操作。当S1时，允许多个进程进入某特定区；当S变为0后，将阻止任何进程进入特定区。换言之，它相当于一个可控开关。,2023/1/8,计算机科学系,一般“信号量集”的几种特殊情况：2022/,2.3.3 信号量的应用,1.利用信号量实现进程互斥,利用信号量实现进程互斥的进程可描述如下：Var mutex:semaphore=1;begin parbegin process 1:begin repeat wait(mutex);critica

45、l section signal(mutex);remainder seetion until false;end,2023/1/8,计算机科学系,2.3.3 信号量的应用 1.利用信号量实现进程互斥 利用,process 2:begin repeat wait(mutex);critical section signal(mutex);remainder section until false;end parend,2023/1/8,计算机科学系,process 2:begin 2022/9/19计算机科,2.利用信号量实现前趋关系,图 2-10 前趋图举例,2023/1/8,计算机科学系,

46、2.利用信号量实现前趋关系 图 2-10 前趋图举例 20,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;parend en

47、d,2023/1/8,计算机科学系,Var a,b,c,d,e,f,g;semaphore,2.3.4 管 程 机 制,1.管程的定义,管程由四部分组成：局部于管程的共享变量说明；对该数据结构进行操作的一组过程；对局部于管程的数据设置初始值的语句;还须为管程赋予一个名字,2023/1/8,计算机科学系,2.3.4 管 程 机 制 1.管程的定义 管程,图 2-11 管程的示意图,2023/1/8,计算机科学系,图 2-11 管程的示意图 2022/9/19计算机科学系,管程的语法如下：type monitor-name=monitor variable declarations procedu

48、re entry P1();begin end;procedure entry P2();begin end;procedure entry Pn();begin end;begin initialization code;end,2023/1/8,计算机科学系,管程的语法如下：2022/9/19计算机科学系,2.条件变量,管程中对每个条件变量，都须予以说明，其形式为：Var x,y:condition。该变量应置于wait和signal之前，即可表示为X.wait和X.signal。例如，由于共享数据被占用而使调用进程等待，该条件变量的形式为：nonbusy:condition。此时，wai

49、t原语应改为nonbusy.wait，相应地，signal应改为nonbusy.signal。应当指出，X.signal操作的作用，是重新启动一个被阻塞的进程，但如果没有被阻塞的进程，则X.signal操作不产生任何后果。这与信号量机制中的signal操作不同。因为，后者总是要执行s=s+1操作，因而总会改变信号量的状态。,2023/1/8,计算机科学系,2.条件变量 管程中对每个条件变量，都须予,2023/1/8,计算机科学系,接收进程就绪队列1就绪队列2.就绪队列n超时事件1发生事,如果有进程Q处于阻塞状态，当进程P执行了X.signal操作后，怎样决定由哪个进行执行，哪个等待，可采用下述

50、两种方式之一进行处理：(1)P等待，直至Q离开管程或等待另一条件。(2)Q等待，直至P离开管程或等待另一条件。采用哪种处理方式，当然是各执一词。但是Hansan却采用了第一种处理方式。,2023/1/8,计算机科学系,如果有进程Q处于阻塞状态，当进程P执行了X,2.4 经典进程的同步问题,2023/1/8,计算机科学系,2.4 经典进程的同步问题 生产者1生产者2生产者n消费者1,生产者,消费者,缓冲池,共享N个缓冲区,P1 P2 Pm C1 C2 Cn,2023/1/8,计算机科学系,生产者消费者缓冲池共享N个缓冲区P1 P2 Pm 20,1.利用记录型信号量解决生产者消费者问题 假定在生产