第2章进程管理(精品).ppt

《第2章进程管理(精品).ppt》由会员分享，可在线阅读，更多相关《第2章进程管理(精品).ppt（201页珍藏版）》请在taowenge.com淘文阁网|工程机械CAD图纸|机械工程制图|CAD装配图下载|SolidWorks_CaTia_CAD_UG_PROE_设计图分享下载上搜索。

1、第二章进程管理2.1 进程的基本概念2.2 进程的控制2.3 进程同步2.4 经典进程的同步问题2.5 进程通信2.6 线程主要内容主要内容目的和要求目的和要求 通过本章的学习，使学生掌握并理解进通过本章的学习，使学生掌握并理解进程的概念，理解进程的基本状态及其转换的程的概念，理解进程的基本状态及其转换的典型原因，掌握进程生命周期内的创建与撤典型原因，掌握进程生命周期内的创建与撤消、阻塞与唤醒、挂起与激活等操作的执行消、阻塞与唤醒、挂起与激活等操作的执行过程，并理解和掌握进程的同步机制。过程，并理解和掌握进程的同步机制。重点和难点重点和难点1 1、多道程序设计；、多道程序设计；2 2、进程和并

2、发执行；、进程和并发执行；3 3、进程的同步机制进程的同步机制；4 4、线程的概念。、线程的概念。2.1 进程的基本概念2.2.1.1 1.1 程序的顺序执行及其特征程序的顺序执行及其特征程序：程序：一个在时间上按严格次序、顺序执行一个在时间上按严格次序、顺序执行 的操作序列的操作序列 程序的顺序执行：程序的顺序执行：一个具有独立功能的程序一个具有独立功能的程序 独占处理机，直至得到最终结果的过程独占处理机，直至得到最终结果的过程 操作：操作：数据处理的一种规则，一经启动就需数据处理的一种规则，一经启动就需 要在有限时间内完成要在有限时间内完成 计算：计算：若干操作严格顺序执行的集合若干操作严

3、格顺序执行的集合1.1.程序的顺序执行程序的顺序执行 一个具有独立功能的程序独占处理机，直一个具有独立功能的程序独占处理机，直至得到最终结果的过程至得到最终结果的过程；通常一个程序可分为若干程序段，它们必通常一个程序可分为若干程序段，它们必须按照一定的顺序执行，仅当前趋操作执行须按照一定的顺序执行，仅当前趋操作执行后才能执行后继操作后才能执行后继操作；如果用如果用前趋图前趋图描述各程序段的执行顺序，描述各程序段的执行顺序，则呈线性结构则呈线性结构。顺序性顺序性 一个程序的各个部分的执行，严格地按一个程序的各个部分的执行，严格地按照某种先后序执行照某种先后序执行 封闭性封闭性 程序在封闭的环境下

4、运行，即程序运行程序在封闭的环境下运行，即程序运行时独占全部系统资源，资源的状态只有本程时独占全部系统资源，资源的状态只有本程序改变。序改变。2.2.顺序执行的特征顺序执行的特征 可再现性可再现性 只要程序执行时的环境和初始条件相同，只要程序执行时的环境和初始条件相同，当程序重复执行时，不论它是从头到尾不停当程序重复执行时，不论它是从头到尾不停顿地执行，还是顿地执行，还是“停停走走停停走走”地执行，都将地执行，都将获得相同的结果获得相同的结果3.3.性能评价性能评价 优点：程序的顺序执行为程序的调试带来很优点：程序的顺序执行为程序的调试带来很大方便大方便 缺点：资源利用率不高缺点：资源利用率不

5、高 2.2.1.2 1.2 前趋图前趋图1.1.定义定义 前趋图是有向无环图，记为前趋图是有向无环图，记为DAG 前趋图中的每个结点可以表示一条语句、一前趋图中的每个结点可以表示一条语句、一 个程序段或一个进程个程序段或一个进程 结点间的结点间的有向边有向边表示两个结点之间存在的偏表示两个结点之间存在的偏 序或前趋关系序或前趋关系 (Pi,Pj)|在在Pj开始前开始前Pi必须完成必须完成 如果（如果（Pi，Pj），可写成可写成PiPj，Pi是是 Pj的直接前趋，的直接前趋，Pj 是是 Pi 的直接后继的直接后继2.2.说明说明 前趋图中不能出现环路前趋图中不能出现环路 前趋图可用来表示语句、程

6、序段或进程之前趋图可用来表示语句、程序段或进程之间执行的先后顺序间执行的先后顺序 如果如果PiPiPjPj，则则PiPi必须先于必须先于PjPj执行执行 如果如果Pi Pi PjPj，则则PiPi和和PjPj可以任意顺序执行可以任意顺序执行2.2.1.3 1.3 程序并发执行及其特征程序并发执行及其特征1.1.并发环境并发环境 在一定时间内物理机器上有两个或两在一定时间内物理机器上有两个或两个以上的程序同处于个以上的程序同处于开始运行、但尚未结开始运行、但尚未结束束的状态，并且起始时间、推进速度、结的状态，并且起始时间、推进速度、结束时间均是束时间均是不可预知不可预知的的2.2.程序的并发执行

7、程序的并发执行 是指多个程序的执行在时间上是重叠的是指多个程序的执行在时间上是重叠的 如果不同程序的若干程序段如果不同程序的若干程序段使用的资源不同使用的资源不同且且不存在合作关系不存在合作关系，则允许，则允许同时同时执行执行 如果用前趋图描述多个程序的各程序段的执如果用前趋图描述多个程序的各程序段的执行顺序，则呈网状结构行顺序，则呈网状结构并发执行举例并发执行举例 例例1 1 输输入入、计计算算、打打印印三三个个程程序序对对一一批批作作业业进进行行处处理时，存在以下的前趋关系：理时，存在以下的前趋关系：IiIiCiCi，IiIi+1IiIi+1，CiCiPiPi，CiCi+1CiCi+1，P

8、iPi+1PiPi+1在在Pi-1Pi-1和和CiCi以及以及Ii+1Ii+1之间，可以并发执行之间，可以并发执行I1I2I3I4C1C2C3C4P1P2P3P4例例2 2 对于具有下述四条语句的程序段：对于具有下述四条语句的程序段：S1:a=x+2S1:a=x+2 S2:b=y+4 S2:b=y+4 S3:c=a+b S3:c=a+b S4:d=c+b S4:d=c+b 3.3.并发执行的特征并发执行的特征 间断性间断性 程程序序并并发发执执行行时时，由由于于它它们们共共享享资资源源或或程程序序之之间间相相互互合合作作完完成成一一项项共共同同任任务务，因因而而使使程序之间相互制约程序之间相互

9、制约 失去封闭性失去封闭性 程程序序并并发发执执行行时时，多多个个程程序序共共享享系系统统资资源源，资资源源的的状状态态由由多多个个程程序序改改变变，运运行行环环境境失失去去封闭性。封闭性。不可再现性不可再现性 由由于于程程序序的的并并发发执执行行，打打破破了了由由另另一一程程序序独独占占系系统统资资源源的的封封闭闭性性，因因而而破破坏坏了可再现性。了可再现性。例如例如：程序程序A A和程序和程序B B共享变量共享变量N N A A：N=N+1;N=N+1;B B：PrintPrint（N N）；）；N=0 N=0；由于执行速度不同，导致执行结果各异由于执行速度不同，导致执行结果各异.性能评价

10、性能评价 优点：提高资源利用率和系统吞吐量优点：提高资源利用率和系统吞吐量 缺点：容易出现缺点：容易出现与时间有关的错误与时间有关的错误 不可再现性是不允许的！不可再现性是不允许的！必须通过必须通过 Berstein Berstein 条件条件 的限制，保证的限制，保证程序在异步环境下的执行结果是确定的。程序在异步环境下的执行结果是确定的。读集读集R(Pi)R(Pi)：为程序为程序PiPi在执行期间所需在执行期间所需参考的所有变量的集合参考的所有变量的集合 写集写集W(Pi)W(Pi)：为程序为程序PiPi在执行期间所要在执行期间所要改变的所有变量的集合改变的所有变量的集合 程序程序P1P1和

11、和P2P2能够并发执行，应满足能够并发执行，应满足Bernstein Bernstein 条件：条件：R(P1)W(P2)R(P2)W(P1)W(P1)W(P2)=BersteinBerstein条件条件2.1.4 2.1.4 进程的特征与状态进程的特征与状态1.1.进程的定义与特征进程的定义与特征【进程的定义】【进程的定义】进程是程序的一次执行进程是程序的一次执行 进程是程序在数据集合上的一次运行过程进程是程序在数据集合上的一次运行过程 进程是进行进程是进行资源分配资源分配和和调度执行调度执行的独立单位；的独立单位；进程由程序段、数据段和进程由程序段、数据段和 PCB PCB 三部分组成三部

12、分组成【进程的特征】【进程的特征】思考思考：进程与程序的区别：进程与程序的区别?结构特征结构特征 为了控制和管理进程，系统为每个进程设为了控制和管理进程，系统为每个进程设置进程控制块置进程控制块PCBPCB，进程由进程由PCBPCB、程序段和数程序段和数据段组成据段组成 动态性动态性 进程的实质是程序的一次执行过程，因此，进程的实质是程序的一次执行过程，因此，动态特征是进程最重要的特征动态特征是进程最重要的特征并发性并发性 没有为之建立进程的程序是不能并发执行的，没有为之建立进程的程序是不能并发执行的，仅当为之建立一个进程后才能参加并发执行仅当为之建立一个进程后才能参加并发执行 独立性独立性

13、进程是资源分配的基本单位，也是调度执行进程是资源分配的基本单位，也是调度执行的独立单位的独立单位 异步性异步性 由于进程间的相互制约，使进程具有执行的由于进程间的相互制约，使进程具有执行的间断性，即进程按各自独立的、不可预知的速间断性，即进程按各自独立的、不可预知的速度向前推进度向前推进 作业是向计算机提交的任务实体，而进程是作业是向计算机提交的任务实体，而进程是 用户任务的执行实体用户任务的执行实体 一个作业可由多个进程组成，但必须至少由一个作业可由多个进程组成，但必须至少由 一个进程组成，反之不然一个进程组成，反之不然 作业的概念主要用在批处理系统中，而进程作业的概念主要用在批处理系统中，

14、而进程 的概念用于所有的多道系统中的概念用于所有的多道系统中*进程与作业的区别进程与作业的区别*2.2.进程的三种基本状态进程的三种基本状态 就绪状态就绪状态 当进程分配到除当进程分配到除 CPU CPU 以外所有必要的资源，以外所有必要的资源，只要再获得只要再获得CPUCPU即可运行的状态即可运行的状态 处于就绪状态的进程排成就绪队列等待处于就绪状态的进程排成就绪队列等待 进程调度进程调度 执行状态执行状态 已获得已获得CPUCPU且正在运行的状态且正在运行的状态 单处理机系统只有一个处于运行状态的进程单处理机系统只有一个处于运行状态的进程 阻塞状态阻塞状态 正在执行的进程因发生某事件而暂停

15、执行正在执行的进程因发生某事件而暂停执行的状态，也称的状态，也称等待等待或或睡眠睡眠状态状态 将处于阻塞状态的进程按将处于阻塞状态的进程按阻塞原因阻塞原因排成不排成不同的阻塞队列同的阻塞队列 引起阻塞的事件消失后，进程不会立即恢引起阻塞的事件消失后，进程不会立即恢复到执行状态，而转变为就绪状态等待重新复到执行状态，而转变为就绪状态等待重新调度调度执行执行就绪就绪阻塞阻塞进程的状态及转换进程的状态及转换进程的状态及转换进程的状态及转换 就绪就绪执行：执行：CPUCPU空闲，引起进程调度空闲，引起进程调度 执行执行就绪：就绪：当前进程的当前进程的CPUCPU被剥夺（被剥夺（2 2种）种）执行执行阻

16、塞：阻塞：当前进程因等待某个事件而当前进程因等待某个事件而 无法执行，主动放弃无法执行，主动放弃CPUCPU 阻塞阻塞就绪：就绪：阻塞进程等待的事件出现，阻塞进程等待的事件出现，被唤醒到就绪队列，再次竞争被唤醒到就绪队列，再次竞争CPUCPU 3.3.挂起状态挂起状态 引入挂起状态的原因引入挂起状态的原因 终端用户的请求终端用户的请求 父进程的请求父进程的请求 负荷调节的需要负荷调节的需要 操作系统的需要操作系统的需要 处于挂起状态的进程是静止的处于挂起状态的进程是静止的 进程状态的转换进程状态的转换 通过通过挂起原语挂起原语将进程由将进程由活动活动状态变为状态变为静止静止状态：状态：活动就绪

17、活动就绪静止就绪：处于静止就绪状态的静止就绪：处于静止就绪状态的进程不再被调度执行；进程不再被调度执行；活动阻塞活动阻塞静止阻塞：处于静止阻塞状态的静止阻塞：处于静止阻塞状态的进程在期待的事件出现后，从静止阻塞变为进程在期待的事件出现后，从静止阻塞变为静止就绪；静止就绪；处于执行状态的进程被挂起后，变为静止就处于执行状态的进程被挂起后，变为静止就绪状态，不再参与调度。绪状态，不再参与调度。通过通过激活原语激活原语将进程由将进程由静止静止状态变为状态变为活动活动状态：状态：静止就绪静止就绪活动就绪：处于静止就绪状态活动就绪：处于静止就绪状态的进程变为活动就绪状态，等待进程调度；的进程变为活动就绪

18、状态，等待进程调度；静止阻塞静止阻塞活动阻塞：静止阻塞状态的进活动阻塞：静止阻塞状态的进程变为活动阻塞状态，等待期待的事件发生程变为活动阻塞状态，等待期待的事件发生而进入就绪队列。而进入就绪队列。具有挂起状态的进程状态图具有挂起状态的进程状态图4.4.创建状态和终止状态创建状态和终止状态 创建状态创建状态 已分配了已分配了PCBPCB 已填写了进程标识符等信息已填写了进程标识符等信息 尚未送入就绪队列（比如内存不足）尚未送入就绪队列（比如内存不足）增加管理的灵活性增加管理的灵活性 终止状态终止状态 PCB PCB 从所在队列移出从所在队列移出 暂时由辅助程序保留以便收集数据暂时由辅助程序保留以

19、便收集数据 尚未撤消尚未撤消PCBPCB 进行记账信息的收集进行记账信息的收集终止终止创建创建就绪就绪阻塞阻塞执行执行许可许可释放释放等待事件等待事件事件发生事件发生进程调度进程调度时间片完时间片完进程的五种基本状态及其转换进程的五种基本状态及其转换2.1.5 2.1.5 进程控制进程控制块块PCBPCB1.1.PCBPCB的作用的作用 系统为了管理进程设置的数据结构，存放系统为了管理进程设置的数据结构，存放了用于描述进程情况和控制进程运行所需的了用于描述进程情况和控制进程运行所需的全部信息全部信息 系统利用系统利用 PCB PCB 来控制和管理进程，所以来控制和管理进程，所以PCBPCB是系

20、统感知进程存在的是系统感知进程存在的唯一标志唯一标志 进程与进程与PCBPCB是一一对应的是一一对应的.PCBPCB的内容的内容 描述信息描述信息内部标识符：系统赋予进程的数字序号内部标识符：系统赋予进程的数字序号外部标识符：创建者提供和使用的标识符外部标识符：创建者提供和使用的标识符家族关系：父进程、子进程标识符，家族关系：父进程、子进程标识符，以及用户标识符以及用户标识符mainA1A2A3A21 现场信息现场信息运行时，保存在运行时，保存在CPU中；中断时，保存在中；中断时，保存在PCB中。中。通用寄存器：暂存中间结果等；通用寄存器：暂存中间结果等；指令计数器指令计数器PCPC：下一条指

21、令的内存地址；下一条指令的内存地址；程序状态字程序状态字PSWPSW：条件码、中断允许位、中条件码、中断允许位、中断屏蔽字等；断屏蔽字等；用户栈指针：指向存放过程和系统调用的用户栈指针：指向存放过程和系统调用的参数及断点地址的参数及断点地址的栈顶栈顶。调度信息调度信息 进程状态进程状态 进程优先级进程优先级 各种计时信息各种计时信息 事件（阻塞原因）事件（阻塞原因）控制信息控制信息 程序和数据起始地址程序和数据起始地址 进程同步和通信信息进程同步和通信信息 资源清单资源清单 链接指针链接指针.PCBPCB的组织方式的组织方式 链接方式链接方式（队列（队列）按进程状态分别组成执行队列、就绪队按进

22、程状态分别组成执行队列、就绪队列、等待队列列、等待队列 索引方式索引方式(表表)按进程状态分别建立索引表，表明按进程状态分别建立索引表，表明PCBPCB在在PCBPCB表中的地址表中的地址按链接方式组织按链接方式组织PCBPCBPCB1PCB1PCB2PCB2PCB3PCB3PCB4PCB4PCB5PCB5PCB6PCB6PCB7PCB7PCBnPCBn.空空 PCBPCB运行态运行态就绪态就绪态等待等待1 1等待等待2 26 67 75 510101515队列管理队列管理 队列数据结构：队列数据结构：指向队首的表指针指向队首的表指针 三个队列：三个队列：运行队列、就绪队列、等待队列运行队列、

23、就绪队列、等待队列 排队方式：排队方式：排队首、排队尾、插队排队首、排队尾、插队 出队方式出队方式:队首出队、队中出队队首出队、队中出队 队列管理队列管理:中断之后，进程调度之前中断之后，进程调度之前按索引方式组织按索引方式组织PCBPCB 进程控制主要是对系统中所有进程，从创进程控制主要是对系统中所有进程，从创建到撤销的全过程实行的管理和控制建到撤销的全过程实行的管理和控制 进程控制一般由进程控制一般由OSOS的的内核内核通过执行各种通过执行各种 原语原语操作实现操作实现2.2 进程控制 加在硬件上的第一层软件，通过执行加在硬件上的第一层软件，通过执行各种各种原语原语操作实现控制和管理功能，

24、具有操作实现控制和管理功能，具有进程管理、资源管理、中断处理等功能进程管理、资源管理、中断处理等功能内核内核 内核执行的特点内核执行的特点 由中断驱动由中断驱动的的:中断中断内核内核退出退出 内核执行是连续的内核执行是连续的 内核使用特权指令内核使用特权指令 是由若干条机器指令构成，用以完成特定是由若干条机器指令构成，用以完成特定功能的一段程序功能的一段程序 原语是原子操作，要么全做，要么全不做原语是原子操作，要么全做，要么全不做 原子性通原子性通过过关中断关中断实现实现原语原语 *进程上下文进程上下文*进程执行活动全过程的静态描述进程执行活动全过程的静态描述 包括各种寄存器和堆栈的值、正文段

25、、数包括各种寄存器和堆栈的值、正文段、数据集和据集和PCBPCB结构结构PCB各种各种控制表控制表指针指针各种寄存器各种寄存器正文集正文集数据集数据集栈区栈区2.2.2.2.1 1 进程进程的创建的创建1.1.进程图进程图是是描述进程的家族关系的描述进程的家族关系的有向树有向树（PCBPCB）一个结点代表一个进程一个结点代表一个进程，一条弧代表进程，一条弧代表进程之间的父子关系之间的父子关系根结点为该家族的祖先根结点为该家族的祖先【引入进程图的目的】【引入进程图的目的】子进程继承父进程的资源子进程继承父进程的资源子进程撤销时，向父进程归还资源子进程撤销时，向父进程归还资源父进程撤销时，同时撤销

26、所有的子进程父进程撤销时，同时撤销所有的子进程【进程图和前趋图】【进程图和前趋图】前趋图前趋图描述的是任务描述的是任务(或进程或进程)之间的前趋之间的前趋关系关系,只有在前趋进程完成后，其后继进程只有在前趋进程完成后，其后继进程才能运行才能运行进程图进程图描述进程的创建者和被创建者之间描述进程的创建者和被创建者之间的关系，它们可以并发执行，也可以父进的关系，它们可以并发执行，也可以父进程等待其所有的子进程结束后再执行，这程等待其所有的子进程结束后再执行，这完全取决于创建原语和创建者的需要完全取决于创建原语和创建者的需要 2.2.引起进程创建的事件引起进程创建的事件用户登录：用户登录：分时用户登

27、录分时用户登录作业调度：作业调度：批处理作业调度批处理作业调度提供服务：提供服务：用户请求系统服务用户请求系统服务(如打印如打印)应用请求：应用请求：父进程创建子进程父进程创建子进程3.3.进程的创建进程的创建 申请空白申请空白PCBPCB，分配进程标识符；分配进程标识符；为新进程分配内存资源；为新进程分配内存资源；初始化进程控制块初始化进程控制块 初始化标识符信息（该进程、父进程初始化标识符信息（该进程、父进程）初始化处理机状态信息（初始化处理机状态信息（PCPC、栈指针）栈指针）初始化处理机控制信息（进程状态、优先级）初始化处理机控制信息（进程状态、优先级）将新进程插入就绪队列将新进程插入

28、就绪队列1.1.引起进程终止的事件引起进程终止的事件 正常结束正常结束 批处理作业发出暂停（批处理作业发出暂停（HaltHalt）指令指令 用户退出登录用户退出登录 进程执行一终止服务请求进程执行一终止服务请求 2.2.22.2.2 进程进程的终止的终止 异常结束异常结束 越界错误；越界错误；保护错；保护错；非法指令；非法指令；特权指令错；特权指令错；运行超时；运行超时；等待超时；等待超时；算数运算错算数运算错 I/OI/O故障。故障。外界干预外界干预 操作系统干预；操作系统干预；父进程请求；父进程请求；父进程终止。父进程终止。2.2.进程的终止过程进程的终止过程 按标识符查找该进程，读取进程

29、状态；按标识符查找该进程，读取进程状态；若若该该进进程程处处于于执执行行状状态态,立立即即终终止止并并置置调调度度标志为真，引起新的进程调度；标志为真，引起新的进程调度；若该进程有子孙进程，则终止子孙进程运行；若该进程有子孙进程，则终止子孙进程运行；将该进程的所有资源，归还给父进程或系统；将该进程的所有资源，归还给父进程或系统；将将该该进进程程的的PCBPCB从从所所在在队队列列移移出出，等等待待搜搜集集信息，并撤销该进程的信息，并撤销该进程的PCBPCB。2.2.32.2.3 进程进程的阻塞与唤醒的阻塞与唤醒1.1.引起进程阻塞和唤醒的事件引起进程阻塞和唤醒的事件 请求系统服务请求系统服务

30、无法获得服务，进程主动阻塞；无法获得服务，进程主动阻塞；服务完成，由服务完成，由服务释放进程服务释放进程唤醒阻塞进程。唤醒阻塞进程。启动某种操作启动某种操作 进程主动阻塞，等待操作完成；进程主动阻塞，等待操作完成；操作完成，由操作完成，由中断处理程序中断处理程序唤醒阻塞进程。唤醒阻塞进程。合作数据尚未到达合作数据尚未到达 合作进程的数据尚未到达，等待进程阻塞；合作进程的数据尚未到达，等待进程阻塞；新数据到达，由新数据到达，由合作进程合作进程唤醒阻塞进程。唤醒阻塞进程。无新工作可做无新工作可做 系统进程无新工作可作，主动阻塞；系统进程无新工作可作，主动阻塞；新工作新工作到达时，系统进程被唤醒。到

31、达时，系统进程被唤醒。2.2.进程阻塞过程进程阻塞过程 停停止止进进程程的的执执行行，将将进进程程状状态态由由执执行行改改为为阻塞阻塞；按照阻塞原因将按照阻塞原因将PCBPCB插入相应的插入相应的阻塞队列阻塞队列；引起新的进程调度并进行引起新的进程调度并进行进程切换。进程切换。（保存老现场，设置新现场保存老现场，设置新现场）3.3.进程唤醒过程进程唤醒过程 将唤醒进程的将唤醒进程的PCBPCB从阻塞队列移出；从阻塞队列移出；将进程状态由将进程状态由阻塞阻塞改为改为就绪就绪；将将PCBPCB插入插入就绪队列就绪队列。2.2.42.2.4 进程进程的挂起与激活的挂起与激活1.1.进程的挂起进程的挂

32、起【挂起的事件】【挂起的事件】进程将自身挂起；进程将自身挂起；父进程将某个子进程挂起。父进程将某个子进程挂起。【挂起的过程】【挂起的过程】若处于若处于活动就绪活动就绪状态，则改为状态，则改为静止就绪静止就绪；若处于若处于活动阻塞活动阻塞状态，则改为状态，则改为静止阻塞静止阻塞；若处于若处于执行状态执行状态，则改为，则改为静止就绪静止就绪，并引起，并引起新的进程调度。新的进程调度。2.2.进程的激活进程的激活【激活的事件】【激活的事件】父进程请求激活指定进程；父进程请求激活指定进程；内存空间足够，允许激活挂起进程。内存空间足够，允许激活挂起进程。【激活的过程】【激活的过程】将进程从外存调入内存，

33、检查进程的状态将进程从外存调入内存，检查进程的状态;若处于静止就绪状态，则改为活动就绪；若处于静止就绪状态，则改为活动就绪；若处于静止阻塞状态，则改为活动阻塞。若处于静止阻塞状态，则改为活动阻塞。例例1 1 父进程：创建子进程父进程：创建子进程1 1和子进程和子进程2 2，并输出，并输出字母字母a a；子进程子进程1 1：输出字母：输出字母b b 子进程子进程2 2：输出字母：输出字母c c 系统调用系统调用fork()fork()：创建子进程创建子进程 pidpid=fork=fork（）；（）；pidpid=-1=-1：子进程创建失败子进程创建失败 pidpid=0=0：子进程创建成功，并

34、运行子进程子进程创建成功，并运行子进程 pidpid00：子进程创建成功，但运行父进程，子进程创建成功，但运行父进程，返回子进程标识符返回子进程标识符#includeMain()int p1,p2;while (p1=fork()=-1);if (p1=0)putchar(b);else while(p2=fork()=-1);if (p2=0)putchar(c);else putchar(a);/else/while例例2 2 画出进程画出进程A A、B B运行后的进程家族树运行后的进程家族树 （考虑最多情形）（考虑最多情形）#includeMain()int i,pid;for (i=1

35、;i=4;+i)if (pid=fork()0)break;进程进程A AA1234进程进程B BB1234#includeMain()int i,pid;for (i=1;i=4;+i)if (pid=fork()=0)break;2.3 进程同步2.3.1 2.3.1 进程同步的基本概念进程同步的基本概念1.1.两种形式的制约关系两种形式的制约关系 直接制约直接制约 进程之间存在相互进程之间存在相互合作关系合作关系 进程同步的主要任务是：保证相互合作的进程同步的主要任务是：保证相互合作的诸进程在执行次序上的协调，不会出现诸进程在执行次序上的协调，不会出现与时间与时间有关的错误有关的错误 间

36、接制约间接制约 进程之间彼此独立，由于进程之间彼此独立，由于资源共享资源共享而形成而形成 的制约关系的制约关系 进程同步的主要任务：保证诸进程进程同步的主要任务：保证诸进程互斥地互斥地 访问临界资源访问临界资源 同步机制包括同步机制包括同步同步与与互斥互斥两个方面！两个方面！相互感知程度相互感知程度 交互关系交互关系 进程对其他进程进程对其他进程的影响的影响 相互不感知相互不感知(完全不了解其它进完全不了解其它进程的存在程的存在)竞争竞争(competition)competition)一个进程的操作对一个进程的操作对其他进程的结果无其他进程的结果无影响影响 间接感知间接感知(双方都与第三方交

37、双方都与第三方交互，如共享资源互，如共享资源)通过共享进行协作通过共享进行协作 一个进程的推进依一个进程的推进依赖于其他进程对资赖于其他进程对资源的占有情况源的占有情况 直接感知直接感知(双方直接交互，如双方直接交互，如通信通信)通过通信进行协作通过通信进行协作 一个进程的结果依一个进程的结果依赖于从其他进程获赖于从其他进程获得的信息得的信息 进程间的关系进程间的关系 由由OS统一管理和分配统一管理和分配 系统中的硬件资源采用这种共享方式；系统中的硬件资源采用这种共享方式；用户通过系统调用请求和释放资源用户通过系统调用请求和释放资源 由进程自行使用由进程自行使用 系统中的某些数据结构可通过进程

38、间协调系统中的某些数据结构可通过进程间协调的方式实现资源的共享；的方式实现资源的共享；进程进程互斥互斥是实现这类资源共享的有效方式是实现这类资源共享的有效方式*资源共享方式资源共享方式*2.2.临界资源和临界区临界资源和临界区 临界资源临界资源：系统中某些资源一次只允许一个系统中某些资源一次只允许一个进程使用，称这样的进程使用，称这样的资源资源为临界资源为临界资源 (如：打印机、磁带机等如：打印机、磁带机等)临界区临界区：在进程中涉及到临界资源的在进程中涉及到临界资源的程序段程序段 互斥的实现：互斥的实现：只要保证并发执行的诸进程互只要保证并发执行的诸进程互斥地进入各自的临界区，就能实现对临界

39、资斥地进入各自的临界区，就能实现对临界资源的互斥访问！源的互斥访问！3.3.进程互斥的锁机制进程互斥的锁机制 构成构成 锁变量锁变量W W：表示临界资源表示临界资源状态状态 （1 1：开；：开；0 0：关）：关）加锁原语加锁原语Lock(W)Lock(W)：1 10 0；开锁原语开锁原语Unlock(W)Unlock(W)：0 01 1。使用使用 进入临界区前，进程通过锁变量判断临进入临界区前，进程通过锁变量判断临界资源是否被占用界资源是否被占用 占用：则进程反复测试占用：则进程反复测试 W W 的状态（忙等）的状态（忙等）否则否则：为临界资源加锁；（进入前）为临界资源加锁；（进入前）进入临界

40、区进入临界区；（使用临界资源（使用临界资源）为临界资源开锁。（退出前）为临界资源开锁。（退出前）（临界资源）（临界资源）临界资源和临界区示意临界资源和临界区示意4.4.进程机制应遵循的准则进程机制应遵循的准则 空闲让进空闲让进 当无进程处于临界区时，必须让要求进入当无进程处于临界区时，必须让要求进入临界区的一个进程立即进入，以临界区的一个进程立即进入，以便便有效地利用有效地利用临界资源临界资源 忙则等待忙则等待 当已有进程处于临界区内时，其它试图进当已有进程处于临界区内时，其它试图进入临界区的进程必须等待入临界区的进程必须等待 有限等待有限等待 对要求进入临界区的进程，应在有限时对要求进入临界

41、区的进程，应在有限时间内使之进入，以免陷入间内使之进入，以免陷入“死等死等”让权等待让权等待 对于等待进入临界区的进程而言，它必对于等待进入临界区的进程而言，它必须立即释放处理机，以免进程须立即释放处理机，以免进程“忙等忙等”1.1.信号量机制概述信号量机制概述 锁机制存在的问题锁机制存在的问题 仅能表示仅能表示“开开”与与“关关”两种状态两种状态 进程能否进入临界区依靠自己测试，没有进程能否进入临界区依靠自己测试，没有 被调度到的进程没有测试机会被调度到的进程没有测试机会 反复测试的状态浪费了处理机的时间反复测试的状态浪费了处理机的时间 锁机制只能解决互斥，不能用于同步锁机制只能解决互斥，不

42、能用于同步 信号量同步机制能完满地解决上述问题信号量同步机制能完满地解决上述问题2.3.2.3.2 2 信号量机制信号量机制 信号量（信号量（semaphoresemaphore）是一个数据结构，表示如下：是一个数据结构，表示如下：Typedef struct semaphore int value；process_queue L；semaphore 信号量说明信号量说明 struct semaphore s；信号量的使用信号量的使用 必须必须且且只能只能置一次初值置一次初值 不同的使用场合初值的含义不同不同的使用场合初值的含义不同 初值不能为负数初值不能为负数 信号量的值只能由信号量的值只能

43、由P P、V V原语改变原语改变 P P、V V原语原语 P P是荷兰语是荷兰语PasserenPasseren(相当于相当于Pass)Pass)的首字母；的首字母；V V是是VerhoogVerhoog(相当于相当于increment)increment)的首字母的首字母 不同类型的信号量执行不同类型的信号量执行P P、V V原语含义不同原语含义不同 P P、V V原语的执行具有原子性原语的执行具有原子性 P P、V V原语必须成对出现原语必须成对出现 本教材用本教材用waitwait表示表示P P原语，用原语，用signalsignal表示表示V V原语原语P P操作操作P(s)s.val

44、ue=s.value-1;if(s.value 0)block(s.L);/P(s)V V操作操作V(s)s.value=s.value+1;if(s.value=0)wakeup(s.L)；/V(s)1.1.进程互斥进程互斥 互斥互斥信号量信号量 为每类临界资源设置一互斥信号量为每类临界资源设置一互斥信号量s s s s的初值的初值s.value=1s.value=1，表示临界资源表示临界资源可用可用 为临界资源设置一个阻塞队列，因请求该为临界资源设置一个阻塞队列，因请求该 临界资源而阻塞的进程挂入阻塞队列临界资源而阻塞的进程挂入阻塞队列2.3.32.3.3 信号量的应用信号量的应用 P(s

45、)：表示测试临界资源是否可用表示测试临界资源是否可用 s.value=1：临界资源临界资源可用，为临界资源可用，为临界资源 加锁，进入临界区；加锁，进入临界区；s.value=0：临界资源被占用临界资源被占用 s.value0：没有阻塞进程没有阻塞进程，原进程运行原进程运行 s.value=0：唤醒最后一个阻塞的进程唤醒最后一个阻塞的进程 s.valueN)V(mutex)；离开理发店；离开理发店；else count=count+1；if(count1)P(sofa)；在沙发中就座在沙发中就座；P(empty)；从沙发上起来；从沙发上起来；V(sofa)；else P(empty)；V(mu

46、tex)；在理发椅就座；在理发椅就座；V(full)；开始理发；开始理发；/else/guest Barber()P(full)；为顾客理发；为顾客理发；V(empty)；离开理发椅；离开理发椅；P(mutex)；count=count-1；V(mutex)；说明：说明：1 1、对理发椅的使用，相、对理发椅的使用，相当于只有一个缓冲区的当于只有一个缓冲区的进程合作问题；进程合作问题；2 2、设置互斥信号量，实、设置互斥信号量，实现对现对countcount的互斥使用；的互斥使用；3 3、如果考虑付费与收费、如果考虑付费与收费问题，该怎样表示？问题，该怎样表示？采用采用P-VP-V同步机制编写并

47、发程序，共享同步机制编写并发程序，共享变量及信号量的操作将分散于各进程中变量及信号量的操作将分散于各进程中 缺点缺点 易读性差易读性差 不利于修改和维护不利于修改和维护 正确性难以保证正确性难以保证2.3.2.3.4 4 管程机制管程机制1.1.管程的定义管程的定义 一种集中管理的同步机制一种集中管理的同步机制 管程管程由四部分由四部分组组成成 管程的名称管程的名称 共享数据结构的说明共享数据结构的说明 对数据结构操作的一组过程对数据结构操作的一组过程 初始化语句初始化语句 管管程程相相当当于于围围墙墙，把把共共享享变变量量和和若若干干过过程程围围起来起来，在管程内部使用，在管程内部使用 /名

48、称说明名称说明 TYPE monitor_name=MONITOR；/共享变量说明共享变量说明 define 本管程内所定义、本管程外可调本管程内所定义、本管程外可调 用的过程（函数）名列表用的过程（函数）名列表 use 本管程外所定义、本管程内将调用本管程外所定义、本管程内将调用 的过程（函数）名字表的过程（函数）名字表管程的语法描述管程的语法描述/过程或函数说明过程或函数说明 PROCEDURE 过程过程名名(形参表形参表)；BEGIN 语句序列语句序列；END；.FUNCTION 函数函数名名(形参表形参表)：值类型；：值类型；BEGIN 语句序列语句序列；END;./初始化语句初始化语

49、句 BEGIN 共享变量初始化语句序列；共享变量初始化语句序列；END；引入进程为了实现并发执行，引入管程为引入进程为了实现并发执行，引入管程为了实现资源的互斥访问；了实现资源的互斥访问；进程通过调用管程中的过程对共享数据结进程通过调用管程中的过程对共享数据结构进行操作；构进行操作；由编译程序实现对管程的互斥进入；由编译程序实现对管程的互斥进入；管程具有模块化、对象化、信息掩蔽特征。管程具有模块化、对象化、信息掩蔽特征。管程与进程管程与进程2.2.条件变量条件变量 两个同步原语：两个同步原语：wait：测试临界资源，阻塞等待进程测试临界资源，阻塞等待进程 signal：释放临界资源，唤醒阻塞进

50、程释放临界资源，唤醒阻塞进程 根据进程阻塞原因，设置不同条件变量根据进程阻塞原因，设置不同条件变量(x)：x.wait：进程因进程因x条件被阻塞，插入等待队列条件被阻塞，插入等待队列并释放管程；并释放管程；x.signal：唤醒因唤醒因x条件阻塞的进程；若无条件阻塞的进程；若无则执行空操作，并继续执行原进程。则执行空操作，并继续执行原进程。入口等待队列入口等待队列 一个进程试图进入一个巳被占用的管程一个进程试图进入一个巳被占用的管程 时，应当在管程的入口处的等待队列中等待时，应当在管程的入口处的等待队列中等待 紧急等待队列紧急等待队列 在管程内部，由于执行唤醒操作，可能在管程内部，由于执行唤醒