【操作系统-进程】PV操作——读者写者问题

article/2025/9/30 9:55:43

文章目录

    • 读者写者问题万能模板
      • 万能模板 1——读进程优先
      • 万能模板 2——读写公平法
      • 万能模板 3——写进程优先
    • 题目 1：南北过桥问题
    • 题目 2：录像厅问题
    • 题目 3：更衣问题

读者写者问题万能模板

读者写者问题，其本质就是连续多个同类进程访问同一个临界资源的问题。

第一个进程开始访问临界资源前，需要对资源加上互斥锁，后面的进程再访问时就不用再对资源加互斥锁了，直到最后一个进程访问完后，发现自己是最后一个进程，就解锁互斥锁。这就像一种情况：第一个人进房间时必须顺手开门，后面进来的人和离开的人就不用开门，直到最后一个人离开房间时才需要顺手关门。

代码的通用模板是“三段式”，如下：

int count = 0; // 记录正在访问的进程数量
信号量 busy = 1; // “完成事件”的互斥锁
信号量 mutex = 1; // 变量 count 的互斥锁Process(){while(1){P(mutex);count++; // 访问资源的进程数量加 1if (count == 1){ // （1）如果发现自己是第一个访问的进程，需要负责加锁P(busy);}V(mutex);完成事件; // （2）访问临界资源、完成临界事件P(mutex);count--; // 访问完毕，访问资源的进程数量减 1if (count == 0){ // （3）如果发现自己是最后一个访问的进程，需要负责解锁V(busy);}V(mutex);}
}

理解了最基本的原理后，下面来正式讨论读者写者问题。

【读者写者问题】有读者和写者两组并发进程，共享一个文件，当两个或两个以上的读进程（只是读数据，不会对数据产生影响，而消费者读数据时，会将数据取走，因此不能两个消费者一起读数据）同时访问共享数据时不会产生副作用，但若某个写进程和其他进程（读进程或写进程）同时访问共享数据时则可能导致数据不一致的错误。

因此要求:

  • 允许多个读者可以同时对文件执行读操作；
  • 只允许一个写者往文件中写信息；
  • 任一写者在完成写操作之前不允许其他读者或写者工作；
  • 写者执行写操作前，应让已有的读者和写者全部退出。

万能模板 1——读进程优先

即使写者发出了请求写的信号，但是只要还有读者在读取内容，就还允许其他读者继续读取内容，直到所有读者结束读取，才真正开始写。

int count = 0;
信号量 busy = 1; // “读文件”和“写文件”的互斥锁
信号量 mutex = 1; // 变量 count 的互斥锁Reader(){ // 读者进程while(1){P(mutex);count++; if (count == 1){ P(busy);}V(mutex);读文件; P(mutex);count--; if (count == 0){ V(busy);}V(mutex);}
}Writer(){ // 写者进程while(1){P(busy);写文件;V(busy);}
}

如果读者写者到达的顺序是：读者 1–读者2–读者 3–写者 A–读者 4–写者 B–读者 5，则：

  • 读者 1、读者 2、读者 3 到达，busy 加锁，开始读；
  • 写者 A 到达，但是读者还在读，未释放 busy 锁，因此不能写；
  • 读者 4 到达，可以开始读；
  • 写者 B 到达，但是读者还在读，未释放 busy 锁，因此不能写；
  • 读者 5 到达，可以开始读；
  • 等到读者们都读完，释放 busy 锁，写者才可以开始写。

万能模板 2——读写公平法

读写进程都要排队进行操作文件。即使里面有读进程在操作文件，读进程也要和写进程一起排队。

int count = 0;
信号量 queue = 1; // 实现“读写公平”的互斥锁，可以视为一个队列
信号量 busy = 1; // “读文件”和“写文件”的互斥锁
信号量 mutex = 1; // 变量 count 的互斥锁Reader(){ // 读者进程while(1){P(queue); // 在无写进程请求时不需要进入队列P(mutex); // 该互斥量实际上是多余的，上面语句已经兼有互斥功能count++; if (count == 1){ P(busy);}V(mutex); // 该互斥量实际上是多余的，下面语句已经兼有互斥功能V(queue); // 恢复对共享文件的访问读文件; P(mutex);count--; if (count == 0){ V(busy);}V(mutex);}
}Writer(){ // 写者进程while(1){P(queue); // 在无其他写进程请求时不需要进入队列P(busy);写文件;V(busy);V(queue); // 恢复对共享文件的访问}
}

如果读者写者到达的顺序是：读者 1–读者2–读者 3–写者 A–读者 4–写者 B–读者 5，则：

  • 读者 1、读者 2、读者 3 到达，busy 加锁，开始读；
  • 写者 A 到达，queue 加锁，但是读者还在读，busy 锁仍未释放，因此不能写；
  • 读者 4 到达，但是读者还在读，queue 和 busy 锁仍未释放，不能开始读；
  • 写者 B 到达，queue 锁和 busy 锁仍未释放，因此不能写；
  • 读者 5 到达，但是读者还在读，queue 和 busy 锁仍未释放，不能开始读；
  • 等到读者 1 到 3 都读完，释放 busy 锁，写者 A 才可以开始写；
  • 接下来就是按读者 4、写者 B、读者 5 的顺序依次访问文件。

实际上，读写公平法也可以不用任何除了访问文件外的互斥锁：

信号量 busy = 1; // 也可以视为一个队列Reader(){ // 读者进程while(1){P(busy);读文件;V(busy);}
}Writer(){ // 写者进程while(1){P(busy);写文件;V(busy);}
}

万能模板 3——写进程优先

如果有写者申请写文件，那么在申请之前还在读取文件的读进程可以继续读取，但是如果再有读者申请读取文件，则不能够读取，只有在所有的写者写完之后才可以读取。

int ReaderCount = 0; // 读者数量
int WriterCount = 0; // 写者数量
信号量 Read = 1; // “读文件”的互斥锁
信号量 Write = 1; // “写文件”的互斥锁
信号量 ReaderMutex = 1; // 变量 ReaderCount 的互斥锁
信号量 WriterMutex = 1; // 变量 WriterCount 的互斥锁Reader(){ // 读者进程while(1){P(Read); // 每个读进程都需要对 Read 加锁P(ReaderMutex); // 对 ReadCount 的互斥，实际上，上条语句已经兼有此功能，可以去掉ReaderCount++; if (ReaderCount == 1){ // 如果是第一个读进程P(Write); // 则对写者上锁}V(ReaderMutex); // 对 ReadCount 的互斥，实际上，下条语句已经兼有此功能，可以去掉V(Read); // Read 解锁读文件; P(ReaderMutex); // 对 ReadCount 的互斥ReaderCount--; if (ReaderCount == 0){ // 如果是最后一个读进程V(Write); // 则对写者解锁}V(ReaderMutex); // 对 ReadCount 的互斥}
}Writer(){ // 写者进程while(1){P(WriterMutex); // 对 WriterCount 的互斥WriterCount++; if (WriterCount == 1){ // 如果是第一个写进程P(Read); // 则对读者上锁}V(WriterMutex); // 对 WriterCount 的互斥P(Write); // Write 加锁写文件; V(Write); // Write 解锁P(WriterMutex); // 对 WriterCount 的互斥WriterCount--; if (WriterCount == 0){ // 如果是最后一个写进程V(Read); // 则对读者解锁}V(WriterMutex); // 对 WriterCount 的互斥}
}

如果读者写者到达的顺序是：读者 1–读者2–读者 3–写者 A–读者 4–写者 B–读者 5，则：

  • 读者 1、读者 2、读者 3 到达，Write 加锁，开始读；
  • 写者 A 到达，Read 加锁，但是读者还在读，Write 锁仍未释放，因此不能写；
  • 读者 4 到达，Read 锁仍未释放，不能开始读；
  • 写者 B 到达，Write 锁仍未释放，因此不能写；
  • 读者 5 到达，Read 锁仍未释放，不能开始读；
  • 等到读者 1 到 3 都读完，释放 Write 锁，写者 A 才可以开始写，写完后 Write 解锁。由于写者 A 不是最后一个写进程，因此 Read 不解锁；
  • 写者 B 进行写操作，写完后 Write 解锁，由于写者 B 是最后一个写进程，因此 Read 解锁；
  • 读者 4、读者 5 依次进行读操作。

题目 1：南北过桥问题

【题目 1】有桥如下图所示，车流如箭头所示，桥上不允许两车交汇，但允许同方向多辆车依次通过（即桥上可以有多个同方向的车）。用P、V操作实现交通管理以防止桥上堵塞。

在这里插入图片描述

【解答】直接套“三段式”，如下：

int count1 = 0; // 北到南的车辆数
int count2 = 0; // 南到北车辆数
信号量 bridge = 1;
信号量 mutex1 = 1;
信号量 mutex2 = 1;北到南(){P(mutex1);count1++;if (count1 == 1){P(bridge);}V(mutex1);北到南过桥;P(mutex1);count1--;if (count1 == 0){V(bridge);}V(mutex1);   
}南到北(){P(mutex2);count2++;if (count2 == 1){P(bridge);}V(mutex2);南到北过桥;P(mutex2);count2--;if (count2 == 0){V(bridge);}V(mutex2);   
}

题目 2：录像厅问题

【题目 2】假设一个录像厅有 0,1,2 三种不同的录像片可由观众选择放映。录像厅的放映规则为：

  • 任何时刻最多只能放映一种录像片，正在放映的录像片是自动循环放映的。最后一个观众主动离开时结束当前录像片的放映。
  • 选择当前正在放映录像片的观众可立即进入，允许同时有多位选择同一中录像片的观众同时观看，同时观看的观众数量不受限制。
  • 等待观看其他录像片的观众按到达顺序排队，当一种新的录像片开始放映时，所有等待观看该录像片的观众可一次进入录像厅同时观看。

【解答 1】本题也可以直接套“三段式”，如下：

int count0 = 0; // 看影片 0 的观众数
int count1 = 0; // 看影片 1 的观众数
int count2 = 0; // 看影片 2 的观众数
信号量 movie = 1;
信号量 mutex0 = 1;
信号量 mutex1 = 1;
信号量 mutex2 = 1;看影片0的观众(){P(mutex0);count0++;if (count0 == 1){P(movie);}V(mutex0);看影片0;P(mutex0);count0--;if (count0 == 0){V(movie);}V(mutex0);
}看影片1的观众(){P(mutex1);count1++;if (count1 == 1){P(movie);}V(mutex1);看影片1;P(mutex1);count1--;if (count1 == 0){V(movie);}V(mutex1);
}看影片2的观众(){P(mutex2);count2++;if (count2 == 1){P(movie);}V(mutex2);看影片2;P(mutex2);count2--;if (count2 == 0){V(movie);}V(mutex2);
}

【解答 2】借助“写进程优先”的思想，观看某影片的观众在进去前，可以先把要观看其他影片的观众先上锁，让他们暂时阻塞，如下：

int count0 = 0; // 看影片 0 的观众数
int count1 = 0; // 看影片 1 的观众数
int count2 = 0; // 看影片 2 的观众数
信号量 mutex0 = 1; // 影片 0 的互斥锁，兼有对变量 count0 的互斥功能
信号量 mutex1 = 1; // 影片 1 的互斥锁，兼有对变量 count1 的互斥功能
信号量 mutex2 = 1; // 影片 2 的互斥锁，兼有对变量 count2 的互斥功能看影片0的观众(){P(mutex0);count0++;if (count0 == 1){ // 第一个进去的观众把其他影片的观众“挡住”P(mutex1);P(mutex2);}V(mutex0);看影片0;P(mutex0);count0--;if (count0 == 0){ // 最后一个出来的观众允许其他影片的观众进来V(mutex1);V(mutex2);}V(mutex0);
}看影片1的观众(){P(mutex1);count1++;if (count1 == 1){ // 第一个进去的观众把其他影片的观众“挡住”P(mutex0);P(mutex2);}V(mutex1);看影片1;P(mutex1);count1--;if (count1 == 0){ // 最后一个出来的观众允许其他影片的观众进来V(mutex0);V(mutex2);}V(mutex1);
}看影片2的观众(){P(mutex2);count2++;if (count2 == 1){ // 第一个进去的观众把其他影片的观众“挡住”P(mutex0);P(mutex1);}V(mutex2);看影片2;P(mutex2);count2--;if (count2 == 0){ // 最后一个出来的观众允许其他影片的观众进来V(mutex0);V(mutex1);}V(mutex2);
}

看似没毛病吧。然而，事实上这段代码是有问题的，可能会引发死锁，哈哈哈……你发现了吗？

题目 3：更衣问题

【题目 3】某男⼦⾜球俱乐部，有教练、队员若⼲。每次⾜球训练开始之前，教练、球员都需要先进⼊更⾐室换⾐服，可惜俱乐部只有⼀个更⾐室。教练们脸⽪薄，⽆法接受和别⼈共⽤更⾐室。队员们脸⽪厚，可以和其他队员⼀起使⽤更⾐室。如果队员和教练都要使⽤更⾐室，则应该让教练优先。请使⽤ P、V 操作描述上述过程的互斥与同步，并说明所⽤信号量及初值的含义。

【解答】把教练视为写进程，把队员视为读进程，更衣室视为缓冲区，则该题需要实现的“写进程优先”。如下：

int ReaderCount = 0; // 读者数量
int WriterCount = 0; // 写者数量
信号量 Read = 1; // “读文件”的互斥锁
信号量 Write = 1; // “写文件”的互斥锁
信号量 ReaderMutex = 1; // 变量 ReaderCount 的互斥锁
信号量 WriterMutex = 1; // 变量 WriterCount 的互斥锁Reader(){ // 读者进程（相当于教练）while(1){P(Read); // 每个读进程都需要对 Read 加锁P(ReaderMutex); // 对 ReadCount 的互斥ReaderCount++; if (ReaderCount == 1){ // 如果是第一个读进程P(Write); // 则对写者上锁}V(ReaderMutex); // 对 ReadCount 的互斥V(Read); // Read 解锁读文件; P(ReaderMutex); // 对 ReadCount 的互斥ReaderCount--; if (ReaderCount == 0){ // 如果是最后一个读进程V(Write); // 则对写者解锁}V(ReaderMutex); // 对 ReadCount 的互斥}
}Writer(){ // 写者进程（相当于队员）while(1){P(WriterMutex); // 对 WriterCount 的互斥WriterCount++; if (WriterCount == 1){ // 如果是第一个写进程P(Read); // 则对读者上锁}V(WriterMutex); // 对 WriterCount 的互斥P(Write); // Write 加锁写文件; V(Write); // Write 解锁P(WriterMutex); // 对 WriterCount 的互斥WriterCount--; if (WriterCount == 0){ // 如果是最后一个写进程V(Read); // 则对读者解锁}V(WriterMutex); // 对 WriterCount 的互斥}
}

http://chatgpt.dhexx.cn/article/1vpKdOAq.shtml

相关文章

经典进程同步问题（三）——读者写者问题

经典进程同步问题（三）——读者写者问题

目录 一、问题描述 二、解题思路 2.1 读者优先算法 2.2 写者优先算法 2.3 读写公平 三、源码实现 3.1 读者优先 3.2 写者优先 3.3 读写平等 一、问题描述 一个数据问价或记录可以被多个进程共享，我们把只读该文件的进程称为“读者进程”，其他进…
阅读更多...
2. 堆与栈的区别

2. 堆与栈的区别

2. 堆与栈的区别 在理解这两个概念时，需要放到具体的场景下，因为不同场景下，堆与栈代表不同的含义。一般情况下，有两层含义： （1）程序内存布局场景下，堆与栈表示的是两种内存管理方式…
阅读更多...
栈与堆的区别（内存分配与数据结构）

栈与堆的区别（内存分配与数据结构）

参考自https://blog.csdn.net/K346K346/article/details/80849966/ 堆（Heap）与栈（Stack）包含两层含义： 程序内存布局场景下的内存管理方式数据结构中的两种常见的数据结构 1. 程序内存分配中的堆与栈 1.1 栈介绍 …
阅读更多...
C语言里栈和堆的区别整理

C语言里栈和堆的区别整理

这里说的是C语言程序内存分配中的堆和栈。下面先谈谈C语言的内存管理： 可执行程序在存储时（没有调到内存）分为代码区（text）、数据区（data）和未初始化数据区（bss）3个部分。…
阅读更多...
看懂堆与栈的区别与联系

看懂堆与栈的区别与联系

<div class"simditor-body clearfix" style"height: auto; overflow: inherit;"><h2> <strong>　　堆和栈概要</strong></h2>在计算机领域&#xff0c;堆栈是一个不容忽视的概念&#xff0c;堆栈是两种数据结构。堆栈都是一…
阅读更多...
C语言：栈和堆的区别

C语言：栈和堆的区别

c语言五大内存分区 栈区&#xff08;stack&#xff09;:存放函数形参和局部变量&#xff08;auto类型&#xff09;&#xff0c;由编译器自动分配和释放 堆区&#xff08;heap&#xff09;:该区由程序员申请后使用&#xff0c;需要手动释放否则会造成内存泄漏。如果程序员没有手…
阅读更多...
什么是栈（Stack）？什么是堆（Heap）？栈和堆的区别是什么？

什么是栈（Stack）？什么是堆（Heap）？栈和堆的区别是什么？

原参考地址&#xff1a;https://zhidao.baidu.com/question/36918441.html 栈&#xff1a;由操作系统自动分配释放 &#xff0c;存放函数的参数值&#xff0c;局部变量du的值等。其操作方式类似于数据结构中的栈&#xff1b; 堆&#xff1a; 一般由程序员分配释放&#xff0c…
阅读更多...
堆和栈的概念和区别

堆和栈的概念和区别

在说堆和栈之前&#xff0c;我们先说一下JVM&#xff08;虚拟机&#xff09;内存的划分&#xff1a; Java程序在运行时都要开辟空间&#xff0c;任何软件在运行时都要在内存中开辟空间&#xff0c;Java虚拟机运行时也是要开辟空间的。JVM运行时在内存中开辟一片内存区域&#x…
阅读更多...
堆与栈的区别详细总结

堆与栈的区别详细总结

1、堆与栈的区别详细总结_Fighting的博客-CSDN博客_堆和栈的区别 2、堆和栈的区别 - 江雨牧 - 博客园 3、堆和栈的区别_内外皆秀的博客-CSDN博客_堆和栈的区别 4、一文读懂堆与栈的区别_恋喵大鲤鱼的博客-CSDN博客_堆和栈的区别 一般情况下&#xff0c;如果有人把堆栈合起来…
阅读更多...
栈和堆的区别

栈和堆的区别

栈和堆的区别 前面已经介绍过&#xff0c;栈是由编译器在需要时分配的&#xff0c;不需要时自动清除的变量存储区。里面的变量通常是局部变量、函数参数等。堆是由malloc()函数分配的内存块&#xff0c;内存释放由程序员手动控制&#xff0c;在C语言为free函数完成。栈和堆的主…
阅读更多...
Struts常见面试题

Struts常见面试题

Struts分为Struts1和Struts2&#xff0c;默认情况下指的是Struts2&#xff0c;Struts1除非特别说明。 1、Struts2 中的 # 和 % 分别是做什么的&#xff1f; &#xff08;1&#xff09;使用#获取 context 里面的数据 <s:iterator value “list” var”user”> <s:p…
阅读更多...
关于Struts2的笔试题（一）

关于Struts2的笔试题（一）

一. struts2框架中struts.xml配置文件,package标签的属性有那几个?各有什么功能? 1.name属性 作用:定义一个包的名称&#xff0c;它必须唯一。 2.namespace属性 作用:主要是与action标签的name属性联合使用来确定一个action 的访问路径 3.extends属性 作用:指定继承自哪个…
阅读更多...
Struts2详述一（struts2基础及2个核心）

Struts2详述一（struts2基础及2个核心）

临近大学毕业了&#xff0c;在毕业之前做点大学学到的知识和总结。如有哪些方面存在错误还望大神见谅。 首先&#xff0c;这里想从SSH这三大框架说起。首选从最简单的Struts2说起。这一篇我将讲述struts2一些基础及2个核心&#xff08;Action和result&#xff09;,下篇我们将着…
阅读更多...
【面试】【Struts2常见问题总结】【02】

【面试】【Struts2常见问题总结】【02】

【常见面试问题总结目录>>>】 031 struts2如何对指定的方法进行验证&#xff1f; 1.validate()方法会校验action中所有与execute方法签名相同的方法&#xff1b; 　　2.要校验指定的方法通过重写validateXxx()方法实现&#xff0c; validateXxx()只会校验action中方法…
阅读更多...
【面试】【Struts2常见问题总结】【01】

【面试】【Struts2常见问题总结】【01】

【常见面试问题总结目录>>>】 001 请简述struts1的工作流程和机制&#xff1a; Struts的工作流程: 　　在web应用启动时就会加载初始化ActionServlet,ActionServlet从 　　struts-config.xml文件中读取配置信息,把它们存放到各种配置对象 　　当ActionServlet接收到…
阅读更多...
一道Struts面试题

一道Struts面试题

题目是这样的 有两张表 一张为新闻类别表 有&#xff12;个字段&#xff1a; nid(pk) sort 有一张新闻内容表 有三个字段 cid(pk) nid(fk) title content 要求通过下拉列表框的方法选择新闻类别然后显示该类别的新闻标题&#xff08;在当前…
阅读更多...
Java面试----2018年最新Struts2面试题

Java面试----2018年最新Struts2面试题

1、描述Struts2的工作原理 答:客户端发送请求--》请求经过一系列过滤器--》FilterDispatcher通过ActionMapper来决定这个Request需要调用哪个Action --》FilterDispatcher把请求的处理交给ActionProxy--》通过ConfigurationManager询问Struts配置文件&#xff08;Struts.xml&a…
阅读更多...
Struts2面试问题

Struts2面试问题

转载自 Struts2面试问题 1.什么是Struts2&#xff1f; Apache Struts2是一个用Java构建Web应用程序的开源框架。Struts2基于OpenSymphony WebWork框架。它从Struts1中得到了很大的改进&#xff0c;使其更加灵活&#xff0c;易于使用和扩展。Struts2的核心组件是Action&…
阅读更多...
查看es的tcp和http端口

查看es的tcp和http端口

1、登录linux部署服务器&#xff0c;用命令查找配置文件elasticsearch.yml&#xff0c;如图 find -name elasticsearch.yml 2、进到elasticsearch.yml文件的目录 3、查看tcp&#xff0c;http端口
阅读更多...
w10查看端口_Windows 10系统如何查看已打开的端口

w10查看端口_Windows 10系统如何查看已打开的端口

最近Win10用户反映&#xff0c;电脑很经常中病毒&#xff0c;用户表示并没有在电脑上插入U盘&#xff0c;也没有打开不安全的网页&#xff0c;但就是一直中毒&#xff0c;这让用户非常苦恼。其实&#xff0c;出现这一问题&#xff0c;可能与电脑开启了一些端口有关&#xff0c;…
阅读更多...
推荐文章

Copyright @ 2022~2023