第二章-进程的描述与控制

第二章第二章 进程的描述与控制进程的描述与控制 第第 1 节节 进程的基本概念进程的基本概念 一 程序的顺序执行一 程序的顺序执行 程序是一个在时间上有严格次序的指令序列 仅当前一操作 指 令 执行完后 才能执行后继操作 如下图 b 如果在单道环境下对用户作业的处理 总须先输入用户的程序 和数据 然后进行计算 最后才能打印计算结果 见下图 a a 程序的顺序执行 b 三条语句的顺序执行 I1C1P1I2C2P2S1S2S3 程序顺序执行的前驱图 所以 在单道系统中 程序执行具有以下特征 1 顺序性 2 封闭性 3 可再现性 P33 34 其中最大特征就是程序的顺序执行 二 前趋图二 前趋图 描述程序执行顺序的工具描述程序执行顺序的工具 前趋图 Precedence Graph 是一个有向无循环图 记为 DAG Directed Acyclic Graph 用于描述进程之间执行的前后关系 图中 的每个结点可用于描述一个进程 一段程序 乃至一条语句 结点 间的有向边 则用于表示两个结点之间存在的偏序关系 Partial Order 或前趋关系 Precedence Relation 如果 Pi Pj 称 Pi 是 Pj 的直接前趋 而称 Pj 是 Pi 的直接后继 在前趋图中 把没有前趋的结点称为初始结点 Initial Node 把没有 后继的结点称为终止结点 Final Node 每个结点还具有一个重量 Weight 用于表示该结点所含有的程序量或结点的执行时间 P1P3P8P9 P4 P2 P5 P6 P7 S1 S2 S3 a 具有九个结点的前趋图 b 具有循环的前趋图 前趋图 对于上图 a 所示的前趋图 存在下述前趋关系 P1 P2 P1 P3 P1 P4 P2 P5 P3 P5 P4 P6 P4 P7 P5 P8 P6 P8 P7 P9 P8 P9 对于具有下述四条语句的程序段 可以用右边的前驱图描述语 句间的前驱关系 前趋图 S1 a x 2 S2 b y 4 S3 c a b S4 d c b 三 程序的并发执行三 程序的并发执行 1 什么是并发执行 并行执行 回顾概念 在下图中 每一个作业由输入程序 计算程序和打印程序组成 以至对一个作业的输入 计算和打印三个操作 必须顺序执行 三 操作之间存在着 Ii Ci Pi 这样的前趋关系 S1 S2 S3S4 对于同类的四个作业 每个作业的内部操作之间 作业和作业 的操作之间存在下图描述的前驱关系 P1P2P3P4 I1I2I3I4 C1C2C3C4 程序并发执行时的前趋图 讨论 哪些操作的执行必须是顺序的 哪些操作的执行是可以 并行的 在该例中存在下述前趋关系 Ii Ci Ci Pi Ii Ii 1 Ci Ci 1 Pi Pi 1 而 Ii 1 和 Ci 及 Pi 1 是重迭的 亦即在 Pi 1 和 Ci 以及 Ii 1 之间 可以并行执行 多程序并发执行表现为 这些程序的执行在时间上是重叠的 一个程序的执行尚未结束 另一个程序的执行已经开始 即使这种 重叠是很小的一部分 前驱图上重叠的部分 是不同程序在不同资 源上并行工作形成的 程序的并发执行可进一步分 为 不同程序间的并发执行 同一程序中不同程序段 线程 的并发执行 例如 在一个程序中有 5 个程序段 上图 2 程序并发执行带来的影响 与程序的顺序执行相比较 1 程序运行的间断性 异步性 2 程序的执行失去了封闭性和以此为基础的可再现性 例如 有两个循环程序 A 和 B 它们共享一个变量 n 初值为 10 并发程序相互影响示意图 n n 1 在 Print n 和 n 0 之前 此时得到的 n 值分别为 11 11 0 n n 1 在 Print n 和 n 0 之后 此时得到的 n 值分别为 10 0 1 n n 1 在 Print n 和 n 0 之间 此时得到的 n 值分别为 10 11 0 3 程序之间由于资源共享与竞争 形成了相互制约 为了合理管理系统资源 协调各程序间在执行时对资源的竞争 需要一个记录和描述程序执行过程的基本单位 于是引进了 进程 这一概念 四 进程的定义四 进程的定义 1 较典型的进程定义有 1 进程是一个程序在给定活动空间和初始环境下 在一个处理机 上的一次执行过程 2 进程是程序在一个数据集合上运行的过程 它是系统进行资源 分配和调度的一个独立单位 2 进程实体 程序段 相关数据 PCB 进程控制块 是管理进程 的数据结构 程序与数据 描述进程本身所应完成的功能 PCB 记录进程的动态特征 记录进程与其他进程 与系统资源间 的关系 进程 控制块 PCB 程序 与 数据 3 进程的特征 1 结构特征 2 动态性 3 并发性 4 独立性 5 异步性 P36 在引入了进程实体的概念后 我们可以把传统 OS 中的进程定 义为 进程是进程实体的一次运行过程 是系统进行资源分配和 调度的一个独立单位 五 进程的三种基本状态五 进程的三种基本状态 执行状态 进程已获得当前运行所必需的资源 并已获得处理机 它的程序正在处理机上执行 P36 就绪状态 进程已获得除 CPU 之外的 继续往下运行所必需的资源 一旦得到 CPU 控制权 立即可以投入运行 就绪队列 P36 阻塞状态 等待状态 进程由于等待某一事件的发生而暂停执行 这时 即使给它 CPU 控制权 它也无法执行 等待队列 P36 进程的三种基本状态间的转换 进程的三种基本状态及其转换图 再增加两种常见状态 创建状态 创建进程是一个复杂的过程 要持续一段时间 P37 终止状态 撤销进程也是一个复杂的过程 要持续一段时间 P37 进程的五种基本状态及转换图 六 挂起状态六 挂起状态 在一般 OS 中 进程的基本状态只有前面三种 而在另一些 OS 中 由于控制的需要 引入 挂起 状态 挂起 状态分为静止就绪和静止阻塞两种 挂起 就意味着 暂停对该进程分配 CPU 资源 挂起状态同样有对应的队列 引入挂 起后 进程的 5 种状态转换 具有挂起状态的进程状态转换图 具有创建 终止和挂起状态的进程状态图 引起 挂起 的原因 P38 1 负荷调节的需要 2 终端用户的请求 3 父进程请求 4 操作系统的需要 七 进程控制块七 进程控制块 PCB 1 进程控制块 是进程管理的数据结构 包含了一个进程的描述信 息 控制信息 资源信息的 它随进程的创建而产生 在进程执行 的过程中动态地记录进程各信息的变化 当一个进程完成其功能后 系统则回收 PCB 进程也随之消失 PCB 是进程存在的唯一标志 是操作系统的一种资源 2 进程控制块中的信息 1 进程标识符 进程标识符用于唯一标识一个进程 一个进程通常有两种标识符 内部标识符 在所有的操作系统中 都为每一个进程赋予一 个唯一的数字标识符 它通常是一个进程的序号 设置内部标识符 主要是为了方便系统使用 外部标识符 它由创建者提供 通常是由字母 数字组成 往往是由用户 进程 在访问该进程时使用 为了描述进程的家族关 系 还应设置父进程标识及子进程标识 此外 还可设置用户标识 以指示拥有该进程的用户 2 处理机状态 处理机上下文 处理机状态信息主要包括进程运行过程中处理机的各种寄存器 中的内容 通用寄存器 又称为用户可视寄存器 它们是用户 程序可以访问的 用于暂存信息 在大多数处理机中 有 8 32 个 通用寄存器 在 RISC 结构的计算机中可超过 100 个 指令计数 器 其中存放了要访问的下一条指令的地址 程序状态字 PSW 其中含有状态信息 如条件码 执行方式 中断屏蔽标志等 用户栈指针 指每个用户进程都有一个或若干个与之相关的系 统栈 用于存放过程和系统调用参数及调用地址 栈指针指向该栈 的栈顶 3 进程调度信息 在 PCB 中还存放一些与进程调度和进程对换有关的信息 包括 进程状态 指明进程的当前状态 作为进程调度和对换时的依 据 进程优先级 用于描述进程使用处理机的优先级别的一个整 数 优先级高的进程应优先获得处理机 进程调度所需的其它 信息 它们与所采用的进程调度算法有关 比如 进程已等待 CPU 的时间总和 进程已执行的时间总和等 事件 是指进程由执行 状态转变为阻塞状态所等待发生的事件 即阻塞原因 4 进程控制信息 进程控制信息包括 程序和数据的地址 是指进程的程序和 数据所在的内存或外存地 首 址 以便再调度到该进程执行时 能 从 PCB 中找到其程序和数据 进程同步和通信机制 指实现进 程同步和进程通信时必需的机制 如消息队列指针 信号量等 它 们可能全部或部分地放在 PCB 中 资源清单 是一张列出了除除 CPU 以外以外的 进程所需的全部资源及已经分配到该进程的资源的清 单 链接指针 它给出了本进程 PCB 所在队列中的下一个进程 的 PCB 的首地址 3 进程控制块的作用 标识进程的存在 动态地记录进程运行过程 中的各类信息 如进程状态 中断现场 进程的优先级等 提供给 OS 的进程管理和进程调度使用 实现进程的间断性运行方式 实现 与其他进程的同步与通信 P40 4 进程的队列 在系统中存在的各种进程队列 就是由进程的 PCB 组成的 PCB 组成队列的方式 链接方式 索引方式 1 链接方式 PCB 链接队列示意图 2 索引方式 按索引方式组织 PCB 示意图 5 进程与程序的区别 1 程序是静态的 进程是动态的 2 进程更能真实地描述并发 而程序不能 3 一个程序可对应多个进程 4 进程有生命周期 有诞生有消亡 是短暂的 程序是相对长久 的 5 程序可作为软件资源长期保存 而进程只是一次执行过程 是 暂时的 6 进程是系统分配 调度的独立单位 能与其他进程并发执行 7 进程包含程序 数据 PCB 三部分 8 进程具有创建其他进程的功能 而程序没有 第第 2 节节 进程控制进程控制 一 一 OS 的内核的内核 1 什么是 OS 的内核 一个完整的 OS 是由内核和外壳两大部分组 成 内核主要是指 P43 2 OS 内核的两大功能 P43 二 进程控制的有关概念二 进程控制的有关概念 1 处理机的执行状态 P43 2 原语 是由若干机器指令构成的 完成特定功能的程序段 原语 只能在系统状 核心态 下被执行 原语的执行是不能被打断的 P43 OS 内核中包括的原语主要有 进程控制原语 进程通信原语 资源管理原语和其他方面的原 语 其中 进程控制原语包括 创建原语 撤消原语 阻塞原语 唤醒原语等等 3 进程控制 就是操作系统用一些具有特定功能的程序段来创建 终止进程 完成进程在各状态间的转换 从而达到多进程高效率并 发执行和协调 实现资源共享的目的 操作系统的进程控制机构属于 OS 的内核 它是硬件的首次延 伸 它通过执行各种原语来实现其控制功能 学习关于进程控制的原语 我们应该关注 1 什么时候 由于什么事件导致原语的执行 2 由谁来启动原语 3 每个原语的内部处理流程是什么 三 进程的创建三 进程的创建 1 进程创建的两种方式 1 由系统创建 在 OS 生成时建立的一些系统进程 一个应用系统 被启动时最初的一些进程 2 由父进程创建 当一个进程执行 去完成所规定的功能时 它 能自己创建一些子进程 使其各自分担其中的部分功能 子进程也 可以创建自己的子进程 这样就形成了进程家族和进程树 2 进程树 描述进程家族关系的有向树 DEFG BC IJKM A L H 进程树示意图 UNIX 系统中 在树型进程关系中 子进程可以继承其父进程 所拥有的资源 在子进程撤消时 继承的资源归还给父进程 Windows 系统中 在树型进程关系中 子 父进程间没有资源继 承关系 3 引起创建进程的事件 P44 1 作业调度 2 用户登录 3 提供服务 4 启动应用程 序 5 应用请求 4 进程创建原语的流程 P45 1 申请空白 PCB 和进程 ID 2 为新进程分配运行所需资源 3 初始化进程的 PCB 4 将新进程 的 PCB 插入就绪队列 三 进程的终止三 进程的终止 1 引起进程终止 Termination of Process 的事件 1 正常结束 在任何计算机系统中 都应有一个用于表示进程已经运行完成 的指示 例如 在批处理系统中 通常在程序的最后安排一条 Holt 指令或终止的指令 当程序运行到 Holt 指令时 将产生一个中断 去通知 OS 本进程已经完成 在分时系统中 用户可利用 Logs off 去表示进程运行完毕 此时同样可产生一个中断 去通知 OS 进程 已运行完毕 2 异常结束 在进程运行期间 由于出现某些错误和故障而迫使进程终止 这类异常事件很多 常见的有 越界错误 这是指程序所访问的 存储区 已越出该进程的区域 保护错 进程试图去访问一个不 允许访问的资源或文件 或者以不适当的方式进行访问 例如 进 程试图去写一个只读文件 非法指令 程序试图去执行一条不 存在的指令 出现该错误的原因 可能是程序错误地转移到数据区 把数据当成了指令 特权指令错 用户进程试图去执行一条只允 许 OS 执行的指令 运行超时 进程的执行时间超过了指定的最 大值 等待超时 进程等待某事件的时间 超过了规定的最大 值 算术运算错 进程试图去执行一个被禁止的运算 例如 被 0 除 I O 故障 这是指在 I O 过程中发生了错误等 3 外界干预 外界干预并非指在本进程运行中出现了异常事件 而是指进程 应外界的请求而终止运行 这些干预有 操作员或操作系统干预 由于某种原因 例如 发生了死锁 由操作员或操作系统终止该 进程 父进程请求 由于父进程具有终止自己的任何子孙进程的 权利 因而当父进程提出请求时 系统将终止该进程 父进程终 止 当父进程被终止时 OS 也将它的所有子孙进程终止 2 进程终止原语的工作流程 1 根据被终止进程的标识符 从 PCB 集合中检索出该进程的 PCB 从中读出该进程的状态 2 若被终止进程正处于执行状态 应立即终止该进程的执行 并 置调度标志为真 用于指示该进程被终止后应重新进行调度 3 若该进程还有子孙进程 还应将其所有子孙进程予以终止 以 防他们成为不可控的进程 4 将被终止进程所拥有的全部资源 或者归还给其父进程 或者 归还给系统 5 将被终止进程 它的 PCB 从所在队列 或链表 中移出 等待其他 程序来搜集信息 归还给系统 四 进程的阻塞与唤醒四 进程的阻塞与唤醒 1 引起阻塞与唤醒的事件 1 向系统请求共享资源失败 2 启动了某种操作 等待它的完成 3 新数据尚未到达 4 等待新任务到达 引起阻塞的事件 当事件被处理完成 事件结束 后必然引起唤 醒 2 进程阻塞的过程 正在执行的进程 由于发生了上述某一事件而无法继续往下执 行 于是该进程便调用阻塞原语 block 把自己置于阻塞状态 可见 进程的阻塞是进程自身的一种主动行为 进程阻塞原语的流程 进入 block 过程后 由于此时该进程还处于执行状态 所以应 先立即停止执行 把进程控制块中的现行状态由 执行 改为 阻 塞 并将 PCB 插入阻塞队列 如果系统中设置了因不同事件而阻 塞的多个阻塞队列 则应将本进程插入到具有相同事件的阻塞 等待 队 列 最后 CPU 的使用权交给 OS 的调度程序 调度程序进行重新 调度 将处理机分配给另一就绪进程 并进行现场切换 亦即 保 留被阻塞进程的处理机状态 在阻塞进程的 PCB 中 再按新进程的 PCB 中的处理机状态设置 CPU 的环境 3 进程的唤醒 处于阻塞状态的某进程所等待的某一事件处理完成 事件发生了 由 发现者进程 比如 用完并释放了阻塞进程需要的 I O 设备的 进程 传送来了阻塞进程所需数据的进程 启动唤醒原语 将对应的 被阻塞进程送入就绪队列 进程唤醒原语的流程 首先把被阻塞的进程从等待该事件的阻塞队列中移出 将其 PCB 中的现行状态由阻塞改为就绪 然后再将该 PCB 插入到就绪队 列中 注意 阻塞与唤醒原语是一对作用刚好相反的原语 因此 如 果在某进程中调用了阻塞原语 则必须在与之合作的另一进程中或 其他相关进程中 安排唤醒原语 以唤醒被阻塞的进程 否则 被 阻塞的进程将会长期处于阻塞状态 从而无机会继续运行 五 进程的挂起与激活五 进程的挂起与激活 1 进程的挂起 当出现 挂起事件 时 系统启动挂起原语 将某个进程挂起 2 进程的激活 当发生 激活事件 时 系统启动激活原语 将指定的进程激 活 3 进程挂起原语的流程 首先检查将被挂起进程的状态 若处于活动就绪或执行状态 便将其改为静止就绪 对于活动阻塞状态的进程 则将之改为静止 阻塞 再将进程的 PCB 移入相应队列 为了方便用户或父进程考查 该进程的运行情况而把该进程的 PCB 复制到某指定的内存区域 最 后 若被挂起的进程刚才正在执行 则转向调度程序重新调度 4 进程激活原语的流程 激活原语先将进程从外存调入内存 检查该进程的现行状态 若是静止就绪 便将之改为活动就绪 若为静止阻塞便将之改为活 动阻塞 再将进程的 PCB 移入相应队列 假如采用的是抢占调度策 略 则每当有新进程进入活动就绪队列时 应检查是否要进行重新 调度 即由调度程序将被激活进程与当前进程进行优先级的比较 如果被激活进程的优先级更低 就不必重新调度 否则 立即剥夺 当前进程的运行 把处理机分配给刚被激活的进程 第第 3 节节 进程的相互制约进程的相互制约 相互协调相互协调 一 进程间的两种相互制约关系一 进程间的两种相互制约关系 进程间的相互制约关系是由于并发执行的进程间相互合作和 或 共享资源而引起的 OS 要协调实现这种相互制约关系 1 间接的相互制约关系 进程互斥 进程 a 资源 进程 b 共享资源 进程 A B 互斥示意图 2 直接的相互制约关系 进程同步 进程 a 进程 b 相互合作 读 写进程同步示意图 1 读 写进程同步示意图 2 二 进程的互斥二 进程的互斥 1 临界资源和临界区 在一段时间内只允许一个进程访问的资源称为临界资源 许多 物理设备 如输入机 打印机 磁带机等都具有这种性质 软件资 源 如公用变量 数据 表格 队列等也都具有这一特点 各进程中对临界资源进行操作的程序段称为临界区 并发进程 中访问同一临界资源的临界区应该互斥执行 例 公共变量 Count 是临界资源 P1 P2 Count R1 Count R2 Count Count 1 Count Count 1 R1 Count R2 Count 进程 P1 P2 并发执行 如果 P1 P2 的的临界区执行不互 斥 2 进程的互斥 临界区互斥执行示意图 进程互斥进程互斥 的概念描述 的概念描述 两个或以上的进程不能同时使用同 一个临界资源 只能一个进程用完了 资源完成了一个任务 另一个 再用 这种现象称为进程的互斥 也就是说 不允许两个或以上的 共享同一临界资源的并发进程同时进入临界区 造成进程的临界区 在时间上有重叠 互斥反映了并发进程间由于资源共享而形成的制 约关系 3 控制进程间实现互斥应遵循的原则 P51 1 空闲让进 2 忙则等待 3 有限等待 4 让权等待 4 进程互斥的实现方法 1 硬件同步机制 P51 52 2 整型信号量和对应的 P V 操作 整型信号量是一个与资源的物理实体个数有关的整型变量 除 初始化外 仅能通过两个标准的原子操作 Atomic Operation wait S 和 signal S 来访问 这两个操作一直被分别简称为 P V 操 作 wait 和 signal 操作可分别描述为 P53 用整型信号量和简单的 P V 操作实现进程互斥 Pa Pb wait s wait s signal s signal s 分别是进程 Pa Pb 中访问资源 S 的临界区 3 记录型信号量和对应的 P V 操作 在整型信号量机制中的 wait 操作 只要是信号量 S 0 就会不 断地测试 因此 该机制并未遵循 让权等待 的准则 而是使进 程处于 忙等 的状态 记录型信号量机制 则是一种不存在 忙 等 现象的进程同步机制 但在采取了 让权等待 的策略后 又 会出现多个进程等待访问同一临界资源的情况 需要组织等待队列 于是引进记录型信号量 描述为 struct semaphore int value list of process L 其中 整型分量 是一个与资源的物理实体个数有关的整型变量 当 其值 0 时 代表系统中供并发进程使用的同一类资源的数量 当 其值 0 时 其绝对值代表目前等待该类资源的等待队列的长度 指针型分量 指向该类资源等待队列的头结点 这时 wait 和 signal 操作可分别描述为 semaphore S P 操作 procedure wait S S value S value 1 申请消耗一个资源 if S value 0 then block S L 阻塞 V 操作 procedure signal S S value S value 1 归还 回收一个资源 if S value 0 then wakeup S L 唤醒 用记录型信号量和对应的 P V 操作 互斥的实现与使用整型 信号量时相同 4 AND 型信号量和对应的 P V 操作 多个进程共享多个资源时采用记录型信号量和 P V 操作实现 进程的互斥 可能会出现死锁问题 于是引进 AND 型信号量 和 与其对应的 P V 操作 AND 同步机制的基本思想是 将进程在整个运行过程中需要的 所有资源 一次性全部地分配给进程 待进程使用完后再一起释放 只要尚有一个资源未能分配给进程 其它所有可能为之分配的资源 也暂不分配给他 亦即 对若干个临界资源的分配 采取原子操作 方式 要么全部分配到进程 要么一个也不分配 由死锁理论可知 这样就可避免上述死锁情况的发生 AND 型信号量的定义与记录型信号量相同 对应的 P V 操作 定义如下 P55 5 信号量集和对应的 P V 操作 信号量集机制的基本思想是 一次分配若干类资源 每类资源 一次分配一批 而不是一个 当某类资源的空闲数量少于下限时 停止分配该类资源 P55 用不同类型的信号量和其对应的 P V 操作实现进程的互斥 原理是一致的 即用一对 P V 操作将临界区括起来 只是 P V 操 作的意义不同 Pa Pb wait s wait s signal s signal s 分别是进程 Pa Pb 中的访问资源 S 的临界区 三 进程的同步三 进程的同步 1 引例 两进程 A B A 进程向缓冲区 buf 中放数据 B 进程从 buf 中取数据打印 进程 A B 的工作要多次进行 进程 A 和进程 B 并发执行 相互合作 A 写进程 do while 1 while buf 空 计算 得到一个结果 结果放入 buf B 读进程 do while 1 while buf 空 取出 buf 中的数据 打印 清空 buf 2 进程同步 如果用引例中的方法由应用程序自己控制同步执行的步骤 则 不符合 让权等待 的原则 会造成 CPU 资源的极大浪费 进程同步进程同步 的概念描述 的概念描述 异步环境下的一组并发进程 由于 需要互发消息 数据 相互合作 在一些关键点上要相互等待 从而 相互制约彼此的执行速度 要步调一致地向前推进 同步反映了并 发进程间由于相互合作而形成的制约关系 3 用信号量和 P V 操作来实现进程同步控制 用前面介绍过的信号量和 P V 操作也可以实现进程的同步控 制 对于引例 我们引入两个信号量 s1 描述缓冲区资源 s1 1 表示缓冲区为空 可以放数据 s1 0 表示缓冲区里已放满 了数据 s2 描述数据资源 s2 1 表示缓冲区内有数据供打印 s2 0 表示缓冲区里没有数据供打印 系统初始化时 s1 赋初值 1 s2 赋初值 0 进程同步的实现 A 写进程 B 读进程 计算 wait s2 wait s1 从缓冲区取数据 向缓冲区中放数据 signal s1 signal s2 打印数据 在这里 进程 A B 通过信号量 s1 s2 交换控制信息 同一个信 号量的 P V 操作也成对出现 但分别出现在不同进程中 通过缓 冲区交互数据信息 合作完成任务 四 利用信号量实现前趋关系四 利用信号量实现前趋关系 执行顺序的控制执行顺序的控制 S4S5S3 S1 S6 S2 进程 S1 S6 执行的前后顺序关系如上图所示 用信号量和 P V 操作实现它们的并发同步执行 p1 S1 signal a signal b p2 wait a S2 signal c signal d p3 wait b S3 signal e p4 wait c S4 signal f p5 wait d S5 signal g p6 wait e wait f wait g S6 main semaphore a b c d e f g a value 0 b value 0 c value 0 d value 0 e 0 f value 0 g value 0 可以运行的信号 a L null b L null c L null d L null e L null f L null g L null 等待运行的队列 cobegin p1 p2 p3 p4 p5 p6 p7 coend 五 私有信号量和共有信号量五 私有信号量和共有信号量 对于一个信号量 我们可以将 P 操作看成消耗一个对应资源 减 1 将 V 操作看成生产一个对应资源 加 1 在实现进程互斥时使用的信号量 标志着对并发执行的一组进 程使用临界资源的制约 这样的信号量称为公有信号量 在实现进程同步时使用的信号量 使得生产进程和消耗进程之 间能交换控制信息 不影响并发执行的其他进程 这样的信号量称 为私有信号量 第第 4 节节 经典经典的进程的进程同步同步问题问题 一 生产者一 生产者 消费者问题消费者问题 1 问题的描述 在计算机系统中每个进程都在不断申请使用 释放 各种不同类型的资源 我们把申请使用某类资源的进程 称为这类 资源的消费者 把产生或释放某类资源的进程 称为这类资源的生 产者 对于硬件资源和数据资源 生产的意义略有不同 例如 在输入时 输入进程是数据的生产者 计算进程是数据的消费者 而在输出时 则计算进程是数据的生产者 而打印进程是数据的消 费者 生产者和消费者之间如何同步 该问题有很大的代表性及实 用价值 2 生产者 消费者问题的解决方法 例如 有一个容量为 n 的公共缓冲区 生产者进程向其中存入 数据 消费者进程从其中取数据去打印 这里 同步的问题描述为 1 生产者要存数据 缓冲区中至少要有一个空单元 否则生产者 应等待 生产者往缓冲区中存入一个数据后要发消息 通知消费者 多了一个数据 2 消费者要取数据 缓冲区中至少要有一个数据 否则消费者应 等待 消费者从缓冲区中取走一个数据后要发消息 通知生产者多 了一个空单元 3 对于公共缓冲区 可能同时存在多个生产者和多个消费者 公 共缓冲区是一个临界资源 所有生产者或消费者对它的访问都必须 是互斥进行的 生产者进程 消费者进程通过共享缓冲区传递数据示意图 生产者和消费者通过缓冲区传递数据 它们具有同步关系 生 产者和消费者都要访问临界资源 缓冲区 它们之间有互斥关系 这里设三个信号量 均为记录型 指针分量的说明略去 empty 表示缓冲区内目前的空单元数 初值为 n 缓冲区的大小 data 表示缓冲区内目前存放的未被打印数据的个数 初值为 0 mutex 控制对缓冲区互斥访问的信号量 初值为 1 并发执行的生产者 消费者进程描述为 生产者 消费者 Wait empty Wait data Wait mutex Wait mutex 向缓冲区存入 从缓冲区取出 一个数据 一个数据 Signal data Signal empty Signal mutex Signal mutex 3 注意 1 并发执行的生产者和消费者进程可以有多个 异步运行 2 在每个程序中用于实现互斥的 wait mutex 和 signal mutex 必须成 对地出现 3 实现同步时 对资源信号量 empty 和 data 的 wait 和 signal 操作 同样需要成对地出现 但它们分别处于不同的程序中 4 在每个程序中的多个 wait 操作顺序不能颠倒 应先执行对同步信 号量的 wait 操作 然后再执行对互斥信号量的 wait 操作 否则可能 引起进程死锁 5 如果生产 消费动作需多次重复的话 只需在上述程序段外套上 循环控制即可 4 用 AND 型信号量对生产者 消费者问题可描述为 P61 二 哲学家进餐问题二 哲学家进餐问题 1 问题的描述 有 5 个哲学家共用一张圆桌 分别坐在周围的 5 张 椅子上 在圆桌上有 5 个碗和 5 只筷子 他们的生活方式是交替的 进行思考和进餐 平时 一个哲学家进行思考 饥饿是便试图取用 其左右最靠近他的筷子 只有当他两只筷子都拿到时 才能进餐 进餐毕 放下筷子 继续思考 2 利用记录型信号量解决哲学家进餐问题 经分析可知 放在桌子上的每个筷子都是一个临界资源 在一 段时间内只允许一位哲学家使用 为了实现对筷子的互斥使用 可 以为每个筷子设一个互斥信号量 由这五个信号量构成信号量数组 每个信号量的数值型分量的初值为 1 其描述如下 semaphore chopstick 5 1 1 1 1 1 第 i 位哲学家的活动可描述为 do wait chopstick i 试图取用其左手的筷子 wait chopstick i 1 mod 5 试图取用其右手的筷子 Eat 使用资源 signal chopstick i signal chopstick i 1 mod 5 Think while TRUE i 可以是 1 2 3 4 5 由于这里是多个并发进程共享多个临 界资源 可能会出现死锁问题 解决的办法有 1 至多只允许有四位哲学家同时去拿左边的筷子 最终能保证至 少有一位哲学家能够进餐 并在用毕时能释放出他用过的两只筷子 从而使更多的哲学家能够进餐 2 仅当哲学家的左 右两只筷子均可用时 才允许他拿起筷子进 餐 3 规定奇数号哲学家先拿他左边的筷子 然后再去拿右边的筷子 而偶数号哲学家则相反 按此规定 将是 2 3 号哲学家竞争 3 号 筷子 4 5 号哲学家竞争 5 号筷子 即五位哲学家都先竞争奇数号 筷子 获得后 再去竞争偶数号筷子 最后总会有一位哲学家能获 得两只筷子而进餐 资源编号 进程编号 按序分配 3 利用 AND 型信号量机制来实现对五只筷子的互斥使用 P64 三 读者三 读者 写者问题写者问题 半临界资源半临界资源 1 问题描述 一个数据文件被多个进程共享 我们将这些进程中只 对文件进行读操作的称为 读者 将其他进程称为 写者 并发 执行的读者 写者可以有多个 允许多个读者同时对一个文件进行读操作 但不允许一个写者 和其他读者 写者同时对一个文件进行操作 解决问题涉及的信号量和公共变量 Wmutex 初值为 1 用于读写进程间 或写写进程间实现对文件 访问的互斥 公共变量 Readcount 读者计数器 它的值表示当前有多少个读 者在同时读共享的数据文件 初值为 0 每个读者 开始读之前都 要 Readcount 1 结束读之后都要做 Readcount 1 Rmutex 初值为 1 用于实现读者对公共变量 Readcount 访问的 互斥 读写进程间的制约关系 在读进程中 只有当 Readcount 0 时 目前没有读者在读 才需要执行 wait Wmutex 通知写者第一个 读者来了 在读进程中 只有当执行了 Readcount 1 后 Readcount 的 值为 0 才需要执行 signal Wmutex 通知写者最后一个读者走了 这样就实现了读与写进程间的互斥 2 用记录型信号量实现读者 写者问题 semaphore Rmutex 1 Wmutex 1 int Readcount 0 void Writer 写者 就是一个普通的临界资源互斥使用控制 do wait wmutex perform write operation 写文件操作程序段 signal wmutex while TRUE void Reader 读者 半临界资源互斥使用控制 do wait rmutex if Readcount 0 then wait wmutex 第一个读者想 进入临界区才需要 P 操作 Readcount signal rmutex perform read operation 读文件操作程序段 wait rmutex Readcount if Readcount 0 then signal wmutex 最后一个读 者离开临界区才需要 V 操作 signal rmutex while TRUE voil main cobegin reader writer coend 第第 6 节节 进程通信进程通信 进程通信的分类 进程通信的分类 1 低级通信 进程之间交换控制信息 一般只传送几个字节 达到控制进程 执行速度 协调进程执行的作用 可由 P V 原语来完成 进程的同步与互斥控制就属于低级通信 信号量机制和 P V 操作只能传递控制信号 控制信号本身不包含任何数据 2 高级通信 用信号量和 P V 操作难于实现进程间大批量的数据传送 原 因是 效率低 生产者每次只能向缓冲池投放一个产品 数据 消费者每次也只能从缓冲池取一个消息 数据 通信对用户不透 明 高级通信 用户在程序中利用操作系统提供的通信命令 系统调 用 高效 大批量地传送数据 高级通信的过程对用户是透明的 以下介绍的是进程间的高级通信 一 进程通信的类型一 进程通信的类型 1 共享存储器系统 Shared Memory System 相互通信的进程共享某些数据结构或共享存储区 进程之间能 够通过这些空间进行通信 据此 又可以把它们分为以下两种类型 1 基于共享数据结构的方式 P67 2 基于共享存储区的方式 P68 虽然可以大批量传递数据 但实现方式对程序员不透明 2 管道 Pipe 通信 所谓 管道 是指连接一个写进程和一个读进程的一个共享文 件 用于实现它们之间通信的 又名 pipe 文件 向管道 共享文件 提供输入的发送进程 即写进程 以字符流形式将大量的数据送入 管道 而接受管道输出的接收进程 即读进程 则从管道中接收 读 数据 由于发送进程和接收进程是利用管道进行通信的 故又称为 管道通信 这种方式首创于 UNIX 系统 由于它能有效地传送大量 数据 因而又被引入到许多其它操作系统中 3 消息传递系统 Message passing system 不论是单机系统 多机系统 还是计算机网络 消息传递机制 都是用得广泛的一种进程间通信的机制 在消息传递系统中 进程 间的数据交换 是以格式化的消息 message 为单位的 其中含发送者 信息 在计算机网络中 又把 message 称为报文 程序员直接利用 系统提供的一组通信命令 原语 进行通信 操作系统隐藏了通信的 实现细节 大大减化了通信程序编制的复杂性 而获得广泛的应用 消息传递系统的通信方式属于高级通信方式 又因其实现方式的不 同而进一步分成直接通信方式和间接通信方式两类 P68 4 客户机 服务器系统 关注计算机网络中的相关内容 P68 二 实现消息传递通信的两种方式二 实现消息传递通信的两种方式 1 直接通信方式 实时通信 发送 接收信息的双方进程 使用一对发送 接收原语来完成数 据的交换 在发送原语中指明接收进程 发送数据存放地址 在接 收原语中指明发送进程 接收数据的存放地址 通信命令 原语 的格式 Send Receiver message 发送一个消息给接收进程 Receive Sender message 接收一个发送进程发来的消息 例如 原语 Send P2 m1 表示将消息 m1 发送给接收进程 P2 而原语 Receive P1 m1 则表示接收由 P1 发来的消息 m1 在某些情况下 接收进程可与多个发送进程通信 因此 它不 可能事先指定发送进程 例如 用于提供打印服务的进程 它可以 接收来自任何一个进程的 打印请求 消息 对于这样的应用 在 接收进程接收消息的原语中的源进程参数 是完成通信后的返回值 接收原语可表示为 Receive id message 利用直接通信原语 来解决生产者 消费者问题 当生产者生产 出一个产品 消息 后 便用 Send 原语将消息发送给消费者进程 而 消费者进程则利用 Receive 原语来得到一个消息 如果消息尚未生 产出来 消费者必须等待 直至生产者进程将消息发送过来 生产者 消费者的直接通信过程可分别描述如下 do produce an item in nextp send consumer nextp while TRUE do 注意 在这里 应用程序 的任务是使用通信原语完 成通信 而OS的任务是提 供通信原语 通信中的同 步 互斥 在原语中实现 控制 与应用程序员无关 receive producer nextc consume the item in nextc while TRUE 在单机和计算机网络中 高级通信普遍采用直接消息传递通信 实现这种通信涉及到下列问题 P70 71 1 通信原语 2 通信链路 3 消息的格式 4 进程同步方式 2 间接通信方式 信箱通信 非实时通信 信箱是由发送进程和接收进程共享的一种数据结构实体 用来 暂时存放发送进程发给接收进程的消息 逻辑上它分成两部分 信箱头 由若干格子组成的信箱体 信 箱头描述它的名称 大小 方向 拥有者等控制信息 OS 为邮箱通信提供了一组原语 1 信箱的创建和撤消 进程可利用信箱创建原语来建立一个新信 箱 创建者进程应给出信箱名字 信箱属性 公用 私用或共享 对于共享信箱 还应给出共享者的名字 当进程不再需要读信箱时 可用信箱撤消原语将之撤消 2 消息的发送和接收 当进程之间要利用信箱进行通信时 必须 使用共享信箱 并利用系统提供的下述通信原语进行通信 Send mailbox message 将一个消息发送到指定信箱 Receive mailbox message 从指定信箱中接收一个消息 信箱可由操作系统创建 也可由用户进程创建 创建者是信箱 的拥有者 据此 可把信箱分为以下三类 1 私用信箱 用户进程可为自己建立一个新信箱 并作为该进程的一部分 信箱的拥有者有权从信箱中读取消息 其他用户则只能将自己构成 的消息发送到该信箱中 这种私用信箱可采用单向通信链路的信箱 来实现 当拥有该信箱的进程结束时 信箱也随之消失 2 公用信箱 它由操作系统创建 并提供给系统中的所有核准进程使用 核 准进程既可把消息发送到该信箱中 也可从信箱中读取发送给自己 的消息 显然 公用信箱应采用双向通信链路的信箱来实现 通常 公用信箱在系统运行期间始终存在 3 共享信箱 它由某进程创建 在创建时或创建后 指明它是可共享的 同 时须指出共享进程 用户 的名字 信箱的拥有者和共享者 都有权 从信箱中取走发送给自己的消息 在利用信箱通信时 在发送进程和接收进程之间 存在以下四 种关系 1 一对一关系 这时可为发送进程和接收进程建立一条两者专 用的通信链路 使两者之间的交互不受其他进程的干扰 2 多对一关系 允许提供服务的进程与多个用户进程之间进行 交互 也称为客户 服务器交互 client server interaction 3 一对多关系 允许一个发送进程与多个接收进程进行交互 使发送进程可用广播方式 向接收者 多个 发送消息 4 多对多关系 允许建立一个公用信箱 让多个进程都能向信 箱中投递消息 也可从信箱中取走属于自己的消息 发送和接收进程对信箱的互斥访问由 OS 控制 包含在通信原语 中 对用户透明 三 消息缓冲队列通信三 消息缓冲队列通信 直接消息传递通信实例直接消息传递通信实例 1 消息缓冲队列通信是一种本地并发进程高级通信方式 它的基本 思想 发送进程 在利用发送原语发送消息之前 先在自己的内存空 间 设置一发送区 a 把待发送的消息正文 发送进程标识符 消 息长度等信息填入其中 然后调用发送原语 把消息发送给目标 接 收 进程 发送原语 Send x a 首先根据发送区 a 中所设置的消息长度 a size 来申请一缓冲区 i 接着 把发送区 a 中的信息复制到缓冲区 i 中 然后将 i 挂到接收进程 x 的消息缓冲队列 mq 上 为了能将 i 挂到 mq 上 还应先获得接收进程 x 的内部标识符 找到它的 PCB 接收进程 则在自己的内存空间设置一个接收区 b 接收消息 时 调用接收原语 Receive y b 将自己的消息缓冲队列中的第一 个缓冲区 j 摘取下来 将其中的数据复制到接收区 b 中 然后释放 缓冲区 j 进程的消息缓冲队列是一个临界资源 对一个消息缓冲队列的 访问操作前后 都要执行 wait 和 signal 操作 另外 当消息缓冲队列为空时 接收进程不能对它进行操作 OS 要在进程的 PCB 中设置有关的数据项 进行同步 互斥控制 2 消息缓冲队列通信机制中的数据结构 1 消息缓冲区 是消息缓冲队列的结点 是这种通信方式使用的 主要数据结构 它可描述如下 typedef struct message buffer int sender 发送者进程标识符 int size 消息长度 int text 消息正文 int next 指向下一个消息缓冲区的指针 2 PCB 中有关通信的数据项 在利用消息缓冲队列通信机制时 在 设置消息缓冲队列的同时 还应增加用于对消息队列进行操作和实 现同步的信号量 并将它们置入进程的 PCB 中 在 PCB 中应增加 的数据项可描述如下 typedef struct processcontrol block struct message buffer mq 消息队列队首指针 semaphore mutex 消息队列互斥信号量 semaphore sm 消息缓冲队列的长度 PCB 3 OS 提供数据发送 接收原语 P74 75 在采用消息缓冲队列机制进行进程通信时 OS 在进程的 PCB 中设置专门的数据结构 并提供通信原语 用户程序则使用通信原 语直接进行进程通行 消息缓冲通信示意图 第第 7 节节 线程的基本概念线程的基本概念 一 线程的概念一 线程的概念 1 引入