第2章 进程的描述与控制

2020年4月15日 操作系统 1 第2章进程的描述与控制 2020年4月15日 第二章进程管理 2 主要内容 2 1进程的基本概念2 2进程控制2 3进程同步2 4经典的同步问题2 5管程机制2 6进程通信2 7线程2 8例题选讲 2020年4月15日 第二章进程管理 3 2 1进程的基本概念 例如下面3个语句 1 程序的顺序执行 S1 a x yS2 b a 5S3 c b 1 前趋图 是一个有向无循环图DAG DirectedAcyclicGraph S1 S2 S3 上面语句的前趋图可以表示为 S S1 S2 S3 S1 S2 S2 S3 1 程序的顺序执行与特征 eg2 S1 a x yS2 b a 5S3 c b 1 在早期的单道程序工作环境下 内存中只有一个作业的程序 一个作业完成了 后一个作业才进入内存 并得以执行 这样一来 机器执行程序的过程就严格按顺序方式执行 特征 1 顺序性程序的执行是按照程序机构所指定的顺序执行 即每一操作必须在前一操作完成以后才能开始 2 封闭性程序是在封闭的环境下运行的 即程序运行时独占全机资源 资源的状态完全由该程序的控制逻辑所决定 不受外界因素的影响 3 可再现性只要程序执行的初始条件相同 执行结果就完全相同 即程序执行结果与它的运行速度无关 2 程序的并发执行和特征程序的并发执行和资源共享使系统的工作情况变得复杂 产生了新的特征 1 不可再现性并发程序的执行结果与它们的相对速度有关 如图 两并发程序A和B互相独立运行 A中对变量n实现累加操作 B中打印n值 它们的相对执行速度是不确定的 若A执行到k1时 控制转到B B执行过程中打印n的值为0 当B运行到s时 控制又转到A 则A在k1点后继续执行 若A运行得快一些 当它执行到k2时 控制才转到B 则B执行时打印机出n得值为1 2 制约性并发程序之间相互依赖和制约 如图I C O是三个相互合作的程序 当计算程序Ci 1处理后 若输入程序未完成对Ii的处理 计算程序便无法进行Ci的处理 致使它暂停运行 另外几个并发程序还可能因竞争同一资源而相互制约 3 程序与计算不再一一对应 程序 是指令的有序集合 是静态的概念 而 计算 是指令系列在处理机上的执行过程 是动态的概念 在并发执行时 一个共享程序可被多个用户作业调用 从而形成了多个计算 如图 A和B执行中都调用C 在A调用时C时 C是属于A的执行过程的一部分 在B调用C时 C是属于B的执行过程的一部分 C属于A B的不同执行过程 4 失去封闭性 共69页 第9页 进程的概念 操作系统用 进程 来描述系统中各并发活动进程 process 又叫做任务 task 进程是程序的一次执行过程定义 进程是具有独立功能的程序在一个数据集合上的一次动态执行过程 是系统进行资源分配和调度的一个独立单位 共69页 第10页 进程具有的特性 动态性 进程是程序的一次执行过程 是临时的 有生命期的 独立性 进程是系统进行资源分配和调度的一个独立单位 并发性 多个进程可在处理机上交替执行 结构性 系统为每个进程建立一个进程控制块 共69页 第11页 进程和程序 进程是动态的 程序是静态的 程序是有序代码的集合 进程是程序的执行 没有程序就没有进程 通常 进程不可以在计算机之间迁移 而程序可以复制 进程是暂时的 程序是永久的 进程包括程序 数据和进程控制块 通过多次执行 一个程序可对应多个进程 通过调用关系 一个进程可包括多个程序 进程可创建其他进程 而程序不能形成新的程序 2 进程的特征动态性进程是程序在并发系统内的一次执行 一个进程有一个从产生到消失的生命期 并发性正是为了描述程序在并发系统内执行的动态特性才引入了进程 没有并发就没有进程 独立性每个进程的程序都是相对独立的顺序程序 可以按照自己的方向和速度独立地向前推进 制约性进程之间的相互制约 主要表现在互斥地使用资源和相关进程之间必要的同步和通讯 结构性进程 PCB 程序 数据集合 2 1 2进程的状态和组成1 进程的状态及其转换 1 进程的基本状态 运行状态 Running 就绪状态 Ready 阻塞状态 Blocked 创建状态 New 退出状态 Exit 运行状态指当前进程已占有CPU 它的程序段正在执行 处于这种状态的进程的个数不能大于CPU的数目 就绪状态进程获得了除处理机外的一切资源 等待分配CPU资源 一旦得到CPU就可以运行 阻塞状态进程因等待某种事件发生而暂不能运行的状态 创建状态进程处于创建过程中 还不能运行 退出状态进程已结束运行 回收除PCB之外的其它资源 在一个具体的系统中 为了调度的方便 合理 往往设立了更多个进程状态 如在UNIX操作系统中 进程状态可分为10种 但上述这几种状态是最基本的 因为如果不设立运行状态就不知道哪一个进程正在占有CPU 如果不设立就绪状态 就无法有效地挑选出适合运行的进程 如果不设立阻塞状态 就无法区分各进程除CPU之外是否还缺其它资源 2 进程状态的转换 就绪 运行处于就绪状态的进程被调度程序选中 分到CPU后 该进程状态就由就绪态变为运行态 运行 阻塞正在运行的进程因某种条件未满足而放弃对CPU的占用 阻塞 就绪处于阻塞状态的进程所等待的事件发生了 运行 就绪正在运行的进程如用完了本次分配给它的CPU时间片 它就得从CPU时间片上退下来 暂停运行 挂起进程模型 就绪状态进程在内存且可立即进入运行状态 阻塞状态进程在内存并等待某事件的出现 就绪挂起状态进程在外存 但只要进入内存 即可运行 阻塞挂起状态进程在外存并等待某事件的出现 2 进程的组成进程的组成程序 数据和进程控制块 PCB 2 进程控制块的组成PCB中含有进程描述信息 进程控制信息 资源占用信息和处理器现场保护结构这四个部分 是进程动态特性的集中反映 它是系统对进程进行识别和控制的依据 在不同的系统中 PCB的具体成分是不同的 总的来说 PCB一般包括如下内容 进程名 现行状态 优先级 现场保护区 资源清单 族系关系 进程实体信息 进程通信机制与其它信息等 共69页 第19页 进程的描述 PCB是进程存在的唯一标识通常 一个进程的信息包括 至少一个可执行程序一个独立的地址空间一个执行栈区 子程序调用 系统调用 进程切换 打开的文件 申请使用的I O设备等 进程控制块 PCB processcontrolblock 进程描述符 processdescriptor 共69页 第20页 PCB中的基本信息 进程标识数 用于唯一地标识一个进程 通常是一个整数 外部标识符 由用户使用 如 send进程 print进程等 进程的状态 调度 存储器管理信息 是调度进程所必需的信息 包括进程状态 优先级 程序在主存地址 在外存的地址等 进程使用的资源信息 分配给进程的I O设备 正在打开的文件等 共69页 第21页 CPU现场保护区 保存进程运行的现场信息 包括 程序计数器 PC 程序状态字 通用寄存器 堆栈指针等 记帐信息 包括使用CPU时间量 帐号等 进程之间的家族关系 类UNIX系统 进程之间存在着家族关系 父 子进程 Windows进程之间不具有父子关系 进程的链接指针 链接相同状态的进程 共69页 第22页 Unix structproc Linux structtask struct Windows执行体进程块 EPROCESS 内核实现线程调度 调度信息在KTHREAD结构中 实例 3 进程队列系统中有许多进程 处于就绪状态和处于阻塞状态的进程可分别有多个 而阻塞的原因又可以各不相同 因此为了调度和管理的方便起见 常将各进程的PCB用适当的方式组织起来 一般说来 有以下几种PCB组织方式 线性方式 链接方式 索引方式 1 线性方式把所有不同状态的进程的PCB组织在一个表格中 2 链接方式将处于不同状态的PCB放在不同的队列中 处于相同状态的PCB组成队列 如此便形成执行队列 就绪队列 等待队列 共69页 3 索引方式利用索引表记载相应状态进程的PCB地址 2 3进程控制 进程是有 生命期 的动态过程 核心对它们实施管理 进程控制的功能是完成进程状态的转换 主要包括 创建进程 撤销进程 挂起进程 解除挂起 阻塞进程 唤醒进程 调度进程等 这些操作是由若干条机器指令构成用以完成特定功能的一段程序 被称做原子操作 原语 原语 是机器指令的延伸 往往是为完成某些特定的功能而编制的一段系统程序 为保证操作的正确性 在许多机器中规定 执行原语操作时 要屏蔽中断 以保证其操作的不可分割性 原语操作也称做 原子操作 即一个操作中的所有动作要么全做 要么全不做 2 3 1进程的创建 1 进程图 ProcessGraph 2 引起创建进程的事件用户登录 作业调度 提供服务 应用请求 3 进程的创建 CreationofProgress 进程可借助创建原语建立一个子进程 创建进程的主要操作过程是 1 申请一个空闲的PCB 2 为新进程分配资源 3 将新进程的PCB初始化 4 将新进程加到就绪队列中 创建进程流程图 2 3 2进程的终止 一个进程在完成其任务后 应将该进程撤销 以便释放出它所占用的资源 撤销原语一般由其父进程或祖先发出 不会自己撤销自己 一旦系统中出现要求终止进程的事件后 便调用进程终止原语 1 引起进程终止 TerminationofProcess 的事件 正常结束 异常结束 外界干预 2 进程的终止过程 1 根据被终止进程的标识符 从PCB集合中检索出该进程的PCB 从中读出该进程的状态 2 若被终止进程正处于执行状态 应立即终止该进程的执行 并置调度标志为真 用于指示该进程被终止后应重新进行调度 3 若该进程还有子孙进程 还应将其所有子孙进程予以终止 以防他们成为不可控的进程 4 将被终止进程所拥有的全部资源 或者归还给其父进程 或者归还给系统 5 将被终止进程 它的PCB 从所在队列 或链表 中移出 等待其他程序来搜集信息 撤消进程流程图 2 3 3进程的阻塞与唤醒 进程的阻塞正在运行的进程因等待某事件发生 只能转变为阻塞态 等待相应事件出现后再把它唤醒 正在运行的进程通过调用阻塞原语主动地把自己阻塞 进程阻塞的过程如下 1 立即停止当前进程的执行 2 将现行进程的CPU现场送到该进程的PCB现场保护区中保存起来 以便将来重新运行时恢复此时的现场 3 把该进程PCB中的现行状态由 运行 改为阻塞 把它插入到具有相同事件的阻塞队列中 4 然后转到进程调度程序 重新从就绪队列中挑选一个合适进程投入运行 阻塞进程流程图 2 进程的唤醒 当被阻塞进程所等待的事件出现时 则由另外的与被阻塞进程相关的进程调用唤醒原语 将等待该事件的进程唤醒 可见 被阻塞进程不能唤醒自己 唤醒原语的主要操作过程是 1 首先把被阻塞进程从相应的阻塞队列中摘下 2 将现行状态改为就绪态 然后把该进程插入到就绪队列中 3 如果被唤醒进程比运行进程有更高的优先级 则设置重新调度标志 阻塞原语与唤醒原语恰好是一对相反的原语 调用前者是自己去睡眠 调用后者是把 别人 唤醒 使用时也要成对 前边有睡的 后边要有叫醒的 否则 前者就要 长眠 了 唤醒进程流程图 2 3 4进程的挂起与激活 1 进程的挂起 当需要把某进程置于挂起就绪状态或挂起阻塞状态时 可调用挂起原语 调用挂起原语的进程只能挂起它自己或它的子孙 挂起原语的执行过程是 首先检查被挂起进程的状态 若处于活动就绪状态 便将其改为静止就绪 对于活动阻塞状态的进程 则将之改为静止阻塞 为了方便用户或父进程考查该进程的运行情况而把该进程的PCB复制到某指定的内存区域 最后 若被挂起的进程正在执行 则转向调度程序重新调度 2 进程的激活过程 激活原语将处于静止状态的进程变为活动状态 一个进程只能将自己的子孙进程解挂 一个进程可以将自己挂起 却不能将自己解挂 激活原语的执行过程是 激活原语先将进程从外存调入内存 检查该进程的现行状态 若是静止就绪 便将之改为活动就绪 若为静止阻塞便将之改为活动阻塞 假如采用的是抢占调度策略 则每当有新进程进入就绪队列时 应检查是否要进行重新调度 即由调度程序将被激活进程与当前进程进行优先级的比较 如果被激活进程的优先级更低 就不必重新调度 否则 立即剥夺当前进程的运行 把处理机分配给刚被激活的进程 2 4进程同步 在同一系统内并发执行的诸程序之间 即有独立性又有相互制约性 独立性是指各进程都可独立的向前推进 制约性是指各个进程对资源的共享以及为完成一项共同任务需要彼此合作等产生的相互制约关系 进程间的相互关系分为同步关系和互斥关系 如果对进程的活动不加以约束 就会使系统出现混乱 如多个进程的输出结果混在一起 数据处理的结果不唯一 系统内某些空闲的资源无法得到利用等问题 为了保证系统中所有进程都能正常活动 使程序的执行具有可再现性 就必须提供进程同步机制 即实现进程同步和互斥 2 4 1进程同步的基本概念 两种形式的制约关系 1 同步 直接相互制约关系 进程间共同完成一项任务时直接发生相互作用的关系 相互合作的关系 eg 有一输入进程A通过单缓冲区向计算进程B提供数据 当该缓冲区空时 计算进程B将因不能获得所需数据而阻塞 一旦进程A将数据送入该缓冲时 便将进程B唤醒 反之 当缓冲已满 进程A不能再向缓冲区投放数据时 进程A必须阻塞 仅当进程B将缓冲区内数据取走时 才能唤醒进程A 司机和售票员的同步 eg eg 有用户作业程序 其形式是Z func1 x func2 y 其中func1 x func2 y 均是复杂函数 为加快速度 可用两进程P1 P2各计算一个函数 进程P2计算func2 y 进程P1计算完func1 x 之后 与进程P2的计算结果相乘 获得最终结果Z 2 互斥 间接相互制约关系 两个进程在逻辑上本来完全独立 由于竞争同一物理资源而相互制约的关系 对资源争用的关系 eg 在仅有一台打印机的系统中 有两个进程A和B 如果当A需要打印时 系统已将打印机分配给B 则进程A必须阻塞 一旦进程B将打印机释放 系统便将A唤醒 使之由阻塞状态变为就绪状态 2 临界资源和临界区 1 临界资源 CriticalResouce 一次只允许一个进程使用的资源 例如打印机 输入机和共享变量均为临界资源 eg 两进程P1 P2共享一变量x 当两进程按下列顺序执行时 R1 R2是处理器中的寄存器 P1 R1 x R1 R1 1 x R1 P2 R2 x R2 R2 1 x R2 其结果使x增加了2 P1 R1 x P2 R2 x P1 R1 R1 1 x R1 P2 R2 R2 1 x R2 其结果使x增加了1 为预防这种错误 对变量x应按临界资源处理 即令P1和P2顺序使用x 2 临界区 criticalsection 在每个进程中访问临界资源的那段程序 简称CS区 为了实现对临界资源的互斥访问 就应该保证各进程互斥地进入自己的临界区 为此 每个进程在进入临界区之前 必须先提出申请 经允许后方可进入 例如 计算机中的打印机是互斥资源 它只能 停停打打 而不能中途去打印另一任务 3 临界区的调用原则空闲让进当无进程处于临界区时 必须让一个要求进入临界区的进程立即进入 以有效地利用临界资源 忙则等待当已有进程进入临界区时 其它试图进入自己临界区的程序必须等待 以保证它们互斥地进入临界区 有限停留进入临界区地进程要在有限时间内退出 以便其它进程能及时进入自己的临界区 让权等待对于等待进入临界区的进程而言 它必须立即释放处理机 避免进程 忙等 3 临界区互斥执行的解决方法 1 软件方法单标志算法假设有两个进程Pi和Pj 设立一个共用整型变量turn 描述允许进入临界区的进程标识 while turn i Criticalsectionturn j Remaindersection 该算法可以保证任何时刻最多只有一个进程在临界区 但它的缺点是强制轮流进入临界区 没有考虑进程的实际需要 while turn j Criticalsectionturn i Remaindersection 双标志 先检查算法设立一个标志数组flag 描述各进程是否在临界区 初值均为FALSE while flag j flag i TRUE Criticalsectionflag i FALSE Remaindersection 该算法克服了算法1的缺点 两个进程不用交替进入 可连续使用 但由于使用多个标志 算法又产生一个新问题 即进程Pi和Pj可能同时进入临界区 从而违反了最多只有一个进程在临界区的要求 while flag i flag j TRUE Criticalsectionflag j FALSE Remaindersection 双标志 先修改后检查算法设立一个标志数组flag 描述各进程是否想进入临界区 flag i TRUE while flag j Criticalsectionflag i FALSE Remaindersection 该算法可防止两个进程同时进入临界区 但它的缺点是Pi和Pj可能都进入不了临界区 即在修改本进程标志flag之后和检查对方flag之前有一段时间间隔 这个间隔导致两个进程都想进入临界区 从而在检查对方标志时不通过 flag j TRUE while flag i Criticalsectionflag j FALSE Remaindersection 先修改 后检查 后修改者等待算法假设有两个进程Pi和Pj 设立一个标志数组flag 描述各进程是否想进入临界区 标志turn表示修改的先后 由于turn中保存的是较晚的一次赋值 因此较晚修改标志的进程等待 flag i TRUE turn j while flag j Remaindersection 本算法可完全正常工作 即实现了同步机制要求的空闲则入和忙则等待准则 flag j TRUE turn i while flag i Remaindersection 2 硬件方法利用软件方法实现进程互斥有很大局限性 如不适用数目很多的进程间的互斥 最主要的问题是修改标志和检查标志不能作为一个整体被执行 硬件方法的主要思路是用一条指令完成读和写两个操作 因而保证读操作与写操作不被打断 依据所采用的指令的不同硬件方法分成TS指令和Swap指令两种 TS Test And Set 指令TS指令的功能是读出指定标志后把该标志设置为TRUE TS指令 booleanTS boolean lock booleanold old lock lock TRUE returnold 利用TS实现进程互斥 whileTS Remaindersection SWAP 或Exchange 指令SWAP指令的功能是交换两个字的内容 Swap指令 voidSWAP int a int b inttemp temp a a b b temp 利用Swap实现进程互斥 key TRUE Do SWAP Remaindersection 2 4 2信号量机制 1 整型信号量 信号量 semaphore 也叫信号灯 它代表可用资源实体的数量 整型信号量被定义为一个整型量 除初始化外 仅能通过两个标准的原子操作wait S 和signal S 来访问 这两个操作一直被分别称为P V操作 wait和signal操作可描述为 wait S while S 0 S S 1 signal S S S 1 应该注意 wait signal操作都应作为一个整体实施 是两个原子操作 不允许分割或相互穿插执行 为保证这一点 在单CPU系统中通常是在屏蔽中断的条件下执行P V操作 wait S wait操作一次 S S 1 若S 0 表示有资源 当前进程可继续执行 若S0时 S表示可用资源的数量 当S 0时 表示已无可用资源 请求者必须等待别的进程释放了该类资源 它才能运行下去 所以它要排队 signal S V操作一次 S值加1 即S S 1 如果S 0 则该进程继续运行 如果S 0 则释放信号量队列上的第一个PCB 即信号量指针所指向的PCB 和对应的进程 把阻塞态改为就绪态 执行V操作的进程继续运行 执行一次signal操作意味着释放一个单位资源 因此S值加1 若S 0 表示有某些进程正在等待该资源 因而要把队列头上的进程唤醒 释放资源的进程总是可以运行下去的 2 记录型信号量 一般是由两个成员组成的数据结构 当多个进程都等待同一信号量时 它们就排成一个队列 由信号量的指针指出该队列的头 而PCB队列是通过PCB本身所包含的指针项进行链接的 最后一个PCB的链接指针为0 信号量的值是与相应资源的使用情况有关的 当它的值大于0时 表示当前可用资源的数量 当它的值小于0时 其绝对值表示等待使用该资源的进程个数 即在该信号量队列上排队的PCB的个数 如图 structsemaphore value int L pointertoPCB 相应地 wait S 和signal S 操作可描述为 voidwait S semaphore S value S value 1 if S value 0 block S L voidsignal S semaphore S value S value 1 if S value 0 wakeup S L 3 AND型信号量 上述的进程互斥问题 是针对各进程之间要共享一个临界资源而言的 在有些应用场合 是一个进程需要先获得两个或更多的共享资源后 方能执行其任务 eg 现有两个进程A和B 它们都要求访问共享数据D和E 当然 共享数据都应该作为临界资源 为此 可为这两个数据分别设置用于互斥的信号量Dmutex和Emutex 并令它们的初值都是1 相应的 在两个进程中都要包含两个对Dmutex和Emutex的操作 即 ProcessA wait Dmutex wait Emutex ProcessB wait Emutex wait Dmutex 但当进程A和B交替执行时 会出现死锁 AND同步机制的基本思想是 将进程在整个运行过程中需要的所有资源 一次性全部地分配给进程 待进程使用完后再一起释放 只要尚有一个资源未能分配给进程 其它所有可能为之分配的资源 也不分配给他 Swait Simultaneouswait 定义如下 voidSwait S1 S2 Sn if S1 1 else placetheprocessinthewaitingqueueassociatedwiththefirstSifoundwithSi 1 andsettheprogramcounterofthisprocesstothebeginningofSwaitoperation Ssignal Simultaneoussignal 定义如下 voidSsignal S1 S2 Sn for i 1 i n i Si Si 1 removealltheprocesswaitinginthequeueassociatedwithSiintothereadyqueue 4 信号量集在记录型信号量机制中 wait S 和signal S 操作仅能对信号量施以加1或减1操作 当一次需要N个某类临界资源时 便要进行N次wait S 操作 很低效 另外 在有些情况下 当资源数量低于某一下限值时 便不予以分配 故在上述的基础上加以扩充 形成一般化的 信号量集 机制 其中 S为信号量 d为需求值 t为下限值 Swait S1 t1 d1 Sn tn dn 定义如下 voidSwait S1 t1 d1 Sn tn dn if S1 t1 else placetheexecutingprocessinthewaitingqueueofthefirstSifoundwithSi ti andsetitsprogramcountertothebeginningofSPoperation Swait S1 d1 Sn dn 定义如下 voidSwait S1 d1 S2 d2 Sn dn for i 1 i n i Si Si di removealltheprocesswaitinginthequeueassociatedwithSiintothereadyqueue 2 4 3信号量的应用 利用信号量实现进程互斥设mutex是一个互斥信号量 初始值为1 A进程 B进程 wait mutex wait mutex 互斥工作段互斥工作段signal mutex signal mutex 一般 信号量集 的几种特殊情况 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后 将阻止任何进程进入特定区 换言之 它相当于一个可控开关 模拟执行 注意 1 信号量mutex用于互斥 初值为1 2 每个程序中用于实现互斥的P mutex 和V mutex 必须成对出现 即先做P进临界区 后做V 出临界区 2 用信号量实现进程同步 供者和用者要交换两信息 缓冲区空和缓冲区满的状态 当缓冲区空时 供者进程才能把信息存入缓冲区中 当缓冲区满时 表示其中有可供加工的信息 用者进程才能从中取出信息 用者不能超前供者 即缓冲区中未存入信息时不能从中取出信息 如供者已把缓冲区写满 但用者尚未取走信息时 供者不能又往其中写信息 避免冲掉前面写入的信息 为此 设置两个信号量 S1 表示缓冲区是否空 0表示不空 1表示空 S2 表示缓冲区是否满 0表示不满 1表示满 设S1初值为1 S2初值为0 则缓冲区的供者进程和用者进程的同步关系用下述方式实现 供者进程 用者进程 do do wait S1 wait S2 启动输入机从缓冲区取出信息 signal S1 收到输入结束中断加工并存盘 signal S2 while TRUE while TRUE 用wait signal操作实现同步时应注意 1 分析进程间的制约关系 确定信号量种类 2 信号量的初值与相应资源的数量有关 也与wait signal操作在程序代码中出现的位置有关 3 同一信号量的wait signal操作要 成对 出现 但它们分别在不同的进程代码中 模拟执行 3 利用信号量实现前趋关系 设有两并发执行的进程P1和P2 P1中有语句V1 P2中有语句V2 我们希望在执行V1后再执行V2 为实现这种前驱关系 可以使进程P1和P2共享一个公用信号量S 并赋予其初值为0 在进程P1中 V1 V S 在进程P2中 P S V2 eg 如右图 可利用信号量实现前驱关系 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 semaphorea b c d e f g a value b value c value d value 0 e value f value g value 0 cobeginp1 p2 p3 p4 p5 p6 coend 2 4 4经典进程的同步问题 生产者 消费者问题 生产者 消费者 Producer Consumer 问题是最著名的进程同步问题 在计算机系统中的许多问题都可以将它归结为生产者 消费者问题 例如 在输入时 输入进程是生产者 计算进程是消费者 而在输出时 则计算进程是生产者 而打印进程是消费者 因此 该问题有很大的代表性及实用价值 这个问题可描述如下 一组生产者进程和一组消费者进程通过缓冲区发生联系 生产者进程将生产的产品 数据 消息等 送入缓冲区 消费者进程则从中取出产品 假定缓冲区共有N个 可把它们设想成一个环形缓冲池 如图所示 有斜线的部分表示该缓冲区放有产品 否则为空 in表示生产者下次存入产品的单元 out表示消费者下次取出产品的单元 为使两类进程协调工作 防止盲目生产和消费 它们应该满足如下同步条件 生产者存放产品的单元数不能超过缓冲区的总容量 N 消费者取出产品的总量不能超过生产者生产产品的总量 in out 生产者进程和消费者进程使用的指针 指向下面可用的缓冲区 初值为0 full 表示放有产品的缓冲区数 初值为0 empty 表示可供使用的缓冲区数 其初值为N mutex 互斥信号量 初值为1 表示互斥进入临界区 即 保证任何时候只有一个进程使用缓冲区 1 利用记录型信号量解决生产者 消费者问题算法描述 生产者进程 消费者进程 do do wait empty wait full wait mutex wait mutex 产品送往buffer in 从buffer out 中取出产品 in in 1 modN out out 1 modN signal mutex signal mutex signal full signal empty while TRUE while TRUE 注意 1 在每个程序中要先做wait mutex 后做signal mutex 二者要成对出现 2 对同步信号量full和empty的wait signal操作同样必须成对出现 但它们分别位于不同的程序中 3 无论是在生产者进程还是消费者进程中 两个wait操作的次序不能颠倒 2 利用AND信号量解决生产者 消费者问题算法描述 生产者进程 消费者进程 do do Swait empty mutex Swait full mutex 产品送往buffer in 从buffer out 中取出产品 in in 1 modN out out 1 modN Ssignal mutex full Ssignal mutex empty while TRUE while TRUE 2 读者 写者问题 reader writersproblem 一个数据对象 文件或记录 可以被多个进程共享 其中有些进程要求读 而另一些进程要求写或修改 于是把只想读的进程称之为 读者 而其它称之为 写者 允许多个读者同时读一个共享对象 但绝不允许一个写者和其它进程 读者和写者 同时访问共享对象 否则将破坏数据完整性 产生混乱 所谓 读者 写者问题 是指保证一个写者必须与其它进程互斥地访问共享对象的同步问题 Rmutex 读互斥信号量 用于使读者互斥地访问共享变量readcount 初值为1 Wmutex 写互斥信号量 用于实现一个写者与其它读者和写者互斥地访问共享对象 初值为1 Readcount 正在读的阅读者数 初值为0 当没有写进程正在访问共享数据集时 阅读者可以进入访问 否则 必须等待 读者进程 wait rmutex readcount readcount 1 ifreadcount 1thenwait wmutex signal rmutex 读数据集 wait rmutex readcount readcount 1 ifreadcount 0thensignal wmutex signal rmutex 写者进程 wait wmutex 写数据集 signal wmutex 1 利用记录型信号量解决读者 写者问题 2 利用信号量集机制解决读者 写者问题 VarRNinteger L mx semaphore RN 1 begin parbegin reader begin repeat Swait L 1 1 Swait mx 1 0 performreadoperation Ssignal L 1 untilfalse end writer begin repeat Swait mx 1 1 L RN 0 performwriteoperation Ssignal mx 1 untilfalse end parend end 3 哲学家进餐问题 TheDinningPhilosophersProblem 该问题是描述有五个哲学家共用一张圆桌 分别坐在周围的五张椅子上 在圆桌上有五个碗和五支筷子 他们的生活方式是交替的进行思考和就餐 平时 一个哲学家进行思考 饥饿时便试图取用其左右最靠近他的筷子 只有在他拿到两支筷子时才能进餐 进餐毕 放下筷子继续思考 分析 放在桌子上的筷子是临界资源 在一段时间内只允许一位哲学家使用 为了实现对筷子的互斥使用 可以用一个信号量表示一支筷子 由这五个信号量构成信号量数组 semaphorechopstick 5 所有信号量均被初始化为1 1 利用记录型信号量解决哲学家进餐问题第i位哲学家的活动可描述为 semaphorechopstick 5 1 1 1 1 1 do wait chopstick i wait chopstick i 1 mod5 eat signal chopstick i signal chopstick i 1 mod5 think while TRUE 当哲学家饥饿时 总是先去拿他左边的筷子 即执行P chopstick i 成功后 再去拿他右边的筷子 即P chopstick i 1 mod5 又成功后便可进餐 进餐毕 又先放下他左边的筷子 然后再放右边的筷子 缺点 可保证不会有两个相邻的哲学家同时进餐 但有可能引起死锁 可采取以下几种解决方法 至多只允许有四位哲学家同时去拿左边的筷子 最终能保证至少有一位哲学家能够进餐 并在用毕时能释放出他用过的两只筷子 从而使更多的哲学家能够进餐 仅当哲学家的左 右两只筷子均可用时 才允许他拿起筷子进餐 规定奇数号哲学家先拿他左边的筷子 然后再去拿右边的筷子 而偶数号哲学家则相反 按此规定 将是1 2号哲学家竞争1号筷子 3 4号哲学家竞争3号筷子 即五位哲学家都先竞争奇数号筷子 获得后 再去竞争偶数号筷子 最后总会有一位哲学家能获得两只筷子而进餐 2 利用AND信号量机制解决哲学家进餐问题 在哲学家进餐问题中 要求每个哲学家先获得两个临界资源 筷子 后方能进餐 这在本质上就是前面所介绍的AND同步问题 故用AND信号量机制可获得最简洁的解法 semaphorechopstick 5 1 1 1 1 1 do think Swait chopstick i 1 mod5 chopstick i eat Ssignal chopstick i 1 mod5 chopstick i while TRUE 2 4管程机制 2 4 1管程的基本概念 1 建立管程的基本理由由于对信号量的控制分布在整个程序的各个进程中 这样不便于系统对临界资源的控制和管理 也很难发现和纠正分散在用户程序中的对同步原语的错误使用等问题 为此 应把分散的各同类临界区集中起来 并为每个可共享资源设立一个专门的管程来统一管理各进程对该资源的访问 这样既便于系统管理共享资源 又能保证互斥访问 管程的基本思想 把信号量及其操作原语封装在一个对象中 2 管程 monitor 的定义是一个关于共享资源的数据结构以及针对该资源的操作过程所构成的软件模块 这组操作能同步进程和改变管程中的数据 管程由三部分组成 1 局部于管程的共享变量说明 2 对该数据结构进行操作的一组过程 3 对局部于管程的数据设置初始值的语句 此外 还须为管程赋予一个名字 管程的示意图 为了实现对临界资源的互斥访问 管程每次只允许一个进程进入其内 即访问管程内的某个过程 这是由编译系统保证的 在管程中设置有进程等待队列以及相应的等待及唤醒操作 进程只能通过调用管程中所说明的外部过程来间接访问管程中的共享变量 每个管程都有一个入口等待队列和一个紧急等待队列 当一个进程试图进入一个已被占用的管程时 被排进入口等待队列 在管程内部 由于执行唤醒操作而出现多个等待进程 因管程的互斥进入而进入紧急等待队列 管程的语法如下 typemonitor name monitor variabledeclarations procedureentryP1 begin end procedureentryP2 begin end procedureentryPn begin end begin initializationcode end 3 引入管程的优点 1 具有良好的封装性 可增强模块的独立性 2 引入管程可以提高代码的可读性 便于修改和维护并保证代码的正确性 4 管程和进程的区别 1 进程是为了描述程序的动态执行过程 而管程是为了协调进程的同步和对共享资源的访问 2 操作系统维护进程的数据结构是PCB 而与管程相关的数据结构是等待队列 3 管程可被进程调用 管程与操作系统的共享资源相关 4 进程有创建和撤消 而管程没有 2 4 2利用管程解决生产者 消费者问题 在利用管程方法来解决生产者 消费者问题时 首先便是为它们建立一个管程 并命名为Proclucer Consumer 或简称为PC 其中包括两个过程 1 put item 过程 生产者利用该过程将产品投放到缓冲池中 并用整型变量count来表示在缓冲池中已有的产品数目 当count n时 表示缓冲池已满 生产者须等待 2 get item 过程 消费者利用该过程从缓冲池中取出一个产品 当count 0时 表示缓冲池中已无可取用的产品 消费者应等待 typeproducer consumer monitor Varin out count integer buffer array 0 n 1 ofitem notfull notempty condition procedureentryput item begin ifcount nthennotfull wait buffer in nextp in in 1 modn count count 1 ifnotempty queuethennotempty signal end procedureentryget item begin ifcount 0thennotempty wait nextc buffer out out out 1 modn count count 1 ifnotfull quenethennotfull signal end beginin out 0 count 0end 在利用管程解决生产者 消费者问题时 其中的生产者和消费者可描述为 producer begin repeat produceaniteminnextp PC put item untilfalse end consumer begin repeat PC get item consumetheiteminnextc untilfalse end 2 6进程通信 进程通信是指并发进程间的信息交换 各进程在执行过程中为合作完成一个共同的任务 需要协调步伐 交流信息 操作系统提供了多种进程间通信机制 可分别适用于多种不同的场合 进程间交换的信息可多可少 少者仅是一个状态或数值 多者可交换成千上万个数据 按通信量的大小 我们可把进程间通信分成低级通信和高级通信 显然 进程的同步和互斥是一种简单的通信 但因交换的信息量少 被归结为低级通信 本节介绍的是高级通信 它是方便高效地交换大量信息的通信方式 高级进程通信方式有很多种 大致可归并为三类 共享存储器 消息传递和管道文件 1 共享存储器系统 Shared MemorySystem 共享存储区可用于进程间的大数据量通信 其方式是在内存中分配一片空间作为共享存储区 需要进行通信的各进程把共享存储区附加到自己的地址空间中 然后就像正常操作一样对共享区中的数据进程读或写 如果用户不需要某个共享存储区 可以把它取消 通过对共享存储区的访问 相关进程间就可以传输大量数据 在使用共享存储区时 需要进程互斥和同步机制的辅助来确保数据一致性 2 6 1进程通信的类型 2 管道 Pipe 通信 管道 pipe 是指用于连接一个读进程和一个写进程以实现他们之间通信的一个共享文件 写进程以字符流形式将大量的数据送入管道 而读进程则从管道中接收 读 数据 进程通过对该文件的读 写实现进程间的通信 由系统自动处理二者间的同步 调度和缓冲 由于发送进程和接收进程是利用管道进行通信的 故又称为管道通信 这种方式首创于UNIX系统 由于它能有效地传送大量数据 因而又被引入到许多其它操作系统中 3 消息传递系统 Messagepassingsystem 消息传递方式以消息 message 为单位在进程间进行数据交换 程序员直接利用系统提供的一组通信命令 原语 进行通信 操作系统隐藏了通信的实现细节 大大简化了通信程序编制的复杂性 因而获得了广泛的应用 因其实现方式的不同进一步分成直接通信方式和间接通信方式 1 直接通信方式 消息缓冲通信 发送进程利用OS所提供的发送命令 直接把消息发送给目标进程 由系统管理一组缓冲区 其中每个缓冲区可以存放一个消息 即一组信息 进程发送消息时 先向系统申请一缓冲区 将消息写进去 然后把缓冲区链接到接收进程的一个消息队列中 并用signal操作通知接收者 接收进程可在适当时候从消息队列中取出消息 并释放该缓冲区 通常 系统提供下述两条通信命令 原语 Send Receiver message 发送消息给接收进程 Receive Sender message 接收Sender发来的消息 例如 原语Send P2 m1 表示将消息m1发送给接收进程P2 原语Receive P1 m1 表示接收由P1发来的消息m1 在某些情况下 接收进程可与多个发送进程通信 不可能事先指定发送进程 例如 用于提供打印服务的进程 它可以接收来自任何一个进程的 打印请求 消息 这时 接收进程的receive原语中的源进程参数 是完成通信后的返回值 可表示为 Receive id message 2 间接通信方式 信箱通信 信箱是实现进程通信的中间实体 可存放一定数量的消息 发送进程将消息送入信箱 接收进程从信箱中取出发给自己的信息 信箱是一种数据结构 在逻辑上可分为两个部分 信箱头 包括信箱名字 信箱属性 公用 私用或共享 信箱格状态等 信箱体 用来存放消息的多个信箱格 信箱的创建和撤消进程可利用信箱创建原语来建立一个新信箱 创建者进程应给出信箱名字 信箱属性 公用 私用或共享 对于共享信箱 还应给出共享者的名字 当进程不再需要读信箱时 可用信箱撤消原语将之撤消 消息的发送和接收进程之间利用信箱进行通信 必须使用共享信箱 并利用系统提供的通信原语进行通信 Send mailbox message 将一个消息发送到指定信箱 Receive mailbox message 从指定信箱中接收一个消息 1 通信链路 communicationlink 为使在发送进程和接收进程之间能进行通信 必须在两者之间建立一条通信链路 1 按通信链路的连接方法 分为点 点连接和多点连接链路 2 按通信方式不同 分为单向通信链路和多向链路 2 6 2消息传递系统实现中的若干问题 2 消息的格式 1 消息必须具有一定的格式