第三章同步、通信与死锁.ppt

1 第三章同步 通信与死锁 2 3 1进程的同步与互斥在多道程序的环境中 系统中的多个进程可以并发执行 同时它们又要共享系统中的资源 由此诸进程间会产生错综复杂的相互制约的关系 一 进程间制约关系1 竞争关系源于资源共享 多个不存在逻辑关系的进程因共享资源而产生制约关系 若一个进程要求使用某一资源 而该资源正被另一个进程使用 并且这一资源不允许两个进程同时访问 那么该进程只有等待 只有这一资源释放后才能使用 2 协作关系源于进程间的协作 一组进程为完成共同任务分工协作 各进程都独立以不可预知速度推进 在执行的先后次序就有约束 在一些关键点上协调工作 若一个进程运行到某关键点时 在尚未收到另一协作进程发来的信息前应阻塞自己 等协作进程发来消息后方可继续执行 进程 资源 进程 进程 进程 3 进程间这种相互依赖又相互制约 相互协作又相互竞争的关系 主要表现在进程互斥和进程同步两方面二 进程互斥引例 宿舍电话的使用打印机的使用1 临界资源一次仅允许一个进程使用的资源称为临界资源 引例中的电话和打印机都属于临界资源 还有光盘刻录机 绘图仪 共享变量 共享的数据结构等等也是临界资源 2 临界区 每个进程中访问临界资源的那段程序段称为临界区 临界段 4 例 统计两个进程P1和P2对共享变量count的访问计数 P1 P2 R1 count R2 count R1 R1 1 R2 R2 1 count R1 count R2 两进程并发执行 可能的执行顺序为 P1 R1 count R1 R1 1 P2 R2 count R2 R2 1 count R2 P1 count R1 虽然两个进程各自都执行了对count加1的操作 但结果为何count只增加1 count是临界资源 P1 P2访问count的两个程序段就是临界区 两个进程必须互斥的进入临界区 否则就可能出与时间有关的错误 5 进程互斥进程应互斥访问同一临界资源 即进程应互斥的进入临界区 当一进程正在访问某临界区时 就不允许其它进程进入 试图进入临界区的另一进程必须等待 进程之间的这种相互制约的关系称为进程互斥 4 进入临界区的准则 每次至多有一个进程进入临界区内执行 若已有进程在临界区中 试图进入此临界区的其他进程应等待 进入临界区的进程应在有限时间内退出 以便让等待队列中的一个进程进入 6 三 进程同步 引例 两位同学约好星期天去玩 早上8 00在校门口 不见不散 当一个同学先来到校门口 要等另一个同学 到齐后一起去玩 互斥的概念来自于诸进程对临界资源的竞争 同步来源于多个进程的协作 在人类社会中竞争与协作是永恒的 进程同步 几个进程相互协作 一个进程到达某点后 若另一进程尚未完成某些操作 就必须停下来等待 只有等另一进程的这些操作完成了才能继续执行 协作进程间需要在某些关键点上排定执行先后次序而等待 传递信号或消息所产生的协作关系称为进程同步 7 例 计算fun1 X fun2 y 两进程合作完成任务进程1 计算fun1 X 进程2 计算fun2 X 与进程1结果相乘 进程1和进程2并发执行 8 3 2进程互斥的实现 一 实现进程互斥的软件算法现在很少用软件方法解决互斥 但通过学习软件解法能使读者了解到 在早期进程互斥问题的解决并不是一件很简单的事 9 尝试 1 boolinside1 false P1不在其临界区内boolinside2 false P2不在其临界区内cobeginprocessP1 processP2 while inside2 while inside1 inside1 true inside2 true 临界区 临界区 inside1 false inside2 false coendP1和P2可能同时进入临界区 10 尝试 2 boolinside1 false P1不在其临界区内boolinside2 false P2不在其临界区内cobeginprocessP1 processP2 inside1 true inside2 true while inside2 while inside1 临界区 临界区 inside1 false inside2 false coendP1和P2可能永远等待 11 processP0 inside 0 true turn 1 while inside 1 processP1 inside 1 true turn 0 while inside 0 cobegin coend boolinside 2 inside 0 false inside 1 false enum 0 1 turn Peterson算法 12 为每一进程设标志位inside i 当inside i true时 表示进程pi要求进入 或正在临界区中执行 此外再设一个变量turn 用于指示允许进入的进程编号 进程0为了进入先置inside 0 true 并置turn为1 表示应轮到p1进入 接着再判断inside 1 turn 1的条件是否满足 若不满足则可进入 或者说当inside 1 false或者turn 0时 进程可以进入 前者表示p1未要求进入 后者表示仅允许p0进入 13 软件解法的缺点 1 忙等待2 实现过于复杂 需要较高的编程技巧 14 二 实现进程互斥的硬件设施 用软件解决很难 现代计算机大多提供一些硬件指令 利用关中断实现进程互斥利用Test and Set指令实现互斥利用swap指令实现进程互斥 15 1 利用关中断实现进程互斥 进程进入临界区时关中断 在进程退出临界区时开中断 关中断方法简单有效关中断方法的缺点 16 2 Test and Set TS 指令实现互斥 TS指令boolTS bool 17 TS指令实现进程互斥bools true cobeginprocessPi i 1 2 nwhile TS s 上锁 临界区 s true 开锁 coend 变量s代表了临界资源的状态 可把它看成一把锁 S初值设为true 表示没有进程在临界区 资源可用 进入临界区前 首先用TS指令测试s 若没有进程在临界区 则可进入 否则循环测试直至s的值为true 当进程退出临界区时 把s的值置为true 18 3 swap指令实现进程互斥 swap指令又称交换指令 在Intelx86中称为XCHG 功能是交换两个字的内容 voidSWAP bool 19 利用swap实现进程互斥为每一临界资源设置一个全局布尔变量lock 其初值为false 表示无进程在临界区内 在每个进程中有局部布尔变量keyi boollock false cobeginProcessPi i 1 2 nboolkeyi true do SWAP keyi lock while keyi 上锁 临界区 SWAP keyi lock 开锁 coend 20 实现进程互斥的软件算法太过复杂 效率低下 实现进程互斥的硬件方法虽简单有效 但采用忙式等待 白白浪费cpu时间 将测试能否进入临界区的责任推卸给各进程 会削弱系统的可靠性 加重用户的编程负担 且这些方案只能解决进程互斥问题 却不能解决进程同步问题 21 3 3信号量与PV操作 一 信号量的概念信号量的概念是由荷兰科学家Dijkstra于1965年提出的 管理和控制铁路和公路交通的重要工具是信号灯 利用信号灯的颜色控制各种车辆的正常通行 在操作系统中引入了信号灯 信号量 的概念 让多个进程通过信号量展开交互 22 1 信号量的定义是一个结构型数据结构 定义如下 structsemaphore intvalue 信号量的值structpcb list 信号量队列的头指针 信号量说明 semaphores 信号量必须置一次且只能置一次初值 初值不能为负数 对信号量只能执行P V操作 23 2 P V操作对信号量仅能执行P V操作 对信号量的P操作记为 P S P操作是一个原子操作 对信号量的V操作记为 V S V操作是一个原子操作 在实际系统中 一般情况下是由机器硬件提供P V操作的指令 当然是原子操作 若机器不提供P V操作的指令 则操作系统提供P V操作原语 24 P s s value 若s value 0 则执行P s 的进程继续执行 若s value 0 则执行P s 的进程被阻塞 并把它插入到等待信号量s的阻塞队列中 V s s value 若s value 0 则执行V s 的进程继续执行 若s value 0 则执行V s 的进程从等待信号量s的阻塞队列中唤醒头一个进程 然后自己继续执行 操作系统正是利用信号量的状态对进程和资源进行管理 从物理意义上理解 P操作相当于申请资源 V操作相当于释放资源 25 二 用信号量实现进程互斥 1 两个进程间的互斥semaphoreS S 1 cobeginProcessP1 ProcessP2 P S P S V S V S coend 临界区 临界区 26 对于两个并发进程 互斥信号量的值仅取1 0和 1三个值若S 1表示没有进程进入临界区若S 0表示有一个进程进入临界区若S 1表示一个进程进入临界区 另一个进程等待进入 27 例 有一个售票厅只能容纳300人 当少于300人时 可以进入购票 否则在外等待 若将每一个购票者看作一个进程 请用P V操作编程实现 semaphoreS S 300 ProcessPi i 1 2 3 P S 进入购票厅 购票 离开购票厅 V S 28 思考 对于n个并发进程 如何实现互斥 信号量的取值范围是什么 有什么含义 设置互斥信号量S m m为某种临界资源可用数量 cobeginprocessP1processP2 processpn P S P S P S V S V S V S coend 临界区 临界区 临界区 互斥信号量联系一组并发进程 各进程对此信号量执行P V操作 因此又称为公用信号量 29 信号量取值范围 m m n信号量的含义 S 0表示有S个资源可用S 0表示无资源可用S 0则 S 表示S等待队列中的进程个数 30 三 用信号量实现进程的同步 1 进程同步模型进程P1到达L1这一点时 若进程P2还未执行到L2点 进程P1就必须停下来等待 等到进程P2到达L2这一点时 P1才能继续运行 也就是进程P1在L1这一点要与进程P2同步 P1等待P2 semaphores S 0CobeginprocessP1 processP2 L1 P s L2 V s coend 总结 P1在L1点等待P2进程执行到L2点才能继续执行 设置信号量s 0P1进程L1点 P S P2进程L2点 V S 31 在操作系统中 同步有各种各样 归纳起来有两类 保证一组合作进程按确定的次序执行保证共享缓冲区的合作进程的同步 2 合作进程的执行次序若干个进程为了完成一个共同任务而并发执行 在这些进程中 有些进程之间有次序的要求 有些进程之间没有次序的要求 为了描述方便 可以用一个图来描述诸进程合作完成某一任务的次序 进程流图 32 33 进程流图是实际例子抽象出来的 例 a b c d c f 34 例 试用信号量实现这三个并发进程按确定的次序执行 a 分析进程的同步关系进程P1 P2可并发执行 P3的执行必须等待P1 P2都完成后才能开始执行 b 设置信号量 说明含义 初值 s13 0表示进程P1尚未执行完成 s23 0表示进程P2尚未执行完成 c 写出程序描述 35 36 例 试用信号量实现这三个进程的同步 SemaphoreSB SC SB 0 SC 0 cobeginPa Pb Pc P SB P SC V SB V SC coend 37 3 共享缓冲区的合作进程的同步设有一个缓冲区buffer 大小为一个字节 某计算进程 和打印进程 共用 CP进程不断产生字符 送buffer IOP进程从buffer中取出字符打印 如不加控制 会有多种打印结果 这取决于这两个进程运行的相对速度 在这众多的打印结果中 只有CP IOP进程的运行刚好匹配的一种是对的 其它均为错误 并且不能重现 38 要保证打印结果的正确 CP IOP必须遵循以下同步规则 1 当CP把结果送入buffer后 IOP才能从buffer中取 否则IOP必须等待 2 当IOP从buffer中取走数据后 CP才能将新产生数据送buffer 否则也必须等待 解决这个问题的步骤 1 分析问题 弄清楚同步关系 如上分析 2 设置信号量 说明含义 初值 3 写出程序描述 39 40 四 互斥和同步对信号量操作方法的差异 互斥和同步都是通过对信号量的P V操作来实现的 但这两种控制机制对信号量的操作策略是不同的 互斥的实现 是不同进程对同一信号量进行P V操作 进入临界区之前执行P操作 退出临界区后执行V操作 同步的实现 Pa进程要同步等待Pb需设置一信号量 Pa进程中实行P操作 Pb进程实行V操作 若进程Pb也要同步等待Pa 则要设置另一个信号量 P V操作必须成对出现 有一个P操作就一定有一个V操作当为互斥操作时 它们同处于同一进程当为同步操作时 则不在同一进程中出现 41 五 经典的进程同步 互斥问题 1 生产者 消费者问题 问题描述 有m个生产者和n个消费者 它们共享可存放k件产品的缓冲区 只要缓冲区未满 生产者就可以把产品送入缓冲区 只要缓冲区未空 消费者就可以从缓冲区中取走物品 42 著名的生产者 消费者问题是计算机操作系统中并发进程内在关系的一种抽象 是典型的进程同步问题 在操作系统中 生产者进程可以是计算进程 发送进程 而消费者进程可以是打印进程 接收进程等等 解决好生产者 消费者问题就解决好了一类并发进程的同步问题 43 问题分析 对于生产者进程 生产一个产品 当要送入缓冲区时 要检查是否有空缓冲区 若有 则可将产品送入缓冲区 并通知消费者进程 否则 等待 对于消费者进程 当它去取产品时 要看缓冲区中是否有产品可取 若有则取走一个产品 并通知生产者进程 否则 等待 这种相互等待 并互通信息就是典型的进程同步 因此应该设两个同步信号量 empty 表示可用的空缓冲区的数目 初值为kfull 表示可以使用产品的数目 初值为 缓冲区是一个临界资源 必须互斥使用 所以另外还需要设置一个互斥信号量mutex 其初值为 44 问题的解 itemB k semaphoreempty empty k 可以使用的空缓冲区数semaphorefull full 0 缓冲区内可以使用的产品数semaphoremutex mutex 1 互斥信号量intin 0 放入缓冲区指针intout 0 取出缓冲区指针 cobeginprocessproducer i processconsumer j while true while true produce P full P empty P mutex P mutex take fromB out appendtoB in out out 1 k in in 1 k V mutex V mutex V empty V full consume coend 45 讨论 若将生产者进程中两个P操作交换次序 那么当缓冲区存满k件产品 empty 0 mutex 1 full k 时 生产者又生产一件产品 将在P empty 上等待 此时mutex 0 消费者进程将在P mutex 上等待 这就导致两进程都处于无休止的等待状态 造成了死锁 若将消费者进程中两P操作交换次序 则当缓冲区为空时 也会出项上述类似问题 46 总结 P V操作必须成对出现 有一个P操作就一定有一个V操作 当为互斥操作时 它们同处于同一进程 当为同步操作时 则不在同一进程中出现 如果两个P操作在一起 那么P操作的顺序至关重要 一个同步P操作与一个互斥P操作在一起时 同步P操作在互斥P操作前 而两个V操作在一起时顺序无关紧要 47 2 读者 写者问题 问题描述有两组并发进程 读者和写者 共享一个文件F要求 允许多个读者同时执行读操作只允许一个写者执行写操作任一写者在完成写操作之前不允许其它读者或写者工作写者执行写操作前 应让已有的写者和读者全部退出 48 问题分析 读者和写者互斥 写者和写者互斥访问文件设信号量writeblock 用于实现读写互斥 写写互斥地访问文件 另设一个全局变量readcount 记录正在读的读者数目 设置信号量mutex 用于使读者互斥地访问共享变量readcount 49 intreadcount 0 读进程计数semaphorewriteblock mutex writeblock 1 mutex 1 cobeginprocessreader i processwriter j P mutex P writeblock readcount 写文件 if readcount 1 V writeblock P writeblock V mutex 读文件 P mutex readcount if readcount 0 V writeblock V mutex Coend 50 3 哲学家就餐问题 问题描述 有五个哲学家围坐在一圆桌旁 桌中央有一盘通心面 每人面前有一只空盘于 每两人之间放一把叉子 每个哲学家思考 饥饿 然后吃通心面 为了吃面 每个哲学家必须获得两把叉子 且每人只能直接从自己左边或右边去取叉子 51 问题分析 每把叉子都必须互斥使用 因此为每把叉子设置互斥信号量fork i i 0 1 2 3 4 初值均为1 当哲学家吃面前必须执行两个P操作 获得自己左边和右边的两把叉子 吃完后必须执行两次V操作 放下两把叉子 52 semaphorefork 5 for inti 0 i 5 i fork i 1 cobeginprocessphilosopher i i 0 1 2 3 4 while true think P fork i P fork i 1 5 eat V fork i V fork i 1 5 coend 53 上述解法可能出现永远等待 有若干种办法可避免死锁 1 至多允许四个哲学家同时吃 2 奇数号先取左手边的叉子 偶数号先取右手边的叉子 3 每个哲学家取到手边的两把叉子才吃 否则一把叉子也不取 54 3 4进程通信 进程通信 InterprocessCommunication IPC 是指进程之间的信息交换 信号量及P V操作实现的是进程之间的低级通讯 所以P V为低级通讯原语 它只能传递简单的信号 不能传递交换大量信息 本节介绍高级进程通信 是指进程间高效的传送大量数据的通信方式 55 进程间通信的方式 信号 signal 通信机制 管道 pipeline 通信机制消息传递 messagepassing 通信机制信号量 semaphore 通信机制共享主存 sharedmemory 通信机制前两种是UNIX最早的版本就提供的进程通信机制 信号通信机制只能发送单个信号而不能传递数据 管道通信虽能传送数据 却只能在进程家族内使用 应用范围有限 56 进程通信方式发展 UNIX发展历史中 AT T的Bell与加大伯克利的BSD是两大主力 Bell致力于改进传统的进程IPC 形成了SYSTEM IPC机制 上述后三种通信机制 BSD在改进IPC的同时 把网络通信规程 TCP IP 实现到UNIX内核中 考虑把同一计算机上的进程通信纳入更广的网络范围的进程间通信 这种努力结果出现了socket网络通信机制 57 一 管道通信机制 管道通信是UNIX的传统进程通信方式 也是UNIX发展最有意义的贡献之一 所谓管道 是指用于连接一个读进程和一个写进程的特殊文件 称pipe文件 发送进程以字符流形式把大量数据送入管道 接收进程从管道中接收数据 所以叫管道通信 58 管道的实质是一个共享文件 基本上可借助于文件系统的机制实现 包括 管道 文件的创建 打开 关闭和读写 但写进程和读进程间的相互协调单靠文件系统机制解决不了 读写进程相互同步 必须做到以下几点 1 互斥 即一个进程正在使用某个管道写入或读出数据时 另一个进程就必须等待 2 发送者和接收者双方必须能够知道对方是否存在 如果对方已经不存在 就没有必要再发送信息 3 同步 指当写进程把一定量的数据发送后 便睡眠等待 直到读进程把管道中数据取走后 在把它唤醒 反之当读进程读空管道时 也被阻塞 直到写进程将数据写入管道后 才将它唤醒 59 二 共享主存通信机制 在主存中开辟一个公用存储区 要通信的