《操作系统-汤小丹-第四版》第2章.ppt
《《操作系统-汤小丹-第四版》第2章.ppt》由会员分享,可在线阅读,更多相关《《操作系统-汤小丹-第四版》第2章.ppt(232页珍藏版)》请在装配图网上搜索。
第二章进程管理 2 1进程的基本概念2 2进程控制2 3进程同步2 4经典进程的同步问题2 5进程通信2 6线程 2 1进程的基本概念 2 1 1程序的顺序执行及其特征1 程序的顺序执行通常可以把一个应用程序分成若干个程序段 在各程序段之间 必须按照某种先后次序顺序执行 仅当前一操作 程序段 执行完后 才能执行后继操作 例如 在进行计算时 总须先输入用户的程序和数据 然后进行计算 最后才能打印计算结果 这里 我们用结点 Node 代表各程序段的操作 在图2 1中用圆圈表示 其中 I代表输入操作 C代表计算操作 P为打印操作 另外 用箭头指示操作的先后次序 这样 上述的三个程序段的执行顺序可示于图2 1 a 中 对一个程序段中的多条语句来说 也有一个执行顺序问题 例如对于下述三条语句的程序段 S1 a x y S2 b a 5 S3 c b 1 其中 语句S2必须在语句S1之后 即a被赋值 才能执行 同样 语句S3也只能在b被赋值后才能执行 因此 这三条语句应按图2 1 b 所示的顺序执行 图2 1程序的顺序执行 2 程序顺序执行时的特征 1 顺序性 处理机的操作严格按照程序所规定的顺序执行 即每一操作必须在上一个操作结束之后开始 2 封闭性 程序是在封闭的环境下执行的 即程序运行时独占全机资源 资源的状态 除初始状态外 只有本程序才能改变它 程序一旦开始执行 其执行结果不受外界因素影响 3 可再现性 只要程序执行时的环境和初始条件相同 当程序重复执行时 不论它是从头到尾不停顿地执行 还是 停停走走 地执行 都将获得相同的结果 程序顺序执行时的特性 为程序员检测和校正程序的错误带来了很大的方便 2 1 2前趋图前趋图 PrecedenceGraph 是一个有向无循环图 记为DAG DirectedAcyclicGraph 用于描述进程之间执行的前后关系 图中的每个结点可用于描述一个程序段或进程 乃至一条语句 结点间的有向边则用于表示两个结点之间存在的偏序 PartialOrder 亦称偏序关系 或前趋关系 PrecedenceRelation Pi Pj PimustcompletebeforePjmaystart 如果 Pi Pj 可写成Pi Pj 称Pi是Pj的直接前趋 而称Pj是Pi的直接后继 在前趋图中 把没有前趋的结点称为初始结点 InitialNode 把没有后继的结点称为终止结点 FinalNode 此外 每个结点还具有一个重量 Weight 用于表示该结点所含有的程序量或结点的执行时间 在图2 1 a 和2 1 b 中分别存在着这样的前趋关系 Ii Ci Pi S1 S2 S3 和 对于图2 2 a 所示的前趋图 存在下述前趋关系 P1 P2 P1 P3 P1 P4 P2 P5 P3 P5 P4 P6 P4 P7 P5 P8 P6 P8 P7 P9 P8 P9或表示为 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 2 b 中却有着下述的前趋关系 S2 S3 S3 S2 图2 2前趋图 2 1 3程序的并发执行及其特征1 程序的并发执行在图2 1中的输入程序 计算程序和打印程序三者之间 存在着Ii Ci Pi这样的前趋关系 以至对一个作业的输入 计算和打印三个操作 必须顺序执行 但并不存在Pi Ii 1的关系 因而在对一批程序进行处理时 可使它们并发执行 例如 输入程序在输入第一个程序后 在计算程序对该程序进行计算的同时 可由输入程序再输入第二个程序 从而使第一个程序的计算操作可与第二个程序的输入操作并发执行 一般来说 输入程序在输入第i 1个程序时 计算程序可能正在对第i个程序进行计算 而打印程序正在打印第i 1个程序的计算结果 图2 3示出了输入 计算和打印这三个程序对一批作业进行处理的情况 图2 3并发执行时的前趋图 在该例中存在下述前趋关系 Ii Ci Ii Ii 1 Ci Pi Ci Ci 1 Pi Pi 1 而Ii 1和Ci及Pi 1是重迭的 亦即在Pi 1和Ci以及Ii 1之间 可以并发执行 对于具有下述四条语句的程序段 S1 a x 2S2 b y 4S3 c a bS4 d c b 图2 4四条语句的前趋关系 2 程序并发执行时的特征1 间断性程序在并发执行时 由于它们共享系统资源 以及为完成同一项任务而相互合作 致使在这些并发执行的程序之间 形成了相互制约的关系 例如 图2 3中的I C和P是三个相互合作的程序 当计算程序完成Ci 1的计算后 如果输入程序I尚未完成Ii的处理 则计算程序就无法进行Ci的处理 致使计算程序必须暂停运行 又如 当打印程序完成Pi的打印后 若计算程序尚未完成Ci 1的计算 则打印程序就无法对Ci 1的计算结果进行打印 一旦使程序暂停的因素消失后 如Ii已处理完成 计算程序便可恢复执行对Ci的处理 简而言之 相互制约将导致并发程序具有 执行 暂停 执行 这种间断性的活动规律 2 失去封闭性程序在并发执行时 是多个程序共享系统中的各种资源 因而这些资源的状态将由多个程序来改变 致使程序的运行失去了封闭性 这样 某程序在执行时 必然会受到其它程序的影响 例如 当处理机这一资源已被某个程序占有时 另一程序必须等待 3 不可再现性程序在并发执行时 由于失去了封闭性 也将导致其再失去可再现性 例如 有两个循环程序A和B 它们共享一个变量N 程序A每执行一次时 都要做N N 1操作 程序B每执行一次时 都要执行Print N 操作 然后再将N置成 0 程序A和B以不同的速度运行 这样 可能出现下述三种情况 假定某时刻变量N的值为n 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 1 4进程的特征与状态1 进程的特征和定义在多道程序环境下 程序的执行属于并发执行 此时它们将失去其封闭性 并具有间断性及不可再现性的特征 这决定了通常的程序是不能参与并发执行的 因为程序执行的结果是不可再现的 这样 程序的运行也就失去了意义 为使程序能并发执行 且为了对并发执行的程序加以描述和控制 人们引入了 进程 的概念 为了能较深刻地了解什么是进程 我们将先对进程的特征加以描述 1 结构特征通常的程序是不能并发执行的 为使程序 含数据 能独立运行 应为之配置一进程控制块 即PCB ProcessControlBlock 而由程序段 相关的数据段和PCB三部分便构成了进程实体 在早期的UNIX版本中 把这三部分总称为 进程映像 值得指出的是 在许多情况下所说的进程 实际上是指进程实体 例如 所谓创建进程 实质上是创建进程实体中的PCB 而撤消进程 实质上是撤消进程的PCB 本教材中也是如此 2 动态性进程的实质是进程实体的一次执行过程 因此 动态性是进程的最基本的特征 动态性还表现在 它由创建而产生 由调度而执行 由撤消而消亡 可见 进程实体有一定的生命期 而程序则只是一组有序指令的集合 并存放于某种介质上 其本身并不具有运动的含义 因而是静态的 3 并发性这是指多个进程实体同存于内存中 且能在一段时间内同时运行 并发性是进程的重要特征 同时也成为OS的重要特征 引入进程的目的也正是为了使其进程实体能和其它进程实体并发执行 而程序 没有建立PCB 是不能并发执行的 4 独立性在传统的OS中 独立性是指进程实体是一个能独立运行 独立分配资源和独立接受调度的基本单位 凡未建立PCB的程序都不能作为一个独立的单位参与运行 5 异步性这是指进程按各自独立的 不可预知的速度向前推进 或说进程实体按异步方式运行 现在我们再来讨论进程的定义 曾有许多人从不同的角度对进程下过定义 其中较典型的进程定义有 1 进程是程序的一次执行 2 进程是一个程序及其数据在处理机上顺序执行时所发生的活动 3 进程是程序在一个数据集合上运行的过程 它是系统进行资源分配和调度的一个独立单位 2 进程的三种基本状态进程执行时的间断性决定了进程可能具有多种状态 事实上 运行中的进程可能具有以下三种基本状态 1 就绪 Ready 状态当进程已分配到除CPU以外的所有必要资源后 只要再获得CPU 便可立即执行 进程这时的状态称为就绪状态 在一个系统中处于就绪状态的进程可能有多个 通常将它们排成一个队列 称为就绪队列 2 执行状态进程已获得CPU 其程序正在执行 在单处理机系统中 只有一个进程处于执行状态 在多处理机系统中 则有多个进程处于执行状态 3 阻塞状态正在执行的进程由于发生某事件而暂时无法继续执行时 便放弃处理机而处于暂停状态 亦即进程的执行受到阻塞 把这种暂停状态称为阻塞状态 有时也称为等待状态或封锁状态 致使进程阻塞的典型事件有 请求I O 申请缓冲空间等 通常将这种处于阻塞状态的进程也排成一个队列 有的系统则根据阻塞原因的不同而把处于阻塞状态的进程排成多个队列 图2 5进程的三种基本状态及其转换 3 挂起状态1 引入挂起状态的原因在不少系统中进程只有上述三种状态 但在另一些系统中 又增加了一些新状态 最重要的是挂起状态 引入挂起状态的原因有 1 终端用户的请求 当终端用户在自己的程序运行期间发现有可疑问题时 希望暂时使自己的程序静止下来 亦即 使正在执行的进程暂停执行 若此时用户进程正处于就绪状态而未执行 则该进程暂不接受调度 以便用户研究其执行情况或对程序进行修改 我们把这种静止状态称为挂起状态 2 父进程请求 有时父进程希望挂起自己的某个子进程 以便考查和修改该子进程 或者协调各子进程间的活动 3 负荷调节的需要 当实时系统中的工作负荷较重 已可能影响到对实时任务的控制时 可由系统把一些不重要的进程挂起 以保证系统能正常运行 4 操作系统的需要 操作系统有时希望挂起某些进程 以便检查运行中的资源使用情况或进行记账 2 进程状态的转换在引入挂起状态后 又将增加从挂起状态 又称为静止状态 到非挂起状态 又称为活动状态 的转换 或者相反 可有以下几种情况 1 活动就绪 静止就绪 当进程处于未被挂起的就绪状态时 称此为活动就绪状态 表示为Readya 当用挂起原语Suspend将该进程挂起后 该进程便转变为静止就绪状态 表示为Readys 处于Readys状态的进程不再被调度执行 图2 6具有挂起状态的进程状态图 2 活动阻塞 静止阻塞 当进程处于未被挂起的阻塞状态时 称它是处于活动阻塞状态 表示为Blockeda 当用Suspend原语将它挂起后 进程便转变为静止阻塞状态 表示为Blockeds 处于该状态的进程在其所期待的事件出现后 将从静止阻塞变为静止就绪 3 静止就绪 活动就绪 处于Readys状态的进程 若用激活原语Active激活后 该进程将转变为Readya状态 4 静止阻塞 活动阻塞 处于Blockeds状态的进程 若用激活原语Active激活后 该进程将转变为Blockeda状态 图2 6示出了具有挂起状态的进程状态图 4 创建状态和终止状态1 创建状态创建一个进程一般要通过两个步骤 首先 为一个新进程创建PCB 并填写必要的管理信息 其次 把该进程转入就绪状态并插入就绪队列之中 当一个新进程被创建时 系统已为其分配了PCB 填写了进程标识等信息 但由于该进程所必需的资源或其它信息 如主存资源尚未分配等 一般而言 此时的进程已拥有了自己的PCB 但进程自身还未进入主存 即创建工作尚未完成 进程还不能被调度运行 其所处的状态就是创建状态 引入创建状态 是为了保证进程的调度必须在创建工作完成后进行 以确保对进程控制块操作的完整性 同时 创建状态的引入 也增加了管理的灵活性 操作系统可以根据系统性能或主存容量的限制 推迟创建状态进程的提交 对于处于创建状态的进程 获得了其所必需的资源 以及对其PCB初始化工作完成后 进程状态便可由创建状态转入就绪状态 2 终止状态进程的终止也要通过两个步骤 首先等待操作系统进行善后处理 然后将其PCB清零 并将PCB空间返还系统 当一个进程到达了自然结束点 或是出现了无法克服的错误 或是被操作系统所终结 或是被其他有终止权的进程所终结 它将进入终止状态 进入终止态的进程以后不能再执行 但在操作系统中依然保留一个记录 其中保存状态码和一些计时统计数据 供其它进程收集 一旦其它进程完成了对终止状态进程的信息提取之后 操作系统将删除该进程 图2 7示出了增加了创建状态和终止状态后 进程的三种基本状态及转换图衍变为五种状态及转换关系图 图2 7进程的五种基本状态及转换 图2 8具有创建 终止和挂起状态的进程状态图 如图2 8所示 引进创建和终止状态后 在进程状态转换时 相比较图2 7所示的进程五状态转换而言 需要增加考虑下面的几种情况 1 NULL 创建 一个新进程产生时 该进程处于创建状态 2 创建 活动就绪 在当前系统的性能和内存的容量均允许的情况下 完成对进程创建的必要操作后 相应的系统进程将进程的状态转换为活动就绪状态 3 创建 静止就绪 考虑到系统当前资源状况和性能要求 并不分配给新建进程所需资源 主要是主存资源 相应的系统进程将进程状态转为静止就绪状态 对换到外存 不再参与调度 此时进程创建工作尚未完成 4 执行 终止 当一个进程到达了自然结束点 或是出现了无法克服的错误 或是被操作系统所终结 或是被其他有终止权的进程所终结 进程即进终止状态 2 1 5进程控制块1 进程控制块的作用为了描述和控制进程的运行 系统为每个进程定义了一个数据结构 进程控制块PCB ProcessControlBlock 它是进程实体的一部分 是操作系统中最重要的记录型数据结构 PCB中记录了操作系统所需的 用于描述进程的当前情况以及控制进程运行的全部信息 进程控制块的作用是使一个在多道程序环境下不能独立运行的程序 含数据 成为一个能独立运行的基本单位 一个能与其它进程并发执行的进程 或者说 OS是根据PCB来对并发执行的进程进行控制和管理的 例如 当OS要调度某进程执行时 要从该进程的PCB中查出其现行状态及优先级 在调度到某进程后 要根据其PCB中所保存的处理机状态信息 设置该进程恢复运行的现场 并根据其PCB中的程序和数据的内存始址 找到其程序和数据 进程在执行过程中 当需要和与之合作的进程实现同步 通信或访问文件时 也都需要访问PCB 当进程由于某种原因而暂停执行时 又须将其断点的处理机环境保存在PCB中 可见 在进程的整个生命期中 系统总是通过PCB对进程进行控制的 亦即 系统是根据进程的PCB而不是任何别的什么而感知到该进程的存在的 所以说 PCB是进程存在的惟一标志 当系统创建一个新进程时 就为它建立了一个PCB 进程结束时又回收其PCB 进程于是也随之消亡 PCB可以被操作系统中的多个模块读或修改 如被调度程序 资源分配程序 中断处理程序以及监督和分析程序等读或修改 因为PCB经常被系统访问 尤其是被运行频率很高的进程及分派程序访问 故PCB应常驻内存 系统将所有的PCB组织成若干个链表 或队列 存放在操作系统中专门开辟的PCB区内 例如在Linux系统中用task struct数据结构来描述每个进程的进程控制块 在Windows操作系统中则使用一个执行体进程块 EPROCESS 来表示进程对象的基本属性 2 进程控制块中的信息1 进程标识符进程标识符用于惟一地标识一个进程 一个进程通常有两种标识符 1 内部标识符 在所有的操作系统中 都为每一个进程赋予了一个惟一的数字标识符 它通常是一个进程的序号 设置内部标识符主要是为了方便系统使用 2 外部标识符 它由创建者提供 通常是由字母 数字组成 往往是由用户 进程 在访问该进程时使用 为了描述进程的家族关系 还应设置父进程标识及子进程标识 此外 还可设置用户标识 以指示拥有该进程的用户 2 处理机状态处理机状态信息主要是由处理机的各种寄存器中的内容组成的 处理机在运行时 许多信息都放在寄存器中 当处理机被中断时 所有这些信息都必须保存在PCB中 以便在该进程重新执行时 能从断点继续执行 这些寄存器包括 通用寄存器 又称为用户可视寄存器 它们是用户程序可以访问的 用于暂存信息 在大多数处理机中 有8 32个通用寄存器 在RISC结构的计算机中可超过100个 指令计数器 其中存放了要访问的下一条指令的地址 程序状态字PSW 其中含有状态信息 如条件码 执行方式 中断屏蔽标志等 用户栈指针 指每个用户进程都有一个或若干个与之相关的系统栈 用于存放过程和系统调用参数及调用地址 栈指针指向该栈的栈顶 3 进程调度信息在PCB中还存放一些与进程调度和进程对换有关的信息 包括 进程状态 指明进程的当前状态 作为进程调度和对换时的依据 进程优先级 用于描述进程使用处理机的优先级别的一个整数 优先级高的进程应优先获得处理机 进程调度所需的其它信息 它们与所采用的进程调度算法有关 比如 进程已等待CPU的时间总和 进程已执行的时间总和等 事件 指进程由执行状态转变为阻塞状态所等待发生的事件 即阻塞原因 4 进程控制信息进程控制信息包括 程序和数据的地址 指进程的程序和数据所在的内存或外存地 首 址 以便再调度到该进程执行时 能从PCB中找到其程序和数据 进程同步和通信机制 指实现进程同步和进程通信时必需的机制 如消息队列指针 信号量等 它们可能全部或部分地放在PCB中 资源清单 即一张列出了除CPU以外的 进程所需的全部资源及已经分配到该进程的资源的清单 链接指针 它给出了本进程 PCB 所在队列中的下一个进程的PCB的首地址 3 进程控制块的组织方式1 链接方式这是把具有同一状态的PCB 用其中的链接字链接成一个队列 这样 可以形成就绪队列 若干个阻塞队列和空白队列等 对其中的就绪队列常按进程优先级的高低排列 把优先级高的进程的PCB排在队列前面 此外 也可根据阻塞原因的不同而把处于阻塞状态的进程的PCB排成等待I O操作完成的队列和等待分配内存的队列等 图2 9示出了一种链接队列的组织方式 图2 9PCB链接队列示意图 2 索引方式系统根据所有进程的状态建立几张索引表 例如 就绪索引表 阻塞索引表等 并把各索引表在内存的首地址记录在内存的一些专用单元中 在每个索引表的表目中 记录具有相应状态的某个PCB在PCB表中的地址 图2 10示出了索引方式的PCB组织 图2 10按索引方式组织PCB 2 2进程控制 进程控制是进程管理中最基本的功能 它用于创建一个新进程 终止一个已完成的进程 或终止一个因出现某事件而使其无法运行下去的进程 还可负责进程运行中的状态转换 如当一个正在执行的进程因等待某事件而暂时不能继续执行时 将其转换为阻塞状态 而当该进程所期待的事件出现时 又将该进程转换为就绪状态等等 进程控制一般是由OS的内核中的原语来实现的 原语 Primitive 是由若干条指令组成的 用于完成一定功能的一个过程 它与一般过程的区别在于 它们是 原子操作 ActionOperation 所谓原子操作 是指一个操作中的所有动作要么全做 要么全不做 换言之 它是一个不可分割的基本单位 因此 在执行过程中不允许被中断 原子操作在管态下执行 常驻内存 图2 11进程树 2 2 1进程的创建1 进程图 ProcessGraph 进程图是用于描述一个进程的家族关系的有向树 如图2 11所示 图中的结点 圆圈 代表进程 在进程D创建了进程I之后 称D是I的父进程 ParentProcess I是D的子进程 ProgenyProcess 2 引起创建进程的事件在多道程序环境中 只有 作为 进程 时 才能在系统中运行 因此 为使程序能运行 就必须为它创建进程 导致一个进程去创建另一个进程的典型事件 可有以下四类 1 用户登录 在分时系统中 用户在终端键入登录命令后 如果是合法用户 系统将为该终端建立一个进程 并把它插入就绪队列中 2 作业调度 在批处理系统中 当作业调度程序按一定的算法调度到某作业时 便将该作业装入内存 为它分配必要的资源 并立即为它创建进程 再插入就绪队列中 3 提供服务 当运行中的用户程序提出某种请求后 系统将专门创建一个进程来提供用户所需要的服务 例如 用户程序要求进行文件打印 操作系统将为它创建一个打印进程 这样 不仅可使打印进程与该用户进程并发执行 而且还便于计算出为完成打印任务所花费的时间 4 应用请求 在上述三种情况下 都是由系统内核为它创建一个新进程 而第4类事件则是基于应用进程的需求 由它自己创建一个新进程 以便使新进程以并发运行方式完成特定任务 例如 某应用程序需要不断地从键盘终端输入数据 继而又要对输入数据进行相应的处理 然后 再将处理结果以表格形式在屏幕上显示 该应用进程为使这几个操作能并发执行 以加速任务的完成 可以分别建立键盘输入进程 表格输出进程 3 进程的创建 CreationofProcess 一旦操作系统发现了要求创建新进程的事件后 便调用进程创建原语Creat 按下述步骤创建一个新进程 1 申请空白PCB 为新进程申请获得惟一的数字标识符 并从PCB集合中索取一个空白PCB 2 为新进程分配资源 为新进程的程序和数据以及用户栈分配必要的内存空间 显然 此时操作系统必须知道新进程所需内存的大小 对于批处理作业 其大小可在用户提出创建进程要求时提供 若是为应用进程创建子进程 也应是在该进程提出创建进程的请求中给出所需内存的大小 对于交互型作业 用户可以不给出内存要求而由系统分配一定的空间 如果新进程要共享某个已在内存的地址空间 即已装入内存的共享段 则必须建立相应的链接 3 初始化进程控制块 PCB的初始化包括 初始化标识信息 将系统分配的标识符和父进程标识符填入新PCB中 初始化处理机状态信息 使程序计数器指向程序的入口地址 使栈指针指向栈顶 初始化处理机控制信息 将进程的状态设置为就绪状态或静止就绪状态 对于优先级 通常是将它设置为最低优先级 除非用户以显式方式提出高优先级要求 4 将新进程插入就绪队列 如果进程就绪队列能够接纳新进程 便将新进程插入就绪队列 2 2 2进程的终止1 引起进程终止的事件1 正常结束在任何计算机系统中 都应有一个用于表示进程已经运行完成的指示 例如 在批处理系统中 通常在程序的最后安排一条Holt指令或终止的系统调用 当程序运行到Holt指令时 将产生一个中断 去通知OS本进程已经完成 在分时系统中 用户可利用Logsoff去表示进程运行完毕 此时同样可产生一个中断 去通知OS进程已运行完毕 2 异常结束在进程运行期间 由于出现某些错误和故障而迫使进程终止 TerminationofProcess 这类异常事件很多 常见的有下述几种 1 越界错误 这是指程序所访问的存储区已越出该进程的区域 2 保护错 这是指进程试图去访问一个不允许访问的资源或文件 或者以不适当的方式进行访问 例如 进程试图去写一个只读文件 3 非法指令 这是指程序试图去执行一条不存在的指令 出现该错误的原因 可能是程序错误地转移到数据区 把数据当成了指令 4 特权指令错 这是指用户进程试图去执行一条只允许OS执行的指令 5 运行超时 这是指进程的执行时间超过了指定的最大值 6 等待超时 这是指进程等待某事件的时间超过了规定的最大值 7 算术运算错 这是指进程试图去执行一个被禁止的运算 例如被0除 8 I O故障 这是指在I O过程中发生了错误等 3 外界干预外界干预并非指在本进程运行中出现了异常事件 而是指进程应外界的请求而终止运行 这些干预有 1 操作员或操作系统干预 由于某种原因 例如 发生了死锁 由操作员或操作系统终止该进程 2 父进程请求 由于父进程具有终止自己的任何子孙进程的权力 因而当父进程提出请求时 系统将终止该进程 3 父进程终止 当父进程终止时 OS也将它的所有子孙进程终止 2 进程的终止过程如果系统中发生了上述要求终止进程的某事件 OS便调用进程终止原语 按下述过程去终止指定的进程 1 根据被终止进程的标识符 从PCB集合中检索出该进程的PCB 从中读出该进程的状态 2 若被终止进程正处于执行状态 应立即终止该进程的执行 并置调度标志为真 用于指示该进程被终止后应重新进行调度 3 若该进程还有子孙进程 还应将其所有子孙进程予以终止 以防它们成为不可控的进程 4 将被终止进程所拥有的全部资源 或者归还给其父进程 或者归还给系统 5 将被终止进程 PCB 从所在队列 或链表 中移出 等待其他程序来搜集信息 2 2 3进程的阻塞与唤醒1 引起进程阻塞和唤醒的事件有下述几类事件会引起进程阻塞或被唤醒 1 请求系统服务当正在执行的进程请求操作系统提供服务时 由于某种原因 操作系统并不立即满足该进程的要求时 该进程只能转变为阻塞状态来等待 例如 一进程请求使用某资源 如打印机 由于系统已将打印机分配给其他进程而不能分配给请求进程 这时请求者进程只能被阻塞 仅在其他进程在释放出打印机的同时 才将请求进程唤醒 2 启动某种操作当进程启动某种操作后 如果该进程必须在该操作完成之后才能继续执行 则必须先使该进程阻塞 以等待该操作完成 例如 进程启动了某I O设备 如果只有在I O设备完成了指定的I O操作任务后进程才能继续执行 则该进程在启动了I O操作后 便自动进入阻塞状态去等待 在I O操作完成后 再由中断处理程序或中断进程将该进程唤醒 3 新数据尚未到达对于相互合作的进程 如果其中一个进程需要先获得另一 合作 进程提供的数据后才能对数据进行处理 则只要其所需数据尚未到达 该进程只有 等待 阻塞 例如 有两个进程 进程A用于输入数据 进程B对输入数据进行加工 假如A尚未将数据输入完毕 则进程B将因没有所需的处理数据而阻塞 一旦进程A把数据输入完毕 便可去唤醒进程B 4 无新工作可做系统往往设置一些具有某特定功能的系统进程 每当这种进程完成任务后 便把自己阻塞起来以等待新任务到来 例如 系统中的发送进程 其主要工作是发送数据 若已有的数据已全部发送完成而又无新的发送请求 这时 发送 进程将使自己进入阻塞状态 仅当又有进程提出新的发送请求时 才将发送进程唤醒 2 进程阻塞过程正在执行的进程 当发现上述某事件时 由于无法继续执行 于是进程便通过调用阻塞原语block把自己阻塞 可见 进程的阻塞是进程自身的一种主动行为 进入block过程后 由于此时该进程还处于执行状态 所以应先立即停止执行 把进程控制块中的现行状态由 执行 改为 阻塞 并将PCB插入阻塞队列 如果系统中设置了因不同事件而阻塞的多个阻塞队列 则应将本进程插入到具有相同事件的阻塞 等待 队列 最后 转调度程序进行重新调度 将处理机分配给另一就绪进程并进行切换 亦即 保留被阻塞进程的处理机状态 在PCB中 再按新进程的PCB中的处理机状态设置CPU的环境 3 进程唤醒过程当被阻塞进程所期待的事件出现时 如I O完成或其所期待的数据已经到达 则由有关进程 比如用完并释放了该I O设备的进程 调用唤醒原语wakeup 将等待该事件的进程唤醒 唤醒原语执行的过程是 首先把被阻塞的进程从等待该事件的阻塞队列中移出 将其PCB中的现行状态由阻塞改为就绪 然后再将该PCB插入到就绪队列中 应当指出 block原语和wakeup原语是一对作用刚好相反的原语 因此 如果在某进程中调用了阻塞原语 则必须在与之相合作的另一进程中或其他相关的进程中安排唤醒原语 以能唤醒阻塞进程 否则 被阻塞进程将会因不能被唤醒而长久地处于阻塞状态 从而再无机会继续运行 2 2 4进程的挂起与激活1 进程的挂起当出现了引起进程挂起的事件时 比如 用户进程请求将自己挂起 或父进程请求将自己的某个子进程挂起 系统将利用挂起原语suspend 将指定进程或处于阻塞状态的进程挂起 挂起原语的执行过程是 首先检查被挂起进程的状态 若处于活动就绪状态 便将其改为静止就绪 对于活动阻塞状态的进程 则将之改为静止阻塞 为了方便用户或父进程考查该进程的运行情况而把该进程的PCB复制到某指定的内存区域 最后 若被挂起的进程正在执行 则转向调度程序重新调度 2 进程的激活过程当发生激活进程的事件时 例如 父进程或用户进程请求激活指定进程 若该进程驻留在外存而内存中已有足够的空间时 则可将在外存上处于静止就绪状态的该进程换入内存 这时 系统将利用激活原语active 将指定进程激活 激活原语先将进程从外存调入内存 检查该进程的现行状态 若是静止就绪 便将之改为活动就绪 若为静止阻塞 便将之改为活动阻塞 假如采用的是抢占调度策略 则每当有新进程进入就绪队列时 应检查是否要进行重新调度 即由调度程序将被激活进程与当前进程进行优先级的比较 如果被激活进程的优先级更低 就不必重新调度 否则 立即剥夺当前进程的运行 把处理机分配给刚被激活的进程 2 3进程同步 2 3 1进程同步的基本概念1 两种形式的制约关系在多道程序环境下 当程序并发执行时 由于资源共享和进程合作 使同处于一个系统中的诸进程之间可能存在着以下两种形式的制约关系 1 间接相互制约关系 同处于一个系统中的进程 通常都共享着某种系统资源 如共享CPU 共享I O设备等 所谓间接相互制约即源于这种资源共享 例如 有两个进程A和B 如果在A进程提出打印请求时 系统已将惟一的一台打印机分配给了进程B 则此时进程A只能阻塞 一旦进程B将打印机释放 则A进程才能由阻塞改为就绪状态 2 直接相互制约关系 这种制约主要源于进程间的合作 例如 有一输入进程A通过单缓冲向进程B提供数据 当该缓冲空时 计算进程因不能获得所需数据而阻塞 而当进程A把数据输入缓冲区后 便将进程B唤醒 反之 当缓冲区已满时 进程A因不能再向缓冲区投放数据而阻塞 当进程B将缓冲区数据取走后便可唤醒A 2 临界资源在第一章中我们曾经介绍过 许多硬件资源如打印机 磁带机等 都属于临界资源 CriticalResouce 诸进程间应采取互斥方式 实现对这种资源的共享 下面我们将通过一个简单的例子来说明这一过程 生产者 消费者 producer consumer 问题是一个著名的进程同步问题 它描述的是 有一群生产者进程在生产产品 并将这些产品提供给消费者进程去消费 为使生产者进程与消费者进程能并发执行 在两者之间设置了一个具有n个缓冲区的缓冲池 生产者进程将它所生产的产品放入一个缓冲区中 消费者进程可从一个缓冲区中取走产品去消费 尽管所有的生产者进程和消费者进程都是以异步方式运行的 但它们之间必须保持同步 即不允许消费者进程到一个空缓冲区去取产品 也不允许生产者进程向一个已装满产品且尚未被取走的缓冲区中投放产品 我们可利用一个数组来表示上述的具有n个 0 1 n 1 缓冲区的缓冲池 用输入指针in来指示下一个可投放产品的缓冲区 每当生产者进程生产并投放一个产品后 输入指针加1 用一个输出指针out来指示下一个可从中获取产品的缓冲区 每当消费者进程取走一个产品后 输出指针加1 由于这里的缓冲池是组织成循环缓冲的 故应把输入指针加1表示成in in 1 modn 输出指针加1表示成out out 1 modn 当 in 1 modn out时表示缓冲池满 而in out则表示缓冲池空 此外 还引入了一个整型变量counter 其初始值为0 每当生产者进程向缓冲池中投放一个产品后 使counter加1 反之 每当消费者进程从中取走一个产品时 使counter减1 生产者和消费者两进程共享下面的变量 Varn integer typeitem varbuffer array 0 1 n 1 ofitem in out 0 1 n 1 counter 0 1 n 指针in和out初始化为1 在生产者和消费者进程的描述中 noop是一条空操作指令 whileconditiondono op语句表示重复的测试条件 condication 重复测试应进行到该条件变为false 假 即到该条件不成立时为止 在生产者进程中使用一局部变量nextp 用于暂时存放每次刚生产出来的产品 而在消费者进程中 则使用一个局部变量nextc 用于存放每次要消费的产品 consumer repeatwhilecounter 0dono op nextc buffer out out out 1 modn counter counter 1 consumertheiteminnextc untilfalse 虽然上面的生产者程序和消费者程序在分别看时都是正确的 而且两者在顺序执行时其结果也会是正确的 但若并发执行时就会出现差错 问题就在于这两个进程共享变量counter 生产者对它做加1操作 消费者对它做减1操作 这两个操作在用机器语言实现时 常可用下面的形式描述 register1 counter register2 counter register1 register1 1 register2 register2 1 counter register1 counter register2 假设counter的当前值是5 如果生产者进程先执行左列的三条机器语言语句 然后消费者进程再执行右列的三条语句 则最后共享变量counter的值仍为5 反之 如果让消费者进程先执行右列的三条语句 然后再让生产者进程执行左列的三条语句 则counter值也还是5 但是 如果按下述顺序执行 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 正确的counter值应当是5 但现在是4 读者可以自己试试 倘若再将两段程序中各语句交叉执行的顺序改变 将可看到又可能得到counter 6的答案 这表明程序的执行已经失去了再现性 为了预防产生这种错误 解决此问题的关键是应把变量counter作为临界资源处理 亦即 令生产者进程和消费者进程互斥地访问变量counter 3 临界区由前所述可知 不论是硬件临界资源 还是软件临界资源 多个进程必须互斥地对它进行访问 人们把在每个进程中访问临界资源的那段代码称为临界区 criticalsection 显然 若能保证诸进程互斥地进入自己的临界区 便可实现诸进程对临界资源的互斥访问 为此 每个进程在进入临界区之前 应先对欲访问的临界资源进行检查 看它是否正被访问 如果此刻该临界资源未被访问 进程便可进入临界区对该资源进行访问 并设置它正被访问的标志 如果此刻该临界资源正被某进程访问 则本进程不能进入临界区 因此 必须在临界区前面增加一段用于进行上述检查的代码 把这段代码称为进入区 entrysection 相应地 在临界区后面也要加上一段称为退出区 exitsection 的代码 用于将临界区正被访问的标志恢复为未被访问的标志 4 同步机制应遵循的规则为实现进程互斥地进入自已的临界区 可用软件方法 更多的是在系统中设置专门的同步机构来协调各进程间的运行 所有同步机制都应遵循下述四条准则 1 空闲让进 当无进程处于临界区时 表明临界资源处于空闲状态 应允许一个请求进入临界区的进程立即进入自己的临界区 以有效地利用临界资源 2 忙则等待 当已有进程进入临界区时 表明临界资源正在被访问 因而其它试图进入临界区的进程必须等待 以保证对临界资源的互斥访问 3 有限等待 对要求访问临界资源的进程 应保证在有限时间内能进入自己的临界区 以免陷入 死等 状态 4 让权等待 当进程不能进入自己的临界区时 应立即释放处理机 以免进程陷入 忙等 状态 2 3 2信号量机制1 整型信号量最初由Dijkstra把整型信号量定义为一个用于表示资源数目的整型量S 它与一般整型量不同 除初始化外 仅能通过两个标准的原子操作 AtomicOperation wait S 和signal S 来访问 很长时间以来 这两个操作一直被分别称为P V操作 Wait S 和signal S 操作可描述为 wait S whileS 0dono op S S 1 signal S S S 1 wait S 和signal S 是两个原子操作 因此 它们在执行时是不可中断的 亦即 当一个进程在修改某信号量时 没有其他进程可同时对该信号量进行修改 此外 在wait操作中 对S值的测试和做S S 1操作时都不可中断 2 记录型信号量在整型信号量机制中的wait操作 只要是信号量S 0 就会不断地测试 因此 该机制并未遵循 让权等待 的准则 而是使进程处于 忙等 的状态 记录型信号量机制则是一种不存在 忙等 现象的进程同步机制 但在采取了 让权等待 的策略后 又会出现多个进程等待访问同一临界资源的情况 为此 在信号量机制中 除了需要一个用于代表资源数目的整型变量value外 还应增加一个进程链表指针L 用于链接上述的所有等待进程 记录型信号量是由于它采用了记录型的数据结构而得名的 它所包含的上述两个数据项可描述为 typesemaphore recordvalue integer L listofprocess end 相应地 wait S 和signal S 操作可描述为 procedurewait S varS semaphore beginS value S value 1 ifS value 0thenblock S L endproceduresignal S varS semaphore beginS value S value 1 ifS value 0thenwakeup S L end 在记录型信号量机制中 S value的初值表示系统中某类资源的数目 因而又称为资源信号量 对它的每次wait操作 意味着进程请求一个单位的该类资源 使系统中可供分配的该类资源数减少一个 因此描述为S value S value 1 当S value 0时 表示该类资源已分配完毕 因此进程应调用block原语 进行自我阻塞 放弃处理机 并插入到信号量链表S L中 可见 该机制遵循了 让权等待 准则 此时S value的绝对值表示在该信号量链表中已阻塞进程的数目 对信号量的每次signal操作 表示执行进程释放一个单位资源 使系统中可供分配的该类资源数增加一个 故S value S value 1操作表示资源数目加1 若加1后仍是S value 0 则表示在该信号量链表中 仍有等待该资源的进程被阻塞 故还应调用wakeup原语 将S L链表中的第一个等待进程唤醒 如果S value的初值为1 表示只允许一个进程访问临界资源 此时的信号量转化为互斥信号量 用于进程互斥 3 AND型信号量上述的进程互斥问题 是针对各进程之间只共享一个临界资源而言的 在有些应用场合 是一个进程需要先获得两个或更多的共享资源后方能执行其任务 假定现有两个进程A和B 他们都要求访问共享数据D和E 当然 共享数据都应作为临界资源 为此 可为这两个数据分别设置用于互斥的信号量Dmutex和Emutex 并令它们的初值都是1 相应地 在两个进程中都要包含两个对Dmutex和Emutex的操作 即 processA processB wait Dmutex wait Emutex wait Emutex wait Dmutex 若进程A和B按下述次序交替执行wait操作 processA wait Dmutex 于是Dmutex 0processB wait Emutex 于是Emutex 0processA wait Emutex 于是Emutex 1A阻塞processB wait Dmutex 于是Dmutex 1B阻塞 最后 进程A和B处于僵持状态 在无外力作用下 两者都将无法从僵持状态中解脱出来 我们称此时的进程A和B已进入死锁状态 显然 当进程同时要求的共享资源愈多时 发生进程死锁的可能性也就愈大 AND同步机制的基本思想是 将进程在整个运行过程中需要的所有资源 一次性全部地分配给进程 待进程使用完后再一起释放 只要尚有一个资源未能分配给进程 其它所有可能为之分配的资源也不分配给它 亦即 对若干个临界资源的分配 采取原子操作方式 要么把它所请求的资源全部分配到进程 要么一个也不分配 由死锁理论可知 这样就可避免上述死锁情况的发生 为此 在wait操作中 增加了一个 AND 条件 故称为AND同步 或称为同时wait操作 即Swait Simultaneouswait 定义如下 Swait S1 S2 Sn ifSi 1and andSn 1thenfori 1tondoSi Si 1 endforelseplacetheprocessinthewaitingqueueassociatedwiththefirstSifoundwithSi 1 andsettheprogramcountofthisprocesstothebeginningofSwaitoperationendifSsignal S1 S2 Sn fori 1tondoSi Si 1 RemovealltheprocesswaitinginthequeueassociatedwithSiintothereadyqueue endfor 4 信号量集在记录型信号量机制中 wait S 或signal S 操作仅能对信号量施以加1或减1操作 意味着每次只能获得或释放一个单位的临界资源 而当一次需要N个某类临界资源时 便要进行N次wait S 操作 显然这是低效的 此外 在有些情况下 当资源数量低于某一下限值时 便不予以分配 因而 在每次分配之前 都必须测试该资源的数量 看其是否大于其下限值 基于上述两点 可以对AND信号量机制加以扩充 形成一般化的 信号量集 机制 Swait操作可描述如下 其中S为信号量 d为需求值 而t为下限值 Swait S1 t1 d1 Sn tn dn ifSi t1and andSn tnthenfori 1tondoSi Si di endforelsePlacetheexecutingprocessinthewaitingqueueofthefirstSiwithSi tiandsetitsprogramcountertothebeginningoftheSwaitOperation endive Ssignal S1 d1 Sn dn fori 1tondoSi Si di RemovealltheprocesswaitinginthequeueassociatedwithSiintothereadyqueueendfor 下面我们讨论一般 信号量集 的几种特殊情况 1 Swait S d d 此时在信号量集中只有一个信号量S 但允许它每次申请d个资源 当现有资源数少于d时 不予分配 2 Swait S 1 1 此时的信号量集已蜕化为一般的记录型信号量 S 1时 或互斥信号量 S 1时 3 Swait S 1 0 这是一种很特殊且很有用的信号量操作 当S 1时 允许多个进程进入某特定区 当S变为0后 将阻止任何进程进入特定区 换言之 它相当于一个可控开关 2 3 3信号量的应用1 利用信号量实现进程互斥为使多个进程能互斥地访问某临界资源 只须为该资源设置一互斥信号量mutex 并设其初始值为1 然后将各进程访问该资源的临界区CS置于wait mutex 和signal mutex 操作之间即可 这样 每个欲访问该临界资源的进程在进入临界区之前 都要先对mutex执行wait操作 若该资源此刻未被访问 本次wait操作必然成功 进程便可进入自己的临界区 这时若再有其他进程也欲进入自己的临界区 此时由于对mutex执行wait操作定会失败 因而该进程阻塞 从而保证了该临界资源能被互斥地访问 当访问临界资源的进程退出临界区后 又应对mutex执行signal操作 以便释放该临界资源 利用信号量实现进程互斥的进程可描述如下 Varmutex semaphore 1 beginparbeginprocess1 beginrepeatwait mutex criticalsectionsignal mutex remainderseetionuntilfalse end process2 beginrepeatwait mutex criticalsectionsignal mutex remaindersectionuntilfalse endparend 2 利用信号量实现前趋关系还可利用信号量来描述程序或语句之间的前趋关系 设有两个并发执行的进程P1和P2 P1中有语句S1 P2中有语句S2 我们希望在S1执行后再执行S2 为实现这种前趋关系 我们只须使进程P1和P2共享一个公用信号量S 并赋予其初值为0 将signal S 操作放在语句S1后面 而在S2语句前面插入wait S 操作 即在进程P1中 用S1 signal S 在进程P2中 用wait S S2 由于S被初始化为0 这样 若P2先执行必定阻塞 只有在进程P1执行完S1 signal S 操作后使S增为1时 P2进程方能执行语句S2成功 同样 我们可以利用信号量 按照语句间的前趋关系 见图2 12 写出一个更为复杂的可并发执行的程序 图2 12示出了一个前趋图 其中S1 S2 S3 S6是最简单的程序段 只有一条语句 为使各程序段能正确执行 应设置若干个初始值为 0 的信号量 如为保证S1 S2 S1 S3的前趋关系 应分别设置信号量a和b 同样 为了保证S2 S4 S2 S5 S3 S6 S4 S6和S5 S6 应设置信号量c d e f g Vara b c d e f g semaphore 0 0 0 0 0 0 0 beginparbeginbeginS1 signal a signal b end beginwait a S2 signal c signal d end beginwait b S3 signal e end beginwait c S4 signal f end beginwait d S5 signal g end beginwait e wait f wait g S6 end parendend 图2 12前趋图举例 2 3 4管程机制1 管程的定义系统中的各种硬件资源和软件资源 均可用数据结构抽象地描述其资源特性 即用少量信息和对该资源所执行的操作来表征该资源 而忽略了它们的内部结构和实现细节 例如 对一台电传机 可用与分配该资源有关的状态信息 busy或free 和对它执行请求与释放的操作 以及等待该资源的进程队列来描述 又如 一个FIFO队列 可用其队长 队首和队尾以及在该队列上执行的一组操作来描述 利用共享数据结构抽象地表示系统中的共享资源 而把对该共享数据结构实施的操作定义为一组过程 如资源的请求和释放过程request和release 进程对共享资源的申请 释放和其它操作 都是通过这组过程对共享数据结构的操作来实现的 这组过程还可以根据资源的情况 或接受或阻塞进程的访问 确保每次仅有一个进程使用共享资源 这样就可以统一管理对共享资源的所有访问 实现进程互斥 代表共享资源的数据结构 以及由对该共享数据结构实施操作的一组过程所组成的资源管理程序 共同构成了一个操作系统的资源管理模块 我们称之为管程 管程被请求和释放资源的进程所调用 Hans- 配套讲稿:
如PPT文件的首页显示word图标,表示该PPT已包含配套word讲稿。双击word图标可打开word文档。
- 特殊限制:
部分文档作品中含有的国旗、国徽等图片,仅作为作品整体效果示例展示,禁止商用。设计者仅对作品中独创性部分享有著作权。
- 关 键 词:
- 操作系统-汤小丹-第四版 操作系统 汤小丹 第四
装配图网所有资源均是用户自行上传分享,仅供网友学习交流,未经上传用户书面授权,请勿作他用。
关于本文
相关资源
更多
相关搜索