OS复习笔记ch5-4-2

引言

承接上文我们介绍了信号量机制和应用信号量机制实现的进程同步和互斥,这一节我们将围绕一些经典问题对信号量机制展开更深入地探讨。

读者/写者问题

ppt

读者/写者问题与我们之前遇到的问题类型不同,它描述的是:

有读者和写者两组进程,它们共同访问同一个文件。

对于读者,它可以与多个读者共同读取文件(因为不会修改到文件);

对于写者,它不能与其他任何进程共同访问文件(如果另一进程是写,则可能覆盖同一内容;如果是读,则可能修改正在读的内容)。

这里的互斥问题是读写和写写互斥的问题,但与之前不同的是,除了实现读写和写写的互斥,我们还要实现读读的“不互斥”,即满足”读写互斥,写写互斥,读读允许“

Version1

首先准备一个信号量 rw = 1 表示当前是否有进程在访问文件(注意一开始是没有这样的进程的,1 表示的不是进程数目,是使用互斥信号量给定的初始值,代表任何时刻只有一个进程可以访问)。

在不考虑“读读不互斥”的情况下,我们的伪代码是这样的:

Writer(){               Reader(){while(1){             while(1){P(rw)                P(rw)写文件               读文件  V(rw)                V(rw)}                     }
}                      }

这个代码可以实现读写互斥和写写互斥,但显然无法实现“读读不互斥”,因为每个读进程之间也会受到 rw 的影响,使得某一时刻只能有一个读进程访问文件。

Version2

我们考虑从读进程入手,做一些改进。这里读和读不能同时进行的本质原因在于,所有的读进程都会经历“检查并上锁”这个步骤,而一个读进程进入后就会马上检查并上锁,导致另一个也想要进入的读进程被阻塞,所以我们考虑:能不能不要让所有的读进程都经历“检查并上锁”这一步骤?也就是说,某些进程可以跳过 P 操作,直接进入临界区,这样一来,这些进程就不存在在 P 操作这里被阻塞的可能性。

什么样的进程可以跳过 P 操作呢?


就是中间的那些读进程。因为一开始肯定要有读进程上锁、最后肯定要有读进程解锁,所以上锁和解锁的任务交付给第一个和最后一个进程,而中间的那些进程来去自如,只需要负责读文件,不需要参与上锁和解锁。
为了区分读进程的次序,我们准备一个 count = 0 的变量,它表示的是当前有多少个读进程正在访问文件。然后在读文件的前后,我们分别对 count 进行加一和减一的操作,每次读文件开始之前 count 会加一,所以在此之前如果变量为 0 ,说明当前读进程是第一个读进程;同理,每次读文件之后 count 会减一,所以在此之后如果变量为 0 ,说明当前读进程是最后一个读进程;

此时伪代码如下:

Reader(){while(1){if(count==0)P(rw)count++读文件count--if(count==0)V(rw)}
}

但是这样会产生一些问题。比方 1 号读进程首先进入并上锁,然后在 P 操作之后、count 加一变成 1 之前,进程切换到 2 号读进程,那么 2 号读进程就会卡在 P 操作这个地方,陷入阻塞,显然这时候无法实现我们想要的“读读不互斥”;又比方说,1 号读进程在 count 减一变成 0 之后、释放 rw 之前,进程切换到了 2 号读进程,那么 2 号同样又会被卡在 P 操作这里。所以我们还要进行改进。

问题其实就出在,对 count 的检查和赋值不是一个原子操作,这导致的结果是,如果在检查和赋值之间的空隙,进程发生切换,则必然会使得另一进程陷入阻塞。那么能不能让这两个操作一气呵成呢?事实上,可以把 count 当作是一个互斥访问的资源,对 count 的访问是互斥的,也就说明一个时间段内只能有一个读进程去访问它,即使这个过程中切换到了其它进程,那个进程也会被阻塞,从而保证只有一个进程可以访问 count,而这个访问就是检查和赋值,这种情况下,检查和赋值一定是不会被中断的。

准备一个互斥信号量 mutex = 1 表示对 count 的互斥访问,将检查和赋值封装在一个 PV 操作里。伪代码如下:

Reader(){while(1){P(mutex)if(count==0)P(rw)count++V(mutex)读文件P(mutex)count--if(count==0)V(rw)V(mutex)}
}

现在我们再来跑一下过程。
假设还是 1 号读进程运行到 P 操作的时候,进程切换到了 2 号读进程,那么由于互斥信号量 mutex 的存在,导致 2 号进程进入了 mutex 对应的阻塞队列 —— 是的,这时候看起来 2 号进程还是被阻塞了,不过我们要关注到的是,阻塞它的信号量是 mutex,不是 rw。这意味着,在进程重新切换回 1 号进程的时候,1 号进程一旦执行了 V(mutex),就可以将 2 号进程唤醒并送到就绪队列了。也就是说,尽管 2 号进程还是经历了“阻塞”这个过程,但是这个过程只是为了确保 1 号进程检查和上锁两个操作的原子性,一旦操作完成,2 号进程马上就被唤醒了。而之前那种情况不同,之前的情况是,导致 2 号进程被阻塞的是信号量 rw,除非 1 号进程读完后释放,否则 2 号进程会一直处于阻塞状态。这就是说,2 号进程永远不可能与 1 号进程同时读文件,但是改进后是可以的。

但事实上还有另一个问题更加严重——“读写不公平”。也就是说,这样的代码本质上是对读进程更有利的。


因为对读进程来说,一旦第一个读进程进来了,中间即使穿插再多的读进程,也都是允许的,他们根本不受到 rw 这个“锁”的限制;而对于写进程,它的运气就没这么好了,写进程只要想进来,就必须通过 rw 这个“锁”,而这个“锁” 实际上又掌握在最后一个读进程手里 —— 这就是说,万一读进程源源不断进来,始终轮不到最后一个读进程解锁,那么写进程就只能陷入无尽的等待了。

Version3

既然 rw 这把锁无法做到公正对待每一个进程,那我们就考虑在外层加一把“更大、更公正的锁”——所有的进程,无论读还是写,无一例外必须先通过这把“锁”的检查。为此,我们准备一个新的互斥信号量 w = 1,并将 Writer 和 Reader 的一些关键操作封装在 w 的一对 PV 操作里。此时,伪代码如下:

//用于实现对共享文件的互斥访问
semaphore rw = 1; //记录当前有几个读进程在访问文件
semaphore mutex = 1;//用于保证对count变量的互斥访问
semaphore w = 1//用于实现写优先
int count = 0; //用于记录读进程的次序writer() {while(1){P(w);P(rw)写文件V(rw);V(w);}
}reader() {while(1)P(w);P(mutex);if(count==0)	P(rw);Count++;V(mutex);V(w);读文件P(mutex); count--;if(count==0)	V(rw);V(mutex);}
}

我们来跑一下流程。
假设首先来到 1 号读进程,那么它就会执行 P 操作上锁,这个过程中即使有写进程想进来,也会被送到 w 对应的阻塞队列。在 1 号读进程执行到 V 操作之后,写进程才会被唤醒并送到就绪队列,之后就轮到写进程执行了,而写进程虽然通过第一个 P 操作,但是被卡在了第二个 P 操作(读进程尚未释放 rw),所以他来到了 rw 对应的阻塞队列。

注意!重点来了,如果这时候 2 号读进程也想要访问文件,那么在以前,它是不需要通过任何检查就可以直接来读文件的,并且直到 2 号读进程释放 rw 之后,写进程才能真正来执行写文件的操作。但是现在由于我们加了一把“更大的锁w,导致 2 号进程必须先通过 w 的检查,而由于写进程抢先在他之前上了锁,所以 2 号读进程被送到了 w 对应的阻塞队列。也就是说,现在的情况是:写进程等着 1 号读进程释放 rw,而 2 号读进程等着写进程释放 w,1 号读进程是让一切正常进行下去的关键。在处理机又来到 1 号读进程并执行 V(rw) 之后,写进程从 rw 的阻塞队列被唤醒,继续往下执行写文件的操作。而在写进程真正执行完之后,w 才能得到释放,由此又唤醒了 w 阻塞队列中的 2 号读进程,2 号读进程来到处理机运行。

如果换一种情况,是按照 写者 — 读者 — 写者的顺序,那么由于读者在第二个写者之前,所以是读者作为阻塞队列队头,第二个写者则次之,在后续执行过程中,根据队列“先进先出”的原则,也会是读者先于第二个写者访问文件。

综上,这种情况下,实际上谁先到、谁就在后续过程中先被执行(而不是像之前,无论写进程先还是后,读进程都可以“无视规则”抢先一步执行)。由此,我们就实现了“读写公平”。

总结

上文根据王道课上给的案例进行的分析,博主自身在理解这里的时候感觉不是很好记忆,自己结合老师上课的讨论摸索了一套方法解决这个问题。(信号量命名和王道不一致)

首先是解决读者优先问题,设置一个balance信号量(也有写写、写读互斥的作用),解决读写互斥放一个mutex信号量(读的时候不能写),读读允许同样设置一个count计数,配套设置cmutex解决count计数的原子操作。

具体实现思路如下

  1. 先设置好信号量初值
semaphore mutex = 1;
semaphore cmutex = 1;
semaphore balance = 1;
int count = 0;
  1. 然后对写者进程进行分析
writer() {while(1) {P(balance); // 读写平衡P(mutex); // 读写互斥写文件...P(mutex); V(balance); }
}
  1. 对于读者进程进行分析
reader() {while(1) {P(balance); // 读写平衡P(cmutex);  // count操作互斥if(count == 0) P(mutex); //读写互斥count--;V(cmutex);V(balance);读文件...P(cmutex); // count操作互斥count--;if(count == 0) V(mutex);V(cmutex);}
}
  • 读写互斥→mutex(斥)
  • 读读允许→cmutex、count(允)
  • 解决读者优先→balance(平衡)

由于读者写者问题确实有他自身的复杂性,所以一定要有自己的理解,不然很容易就不记得该如何解决,按照演绎的顺序就是三个信号量(一斥二允三平衡)+一个计数器count。

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

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

相关文章

C++初阶学习第七弹——探索STL奥秘(二)——string的模拟实现

标准库中的string:C初阶学习第六弹——string(1)——标准库中的string类-CSDN博客 前言: 在前面我们已经学习了如何使用标准库中的string类,但作为一个合格的程序员,我们不仅要会用,还要知道如…

网络库-libevent介绍

1.简介 libevent是一个事件驱动的网络库,主要用于构建可扩展的网络服务器。它提供了跨平台的API,支持多种事件通知机制,如select、poll、epoll、kqueue等。 主要组件 event: 表示一个具体的事件,包括事件类型、事件回调等。eve…

房屋出租管理系统需求分析及功能介绍

房屋租赁管理系统适用于写字楼、办公楼、厂区、园区、商城、公寓等商办商业不动产的租赁管理及租赁营销;提供资产管理,合同管理,租赁管理, 物业管理,门禁管理等一体化的运营管理平台,提高项目方管理运营效率…

如何查看centos7是否安装nginx

要查看 CentOS 7 系统上是否安装了 Nginx,您可以使用多种方法来检查。以下是一些常见的方法: 通过 RPM 包管理器查询 在 CentOS 系统上,可以使用 RPM 包管理器来查询已安装的软件包。要查看是否安装了 Nginx,您可以在终端中运行以…

【C++】学习笔记——继承_1

文章目录 十一、模板进阶5. 模板的优缺点 十二、继承1. 继承的概念及定义2. 基类和派生类对象赋值转换3. 继承中的作用域4. 派生类的默认成员函数 未完待续 十一、模板进阶 5. 模板的优缺点 优点: 模板复用了代码,节省资源,更快的迭代开发&a…

某银行软件测试笔试题,满分一百你能得多少分?

时间90分钟,满分100分) 考试要求:计算机相关专业试题 一、填空题(每空1分,共10分) 1. ______验证___是保证软件正确实现特定功能的一系列活动和过程。 2. 按开发阶段分,软件测试可分为&#x…

SSIM(Structural Similarity),结构相似性及MATLAB实现

参考文献 Wang, Zhou; Bovik, A.C.; Sheikh, H.R.; Simoncelli, E.P. (2004-04-01). “Image quality assessment: from error visibility to structural similarity”. IEEE Transactions on Image Processing. 13 (4): 600–612. Bibcode:2004ITIP…13…600W. CiteSeerX 10.…

YOLO数据集制作(二)|json文件转txt验证

以下教程用于验证转成YOLO使用的txt格式,适用场景:矩形框,配合json格式文件转成YOLO使用的txt格式脚本使用。 https://blog.csdn.net/StopAndGoyyy/article/details/138681454 使用方式:将img_path和label_path分别填入对应的图…

Android Studio开发之路(九)创建android library以及生成aar文件

一、需求 我做了一个camerax相机opencv图像处理图片上传服务器功能的android应用,应客户需求要将其改成一个SDK,由客户加到他们自己的app里边。 于是,我需要制作一个library,打包成aar文件(jar:只有代码,没…

YOLOv5改进 | 注意力机制 | 用于移动端的高效坐标CA注意力机制

在深度学习目标检测领域,YOLOv5成为了备受关注的模型之一。本文给大家带来的是能用于移动端的高效坐标CA注意力机制。文章在介绍主要的原理后,将手把手教学如何进行模块的代码添加和修改,并将修改后的完整代码放在文章的最后,方便…

打破地域界限,HubSpot海外获客系统引领企业走向国际化

在全球化的浪潮中,企业如何精准把握海外市场、高效获取并转化目标客户,已成为决定其市场地位与未来发展的关键因素。HubSpot海外获客系统以其独特的视角、强大的功能和卓越的性能,正在引领全球营销进入一个新的时代。今天运营坛将深入剖析Hub…

交易复盘-20240513

仅用于记录当天的市场情况,用于统计交易策略的适用情况,以便程序回测 短线核心:不参与任何级别的调整,采用龙空龙模式 一支股票 10%的时候可以操作, 90%的时间适合空仓等待 双成药业 (1)|[9:30]|[3566万]|0.34 中通客车 (1)|[9:43]|[7678万]|0.15 嘉华股份 (2)|[9:30]|[36…

基于Springboot的大学生平时成绩量化管理系统(有报告)。Javaee项目,springboot项目。

演示视频: 基于Springboot的大学生平时成绩量化管理系统(有报告)。Javaee项目,springboot项目。 项目介绍: 采用M(model)V(view)C(controller)三…

Spring Boot日志

目录 一、日志概述 1、为什么要学习日志? 2、日志的用途 (1)系统监控 (2)数据采集 (3)日志审计 二、日志使用 1、打印日志 (1)在程序中得到日志对象 &#xf…

WebView基础知识以及Androidx-WebKit的使用

文章目录 摘要WebView基础一、启动调整模式二、WebChromeClient三、WebViewClient四、WebSettings五、WebView和Native交互 Androidx-WebKit一、启动安全浏览服务二、设置代理三、安全的 WebView 和 Native 通信支持四、文件传递五、深色主题的支持六、JavaScript and WebAssem…

自主实现Telnet流量抓取

自主实现Telnet流量抓取 根据测试需求,需要抓取Telnet流量包,使用wireshark Python(socket、telnetlib库)实现 实现代码 主要此处有坑, 根据协议规则,wireshark 默认端口为23 的是Telnet协议&#xff0…

3D模型实时变形算法

最近,在尝试渲染一些奇怪的形状后,我陷入了计算机图形学的困境。事实证明,对于我试图解决的具体问题,没有现有的选项完全适合我想要做的事情。几周后,我终于带着一些答案再次浮出水面,写了很多行代码&#…

DS:顺序表、单链表的相关OJ题训练(2)

欢迎各位来到 Harper.Lee 的学习世界! 博主主页传送门:Harper.Lee的博客主页 想要一起进步的uu欢迎来后台找我哦! 一、力扣--141. 环形链表 题目描述:给你一个链表的头节点 head ,判断链表中是否有环。如果链表中有某个…

HTML学习|网页基本信息、网页基本标签、图像标签、超链接标签、列表标签、表格标签、媒体元素、页面结构分析、iframe内联框架

网页基本信息 DOCTYPE是设置使用什么规范,网页整个信息都在html标签中,head标签里包含字符集设置,网页介绍等信息,title标签是网页的名称,网页的主干都在body标签中 网页基本标签 标题标签 h1~h6都是标题标签&#x…

2024数维杯数学建模A题B题C题思路+模型+代码(开赛后第一时间更新)

2024数维杯数学建模A题B题C题思路模型代码(开赛后第一时间更新) https://mbd.pub/o/bread/ZpWakpdq https://mbd.pub/o/bread/ZpWakpdq 2024年第九届数维杯大学生数学建模挑战赛参赛规则 竞赛要求及论文提交方式; ①本次参赛作品统一在线提交到竞赛…