经典的同步/互斥问题—读者与写者(读者优先、写者优先、读写公平)

2024-03-10 21:10

本文主要是介绍经典的同步/互斥问题—读者与写者(读者优先、写者优先、读写公平),希望对大家解决编程问题提供一定的参考价值,需要的开发者们随着小编来一起学习吧!

经典的同步/互斥问题—读者与写者(读者优先、写者优先、读写公平)

一、问题描述

一个数据文件或记录,可被多个进程共享,我们把只要求读该文件的进程称为“读者进程”,其他进程则称为“写者进程”。
允许多个进程同时读一个共享对象,因为读操作不会使数据文件混乱。但不允许一个写者进程和其他读者进程或写者进程同时访问共享对象。因为这种访问将会引起混乱。

在这里插入图片描述

二、问题分析

对共享资源的读写操作,任一时刻“写者”最多只允许一个,而“读者”则允许多个:
“读-写”互斥
“写-写”互斥
“读-读”允许

当读进程reader要访问数据记录有以下几种情况:
1、无进程在访问,顺利进入临界区,访问临界资源
2、已有读进程在访问,此时仍可访问临界资源,但要记录有几个读进程在访问临界资源
3、已有写进程在访问,reader阻塞

当写进程writer要访问数据记录有以下几种情况:
1、无进程在访问,顺利进入临界区,访问临界资源
2、已有读进程在访问,writer阻塞
3、已有写进程在访问,writer阻塞

三、解决过程

①解决读写互斥、写写互斥

semaphore wmutex=1;//读写互斥
void reader(){//读者do{P(wmutex);read;//读者读V(wmutex);}while(TRUE);
}void writer(){//写者do{P(wmutex);write;//写者写V(wmutex);}while(TRUE);
}

上面实现了“读写互斥”、“写写互斥”,但假设读进程A正在访问共享资源,执行了P(wmutex) “上锁 ”,还没有执行V操作解锁,此时有读进程B也想访问共享资源,此时,读进程B会被阻塞。即读进程与读进程之间也变成了必须互斥访问共享资源,并不满足“读读允许”。

②再实现“读读允许”

semaphore wmutex=1;//读写互斥
int readcount=0;//记录当前有几个读进程在访问临界资源
void reader(){//读者do{if(readcount==0)P(wmutex);readcount++;read;//读者读readcount--;if(readcount==0)V(wmutex);}while(TRUE);
}void writer(){//写者do{P(wmutex);write;//写者写V(wmutex);}while(TRUE);
}

上述方法表面上看已经满足了“读-读”允许 的条件,但其实还存在一点问题:
如果读进程A想要访问共享资源,并且执行了P(wmutex)“上锁”操作,此时(进程A执行到“readcount++”之前或“readcount- -”之后),读进程B也想要访问共享资源,由于readcount=0也会执行P(wmutex),但是因为进程A已经执行了“上锁”操作,所以进程B还是会被阻塞,无法访问共享资源。可见,仍然可能出现读进程不可同时访问共享数据的情况。
出现这个问题的原因:
对于readcount变量的检查与赋值操作无法“一气呵成”,可以被中断。
解决方法:
可以增加一个rmutex互斥信号量来保证if判断语句和readcount++(readcount–)能够“一气呵成”执行完,保证各读进程对readcount的访问是互斥的。

③保证各读进程对readcount的访问是互斥的(读者优先)

semaphore rmutex=1,wmutex=1int readcount=0void reader(){//读者do{wait(rmutex)//申请对readcount的使用if(readcount==0)wait(wmutex);//第一个读者阻止后面的写者使用readcount++;signal(rmutex);//释放对readcount的使用read;//读者读wait(rmutex);//申请对readcount的使用readcount--;if(readcount==0)signal(wmutex);//最后一个读者使用完,写者才可使用signal(rmutex);//释放对readcount的使用}while(TRUE);
}void writer(){//写者do{wait(wmutex);//申请读文件write;//写者写signal(wmutex);//释放文件资源}while(TRUE);
}

上述解决方案确实已经达到了多个读者可以同时访问共享数据的目的,但此时,又出现了新的问题:
来看这样一种情况(下面用W表示写进程,R表示读进程):
R1,R2,W1,R3顺序到达,如何访问临界资源呢?

1.首先R1访问,rmutex=1, readcount = 1, wmutex = 0
2.R1还没访问完,R2到达:因为读进程可以同时访问,所以R2也可以访问临界资源,rmutex=1, readcount=2, wmutex = 0
3.W1到达:因为wmutex为0,所以W1阻塞
4.R3到达:仍可以访问临界资源,rmutex=1, readcount=3, wmutex = 0

如果有源源不断的读进程到达,写进程W1永远也不可能访问到临界资源,就是说写者有可能会被“饿死”,违反了有限等待的这条原则。
即这种算法是“读者优先”的,为什么会这样呢?
因为在第一个读者到达时,使得wmutex为0,阻塞了后续所有的写者,读者却仍然可以访问临界资源,我们只要使得后续的读者也阻塞,这样就使得读者和写者的优先级根据到达时间先后来决定,从而解决问题。

④实现读写公平
为此,可在原来的读优先算法的基础上增加:
初值为1的信号量S,这个信号量不分读者写者,只要有进程在访问临界资源,就不允许其他进程再访问了

semaphore rmutex=1,wmutex=1, S=1;
int readcount=0, writecount=0;
void reader(){//读者do{wait(S);		//**wait(rmutex)//申请对readcount的使用if(readcount==0)wait(wmutex);//第一个读者阻止后面的写者使用readcount++;signal(rmutex);//释放对readcount的使用signal(S);		//**read;//读者读wait(rmutex);//申请对readcount的使用readcount--;if(readcount==0)signal(wmutex);//最后一个读者使用完,写者才可使用signal(rmutex);//释放对readcount的使用//signal(S);  //如果把V操作放在这里,其他的读进程也不能访问临界资源了}while(TRUE);
}void writer(){//写者do{wait(S);		//**wait(wmutex);write;//读者读signal(wmutex);//最后一个写者使用完,读者才可使用signal(S);		//**}while(TRUE);
}

此时,当R1,R2都在访问数据,W1到达阻塞使得信号量S变为0,R3到达后也不能进入临界区,只能乖乖的等着W1执行完后,再访问临界资源。由此,便实现了读写平等。

⑤写者优先
那么,想实现写者优先,如何去做?只要将写者的到达数量也统计一下,不为0,读者就不能进临界区即可:
①初值为0的整型变量writecount,用来对写者进行计数
②初值为1的互斥信号量wcMutex,用来实现多个写者对writecount进行互斥访问

semaphore S=1;
semaphore rmutex=1,wmutex=1, wcMutex=1;
int readcount=0, writecount=0;
void reader(){//读者do{wait(S);wait(rmutex)//申请对readcount的使用if(readcount==0)wait(wmutex);//第一个读者阻止后面的写者使用readcount++;signal(rmutex);//释放对readcount的使用signal(S);	read;//读者读wait(rmutex);//申请对readcount的使用readcount--;if(readcount==0)signal(wmutex);//最后一个读者使用完,写者才可使用signal(rmutex);//释放对readcount的使用}while(TRUE);
}void writer(){//写者 do{wait(wcMutex);//申请对writecount的使用if(writecount==0)wait(S);//第一个写者阻止后面的读者使用writecount++;signal(wcMutex);//释放对writecount的使用wait(wmutex);write;//读者读signal(wmutex);	wait(wcMutex);//申请对writecount的使用writecount--;if(writecount==0)signal(S);//最后一个写者使用完,读者才可使用signal(wcMutex);//释放对writecount的使用}while(TRUE);
}

可以试一下,依照上述代码,W1,W2,R1,W3的访问临界资源的顺序是怎样的。

这篇关于经典的同步/互斥问题—读者与写者(读者优先、写者优先、读写公平)的文章就介绍到这儿,希望我们推荐的文章对编程师们有所帮助!



http://www.chinasem.cn/article/795517

相关文章

基于MySQL Binlog的Elasticsearch数据同步实践

一、为什么要做 随着马蜂窝的逐渐发展,我们的业务数据越来越多,单纯使用 MySQL 已经不能满足我们的数据查询需求,例如对于商品、订单等数据的多维度检索。 使用 Elasticsearch 存储业务数据可以很好的解决我们业务中的搜索需求。而数据进行异构存储后,随之而来的就是数据同步的问题。 二、现有方法及问题 对于数据同步,我们目前的解决方案是建立数据中间表。把需要检索的业务数据,统一放到一张M

服务器集群同步时间手记

1.时间服务器配置(必须root用户) (1)检查ntp是否安装 [root@node1 桌面]# rpm -qa|grep ntpntp-4.2.6p5-10.el6.centos.x86_64fontpackages-filesystem-1.41-1.1.el6.noarchntpdate-4.2.6p5-10.el6.centos.x86_64 (2)修改ntp配置文件 [r

10. 文件的读写

10.1 文本文件 操作文件三大类: ofstream:写操作ifstream:读操作fstream:读写操作 打开方式解释ios::in为了读文件而打开文件ios::out为了写文件而打开文件,如果当前文件存在则清空当前文件在写入ios::app追加方式写文件ios::trunc如果文件存在先删除,在创建ios::ate打开文件之后令读写位置移至文件尾端ios::binary二进制方式

好题——hdu2522(小数问题:求1/n的第一个循环节)

好喜欢这题,第一次做小数问题,一开始真心没思路,然后参考了网上的一些资料。 知识点***********************************无限不循环小数即无理数,不能写作两整数之比*****************************(一开始没想到,小学没学好) 此题1/n肯定是一个有限循环小数,了解这些后就能做此题了。 按照除法的机制,用一个函数表示出来就可以了,代码如下

hdu1043(八数码问题,广搜 + hash(实现状态压缩) )

利用康拓展开将一个排列映射成一个自然数,然后就变成了普通的广搜题。 #include<iostream>#include<algorithm>#include<string>#include<stack>#include<queue>#include<map>#include<stdio.h>#include<stdlib.h>#include<ctype.h>#inclu

hdu1180(广搜+优先队列)

此题要求最少到达目标点T的最短时间,所以我选择了广度优先搜索,并且要用到优先队列。 另外此题注意点较多,比如说可以在某个点停留,我wa了好多两次,就是因为忽略了这一点,然后参考了大神的思想,然后经过反复修改才AC的 这是我的代码 #include<iostream>#include<algorithm>#include<string>#include<stack>#include<

购买磨轮平衡机时应该注意什么问题和技巧

在购买磨轮平衡机时,您应该注意以下几个关键点: 平衡精度 平衡精度是衡量平衡机性能的核心指标,直接影响到不平衡量的检测与校准的准确性,从而决定磨轮的振动和噪声水平。高精度的平衡机能显著减少振动和噪声,提高磨削加工的精度。 转速范围 宽广的转速范围意味着平衡机能够处理更多种类的磨轮,适应不同的工作条件和规格要求。 振动监测能力 振动监测能力是评估平衡机性能的重要因素。通过传感器实时监

缓存雪崩问题

缓存雪崩是缓存中大量key失效后当高并发到来时导致大量请求到数据库,瞬间耗尽数据库资源,导致数据库无法使用。 解决方案: 1、使用锁进行控制 2、对同一类型信息的key设置不同的过期时间 3、缓存预热 1. 什么是缓存雪崩 缓存雪崩是指在短时间内,大量缓存数据同时失效,导致所有请求直接涌向数据库,瞬间增加数据库的负载压力,可能导致数据库性能下降甚至崩溃。这种情况往往发生在缓存中大量 k

6.1.数据结构-c/c++堆详解下篇(堆排序,TopK问题)

上篇:6.1.数据结构-c/c++模拟实现堆上篇(向下,上调整算法,建堆,增删数据)-CSDN博客 本章重点 1.使用堆来完成堆排序 2.使用堆解决TopK问题 目录 一.堆排序 1.1 思路 1.2 代码 1.3 简单测试 二.TopK问题 2.1 思路(求最小): 2.2 C语言代码(手写堆) 2.3 C++代码(使用优先级队列 priority_queue)

poj 3190 优先队列+贪心

题意: 有n头牛,分别给他们挤奶的时间。 然后每头牛挤奶的时候都要在一个stall里面,并且每个stall每次只能占用一头牛。 问最少需要多少个stall,并输出每头牛所在的stall。 e.g 样例: INPUT: 51 102 43 65 84 7 OUTPUT: 412324 HINT: Explanation of the s