第二进程管理

《第二进程管理》由会员分享，可在线阅读，更多相关《第二进程管理（148页珍藏版）》请在装配图网上搜索。

1、第二章 进 程 管 理 辽东学院信息技术学院第二章第二章 进程管理进程管理 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.1 进程的基本概念进程的基本概念 2.1.1 程序的顺序执行及其特征程序的顺序执行及其特征 I:输入数据C:处理数据O:输出结果数据处理程序ICOI1C1O1前趋图第二章 进 程 管 理 辽东学院信息技术学院a:=x+y;b:=a*5;C:=a+6

2、D:=a/cS1:S2:S3:S4:S1S2S3(1)顺序性：(2)封闭性：(3)可再现性：S4 程序运行时独占全机资源 环境和初始条件环境和初始条件相同，运行多次相同，运行多次获得相同的结果获得相同的结果第二章 进 程 管 理 辽东学院信息技术学院 2.1.3 程序的并发执行及其特征程序的并发执行及其特征I:输入数据C:处理数据O:输出结果数据处理程序ICOI1C1O1I2C2O2第二章 进 程 管 理 辽东学院信息技术学院a:=x+y;b:=a*5;C:=a+6;D:=a/cS1:S2:S3:S4:S1S2S4S3(1)间断性：执行-暂停-执行(2)失去封闭性：资源共享(3)不可再现性：不

3、可再现性：结果不同第二章 进 程 管 理 辽东学院信息技术学院不可再现性不可再现性 例如，有两个程序A和B，它们共享一个变量N。程序A每执行一次时，都要做N=N+1操作；程序B每执行一次时，都要执行Print(N)操作。程序A和B以不同的速度运行。第二章 进 程 管 理 辽东学院信息技术学院程序A程序BWhile(1)n:=n+1;While(1)print n;某时刻，N=9：程序程序A得到的得到的N值为：值为：10程序B得到的N值为：10第二章 进 程 管 理 辽东学院信息技术学院循环程序A循环程序BWhile(1)n:=n+1;While(1)print n;某时刻，N=9：程序B得到的

4、N值为：9第二章 进 程 管 理 辽东学院信息技术学院2.1.4 进程的特征与状态进程的特征与状态 1.进程的特征和定义进程的特征和定义 1)结构特征：进程控制块（PCB）+数据+程序段2)动态性：进程一次执行过程；产生、灭亡3)并发性 ：并发执行4)独立性：独立运行、独立分配资源、独立调度单位 5)异步性：不可预知速度运行进程引入原因进程引入原因：程序并发执行三大特性不能参与并发，并发+动态描述-进程第二章 进 程 管 理 辽东学院信息技术学院 较典型的进程定义有：(1)进程是程序的一次执行。(2)进程是一个程序及其数据在处理机上顺序执行时所发生的活动。(3)进程是程序在一个数据集合上运行的

5、过程，它是系统进行资源分配和调度的一个独立单位。在引入了进程实体的概念后，我们可以把传统OS中的进程定义为：“进程是进程实体的运行过程，是系统进行资源分配和调度的一个独立单位”。第二章 进 程 管 理 辽东学院信息技术学院进程与程序的区别进程与程序的区别(1)程序是指令的有序集合，其本身没有任何运行的含义，是一个程序是指令的有序集合，其本身没有任何运行的含义，是一个静态静态的概念。而进程是程序在处理机上的一次执行过程，它是一的概念。而进程是程序在处理机上的一次执行过程，它是一个个动态动态的概念。的概念。(2)程序可以作为一种软件资料长期存在，而程序可以作为一种软件资料长期存在，而进程是有一定生

6、命期进程是有一定生命期的的。程序是。程序是永久永久的，进程是的，进程是暂时暂时的。的。(3)进程更能真实地描述进程更能真实地描述并发并发，而程序不能，而程序不能(4)进程进程包括程序包括程序和数据和数据+PCB两部分两部分(5)进程具有进程具有创建其他进程创建其他进程的功能，而程序没有的功能，而程序没有(6)同一程序同时运行于若干个数据集合上，它将属于若干个不同同一程序同时运行于若干个数据集合上，它将属于若干个不同的进程。也就是说的进程。也就是说同一程序可以对应多个进程同一程序可以对应多个进程 第二章 进 程 管 理 辽东学院信息技术学院思考？思考？为什么引入进程的概念？为什么引入进程的概念？

7、第二章 进 程 管 理 辽东学院信息技术学院2.进程的三种基本状态进程的三种基本状态(1)就绪(Ready)状态(2)执行状态(3)阻塞状态 第二章 进 程 管 理 辽东学院信息技术学院进程的三种基本状态及其转换 执执 行行阻阻 塞塞就就 绪绪时间片完时间片完 I/OI/O请求请求 进程调度进程调度 I/OI/O完成完成第二章 进 程 管 理 辽东学院信息技术学院3.挂起状态挂起状态1)引入挂起状态的原因引入挂起状态的原因(1)终端用户的请求。(2)父进程请求。(3)负荷调节的需要。(4)操作系统的需要。第二章 进 程 管 理 辽东学院信息技术学院2)进程状态的转换(1)活动就绪静止就绪(挂起

8、)。(2)活动阻塞静止阻塞。(3)静止就绪活动就绪。(4)静止阻塞活动阻塞。第二章 进 程 管 理 辽东学院信息技术学院具有挂起状态的进程状态图具有挂起状态的进程状态图 请求请求I/OI/O静止静止阻塞阻塞活动活动阻塞阻塞静止静止就绪就绪活动活动就绪就绪执行执行挂起挂起挂起挂起挂起挂起激活激活激活激活唤醒唤醒唤醒唤醒时间片到时间片到CPU调度调度第二章 进 程 管 理 辽东学院信息技术学院4 4创建状态和终止状态创建状态和终止状态1)创建状态 创建一个进程两步骤：为一个新进程创建创建PCBPCB，并填写必要的管理信息；其次，把该进程转入就绪状态并插入就绪队列之插入就绪队列之中。刚创建进程 还未

9、进入主存，即创建工作尚未完成，进程还不能被调度运行，其所处的状态就是创建状态。2)终止状态 进程自然结束点、出现了无法克服的错误、或是被操作系统所终结、或是被其他有终止权的进程所终结，它将进入终止状态。进程的终止也要通过两个步骤：首先等待操作系统进行善后处理善后处理 ，然后将其PCBPCB清零清零，并将PCB空间返还系统。第二章 进 程 管 理 辽东学院信息技术学院创建就绪阻塞执行终止许可I/O请求释放I/O完成时间片完进程调度进程的五种基本状态及转换 第二章 进 程 管 理 辽东学院信息技术学院请求请求I/OI/O静止静止阻塞阻塞活动活动阻塞阻塞静止静止就绪就绪活动活动就绪就绪执行执行挂起挂

10、起挂起挂起挂起挂起激活激活激活激活唤醒唤醒唤醒唤醒时间片到时间片到CPU调度调度终止终止释放释放创建创建许可许可许可许可七状态转换图第二章 进 程 管 理 辽东学院信息技术学院思考？思考？1如果单如果单CPU系统中有系统中有N个进程，运行的用户进程最多几个，个进程，运行的用户进程最多几个，最少几个；阻塞的用户进程最多几个，最少几个？最少几个；阻塞的用户进程最多几个，最少几个？2.有没有这样的状态转换，为什么？有没有这样的状态转换，为什么？阻塞阻塞运行；运行；就绪就绪阻塞阻塞第二章 进 程 管 理 辽东学院信息技术学院2.1.5 进程控制块进程控制块 1.进程控制块的作用进程控制块的作用 进程控

11、制块的作用是使一个在多道程序环境下不能独立运行的程序(含数据)，成为一个能独立运行的基本单位，一个能与其它进程并发执行的进程。或者说，OS是根据PCB来对并发执行的进程进行控制和管理的。为了描述一个进程和其它进程以及系统资源的关系，为了刻画一为了描述一个进程和其它进程以及系统资源的关系，为了刻画一个进程在各个不同时期所处的状态，人们采用了一个与进程相联个进程在各个不同时期所处的状态，人们采用了一个与进程相联系的数据块，称为进程控制块（系的数据块，称为进程控制块（PCB）。）。系统利用系统利用PCB来控制和管理进程，所以来控制和管理进程，所以PCB是系统是系统感知进程存在感知进程存在的唯一标志的

12、唯一标志进程与进程与PCB是一一对应的是一一对应的第二章 进 程 管 理 辽东学院信息技术学院2.进程控制块中的信息进程控制块中的信息 进程标识符现行状态现场保留区程序与数据地址互斥与同步机构进程通信机构进程优先数资源清单链接字家族关系内部标识符外部标识符描述信息现场信息控制及资源管理信息第二章 进 程 管 理 辽东学院信息技术学院3.进程控制块的组织方式进程控制块的组织方式 1)链接方式 PCB链接队列示意图 1 PCB9 0 PCB8 9 PCB7 7 PCB6 PCB5 8 PCB4 0 PCB3 3 PCB2 4 PCB1就绪队列指针就绪队列指针阻塞队列指针阻塞队列指针空闲队列指针空闲

13、队列指针执行指针执行指针链接方式：链接方式：第二章 进 程 管 理 辽东学院信息技术学院2)索引方式 按索引方式组织PCB PCB7PCB6PCB5PCB4PCB3PCB2PCB1执行指针执行指针就绪表指针就绪表指针阻塞表指针阻塞表指针就绪索引表就绪索引表阻塞索引表阻塞索引表索引方式：索引方式：第二章 进 程 管 理 辽东学院信息技术学院思考？思考？何时会发生进程切换？何时会发生进程切换？进程切换进程切换指一个进程进处理器,另一个进程出处理器的过程。若有一个进程从运行态变成阻塞态或就绪态（进程的状态发生改变）,或完成工作后就撤消,则必定会发生进程切换。第二章 进 程 管 理 辽东学院信息技术学

14、院2.2 进进 程程 控控 制制 2.2.1 进程的创建进程的创建 1.进程图(Process Graph)图 2-9 进程树 DEFGHBCIJKLMA进程控制就是对系统中的所有进程实施管理，进程控制就是对系统中的所有进程实施管理，进程控制一般有进程控制一般有原语原语来实现。来实现。原语是由若干条指令组成，用于完成一定原语是由若干条指令组成，用于完成一定功能的一个过程。其特点是原语执行时不可功能的一个过程。其特点是原语执行时不可被中断被中断。常用原语：常用原语：创建原语创建原语Creat()终止原语终止原语Terminal()阻塞原语阻塞原语Block()、唤醒原语、唤醒原语Wakeup()

15、描述一个进程的家族关系的有向图。PCB第二章 进 程 管 理 辽东学院信息技术学院2.引起创建进程的事件引起创建进程的事件(1)用户登录。分时系统，系统(2)作业调度。批处理系统，系统(3)提供服务。打印进程，系统(4)应用请求。应用进程自己创建第二章 进 程 管 理 辽东学院信息技术学院3.进程的创建进程的创建(Creation of Progress)OS调用调用Creat()原语原语|申请一申请一空闲空闲PCB，获得数字标识符，获得数字标识符|分配必要的资源分配必要的资源|初始化初始化PCB:标识信息到标识信息到PCB;处理机和进程状态；处理机和进程状态；|插入就绪队列插入就绪队列第二章

16、 进 程 管 理 辽东学院信息技术学院2.2.2 进程的终止进程的终止 1.引起进程终止引起进程终止(Termination of Process)的事件的事件 1)正常结束正常结束：产生中断：产生中断-OS 2)异常结束异常结束：越界；保护错：越界；保护错rw;非法指令；运行非法指令；运行超时；程序错；超时；程序错；I/O错错 3)外界干预外界干预 ：操作员或者：操作员或者OS终止；父进程请求；终止；父进程请求；父进程终止父进程终止 第二章 进 程 管 理 辽东学院信息技术学院 2.进程的终止过程进程的终止过程 OS调用终止原语，过程：(1)从PCB集合中检索出该进程的检索出该进程的PCB，

17、从中读出该进程的状态。(2)若被终止进程正处于执行状态，应立即终止该进程的执行，并置调度标志为真，用于指示该进程被终止后应重新进行调度。(3)若该进程还有子孙进程子孙进程，还应将其所有子孙进程予以终止子孙进程予以终止。(4)将被终止进程所拥有的全部资源，或者归还归还给其父进程，或者归还给系统。(5)将被终止进程(PCB)从所在队列(或链表)中移出移出，等待其他程序来搜集信息。第二章 进 程 管 理 辽东学院信息技术学院2.2.3 进程的阻塞与唤醒进程的阻塞与唤醒1.引起进程阻塞和唤醒的事件引起进程阻塞和唤醒的事件 1)请求系统服务 2)启动某种操作：如果启动I/O必须等待完成 3)新数据尚未到

18、达：合作进程 4)无新工作可做：对于某些服务系统进程第二章 进 程 管 理 辽东学院信息技术学院 2.进程阻塞过程进程阻塞过程 正在执行的进程，当发现上述某事件时，由于无法继续执行，于是进程进程便通过调用阻塞原语便通过调用阻塞原语block把自己阻塞把自己阻塞。可见，进程进程的阻塞是进程自身的一种的阻塞是进程自身的一种主动行为主动行为。进入block过程后，保存CPU现场 置进程的状态插入阻塞(等待)队列 转进程调度第二章 进 程 管 理 辽东学院信息技术学院 3.进程唤醒过程进程唤醒过程 当被阻塞进程所期待的事件出现时，如I/O完成或其所期待的数据已经到达，则由有关进程由有关进程(比如，用完

19、并释放了该I/O设备的进程)调用唤醒原语wakeup()，将等待该事件的进程唤醒唤醒。唤醒原语执行的过程是：从阻塞队列中移出被唤醒进程置进程的状态将被唤醒进程送入就绪队列转进程调度或返回阻塞阻塞-唤醒唤醒第二章 进 程 管 理 辽东学院信息技术学院2.2.4 进程的挂起与激活进程的挂起与激活 1.进程的挂起进程的挂起 当出现了引起进程挂起的事件时（用户进程请求；父进程用户进程请求；父进程请求；负荷调节；请求；负荷调节；OS需要）需要），系统将利用挂起原语suspend()将指定进程或处于阻塞状态的进程挂起。挂起原语的执行过程：活动就绪活动就绪状态-便将其改为静止就绪静止就绪；活动阻塞活动阻塞状

20、态的进程-静止阻塞静止阻塞。第二章 进 程 管 理 辽东学院信息技术学院 2.进程的激活过程进程的激活过程 当发生激活进程的事件时，例如，父进程或用户进程请求请求激活指定进程，系统将利用激活原语激活原语active()将指定进程激活将指定进程激活。激活原语：静止就绪静止就绪-活动就绪活动就绪；静止阻塞静止阻塞-活动阻塞活动阻塞。挂起挂起-激活激活对换：将进程从外存调入内存从外存调入内存第二章 进 程 管 理 辽东学院信息技术学院思考？思考？为什么创建进程要用原语来实现？为什么创建进程要用原语来实现？请设想一下进程在什么情况下会变为阻塞状态？请设想一下进程在什么情况下会变为阻塞状态？阻塞进程在什

21、么情况下会被唤醒？谁来唤醒它？阻塞进程在什么情况下会被唤醒？谁来唤醒它？第二章 进 程 管 理 辽东学院信息技术学院复习 程序顺序执行时的特征程序顺序执行时的特征 程序并发执行时的特征程序并发执行时的特征 进程的特征和定义进程的特征和定义 进程与程序的区别进程与程序的区别 进程的三种基本状态及转换图进程的三种基本状态及转换图 什么是进程控制块什么是进程控制块?它的作用它的作用?OS何时会发生进程切换？何时会发生进程切换？第二章 进 程 管 理 辽东学院信息技术学院 2.3.1进程同步的基本概念进程同步的基本概念 1两种形式的制约关系两种形式的制约关系 (1)间接相互制约关系间接相互制约关系。同

22、处于一个系统中的进。同处于一个系统中的进程，通常都程，通常都共享着某种系统资源共享着某种系统资源。(2)直接相互制约关系直接相互制约关系。这种制约主要源于进程。这种制约主要源于进程间的合作。间的合作。2.3 进进 程程 同同 步步 进程同步：进程同步：对多个相关进程在执行次序上进行协调执行次序上进行协调，使系统中诸进程之间能有效地共享资源和相互合作，从而使程序的执行具有可再现性。可再现性。同步机制同步机制：用来实现同步的机制称作同步机制。：用来实现同步的机制称作同步机制。第二章 进 程 管 理 辽东学院信息技术学院2.同步和互斥同步和互斥 第二章 进 程 管 理 辽东学院信息技术学院如：打印机

23、、内存单元、表格 第二章 进 程 管 理 辽东学院信息技术学院repeat entry section /进入区 critical section；/临界区 exit section /退出区 remainder section；/剩余代码 until false；第二章 进 程 管 理 辽东学院信息技术学院5同步机制应遵循的规则同步机制应遵循的规则(1)空闲让进空闲让进。当无进程处于临界区时，应允许一个请求进入临界区的进程立即进入自己的临界区。(2)忙则等待忙则等待。当已有进程进入临界区时，其它试图进入临界区的进程必须等待，以保证对临界资源的互斥访问。(3)有限等待有限等待。对要求访问临界资

24、源的进程，应保证在有限时间内能进入自己的临界区，以免陷入“死等”状态。(4)让权等待让权等待。当进程不能进入自己的临界区时，应立即释放处理机，以免进程陷入“忙等”状态。第二章 进 程 管 理 辽东学院信息技术学院第二章 进 程 管 理 辽东学院信息技术学院记录型信号量定义 type semaphore=record value:integer；L:list of process；end Value-代表资源数目 一个进程链表指针L，用于链接上述的所有等待进程第二章 进 程 管 理 辽东学院信息技术学院P操作操作(Wait操作操作)：申请一个单位资源：申请一个单位资源V操作操作(Signal操作

25、操作)：释放一个单位资源：释放一个单位资源第二章 进 程 管 理 辽东学院信息技术学院若若S=0，继续，继续s=s-1当当S.value0时，表示该类资源已分配完毕，因此进程应调用时，表示该类资源已分配完毕，因此进程应调用block原语，进行自我阻塞，放弃处理机，并插入到信号量链表原语，进行自我阻塞，放弃处理机，并插入到信号量链表S.L中中第二章 进 程 管 理 辽东学院信息技术学院V(s):若若S0，继续，继续s=s+1对信号量的每次signal操作，表示执行进程释放一个单位资源若加1后仍是S.value0，则表示在该信号量链表中，仍有等待该资源的进程被阻塞，故还应调用wakeup原语，将S

26、.L链表中的第一个等待进程唤醒第二章 进 程 管 理 辽东学院信息技术学院例：例：1台打印机，台打印机，A和和B进程申请使进程申请使用打印机，进程互斥，正确使用。用打印机，进程互斥，正确使用。第二章 进 程 管 理 辽东学院信息技术学院互斥信号量互斥信号量mutex（初值为（初值为1）Semphore:mutex=1临界区P(mutex)P(mutex)V(mutex)V(mutex)第二章 进 程 管 理 辽东学院信息技术学院信号量及P、V操作讨论 对于两个并发进程争用同一个临界资源，互斥信号量的值仅取1、0和-1三个值 若UTEX1表示没有进程进入临界区 若UTEX0表示有一个进程进入临界

27、区 若UTEX-1表示一个进程进入临界区，另一个进程等待进入。第二章 进 程 管 理 辽东学院信息技术学院思考 对于N个并发进程争用同一个临界资源，互斥信号量的取值范围是什么，有什么含义。第二章 进 程 管 理 辽东学院信息技术学院例：供者和用者对单缓冲区的同步例：供者和用者对单缓冲区的同步供者负责通过读卡机往缓冲区中输入数供者负责通过读卡机往缓冲区中输入数据据用者则负责从缓冲区中取出数据用于处用者则负责从缓冲区中取出数据用于处理理第二章 进 程 管 理 辽东学院信息技术学院同步信号量：同步信号量：S1缓冲区资源（初值为缓冲区资源（初值为1）S2数据资源（初值为数据资源（初值为0）P(S2)V

28、(S2)V(S1)第二章 进 程 管 理 辽东学院信息技术学院1)信号量的物理含义：S0表示有S个资源可用S=0表示无资源可用S0则|S|表示S等待队列中的进程个数P(S)：表示申请一个资源 V(S)：表示释放一个资源。信号量的初值应该大于等于信号量的初值应该大于等于0 0信号量及P、V操作讨论（续1）第二章 进 程 管 理 辽东学院信息技术学院【思考题】司机进程：司机进程：while(1)while(1)启动车辆启动车辆正常驾驶正常驾驶到站停车到站停车 售票员进程：售票员进程：while(1)while(1)关门关门售票售票开门开门 用用P.VP.V操作解决司机与售票员的问题操作解决司机与售

29、票员的问题第二章 进 程 管 理 辽东学院信息技术学院司机进程：司机进程：while(1)while(1)启动车辆启动车辆正常驾驶正常驾驶 到站停车到站停车 售票员进程：售票员进程：while(1)while(1)关门关门 售票售票开门开门 同步信号量：同步信号量：S1开车信号量（初值为开车信号量（初值为0）S2开门信号量（初值为开门信号量（初值为0）V(S1)V(S2)P(S2)第二章 进 程 管 理 辽东学院信息技术学院2)P.V操作必须成对出现，有一个P操作就一定有一个V操作当为互斥操作时，它们同处于同一进程当为同步操作时，则不在同一进程中出现如果P(S1)和P(S2)两个操作在一起，那

30、么P操作的顺序至关重要。一个同步P操作与一个互斥P操作在一起时同步P操作在互斥P操作前而两个V操作无关紧要信号量及P、V操作讨论（续2）第二章 进 程 管 理 辽东学院信息技术学院3）P、V操作的优缺点优点：简单，而且表达能力强（用P、V操作可解决任何同步互斥问题）缺点：不够安全，P、V操作使用不当会出现死锁；遇到复杂同步互斥问题时实现复杂信号量及P、V操作讨论（续3）第二章 进 程 管 理 辽东学院信息技术学院三、利用P、V操作解决合作进程的执行次序 若干个进程为了完成一个共同任务而并发执行，在这些进程中，有些进程之间有次序的要求，有些进程之间没有次序的要求，为了描述方便，可以用一个图来表示

31、进程集合的执行次序。如图P1P2P3P4P1P2P3P4P5P6P1P2P3 P4sf1)串行2)串/并行3)并行第二章 进 程 管 理 辽东学院信息技术学院例题1如图，试用信号量实现这三个进程的同步。Pa：V(SB);V(SC);Pb：P(SB);Pc：P(SC);PaPbPcSBSC为进程Pa和Pb设置共享公用信号量SB，为进程Pa和Pc设置共享公用信号量SC，初值均为0第二章 进 程 管 理 辽东学院信息技术学院【思考题1】如图，试用信号量实现这三个进程的同步。如图，试用信号量实现这三个进程的同步。PaPbPcSBSC第二章 进 程 管 理【思考题2】如图，试用信号量实现这6个进程的同步

32、S12S13S14S45S26P3P1P2P4P5P6S35S56为进程P1和P2设置共享公用信号量S12，P1和P3设置共享公用信号量S13，P1和P4设置共享公用信号量S14，P2和P6设置共享公用信号量S26，P3和P5设置共享公用信号量S35，P4和P5设置共享公用信号量S45，P5和P6设置共享公用信号量S56，P1进程进程V(S12);V(S13)；V(S14);P2进程进程 P(S12);V(S26);P3进程进程 P(S13);V(S35）;P4进程进程P(S14);V(S45)；P5进程进程 P(S35);P(S45);V(S56);初值均为初值均为0第二章 进 程 管 理

33、辽东学院信息技术学院P5进程进程 P(S35);P(S45);V(S56);P1进程进程V(S12);V(S13)；V(S14);P2进程进程 P(S12);V(S26);P3进程进程 P(S13)V(S35）P4进程进程P(S14);V(S45)；P6进程进程P(S26);P(S56);P3P1P2P4P5P6第二章 进 程 管 理 辽东学院信息技术学院 总结总结进程互斥进程互斥：在OS中，当某一进程正在访问cs时，就不允许其它进程来读写(访问)，否则就会发生后果无法估计的错误，进程之间的这种相互制约关系为进程互斥。进程同步：进程同步：并发进程在一些关键点上可能需要互相等待与互通消息，这种相

34、互制约的等待与互通消息，称为进程同步。第二章 进 程 管 理 辽东学院信息技术学院进程同步与互斥关系：进程同步与互斥关系：都反映了在异步环境下并发进程间的相互制约关系。可归于同步范畴，但互斥是同步问题的一个特例，互斥解决临界区的使用，同步是并发进程在一些关键点上需互相等待互发消息。第二章 进 程 管 理 辽东学院信息技术学院2.4经典的进程同步问题 生产者/消费者问题 读者/写者问题 哲学家进餐问题 管程机制第二章 进 程 管 理 辽东学院信息技术学院2.4.1生产者/消费者问题描述 通过一个有界缓冲池(包含N个缓冲区)可以把一群生产者p1,p2,pm，和一群消费者Q1,Q2,Qn联系起来。如

35、图 只要缓冲池未满，生产者就可以把消息送入缓冲池;只要缓冲池未空，消费者就可以从缓冲区中取走消息。第二章 进 程 管 理 辽东学院信息技术学院同步信号量：S1空缓冲区数=n；S2满缓冲区数=0互斥信号量 mutex=1 第二章 进 程 管 理 辽东学院信息技术学院图.生产者(m)：P消费者(n)：QBuffer(n-1)n个缓冲区(Buffer)Buffer(0)Buffer(i)生产消息；申请空缓冲区；放消息；指针 移动；满缓冲区+1；申请满缓冲区；取消息；指针 移动；释放空缓冲区；消费消息；Buffer(i)i:0，n-1i=(i+1)%nBuffer(j)j:0，n-1j=(j+1)%n

36、同步信号量：S1空缓冲区数，n；S2满缓冲区数，0。互斥信号量：mutex，1第二章 进 程 管 理 辽东学院信息技术学院图生产者(m)：P消费者(n)：Q生产消息；申请空缓冲区；放消息；指针 移动；满缓冲区+1；申请满缓冲区；取消息；指针 移动；释放空缓冲区；消费消息；Buffer(i)i:0，n-1i=(i+1)%nBuffer(j)j:0，n-1j=(j+1)%n同步信号量：S1空缓冲区数，n；S2满缓冲区数，0;互斥信号量：mutex，1.Message bufferm;i,j=0;生产者生产者P：i=0;while(1)生产消息生产消息;P(S1);P(mutex);往往Buffer

37、 i放消息放消息;i=(i+1)%n;V(mutex);V(S2);消费者消费者Q：j=0;while(1)P(S2);P(mutex);从从Bufferj取消息取消息;j=(j+1)%n;V(mutex);V(S1);消费消息消费消息;第二章 进 程 管 理 辽东学院信息技术学院【思考题】如果生产者消费者问题中的缓冲池是无界的，又该如何解呢？第二章 进 程 管 理 辽东学院信息技术学院Buffer(0)Buffer(1)Buffer(i)生产者(m)：P消费者(n)：Q生产消息；放消息；指针 移动；满缓冲区+1；申请满缓冲区；取消息；指针 移动；消费消息；Buffer(i)i=i+1Buff

38、er(j)j=j+1互斥信号量：mutex，1同步信号量：S1满缓冲区，0。第二章 进 程 管 理 辽东学院信息技术学院Q：J=0;while(1)P(S1);P(mutex);从Bufferj取消息;j=j+1;V(mutex);消费消息;互斥信号量：mutex，1同步信号量：S1满缓冲区，0。P：i=0;while(1)生产消息;P(mutex);往Buffer i放消息;i=i+1;V(mutex);V(S1);第二章 进 程 管 理 辽东学院信息技术学院【练习题】有一个仓库，可以存放A和B两种产品，但要求：（1）每次只能存入一种产品（A或B）（2）NA产品数量B产品数量M。其中，N和M

39、是正整数。试用P、V操作描述产品A与B的入库过程。分析：(1)互斥地使产品入库(2)A-BM，B-AN，A产品的数量不能比B产品的数量少N个以上，A产品的数量不能比B产品的数量多M个以上 第二章 进 程 管 理 辽东学院信息技术学院仓库生产产品申请入库A产品入库允许B多放入一个A产品入库B产品入库A-BM，B-A=3)，每个位置可存放一，每个位置可存放一个车架或一个车轮；有一组工人负责生产个车架或一个车轮；有一组工人负责生产车架车架，另一组工人负责生产，另一组工人负责生产车轮车轮，第三组工人负责第三组工人负责组装自行车组装自行车，用，用P,V描述三组工人操作过程。描述三组工人操作过程。工人1

40、Repeat 加工一个车架 车架放入箱中 工人2 Repeat 加工一个车轮 车轮放入箱中工人3Repeat取一个车架;取2个车轮;组装一台自行车信号量：信号量：s 箱子空位置箱子空位置=n；s1 车架车架=0；s2车轮车轮=0；mutex=1P(s)P(mutex)V(mutex)V(s1)P(s)P(mutex)V(mutex)V(s2)P(s1);P(mutex)V(mutex)P(s2);P(s2);P(mutex)V(mutex)V(s);V(s);V(s)信号量：信号量：s 箱子空位置箱子空位置=n;s1 车架车架=0；s2车轮车轮=0；mutex=1 cj 车架最多位置车架最多位

41、置=n-2;cl 车轮最多位置车轮最多位置=n-1P(cj)P(cl)V(cj);V(cl);V(cl)第二章 进 程 管 理 辽东学院信息技术学院2.4.4 管程(monitor)机制信号量同步的缺点：信号量同步的缺点：同步操作分散：同步操作分散：信号量机制中，同步操作分散在各个进程中，使用不当就可能导致各进程死锁;易读性差：易读性差：要了解对于一组共享变量及信号量的操作是否正确，必须通读整个系统或者并发程序；不利于修改和维护：不利于修改和维护：各模块的独立性差，任一组变量或一段代码的修改都可能影响全局；正确性难以保证：正确性难以保证：操作系统或并发程序通常很大，很难保证这样一个复杂的系统没

42、有逻辑错误；第二章 进 程 管 理 辽东学院信息技术学院 管程的基本概念管程的基本概念 管程的定义：管程是关于共享资源的数据结构及一组针对该资源的操作过程所构成的软件模块。管程可增强模块的独立性：引入管程可提高代码的可读性，便于修改和维护，正确性易于保证 管程被请求和释放资源的进程所调用第二章 进 程 管 理 辽东学院信息技术学院条件变量条件变量(condition)(condition)在管程内部可以说明和使用一种特殊类型在管程内部可以说明和使用一种特殊类型的变量的变量-条件变量条件变量。每个条件变量表示。每个条件变量表示一种阻塞原因，并不取具体数值相一种阻塞原因，并不取具体数值相当于每个原

43、因对应一个队列当于每个原因对应一个队列。第二章 进 程 管 理 辽东学院信息技术学院 同步操作原语C.wait和C.signal：针对条件变量c，执行C.wait（c）的进程将自己阻塞在c队列中，C.signal(c)将c队列中的一个进程唤醒。q C.signal(c)操作的作用，是重新启动一个被阻塞的进程，但如果没有进程被阻塞，则C.signal(c)操作不产生任何效果，这与信号量机制中的signal操作不同。条件变量条件变量(condition)(condition)第二章 进 程 管 理 辽东学院信息技术学院管程中的多个进程进入管程中的多个进程进入 当一个进入管程的进程执行唤醒操作时（如

44、进程唤醒进程），管程结构不允许被唤醒的进程重新执行（管程内只能有一个进程）。这种情况有三种可能的解决办法：P等待Q继续，直到Q等待或退出；Hoare采用。Q等待P继续，直到P等待或退出；Lampson和Redell采用。规定唤醒为管程中最后一个可执行的操作，这样被唤醒的进程可以立即执行。第二章 进 程 管 理 辽东学院信息技术学院管程示意图管程示意图urgent queue第二章 进 程 管 理 辽东学院信息技术学院5.5.管程的组成管程的组成第二章 进 程 管 理 辽东学院信息技术学院管程的组成管程的组成 名称名称：数据结构说明数据结构说明：一组局部于管程的共享变量 操作原语操作原语：对共享

45、变量进行操作的一组原语过程（程序代码），初始化代码初始化代码：对控制变量进行初始化的代码第二章 进 程 管 理 辽东学院信息技术学院2.5.2 利用管程解决利用管程解决生产者生产者-消费者问题消费者问题参见参见P60第二章 进 程 管 理 辽东学院信息技术学院管程机制管程机制(复习复习)引入原因引入原因 过多信号量的使用，容易造成死锁过多信号量的使用，容易造成死锁 管程的基本概念管程的基本概念 把数据及其上的一组操作看作一个整体把数据及其上的一组操作看作一个整体管程管程 管程组成管程组成 名称名称 局部于管程的局部变量局部于管程的局部变量 局部于管程的数据初值设置局部于管程的数据初值设置 在数

46、据上的一组操作在数据上的一组操作第二章 进 程 管 理 辽东学院信息技术学院2.5 2.5 进程的通信进程的通信进程之间的信息交换进程之间的信息交换-进程通信进程通信低级通信进程同步低级通信进程同步进程的同步，简单的信号交换进程的同步，简单的信号交换如：锁、信号量如：锁、信号量高级通信进程通信高级通信进程通信高效、大量数据传递高效、大量数据传递第二章 进 程 管 理 辽东学院信息技术学院2.5.1 2.5.1 高级进程通信的类型高级进程通信的类型共享存储器系统共享存储器系统消息传递系统消息传递系统管道通信系统管道通信系统第二章 进 程 管 理 辽东学院信息技术学院n 基于共享数据结构的通信方式

47、基于共享数据结构的通信方式 在这种通信方式中，诸进程在这种通信方式中，诸进程公用某些数据结构公用某些数据结构，借以实，借以实现诸进程间的信息交换。现诸进程间的信息交换。生产者生产者-消费者消费者 缓冲区缓冲区 程程 序序 员：员：提供对公用数据结构的设置提供对公用数据结构的设置 及对进程间同步的控制及对进程间同步的控制 操作系统：提供共享存储器操作系统：提供共享存储器 特特 点点：低效，只适合传递相对少量的数据。低效，只适合传递相对少量的数据。n基于共享存储区的通信方式基于共享存储区的通信方式 在存储器中划出了一块共享存储区，诸进程可通过对在存储器中划出了一块共享存储区，诸进程可通过对共共享存

48、储区享存储区中数据的读或写来实现通信。中数据的读或写来实现通信。特点特点：传输大量数据：传输大量数据1.1.共享存储器系统共享存储器系统 在共享存储器系统中，相互通信的进程共享某些在共享存储器系统中，相互通信的进程共享某些数据结构或共享数据结构或共享存储区存储区，进程之间能够通过这些空间进行通信。，进程之间能够通过这些空间进行通信。第二章 进 程 管 理 辽东学院信息技术学院 消息传递系统：消息传递系统：进程间的数据交换，以格式化的消息进程间的数据交换，以格式化的消息为单位。为单位。在计算机网络中消息称为报文。程序员直接利用系统在计算机网络中消息称为报文。程序员直接利用系统提供的一组通信命令提

49、供的一组通信命令(原语原语)进行通信。进行通信。2.消息传递系统消息传递系统3.管道通信管道通信 所谓所谓“管道管道”，是指用于连接一个读进程和一个写进程以，是指用于连接一个读进程和一个写进程以实现他们之间通信的一个共享文件，又名实现他们之间通信的一个共享文件，又名pipe文件。文件。第二章 进 程 管 理 辽东学院信息技术学院 在进程之间通信时，源进程可以直接或间接地将消息传在进程之间通信时，源进程可以直接或间接地将消息传送给目标进程。送给目标进程。1.直接通信方式直接通信方式通信原语：通信原语：Send(Receiver,message);发送一个消息给接收进程发送一个消息给接收进程Rec

50、eive(Sender,message);接收接收Sender发来的消息发来的消息2.5.2 2.5.2 消息传递通信的实现方法消息传递通信的实现方法第二章 进 程 管 理 辽东学院信息技术学院2.间接通信方式间接通信方式信箱信箱 消息在信箱中可以安全地保存，只允许核准的目标用户随时消息在信箱中可以安全地保存，只允许核准的目标用户随时读取。读取。利用信箱通信方式，既可实时通信，又可非实时通信。利用信箱通信方式，既可实时通信，又可非实时通信。系统为信箱通信提供若干原语：系统为信箱通信提供若干原语：信箱的创建和撤消信箱的创建和撤消消息的发送和接收消息的发送和接收 信箱由操作系统创建信箱由操作系统创

51、建 Send(mailbox,message);将一个消息发送到指定信箱将一个消息发送到指定信箱 Receive(mailbox,message);从指定信箱中接收一个消息从指定信箱中接收一个消息第二章 进 程 管 理 辽东学院信息技术学院信箱的分类：信箱的分类：私用信箱：用户进程创建私用信箱：用户进程创建 公用信箱：公用信箱：OS 共享信箱共享信箱:进程创建并指明进程创建并指明利用利用信箱信箱通信时，发送进程和接收进程之间的四种关通信时，发送进程和接收进程之间的四种关系：系：一对一关系一对一关系 多对一关系多对一关系 一对多关系一对多关系 多对多关系多对多关系第二章 进 程 管 理 辽东学院

52、信息技术学院2.5.3 2.5.3 消息缓冲队列通信机制消息缓冲队列通信机制 发送进程利用发送进程利用SendSend原语，将消息原语，将消息直接直接发送给发送给接收进程；接受进程则利用接收进程；接受进程则利用ReceiveReceive原语接收消息。原语接收消息。1.消息缓冲队列通信机制中的数据结构消息缓冲队列通信机制中的数据结构(1)(1)消息缓冲区消息缓冲区type message buffer=record sender;发送者进程标识符发送者进程标识符 size;消息长度消息长度 text;消息正文消息正文 next;指向下一个消息缓冲区的指针指向下一个消息缓冲区的指针 end第二章

53、 进 程 管 理 辽东学院信息技术学院(2)PCB中有关通信的数据项中有关通信的数据项 增加用于对消息队列进行操作和实现同步的信号量，并增加用于对消息队列进行操作和实现同步的信号量，并将它们置入进程的将它们置入进程的PCB中。中。type processcontrol block=record mq;消息队列队首指针消息队列队首指针 mutex;消息队列互斥信号量消息队列互斥信号量 sm;消息队列资源信号量消息队列资源信号量 end2.6.4 2.6.4 消息缓冲队列通信机制消息缓冲队列通信机制第二章 进 程 管 理 辽东学院信息技术学院text:Hello size:5sender:Asen

54、d(B,a)sm mutex mq next:0text:Hellosize:5sender:Atext:Hello size:5sender:Areceive(b)发发送送区区a接接收收区区b 进程进程A 进程进程B第一消息缓冲区第一消息缓冲区PCB(B)第二章 进 程 管 理 辽东学院信息技术学院2.发送原语发送原语 发送进程在利用发送原语发送消息之前，应先在自己的发送进程在利用发送原语发送消息之前，应先在自己的内存空间，设置一发送区内存空间，设置一发送区a a，把待发送的消息正文、发送进，把待发送的消息正文、发送进程标识符、消息长度等信息填入其中，然后调用发送原语，程标识符、消息长度等信

55、息填入其中，然后调用发送原语，把消息发送给目标把消息发送给目标(接收接收)进程。发送原语首先根据发送区进程。发送原语首先根据发送区a a中所设置的消息长度中所设置的消息长度a.sizea.size来申请一缓冲区来申请一缓冲区i i，接着，把发，接着，把发送区送区a a中的信息复制到缓冲区中的信息复制到缓冲区i i中。中。为了将为了将i 挂在接收进程的消息队列挂在接收进程的消息队列mq上，应先获得接收进上，应先获得接收进程的内部标识符程的内部标识符j，然后将，然后将i 挂在挂在j.mq上。上。由于队列属于临界资源，所以执行由于队列属于临界资源，所以执行insert操作的前后，都操作的前后，都要执

56、行要执行wait和和signal操作。操作。procedure send(receiver,a)begin getbuf(a.size,i);根据根据a.size申请缓冲区申请缓冲区 i.sender:=a.sender;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);end2.6.4 2.6.4 消息缓冲队列通信机制消息缓冲队列通信机制将消息缓冲区插

57、入消息队列将消息缓冲区插入消息队列将发送区将发送区a中的信息复制到中的信息复制到消息缓冲区中消息缓冲区中第二章 进 程 管 理 辽东学院信息技术学院3.接收原语接收原语 接收进程调用接收原语接收进程调用接收原语receive(b)receive(b)，从自己的消息缓，从自己的消息缓冲队列冲队列mqmq中，摘下第一个消息缓冲区中，摘下第一个消息缓冲区i i，并将其中的数据复，并将其中的数据复制到以制到以b b为首址的指定消息接受区内。为首址的指定消息接受区内。procedure receive(b)begin j:=internal name;j为接收进程内部标识符为接收进程内部标识符 wait

58、(j.sm);wait(j.mutex);remove(j.mq,i);将将消息队列中的第消息队列中的第i i个消息移出个消息移出 signal(j.mutex);b.sender:=i.sender;b.size:=i.size;将将消息缓冲区消息缓冲区i i中的信息中的信息 b.text:=i.text;复制到接收区复制到接收区b b end2.6.4 2.6.4 消息缓冲队列通信机制消息缓冲队列通信机制第二章 进 程 管 理 辽东学院信息技术学院2.6 线程线程(THREAD)进程是一个可拥有资源的独立单位进程是一个可拥有资源的独立单位进程是一个可独立调度的基本单位进程是一个可独立调度的

59、基本单位系统进行的操作：系统进行的操作：创建进程创建进程撤销进程撤销进程进程切换进程切换 进程的基本属性进程的基本属性 第二章 进 程 管 理 辽东学院信息技术学院引入引入进程进程 的目的：的目的：使多个程序能并发执行，提高使多个程序能并发执行，提高资源利用率资源利用率和系统和系统吞吞吐量吐量。引入引入线程线程 的目的：的目的：减少程序在并发执行时所付出的减少程序在并发执行时所付出的时空开销时空开销，使，使OSOS具具有更好的并发性。有更好的并发性。1.1.线程的引入线程的引入2.7.1 线程的基本概念线程的基本概念第二章 进 程 管 理 辽东学院信息技术学院2.2.线程的概念线程的概念 线程

60、：进程中一个相对独立的执行流。线程：进程中一个相对独立的执行流。进程进程/线程线程 进程是资源分配单位进程是资源分配单位 线程是线程是CPU执行单位执行单位 多线程优点多线程优点 切换速度快（地址空间不变）切换速度快（地址空间不变）系统开销小系统开销小 通讯容易（共享数据空间）通讯容易（共享数据空间）第二章 进 程 管 理 辽东学院信息技术学院3.线程的属性线程的属性(1)轻型实体。(2)独立调度和分派的基本单位。(3)可并发执行。(4)共享进程资源。第二章 进 程 管 理 辽东学院信息技术学院 4.线程的状态线程的状态 (1)状态参数。在OS中的每一个线程都可以利用线程标识符和一组状态参数进

61、行描述。状态参数通常有这样几项：寄存器状态，它包括程序计数器PC和堆栈指针中的内容；堆栈，在堆栈中通常保存有局部变量和返回地址；线程运行状态，用于描述线程正处于何种运行状态；优先级，描述线程执行的优先程度；线程专有存储器，用于保存线程自己的局部变量拷贝；信号屏蔽，即对某些信号加以屏蔽。第二章 进 程 管 理 辽东学院信息技术学院 (2)线程运行状态。执行状态，表示线程正获得处理机而运行；就绪状态，指线程已具备了各种执行条件，一旦获得CPU便可执行的状态；阻塞状态，指线程在执行中因某事件而受阻，处于暂停执行时的状态。第二章 进 程 管 理 辽东学院信息技术学院 5.线程的创建和终止线程的创建和终

62、止 在多线程OS环境下，应用程序在启动时，通常仅有一个线程在执行，该线程被人们称为“初始化线程”。它可根据需要再去创建若干个线程。在创建新线程时，需要利用一个线程创建函数(或系统调用)，并提供相应的参数，如指向线程主程序的入口指针、堆栈的大小，以及用于调度的优先级等。在线程创建函数执行完后，将返回一个线程标识符供以后使用。终止线程的方式有两种：一种是在线程完成了自己的工作后自愿退出；另一种是线程在运行中出现错误或由于某种原因而被其它线程强行终止。第二章 进 程 管 理 辽东学院信息技术学院例：例：Java-Thread类类 JavaJava线程状态之间的转换关系图线程状态之间的转换关系图 Sl

63、eep()Suspend()Waiting I/O RunnableSuspendDeadNewStart()Stop()Resume()第二章 进 程 管 理 辽东学院信息技术学院6.多线程多线程OS中的进程中的进程 在多线程OS中，进程是作为拥有系统资源的基本单位，通常的进程都包含多个线程并为它们提供资源，但此时的进程就不再作为一个执行的实体。多线程OS中的进程有以下属性：(1)作为系统资源分配的单位。(2)可包括多个线程。(3)进程不是一个可执行的实体。第二章 进 程 管 理 辽东学院信息技术学院7.7.线程与进程的比较线程与进程的比较(1)(1)u线程：线程：作为作为CPU调度单位。调

64、度单位。n线程只拥有必不可少的资源，如：线程状态、寄存器上下文线程只拥有必不可少的资源，如：线程状态、寄存器上下文和栈和栈n同样具有就绪、阻塞和执行三种基本状态同样具有就绪、阻塞和执行三种基本状态u进程：进程：其它资源分配单位（存储器、文件、其它资源分配单位（存储器、文件、IO等）。等）。第二章 进 程 管 理 辽东学院信息技术学院调度：调度：线程线程作为作为CPU调度的基本单位，而进程只作为其它资源调度的基本单位，而进程只作为其它资源分配单位。分配单位。并发性：并发性：进程之间可以并发，且一个进程的多个线程之进程之间可以并发，且一个进程的多个线程之间亦可并发。间亦可并发。拥有资源：拥有资源：

65、进程间相互独立，同一进程的各线程间共享进程间相互独立，同一进程的各线程间共享资源。某进程内的线程在其它进程不可见。资源。某进程内的线程在其它进程不可见。系统开销：系统开销：线程上下文切换比进程上下文切换要快得多线程上下文切换比进程上下文切换要快得多7.7.线程与进程的比较线程与进程的比较(2)(2)第二章 进 程 管 理 辽东学院信息技术学院2.7.2 线程间的同步和通信线程间的同步和通信 1.1.互斥锁互斥锁(mutex)(mutex)互斥锁用于线程对资源的互斥访问互斥锁用于线程对资源的互斥访问 互斥锁有两种状态：开、关互斥锁有两种状态：开、关 互斥锁的操作：关锁互斥锁的操作：关锁lockl

66、ock、开锁、开锁unlockunlock第二章 进 程 管 理 辽东学院信息技术学院 下面给出了对上述资源的申请(左半部分)和释放(右半部分)操作的描述。Lock mutex Lock mutex check data structures;mark resource as free;while(resource busy);unlock mutex;wait(condition variable);wakeup(condition variable);mark resource as busy;unlock mutex;第二章 进 程 管 理 辽东学院信息技术学院3.信号量机制信号量机制 (1)私用信号量(private samephore)。当某线程需利用信号量来实现同一进程中各线程之间的同步时，可调用创建信号量的命令来创建一私用信号量，其数据结构是存放在应用程序的地址空间中。私用信号量属于特定的进程所有，OS并不知道私用信号量的存在，因此，一旦发生私用信号量的占用者异常结束或正常结束，但并未释放该信号量所占有空间的情况时，系统将无法使它恢复为0(空)，也不能将它传送给下一个请求