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

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

相关文章

Spring的RedisTemplate的json反序列泛型丢失问题解决

《Spring的RedisTemplate的json反序列泛型丢失问题解决》本文主要介绍了SpringRedisTemplate中使用JSON序列化时泛型信息丢失的问题及其提出三种解决方案,可以根据性... 目录背景解决方案方案一方案二方案三总结背景在使用RedisTemplate操作redis时我们针对

Kotlin Map映射转换问题小结

《KotlinMap映射转换问题小结》文章介绍了Kotlin集合转换的多种方法,包括map(一对一转换)、mapIndexed(带索引)、mapNotNull(过滤null)、mapKeys/map... 目录Kotlin 集合转换:map、mapIndexed、mapNotNull、mapKeys、map

nginx中端口无权限的问题解决

《nginx中端口无权限的问题解决》当Nginx日志报错bind()to80failed(13:Permissiondenied)时,这通常是由于权限不足导致Nginx无法绑定到80端口,下面就来... 目录一、问题原因分析二、解决方案1. 以 root 权限运行 Nginx(不推荐)2. 为 Nginx

解决1093 - You can‘t specify target table报错问题及原因分析

《解决1093-Youcan‘tspecifytargettable报错问题及原因分析》MySQL1093错误因UPDATE/DELETE语句的FROM子句直接引用目标表或嵌套子查询导致,... 目录报js错原因分析具体原因解决办法方法一:使用临时表方法二:使用JOIN方法三:使用EXISTS示例总结报错原

Windows环境下解决Matplotlib中文字体显示问题的详细教程

《Windows环境下解决Matplotlib中文字体显示问题的详细教程》本文详细介绍了在Windows下解决Matplotlib中文显示问题的方法,包括安装字体、更新缓存、配置文件设置及编码調整,并... 目录引言问题分析解决方案详解1. 检查系统已安装字体2. 手动添加中文字体(以SimHei为例)步骤

SpringSecurity整合redission序列化问题小结(最新整理)

《SpringSecurity整合redission序列化问题小结(最新整理)》文章详解SpringSecurity整合Redisson时的序列化问题,指出需排除官方Jackson依赖,通过自定义反序... 目录1. 前言2. Redission配置2.1 RedissonProperties2.2 Red

nginx 负载均衡配置及如何解决重复登录问题

《nginx负载均衡配置及如何解决重复登录问题》文章详解Nginx源码安装与Docker部署,介绍四层/七层代理区别及负载均衡策略,通过ip_hash解决重复登录问题,对nginx负载均衡配置及如何... 目录一:源码安装:1.配置编译参数2.编译3.编译安装 二,四层代理和七层代理区别1.二者混合使用举例

C#读写文本文件的多种方式详解

《C#读写文本文件的多种方式详解》这篇文章主要为大家详细介绍了C#中各种常用的文件读写方式,包括文本文件,二进制文件、CSV文件、JSON文件等,有需要的小伙伴可以参考一下... 目录一、文本文件读写1. 使用 File 类的静态方法2. 使用 StreamReader 和 StreamWriter二、二进

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

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

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

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