计算机操作系统第四版第二章进程同步ppt课件.ppt

1 进程同步 进程的同步关系 进程的同步原则 信号量 2 程序 间 并发执行的特征 程序运行时独占资源 程序a N 3 print N N N 1 print N K 5 print K K K 1 print K 程序b 顺序执行ab 打印结果 3456 并发执行ab 1 2 3 4 5 6 7 8 1 2 3 4 5 6 7 8 打印结果 3546 资源非封闭 3 进程的同步 进程同步问题的提出进程异步推进可能造成混乱混乱可能导致不可再现进程同步目标 维持进程并发性以提高系统效率 进程执行异步 断续 资源的非封闭 共享 结果不可再现 进程同步 进程间相互合作 资源有效共享 结果可再现 4 进程的同步关系 2 3 1进程同步的基本概念 进程间的两种主要关系临界资源与临界区进程同步必须遵循的原则 5 进程间的两种主要关系进程间的关系与进程间的独立性进程间的关系是在进程间相对独立的前提下发展的独立获得资源独立调度 6 进程间的同步关系 一 正常行车 到站停车 开车 售票 开车门 关车门 司机 售票员 合作 合作 检查车况 维持秩序 7 获得打印数据 进程间的同步关系 二 打印进程1 打印进程2 打印 打印 互斥 获得打印数据 8 进程间的同步关系 三 计算进程 打印进程 计算结果送到Buffer 从Buffer中取数 Buffer 互斥 完成数据计算 打印 通知打印进程打印 通知计算进程送下一个数 合作 9 进程间的同步关系 相互合作 竞争资源 司机与售票员 多个打印者 计算者与打印者 其他例子 流水线生产仓库两个队篮球比赛 10 两种形式的制约关系 间接相互制约关系 源于资源共享 产生互斥问题直接相互制约关系 源于进程间合作 产生同步问题 正常行车 到站停车 开车 售票 开车门 关车门 司机 售票员 同步 同步 检查车况 维持秩序 12 同步实现初探 二 打印进程1 打印进程2 打印 打印 互斥 获得打印数据 获得打印数据 13 同步实现初探 三 计算进程 打印进程 计算结果送到Buffer 从Buffer中取数 Buffer 互斥 互斥 向打印进程发信号通知其从Buffer里取数 Buffer空 否 是 完成数据计算 打印 向计算进程发信号通知其向Buffer送数 Buffer空 否 是 合作 14 进程间的同步关系 进程同步时面临的两种主要关系 相互合作 竞争资源 司机与售票员 多个打印者 计算者与打印者 事件 设备等抽象为资源对进程间关系的处理变为对资源的访问方式 15 临界资源 临界资源临界资源一次只允许一个进程访问的资源资源状态为临界 0或1 最简单的资源 生产者 消费者的同步问题 生产者把产品生产出来 送入仓库 给消费者发信号 消费者得到信号后 到仓库取产品 取走产品后给生产者发信号 16 如果生产者和消费者共享的缓冲池容量为可以存放n件物品 n 1 由于缓冲器可存n件物品 因此 必须指出缓冲器中什么位置已有物品可供消费 什么位置尚无物品可供生产者存放物品 可以用输入指针in和输出指针out分别指示生产者往缓冲器存物品和消费者从缓冲器取物品的相对位置 它们的初值为0 生产者和消费者按位置的顺序去存物品和取物品 缓冲池被循环使用 每当生产进程生产并投放一个产品后 输入指针加1 由于缓冲池循环使用 可表示为 in in 1 modn 每当消费者进程取走一个产品后 输出指针加1 由于缓冲池循环使用 可表示为 out out 1 modn 17 当 in 1 modn out时 表示缓冲池满 当in out时 表示缓冲池空 整型变量counter表示缓冲池中产品的个数 初值为0 no op是一条空操作指令 whileconditiondono op语句表示重复测试条件 condicition 直至条件为false 假 局部变量nextp 生产者用于暂时存放刚生产出的产品 局部变量nextc 消费者暂时存放要消费的产品 18 Varn integer typeitem varbuffer array 0 1 n 1 ofitemin out 0 1 n 1 counter 0 1 n producer repeat produceaniteminnextp whilecounter ndono op buffer in nextp in in 1 modn counter counter 1 untilfalse consumer repeatwhilecounter 0dono op nextc buffer out out out 1 modn counter counter 1 consumertheiteminnextc untilfalse 19 上述两个操作用机器语言实现时 可用下面的形式描述 register1 counter register1 register1 1 counter register1 register2 counter register2 register2 1 counter register2 各进程如何互斥使用临界资源 20 临界区 临界区每个进程中用于访问临界资源的代码 同类临界区 同类资源的临界区 进入区 在临界区前加上一段用于检查的代码 退出区 在临界区后加上一段用于恢复临界区未被访问的标志的代码 剩余区 除进入区 临界区及退出区之外的其它部分的代码 21 repeatentrysectioncriticalsection exitsectionremaindersection untilfalse 22 临界区 进入区 临界区 退出区 进入区 临界区 退出区 阻塞等待资源释放 改变资源状态 释放资源唤醒等待进程 进程1 进程2 23 同步四原则 同步机制应遵循的原则 十六字原则 空闲让进 忙则等待 有限等待 让权等待 24 同步原则 进程同步应遵循的原则空闲让进当资源空闲时 应当允许访问资源的进程进入临界区忙则等待当资源被占用时 应使申请访问该资源的进程等待 等待使用者归还资源 两个基本原则 必须遵循 25 同步原则 进程同步应遵循的原则让权等待在进程等待资源时 从执行态转为阻塞态 应当让出CPU的使用权 系统将把CPU分配给其它进程使用 以提高系统效率 防止 忙等 有限等待系统应保证等待的进程能在有限的时间内获得资源 继续执行 以防止无限等待浪费该进程已占用的资源 防止 死等 26 锁机制 临界资源锁机制例 商场的试衣间是互斥资源是临界资源是共享资源每个顾客必须遵循以下过程使用试衣间 靠锁实现资源的共享管理 观察锁状态 关锁 使用试衣间 开锁 27 锁机制 临界资源锁机制 锁 锁变量L 每个进程必须按照以下过程操作资源 L 1关闭状态 资源忙 L 0打开状态 资源空闲 抽象 L 1 临界区 L 0 28 锁机制实现 一种简单的锁操作实现 voidlock L check if L 1 gotocheck elseL 1 voidunlock L L 0 29 锁机制实现 check if L 1 gotocheck elseL 1 临界区 L 进程1 进程2 unlock L check if L 1 gotocheck elseL 1 临界区 unlock L 0 0 0 30 锁操作模型 锁操作的一般模型 Pi lock L C i unlock L Pj lock L C j unlock L C i Pi的临界区 Pi 进程i 31 出了问题的锁 check if L 1 gotocheck elseL 1 临界区 unlock L check if L 1 gotocheck elseL 1 临界区 unlock L 出现问题的锁 进程1 进程2 L 0 尚未执行 问题出在 判断状态后改变状态前被打断 32 锁机制实现 关锁操作不可被打断用原语实现关锁操作关锁操作在一个指令周期内完成 软件方法 硬件方法 锁操作的特点 实现了进程互斥访问临界资源 不遵循让权等待原则 忙等 33 信号量机制 由Dijkstra提出的一种解决进程的同步与互斥的工具 信号量 用于表示资源数目或请求使用某一资源的进程个数的整型量 1 整型信号量S是与临界区内所使用的共享资源有关的信号量 仅能通过两个标准的原子操作wait s 和signal s 来访问 两个操作一直被分别称为P V操作 信号量机制 信号量是比锁更高级的资源抽象方式 wait S whileS 0dono opS S 1 signal S S S 1 34 经典信号量 2 经典信号量的P V操作资源的申请与释放 原语 信号量 S 忙等 35 P原语操作和V原语操作 P原语操作的主要动作S 1如果S 1以后仍大于等于零 则进程继续进行如果S 1以后小于零 则将该进程阻塞以后插入阻塞队列 然后转进程调度V原语操作的主要动作S 1如果相加后结果大于零 则继续进行相加后结果小于等于零 则从该信号的等待队列中唤醒一个等待进程 然后返回原进程继续执行或者转进程调度 36 37 P操作P S S if S 0 继续执行 else阻塞并进入等待队列 V操作V S S S 1 if S 0 继续运行 else唤醒等待队列中的一个进程 并继续运行 信号量 PV操作 38 记录型信号量 2 记录型信号量引入进程阻塞机制 多个进程等待访问同一临界资源的情况 在信号量里增加对阻塞进程的纪录 增加一个进程链表L typeSemaphore recordvalue integer L listofprocess end 资源个数 阻塞进程 PCB 队列 39 记录型信号量的P V操作 P s s value s value 1 s value 0 本进程获得一个资源 临界区 资源访问区 本进程进入s list队列 进入阻塞状态 N Y V s s value s value 1 s value 0 将s list中第一个进程唤醒 N Y 40 P s 和V s 操作原语 voidP s structsemaphores s value s value 1 if s value 0 block s p voidv s structsemaphores s value s value 1 if s value 0 wakeup s p 41 记录型信号量机制特点 进程对资源访问的过程 原语保证p v 操作都是原语二者必须成对出现 记录型信号量特点 P s 进入临界区 V s s为0时进程会进入阻塞状态 42 3 AND型信号量 只需了解 引入原因 一个进程需要先获得两个或更多的资源后 方能执行其任务 ProcessA ProcessB p Dmutex p Emutex p Emutex p Dmutex ProcessA p Dmutex 于是 mutex Process p mutex 于是 mutex ProcessA p mutex 于是 mutex 阻塞Process p mutex 于是 mutex 阻塞 43 P1 S1 P1 S2 P2 S2 P2 S1 进程1 进程2 系统推进过程为 进程2阻塞 进程1阻塞 S1 S2 进程1和进程2都无法继续推进出现死锁 V S2 V S1 V S1 V S2 44 基本思想将对多个信号量的逐个申请改为一次 用一个原子操作完成进程要么一次获得所有的资源 要么一个也申请不到不会存在互相等待的局面 SP S1 S2 S3 Sn 45 信号量集 了解 引入原因 在记录型信号量中每次对 仅能施以加 或减 操作 即每次只能获得或释放一个单位的临界资源 一次需要 个某类临界资源时 资源数量低于某一下限值时 便不予分配可对 信号量机制加以扩充 形成一般化的 信号量集 机制 46 公用与私用信号量 公用信号量 私用信号量 一组进程共享 都可进行P V操作 用于进程间资源的竞争 拥有信号量的进程只对信号量进行P操作 V操作由其他进程进行 用于进程间的合作 P s V s 访问资源 P s V s 访问资源 进程1 进程2 P s V s 后继进程 前驱进程 47 信号量的应用 利用信号量实现进程互斥 P s V s 临界区 P s V s 临界区 临界资源 进程 进程 原理 为临界资源设置一互斥信号量 初始值为 将每个进程的临界区CS置于P S 和V S 操作之间即可 48 例1 n个并发进程共用一个公用变量Q 写出信号量实现n个进程互斥时的程序描述 并说明信号量的取值范围 49 答案 varQ semaphore 1 Beginparbeginprocess1 beginrepeatp Q criticalsectionv Q remaindersectionuntilfalse endprocess2 begin 50 process2 beginrepeatp Q criticalsectionv Q remaindersectionuntilfalse end processn begin endParendend 51 2 利用信号量实现前驱关系设有 个并发执行的进程 P1 s1 P2 s2为了实现前驱关系S1S2 可使他们共享一个公用信号量 初值为 P1 S1 V s P2 P s S2 52 S1 S2 S3 S4 S5 S6 Vara b c d e f g semaphore 0 0 0 0 0 0 0 beginparbeginbeginS1 v a v b end beginp a S2 v c v d endbeginp b S3 v e endbeginp c S4 v f endbeginp d S5 v g endbeginp e p f p g S6 endparendend a b e d c f g 53 3 利用信号量实现进程同步 P s1 V s2 临界区 P s2 V s1 临界区 进程 进程B 54 分析进程间的制约关系 确定信号量的种类 从而明确设置信号量 信号量的初始值与相应资源有关 信号量的P V操作要 成对 出现 但分别在不同的进程代码中 55 生产者 消费者的同步问题 生产者把产品生产出来 送入仓库 给消费者发信号 消费者得到信号后 到仓库取产品 取走产品后给生产者发信号 1 用empty表示是否可以把物品存入缓冲器 由于缓冲器中只能放一件物品 系统初始化时应允许放入物品 故empty的初值应为1 2 用full表示缓冲器中是否存有物品 显然 系统初始化时缓冲器中应该无物品 故full的初值应为0 56 生产者和消费者并发执行时 用PV操作实现同步机制如下 Buffer integer empty full integer empty 1 full 0 cobegin ProcedureproducerBeginL1 produceaproduct P empty Buffer product V full GotoL1 End ProcedureconsumerBeginL2 P full takeaproductfrombuffer V empty consume End Coend 57 例1 get copy put等3个进程共用两个缓冲区s t 其大小为每次存放一个记录 get进程负责不断地把输入记录送入缓冲区s中 copy进程负责从缓冲区s中取出记录复制到缓冲区t中 而put进程负责把记录从缓冲区t中取出打印 试用P V操作实现这3个进程间的同步 并写出程序描述 S t get copy put 58 答案 Varsempty sfull tempty tfull semaphore 1 0 1 0 Beginparbeginget beginrepeat读入信息 p sempty 放入缓冲区S v sfull untilfalse end 59 copy beginrepeatp sfull 从缓冲区S中取出记录 v sempty 加工 p tempty 放入缓冲区t v tfull untilfalse end 60 put beginrepeatp tfull 从缓冲区t中取出记录 v tempty 打印记录 untilfalse endparendend 61 经典进程同步问题 经典进程同步问题生产者 消费者问题和尚打水问题哲学家进餐问题 62 生产者消费者问题 生产者 消费者问题问题描述 一组生产者向一组消费者提供产品 它们共享一个缓冲池 P1P2Pn C1C2Cn In指示下一个可投放产品的缓冲区 Out指示下一个可从中获取产品的缓冲区 63 如果生产者和消费者共享的缓冲池容量为可以存放n件物品 n 1 由于缓冲器可存n件物品 因此 必须指出缓冲器中什么位置已有物品可供消费 什么位置尚无物品可供生产者存放物品 可以用输入指针in和输出指针out分别指示生产者往缓冲器存物品和消费者从缓冲器取物品的相对位置 它们的初值为0 生产者和消费者按位置的顺序去存物品和取物品 缓冲池被循环使用 每当生产进程生产并投放一个产品后 输入指针加1 由于缓冲池循环使用 可表示为 in in 1 modn 每当消费者进程取走一个产品后 输出指针加1 由于缓冲池循环使用 可表示为 out out 1 modn 64 当 in 1 modn out时 表示缓冲池满 当in out时 表示缓冲池空 局部变量nextp 生产者用于暂时存放刚生产出的产品 局部变量nextc 消费者暂时存放要消费的产品 65 生产者消费者问题 生产者生产的产品放入缓冲池内 消费者从缓冲池内取走产品消费 消费者消费后的空白缓冲区供生产者使用 规则 有空的buffer时生产者便可将产品送入缓冲池 有满的buffer时消费者可从中取走产品 消费者与生产者互斥地访问缓冲区 66 生产者消费者算法分析 算法分析两类进程 生产者进程和消费者进程 1 进程间的关系生产者生产产品后消费者消费消费者消费后的空白缓冲块由生产者存放产品两个进程在使用缓冲区时的关系 合作关系 互斥关系 67 生产者消费者算法分析 信号量full 缓冲池中满缓冲区的数量empty 缓冲池中空缓冲区的数量mutex 实现各进程对缓冲池的互斥使用 68 利用记录型信号量实现 Varmutex empty full semaphore 1 n 0 buffer array 0 n 1 ofitem in out integer 0 0 producer beginrepeatproduceanitemnextp P empty P mutex Buffer in nextp In in 1 modn V mutex V full Untilfalse end consumer beginrepeatP full P mutex nextc buffer out out out 1 modn V mutex V empty consumertheiteminnextc Untilfalse end 69 P操作的顺序是很重要的 如果把生产者和消费者进程中的两个P操作交换顺序 则会导致错误 而V操作的顺序却是无关紧要的 一般来说 用于同步的信号量上的P操作在前执行 而用于互斥的信号量上的P操作在后执行 70 利用AND型信号量实现 Producer produceanitemnextp P empty mutex Buffer in nextp In in 1 modn V mutex full consumer P full mutex nextc buffer out out out 1 modn V mutex empty Consumertheiteminnextc 用P empty mutex 代替p empty 和p mutex 71 生产者消费者算法小结 小结 在分析进程同步问题中 逐个分析进程间的关系是关键不管多复杂的关系 总能归结为两种基本关系 竞争与合作 总是这两种关系的组合不管公用还是私用 信号量的使用必须成对出现 72 和尚打水问题某寺庙有小 老和尚若干 有一水缸 由小和尚提水入缸供老和尚饮用 水缸可以容纳10桶水 水取自同一井水 水井狭窄 每次只能容一个桶取水 水桶总数为3个 每次入 出水缸仅一桶 且不可同时进行 试给出有关取水 入水的算法描述 73 Varmutex1 mutex2 empty full count semaphore mutex1 1 mutex2 1 empty 10 full 0 count 3 process小和尚 begin repeatP empty P count P mutex1 从井中取水 V mutex1 P mutex2 送水入水缸 V mutex2 V count V full untilfalse end process老和尚 begin repeatP full P count P mutex2 从缸中取水 V mutex2 V empty V count untilfalse end 74 例2 某招待所有100个床位 住宿者住入要先登记 在登记表上填写姓名及床位号 离去时要撤消登记 在登记表上删去姓名和床位号 请用P V操作给出登记及撤消登记进程的算法描述 75 Varempty mutex semaphore 100 1 Beginparbegin住宿 beginP empty P mutex 登记住宿 V mutex end 撤消 beginP mutex 撤消登记 V mutex V empty end parend 76 读者写者问题 读者 写者问题 ReaderandWriter 问题描述一个数据纪录 有多个进程进行读操作 另一些进程进行修改操作 Reader Writer 读写策略允许多个进程同时进行读操作不允许多于一个进程进行写操作不允许读写操作同时进行 读不互斥 写互斥 读写互斥 77 读者写者问题分析 读者 写者 读操作 写操作 p mutex v mutex p mutex v mutex 写者之间互斥 读者与写者之间互斥 读者之间 互斥 78 哲学家问题 哲学家进餐问题问题描述五位哲学家围桌而坐哲学家在思考问题时不需要任何资源 思考完问题后进入进餐态 每人必须获得左右两支筷子才能进餐 思考 思考 思考 思考 思考 准备进餐 进餐 准备进餐 进餐 79 哲学家问题分析 死锁 思考 思考 思考 思考 思考 准备进餐 准备进餐 准备进餐 准备进餐 准备进餐 思考 p left stick p right stick v right stick v left stick eat 80 1 在多进程的系统中 为了保证公共变量的完整性 各进程应互斥进入临界区 所谓临界区是指 A 一个缓冲区B 一段数据区C 同步机制D 一段程序2 一个进程是 A 由协处理机执行的一个程序B 一个独立的程序 数据集C PCB结构与程序和数据的组合D 一个独立的程序3 设有5个进程共享一个互斥段 如果最多允许有3个进程同时进入互斥段 则所采用的互斥信号量的初值应是 A 5B 3C 1D 04 N个进程共享某一临界资源 则互斥信号量的取值范围为 A 0 1B 1 0C 1 N 1 D 0 N 1 D C B C 81 5 对两个并发进程 其互斥信号量为mutex 若mutex 0 则表明 A 没有进程进入临界区B 有一个进程进入临界区C 一个进程进入临界区而另一个进程正处于等待进入临界区状态D 有两个进程进入临界区6 若有3个进程共享一个互斥段 每次最多允许两个进程进入互斥段 则信号量的变化范围是 A 2 1 0 1B 3 2 1 0C 2 1 0 1 2D 1 0 1 27 对于给定的信号量s 等待操作P s 定义为 ifs 0then eles挂起调用的进程 A s 0B s s 1C s s 1D s 1 B A C 82 8 并发进程之间 A 彼此无关B 必须同步C 必须互斥D 可能需要同步或互斥9 当 时 进程从执行状态转变为就绪状态 A