PV模型:(有待整理汇总
多生产者、单生产者、多消费者、单消费者、单一生产者资源,单一消费者资源
多生产者资源,多消费者资源,多口袋,口袋容量大于1,口袋容量等于一,排列组合
大多数都是消费者-生产者问题
[https://zhuanlan.zhihu.com/p/593795480]可搭配食用
生产者、消费者问题:
抽象为多生产者提供单一产品,多消费者消费单一产品,单口袋容量大于一的情况
对于生产者:
如果管道不满,并且能够得到管道使用权,那么写
对于消费者:
如果管道不空,并且能够得到管道使用权,那么读
构建逻辑关系:
互斥资源只有一个就是对管道的占据权
同步资源其实就是指当前的管道内的内容资源
下面有对这个资源进行解释,为何需要拆分为一个空,一个满而不是采用一个计数器
因而构建互斥资源初始量为一,两个同步资源一个初始量为零,一个初始量为满
需要先检查,后占用,否则会产生死锁问题
附:
可以更加简化流程
口袋空间设置为资源,口袋的使用权也设置为资源,消费者使用资源也设为资源
A当口袋没有生产者资源或者没有口袋使用权资源时陷入阻塞
A当口袋有生产者资源并且有口袋使用权时被唤醒并提供消费者资源、口袋使用权资源
唤醒的同时“消耗生产者资源”
P口袋有没有空资源(生产者资源
P口袋有没有人在用(口袋使用权
V创造口袋消费者资源
V口袋使用权
B当口袋没有消费者资源或者没有口袋使用权资源时陷入阻塞
B当口袋有消费者资源并且有口袋使用权时被唤醒并提供口袋使用权资源、生产者资源
唤醒的同时“消耗消费者资源”
P口袋有没有满资源(消费者资源
P口袋有没有人在用(口袋使用权
V创造口袋生产者资源
V口袋使用权
对于书上一长串话的解释:
简单来说就是导致了先占用,后检查,检查不通过,于是一直占用
对于生产者来说就是先占用了一个满的管道,然后检查发现是满的,于是一直不写
导致消费者想要读的时候被阻塞
对于消费者来说就是先占用了一个空的管道,然后检查发现是空的,于是一直不读
导致生产者想要写的时候被阻塞
其实这里就是典型的提示,必须要先检查有无生产者/消费者资源,再检查互斥量
否则会产生经典的死锁问题
附:
需要注意的是,这边采用了一个FULL和一个EMPTY两个变量来定义管道缓冲区状态
其实要理解为什么这里设置两个,因为没办法实现上限的控制
如果单纯使用一个X计数器,计数当前已经有的字数资源,那么实际上是达成不到效果的
因为用P、V操作,只能实现对X的占用、释放,无法对其设置一个上限,只能有个下限
计数器的话,是没办法实现互斥访问的,因为计数器资源只能代表字数资源
管道资源的占据,还是需要依靠一个互斥量来实现,计数器资源是一个同步资源
附:
其实这里对读、写两组进程,虽然说是一组,但因为实现了互斥资源的占用
所以实际上一时刻内只有一个进程在读或者写,而不是多个,Full和Empty资源是同步的
互斥资源只有那么一个,并且资源量从开始就固定不变,并且也是不允许被改变的
同步资源一般不止那么一个,资源量也随时都会改变
水果问题:
父亲而言:
如果当前盘子里没有水果,且母亲不放橘子,那么放一个苹果
母亲而言:
如果当前盘子里没有水果,且父亲不放苹果,那么放一个橘子
女儿而言:
如果当前盘子里有苹果,那么吃一个苹果
儿子而言:
如果当前盘子里有橘子,那么吃一个橘子
构建逻辑关系:
A当没有生产者资源或者没有使用权时陷入阻塞
A当有生产者资源并且有使用权时被唤醒消费生产者资源提供消费者资源
P有没有生产者资源(盘子是否为空
P口袋有没有人在用(盘子是否被占用
V创造消费者资源(提供一个苹果/橘子
V口袋使用权(口袋的互斥访问
B当没有消费者资源或者没有使用权时陷入阻塞
B当有消费者资源并且有使用权时被唤醒消费消费者资源提供生产者资源
P有没有消费者资源(盘子里是否有苹果/橘子
P口袋有没有人在用(盘子是否被占用
V创造生产者资源(提供一个空盘子
V口袋使用权(口袋的互斥访问
附:
其实可以看到书上的代码明显比我个人列出的更为简单和简洁
主要是删去了口袋使用权的互斥,其实也很容易理解
假设,口袋是有使用权的
生产者资源最多只有一个,意味着同一时刻只有一个生产者会占用该使用权
同时消费者在等待生产者创造消费者资源,不会过来占据口袋使用权
在逻辑上只需要实现,先释放口袋使用权,再创造消费者资源,就可以保证消费者不来用
同时因为生产者资源这时候已经用完了,在释放口袋使用权的时候也没生产者会用
消费者资源最多也只有一个,意味着同一时间也只有一个消费者会占用该使用权
同时生产者也类似,在等待消费者创造生产者资源,也不会过来占据口袋的使用权
在逻辑上,同样只需要实现,先释放口袋的使用权,再创造生产者资源,生产者也不会抢
可以看到这边的口袋使用权可以说是个摆设
生产者生产的时候,没有别人来占据,同时间只有一个生产者生产
消费者消费的时候,同样没有别人来占据,同时间只有一个消费者消费
所以没有这个互斥量也不会出事
但,个人列出的是更为广泛可用的一个模板,大部分消费者-生产者都可以这样处理
因为互斥往往在对共享资源的访问之上
生产者要等到有生产者资源的时候才能生产
消费者要等到有消费者资源的时候才能消费
同步、互斥量基本也就这些
读者、写者问题:
第一种思路,饿死写者思路
对于写者:
当现在没有读者在读并且写者在写的时候写
对于读者:
当现在没有写者在写的时候读
构建逻辑关系:
A当没有生产者资源的时候陷入阻塞,当没有访问权资源的时候阻塞
当有生产者资源的时候被唤醒,创造消费者资源
这里的生产者资源,就是指当前没有正在读的进程,若读进程为零则可用
这里的访问权资源,就是指当前没有正在写的进程,若有访问权资源则可用
在读者进程中采用锁写者资源的方式来决定是否有写者资源
因而实际上写者资源和访问权资源重复,同一时刻只能有一个写者资源
P写者资源
V写者资源
B当没有消费者资源的时候陷入阻塞
其他情况均创造生产者资源
这里的消费者资源,其实没有其他的,只有一个访问权资源,但多个读者又不互斥
所以肯定需要被写者互斥,但又不能对读者互斥,在读的时候内均锁住读者的写资源即可
这里的生产者资源,就是读者数量为零的时候创建,其他情况不创建
也可以采用一个读者计数器来实现创建
P互斥访问计数资源,这个必须互斥
readcount++
if readcount == 0
P锁住写者资源让其不能写
V互斥释放计数资源,当读的时候没必要占用资源,否则就会导致实际上变成单读者占用
P互斥访问计数资源,同样互斥修改计数器
readcount–
if readcount == 0
V释放写者资源让其现在能写
V互斥释放计数资源
第二种思路,写优先:
只需要补充一个读写互斥资源即可
写者占据资源的时候读者不能写,所以最后释放
读者占据资源的时候,主要是阻塞写者资源的情况下需要互斥,其他情况不需要
读者、写者问题的核心是采用了一个计数器,同时依赖计数器锁死写进程
当读者读的时候,只要有读者存在的情况,计数器都会保证写进程当前被锁死无法进行
当没有读者才释放让写者进行运行
保证了写者只有在当前读者全部退出的情况下才运行
同时也保证了当前的读者之间不会有互斥的访问
对计数器资源需要互斥访问,否则就会导致计数器表示的错误
吸烟者问题:
这个还是比较好理解的,其实就是生产者-消费者的变体,一个生产者提供多消费者资源
生产者而言
当有生产者资源的时候,当有占用权的时候
提供A或B或C,这个当前是需要随机数或者说顺序执行实现的
P生产者资源(这里是桌子是否空,或者说是否消费完
P占用权(这里是单生产者,所以不需要占用权,多生产者的时候需要考虑
对于消费者:
当有消费者资源,当有占用权的时候
消费A或B或C
P消费者资源,这里就是单纯的指代消费者资源,和水果资源是如出一辙的
P占用权,这里生产者和消费者同样是被动互斥占用的,和水果基本类似,不需要考虑
但写了肯定不会算错
V生产者资源(这里是指消费完毕,当前桌子为空,提供空资源,或提供空消费资源
其实消费者、生产者这边可以有非常多的变体
但个人认为,核心是把握生产者什么时候被阻塞,什么时候被唤醒生产,生产什么
对应,生产者资源、存储区占用权、消费者资源
消费者就是把握什么时候被阻塞,什么时候被唤醒消费,提供什么生产者资源
对应,消费者资源、存储区占用权、生产者资源
通过同步解决生产、消费资源
通过互斥解决存储区的占用权问题
非消费者-生产者问题:
哲学家问题:
一个进程需要同时持有多个临界资源,而这个临界资源可能被其他同类进程使用
于是就可能导致持有到一半的时候,另外一个也持有到一半,导致死锁
应该怎么处理?
其实最核心的就是,让一个哲学家现在能够吃饭
那么说实话如果不考虑系统量,我每次只让一个哲学家吃饭都没事,谁都只能看着他吃
当然没必要这样,互斥量就是基于这样一个思想提出的
先说书上的采用互斥量的解决方法
其实相当于每次只放一个哲学家进来取筷子,如果没有办法两个都取到那么就先等待
通过信号量mutex对eat()之前的取左侧和右侧筷子的操作进行保护,使之成为一个原子操作,防止死锁的出现
当一个哲学家两个筷子都取到后,那么就可以让别的哲学家取筷子,自己就先吃饭
这个适用性最广
再说,只放四个哲学家进来,让一个哲学家在外面饿着
其实这样就是保证一定会有一个哲学家当前能够成功进餐,其他的只需要等待就行
如果要普遍化的话,就是要实现“一次必须要有一个进程能够成功运行,且不会死锁”
奇数偶数、左右手撇子法都是一样的
保证当前一定有一个哲学家能够吃到饭,这就是核心