本文共 2747 字,大约阅读时间需要 9 分钟。
6-1进程同步背景
1.生产者消费者问题
采用共享内存解决生产中消费者问题时,N个缓冲区最多只能用N-1个,如何解决?
2.共享数据的一致性
①对共享数据的并发访问可能导致数据的不一致性
②要保持数据的一致性,需要一种保证并发进程的正确执行顺序的机制。
③竞争条件 race condition
若干并发的进程(线程)都可以访问和操纵同一共享数据,从而执行结果取决于并发进程对这个数据的访问次序。为保证数据的一致性,需有同步机制来保证多个进程对共享数据的互斥访问。
3.进程间的制约
①进程类型:协作进程,彼此影响;独立进程,互斥。
②进程间资源的访问冲突:共享变量的修改冲突;操作顺序冲突。
③进程间的制约关系:
间接制约:资源互斥,进程竞争,进程的互斥
直接制约:进行协作,进程的同步
4.进程间的交互关系
互斥:多个进程不能同时使用同一个资源
同步:进程之间协作
死锁:多个进程互不相让,都得不到足够资源
6-2 临界区
1.临界区的访问过程
①对于临界资源,多个进程必须互斥对它的进行访问。
②临界区(critical section):进程中访问临界资源的一段代码。
③实现进程对临界资源的互斥访问——各进程互斥地进入自己的临界区。
④假定一个系统中有n个进程(P0,P1,……,Pn)每个进程。
⑤当一个进程在临界区中执行时,其他进程都不能进入临界区。
2.进入区和退出区
①临界区的执行在时间上互斥,进程必须请求允许进入临界区。
②进入区(entry section):在进入临界区之前,检查可否进入临界区的一段代码。如果可进入,通常设置相应“正在访问临界区”标志。
③退出区(exit section):用于将“正在访问临界区”标志清除的一段代码。
④剩余区(remainder section):代码中的其余部分。
3.临界区的解决方案——三个要求
①互斥 mutual exclusion
假定进程Pi在其临界区内执行,其他任何进程将被排斥在自己的临界区之外。
②有空让进 progress
临界区虽没有进程只想,但有些进程需进入临界区,不能无限期延长下一个需要临界区进程的等待时间。
③有限等待 bounded waiting
在一个进程提出进入临界区的请求和该请求得倒答复的时间内,其他进程进入临界区的次数必须是有限的。
4.如何实现进程间的互斥
①两进程互斥的软件方法——算法1
设立一个两进程公用的整型变量turn:描述允许进入临界区的进程标识。
有两个进程Pi和Pj,如果turn == j,进程Pi允许在其临界区执行。
缺点:强制轮流进入临界区,没有充分考虑进场的实际需要,容易造成资源利用不充分。进程1让出临界区之后,进程2进入临界区之前,进程1无法再使用临界区。
②算法2
设立一个标志数组flag[]:描述进程是否准备进入临界区,初值均为FALSE。
优点:不用交替进入,可连续使用。
缺点:两进程可能都进不了临界区。
③算法3
turn=j,描述可进入的进程(同时修改标志),在进入区修改后检查,并检查并发修改的先后:
检查对方的flag,如不在临界区则自己进入——空闲则进
否则再次检查turn;先到先入,后到等待。
6-3信号量
OS可从进程管理者的角度处理互斥问题,信号量就是OS提供的管理公有资源的有效手段。
1.信号量——可用资源实体的数量 整型变量
①第一种 经典定义
除初始化外,仅能通过两个不可分割(原子)的操作访问。
P(S):
while S<=0 do no-op(等待,存在忙等,自旋锁);
S--;
V(S):
S++;
②第二种 一种不需要等待的同步工具
P(S):
S--;
if S<0 do block(阻塞)
V(S):
S++;
if S<=0 then wake up(唤醒其他操作)
2.信号量更多知识 Semaphore
①S是临界区内所使用公用资源有关的信号量。
P(S):表示申请一个资源
V(S):表示释放一个资源②初始为非负整数,表示空闲资源总数。
③在信号量经典定义下,S的值不可能为负。
④后一种定义中:S>=0,可供进程使用的资源数
S<0,绝对值是正在等待进入临界区的进程数。
3.利用信号量实现互斥
为临界资源设置一个互斥信号量,初值为1。每个进程中将临界区代码置于P(S)和V(S)原语之间
P(S):
Critical Section();
V(S);
4.利用信号量来描述前趋关系
6-4 哲学家问题 Dining Philosophers Problems
1.问题
2.解答
可能会出现死锁,五个人每个人拿起左边筷子。
3.解决死锁
①最多允许四个哲学家同时就坐
②同时拿起两根筷子
③非对称解决(单数座位号先拿左,双数先拿右)
6-5生产者消费者问题(有限缓冲区问题)
1.问题描述:若干进程通过有限的共享缓冲区交换数据,“生产者”可不断写入,“消费者”不断读出,共享缓冲区共有N个;任何时刻只能有一个进程可对共享缓冲区进行操作。
2.采用信号量机制解决
①full是“满”数目,初值为0,empty是“空”数目,初值为N。实际上,full + empty = N
②mutex用于访问缓冲区时的互斥,初值为1
③每个进程各个P操作的次序是重要的:先检查资源数目,再检查是否互斥——否则可能死锁(两种P操作)
6-6 读写问题
1.问题描述:对共享资源的读写操作,任一时刻“写者”最多允许一个,而“读者”允许多个。
①互斥 “读——写”
②互斥 “写——写”
③允许 “读——读”
2.如果读者来:
①无读者、写者,新读者可以读。
②有写者等,但有其他读者正在读,则新读者也可以读。
③有写者写,新读者等。
3.如果写者来:
①无读者,新写者可以写。
②有读者,新写者等待。
③有其他写者,新写者等待。
4.采用信号量机制
①信号量Wmutex表示“允许写”,初值为1
②公共变量Rcount表示“正在读”的进程数,初值为0
③信号量Rmutex表示Rcount的互斥操作,初值是1
5.PV操作讨论总结
1.①S>0 表示有S个资源可用
②S=0 表示无资源可用
③S<0 则|S|表示S等待队列中的进程个数
④P(S) 表示申请一个资源
⑤V(S) 表示释放一个资源
⑥信号量初始值应大于0
2.①PV操作必须成对出现,有一个P操作就一定有一个V操作。
②互斥问题:PV操作处于同一进程
同步问题:PV操作不在同一进程。
③对于前后相连的两个P(S1)和P(S2),顺序是至关重要的,同步P操作应该放在互斥P操作之前。
本文知识以及图片来源:慕课_操作系统原理_田丽华
网址:
转载地址:https://blog.csdn.net/Fan_z_0802/article/details/96382437 如侵犯您的版权,请留言回复原文章的地址,我们会给您删除此文章,给您带来不便请您谅解!