计算机操作系统第三章.ppt

第三章进程的同步与通信 进程同步的主要任务 是使并发执行的诸进程之间能有效地共享和相互合作 从而使程序的执行具有可再现性 第三章进程的同步与通信 进程同步的基本概念信号量机制经典进程同步问题管程机制进程通信UNIX进程同步和进程通信 3 1进程同步的基本概念 多道程序环境下 进程间可能存在两种关系 资源共享关系相互合作关系进程间相互制约 直接制约 进行协作 等待来自其他进程的信息 同步 间接制约 进行竞争 独占分配到的部分或全部共享资源 互斥 3 1进程同步的基本概念 3 1 1临界资源3 1 2临界区3 1 3利用软件方法解决进程互斥问题3 1 4利用硬件方法解决进程互斥问题 3 1 1临界资源 临界资源 criticalresource 需要进程间互斥方式访问的共享资源 即一次只允许一个进程访问 生产者 消费者问题 Producer Consumer 若干进程通过有限的共享缓冲区交换数据 其中 生产者 进程不断写入 而 消费者 进程不断读出 共享缓冲区共有N个 任何时刻只能有一个进程可对共享缓冲区进行操作 producer produceaniteminnextp while counter n buffer in nextp in in 1 n counter while counter 0 Nextc buffer out out out 1 n counter Consumetheiteminnextc consumer 共享变量的修改冲突 操作顺序冲突 有3个进程 get copy和put 它们对4个存储区域f s t和g进行操作 把f中的序列原样复制到g中 有6种可能的操作顺序 只有一种结果是正确的 3 1 2临界区 临界区 criticalsection 每个进程中访问临界资源的那段代码称为临界区若能保证个进程互斥地进入自己的临界区 就能保证他们互斥的访问临界资源 3 1 2临界区 进入区 entrysection 在进入临界区之前 检查可否进入临界区的一段代码 如果可以进入临界区 通常设置相应 正在访问临界区 标志退出区 exitsection 用于将 正在访问临界区 标志清除 剩余区 remaindersection 代码中的其余部分 3 1 2临界区 同步机制应遵循的准则空闲让进 其他进程均不处于临界区 忙则等待 已有进程处于其临界区 有限等待 等待进入临界区的进程不能 死等 让权等待 不能进入临界区的进程 应释放CPU 如转换到阻塞状态 3 1 3利用软件方法解决进程互斥问题 有两进程Pi和Pj共享一个临界资源R 用软件方法使进程Pi和Pj互斥访问资源R 3 1 3利用软件方法解决进程互斥问题 算法1 设立一个公用整型变量turn 描述允许进入临界区的进程标识在进入区循环检查是否允许本进程进入 turn为i时 进程Pi可进入 在退出区修改允许进入进程标识 进程Pi退出时 改turn为进程Pj的标识j while turn i criticalsection turn j remaindersection 3 1 3利用软件方法解决进程互斥问题 算法1 缺点强制轮流进入临界区 没有考虑进程的实际需要 容易造成资源利用不充分 在Pi出让临界区之后 Pj使用临界区之前 Pi不可能再次使用临界区 3 1 3利用软件方法解决进程互斥问题 算法2 设立一个标志数组flag 描述进程是否在临界区 初值均为FALSE 先检查 后修改 在进入区检查另一个进程是否在临界区 不在时修改本进程在临界区的标志 在退出区修改本进程在临界区的标志 criticalsection flag i FALSE remaindersection while flag j flag i ture 3 1 3利用软件方法解决进程互斥问题 算法2 优点不用交替进入 可连续使用 缺点Pi和Pj可能同时进入临界区 即在检查对方flag之后和切换自己flag之前有一段时间 结果都检查通过 这里的问题出在检查和修改操作不能连续进行 3 1 3利用软件方法解决进程互斥问题 算法3 类似于算法2 与互斥算法2的区别在于先修改后检查 可防止两个进程同时进入临界区 criticalsection flag i FALSE remaindersection flag i ture while flag j 3 1 3利用软件方法解决进程互斥问题 算法3 缺点Pi和Pj可能都进入不了临界区 即在切换自己flag之后和检查对方flag之前有一段时间 结果都切换flag 都检查不通过 3 1 3利用软件方法解决进程互斥问题 算法4 结合算法1和算法3 是正确的算法同时使用flag 和turn在进入区先修改后检查 并检查并发修改的先后检查对方flag 如果不在临界区则自己进入 空闲则入否则再检查turn 保存的是较晚的一次赋值 则较晚的进程等待 较早的进程进入 先到先入 后到等待 3 1 3利用软件方法解决进程互斥问题 算法4 criticalsection flag i false remaindersection flag i ture turn j while flag j criticalsection flag j false remaindersection flag j ture turn i while flag i 3 1 4利用硬件方法解决进程互斥问题 Test and Set指令 该指令读出标志后将其设置为TRUEbooleanTS boolean lock booleanold old lock lock TRUE returnold lock表示资源的两种状态 TRUE表示正被占用 FALSE表示空闲 3 1 4利用硬件方法解决进程互斥问题 利用TS实现进程互斥 利用TS实现进程互斥 每个临界资源设置一个公共布尔变量lock 初值为FALSE在进入区利用TS进行检查 有进程在临界区时 重复检查 直到其它进程退出时 检查通过 3 1 4利用硬件方法解决进程互斥问题 Swap指令 交换两个字 字节 的内容voidSWAP int a int b inttemp temp a a b b temp 3 1 4利用硬件方法解决进程互斥问题 利用Swap实现进程互斥 key TRUE do SWAP criticalsection remaindersection 利用Swap实现进程互斥 每个临界资源设置一个公共布尔变量lock 初值为FALSE 每个进程设置一个私有布尔变量key locl FALSE 3 1 4利用硬件方法解决进程互斥问题 硬件方法的优点适用于任意数目的进程 在单处理器或多处理器上简单 容易验证其正确性可以支持进程内存在多个临界区 只需为每个临界区设立一个布尔变量硬件方法的缺点等待要耗费CPU时间 不能实现 让权等待 可能 饥饿 从等待进程中随机选择一个进入临界区 有的进程可能一直选不上可能死锁 3 2信号量机制 1965年 由荷兰学者Dijkstra提出 所以P V分别是荷兰语的test proberen 和increment verhogen 是一种卓有成效的进程同步机制 3 2信号量机制 3 2 1整型信号量机制3 2 2记录型信号量机制3 2 3信号量集机制 3 2 1整型信号量机制 把整型信号量定义为一个整型量 除初始化外 仅能通过两个标准的原子操作 AtomitcOperation wait S 和Signal S 来访问 这两个操作也称为P V操作 voidwait ints while s 0 s P操作 voidsignal ints s V操作 3 2 1整型信号量机制 为临界资源设置一整型信号量mutex 使其初值为1 将各进程的临界区置于wait S 和signal S 之间即可 wait mutex criticalsection remaindersection Signal metux wait mutex criticalsection remaindersection Signal metux Process1 Process2 3 2 1整型信号量机制 注意 wait mutex 和signal metex 必须成对出现缺少wait mutex 不能保证互斥访问临界资源缺少signal mutex 将使临界资源永远不被释放 3 2 1整型信号量机制 用信号量来描述前驱关系进程P1中有语句S1 进程P2中有语句S2 若希望S1先于S2执行设一信号量S 初值为0进程P1中S1 signal S 进程P2中wait S S2 3 2 1整型信号量机制 inta 0 b 0 c 0 d 0 e 0 f 0 g 0 voidp1 S1 signal a signal b voidp2 wait a S2 signal signal c voidp6 wait e wait f wait g S6 3 2 2记录信号量机制 每个信号量s除一个整数值s value 计数 外 还有一个进程等待队列s queue 其中是阻塞在该信号量的各个进程的标识信号量只能通过初始化和两个标准的原语来访问 作为OS核心代码执行 不受进程调度的打断初始化指定一个非负整数值 表示空闲资源总数 又称为 资源信号量 若为非负值表示当前的空闲资源数 若为负值其绝对值表示当前等待临界区的进程数 structs intvalue Listqueue 记录信号量 3 2 2记录信号量机制 voidwait S s count 表示申请一个资源if s count 0 表示没有空闲资源 调用进程进入等待队列s queue block 阻塞调用进程 voidsignal S s count 表示释放一个资源 if s count 0 表示有进程处于阻塞状态 从等待队列s queue中取出一个进程P wakeup 进程P进入就绪队列 3 2 4信号量集机制 AND信号量集机制用于同时需要多种资源且每种占用一个时的信号量操作 一段处理代码需要同时获取两个或多个临界资源 可能死锁 各进程分别获得部分临界资源 然后等待其余的临界资源 各不相让 3 2 4信号量集机制 AND信号量集机制基本思想 在一个原语中 将一段代码同时需要的多个临界资源 要么全部分配给它 要么一个都不分配 称为Swait SimultaneousWait 在Swait时 各个信号量的次序并不重要 虽然会影响进程归入哪个阻塞队列 但是由于是对资源全部分配或不分配 所以总有进程获得全部资源并在推进之后释放资源 因此不会死锁 3 2 4信号量集机制 Swait S1 S2 Sn P原语 while TRUE if S1 1 3 2 4信号量集机制 Ssignal S1 S2 Sn V原语 while TRUE for i 1 i n i Si 释放占用的资源 for eachprocessPwaitinginSi queue 检查每种资源的等待队列的所有进程 从等待队列Si queue中取出进程P if 判断进程P是否通过Swait中的测试 注 与signal不同 这里要进行重新判断 通过检查 资源够用 时的处理 进程P进入就绪队列 else 未通过检查 资源不够用 时的处理 进程P进入某等待队列 3 2 4信号量集机制 一般 信号量集 机制用于同时需要多种资源 每种占用的数目不同 且可分配的资源还存在一个临界值时的处理基本思想 在AND型信号量集的基础上进行扩充 进程对信号量Si的测试值为ti 用于信号量的判断 即Si ti 表示资源数量低于ti时 便不予分配 占用值为di 用于信号量的增减 即Si Si di和Si Si di Swait S1 t1 d1 Sn tn dn Ssignal S1 d1 Sn dn 3 2 4信号量集机制 一般 信号量集 的几种特定情况 Swait S d d 表示每次申请d个资源 当少于d个时 便不分配 Swait S 1 1 表示互斥信号量 Swait S 1 0 作为一个可控开关当S 1时 允许多个进程进入临界区 当S 0时 禁止任何进程进入临界区 3 3经典进程同步问题 3 3 1生产者 消费者问题3 3 2读者 写者问题3 3 3哲学家进餐问题 3 3 1生产者 消费者问题 问题描述若干进程通过有限的共享缓冲区交换数据 其中 生产者 进程不断写入 而 消费者 进程不断读出 共享缓冲区共有N个 任何时刻只能有一个进程可对共享缓冲区进行操作 3 3 1生产者 消费者问题 记录型信号量解决mutex用于访问缓冲区时的互斥 初值是1full是 满 数目 初值为0 empty是 空 数目 初值为N 实际上 full和empty是同一个含义 full empty N 3 3 1生产者 消费者问题 AND信号量解决用Swait empty mutex 代替wait empty 和wait mutex 依此类推 3 3 2读者 写者问题 问题描述 对共享资源的读写操作 任一时刻 写者 最多只允许一个 而 读者 则允许多个 读 写 互斥 写 写 互斥 读 读 允许 3 3 2读者 写者问题 采用记录型信号量Wmutex表示 允许写 初值是1 公共变量readcount表示 正在读 的进程数 初值是0 RMutex表示对readcount的互斥操作 初值是1 3 3 2读者 写者问题 P wmutex write V wmutex P rmutex if readcount 0 P wmutex readcount V rmutex read P rmutex readcount if readcount 0 V Wmutex V rmutex Writer进程 reader进程 3 3 2读者 写者问题 采用一般 信号量集 机制 问题增加一个限制条件 同时读的 读者 最多RN个mx表示 允许写 初值是1L表示 允许读者数目 初值为RN Swait mx 1 1 L RN 0 write Ssignal mx 1 Swait L 1 1 mx 1 0 read Ssignal L 1 Writer进程 reader进程 3 3 3哲学家进餐问题 问题描述 由Dijkstra首先提出并解决 5个哲学家围绕一张圆桌而坐 桌子上放着5支筷子 每两个哲学家之间放一支 哲学家的动作包括思考和进餐 进餐时需要同时拿起他左边和右边的两支筷子 思考时则同时将两支筷子放回原处 如何保证哲学家们的动作有序进行 如 不出现有人永远拿不到筷子 3 4管程机制 3 4 1管程的引入3 4 2管程的基本概念3 4 3利用管程解决生产者 消费者问题3 4 4利用管程解决哲学家进餐问题 3 4 1管程的引入 信号量的缺点P V操作使用不当 如次序颠倒 重复 遗漏P V操作 可能造成与时间相关的错误易读性差 要了解对于一组共享变量及信号量的操作是否正确 必须通读整个系统或者并发程序 不利于修改和维护 各模块的独立性差 任一组变量或一段代码的修改都可能影响全局 正确性难以保证 操作系统或并发程序通常很大 很难保证这样一个复杂的系统没有逻辑错误 3 4 1管程的引入 管程的引入1971年 Dijkstra提出把进程对临界资源的同步操作集中起来构成 秘书 进程1973年 Hoare和Hanson把 秘书 进程思想发展成 管程 概念 把并发进程间的同步操作 分别集中于相应的管程中 3 4 2管程的基本概念 管程的概念一个管程定义了一个数据结构和能为并发进程所执行的 在该数据结构上 一组操作 这组操作能同步进程和改变管程中的数据管程的组成局部于管程的共享变量说明对该数据结构进行操作的一组进程对局部于管程的数据设置初始值 3 4 2管程的基本概念 管程的特征模块化 一个管程是一个基本程序单位 可以单独编译 抽象数据类型 管程是一种特殊的数据类型 其中不仅有数据 而且有对数据进行操作的代码信息封装 管程是半透明的 管程中的外部过程 函数 实现了某些功能 至于这些功能是怎样实现的 在其外部则是不可见的 改变管程中的数据 3 4 2管程的基本概念 管程的原理所有进程要访问临界资源时 都必须经过管程才能进入 且管程每次只准许一个进程进入管程 从而实现了进程互斥利用管程实现进程同步时 必须设置两个同步操作原语wait和signal当某进程通过管程请求临界资源而未能满足时 管程便调用wait原语使该进程等待 并将它排在等待队列上 当另一进程访问完并释放之后 管程又调用signal原语 唤醒等待队列中的队首进程 3 4 2管程的基本概念 管程中的队列进入队列 因为管程是互斥进入的 所以当一个进程试图进入一个巳被占用的管程时它应当在管程的入口处等待 因而在管程的入口处应当有一个进程等待队列 称作入口等待队列 紧急等待队列 如果进程 唤醒进程 则 等待 继续 如果进程 在执行又唤醒进程 则 等待 继续 如此 在管程内部 由于执行唤醒操作 可能会出现多个等待进程 已被唤醒 但由于管程的互斥进入而等待 因而还需要有一个进程等待队列 这个等待队列被称为紧急等待队列 它的优先级应当高于入口等待队列的优先级 3 4 2管程的基本概念 条件变量为了区别不同的等待原因 引入条件变量condition每个条件变量有wait和signal原语针对条件变量c cwait c 将自己阻塞在c队列中 csignal c 将c队列中的一个进程唤醒 3 4 2管程的基本概念 若进程P唤醒进程Q 则随后可有两种执行方式 进程P Q都是管程中的进程 P等待 直到执行Q离开管程或下一次等待 Hoare采用 Q送入Ready队列 直到执行P离开管程或下一次等待 3 4 3利用管程解决生产者 消费者问题 建立一个管程PC 包括两个过程put item get item 3 4 4利用管程解决哲学家进餐问题 哲学家的三种状态进餐 饥饿和思考管程中的三个过程pickup putdown test 3 5进程通信 进程通信指进程间的信息交换进程的互斥和同步可归结为低级通信本节介绍高级进程通信 指用户可直接利用操作系统提供的一组通信命令 高效地传送大量数据的通信方式 3 5进程通信 3 5 1进程通信的类型3 5 2直接通信和间接通信方式3 5 3消息传递系统中的几个问题3 5 4消息缓冲队列机制 3 5 1进程通信的类型 低级通信 只能传递状态和整数值 控制信息 包括进程互斥和同步所采用的信号量和管程机制 优点是速度快 缺点是 传送信息量小 效率低 每次通信传递的信息量固定 若传递较多信息则需要进行多次通信 编程复杂 用户直接实现通信的细节 编程复杂 容易出错 高级通信 能够传送任意数量的数据 包括三类 共享存储区 管道 消息传递 3 5 1进程通信的类型 共享存储区基于共享数据结构的通信方式基于共享存储区的通信方式消息传递系统进程间的数据交换是以格式化的消息为单位的 计算机网络中也称报文包括直接通信和间接通信方式 3 5 1进程通信的类型 管道通信用于连接一个读进程和一个写进程以实现他们之间通信的一个共享文件必须解决的问题 互斥 同步 对方是否存在 3 5 2直接通信和间接通信方式 直接通信方式 消息直接发给目标进程要求收 发双方显式指出对方的标识符Send Receiver message Receive Sender message 接收进程可以接收多个发送进程的消息 这时可用完成通信后的返回值做源进程参数Receive id message 3 5 2直接通信和间接通信方式 直接通信方式解决生产者 消费者问题 产生数据于nextp中 send consumer nextp producer receive producer nextc 消费nextc中数据 consumer 3 5 2直接通信和间接通信方式 间接通信方式 进程间通过某种共享数据结构的实体作为通信中转 如消息队列和信箱信箱操作原语 创建 撤消 发送 接收信箱分类 私用信箱 公用信箱 共享信息通讯方式 一对一 多对一 一对多 多对多 3 5 3消息传递系统中的几个问题 通信链路显式建立 隐式建立点点连接链路 多点连接链路单向 双向无容量 没有缓冲区 有容量 有缓冲区 3 5 3消息传递系统中的几个问题 消息的格式单机环境 格式简单 如字节流 bytestream 网络环境 消息又称报文 datagram message 消息头 发送进程名 接收进程名 消息长度 类型 编号 发送日期和时间等消息正文定长 不定长 3 5 3消息传递系统中的几个问题 发送接收进程同步方式发送 接收阻塞 无缓冲区发送不阻塞 接收阻塞 发送 接收均不阻塞 3 5 4消息缓冲队列通信机制 消息缓冲队列通信机制中的数据结构消息缓冲区 sender发送进程标识符size消息长度text正文next指向下一消息缓冲区的指针PCB中有关通信的数据项 mq消息队列对首指针mutex消息队列互斥信号量sm消息队列资源信号量 3 5 4消息缓冲队列通信机制 发送原语 voidsend receiver a int i malloc a size i sender a sender i size a size i text a text i next 0 获得接收进程receiver的进程内部标识符为j wait j mutex insert j mq i signal j mutex signal j sm 3 5 4消息缓冲队列通信机制 接收原语 voidreceive b 获得接收进程receiver的进程内部标识符为j wait j sm wait j mutex remove j mq i signal j mutex b sender i sender b size i size b text i text 3 6UNIX进程同步和进程通信 3 6 1UNIX进程同步机制3 6 2UNIX进程通信机制 3 6 1UNIX进程同步机制 UNIX的信号量UNIX支持信号量和信号量集相关数据结构 semid ds表示一个信号量集合sem表示集合中的一个信号量有关的系统调用 semget 信号量的初始化semctl 信号量控制 查询信号量状态等Semop 信号量操作 原则操作 3 6 1UNIX进程同步机制 Linux的自旋锁 spinlock 自旋锁最多被一个可执行线程持有 如果一个执行线程试图获得一个被争用 已被持有 的自旋锁 那么该线程将一直进行忙循环 旋转 等待锁重新可用 自旋锁的实现和体系结构密切相关 往往通过汇编实现 代码文件定义在中 3 6 2UNIX进程通信机制 UNIX进程间通信IPC信号 简单的进程通信机制 通知进程发生了某种事件 也称为软中断 提供了一种处理异步事件的方法管道 有名管道FIFO和无名管道pipe系统V风格IPC 消息队列 信号量和共享存储BSD风格IPC 套接字 管道管道提供进程间单向通信的方法 简单的说 管道是连接一个进程的输出至另一个进程的输入的方法 3 6 2UNIX进程通信机制 3 6 2UNIX进程通信机制 FIFOFIFO是作为有名文件存在与文件系统中的 因此在使用前要打开它 可以用open close等处理打开和关闭FIFO 但要注意不能使用O RDWR方式打开 因为FIFO是半双工的 3 6 2UNIX进程通信机制 消息队列提供一种广义的消息传递方法 允许进程发送和接收一个缓冲区种数据 希望通信的一组进程通过一个具有唯一表示的消息队列连接在一起 要传送的任意数据打包并以消息的形式通过消息队列传送 消息的格式可以有操作系统规定 也可以有协作的进程规定消息队列中的数据按照它们提交的顺序传递 消息队列实际上是内核地址空间的内部链表 两个或多个进程可以通过访问一个公共的系统消息队列来交换信息 使用消息队列的进程可以执行两种操作 发送消息和接收消息 发送进程放置一个消息于这个消息队列中 接收进程从这个消息队列获得信息 3 6 2UNIX进程通信机制 消息队列 messagequeue 每个message不定长 由类型 type 和正文 text 组成UNIX消息队列API msgget依据用户给出的整数值key 创建新消息队列或打开现有消息队列 返回一个消息队列ID msgsnd发送消息 msgrcv接收消息 可以指定消息类型 没有消息时 返回 1 msgctl对消息队列进行控制 如删除消息队列 3 6 2UNIX进程通信机制 通过指定多种消息类型 可以在一个消息队列中建立多个虚拟信道注意消息队列不随创建它的进程的终止而自动撤销 必须用msgctl msgqid IPC RMID 0 msgget获得消息队列ID之后 fork创建子进程 在子进程中能继承该消息队列ID而不必再一次msgget 3 6 2UNIX进程通信机制 共享存储允许多个进程访问存储区中相同的数据区 希望通信的进程通过一块具有唯一标识的共享存储连接在一起 进行通信的进程可以用与正常存储访问一样的方法访问这块共享存储 从而交换数据共享存储是物理存储器上一段可以由两个以上的进程共享的存储空间 共享存储段具有大小和物理存储地址 想要访问共享存储段的进程可以连接这段存储区到自己的地址空间中的合适地方 其他进程也一样 3 6 2UNIX进程通信机制 共享存储共享存储段一旦连接到进程的地址空间 进程就可以如同访问用malloc分配的存储空间一样来访问它们 如果一个进程更改该共享存储段的内容 其他进程将立即看到这种改变共享存储段提供了进程间共享数据的最快途径 一个进程简单地写数据至存储器 另一个进程从存储器读它们 这之间完全不需要read write之类的系统调用 3 6 2UNIX进程通信机制 创建或打开共享存储区 shmget 依据用户给出的整数值key 创建新区或打开现有区 返回一个共享存储区ID 连接共享存储区 shmat 连接共享存储区到本进程的地址空间 可以指定虚拟地址或由系统分配 返回共享存储区首地址 父进程已连接的共享存储区可被fork创建的子进程继承 拆除共享存储区连接 shmdt 拆除共享存储区与本进程地址空间的连接 共享存储区控制 shmctl 对共享存储区进行控制 如 共享存储区的删除需要显式调用shmctl shmid IPC RMID 0 3 6 2UNIX进程通信机制 套接字套接字上管道概念的一种扩充 同管道一样 套接字也解释为文件描述字 但套接字比管道更通用 它不仅支持本地无关联两个进程之间的点对点双向通信 而且支持跨网络的 允许于不同机器的进程之间的通信