工学进程管理.pptx_咨信网zixin.com.cn

资源描述

1、第 2 章进程管理第二章第二章进程管理进程管理1.1 1.1 进程的基本概念进程的基本概念1.2 1.2 进程控制进程控制 1.3 1.3 进程的同步与互斥进程的同步与互斥1.4 1.4 经典的进程同步问题经典的进程同步问题1.5 1.5 管程机制管程机制1.6 1.6 进程通信进程通信1.7 1.7 线程线程第 2 章进程管理第第一一节节进程的基本概念第 2 章进程管理一、程序的顺序执行一、程序的顺序执行程序是一个在时间上有严格次序的指令序列。仅当前一操作(程序段)执行完后，才能执行后继操作。例如，在进行计算时，总须先输入用户的程序和数据，然后进行计算，

2、最后才能打印计算结果。第 2 章进程管理图 2-1 程序的顺序执行第 2 章进程管理在单道系统中，程序执行具有以下特征(P5)：(1)顺序性 (2)封闭性 (3)可再现性其中最大特征就是程序的顺序执行。第 2 章进程管理二、前趋图二、前趋图前趋图(Precedence Graph)是一个有向无循环图，记为DAG(Directed Acyclic Graph)，用于描述进程之间执行的前后关系。图中的每个结点可用于描述一个程序段或进程、一条语句；结点间的有向边则用于表示两个结点之间存在的偏序(Partial Order)或前趋关系(Precedence Rela

3、tion)“”。第 2 章进程管理 =(Pi,Pj)|Pi must complete before Pj may start,如果(Pi,Pj),可写成PiPj，称Pi是Pj的直接前趋，而称Pj是Pi的直接后继。在前趋图中，把没有前趋的结点称为初始结点(Initial Node)，把没有后继的结点称为终止结点(Final Node)。第 2 章进程管理每个结点还具有一个重量(Weight)，用于表示该结点所含有的程序量或结点的执行时间。图 2-2 前趋图第 2 章进程管理对于图 2-2(a)所示的前趋图，存在下述前趋关系：P1P2,P1P3,P1P4,P2P5,

4、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 章进程管理三、程序的并发执行三、程序的并发执行1、什么是程序的并发执行(回顾)程序的并发执行可进一步分为：不同程序间的并发执行；同一程序中不同程序段的并发执行。第 2 章进程管理并发程序的前趋图：第 2 章进程管理在该例中存在下述前趋关系：IiCi，I

5、iIi+1,CiPi,CiCi+1，PiPi+1 而Ii+1和Ci及Pi-1是重迭的，亦即在Pi-1和Ci以及Ii+1之间，可以并发执行。第 2 章进程管理对于具有下述四条语句的程序段，前趋图：S1:a=x+2 S2:b=y+4 S3:c=a+b S4:d=c+b 第 2 章进程管理 2、程序并发执行带来的影响：、程序并发执行带来的影响：程序运行的间断性；程序的执行失去了封闭性和以此为基础的可再现性；程序之间由于资源共享与竞争，形成了相互制约。第 2 章进程管理例如，有两个循环程序A和B，它们共享一个变量N。程序A每执行一次时，都要做N=N+1操作；程序B每执行一次

6、时，都要执行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。第 2 章进程管理为了合理管理系统资源、协调各程序段在执行时对资源的竞争，需要一个记录和描述程序执行过程的基本单位，于是引进了“进程”这一概念。第 2 章进程管理四、进程的定义四、进程的定义1、较典型的进程定义有：(1)进程是程序的一次执行。(

7、2)进程是一个程序及其数据在处理机上顺序执行时所发生的活动。(3)进程是程序在一个数据集合上运行的过程，它是系统进行资源分配和调度的一个独立单位。第 2 章进程管理四、进程的定义四、进程的定义2、进程实体：程序段、相关数据、PCB(进程控制块)-管理进程的数据结构3、进程的特征(p19-22)：(1)结构特征 (2)动态性 (3)并发性 (4)独立性 (5)异步性第 2 章进程管理在引入了进程实体的概念后，我们可以把传统OS中的进程定义为：“进程是进程实体的运行过程，是系统进行资源分配和调度的一个独立单位”第 2 章进程管理五、进程的三种基本状态五、进程的三种基本

8、状态(p23-24)就绪状态-就绪队列执行状态阻塞状态(等待状态)-等待队列第 2 章进程管理进程基本状态转换图进程基本状态转换图就绪就绪执行执行阻塞阻塞进程调度进程调度时间片用完时间片用完等待某个事件等待某个事件发生而阻塞发生而阻塞因等待的事因等待的事件已发生而件已发生而被唤醒被唤醒创建创建撤消撤消第 2 章进程管理图2-7 进程的五种基本状态及转换p31-33 第 2 章进程管理六、挂起状态六、挂起状态在一般OS中，进程只有以上三种基本状态。而在一些有特殊要求的OS中，由于控制的需要，引入“挂起”状态。“挂起”状态有静止就绪和静止阻塞两种。“挂起”就意味着暂

9、停对该进程分配CPU资源。第 2 章进程管理六、挂起状态六、挂起状态引起“挂起”的原因(P26-27)：(1)终端用户的请求。(2)父进程请求。(3)负荷调节的需要。(4)操作系统的需要。第 2 章进程管理图2-6 具有挂起状态的进程状态图调度第 2 章进程管理图2-8 具有创建、终止和挂起状态的进程状态图第 2 章进程管理七、进程控制块七、进程控制块(PCB)1、进程控制块：包含了进程的描述信息、控制信息、资源信息的数据结构。它随进程的创建而产生、在进程执行的过程中记录进程各信息的变化。当一个进程完成其功能后，系统则回收PCB，进程也随之消失。第

10、2 章进程管理 2、进程控制块的作用：标识进程的存在、动态地记录进程运行过程中的所有控制信息，如进程状态、中断现场、进程的优先级等，以便OS感知进程的存在，根据系统资源的情况和设计原则(算法)对进程(通过PCB)进行控制和管理。第 2 章进程管理 3.进程控制块中的信息进程控制块中的信息 1)进程标识符进程标识符用于惟一地标识一个进程。一个进程通常有两种标识符：(1)内部标识符。在所有的操作系统中，都为每一个进程赋予一个惟一的数字标识符，它通常是一个进程的序号。设置内部标识符主要是为了方便系统使用。(2)外部标识符。它由创建者提供，通常是由字母、数字组成，往往是由用户(进程)

11、在访问该进程时使用。为了描述进程的家族关系，还应设置父进程标识及子进程标识。此外，还可设置用户标识，以指示拥有该进程的用户。第 2 章进程管理 2)处理机状态处理机状态信息主要是由处理机的各种寄存器中的内容组成的。通用寄存器，又称为用户可视寄存器，它们是用户程序可以访问的，用于暂存信息，在大多数处理机中，有 832 个通用寄存器，在RISC结构的计算机中可超过 100 个；指令计数器，其中存放了要访问的下一条指令的地址；程序状态字PSW，其中含有状态信息，如条件码、执行方式、中断屏蔽标志等；用户栈指针，指每个用户进程都有一个或若干个与之相关的系统栈，用于存放过程和系统调用参数及调用地

12、址。栈指针指向该栈的栈顶。第 2 章进程管理 3)进程调度信息在PCB中还存放一些与进程调度和进程对换有关的信息，包括：进程状态，指明进程的当前状态，作为进程调度和对换时的依据；进程优先级，用于描述进程使用处理机的优先级别的一个整数，优先级高的进程应优先获得处理机；进程调度所需的其它信息，它们与所采用的进程调度算法有关，比如，进程已等待CPU的时间总和、进程已执行的时间总和等；事件，是指进程由执行状态转变为阻塞状态所等待发生的事件，即阻塞原因。第 2 章进程管理 4)进程控制信息进程控制信息包括：程序和数据的地址，是指进程的程序和数据所在的内存或外存地(首)址，以便再调度到

13、该进程执行时，能从PCB中找到其程序和数据；进程同步和通信机制，指实现进程同步和进程通信时必需的机制，如消息队列指针、信号量等，它们可能全部或部分地放在PCB中；资源清单，是一张列出了除CPU以外的、进程所需的全部资源及已经分配到该进程的资源的清单；链接指针，它给出了本进程(PCB)所在队列中的下一个进程的PCB的首地址。第 2 章进程管理在系统中存在的各种进程队列，就是由进程的PCB组成的。PCB组成队列的方式：链接方式索引方式第 2 章进程管理 1)链接方式图 2-7 PCB链接队列示意图第 2 章进程管理 2)索引方式图 2-8 按索引方式组织PCB 第

14、 2 章进程管理进程与程序的区别进程与程序的区别(1)程序是静态的，进程是动态的;(2)进程更能真实地描述并发,而程序不能;(3)一个程序可对应多个进程，反之亦然;(4)进程有生命周期，有诞生有消亡，是短暂的；而程序是相对长久的;第 2 章进程管理进程与程序的区别进程与程序的区别(5)程序可作为软件资源长期保存，进程只是一次执行过程，是暂时的；(6)进程是系统分配调度的独立单位，能与其他进程并发执行；(7)进程包含程序和数据两部分；(8)进程具有创建其他进程的功能，而程序没有。第 2 章进程管理第第二二节节进程控制第 2 章进程管理一、进程控制

15、的有关概念一、进程控制的有关概念1、进程控制：就是系统用一些具有特定功能的程序段来创建、终止进程，完成进程在各状态间的转换，从而达到多进程高效率并发执行和协调、实现资源共享的目的。第 2 章进程管理操作系统的进程控制机构属于os的内核，它是硬件的首次延伸，它通过执行各种原语来实现其控制功能。2、原语：是由若干机器指令构成的、完成特定功能的程序段。原语只能在系统状态(核心态)下被执行。原语的执行是不能被打断的。(p50)第 2 章进程管理 OS内核中包括的原语主要有：进程控制原语、进程通信原语、资源管理原语和其他方面的原语。其中，进程控制原语包括：创建原语、撤消原语、阻塞原语、

16、唤醒原语等等。第 2 章进程管理二、进程的创建二、进程的创建1、进程创建的两种方式：(1)由系统创建：在OS生成时建立的一些系统进程；一个应用系统被启动时最初的一些进程。第 2 章进程管理(2)由父进程创建：当一个进程执行，去完成所规定的功能时，它能创建一些子进程，使其各自分担其中的部分功能；子进程也可以创建自己的子进程。这样就形成了进程家族和进程树。在树型进程关系中，子进程可以继承其父进程所拥有的资源，在子进程撤消时继承的资源归还给父进程。第 2 章进程管理 2、进程树：描述进程家族关系的有向树图 2-9 进程树第 2 章进程管理 3.引起创建进程的事件引

17、起创建进程的事件(P53-55)(1)用户登录。(2)作业调度。(3)提供服务。(4)启动应用程序(应用请求)。第 2 章进程管理 4.进程创建原语的流程进程创建原语的流程(P56-58)(1)申请空白PCB。(2)为新进程分配资源。(3)初始化进程控制块。(4)将新进程(的PCB)插入就绪队列。第 2 章进程管理三、三、进程的终止进程的终止 1、引起进程终止引起进程终止(Termination of Process)的事件的事件 1)正常结束在任何计算机系统中，都应有一个用于表示进程已经运行完成的指示。例如，在批处理系统中，通常在程序的最后安排一条Holt指令或终止的系统

18、调用。当程序运行到Holt指令时，将产生一个中断，去通知OS本进程已经完成。在分时系统中，用户可利用Logs off去表示进程运行完毕，此时同样可产生一个中断，去通知OS进程已运行完毕。第 2 章进程管理 2)异常结束在进程运行期间，由于出现某些错误和故障而迫使进程终止。这类异常事件很多，常见的有：越界错误。这是指程序所访问的存储区，已越出该进程的区域；保护错。进程试图去访问一个不允许访问的资源或文件，或者以不适当的方式进行访问，例如，进程试图去写一个只读文件；非法指令。程序试图去执行一条不存在的指令。出现该错误的原因，可能是程序错误地转移到数据区，把数据当成了指令；特权指令错。用户

19、进程试图去执行一条只允许OS执行的指令；运行超时。进程的执行时间超过了指定的最大值；等待超时。进程等待某事件的时间，超过了规定的最大值；算术运算错。进程试图去执行一个被禁止的运算，例如，被0除；I/O故障。这是指在I/O过程中发生了错误等。第 2 章进程管理 3)外界干预外界干预并非指在本进程运行中出现了异常事件，而是指进程应外界的请求而终止运行。这些干预有：操作员或操作系统干预。由于某种原因，例如，发生了死锁，由操作员或操作系统终止该进程；父进程请求。由于父进程具有终止自己的任何子孙进程的权利，因而当父进程提出请求时，系统将终止该进程；父进程终止。当父进程终止时，OS也将他的所有子

20、孙进程终止。第 2 章进程管理 2.进程终止原语的工作流程进程终止原语的工作流程 (1)根据被终止进程的标识符，从PCB集合中检索出该进程的PCB，从中读出该进程的状态。(2)若被终止进程正处于执行状态，应立即终止该进程的执行，并置调度标志为真，用于指示该进程被终止后应重新进行调度。(3)若该进程还有子孙进程，还应将其所有子孙进程予以终止，以防他们成为不可控的进程。(4)将被终止进程所拥有的全部资源，或者归还给其父进程，或者归还给系统。(5)将被终止进程(它的PCB)从所在队列(或链表)中移出，等待其他程序来搜集信息。(归还给系统)第 2 章进程管理 1、引起阻塞与唤醒的事件：

21、(1)请求系统服务 (2)启动某种操作 (3)新数据尚未到达 (4)无新工作可做引起阻塞的事件，当事件被处理完成(事件结束)后必然引起唤醒。四、进程的阻塞与唤醒四、进程的阻塞与唤醒第 2 章进程管理注意：阻塞与唤醒原语是一对作用刚好相反的原语。因此，如果在某进程中调用了阻塞原语，则必须在与之合作的另一进程中或其他相关进程中，安排唤醒原语，以唤醒被阻塞的进程；否则，被阻塞的进程将会长期处于阻塞状态，从而无机会继续运行。第 2 章进程管理 2、进程的阻塞：(1)进程由于等待的某一事件没有发生而自己调用阻塞原语，将本进程置于等待状态。第 2 章进程管理 (2)进程阻塞原语

22、的流程进程阻塞原语的流程进程的阻塞是进程自身的一种主动行为。进程通过调用阻塞原语block自我阻塞。进入block过程后，由于此时该进程还处于执行状态，所以应先立即停止执行，把进程控制块中的现行状态由“执行”改为“阻塞”，并将PCB插入阻塞队列。如果系统中设置了因不同事件而阻塞的多个阻塞队列，则应将本进程插入到具有相同事件的阻塞(等待)队列。最后，CPU的使用权交给调度程序。调度程序进行重新调度，将处理机分配给另一就绪进程，并进行现场切换，亦即，保留被阻塞进程的处理机状态(在阻塞进程的PCB中)，再按新进程的PCB中的处理机状态设置CPU的环境。第 2 章进程管理 2、进程的唤醒：(

23、1)处于等待状态的进程所期待的某一事件发生了，由“发现者进程”(比如，用完并释放了等待进程需要的I/O设备的进程、传送来了等待进程所需数据的进程)启动唤醒原语，将对应的等待进程送入就绪队列。第 2 章进程管理（2）进程）进程唤醒原语的流程唤醒原语的流程首先把被阻塞的进程从等待该事件的阻塞队列中移出，将其PCB中的现行状态由阻塞改为就绪，然后再将该PCB插入到就绪队列中。第 2 章进程管理五、进程的挂起与激活五、进程的挂起与激活1、进程的挂起：由于出现了“挂起事件”，系统执行挂起原语，将某个进程挂起。2、进程的激活：当发生“激活事件”时，系统执行激活原语，将指定的进程激活。第

24、 2 章进程管理 3、进程挂起原语的流程首先检查被挂起进程的状态，若处于活动就绪状态，便将其改为静止就绪；对于活动阻塞状态的进程，则将之改为静止阻塞。再将进程的PCB移入相应队列。为了方便用户或父进程考查该进程的运行情况而把该进程的PCB复制到某指定的内存区域。最后，若被挂起的进程刚才正在执行，则转向调度程序重新调度。第 2 章进程管理 4、进程激活原语的流程激活原语先将进程从外存调入内存，检查该进程的现行状态，若是静止就绪，便将之改为活动就绪；若为静止阻塞便将之改为活动阻塞。再将进程的PCB移入相应队列。假如采用的是抢占调度策略，则每当有新进程进入就绪队列时，应检查是否要

25、进行重新调度，即由调度程序将被激活进程与当前进程进行优先级的比较，如果被激活进程的优先级更低，就不必重新调度；否则，立即剥夺当前进程的运行，把处理机分配给刚被激活的进程。第 2 章进程管理关于进程控制的原语，我们应该关注：(1)什么时候由于什么原因或发生了什么事件要执行；(2)由谁来执行；(3)原语的内部处理流程是什么。第 2 章进程管理第第三三节节进程的同步与互斥第 2 章进程管理一、进程间的相互制约关系一、进程间的相互制约关系进程间的相互制约关系是由于并发执行的进程间相互合作和共享资源而引起的。间接的相互制约关系(进程的互斥)：进程a-资源-进程b (共

26、享资源)直接的相互制约关系(进程的同步)：进程a-进程b (相互合作)第 2 章进程管理进程A1请求资源R3释放资源R进程B2请求资源R4释放资源R(阻塞)R分配拒绝使用R使用R唤醒进程A、B互斥分配第 2 章进程管理写进程Func1(x)放计算结果，并放计算结果，并设缓冲区满设缓冲区满读进程Func2(x)取结果，并清取结果，并清空缓冲区空缓冲区YN读、写进程同步缓冲区空？缓冲区空？YN缓冲区满？缓冲区满？阻塞阻塞阻塞阻塞唤醒唤醒第 2 章进程管理二、进程的互斥二、进程的互斥1、临界资源和临界区一次只允许一个进程使用的资源称为临界资源；各进程中对临界资源操作的

27、程序段称为临界区；并发进程中相对同一临界资源的临界区应互斥执行。第 2 章进程管理例：变量Count是临界资源P1:P2:Count=R1 Count=R2Count=Count+1 Count=Count-1R1=Count R2=Count 进程P1，P2并发执行。如果P1，P2的的临界区执行不互斥第 2 章进程管理 2、进程的互斥、进程的互斥两个或以上的进程不能同时使用同一临界资源，只能一个进程使用完了(资源完成了一个任务)另一个再使用，这种现象称为进程的互斥。也就是说，不允许两个以上的共享同一临界资源的并发进程同时进入临界区。第 2 章进程管理进程互斥执行

28、应遵循一定的原则(P88-89)：(1)空闲让进(2)忙则等待 (3)有限等待 (4)让权等待第 2 章进程管理 3、整型信号量和简单的、整型信号量和简单的P、V操作操作整型信号量是一个与资源的物理实体个数有关的整型变量，除初始化外，仅能通过两个标准的原子操作(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;释放一个资源第 2 章进程管理用整型信号量和简单的P、V

29、操作实现进程互斥：Pa：Pb：wait(s)wait(s)signal(s)signal(s)、分别是进程Pa、Pb中的临界区。第 2 章进程管理 4.记录型信号量和对应的记录型信号量和对应的P、V操作操作在整型信号量机制中的wait操作，只要是信号量S0，就会不断地测试。因此，该机制并未遵循“让权等待”的准则，而是使进程处于“忙等”的状态。记录型信号量机制，则是一种不存在“忙等”现象的进程同步机制。但在采取了“让权等待”的策略后，又会出现多个进程等待访问同一临界资源的情况，需要组织等待队列。第 2 章进程管理于是引进记录型信号量，描述为：type semaphore=re

30、cord value:integer;L:list of process;end第 2 章进程管理整型分量：是一个与资源的物理实体个数有关的整型变量，当其值 0时，代表供并发进程使用的某种资源的数量；当其值 0时，其绝对值代表目前等待该类资源的阻塞队列的长度。指针型分量：指向该类资源阻塞队列的头结点。第 2 章进程管理当信号量是记录型数据时，P、V操作被描述为：procedure wait(S)var S:semaphore;begin S.value=S.value-1;if S.value0 then block(S.L)；阻塞 end procedure signal

31、(S)var S:semaphore;begin S.value=S.value+1;if S.value0 then wakeup(S.L)；唤醒 end第 2 章进程管理 5、AND型信号量和对应的型信号量和对应的P、V操作操作多个进程共享多个资源时用记录型信号量和P、V操作实现进程的互斥，会出现死锁问题。于是引进AND型信号量，和与其对应的P、V操作。第 2 章进程管理 AND机制的基本思想是：将进程在整个运行过程中需要的所有资源，一次性全部地分配给进程，待进程使用完后再一起释放。只要尚有一个资源未能分配给进程，其它所有可能为之分配的资源，也不分配给他。亦即，对若干个临

32、界资源的分配，采取原子操作方式：要么全部分配到进程，要么一个也不分配。由死锁理论可知，这样就可避免上述死锁情况的发生。第 2 章进程管理对应的P、V操作定义如下：Swait(S1,S2,Sn)if S11 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 beginni

33、ng of Swait operation endif第 2 章进程管理 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;第 2 章进程管理 6、信号量集和对应的、信号量集和对应的P、V操作操作信号量集机制的基本思想是：一次分配若干类资源；每类资源一次分配一批(而不是一个)；当某类资源的空闲数量少于下限时，不分配该类资源。第 2 章进程管理信号量集下的信

34、号量集下的P、V操作：操作：Swait(S1,t1,d1,Sn,tn,dn);t-下限、d-一次分配的数量 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 beginning of the Swait Operation.endif第 2 章进程管理 signal(S1,d1,Sn,dn)fo

35、r i=1 to n do Si=Si+di;Remove all the process waiting in the queue associated with Si into the ready queue endfor;第 2 章进程管理用不同类型的信号量和其对应的P、V操作实现进程的互斥，形式是完全一样，只是P、V操作的意义不同。Pa：Pb：wait(s)wait(s)signal(s)signal(s)、分别是进程Pa、Pb中的访问资源S的临界区。第 2 章进程管理三、进程的同步三、进程的同步1、引例：A进程向缓冲区buf中放数据、B进程从buf中取数据打印。A

36、进程：do while buf 空 ;计算，得到一个结果；buf 一个结果；第 2 章进程管理 B进程：do while buf=空 ;取出buf中的数据，打印；清空buf；进程A和进程B是两个并发执行的、相互合作的进程。第 2 章进程管理 2、进程同步、进程同步如果引例中的进程A、B并发执行时不进行任何控制，会造成CPU资源的极大浪费。进程同步：异步环境下的一组并发进程，由于需要互发消息，相互合作，相互等待，从而相互制约彼此的执行速度，要以一定的速度向前推进。第 2 章进程管理 3、用信号量和、用信号量和P、V操作来实现进程操作来实现进程同步同步用前面介绍过的信号

37、量和P、V操作也可以实现进程的同步控制。对于引例，我们引入两个信号量s1和s2。s1=1，表示缓冲区为空，可以放数据，s1=0，表示缓冲区里放满了数据；s2=1，表示缓冲区内有数据供打印，s2=0，表示缓冲区里没有数据供打印。第 2 章进程管理进程同步的实现Pa：Pb：计算；wait(s2)wait(s1)从缓冲区取数据；向缓冲区中放数据；signal(s1)signal(s2)打印数据；第 2 章进程管理在这里，我们可以将P操作看成消耗一个资源，将V操作看成生产一个资源；进程Pa看作信号s1的消耗者，信号s2的产生者。反之，将进程Pa看作信号s1的消耗者，信号s2的产生者

38、。产生者和消耗者并发执行，通过信号量交换信息，可以合作完成任务。第 2 章进程管理四、四、利用信号量实现前趋关系利用信号量实现前趋关系图 2-10 前趋图举例第 2 章进程管理 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 w

39、ait(d);S5;signal(g);end;begin wait(e);wait(f);wait(g);S6;end;parend end 第 2 章进程管理私有信号量和共有信号量私有信号量和共有信号量在实现进程互斥时使用的信号量，标志着对并发执行的一组进程使用临界资源的制约，这样的信号量称为公有信号量；在实现进程同步时使用的信号量，使得生产进程和消耗进程之间能交换信息，不影响并发执行的其他进程。这样的信号量称为私有信号量。第 2 章进程管理第第四四节节经典的进程同步问题第 2 章进程管理一、生产者一、生产者-消费者问题消费者问题1、问题的描述：在计算机

40、系统中每个进程都在申请使用、释放各种不同类型的资源。我们把申请使用某类资源的进程，称为这类资源的消费者，把产生或释放某类资源的进程，称为这类资源的生产者。例如，在输入时，输入进程是数据的生产者，计算进程是数据的消费者；而在输出时，则计算进程是数据的生产者，而打印进程是数据的消费者。(对于硬件资源和数据资源，意义略有不同。)该问题有很大的代表性及实用价值。第 2 章进程管理 2、解决生产者消费者问题的方法例如，有一个大小为n的公共缓冲区，生产者进程向其中存入数据，消费者进程从其中取数据去打印。同步的问题描述为：(1)消费者要取数据，缓冲区中至少要有一个数据，否则消费者应等待；第 2 章

41、进程管理(2)生产者要存数据，缓冲区中至少要有一个空位置，否则生产者应等待；(3)缓冲区是一个临界资源，生产者和消费者对它的访问必须互斥进行。生产者和消费者通过缓冲区传递信息，它们具有同步关系；生产者和消费者都要访问临界资源-缓冲区，它们之间有互斥关系。可以同时存在多个生产者和多个消费者。第 2 章进程管理这里设三个信号量：empty：表示缓冲区目前的空单元数，初值为n(缓冲区的大小)；full：表示缓冲区中目前存放的未被打印数据的个数，初值为0；mutex：控制对缓冲区互斥访问的信号量，初值为1。其中empty、full是私有信号量，mutex是公有信号量。第 2 章进

42、程管理并发执行的生产者、消费者进程描述为：生产者：消费者：Wait(empty)Wait(full)Wait(mutex)Wait(mutex)向缓冲区存入从缓冲区取出一个数据；一个数据；Signal(full)Signal(empty)Signal(mutex)Signal(mutex)第 2 章进程管理 3、注意：(1)并发执行的、对于同一资源的生产者和消费者进程可以有多个；(2)在每个程序中用于实现互斥的wait(mutex)和signal(mutex)必须成对地出现；(3)实现同步时，对资源信号量empty和full的wait和signal操作，同样需要成对地出现，但它

43、们分别处于不同的程序中。(4)在每个程序中的多个wait操作顺序不能颠倒。应先执行对资源信号量的wait操作，然后再执行对互斥信号量的wait操作，否则可能引起进程死锁。第 2 章进程管理二、哲学家进餐问题二、哲学家进餐问题1、问题的描述：有5个哲学家共用一张圆桌，分别坐在周围的5张椅子上，在圆桌上有5个碗和5只筷子。他们的生活方式是交替的进行思考和进餐。平时，一个哲学家进行思考；饥饿是便试图取用其左右最靠近他的筷子；只有当他拿到两只筷子时，才能进餐。进餐毕，放下筷子，继续思考。第 2 章进程管理 2、利用记录型信号量解决哲学家进餐问题：经分析可知，放在桌子上的每个筷子都是临

44、界资源，在一段时间内只允许一位哲学家使用。为了实现对筷子的互斥使用，可以用一个信号量表示一只筷子，由这五个信号量构成信号量数组。其描述如下：Var chopstick:array0,4 of semaphore;第 2 章进程管理所有信号量均被初始化为1，第i位哲学家的活动可描述为：repeat wait(chopsticki);wait(chopstick(i+1)mod 5);eat;使用资源 signal(chopsticki);signal(chopstick(i+1)mod 5);think;until false;第 2 章进程管理由于这里是多个进程共享多个临界

45、资源，可能会出现死锁问题，解决的办法有：(1)至多只允许有四位哲学家同时去拿左边的筷子，最终能保证至少有一位哲学家能够进餐，并在用毕时能释放出他用过的两只筷子，从而使更多的哲学家能够进餐。(2)仅当哲学家的左、右两只筷子均可用时，才允许他拿起筷子进餐。第 2 章进程管理(3)规定奇数号哲学家先拿他左边的筷子，然后再去拿右边的筷子；而偶数号哲学家则相反。按此规定，将是1、2号哲学家竞争1号筷子；3、4号哲学家竞争3号筷子。即五位哲学家都先竞争奇数号筷子，获得后，再去竞争偶数号筷子，最后总会有一位哲学家能获得两只筷子而进餐。3、利用AND型信号量机制来实现对五只筷子的互斥使用：教材P62第

46、 2 章进程管理三、读者三、读者-写者问题写者问题1、问题描述：一个数据文件被多个进程共享，我们将只要求读文件的进程称为“读者”，将其他进程称为“写者”。允许多个读者同时对一个文件进行读操作，但不允许一个写者和其他读者、写者同时对一个文件进行读、写操作。第 2 章进程管理问题涉及的信号量：Wmutex：初值为1，用于读写进程间、或写写进程间实现互斥；公共变量Readcount：计数器，表示当前有多少个进程在读共享的数据文件，初值为0。每个读进程，开始执行时都要做Readcount+1，结束执行时都要做 Readcount-1。Rmutex：初值为1，用于实现对公共变量Rea

47、dcount的互斥访问；第 2 章进程管理读写进程间的制约关系：在读进程中，wait(Wmutex)通知“写者”第一个读者来了、signal(Wmutex)通知“写者”最后一个读者走了。所以，只有当Readcount=0时(目前没有读进程在读)，读进程才需要执行wait(Wmutex)；只有当读进程执行了Readcount-1后其值为0，它才需要执行signal(Wmutex)；这样就实现了读与写进程间的互斥；第 2 章进程管理 2、用记录型信号量实现读者写者问题：Var rmutex,wmutex:semaphore=1,1;Readcount:integer=0;begi

48、n parbegin Reader:begin repeat wait(rmutex);if readcount=0 then wait(wmutex);Readcount=Readcount+1;signal(rmutex);perform read operation;第 2 章进程管理 wait(rmutex);readcount =readcount-1;if readcount=0 then signal(wmutex);signal(rmutex);until false;end writer:begin repeat wait(wmutex);perform write

49、operation;signal(wmutex);until false;end parend end3、用信号量集机制实现读者写者问题：教材P64第 2 章进程管理第第五五节节管程机制第 2 章进程管理第第六六节节进程通信第 2 章进程管理 0、进程通信的分类、进程通信的分类1、低级通信：进程之间交换控制信息。一般只传送几个字节，达到控制进程执行速度的作用，由P、V原语来完成；进程的同步与互斥就是一种低级通信，信号量机制和P、V操作只能传递控制信号，控制信号本身不包含任何数据。第 2 章进程管理 2、高级通信：用信号量和P、V操作难于用在实现

50、进程间大批量的数据传送。（其主要原因参考教材P65）高级通信：用户在程序中利用操作系统提供的通信命令(系统调用)，高效、大批量地传送数据。高级通信的过程对用户是透明的。以下介绍的是进程间的高级通信。第 2 章进程管理一、进程通信的类型一、进程通信的类型1、共享存储器系统(Shared-Memory System)相互通信的进程共享某些数据结构或共享存储区，进程之间能够通过这些空间进行通信。据此，又可以把它们分为以下两种类型：(1)基于共享数据结构的方式 P151 (2)基于共享存储区的方式 P152第 2 章进程管理 2、消息传递系统(Message passing syst

展开阅读全文