《第2章 进程的描述与控制.pptx》由会员分享，可在线阅读，更多相关《第2章 进程的描述与控制.pptx（177页珍藏版）》请在taowenge.com淘文阁网|工程机械CAD图纸|机械工程制图|CAD装配图下载|SolidWorks_CaTia_CAD_UG_PROE_设计图分享下载上搜索。
1、2022年12月20日操作系统1第第2 2章章 进程的描述与控制程的描述与控制2022年12月20日第二章 进程管理2主要内容主要内容 2.1 进程的基本概念进程的基本概念 2.2 进程控制进程控制 2.3 进程同步进程同步 2.4 经典的同步问题经典的同步问题 2.5 管程机制管程机制 2.6 进程通信进程通信 2.7 线程线程 2.8 例题选讲例题选讲2022年12月20日第二章 进程管理32.1 进程的基本概念程的基本概念例如下面例如下面3个语句：个语句：1.程序的顺序执行程序的顺序执行S1：a:=x+yS2：b:=a-5S3：c:=b+1前趋图前趋图是一个有向无循环图是一个有向无循环图
2、DAG(Directed Acyclic Graph)S1S2S3上面语句的前趋图可以表示为：S=S1,S2,S3=(S1,S2),(S2,S3)第2章 进程的描述与控制 1 1.程序的顺序执行与特征程序的顺序执行与特征S1S1S2S2S3S3eg2:S1:a:=x+yeg2:S1:a:=x+y S2:b:=a-5 S2:b:=a-5 S3:c:=b+1 S3:c:=b+1输入数据输入数据加工处理加工处理打印结果打印结果eg1eg1:在早期的单道程序工作环境下，内存中只有一个作业的程在早期的单道程序工作环境下，内存中只有一个作业的程序。一个作业完成了，后一个作业才进入内存，并得以执行。序。一个
3、作业完成了，后一个作业才进入内存，并得以执行。这样一来，机器执行程序的过程就严格按顺序方式执行。这样一来，机器执行程序的过程就严格按顺序方式执行。第2章 进程的描述与控制 特征：特征：(1)(1)顺序性顺序性 程序的执行是按照程序机构所指定的顺序执行，即每一程序的执行是按照程序机构所指定的顺序执行，即每一操作必须在前一操作完成以后才能开始。操作必须在前一操作完成以后才能开始。(2)(2)封闭性封闭性 程序是在封闭的环境下运行的。即程序运行时独占全机程序是在封闭的环境下运行的。即程序运行时独占全机资源，资源的状态完全由该程序的控制逻辑所决定，不受外资源，资源的状态完全由该程序的控制逻辑所决定，不
4、受外界因素的影响。界因素的影响。(3)(3)可再现性可再现性 只要程序执行的初始条件相同，执行结果就完全相同。只要程序执行的初始条件相同，执行结果就完全相同。即程序执行结果与它的运行速度无关。即程序执行结果与它的运行速度无关。第2章 进程的描述与控制 2.2.程序的并发执行和特征程序的并发执行和特征 程序的并发执行和资源共享使系统的工作情况变得复杂，程序的并发执行和资源共享使系统的工作情况变得复杂，产生了新的特征。产生了新的特征。(1)(1)不可再现性不可再现性 并发程序的执行结果与它们的相对速度有关。并发程序的执行结果与它们的相对速度有关。.n:=0.n:=n+1.Ak1k2.打印n.Bs
5、如图，两并发程序如图，两并发程序A A和和B B互相独立运互相独立运行，行，A A中对变量中对变量n n实现累加操作，实现累加操作，B B中打印中打印n n值，它们的相对执行速度是不确定的。值，它们的相对执行速度是不确定的。若若A A执行到执行到k1k1时，控制转到时，控制转到B B，B B执行执行过程中打印过程中打印n n的值为的值为0 0。当。当B B运行到运行到s s时，时，控制又转到控制又转到A A，则，则A A在在k1k1点后继续执行。点后继续执行。若若A A运行得快一些，当它执行到运行得快一些，当它执行到k2k2时，时，控制才转到控制才转到B B，则，则B B执行时打印机出执行时打
6、印机出n n得值得值为为1 1。第2章 进程的描述与控制(2)(2)制约性制约性 并发并发程序之间相互依赖和制约。程序之间相互依赖和制约。如图如图I I、C C、O O是三个相互合作的程序，当计算程序是三个相互合作的程序，当计算程序C Ci-1i-1处理后，若输入程序未完成对处理后，若输入程序未完成对I Ii i的处理，计算程序便无法的处理，计算程序便无法进行进行C Ci i的处理，致使它暂停运行。的处理，致使它暂停运行。另外几个并发程序还可能因竞争同一资源而相互制约。另外几个并发程序还可能因竞争同一资源而相互制约。I1I2I3I4P1C1P2P3C2C3P4C4第2章 进程的描述与控制(3)
7、(3)程序与计算不再一一对应程序与计算不再一一对应 “程序程序”是指令的有序集合，是静态的概念。而是指令的有序集合，是静态的概念。而“计算计算”是指令系列在处理机上的执行过程，是动态的概念。在并是指令系列在处理机上的执行过程，是动态的概念。在并发执行时，一个共享程序可被多个用户作业调用，从而形成发执行时，一个共享程序可被多个用户作业调用，从而形成了多个计算。了多个计算。.CALL C.B.CALL C.A.C 如图：如图：A A和和B B执行中都调用执行中都调用C C。在。在A A调用时调用时C C时，时，C C是属于是属于A A的执行过程的一部分；在的执行过程的一部分；在B B调用调用C C
8、时，时，C C是属于是属于B B的执行过程的执行过程的一部分。的一部分。C C属于属于A A、B B的不同执行过程。的不同执行过程。(4)(4)失去封闭性失去封闭性第2章 进程的描述与控制 共69页第9页进程的概念操作系统用操作系统用操作系统用操作系统用“进程进程进程进程”来描述系统中各并发活动来描述系统中各并发活动来描述系统中各并发活动来描述系统中各并发活动进程（进程（进程（进程（processprocess）又叫做任务（）又叫做任务（）又叫做任务（）又叫做任务（tasktask）进程是程序的一次执行过程进程是程序的一次执行过程进程是程序的一次执行过程进程是程序的一次执行过程定义：进程是具有
9、独立功能的程序在一个数据集定义：进程是具有独立功能的程序在一个数据集定义：进程是具有独立功能的程序在一个数据集定义：进程是具有独立功能的程序在一个数据集合上的一次动态执行过程。是系统进行资源分配合上的一次动态执行过程。是系统进行资源分配合上的一次动态执行过程。是系统进行资源分配合上的一次动态执行过程。是系统进行资源分配和调度的一个独立单位。和调度的一个独立单位。和调度的一个独立单位。和调度的一个独立单位。第2章 进程的描述与控制 共69页第10页进程具有的特性动态性动态性。进程是程序的一次执行过程，是。进程是程序的一次执行过程，是临时的，有生命期的。临时的，有生命期的。独立性独立性。进程是系统
10、进行资源分配和调度。进程是系统进行资源分配和调度的一个独立单位。的一个独立单位。并发性并发性。多个进程可在处理机上交替执行。多个进程可在处理机上交替执行。结构性结构性。系统为每个进程建立一个进程控。系统为每个进程建立一个进程控制块。制块。第2章 进程的描述与控制 共69页第11页进程和程序1.进程是动态的，程序是静态的。程序是有序代码的集合，进程是程序的执行，没有程序就没有进程。通常，进程不可以在计算机之间迁移，而程序可以复制。2.进程是暂时的，程序是永久的。3.进程包括程序、数据和进程控制块。4.通过多次执行，一个程序可对应多个进程；通过调用关系，一个进程可包括多个程序。进程可创建其他进程，
11、而程序不能形成新的程序。第2章 进程的描述与控制(2)(2)进程的特征进程的特征动态性动态性 进程是程序在并发系统内的一次执行，一个进程进程是程序在并发系统内的一次执行，一个进程有一个从产生到消失的生命期；有一个从产生到消失的生命期；并并发发性性 正正是是为为了了描描述述程程序序在在并并发发系系统统内内执执行行的的动动态态特特性性才引入了进程，没有并发就没有进程；才引入了进程，没有并发就没有进程；独独立立性性 每每个个进进程程的的程程序序都都是是相相对对独独立立的的顺顺序序程程序序，可可以以按照自己的方向和速度独立地向前推进；按照自己的方向和速度独立地向前推进；制制约约性性 进进程程之之间间的
12、的相相互互制制约约，主主要要表表现现在在互互斥斥地地使使用用资资源和相关进程之间必要的同步和通讯；源和相关进程之间必要的同步和通讯；结构性结构性 进程进程 =PCB+=PCB+程序程序 +数据集合。数据集合。第2章 进程的描述与控制 2.1.2 进程的状态和组成进程的状态和组成1.1.进程的状态及其转换进程的状态及其转换(1)(1)进程的基本状态进程的基本状态:运行状态运行状态(Running)(Running)、就绪状态、就绪状态(Ready)(Ready)、阻塞状态阻塞状态(Blocked)(Blocked)、创建状态、创建状态(New)(New)、退出状态、退出状态(Exit)(Exit
13、)。运运行行状状态态 指指当当前前进进程程已已占占有有CPUCPU，它它的的程程序序段段正正在在执执行行。处于这种状态的进程的个数不能大于处于这种状态的进程的个数不能大于CPUCPU的数目；的数目；就就绪绪状状态态 进进程程获获得得了了除除处处理理机机外外的的一一切切资资源源。等等待待分分配配CPUCPU资源，一旦得到资源，一旦得到CPUCPU就可以运行；就可以运行；阻塞状态阻塞状态 进程因等待某种事件发生而暂不能运行的状态；进程因等待某种事件发生而暂不能运行的状态；第2章 进程的描述与控制 创建状态创建状态 进程处于创建过程中，还不能运行；进程处于创建过程中，还不能运行；退出状态退出状态 进
14、程已结束运行，回收除进程已结束运行，回收除PCBPCB之外的其它资源。之外的其它资源。在一个具体的系统中，为了调度的方便、合理，往往在一个具体的系统中，为了调度的方便、合理，往往设立了更多个进程状态。如在设立了更多个进程状态。如在UNIXUNIX操作系统中，进程状态操作系统中，进程状态可分为可分为1010种。但上述这几种状态是最基本的。因为如果不种。但上述这几种状态是最基本的。因为如果不设立运行状态就不知道哪一个进程正在占有设立运行状态就不知道哪一个进程正在占有CPUCPU；如果不；如果不设立就绪状态，就无法有效地挑选出适合运行的进程；如设立就绪状态，就无法有效地挑选出适合运行的进程；如果不设
15、立阻塞状态，就无法区分各进程除果不设立阻塞状态，就无法区分各进程除CPUCPU之外是否还之外是否还缺其它资源。缺其它资源。第2章 进程的描述与控制(2)(2)进程状态的转换进程状态的转换阻塞阻塞就绪就绪运行运行完成释放完成释放提交进入提交进入等待事件等待事件事件发生事件发生时间片到时间片到调度选中进入调度选中进入创建创建退出退出创建进程创建进程就就绪绪运运行行 处处于于就就绪绪状状态态的的进进程程被被调调度度程程序序选选中中，分分到到CPUCPU后，该进程状态就由就绪态变为运行态；后，该进程状态就由就绪态变为运行态；运运行行阻阻塞塞 正正在在运运行行的的进进程程因因某某种种条条件件未未满满足足
16、而而放放弃弃对对CPUCPU的占用；的占用；阻塞阻塞就绪就绪 处于阻塞状态的进程所等待的事件发生了；处于阻塞状态的进程所等待的事件发生了；运运行行就就绪绪 正正在在运运行行的的进进程程如如用用完完了了本本次次分分配配给给它它的的CPUCPU时时间片，它就得从间片，它就得从CPUCPU时间片上退下来，暂停运行。时间片上退下来，暂停运行。第2章 进程的描述与控制 就绪就绪运行运行完成释放完成释放提交进入提交进入阻塞阻塞等待事件等待事件事件发生事件发生时间片到时间片到调度选中进入调度选中进入创建创建退出退出就绪挂起就绪挂起阻塞挂起阻塞挂起激活激活挂起挂起激活激活挂起挂起事件发生事件发生挂起挂起挂起进
17、程模型：挂起进程模型：第2章 进程的描述与控制 就绪状态就绪状态 进程在内存且可立即进入运行状态；进程在内存且可立即进入运行状态；阻塞状态阻塞状态 进程在内存并等待某事件的出现；进程在内存并等待某事件的出现；就绪挂起状态就绪挂起状态 进程在外存，但只要进入内存，即可运行；进程在外存，但只要进入内存，即可运行；阻塞挂起状态阻塞挂起状态 进程在外存并等待某事件的出现。进程在外存并等待某事件的出现。第2章 进程的描述与控制 2.2.进程的组成进程的组成(1)(1)进程的组成进程的组成 程序、数据和进程控制块程序、数据和进程控制块(PCB)(PCB)。(2)(2)进程控制块的组成进程控制块的组成 PC
18、BPCB中含有中含有进程描述信息、进程控制信息、资源占用信进程描述信息、进程控制信息、资源占用信息和处理器现场保护结构息和处理器现场保护结构这四个部分，是进程动态特性的集这四个部分，是进程动态特性的集中反映，它是系统对进程进行识别和控制的依据，在不同的中反映，它是系统对进程进行识别和控制的依据，在不同的系统中，系统中，PCBPCB的具体成分是不同的。总的来说，的具体成分是不同的。总的来说，PCBPCB一般包括一般包括如下内容：如下内容：进程名、现行状态、优先级、现场保护区、资源进程名、现行状态、优先级、现场保护区、资源清单、族系关系、进程实体信息、进程通信机制与其它信息清单、族系关系、进程实体
19、信息、进程通信机制与其它信息等。等。第2章 进程的描述与控制 共69页第19页进程的描述PCB是进程存在的唯一标识是进程存在的唯一标识通常，一个进程的信息包括：通常，一个进程的信息包括：至少一个可执行程序至少一个可执行程序一个独立的地址空间一个独立的地址空间一个执行栈区（子程序调用，系统调用，进程切换）一个执行栈区（子程序调用，系统调用，进程切换）打开的文件、申请使用的打开的文件、申请使用的I/O设备等设备等 进程控制块进程控制块(PCB,process control block)进程描述符进程描述符(process descriptor)第2章 进程的描述与控制 共69页第20页PCB中的
20、基本信息1.进程标识数：用于唯一地标识一个进程，通常是一个整数。外部标识符，由用户使用。如：send进程、print进程等。2.进程的状态、调度、存储器管理信息：是调度进程所必需的信息，包括进程状态、优先级、程序在主存地址、在外存的地址等。3.进程使用的资源信息：分配给进程的I/O设备、正在打开的文件等。第2章 进程的描述与控制 共69页第21页4.CPU现场保护区：保存进程运行的现场信息。包括：程序计数器(PC)、程序状态字、通用寄存器、堆栈指针等。5.记帐信息：包括使用CPU时间量、帐号等。6.进程之间的家族关系：类UNIX系统，进程之间存在着家族关系，父/子进程。Windows 进程之间
21、不具有父子关系。7.进程的链接指针：链接相同状态的进程。第2章 进程的描述与控制 共69页第22页Unix：struct proc;Linux：struct task_struct;Windows 执行体进程块（EPROCESS）EPROCESSKPROCESSETHREADKTHREAD内核实现线程调度，调度信息在内核实现线程调度，调度信息在KTHREAD结构中结构中实例实例第2章 进程的描述与控制 3 3.进程队列进程队列 系统中有许多进程，处于就绪状态和处于阻塞状态的进系统中有许多进程，处于就绪状态和处于阻塞状态的进程可分别有多个，而阻塞的原因又可以各不相同。因此为了程可分别有多个，而阻
22、塞的原因又可以各不相同。因此为了调度和管理的方便起见，常将各进程的调度和管理的方便起见，常将各进程的PCBPCB用适当的方式组用适当的方式组织起来。一般说来，有以下几种织起来。一般说来，有以下几种PCBPCB组织方式：组织方式：线性方式、链接方式、索引方式线性方式、链接方式、索引方式第2章 进程的描述与控制(1)(1)线性方式线性方式 把所有不同状态的进程的把所有不同状态的进程的PCBPCB组织在一个表格中。组织在一个表格中。PCB PCB PCB PCB PCB PCB 1 2 3 n-2 n-1 n第2章 进程的描述与控制(2)(2)链接方式链接方式 将处于不同状态的将处于不同状态的PCB
23、PCB放在不同的队列中，处于相同状态放在不同的队列中，处于相同状态的的PCBPCB组成队列，如此便形成执行队列、就绪队列、等待队列。组成队列，如此便形成执行队列、就绪队列、等待队列。PCB0PCB0PCBPCBPCB0PCB0PCBPCBPCB运行队列指针就绪队列指针阻塞队列1指针阻塞队列2指针共69页就绪队列就绪队列事件事件1的等待队列的等待队列事件事件n的等待队列的等待队列事件事件1出现出现事件事件n出现出现提交提交调度调度被抢先被抢先等待事件等待事件1等待事件等待事件n处理机处理机完成完成第2章 进程的描述与控制(3)(3)索引方式索引方式 利用索引表记载相应状态进程的利用索引表记载相应
24、状态进程的PCBPCB地址。地址。运行指针就绪表指针阻塞表指针阻塞索引表就绪索引表 PCB1PCB2PCB3PCB4PCB5PCB6PCB7第2章 进程的描述与控制 2.3 进进 程程 控控 制制 进程是有进程是有“生命期生命期”的动态过程，核心对它们实施管理。的动态过程，核心对它们实施管理。进程控制的进程控制的功能功能是完成是完成进程状态的转换进程状态的转换，主要包括：，主要包括：创建进创建进程程、撤销进程撤销进程、挂起进程挂起进程、解除挂起解除挂起、阻塞进程阻塞进程、唤醒进程唤醒进程、调度进程调度进程等。等。这些操作是由若干条机器指令构成用以完成特定功能的这些操作是由若干条机器指令构成用以
25、完成特定功能的一段程序，被称做原子操作一段程序，被称做原子操作(原语原语)。原语：原语：是机器指令的延伸，往往是为完成某些特定的功能而是机器指令的延伸，往往是为完成某些特定的功能而编制的一段系统程序。为保证操作的正确性，在许多机器中编制的一段系统程序。为保证操作的正确性，在许多机器中规定，执行原语操作时，要屏蔽中断，以保证其操作的不可规定，执行原语操作时，要屏蔽中断，以保证其操作的不可分割性。原语操作也称做分割性。原语操作也称做“原子操作原子操作”，即一个操作中的所，即一个操作中的所有动作要么全做，要么全不做。有动作要么全做，要么全不做。第2章 进程的描述与控制 2.3.1 进程的创建进程的创
26、建 1.进程图进程图(Process Graph)第2章 进程的描述与控制 2.引起创建进程的事件引起创建进程的事件 用户登录、用户登录、作业调度、作业调度、提供服务、提供服务、应用请求。应用请求。3.3.进程的创建进程的创建(Creation of Progress)进程可借助创建原语建立一个子进程，创建进程的主要进程可借助创建原语建立一个子进程，创建进程的主要操作过程是操作过程是：(1)申请一个空闲的申请一个空闲的PCB；(2)为新进程分配资源；为新进程分配资源；(3)将新进程的将新进程的PCB初始化；初始化；(4)将新进程加到就绪队列中。将新进程加到就绪队列中。第2章 进程的描述与控制
27、创建进程流程图创建进程流程图 第2章 进程的描述与控制 2.3.2 进程的终止进程的终止 一一个个进进程程在在完完成成其其任任务务后后，应应将将该该进进程程撤撤销销，以以便便释释放放出出它它所所占占用用的的资资源源，撤撤销销原原语语一一般般由由其其父父进进程程或或祖祖先先发发出出，不不会会自自己己撤撤销销自自己己。一一旦旦系系统统中中出出现现要要求求终终止止进进程程的的事件后，便调用进程终止原语。事件后，便调用进程终止原语。1.引起进程终止引起进程终止(Termination of Process)的事件的事件 正常结束、异常结束、外界干预正常结束、异常结束、外界干预 第2章 进程的描述与控制
28、 2.进程的终止过程进程的终止过程(1)(1)根据被终止进程的标识符，从根据被终止进程的标识符，从PCBPCB集合中检索出该进集合中检索出该进程的程的PCBPCB，从中读出该进程的状态。，从中读出该进程的状态。(2)(2)若若被被终终止止进进程程正正处处于于执执行行状状态态，应应立立即即终终止止该该进进程程的的执执行行，并并置置调调度度标标志志为为真真，用用于于指指示示该该进进程程被被终终止止后后应应重重新进行调度。新进行调度。(3)(3)若若该该进进程程还还有有子子孙孙进进程程，还还应应将将其其所所有有子子孙孙进进程程予予以以终止，以防他们成为不可控的进程。终止，以防他们成为不可控的进程。(
29、4)(4)将将被被终终止止进进程程所所拥拥有有的的全全部部资资源源，或或者者归归还还给给其其父父进进程，或者归还给系统。程，或者归还给系统。(5)(5)将被终止进程将被终止进程(它的它的PCB)PCB)从所在队列从所在队列(或链表或链表)中移出，中移出，等待其他程序来搜集信息。等待其他程序来搜集信息。第2章 进程的描述与控制 撤消进程流程图撤消进程流程图 第2章 进程的描述与控制 2.3.3 进程的阻塞与唤醒进程的阻塞与唤醒1.进程的阻塞进程的阻塞 正在运行的进程因等待某事件发生，只能转变为阻塞正在运行的进程因等待某事件发生，只能转变为阻塞态，等待相应事件出现后再把它唤醒。态，等待相应事件出现
30、后再把它唤醒。正在运行的进程通过调用阻塞原语主动地把自己阻塞。正在运行的进程通过调用阻塞原语主动地把自己阻塞。进程阻塞的过程如下：进程阻塞的过程如下：(1)(1)立即停止当前进程的执行；立即停止当前进程的执行；(2)(2)将现行进程的将现行进程的CPUCPU现场送到该进程的现场送到该进程的PCBPCB现场保护区中保现场保护区中保存起来，以便将来重新运行时恢复此时的现场；存起来，以便将来重新运行时恢复此时的现场；(3)(3)把该进程把该进程PCBPCB中的现行状态由中的现行状态由“运行运行”改为阻塞，把它改为阻塞，把它插入到具有相同事件的阻塞队列中；插入到具有相同事件的阻塞队列中；(4)(4)然
31、后转到进程调度程序，重新从就绪队列中挑选一个合然后转到进程调度程序，重新从就绪队列中挑选一个合适进程投入运行。适进程投入运行。第2章 进程的描述与控制 阻塞进程流程图阻塞进程流程图第2章 进程的描述与控制 2.进程的唤醒进程的唤醒 当被阻塞进程所等待的事件出现时，则由另外的与被阻当被阻塞进程所等待的事件出现时，则由另外的与被阻塞进程相关的进程调用唤醒原语，将等待该事件的进程唤醒。塞进程相关的进程调用唤醒原语，将等待该事件的进程唤醒。可见，被阻塞进程不能唤醒自己。可见，被阻塞进程不能唤醒自己。唤醒原语的主要操作过程是：唤醒原语的主要操作过程是：(1)(1)首先把被阻塞进程从相应的阻塞队列中摘下；
32、首先把被阻塞进程从相应的阻塞队列中摘下；(2)(2)将现行状态改为就绪态，然后把该进程插入到就绪队列中；将现行状态改为就绪态，然后把该进程插入到就绪队列中；(3)(3)如果被唤醒进程比运行进程有更高的优先级，则设置重新如果被唤醒进程比运行进程有更高的优先级，则设置重新调度标志。调度标志。阻塞原语与唤醒原语恰好是一对相反的原语：调用前者阻塞原语与唤醒原语恰好是一对相反的原语：调用前者是自己去睡眠，调用后者是把是自己去睡眠，调用后者是把“别人别人”唤醒。使用时也要成唤醒。使用时也要成对，前边有睡的，后边要有叫醒的。否则，前者就要对，前边有睡的，后边要有叫醒的。否则，前者就要“长眠长眠”了。第2章
33、进程的描述与控制 唤醒进程流程图唤醒进程流程图 第2章 进程的描述与控制 2.3.4 进程的挂起与激活进程的挂起与激活 1.进程的挂起进程的挂起 当当需需要要把把某某进进程程置置于于挂挂起起就就绪绪状状态态或或挂挂起起阻阻塞塞状状态态时时，可可调调用用挂挂起起原原语语。调调用用挂挂起起原原语语的的进进程程只只能能挂挂起起它它自己或它的子孙。自己或它的子孙。挂挂起起原原语语的的执执行行过过程程是是：首首先先检检查查被被挂挂起起进进程程的的状状态态，若若处处于于活活动动就就绪绪状状态态，便便将将其其改改为为静静止止就就绪绪；对对于于活活动动阻阻塞塞状状态态的的进进程程，则则将将之之改改为为静静止止
34、阻阻塞塞。为为了了方方便便用用户户或或父父进进程程考考查查该该进进程程的的运运行行情情况况而而把把该该进进程程的的PCB复复制制到到某某指指定定的的内内存存区区域域。最最后后，若若被被挂挂起起的的进进程程正正在在执行，则转向调度程序重新调度。执行，则转向调度程序重新调度。第2章 进程的描述与控制 2.进程的激活过程进程的激活过程 激激活活原原语语将将处处于于静静止止状状态态的的进进程程变变为为活活动动状状态态。一一个个进进程程只只能能将将自自己己的的子子孙孙进进程程解解挂挂。一一个个进进程程可可以以将将自自己己挂挂起起，却不能将自己解挂。却不能将自己解挂。激激活活原原语语的的执执行行过过程程是
35、是：激激活活原原语语先先将将进进程程从从外外存存调调入入内内存存，检检查查该该进进程程的的现现行行状状态态，若若是是静静止止就就绪绪，便便将将之之改改为为活活动动就就绪绪；若若为为静静止止阻阻塞塞便便将将之之改改为为活活动动阻阻塞塞。假假如如采采用用的的是是抢抢占占调调度度策策略略，则则每每当当有有新新进进程程进进入入就就绪绪队队列列时时，应应检检查查是是否否要要进进行行重重新新调调度度，即即由由调调度度程程序序将将被被激激活活进进程程与与当当前前进进程程进进行行优优先先级级的的比比较较，如如果果被被激激活活进进程程的的优优先先级级更更低低，就就不不必必重重新新调调度度；否否则则，立立即即剥剥
36、夺夺当当前前进进程程的的运运行行，把把处处理理机机分分配给刚被激活的进程。配给刚被激活的进程。第2章 进程的描述与控制 2.4 进进 程程 同同 步步 在同一系统内并发执行的诸程序之间，即有在同一系统内并发执行的诸程序之间，即有独立性独立性又又有有相互制约性相互制约性。独立性独立性是指各进程都可独立的向前推进；是指各进程都可独立的向前推进；制约性制约性是指各个进程是指各个进程对资源的共享对资源的共享以及为以及为完成一项共同任完成一项共同任务需要彼此合作务需要彼此合作等产生的相互制约关系，进程间的相互关等产生的相互制约关系，进程间的相互关系分为系分为同步关系同步关系和和互斥关系互斥关系。如果对进
37、程的活动不加以约束，就会使系统出现混乱，如果对进程的活动不加以约束，就会使系统出现混乱，如多个进程的输出结果混在一起、数据处理的结果不唯一、如多个进程的输出结果混在一起、数据处理的结果不唯一、系统内某些空闲的资源无法得到利用等问题。为了保证系系统内某些空闲的资源无法得到利用等问题。为了保证系统中所有进程都能正常活动，使程序的执行具有可再现性，统中所有进程都能正常活动，使程序的执行具有可再现性，就必须提供就必须提供进程同步机制进程同步机制，即，即实现进程同步和互斥实现进程同步和互斥。第2章 进程的描述与控制 2.4.1 进程同步的基本概念进程同步的基本概念 1.两种形式的制约关系两种形式的制约关
38、系(1)同步（直接相互制约关系）同步（直接相互制约关系）进程间共同完成一项任务时直接发生相互作用的关系进程间共同完成一项任务时直接发生相互作用的关系（相互合作的关系）。（相互合作的关系）。eg:eg:有一输入进程有一输入进程A A通过单缓冲区向计算进程通过单缓冲区向计算进程B B提供数据。当提供数据。当该缓冲区空时，计算进程该缓冲区空时，计算进程B B将因不能获得所需数据而阻塞；将因不能获得所需数据而阻塞；一旦进程一旦进程A A将数据送入该缓冲时，便将进程将数据送入该缓冲时，便将进程B B唤醒。反之，当唤醒。反之，当缓冲已满，进程缓冲已满，进程A A不能再向缓冲区投放数据时，进程不能再向缓冲区
39、投放数据时，进程A A必须阻必须阻塞，仅当进程塞，仅当进程B B将缓冲区内数据取走时，才能唤醒进程将缓冲区内数据取走时，才能唤醒进程A A。第2章 进程的描述与控制 司机和售票员的同步司机和售票员的同步 eg:第2章 进程的描述与控制 egeg：有有用用户户作作业业程程序序，其其形形式式是是Z=func1(x)*func2(y)其其中中func1(x)，func2(y)均均是是复复杂杂函函数数，为为加加快快速速度度，可可用用两两进进程程P1P1、P2P2各各计计算算一一个个函函数数。进进程程P2P2计计算算func2(y)，进进程程P1P1计计算算完完func1(x)之后，与进程之后，与进程P
40、2P2的计算结果相乘，获得最终结果的计算结果相乘，获得最终结果Z Z。第2章 进程的描述与控制(2)互斥（间接相互制约关系）互斥（间接相互制约关系）两个进程在逻辑上本来完全独立，由于竞争同一物理资两个进程在逻辑上本来完全独立，由于竞争同一物理资源而相互制约的关系（对资源争用的关系）。源而相互制约的关系（对资源争用的关系）。eg:eg:在仅有一台打印机的系统中，有两个进程在仅有一台打印机的系统中，有两个进程A A和和B B，如果当，如果当A A需要打印时，系统已将打印机分配给需要打印时，系统已将打印机分配给B B，则进程，则进程A A必须阻塞；必须阻塞；一旦进程一旦进程B B将打印机释放，系统便
41、将将打印机释放，系统便将A A唤醒，使之由阻塞状态唤醒，使之由阻塞状态变为就绪状态。变为就绪状态。第2章 进程的描述与控制 第2章 进程的描述与控制 2.临界资源和临界区临界资源和临界区(1)临界资源临界资源(Critical Resouce)一一次次只只允允许许一一个个进进程程使使用用的的资资源源。例例如如打打印印机机、输输入入机机和共享变量均为临界资源。和共享变量均为临界资源。eg:两进程两进程P1、P2共享一变量共享一变量x，当两进程按下列顺序执行时，当两进程按下列顺序执行时(R1、R2是处理器中的寄存器是处理器中的寄存器)P1：R1:=x；R1:=R1+1；x:=R1；P2：R2:=x
42、；R2:=R2+1；x:=R2；其结果使其结果使x x增加了增加了2 2。P1：R1:=x；P2：R2:=x；P1：R1:=R1+1；x:=R1；P2：R2:=R2+1；x:=R2；其结果使其结果使x x增加了增加了1 1。为预防这种错误，对变量为预防这种错误，对变量x x应按临界资源处理，即令应按临界资源处理，即令P1P1和和P2P2顺序使用顺序使用x x。第2章 进程的描述与控制(2)(2)临界区临界区(critical section)在每个进程中访问临界资源的那段程序，简称在每个进程中访问临界资源的那段程序，简称CSCS区。区。为为了了实实现现对对临临界界资资源源的的互互斥斥访访问问，
43、就就应应该该保保证证各各进进程程互互斥斥地地进进入入自自己己的的临临界界区区。为为此此，每每个个进进程程在在进进入入临临界界区区之之前前，必须先提出申请，经允许后方可进入。必须先提出申请，经允许后方可进入。例例如如，计计算算机机中中的的打打印印机机是是互互斥斥资资源源，它它只只能能“停停停停打打打打”而不能中途去打印另一任务。而不能中途去打印另一任务。repeat 重复执行下面的代码重复执行下面的代码 入口代码入口代码 critical section;临界区临界区 出口代码出口代码 remainder section;非临界区非临界区(剩留区剩留区)until false;循环，直到条件不满
44、足循环，直到条件不满足entry sectionexit section第2章 进程的描述与控制 A A进程进程 B B进程进程分配表被封锁否？分配表被封锁否？分配表被封锁否？分配表被封锁否？对对B B进程封锁分配表进程封锁分配表 对对A A进程封锁分配表进程封锁分配表 分配资源分配资源(例如打印机例如打印机)分配工作、结束后释放资源分配工作、结束后释放资源 撤消对撤消对B B进程封锁进程封锁 撤消对撤消对A A进程封锁进程封锁等等等等第2章 进程的描述与控制(3)(3)临界区的调用原则临界区的调用原则空闲让进空闲让进 当无进程处于临界区时，必须让一个要求进入当无进程处于临界区时，必须让一个要
45、求进入临界区的进程立即进入，以有效地利用临界资源。临界区的进程立即进入，以有效地利用临界资源。忙则等待忙则等待 当已有进程进入临界区时，其它试图进入自己当已有进程进入临界区时，其它试图进入自己临界区的程序必须等待，以保证它们互斥地进入临界区。临界区的程序必须等待，以保证它们互斥地进入临界区。有限停留有限停留 进入临界区地进程要在有限时间内退出，以便进入临界区地进程要在有限时间内退出，以便其它进程能及时进入自己的临界区。其它进程能及时进入自己的临界区。让权等待让权等待 对于等待进入临界区的进程而言，它必须立即对于等待进入临界区的进程而言，它必须立即释放处理机，避免进程释放处理机，避免进程“忙等忙
46、等”。第2章 进程的描述与控制 3.临界区互斥执行的解决方法临界区互斥执行的解决方法(1)软件方法软件方法 单标志算法单标志算法 假设有两个进程假设有两个进程P Pi i和和P Pj j，设立一个共用整型变量，设立一个共用整型变量turn，描述允许进入临界区的进程标识。描述允许进入临界区的进程标识。while(turn!=i）;Critical section turn=j；Remainder section 该算法可以保证任何时刻最多只有一个进程在临界区。该算法可以保证任何时刻最多只有一个进程在临界区。但它的缺点是强制轮流进入临界区，没有考虑进程的实际但它的缺点是强制轮流进入临界区，没有考虑
47、进程的实际需要。需要。while(turn!=j）;Critical section turn=i；Remainder section第2章 进程的描述与控制 双标志、先检查算法双标志、先检查算法 设立一个标志数组设立一个标志数组flag flag，描述各进程是否在临界区，描述各进程是否在临界区，初值均为初值均为FALSEFALSE。while(flag j);flag i=TRUE;Critical section flag i=FALSE;Remainder section 该算法克服了算法该算法克服了算法1 1的缺点，两个进程不用交替进入，的缺点，两个进程不用交替进入，可连续使用。但由于
48、使用多个标志，算法又产生一个新问可连续使用。但由于使用多个标志，算法又产生一个新问题，即进程题，即进程P Pi i和和P Pj j 可能同时进入临界区，从而违反了最多可能同时进入临界区，从而违反了最多只有一个进程在临界区的要求。只有一个进程在临界区的要求。while(flag i);flag j=TRUE;Critical section flag j=FALSE;Remainder section第2章 进程的描述与控制 双标志、先修改后检查算法双标志、先修改后检查算法 设立一个标志数组设立一个标志数组flag，描述各进程是否想进入临界区。，描述各进程是否想进入临界区。flag i=TRUE
49、;while(flag j);Critical section flag i=FALSE;Remainder section 该算法可防止两个进程同时进入临界区。但它的缺点该算法可防止两个进程同时进入临界区。但它的缺点是是P Pi i和和P Pj j可能都进入不了临界区。即在修改本进程标志可能都进入不了临界区。即在修改本进程标志flagflag之后和检查对方之后和检查对方flagflag之前有一段时间间隔，这个间隔导致之前有一段时间间隔，这个间隔导致两个进程都想进入临界区，从而在检查对方标志时不通过。两个进程都想进入临界区，从而在检查对方标志时不通过。flag j=TRUE;while(fla
50、g i);Critical section flag j=FALSE;Remainder section第2章 进程的描述与控制 先修改、后检查、后修改者等待算法先修改、后检查、后修改者等待算法 假设有两个进程假设有两个进程P Pi i和和P Pj j，设立一个标志数组，设立一个标志数组flag flag，描，描述各进程是否想进入临界区。标志述各进程是否想进入临界区。标志turnturn表示修改的先后，由表示修改的先后，由于于turnturn中保存的是较晚的一次赋值，因此较晚修改标志的进中保存的是较晚的一次赋值，因此较晚修改标志的进程等待。程等待。flagi=TRUE;turn=j;while