网站怎么做浏览量才会多,百度竞价开户多少钱,wordpress调用文章上级栏目名字,营销网站建设的公司操作系统备考学习 day7 第二章 进程与线程2.3 同步与互斥2.3.4 信号量 用信号量实现进程互斥、同步、前驱关系信号量机制实现进程互斥信号量机制实现进程同步信号量机制实现前驱关系 2.3.5 经典同步问题生产者-消费者问题多生产者和多消费者模型抽烟者问题读者-写者问题哲学家进… 操作系统备考学习 day7 第二章 进程与线程2.3 同步与互斥2.3.4 信号量 用信号量实现进程互斥、同步、前驱关系信号量机制实现进程互斥信号量机制实现进程同步信号量机制实现前驱关系 2.3.5 经典同步问题生产者-消费者问题多生产者和多消费者模型抽烟者问题读者-写者问题哲学家进餐问题 2.3.5 管程 第二章 进程与线程
2.3 同步与互斥
2.3.4 信号量 用信号量实现进程互斥、同步、前驱关系 信号量机制实现进程互斥
分析并发进程的关键活动划定临界区如对临界资源打印机的访问就应该放在临界区设置互斥信号量mutex初值为1在进入区P–申请资源在退出区V–释放资源 注意对于不同的临界资源需要设置不同的互斥信号量 P、V操作必须成对出现。缺少P就不能保证临界资源的互斥访问。缺少V会导致资源永不被释放等待进程永不被唤醒
信号量机制实现进程同步
进程同步要让各并发进程按要求有序地推进
用信号量实现进程同步
分析什么地方需要实现“同步关系”即必须保证“一前一后”执行的两个操作设置同步信号量s初始为0在“前操作”之后执行V(S)在“后操作”之前执行P(S)技巧口诀前V后P 信号量机制实现前驱关系
进程P1中有句代码S1P2中有句代码S2P3中有句代码S3。。。。这些代码要求按如下前驱图所示的顺序来执行
其实每一对前驱关系都是一个进程同步问题需要保证一前一后的操作 因此
要为每一对前驱关系各设置一个同步信号量在“前操作”之后对相应的同步信号量执行V操作在“后操作”之前对相应的同步信号量执行P操作 2.3.5 经典同步问题
生产者-消费者问题
问题描述 系统中有一组生产者进程和一组消费者进程生产者进程每次生产一个产品放入缓冲区消费者进程每次从缓冲区取出一个产品并使用注这里的“产品”理解为某种数据 生产者、消费这共享一个初始为空、大小为n的缓冲区 只有缓冲区没满时生产者才能把产品放入缓冲区否则必须等待 缓冲区没满-》生产者生产 只有缓冲区不空时消费者才能从中取出产品否则必须等待 缓冲区没空-》消费者消费 缓冲区是临界资源各进程必须互斥地访问 互斥关系 缓冲区满时生产者必须等待。 缓冲区空时消费者必须等待。
PV操作题目分析步骤
关系分析。找出题目中描述的各个进程分析它们之间的同步、互斥关系整理思路。根据各进程的操作流程确定P、V操作的大致顺序设置信号量。并根据题目条件确定信号量初值。互斥信号量初值一般为1同步信号量的初始值要看对应资源的初始值是多少 实现量进程的同步关系是在其中一个进程执行P另一进程中执行V
如果改变相邻P、V操作的顺序 例如mutex的p操作在前且此时缓冲区内已经放满产品则empty0fulln。按①②③的顺序执行 可能会引起生产者等待消费者释放空闲缓冲区而消费者又等待生产者释放临界区的情况生产者和消费者循环等待被对方唤醒出现“死锁”。 同样的若缓冲区中没有产品即full0emptyn。按③④①的顺序执行就会发生死锁。 因此实现互斥的P操作一定要在实现同步的P操作之后。V操作不会导致进程阻塞因此两个V操作顺序可以交换。 易错点实现互斥和实现同步的两个P操作的先后顺序死锁问题
多生产者和多消费者模型
问题描述桌子上有一只盘子每次只能向其中放入一个水果。爸爸转向盘子中放苹果妈妈专向盘子中放橘子儿子专等着吃盘子中的橘子女儿专等着吃盘子中的苹果。只有盘子空时爸爸或妈妈才可向盘子中放一个水果。仅当盘子中有自己需要的水果时儿子或女儿可以从盘子中取出水果。
关系分析 互斥关系对缓冲区的访问要互斥地进行
同步关系一前一后
父亲将苹果放入盘子后女儿才能取苹果母亲将橘子放入盘子后儿子才能取橘子只有盘子为空时父亲或母亲才能放入水果
“盘子为空”这个事件可以由儿子或女儿触发事件发生后才允许父亲或母亲放水果 总结在生产者-消费者问题中如果缓冲区大小为1那么有可能不需要设置互斥信号量就可以实现互斥访问缓冲区的功能。当然这不是绝对的要具体问题具体分析
建议需要注意的是实现互斥的P操作一定要在实现同步的P操作之后否则可能引起“死锁” 解决“多生产者-多消费者问题”的关键在于理清复杂的同步关系
抽烟者问题 关系分析 这里使用的是用整形变量i来轮流来实现这个“轮流”过程 题目改为“每次随机地让一个吸烟者吸烟”则可以使用random函数来实现这个代码
若一个生产者要生产多种产品或者说会引发多种前驱事件那么各个V操作应该放在各自对应的“事件”发生之后的位置
读者-写者问题
问题描述 有读者和写者两组并发进程共享一个文件当两个或两个以上的读进程同时访问共享数据时不会产生副作用但若某个写进程和其他进程读进程或写进程同时访问共享数据时则可能导致数据不一致的错误。 因此要求
允许多个读者可以同时对文件执行读操作只允许一个写者往文件中写信息任一写者在完成写操作之前不允许其他读者或写者工作写者执行写操作前应让已有的读者和写者全部退出
读者进程与消费者进程不同读者进程在读数据后并不会将数据清空并不会改变数据。因此多个读者可同时访问共享数据
读进程与写进程同时共享数据可能导致读出的数据不一致的问题 两个写进程同时共享数据可能导致数据错误覆盖的问题 关系分析 两类进程写进程、读进程 互斥关系写进程-写进程、写进程-读进程。读进程与读进程不存在互斥问题 问题只要有读进程还在读写进程就要一直阻塞等待可能“饿死”。因此这种算法中读进程是优先的
问题解决 结论在这种算法中连续进入的多个读者可以同时读文件写者和其他进程不能同时访问文件写者不会饥饿但也并不是真正的“写优先”而是相对公平的先来先服务原则 所以也称“读写公平法”
读者-写者问题为我们解决复杂的互斥问题提供了一个参考思路 其核心思想在于设置了一个计数器count用来记录当前正在访问共享文件的读进程数。我们可以用count的值来判断当前进入的进程是否是第一个/最后一个读进程从而做出不同的处理
哲学家进餐问题
问题描述 关系分析 系统中有5个哲学家进程5位哲学家与左邻右舍对其中间筷子的访问是互斥关系
思路整理 这个问题中只有互斥关系但与之前遇到的问题不同的事每个哲学家进程需要同时持有两个临界资源才能开始吃饭。如何避免临界资源分配不当造成的死锁现象是哲学家问题的精髓
信号量设置 定义互斥信号量数组chopsticks[5]{1,1,1,1,1}用于实现对5个筷子的互斥访问。并对哲学家按0~4编号哲学家i左边的筷子编号为i右边的筷子编号为(i1)%5
方法一至多只允许n-1位哲学家同时去拿左筷子最终能保证至少有一位哲学家能进餐并在用完后释放两只筷子供他人使用 方法二仅当哲学家的左右手筷子都拿起来时才允许进餐 解法1利用AND型信号量机制实现 多个临界资源要么全部分配要么一个都不分配因此不会出现死锁的情况 解法2利用信号量的保护机制实现 通过互斥信号量mutex对eat()之前取左侧和右侧筷子的操作进行保护可以防止死锁的出现 方法三规定奇数号哲学家先拿左筷子再拿右筷子而偶数号哲学家相反
哲学家进餐问题的关键在于解决进餐死锁问题 这些进程之间只存在互斥关系但是与之前接触到的互斥关系不同的是每个进程都需要同时持有两个临界资源因此就有“死锁”问题的隐患
2.3.5 管程
管程的定义和基本特征
管程是一种特殊的软件模块有这些部分组成
局部于管程的共享数据结构说明对该数据结构进行操作的一组过程对局部于管程的共享数据设置初始值的语句管程有一个名字
可以把管程理解成一个类过程可以理解为函数
管程的基本特征
局部于管程的数据只能被局部于管程的过程所访问一个进程只有通过调用管程内的过程才能进入管程访问共享数据每次仅允许一个进程在管程内执行某个内部过程 由编译器负责实现各进程互斥地进入管程中的过程 管程中设置条件变量和等待/唤醒操作以解决同步问题
拓展用管程解决生产者消费者问题 引入管程的目的无非就是要更方便地实现进程互斥和互斥
需要在管程中定义共享数据如生产者消费者问题的缓冲区需要在管程中定义用于访问这些共享数据的“入口”–其实就是一些函数如生产者消费者问题中可以定义一个函数用于将产品放入缓冲区再定义一个函数用于从缓冲区取出产品只有通过这些特定的“入口”才能访问共享数据管程中有很多“入口”但是每次只能开放其中一个“入口”并且只能让一个进程或线程进入如生产者消费者问题中各进程需要互斥地访问共享缓冲区。管程的这种特性即可保证一个时间段内最多只会有一个进程在访问缓冲区。注意这种互斥特性是由编译器负责实现的程序员不用关心可在管程中设置条件变量及等待/唤醒操作以解决同步问题。可以让一个进程或线程在条件变量上等待此时该进程应先释放管程的使用权也就是让出“入口”可以通过唤醒操作将等待在条件变量上的进程或线程唤醒。
