计算机操作系统第2章进程管理教学课件PPT.ppt

第二章 进程管理 概述进程的描述进程控制线程 进程互斥和同步进程间通信死锁问题进程其他方面的举例 为了描述程序在并发执行时对系统资源的共享 需要一个描述程序执行时动态特征的概念 这就是进程 本章将讨论进程概念 进程控制和进程间关系 本章要点 基础 进程描述及控制实现 互斥与同步解决 几个经典问题关于 进程通信 重点难点 2 1进程的基本概念 前趋图 是一个有向无循环图 前趋图用于描述进程之间执行的前后关系 图中的每个结点可用于描述一个程序段或进程 乃至一条语句 结点间的有向边则用于表示两个结点之间存在的偏序或前趋关系 节点 概述 图2 1 a 中存在着这样的前趋关系 p1 p2 p1 p3 p1 p4 p2 p5 p3 p5 p4 p6 p4 p7 p5 p8 p6 p8 p7 p9 p8 p9 图2 1前趋图 或表示为 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 应当注意 前趋图中必须不存在循环 但在左图中却有着下述的前趋关系 s2 s3 s3 s2 程序并发执行的目的 提高计算机的处理能力提高资源利用率分为两种形式 多道程序环境下的多道程序的并发执行在某道程序的几个程序段中 包含可同时执行或可颠倒顺序执行的代码 计算 顺序执行和并发执行下各设备的使用效率 顺序执行 并发执行 程序具有封闭性程序失去封闭性独享资源共享资源 互为存在条件 可再现性程序与 计算 不再一一对应有相互制约 进程的定义 进程的特征动态性 进程对应程序的执行进程是动态产生 创建 运行 消亡进程在其生命周期内 在三种基本状态之间转换独立性 各进程的地址空间相互独立 除非采用进程间通信手段 并发性 指多个进程实体同存于内存中 且能在一段时间内同时运行 异步性 每个进程都以其相对独立的不可预知的速度向前推进 结构化 进程 代码段 数据段 pcb 进程与程序的区别进程是动态的 程序是静态的 炒菜 菜谱进程是暂时的 程序的永久的 进程是一个状态变化的过程 程序可长久保存 进程与程序的组成不同 进程的组成包括程序 数据和进程控制块 即进程状态信息 进程与程序的对应关系 通过多次执行 一个程序可对应多个进程 通过调用关系 一个进程可包括多个程序 进程具有并行特征 程序没有 进程是竞争计算机资源的基本单位 进程的描述进程 程序 数据 进程控制块pcb有人把这三部分称为 进程映像 程序是进程的不可缺少的组成部分 如果一个程序段允许被共享 则它应该是可重入的 或纯代码段数据是进程处理的对象进程控制块是进程的控制结构 包含了进程的描述信息 控制信息和资源信息以及现场保护区 是进程的唯一标识 系统通过pcb管理和控制进程 通常的程序是不能并发执行的 为使程序能并发执行 应为之配置一进程控制块 即pcb 所谓创建进程是指创建进程实体中的pcb 撤销亦如此 进程控制块pcb processcontrolblock 进程控制块是由os维护的用来记录进程相关信息和管理进程而设置的一个专门的数据结构包含了进程的描述信息 控制信息和资源信息以及现场保护区pcb是进程动态特性的集中反映系统通过pcb感知进程的存在 通过pcb中所包含的各项变量的变化 掌握进程的状态以达到控制进程活动的目的 pcb结构的全部或部分常驻内存 pcb随进程的创建而填写 随进程的撤消而释放 有生命周期 系统利用pcb来控制和管理进程 所以pcb是系统感知进程存在的唯一标志进程与pcb是一一对应的 进程控制块的内容 数据结构很复杂 进程标识符 内部进程标识符 processid 唯一 通常是一个整数 进程名 外部标识符 通常基于可执行文件名 不唯一 用户标识符 userid 进程组关系 processgroup 进程控制信息 程序和数据的地址 进程同步和通信机制 资源清单 链接指针进程调度信息 进程状态 进程优先级 资源信息等处理机状态 寄存器值 通用 程序计数器pc 状态psw 地址包括栈指针 pcb的组织方式 链接方式 同一状态的进程其pcb成一链表 多个状态对应多个不同的链表各状态的进程形成不同的链表 就绪链表 阻塞链表 链接 索引方式 pcb索引表 执行指针 就绪表指针 等待表指针 空闲表指针 pcb1pcb2pcb3pcb4pcb5pcb6pcb7pcb8pcb9 就绪索引表 143 等待索引表 675 空闲索引表 89 进程的状态及其转换 其它状态创建状态 创建 新new 状态os已完成为创建一进程所必要的工作已构造了进程标识符已创建了管理进程所需的表格终止状态 exit 终止后进程移入该状态它不再有执行资格表格和其它信息暂时保留实用程序为了分析性能和利用率 可能要提取程序的历史信息挂起状态 把一个进程从内存转到外存 挂起状态这个问题的引入是由于进程优先级的引入 一些低优先级进程可能等待较长时间 从而被对换至外存 目的是 提高处理机效率 就绪进程表为空时 os将阻塞进程从内存中 挂起 到磁盘的 挂起队列 再从该队列选另一进程进入内存 或接受一个新进程的请求 为运行进程提供足够内存 资源紧张时 暂停某些进程 如 cpu繁忙 或实时任务执行 内存紧张用于调试 在调试时 挂起被调试进程 从而对其地址空间进行读写 状态间的转换挂起 suspend 把一个进程从内存转到外存 可能有以下几种情况 阻塞到阻塞挂起 没有进程处于就绪状态或就绪进程要求更多内存资源时 会进行这种转换 以纳入新进程或运行就绪进程 就绪到就绪挂起 当有高优先级阻塞 系统认为会很快就绪的 进程和低优先级就绪进程时 系统会选择挂起低优先级就绪进程 运行到就绪挂起 对抢先式分时系统 当有高优先级阻塞挂起进程因事件出现而进入就绪挂起时 系统可能会把运行进程转到就绪挂起状态 状态间的转换激活 activate 把一个进程从外存转到内存 可能有以下几种情况 就绪挂起到就绪 没有就绪进程或挂起就绪进程优先级高于就绪进程时 会进行这种转换 阻塞挂起到阻塞 当一个进程释放足够内存时 系统会把一个高优先级阻塞挂起 系统认为会很快出现所等待的事件 进程转为阻塞状态 较少出现 unixv中的进程状态 另一进程 用户运行态 核心运行态 被抢占状态 僵死状态 内存中睡眠 睡眠且交换 就绪且交换 内存中就绪 创建状态 fork exit 内存足够 内存不足 交换进 交换进 交换出 交换出 唤醒 唤醒 睡眠 被调度 中断返回 系统调用 返回 被抢占 返回用户态 就绪 睡眠 且交换态 外存就绪 睡眠 态 由于内存有限 将原位于内存的程序和数据交换出去 使之位于外存 被抢占态 在进程完成系统调用返回用户态之前 检查是否有优先级更高的进程存在 若有 则当前进程被抢占 这些控制和管理功能是由操作系统的原语来实现 原语 primitive 是在管态下执行 完成系统特定功能的过程 原语和机器指令类似 其特点是执行过程中不允许被中断 是一个不可分割的基本单位 原语的执行是顺序的而不可能是并发的 一种原语的实现方法是以系统调用方式提供原语接口 且采用屏蔽中断的方式来实现原语功能 以保证原语操作不被打断的特性 何时创建进程 用户登录时 作业调度时 用户程序向os提出服务请求时 如创建打印进程用户程序调用其他子程序时 创建过程 create pstat paddr pid prio pname 原语fork 分配空白pcb及内存 初始化pcb并插入就绪队列 输入 新进程的符号名 优先级 开始执行地址输出 新创建进程的内部标识符pid 在总链队列上查找有无同名的进程 if 有同名进程 return 错误码 带错误码返回 从pcb资源池中申请一个空闲的pcb结构 if 无空pcb结构 return 错误码 带错误码返回 用入口参数设置pcb内容 置进程为 就绪 态 将新进程的pcb插入就绪队列 将新进程的pcb插入总链队列 return 新进程的pid 创建原语creat 2 进程的终止 何时终止进程 正常结束 halt return exit logout 异常结束 越界 访问权限错 特权指令错 非法指令错 运行 等待超时 算术运算错 i o故障等os干预 如死锁时 父进程请求终止某子进程 父进程本身已终止时终止过程 kill pid exit 原语找到其pcb 终止运行并重新调度 终止所有子进程 释放资源 将pcb移入空队列 命令形式为 kill原语无参数 无返回信息 算法kill输入 无输出 无 由运行指针得当前进程的pid 释放本进程所占用的资源 该进程从总链队列中摘除 释放pcb结构 转进程调度程序 3 进程的阻塞 何时阻塞 请求系统服务得不到满足时 启动i o操作时 合作进程提供的数据尚未到达时 系统进程无新任务可处理时 阻塞过程 wait 原语保护现场停止执行 修改进程状态 将其pcb插入到阻塞队列 调度另一进程 4 进程的唤醒 当等待事件发生时唤醒 signal 将其pcb改为就绪态 并从阻塞队列移入就绪队列 正在执行的进程由于其时间片完而被暂停执行 此时进程应从运行态变为a状态 处于静止阻塞状态的进程 在进程等待的事件出现后 应转变为b状态 若进程正处于运行态时 应终端的请求而暂停下来以便研究其运行情况 执行挂起进程原语 这时进程应转变为c状态 若进程已处于阻塞状态 则此时应转变为d状态 若进程已处于就绪状态 则此时应转变为e状态 执行解除挂起进程原语后 如挂起进程处于就绪状态 则应转变为f态 如处于阻塞状态 则应转变为g态 一个进程刚被创建时 它的初始状态为h a h 1 静止阻塞 2 活动阻塞 3 静止就绪 4 活动就绪 5 执行 进程同步与互斥一 进程间的相互作用 无关进程 不影响其它进程 与其它进程的进展情况无关 相关进程 由于共享某些资源 所以一个进程的执行可能会影响其它进程的执行结果 与时间有关的错误 对一次只允许一个进程使用的资源 临界资源 的共享过程不加以控制时 会导致程序结果与执行速度有关 即结果不可再现 例 程序a的n n 1和程序b的print n n 0交叉运行 进程的同步 直接制约 进程的互斥 由资源共享引起间接制约 互斥 不允许两个以上的进程同时使用临界资源或进入临界区 互斥时的原则 有空让进 当临界区空闲时 允许请求进程立即进入该临界区 无空等待 有进程正在临界区时 其它请求进程等待 有限等待 请求进程应在有限的等待时间内进入临界区 让权等待 当进程不能进入临界区时 应立即释放处理机 2 3 2信号量机制 基本原理 两个或多个进程可以通过简单的信号进行合作 一个进程可以被迫在某一位置停止 直到它接收到一个特定的信号 任何复杂的合作需求都可以通过适当的信号结构得到满足 为了发信号 需要使用一个称作信号量的特殊变量 为通过信号量s传送信号 进程可执行原语signal s 为通过信号量s接收信号 进程可执行原语wait s 如果相应的信号仍然没有发送 进程被阻塞 直到发生传送 这两个操作被称为 p v 操作 公用信号量 通常用于实现进程间互斥 初值为1 私有信号量 用于实现进间的同步 初值为0或正整数n 仅允许拥有它的进程实施p操作 信号量s大于等于零时表示可供并发进程使用的资源实体数 但s小于零时表示正在等待使用临界区的进程数 p原语的操作功能v原语的操作功能 除初始化外 对s值的修改只能通过原子操作进行 而不能使用一般的赋值语句 1整型信号量信号量s是个特殊的整型变量 信号s的值描述了可用资源的数量或等待该资源的进程个数当s 0时表示可用资源数 当s 0时其绝对值 s 表示等待该资源的进程数 除初始化外 对s值的修改只能通过原子操作进行 而不能使用一般的赋值语句 s是一个整型量 通过2个原子操作wait s 和signal s 来访问 wait s whiles 0dono op 空操作指令 忙等 s s 1 signal s s s 1 2记录型信号量 由于整型机制中会不断测试不满足 让权等待 而引入typesemaphore recordvalue integer l listofprocess endl 为进程链表 用于链接所有等待该类资源进程 procedurewait s vars semaphorebegins value s value 1 ifs value 0themblock s l end proceduresignal s vars semaphonebegins value s vaule 1ifs value 0thenwakeup s l end用wait s 和signal s 实现同步与互斥 在记录型信号量机制中 s value初值 表示系统中某类资源的数目 s value 0 表该信号量链表中已阻塞进程的数目 3and型信号量 当不用它时 有可能发生系统死锁 死锁 在无外力作用下的一种僵持状态 特点 要么全分配 要么一个也不分配 swait s1 s2 sn ifs1 1and andsn 1thenfori 1tondosi si 1 endforelse进程进入第一个达到的满足si 1条件的si信号量队列等待 同时将该进程的程序计数器地址回退 置为sp操作处 endifssignal s1 s2 sn fori 1tondosi si 1 从所有si信号量等待队列中移出进程并置入就绪队列 endfor 4信号量集 略 为提高效率而对and信号的扩充 三种特例 1 swait s d d 允许每次申请d个资源 当资源数少于d时 不予分配 2 swait s 1 1 s 1 记录型信号量 s 1时 互斥型信号量 3 swait s 1 0 可控开关 当时 允许进入 s 1时 不能进入 信号量小结 一个信号量可用于n个进程的同步互斥 且只能由p v操作修改 用于互斥时 s初值为1 取值为1 n 1 相当于临界区的通行证 实际上也是资源个数 s 1时 临界区可用s 0时 已有一进程进入临界区s 0 s 0表示可用资源个数s 0表示该资源的等待队列长度 p v操作小结 p s 请求分配一个资源 v s 释放一个资源 p v操作必须成对出现 用于互斥时 位于同一进程内 用于同步时 交错出现于两个合作进程内 多个p操作的次序不能颠倒 否则可能导致死锁 同步p操作应出现在互斥p操作之前 多个v操作的次序可任意 用p v操作实现进程同步的算法可以简单归纳如下 分析每个进程的执行条件和释放条件 针对每个执行条件设置一个信号量 其初值根据初始情况确定 对每个进程做如下处理 在请求条件处执行p 执行条件信号量 在释放条件处执行v 释放条件信号量 同步问题与互斥问题的区别 互斥问题中各进程涉及共同的临界资源 因此每个进程中涉及同一个临界资源的临界区中所执行的p v操作的信号量是相同的 而同步问题中每个进程由于执行条件和释放条件的不同因而其p v操作涉及的信号量也不同 这是解决这两类问题算法的不同之处 2 3 3信号量的应用 信号量的分类 互斥信号量和资源信号量 互斥信号量用于保证互斥的 用于申请或释放资源的使用权 常初始化为1 资源信号量 用于申请或归还资源 可以初始化为大于1的正整数 表示系统中某类资源的可用个数 wait操作用于申请资源 或使用权 进程执行wait原语时 可能会阻塞自己 signal操作用于释放资源 或归还资源使用权 进程执行signal原语时 有责任唤醒一个阻塞进程 1 利用信号量实现互斥 用于互斥时 对每一个临界资源设一个信号量s s初值为1 取值为1 n 1 相当于临界区的通行证 实际上也是资源个数 s 1时 临界区可用s 0时 已有一进程进入临界区s 0时 临界区已被占用 s 个进程正等待进入 利用信号量实现互斥 对每一临界资源 区 设一信号量s 初值 1 此时s相当于此临界资源的使用许可证 进程1 begin p s 临界区 v s end 进程2 begin p s 临界区 v s end 例 有一单向行驶的公路桥 每次只允许一辆汽车通过 当汽车到达桥头时 若桥上无车便可上桥 否则 需等待 直到桥上的汽车下桥为止 若每一辆汽车为一个进程 请用p v操作编程实现 解 公路桥是1个临界资源 由于它每次只允许一辆汽车通过 故可为它设置一个初值为1的临界资源mutex 汽车过公路桥的动作可描述为 semaphoremutex 1 crossbridge begin行驶到桥头 p mutex 上桥行驶 从另一头下桥 v mutex end 例 某车站售票厅有20个窗口 任何时刻最多可容纳20名购票者进入 当售票厅中少于20名购票者时 则厅外的购票者可立即进入 否则需在厅外等待 若把一个购票者看作一个进程 请用p v操作管理这些并发进程 要求如下 在主函数中给出信号量的定义和初值 给出一个购票者进程的算法 给出当购票者最多不超过n 设n 20 个时 信号量可能的变化范围 问题分析 判断该问题是互斥问题还是同步问题 可以将该售票厅的每个窗口看作是一个临界资源为每个购票者进程共享 每个购票者进程只能使用其中一个窗口 售票厅有20个窗口 所以有20个同类的临界资源 一次可以允许20个进程进入 并且先来者先进入 由此可知 该问题满足互斥的2个必要条件 共享临界资源 共享方式是先来者先进入 所以该问题是互斥问题 根据互斥问题的解决方法设置信号量并赋初值 设置一个信号量mutex 初值为20 用信号量的p v操作将临界区括起来 算法描述 主函数算法 main intmutex 20 cobeginp1 pi pn coend 购票者i的算法 pi p mutex 进入售票厅占有一个窗口购票 v mutex 该类问题是指多个合作进程在执行时有先后次序的要求 前后形成前驱后继关系 可以用前趋图描述 在前驱与后继同步问题中 每个进程是否能够执行 取决于它的所有前驱是否执行结束 每个前驱的结束都是它得以执行的必要条件之一 因此 需要针对该进程的每个前驱设置一个信号量 并在该进程开始处执行相应的p操作 同样 如果进程有后继 则当它结束时 需要执行其后继所等待的信号量的v操作 释放其后继所等待的执行条件 2 利用信号量来描述前趋关系 合作进程的执行次序 例 pa pb pc为一组合作进程 其前驱图如右 要求pa执行结束后 pb pc才能执行 设两个信号量sb sc分别表示进程pb pc能否开始执行 初值为sb 0 sc 0 pa pb pc p sb p sc v sb v sc 共享单缓冲区的两个进程的同步问题 例 设一计算进程ic和一打印进程op共用一个单缓冲 如图所示 ic进程负责不断地计算数据并输入缓冲区t中 op进程负责从缓冲区t中取出数据去打印 同步约束 op进程只有在ic进程将数据输入缓冲区后 才能取出打印 ic进程只有在op进程将数据取出打印后 才能送入下一个计算数据 sa 0 sa信号量表示缓冲区中有无信息 初始无数据 sb 1 sb信号量表示缓冲区中有无空位 初始有空位 对于前驱后继同步问题的算法可以按下列步骤进行 分析每个进程j 看它有无前驱 如果有 则针对每个前驱i设置一个信号量v 初值皆为0 在每个进程j开始时 针对其每个前驱的信号量sij执行p操作 有几个前驱执行几个p操作 在每个进程i执行完毕后 针对其每个后继的信号量sij执行v操作 有几个后继执行几个v操作 其中 i表示前驱进程号 j表示后继进程号 此时 让他们共享一个公用信号量s s初值一般为 0 s 0表示可用资源个数s 0表示该资源的等待队列长度 例如 设有4个进程 其执行的先后关系如下图所示 用p v操作实现其同步 算法描述 main ints12 s13 s24 s34 0 cobeginp1 p2 p3 p4 coend p1 执行p1自己的程序 v s12 v s13 p2 p s12 执行p2自己的程序 v s24 p3 p s13 执行p3自己的程序 v s34 p4 p s24 p s34 执行p4自己的程序 这样 无论哪个进程先来 只要不是p1进程 都会在执行了相应的p操作后 因为执行条件不成立而被挂到相应信号量的等待队列上 等待其前驱执行该信号量的v操作后将其唤醒 从而保证这些进程并发执行时其执行的时序遵循给定的同步关系 s1 s2 s3 s4 s5 s6 a b c d e g f 图2 10前趋图举例 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 用信号量描述同步 有一个同步条件设一s 初值s 0 s为可用资源个数 实现 a进程已执行过程序段1 b进程才能执行程序段2 设一信号量s 初值为0 a进程程序段1l1 v s b进程l2 p s 程序段2 若p v操作的信号量初值为1 当前值为 3 则表示有个等待进程 3个 2 4经典进程同步问题 2 4 1生产者 消费者问题2 4 2哲学家进餐问题2 4 3读者 写者问题 2 4 1生产者 消费者问题 生产者和消费者问题 是相互合作进程关系的一种抽象 是一个广义的概念 可以代表一类具有相同属性的进程 生产者和消费者问题 生产者和消费者进程共享一个固定大小的缓冲区 其中 一个或多个生产者生产数据 并将数据存入缓冲区 并有一个消费者从缓冲区中取数据 假设缓冲区的大小为n 存储单元的个数 它可以被生产者和消费者循环使用 分别设置两个指针in和out in指向生产者将存放数据的存储单元 而out指向消费者将取数据的存储单元 生产者和消费者必须互斥 必须是生产者和消费者互斥进入缓冲区 即 某时刻只允许一个实体 生产者或消费者 访问缓冲区 生产者互斥消费者和其它任何生产者 生产者和消费者必须同步 生产者不能向满缓冲区写数据 消费者也不能在空缓冲区取数据 一个互斥条件 缓冲区一次只能让一个进程访问 设一互斥信号量mutex 初值为1 两个同步条件 缓冲区中至少有一个单元为空时 生产者才送数 设一信号量empty 表示空缓冲区的数量 初值为n 缓冲区中至少有一个单元为满时 消费者才取数 设一信号量full 表示满缓冲区的数量 初值为0 voidmain intmutex 1 empty n full 0 intin 0 out 0 elemtypebuffer n cobeginproducer consumer coend full 装满产品的缓冲区数目 初值为0 empty 空缓冲区数目 初值为n mutex 对缓冲区互斥使用的公用信号量 初值为1 一 利用记录型信号量解决生产者一消费者问题 voidproducer while true 生产一个数据 wait empty 申请空缓冲区 wait mutex 实现对缓冲池的互斥使用 buffer in 生产的数据 in in 1 modn signal mutex signal full 满缓冲区的个数加1 voidconsumer while true wait full 申请满缓冲区 wait mutex 实现互斥 消费buffer out 中的数据 out out 1 modn signal mutex signal empty 空缓冲区的个数加1 二 利用and信号量解决生产者 消费者问题 voidproducer while true 生产一个数据 swait empty mutex 申请空缓冲区 实现对缓冲池的互斥使用 buffer in 生产的数据 in in 1 modn ssignal mutex full 满缓冲区的个数加1 voidconsumer while true swait full mutex 申请满缓冲区 实现互斥 消费buffer out 中的数据 out out 1 modn ssignal mutex empty 空缓冲区的个数加1 注意 进程应该先申请资源信号量 再申请互斥信号量 顺序不能颠倒 对任何信号量的wait与signal操作必须配对 同一进程中的多对wait与signal语句只能嵌套 不能交叉 对同一信号量的wait与signal可以不在同一个进程中 wait与signal语句不能颠倒顺序 wait语句一定先于signal语句 2 4 2哲学家进餐问题 1 利用记录型信号量解决哲学家进餐问题 放在桌子上的筷子是临界资源 在一段时间内只允许一位哲学家使用 为了实现对筷子的互斥使用 可以用一个信号量表示一只筷子 由这五个信号量构成信号量数组 其描述如下 varchopstick array 0 4 ofsemaphore 所有的信号量都要初始化为1 1 原理 至多只允许四个哲学家同时进餐 以保证至少有一个哲学家能够进餐 最终总会释放出他所使用过的两支筷子 从而可使更多的哲学家进餐 以下将room作为信号量 只允许4个哲学家同时进入餐厅就餐 这样就能保证至少有一个哲学家可以就餐 而申请进入餐厅的哲学家进入room的等待队列 根据fifo的原则 总会进入到餐厅就餐 因此不会出现饿死和死锁的现象 semaphorechopstick 5 1 1 1 1 1 semaphoreroom 4 voidphilosopher inti while true think wait room 请求进入房间进餐wait chopstick i 请求左手边的筷子wait chopstick i 1 5 请求右手边的筷子eat signal chopstick i 1 5 释放右手边的筷子signal chopstick i 释放左手边的筷子signal room 退出房间释放信号量room 2 原理 仅当哲学家的左右两支筷子都可用时 才允许他拿起筷子进餐 方法1 利用and型信号量机制实现 根据课程讲述 在一个原语中 将一段代码同时需要的多个临界资源 要么全部分配给它 要么一个都不分配 因此不会出现死锁的情形 当某些资源不够时阻塞调用进程 由于等待队列的存在 使得对资源的请求满足fifo的要求 因此不会出现饥饿的情形 semaphorechopstick 5 1 1 1 1 1 voidphilosopher inti while true think swait chopstick i 1 5 chopstick i eat ssignal chopstick i 1 5 chopstick i 方法2 利用信号量的保护机制实现 通过信号量mutex对eat 之前的取左侧和右侧筷子的操作进行保护 使之成为一个原子操作 这样可以防止死锁的出现 semaphoremutex 1 semaphorechopstick 5 1 1 1 1 1 voidphilosopher inti while true think wait mutex wait chopstick i 1 5 wait chopstick i signal mutex eat signal chopstick i 1 5 signal chopstick i 3 原理 规定奇数号的哲学家先拿起他左边的筷子 然后再去拿他右边的筷子 而偶数号的哲学家则相反 按此规定 将是1 2号哲学家竞争1号筷子 3 4号哲学家竞争3号筷子 即五个哲学家都竞争奇数号筷子 获得后 再去竞争偶数号筷子 最后总会有一个哲学家能获得两支筷子而进餐 而申请不到的哲学家进入阻塞等待队列 根fifo原则 则先申请的哲学家会较先可以吃饭 因此不会出现饿死的哲学家 semaphorechopstick 5 1 1 1 1 1 voidphilosopher inti while true think if i 2 0 偶数哲学家 先右后左 wait chopstick i 1 mod5 wait chopstick i eat signal chopstick i 1 mod5 signal chopstick i else 奇数哲学家 先左后右 wait chopstick i wait chopstick i 1 mod5 eat signal chopstick i signal chopstick i 1 mod5 2 4 3读者 写者问题 读者 写者进程应满足的条件 允许多个读者进程可以同时读数据 不允许多个写者进程同时写数据 即只能互斥写数据 若有写者进程正在写数据 则不允许读者进程读数据 问题描述 为多个进程访问一个共享数据区 如数据库 文件 内存区以及一组寄存器等的数据问题建立一个通用模型 其中若干读进程只能读数据 若干写进程只能写数据 解决读者 写者问题 需设置两个信号量 1 读互斥信号量rmutex 用于使读者互斥地访问共享变量readcount 这里readcount是记录有多少读者正在读 2 写互斥信号量wmutex 用于实现读写互斥和写写互斥地访问共享文件 读者 写者问题进行如下描述 intrmutex wmutex readcount 0 rmutex 1 wmutex 1 voidreader while true wait rmutex if readcount 0 wait wmutex readcount signal rmutex performreadoperation wait rmutex readcount readcount 1 if readcount 0 signal wmutex signal rmutex 一 利用记录型信号量解决读者 写者问题 voidwriter while true wait wmutex performwriteoperation signal wmutex voidmain readcount 0 parbegin reader writer 2 5进程通信 例 建立一pipe 子进程向pipe写 父进程从pipe读 include includemain intx fd 2 charbuf 30 s 30 pipe fd 创建管道 while x fork 1 循环创建 直至成功 if x 0 sprintf buf thisisatest n 写入buf数组 write fd 1 buf 30 把buf中字符写入管道 exit 0 正常结束 else 从子进程返回 执行父进程 wait 0 阻塞父进程 直至子进程终