读者写者问题—内含408真题

读者写者问题—含408

一、问题描述

一个数据问价或记录可以被多个进程共享,我们把只读该文件的进程称为“读者进程”,其他进程为“写者进程”。允许多个进程同时读一个共享对象,但不允许一个写者进程和其他写者进程或读者进程同时访问共享对象。即:保证一个写者进程必须与其他进程互斥的访问共享对象的同步问题;读者-写者问题常用来测试新同步原语。

二、解题思路

首先对于上述问题进行抽象:读者和写者是互斥的,写者和写者是互斥的,读者和读者不互斥;两类进程,一种是写者,另一种是读者。写者很好实现,因为它和其他任何进程都是互斥的,因此对每一个写者进程都给一个互斥信号量的P、V操作即可;而读者进程的问题就较为复杂,它与写者进程是互斥的,而又与其他的读者进程是同步的,因此不能简单的利用P、V操作解决。
下面我们给出三种方案来解决读者和写者之间、读者和读者之间、写者和写者之间的同步与互斥问题:

2.1 读者优先算法(一般意义上的读者写者问题)

为实现Reader和Writer进程之间在读或写时的互斥而设置了一个互斥信号量wmutex。再设置一个整型变量conut表示正在读的进程数目。
仅当count=0时,Reader进程才需要执行P(wmutex)操作;
仅当Reader进程在执行了count减一操作后其值为0时,才需要执行V(wmutex)操作
由于count是一个可被多个Reader进程访问的临界资源,因此为其设置一个互斥信号量cmutex;
其伪码描述如下:

semaphore cmutex=1,wmutex=1;
int count=0;void Reader(){while(1){P(cmutex);if(count==0)P(wmutex);count++;V(cmutex);read;P(cmutex);count--;if(count==0)V(wmutex);V(cmutex);}
}void Writer(){while(1){P(wmutex);write;V(wmutex);}
}

等待Reader进程全部结束之后才逐步执行Writer进程。我们称这样的算法为读者优先算法,也就是说,当存在读进程时,写操作将被延迟,并且只要有一个读进程活跃,随后而来的读进程都将被允许访问文件。这样的方式下,会导致写进程可能长时间等待,且存在写进程“饿死”的情况。


2.2 写者优先算法

所谓写者优先,即:当有读者进程正在执行,写者进程发出申请,这时应该拒绝其他读者进程的请求,等待当前读者进程结束后立即执行写者进程,只有在无写者进程执行的情况下才能够允许读者进程再次运行。
为此,增加一个信号量并且在上面的程序中 writer()和reader()函数中各增加一对PV操作,就可以得到写进程优先的解决程序。

  • 在读者优先的基础上增加信号量rmutex,初值是1,用于禁止所有的读进程。
  • 增加一个记数器,即整型变量writecount,记录写者数,初值是0(原count改为readcount)。
  • writecount为多个写者共享的变量,是临界资源。用互斥信号量wmutex控制, wmutex初值是1
  • mutex用于实现互斥访问缓冲区
    伪码描述如下:
semaphore rmutex=1,cmutex=1,wmutex=1,mutex=1;
int readcount=0,writecount=0;void Reader(){while(1){/**新增代码**/P(rmutex);// 取到该信号量说明此时并没有写进程在等待// 后续读者才可以共享访问临界区// 但是前面已经进入的读进程不受影响/**********/P(cmutex);if(readcount==0)P(mutex);readcount++;V(cmutex);/**新增代码**/V(rmutex);// 已经取到过这个信号量了// 那么就说明已经得到了对临界区的读访问权限// 此时可以一起读/**********/		read;V(cmutex);readcount--;if(readcount==0)V(mutex);V(cmutex);}
}void Writer(){while(1){/**新增代码**/P(wmutex);writecount++;if(writecount==1)// 第一个写进程进来等待以后就P(rmutex);	 // 禁止读进程继续读了V(wmutex);/***********/P(mutex);write;V(mutex);/**新增代码**/P(wmutex);writecount--;if(writecount==0)//当没有写进程时,才允许读进程继续读V(rmutex);V(wmutex);/***********/}
}

2.3 读写公平

为实现读写公平,我们必须要同时满足以下四个条件:

  • 读者写者的优先级相同
  • 读者、写者互斥访问
  • 只允许有一个写者访问临界区
  • 可以有多个读者同时访问临界区的资源
    为此,我们设置一个互斥信号量mutex,其作用是让每个Writer进程和Reader进程进行公平争夺
  • 当Reader争夺到了,那么不管他是不是第一个Reader,他都有权利进入读操作(但是在进行读操作之前,需要释放这个互斥信号量,供后续的Reader和Writer继续公平争夺)
  • 当Writer争夺到了,就等待之前的Reader全部执行完,就可以上处理机运行
semaphore cmutex=1,wmutex=1,mutex=1;
int count=0;void Reader(){while(1){/**新增代码**/P(mutex);//争夺优先权/**********/P(cmutex);if(count==0)P(wmutex);count++;V(cmutex);/**新增代码**/V(mutex);/**********/read;P(cmutex);count--;if(count==0)V(wmutex);V(cmutex);}
}void Writer(){while(1){/**新增代码**/P(mutex);//争夺优先权/**********/P(wmutex);write;V(wmutex);/**新增代码**/V(mutex);/**********/}
}

这个最主要的思路就是让每一次运行的进程都有公平竞争的权利
因为读者优先算法,当读者上处理机运行后,写者就丧失了竞争的权利,只有当读者全部读完才可以重新竞争,这很不公平

2.4 双读者问题(2017年408真题)

先说明一下,双读者问题实际上并不存在,只是针对这道题提出的概念,由于使用常规的读者写者算法会导致并发度不够,所以特地将真题单独作为一个问题考虑

在这里插入图片描述
口说无凭,不如使用对比来更直观地展现其区别吧
首先是使用读者写者问题来解决该问题的算法:

semaphore mutex_x=1;// 对x的互斥访问
semaphore mutex_y=1;// 对y的互斥访问
semaphore mutex_z=1;// 对z的互斥访问
semaphore mutex_count=1;// 对计数器的互斥访问
int count=0;//计数器void thread1(){cnum w;P(mutex_count);if(count==0)P(mutex_y);count++;V(mutex_count);P(mutex_x);w = add(x,y);V(mutex_x);P(mutex_count);count--;if(count==0)V(mutex_y);V(mutex_count);}void thread2(){cnum w;P(mutex_count);if(count==0)P_(mutex_y);count++;V(mutex_count);P(mutex_z);w = add(y,z);V(mutex_z);P(mutex_count);count--;	if(count==0)V(mutex_y);V(mutex_count);	
}void thread3(){cnum w;w.a = 1;w.b = 1;P(mutex_z);z = add(z,w);V(mutex_z);P(mutex_y);y = add(y,w);V(mutex_y);
}

乍一看好像没啥问题,但是有一个很重要的问题是,虽然对于y的访问,实现了读写互斥,同时读与读可以同时进行,但是count信号量限制了并发度,导致两个读操作并不能以最快的方式运行完
下面是标准答案:

semaphore mutex_x=1;// 对x的互斥访问
semaphore mutex_y1=1;// 对y的互斥访问
semaphore mutex_y2=1;// 对y对互斥访问
semaphore mutex_z=1;// 对z的互斥访问
void thread1(){cnum w;P(mutex_y1);P(mutex_x);w = add(x,y);V(mutex_x);V(mutex_y1);
}void thread2(){cnum w;P(mutex_y2);P(mutex_z);w = add(y,z);V(mutex_z);V(mutex_y2);	
}void thread3(){cnum w;w.a = 1;w.b = 1;P(mutex_z);z = add(z,w);V(mutex_z);P(mutex_y1);// 只有同时拥有互斥信号量P(mutex_y2);// 才算是获取了访问权限y = add(y,w);V(mutex_y1);V(mutex_y2);
}

上面的代码,可以大大提高并发度,因为1,2两个线程也可以保证在读y时是绝对并行的

本文来自互联网用户投稿,该文观点仅代表作者本人,不代表本站立场。本站仅提供信息存储空间服务,不拥有所有权,不承担相关法律责任。如若转载,请注明出处:http://www.rhkb.cn/news/146079.html

如若内容造成侵权/违法违规/事实不符,请联系长河编程网进行投诉反馈email:809451989@qq.com,一经查实,立即删除!

相关文章

使用ElementUI结合Vue完善主页的导航菜单和书籍管理以及后台数据分页查询

目录 动态树 数据表 案列 书籍管理 动态树 动态树(Dynamic tree)是一种数据结构,它可以在树中动态地插入、删除和修改节点。与静态树不同,静态树的节点是固定的,一旦构建完成就无法再进行修改。而动态树可以在运行时…

Leetcode 1239. 串联字符串的最大长度

文章目录 题目代码&#xff08;9.29 首刷部分看解析&#xff09; 题目 Leetcode 1239. 串联字符串的最大长度 代码&#xff08;9.29 首刷部分看解析&#xff09; class Solution { public:unordered_set<int> skip;unordered_set<char> used;int maxLength(vecto…

cesium 雷达扫描 (线行扩散效果)

cesium 雷达扫描 (线行扩散效果) 1、实现方法 使用ellipse方法加载圆型,修改ellipse中material方法来实现效果 2、示例代码 2.1、 <!DOCTYPE html> <html lang="en"><head><<

Edge扩展插件推荐专业视频下载器

专业视频下载器&#xff0c;这款扩展插件非常好用&#xff0c;强烈推荐。只要能打开的视频&#xff0c;都能下载。 安装完成是这样的&#xff1a; 有用记得点赞。

在linux下预览markdown的方法,转换成html和pdf

背景 markdown是一种便于编写和版本控制的格式&#xff0c;但却不便于预览——特别是包含表格等复杂内容时&#xff0c;单纯的语法高亮是远远不够的——这样就不能边预览边调整内容&#xff0c;需要找到一种预览方法。 思路 linux下有个工具&#xff0c;叫pandoc&#xff0c…

日期范围搜索

1.日期范围选择界面 <?xml version"1.0" encoding"utf-8"?> <ScrollViewandroid:layout_width"fill_parent"android:layout_height"fill_parent"xmlns:android"http://schemas.android.com/apk/res/android">…

mysql面试题6:MySQL索引的底层原理,是如何实现的?B+树和B树的区别?

该文章专注于面试,面试只要回答关键点即可,不需要对框架有非常深入的回答,如果你想应付面试,是足够了,抓住关键点 面试官:MySQL索引的底层原理,是如何实现的? MySQL索引的底层实现是通过B+树来实现的。B+树是一种多叉平衡查找树,它的特点是能够高效地支持数据的插入…

简历项目优化关键方法论-START

START方法论是非常著名的面试法则&#xff0c;经常被面试官使用的工具 Situation:情况、事情、项目需求是在什么情况下发生Task:任务&#xff0c;你负责的做的是什么Action:动作&#xff0c;针对这样的情况分析&#xff0c;你采用了什么行动方式Result:结果&#xff0c;在这样…

设计模式8、装饰者模式 Decorator

解释说明&#xff1a;动态地给一个对象增加一些额外的职责。就扩展功能而言&#xff0c;装饰模式提供了一种比使用子类更加灵活的替代方案 抽象构件&#xff08;Component&#xff09;&#xff1a;定义一个抽象接口以规范准备收附加责任的对象 具体构件&#xff08;ConcreteCom…

八、3d场景的区域光墙

在遇到区域展示的时候我们就能看到炫酷的区域选中效果&#xff0c;那么代码是怎么编辑的呢&#xff0c;今天咱们就好好说说&#xff0c;下面看实现效果。 思路&#xff1a; 首先&#xff0c;光墙肯定有多个&#xff0c;那么必须要创建一个新的js文件来作为他的原型对象。这个光…

unity打包工具

接手了一个项目&#xff0c;打包存在重大问题&#xff0c;故此在unity addressables 基础上弄了一个简单的打包工具&#xff0c;代码也都做好了注释&#xff0c;操作非常简单以下为操作方法&#xff1a; 首先设置导入Addressables插件&#xff0c;并设置好详细参见&#xff1a…

bypass disable_function 学习

LD_PRELOAD 我是在做了 buu的 REC ME 来做这个系列 所以 LD_PRELOAD 已经有了解了 我们来做这个题目 CTFHub Bypass disable_function —— LD_PRELOAD本环境来源于AntSword-Labs <!DOCTYPE html> <html> <head><title>CTFHub Bypass disable_func…

K-Means(上):数据分析 | 数据挖掘 | 十大算法之一

⭐️⭐️⭐️⭐️⭐️欢迎来到我的博客⭐️⭐️⭐️⭐️⭐️ &#x1f434;作者&#xff1a;秋无之地 &#x1f434;简介&#xff1a;CSDN爬虫、后端、大数据领域创作者。目前从事python爬虫、后端和大数据等相关工作&#xff0c;主要擅长领域有&#xff1a;爬虫、后端、大数据…

liunx的攻击

1.场景和分析 2.病毒分析 3.解决步骤

CTF-python爬虫学习笔记

学习链接 【Python爬虫】爆肝两个月&#xff01;拜托三连了&#xff01;这绝对是全B站最用心&#xff08;没有之一&#xff09;的Python爬虫公开课程&#xff0c;从入门到&#xff08;不&#xff09;入狱 &#xff01; 。知识 1.1 出现错误 复制红框中的内容去查找 1.2 打印…

面试题:线程池灵魂8连问,你挡的住吗?

文章目录 1. 面试官&#xff1a;日常工作中有用到线程池吗&#xff1f;什么是线程池&#xff1f;为什么要使用线程池&#xff1f;2. 面试官&#xff1a;ThreadPoolExecutor 都有哪些核心参数&#xff1f;3. 面试官&#xff1a;什么是阻塞队列&#xff1f;说说常用的阻塞队列有哪…

Wi-Fi直连分享:Android设备间的高速连接

Wi-Fi直连分享&#xff1a;Android设备间的高速连接 引言 随着无线局域网&#xff08;Wi-Fi&#xff09;的普及和发展&#xff0c;使用Wi-Fi直连技术&#xff08;P2P&#xff09;在没有中间接入点的情况下实现设备间直接互联成为可能。通过Wi-Fi直连&#xff0c;具备相应硬件…

云原生Kubernetes:K8S配置资源管理

目录 一、理论 1.Secret 2.Secret创建 3.Secret使用 4.Configmap 5.Configmap创建 6.Configmap使用 二、实验 1.Secret创建 2.Secret使用 3.Configmap创建 4.Configmap使用 三、问题 1.变量引用生成资源报错 2.查看pod日志失败 3.创建configmap报错 4.YAML创建…

2022年中国征信行业覆盖人群、参与者数量及征信业务查询量统计[图]

征信是指依法收集、整理、保存、加工自然人、法人及其他组织的信用信息&#xff0c;并对外提供信用报告、信用评估、信用信息咨询等服务&#xff0c;帮助客户判断、控制信用风险&#xff0c;进行信用管理的活动。 征信业主要范畴 资料来源&#xff1a;共研产业咨询&#xff08…

百元开放式耳机推荐哪款、性价比最好的开放式耳机推荐

随着蓝牙耳机产业的高速发展&#xff0c;目前最热门的蓝牙耳机莫过于开放式的&#xff0c;跟传统的蓝牙耳机相比&#xff0c;开放式的耳机拥有久戴不累、安全舒适等优势&#xff0c;所谓的“开放式耳机”&#xff0c;就是指不用塞入耳朵内&#xff0c;也能听音乐的耳机&#xf…