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

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

相关文章

怎样通过分析GC日志来定位Java进程的内存问题

《怎样通过分析GC日志来定位Java进程的内存问题》:本文主要介绍怎样通过分析GC日志来定位Java进程的内存问题,具有很好的参考价值,希望对大家有所帮助,如有错误或未考虑完全的地方,望不吝赐教... 目录一、GC 日志基础配置1. 启用详细 GC 日志2. 不同收集器的日志格式二、关键指标与分析维度1.

Java 线程安全与 volatile与单例模式问题及解决方案

《Java线程安全与volatile与单例模式问题及解决方案》文章主要讲解线程安全问题的五个成因(调度随机、变量修改、非原子操作、内存可见性、指令重排序)及解决方案,强调使用volatile关键字... 目录什么是线程安全线程安全问题的产生与解决方案线程的调度是随机的多个线程对同一个变量进行修改线程的修改操

Redis出现中文乱码的问题及解决

《Redis出现中文乱码的问题及解决》:本文主要介绍Redis出现中文乱码的问题及解决,具有很好的参考价值,希望对大家有所帮助,如有错误或未考虑完全的地方,望不吝赐教... 目录1. 问题的产生2China编程. 问题的解决redihttp://www.chinasem.cns数据进制问题的解决中文乱码问题解决总结

全面解析MySQL索引长度限制问题与解决方案

《全面解析MySQL索引长度限制问题与解决方案》MySQL对索引长度设限是为了保持高效的数据检索性能,这个限制不是MySQL的缺陷,而是数据库设计中的权衡结果,下面我们就来看看如何解决这一问题吧... 目录引言:为什么会有索引键长度问题?一、问题根源深度解析mysql索引长度限制原理实际场景示例二、五大解决

Springboot如何正确使用AOP问题

《Springboot如何正确使用AOP问题》:本文主要介绍Springboot如何正确使用AOP问题,具有很好的参考价值,希望对大家有所帮助,如有错误或未考虑完全的地方,望不吝赐教... 目录​一、AOP概念二、切点表达式​execution表达式案例三、AOP通知四、springboot中使用AOP导出

Python中Tensorflow无法调用GPU问题的解决方法

《Python中Tensorflow无法调用GPU问题的解决方法》文章详解如何解决TensorFlow在Windows无法识别GPU的问题,需降级至2.10版本,安装匹配CUDA11.2和cuDNN... 当用以下代码查看GPU数量时,gpuspython返回的是一个空列表,说明tensorflow没有找到

解决未解析的依赖项:‘net.sf.json-lib:json-lib:jar:2.4‘问题

《解决未解析的依赖项:‘net.sf.json-lib:json-lib:jar:2.4‘问题》:本文主要介绍解决未解析的依赖项:‘net.sf.json-lib:json-lib:jar:2.4... 目录未解析的依赖项:‘net.sf.json-lib:json-lib:jar:2.4‘打开pom.XM

IDEA Maven提示:未解析的依赖项的问题及解决

《IDEAMaven提示:未解析的依赖项的问题及解决》:本文主要介绍IDEAMaven提示:未解析的依赖项的问题及解决,具有很好的参考价值,希望对大家有所帮助,如有错误或未考虑完全的地方,望不吝... 目录IDEA Maven提示:未解析的依编程赖项例如总结IDEA Maven提示:未解析的依赖项例如

MySQL主从复制与读写分离的用法解读

《MySQL主从复制与读写分离的用法解读》:本文主要介绍MySQL主从复制与读写分离的用法,具有很好的参考价值,希望对大家有所帮助,如有错误或未考虑完全的地方,望不吝赐教... 目录一、主从复制mysql主从复制原理实验案例二、读写分离实验案例安装并配置mycat 软件设置mycat读写分离验证mycat读

Redis分片集群、数据读写规则问题小结

《Redis分片集群、数据读写规则问题小结》本文介绍了Redis分片集群的原理,通过数据分片和哈希槽机制解决单机内存限制与写瓶颈问题,实现分布式存储和高并发处理,但存在通信开销大、维护复杂及对事务支持... 目录一、分片集群解android决的问题二、分片集群图解 分片集群特征如何解决的上述问题?(与哨兵模