操作系统进程同步与通信PPT课件.ppt

第二章进程 进程的同步与通信 第二部分进程同步与进程通信1 进程同步的基本概念2 信号量机制3 经典进程同步问题4 管程机制5 进程通信 1 第二章进程 进程的同步与通信 2 4进程同步的基本概念在多道程序环境下 进程之间可能存在两种关系 1 资源共享2 相互合作进程同步的任务就是 1 在资源共享的情况下 保证诸进程以互斥的方式访问临界资源 必须以互斥方式访问的共享资源 2 在相互合作的关系中 进程同步的主要任务是保证相互合作的诸进程在执行次序上协调 有些教材把这种功能称做 协调 相互合作的进程可能同时存在资源共享的关系 为什么需要进程同步机制 2 第二章进程 进程的同步与通信 2 4进程同步的基本概念2 4 1临界资源为了说明什么是临界资源 我们先看一个例子 回忆第二章P1 P2两个进程并发执行的例子 counter是全局变量 为什么需要进程同步机制 P1 counter counter 1 P2 counter counter 1 3 临界资源 counter counter 1的执行序列为 register1 counterregister1 register1 1counter register1 counter counter 1的执行序列为 register2 counterregister2 register2 1counter register2 为什么需要进程同步机制 4 临界资源 若当前counter 0当P1和P2按下列顺序执行时 会发生counter计数错 register1 counterregister1 0register1 register1 1register1 1register2 counterregister2 0register2 register2 1register2 1counter register1counter 1counter register2counter 1执行结果 counter 1 正确结果应该是 counter 2 如果p1和p2以互斥的方式去访问counter 错误就不会出现了 为什么需要进程同步机制 5 第二章进程 进程的同步与通信 2 4进程同步的基本概念2 4 2临界区一 临界区的定义和进入1 临界区 每个进程中访问临界资源的那段代码称为临界区 2 进入区 检查是否可以进入临界区并对临界区 加锁 的代码 3 退出区 释放临界区访问权的代码 如何实现进程同步 6 第二章进程 进程的同步与通信 2 4进程同步的基本概念2 4 2临界区二 同步机制应遵循的准则控制临界资源访问权的控制算法在设计上应遵循的原则 1 空闲让进2 忙则等待3 有限等待4 让权等待 如何实现进程同步 7 第二章进程 进程的同步与通信 2 5信号量机制在这种机制中 用某种类型的变量 即信号量的取值来表示资源的使用状况 或某种事件是否发生 以此为基础实现进程的同步 我们将介绍整型信号量机制 记录型信号量机制 信号量集机制 如何实现进程同步 8 第二章进程 进程的同步与通信 2 5信号量机制2 5 1整型信号量机制一 整型信号量整型信号量是表示共享资源状态且只能由特殊的原子操作改变的整型量 1 想法 定义一个整型变量 用整型变量值来标记资源使用情况 如整型量 0 说明有可用资源 整型量 0说明资源忙 进程必须等待 对于一次只允许一个进程访问的CS 可定义一个用于互斥的整型信号量 并被初始化为1 如何实现进程同步 9 第二章进程 进程的同步与通信 2 5信号量机制2 5 1整型信号量机制一 整型信号量2 整型信号量的wait和signal操作Wait s whiles 0dono op对CS的互斥访问 s s 1 Signal s s s 1实现对资源的释放注 wait s 和signal s 都是原子操作 见教材P41页 如何实现进程同步 10 第二章进程 进程的同步与通信 2 5信号量机制2 5 1整型信号量机制二 利用整型信号量实现互斥想法 为必须互斥访问的CS定义一个互斥信号量mutex 初始值为1 然后将CS放入wait mutex 和signal mutex 之间 当CS可访问时 wait mutex 才能正常结束使进程进入CS 如何实现进程同步 11 第二章进程 进程的同步与通信 2 5信号量机制2 5 1整型信号量机制 如何实现进程同步 12 第二章进程 进程的同步与通信 2 5信号量机制2 5 1整型信号量机制三 利用信号量来协调进程执行的顺序例1 P1 P2两个进程 要求P2必须在P1结束后执行 为此 设置一个信号量S 初始值为0 parbeginbeginP1 Signal s endbeginWait s P2 endparend 如何实现进程同步 13 第二章进程 进程的同步与通信 2 5信号量机制2 5 1整型信号量机制三 利用信号量来描述前趋关系例2 有P1 P2两个进程 S1 S2 S S6分别是P1 P2中的语句 我们要求它们的执行顺序如下图所示 如何实现进程同步 14 如何实现进程同步 15 第二章进程 进程的同步与通信 2 5信号量机制2 5 1整型信号量机制三 利用信号量来描述前趋关系 例2vara b c d e f g semaphore 0 0 0 0 0 0 beginprabeginbegins1 signal a signal b end beginwait a s2 signal c signal d end beginwait b s3 signal g end beginwait c s4 signal e end beginwait d s5 signal f end beginwait e wait f wait g s6 end parendend 如何实现进程同步 16 小结 1 整型信号量的值只能由wait和signal操作改变2 wait和signal操作都是原子操作 既在这两个操作中对信号量的访问是不能被中断的 为什么 3 原子操作可以通过关中断来实现 为什么对临界资源的访问不简单地通过关中断来实现 4 整型信号量机制的实例 Linux中的自旋锁SpinLock5 不同的资源对应不同的信号量 并不是系统中所有的资源用同一个信号量表示 6 用整型信号量实现互斥时 wait和signal操作分别作为进入区和退出区代码使用 17 第二章进程 进程的同步与通信 2 5信号量机制2 5 2记录型信号量机制一 记录型信号量的数据类型Typesemaphore recordValue integer资源数量L listofprocess阻塞队列end 如何实现进程同步 18 第二章进程 进程的同步与通信 2 5信号量机制2 5 2记录型信号量机制二 使用记录型信号量的wait s 和signal s 操作 procedurewait s vars semaphorebegins value s value 1 ifs value 0thenblock s L end proceduresignal s vars semaphorebegins value s value 1 ifs value 0thenwakeup s L end 如何实现进程同步 19 第二章进程 进程的同步与通信 三 利用记录型信号量实现互斥vars semaphores value 1BeginRepeatwait s CriticalsectionSignal s RemaindersectionUntilfalse end 20 21 第二章进程 进程的同步与通信 2 5信号量机制2 5 2记录型信号量机制四 利用记录型信号量实现 协调 的应用举例 爸爸擀饼 妈妈烙饼 面板上只能容纳两张擀好的饼 只有当面板上有空时 爸爸才能把擀好的饼放在面板上 只有当面板上有饼时 妈妈才能从面板上取饼 试采用信号量机制实现爸爸与妈妈的同步 如何实现进程同步 22 爸爸 擀饼wait empty 放饼signal full 妈妈 wait full 取饼signal empty 烙饼 解 设置两个信号量varempty full semaphore 初始 empty value 2 full value 0 2 5 2记录型信号量机制 如何实现进程同步 23 第二章进程 进程的同步与通信 2 5信号量机制2 5 2记录型信号量机制五 对wait s 和signal s 的说明1 s value 0时 s value的值表示资源数量 s value 0时 s value 的值表示某资源的等待队列中进程的数量 2 每次的wait s 操作 意味着进程请求一个单位的资源 因此描述为s value s value 1 当s value 0时 表示资源已分配完毕 因而进程调用block原语 进行自我阻塞 放弃处理机 并插入到信号链表S L中 如何实现进程同步 24 第二章进程 进程的同步与通信 2 5信号量机制2 5 2记录型信号量机制五 对wait s 和signal s 的说明3 每次的signal s 操作 意味着进程释放一个资源 故s value s value 1操作表示资源数目加1 若加1后仍是S value 0 则表示在该信号链表中 仍有等待该资源的进程被阻塞 故还应该调用wakeup原语 将S L链表中的一个等待进程唤醒 4 如果S value的初值为1 表示只允许一个进程访问临界资源 此时的信号量转化为互斥信号量 5 wait down p proberen signal up v verhogen 如何实现进程同步 25 第二章进程 进程的同步与通信 2 5信号量机制2 5 2记录型信号量机制六 记录型信号量机制的优点不存在忙等 采取 让权等待 的策略 如何实现进程同步 26 include asm i386 semaphore h structsemaphore atomic tcount intsleepers wait queue head twait 27 第二章进程 进程的同步与通信 2 5信号量机制2 5 3信号量集机制问题的引入例 A B两个进程 都要求访问共享数据D和E 若设置两个用于互斥的信号量Dmutex和Emutex并令它们的初值为1 相应地两个进程要包含两个对Dmutex和Emutex的操作 即processA processB wait Dmutex wait Emutex wait Emutex wait Dmutex 如何实现进程同步 28 第二章进程 进程的同步与通信 2 5信号量机制2 5 3信号量集机制在这种互斥方式下 若进程A和B按下述次序交替执行wait操作会造成死锁 processA wait Dmutex 于是Dmutex 0 processB wait Emutex 于是Emutex 0 processA wait Emutex 于是Emutex 1 A阻塞processB waitDmutex 于是Dmutex 1 B阻塞 A等B释放E而被阻塞 B等A释放D而被阻塞 如何实现进程同步 29 第二章进程 进程的同步与通信 2 5信号量机制2 5 3信号量集机制一 AND型信号量机制AND型信号量集机制的目的在于解决进程共享多个临界资源的互斥问题 AND同步机制的基本思想是 将进程在整个运行过程中所需要的所有临界资源 一次性地全部分配给进程 待该进程使用完后再一起释放 只要还有一个资源不能分配给该进程 其它所有可能为之分配的资源 也不分配给它 如何实现进程同步 30 第二章进程 进程的同步与通信 2 5信号量机制2 5 3信号量集机制一 AND型信号量机制 实现 Swait s1 s2 sn ifs1 1and sn 1thenfori 1tondosi si 1endforelse把进程插入Si等待队列 并把程序记数器的值赋为swait的起始地址 endif Ssignal s1 s2 sn Fori 1tondoSi Si 1 将阻塞在Si队列中的进程唤醒 插入就绪队列endfor 如何实现进程同步 31 第二章进程 进程的同步与通信 2 6经典进程同步问题2 6 1生产者 消费者问题一 生产者 消费者问题的描述生产者进程生产消息 并将消息提供给消费者进程消费 为使生产者进程和消费者进程能并发执行 在它们之间设置了一个具有n个缓冲区的缓冲池 生产者进程可以将它所生产的消息放入一个缓冲区中 消费者进程可以从一个缓冲区中取得一个消息消费 任意两个进程必须以互斥的方式访问公共缓冲池 当缓冲池空时 消费者进程必须等待 当缓冲池装满消息时 生产者进程必须等待 如何实现进程同步 32 生产者 消费者问题的描述 Out in 装有消息的缓冲区 空缓冲区 33 第二章进程 进程的同步与通信 2 6经典进程同步问题2 6 1生产者 消费者问题二 需要解决的问题1 对缓冲池的互斥访问 2 对生产者进程 消费者进程的 协调 即 有产品时才能消费 无产品时 必须先生产后消费 有空间时才能生产 空间满时 必须先消费再生产 34 第二章进程 进程的同步与通信 2 6经典进程同步问题2 6 1生产者 消费者问题三 信号量的设置1 一个互斥信号量 mutex用于实现对公共缓冲池的互斥访问 初值为1 2 两个同步信号量 分别表示可用资源数 empty 表示空缓冲区数 初值为nfull 表示装有产品的缓冲区数 初值为0 一个缓冲区中放一个产品 35 第二章进程 进程的同步与通信 2 6经典进程同步问题2 6 1生产者 消费者问题四 实现 Producer beginrepeat produceaniteminnextp wait empty wait mutex buffer in nextp in in 1 modnsignal mutex signal full untilfalse Consumer beginrepeat wait full wait mutex nextc buffer out out out 1 modn signal mutex signal empty consumeiteminnextc untilfalse 36 2 6 1生产者 消费者问题 五 说明1 wait和signal操作成对出现2 wait操作的顺序不能颠倒3 对具有相互合作关系的进程 提供解决问题的模型 37 2 6 1生产者 消费者问题 练习 buffer1 buffer2 P1 P2 P3 38 第二章进程 进程的同步与通信 2 6经典进程同步问题2 6 2读者 写者问题一 问题描述允许多个进程同时读D 允许一个进程写D 写D时 不能有其它任何进程读或写D D是共享对象 39 第二章进程 进程的同步与通信 2 6经典进程同步问题2 6 2读者 写者问题二 利用记录型信号量解决读者 写者问题1 数据结构 1 全局量readcount用于对进入共享区的读进程计数 2 rmutex用于对多个进程共享的变量readcount的互斥访问 3 wmutex用于实现读 写互斥 40 第二章进程 进程的同步与通信 2 6经典进程同步问题2 6 2读者 写者问题二 利用记录型信号量解决读者 写者问题2 算法 writer begin wait wmutex wrintingoperation signal wmutex end 41 2 6 2读者 写者问题 reader begin wait rmutex ifreadcount 0thenwait wmutex readcount signal rmutex readingfile Wait rmutex readcount ifreadcount 0thensignal wmutex signal rmutex end End 42 第二章进程 进程的同步与通信 2 6经典进程同步问题2 6 3哲学家进餐问题一 问题描述 43 第二章进程 进程的同步与通信 2 6经典进程同步问题2 6 3哲学家进餐问题二 利用AND信号量机制解决哲学家进餐问题Varchopstick array 0 4 ofsemaphore 1 1 1 1 1 processirepeatthink swait chopstick i 1 mod5 chopstick i eat ssignal chopstick i 1 mod5 chopstick i Untilfalse 44 第二章进程 进程的同步与通信 2 7管程机制2 7 1管程的引入信号量机制的缺陷 每个访问临界资源的进程都必须自备同步操作wait s 和signal s 这就使大量的同步操作分散在各个进程中 这不仅给系统的管理带来麻烦 而且还会因同步操作的使用不当而导致系统出错 因此引入了 管程 的概念 45 第二章进程 进程的同步与通信 2 7管程机制2 7 2管程的基本概念一 管程的定义管程是描述共享资源的数据结构和在数据结构上的共享资源管理程序 typemoniter name monitervariabledeclarationsprocedureentryP1 begin end procedureentrypn begin end begininitializationcodeend 46 第二章进程 进程的同步与通信 2 7管程机制2 7 2管程的基本概念二 对管程的说明1 管程是可供程序员调用的软件包一个管程是一个由过程 变量及数据结构等组成的一个集合 它们组成一个特殊的模块或软件包 进程可以在任何需要的时候调用管程中的过程 但它们不能在管程外的过程中直接访问管程内的数据结构 47 第二章进程 进程的同步与通信 2 7管程机制2 7 2管程的基本概念二 对管程的说明2 每次只有一个进程调用管程执行任一时刻管程中只能有一个活跃进程 若多个进程同时调用一个管程中的过程 只有一个进程得以进入管程 继续运行 其它进程则被阻塞 48 第二章进程 进程的同步与通信 2 7管程机制2 7 2管程的基本概念二 对管程的说明3 管程是一种编程语言的构件管程是一种编程语言的构件 所以编译器知道它们很特殊 并可以采用与其他过程调用不同的方法来处理它们 典型的 当一个进程调用管程中的过程时 前几条指令将检查在管程中是否有其他的活跃进程 如果有 调用进程将挂起直到另一个进程离开管程 如果没有 则调用进程便进入管程 49 第二章进程 进程的同步与通信 2 7管程机制2 7 2管程的基本概念三 条件变量为了进行并发处理 管程必须包含同步工具 例如 假设一个进程调用了管程 并且当它在管程中时必须被挂起 直到满足某些条件 这就需要一种机制 使得该进程不仅被挂起而且能释放这个进程 以便某些别的进程可以进入 以后当条件满足并且管程再次可用时 需要恢复该进程并允许它在挂起点重新进入管程 管程通过使用条件变量提供同步的支持 这些条件变量包含在管程中 并且只有在管程中才能被访问 50 第二章进程 进程的同步与通信 2 7管程机制2 7 2管程的基本概念三 条件变量一个管程过程 可以用在某条件变量上执行wait操作 将调用的进程阻塞并进入该条件的阻塞队列 也可以用在条件变量上执行signal操作 唤醒在该条件上阻塞的进程 51 三 条件变量 Wait s 调用进程在条件s上挂起 管程现在可以被另一个进程使用 Signal s 恢复在wait之后为某些条件而挂起的进程的执行 如果有多个这样的进程 选择其中一个 如果没有这样的进程 什么也不做 注意 管程的wait signal操作与信号量不同 如果在管程中的一个进程发信号 但没有在这个条件变量上等待的任务 则这个信号丢失 52 第二章进程 进程的同步与通信 2 7管程机制2 7 3利用管程解决生产者 消费者问题 monitorP roducer C onsumer conditionfull empty integercount 缓冲池中的消息数procedureenter item beginifcount Nthenwait full enter item count count 1 signal empty 如果有因缓冲池空而被阻塞的消费者进程 则唤醒该进程end procedureremove item beginifcount 0thenwait empty remove item count count 1 signal full 如果有因缓冲池满而被阻塞的生产者进程 则唤醒该进程endcount 0 endmonitor 53 第二章进程 进程的同步与通信 2 7管程机制2 7 3利用管程解决生产者 消费者问题 Producer BeginrepeatproduceaniteminnextpPC enter item untilfalseend Consumer BeginrepeatPC remove item consumetheiteminnextc Untilfalse end 54 第二章进程 进程的同步与通信 2 7管程机制2 7 3利用管程解决哲学家用餐问题 Typedining philosophers monitorVarstate array 0 4 of thinking hungry eating Varself array 0 4 ofcondition Procedureentrypickup i 0 4 Beginstate i hungry Test i Ifstate i eatingthenself i wait End 55 2 7 3利用管程解决哲学家用餐问题 Procedureentryputdown i 0 4 Beginstate i thinking Test i 4mod5 Test i 1mod5 End 56 2 7 3利用管程解决哲学家用餐问题 Proceduretest k 0 4 BeginIfstate k 4mod5 eatingAndstate k hungryAndstate k 1mod5 eatingThenbeginstate k eatingself k signal EndEnd 57 2 7 3利用管程解决哲学家用餐问题 BeginFori 0to4Dostate i thinking end 58 2 7 3利用管程解决哲学家用餐问题 voidphilosopher inti while true think pickup i eat putdown i 59 第二章进程 进程的同步与通信 2 8进程通信进程通信是指进程之间的信息交换2 8 1进程通信的类型通信机制可分三大类一 共享存储器系统 基于共享数据结构的通信方式 基于共享存储区的通信方式 二 消息传递系统 以消息为单位交换信息 信息是具有一定格式的报文 直接通信方式间接通信方式 60 第二章进程 进程的同步与通信 2 8进程通信2 8 1进程通信的类型三 管道通信管道是指用于连接一个读进程和一个写进程以实现它们之间通信的共享文件 管道机制必须提供的三个功能 1 互斥2 同步3 确定通信对方是否存在 61 第二章进程 进程的同步与通信 2 8进程通信2 8 2直接通信和间接通信方式一 直接通信方式 是指发送进程利用OS所提供的发送命令 直接把消息发送给目标进程 1 发送原语send Receiver message 2 接收原语Receive Sender message 在有些情况下 接收消息的进程可接收多个进程发送此消息 接收原语中的发送者参数由发送者的通信过程返回 62 第二章进程 进程的同步与通信 2 8进程通信2 8 2直接通信和间接通信方式一 直接通信方式3 用直接通信原语解决生产者一消费者问题 repeat produceaniteminnextp send consumer nextp untilfalse repeatreceive producer nextc consumetheiteminnextc untilfalse 63 第二章进程 进程的同步与通信 2 8进程通信2 8 2直接通信和间接通信方式二 间接通信方式 进程间的通信需借助某种共享数据结构的实体 该实体用来暂存消息 1 信箱的创建和撤消进程可利用信箱创建原语来建立一个新信箱 创建者进程应该给出信箱的名字 信箱的属性 公有 私有 共享 对于共享信箱 要给出共享者的名字 当不需要信箱时 可用撤消原语来撤消信箱 64 第二章进程 进程的同步与通信 2 8进程通信2 8 2直接通信和间接通信方式二 间接通信方式2 消息的发送和接收原语 Send mailbox message 将message发送给指定的mailbox Receive mailbox message 从指定的mailbox 中接受消息 信箱 私用信箱 只允许拥有者读 别的进程只能写 公用信箱 所有有权用户既可读又可写 由系统创建 共享信箱 所有共享者可读可写 由进程创建 65 第二章进程 进程的同步与通信 2 8进程通信2 8 3消息传递系统中的几个问题一 通信链路1 显示建立链路隐式建立链路2 连接方法分 点一点连接多点连接 66 第二章进程 进程的同步与通信 2 8进程通信2 8 3消息传递系统中的几个问题一 通信链路3 按通信方式 单向通信链路双向通信链路4 按通信链路的容量不同 无容量通信链路有容量通信链路 67 第二章进程 进程的同步与通信 2 8进程通信2 8 3消息传递系统中的几个问题二 消息的格式1 定长格式 系统开销小 使用不方便 2 不定长格式 系统开销大 使用灵活 68 第二章进程 进程的同步与通信 2 8进程通信2 8 3消息传递系统中的几个问题三 进程同步方式1 发送进程 接收进程都阻塞 2 发送进程不阻塞 接收进程阻塞 3 发送和接收进程都不阻塞 教材p69 69 第二章进程 进程的同步与通信 2 8进程通信2 8 4消息缓冲队列通信机制广泛应用于本地进程间的通信 在这种机制中 发送原语先申请一个空白的消息缓冲区 将待发消息的长度 发送者 消息正文 下一条消息的指针等内容复制到该空白区中 然后将它挂入消息缓冲队列 接受者从自己的消息缓冲队列中取下队首的消息 并将其复制到指定的消息接收区 70 第二章进程 进程的同步与通信 2 8进程通信2 8 4消息缓冲队列通信机制一 消息缓冲队列通信机制中的数据结构1 typemessagebuffer recordsender发送进程的标识符size消息长度text消息正文next指向下一消息缓冲区的指针 end 71 第二章进程 进程的同步与通信 2 8进程通信2 8 4消息缓冲队列通信机制2 PCB中有关通信的数据项Typeprocesscontrolblock Record mq 消息队列队首指针mutex 消息队列互斥信号量sm 消息队列资源信号量 end 72 第二章进程 进程的同步与通信 2 8进程通信2 8 4消息缓冲队列通信机制二 发送原语 教材p70图 发送进程在利用发送原语发送消息之前 应先在自己的内存空间设置一发送区a 把待发送的消息正文 发送进程标识符 消息长度等信息填入其中 然后调用发送原语 把消息发送给目标 接