首页 > 系统相关 >【操作系统-进程】PV操作——读者写者问题

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

时间：2022-10-18 23:35:09浏览次数：55  
标签：busy PV 操作系统 -- 写者 互斥 读者 进程

目录

读者写者问题万能模板

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

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

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

int count = 0; // 记录正在访问的进程数量
信号量 busy = 1; // “完成事件”的互斥锁
信号量 mutex = 1; // 变量 count 的互斥锁

Process(){
    while(1){
        P(mutex);
        count++; // 访问资源的进程数量加 1
        if (count == 1){ // （1）如果发现自己是第一个访问的进程，需要负责加锁
            P(busy);
        }
        V(mutex);
        
        完成事件; // （2）访问临界资源、完成临界事件
        
        P(mutex);
        count--; // 访问完毕，访问资源的进程数量减 1
        if (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操作实现交通管理以防止桥上堵塞。

image

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

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 的互斥
    }
}

标签：busy,PV,操作系统,--,写者,互斥,读者,进程
From： https://www.cnblogs.com/Mount256/p/16804609.html

相关文章

  • 嵌入式操作系统
    这是一篇关于关于嵌入式Linux操作系统知识点的文章，希望通过此，大家能温故了解Linux和嵌入式的知识点概念。1.Linux系统组成用户角度：由内到外，依次是：内核-》系统程序（工具）-......
  • ipv4/ipv6正则校验
    functionis_ipv4(str){ varreg=/^((25[0-5]|2[0-4]\d|1\d\d|[1-9]\d|\d).){3}(25[0-5]|2[0-4]\d|1\d\d|[1-9]\d|\d)$/; returnreg.test(str);}functionis_ipv6(str......
  • 操作系统面试题01
    01、进程和线程的区别1、进程进程是资源分配的基本单位。进程控制块(ProcessControlBlock,PCB)描述进程的基本信息和运行状态，所谓的创建进程和撤销进程，都......
  • ipv4数据报格式及相关计算
       看起来一头雾水，其实这里主要考我们，ipv4数据报的格式理解。考点：1. ipv4的数据报格式      2. 进制转化      3. ipv4首部长度（单......
  • JAVA获取jvm和操作系统相关信息
    JAVA获取jvm和操作系统相关信息背景今日搬砖......
  • 如何计算QPS、PV和需要部署机器数量？
    基本概念网站访问量的常用衡量标准：独立访客(UV)和综合浏览量（PV）,一般以日为单位来计算。独立访客(UV)：指一定时间范围内相同访客多次访问网站，只计算为1个独立访客。综合......
  • IPV4网段划分
    原文链接：https://www.cnblogs.com/GHzcx/p/8979077.htmlIPV4的地址分类及网络号的范围如下：  A类地址（1）A类地址第1字节为网络地址，其它3个字节为主机地址。（2）A......
  • GroupViT: Semantic Segmentation Emerges from Text Supervision论文阅读笔记
    摘要在端到端深度学习系统中，图像区域的分组通常是通过像素级识别标签的自上而下的监督而隐式发生。在本文中，作者将分组机制带回深度网络中，这使得语义分割可以在只有文本信......
  • FPV
    介绍FPV是英文FirstPersonView的缩写，及第一人称视角，是一种基于遥控航模或者车辆模型上加装无限摄像头回传设备，通过远程来查看画面、操作模型的玩法。相关设备FPV系统的主......
  • LVS VS-TUN ipvsadm+heartbeat-ldirectord搭建linux集群
    ​测试环境一台调度机，两台真实机，使用ipvsadm+ldirectord搭建vs-tun的linux集群3台服务器都安装centos5.4调度机IP：eth0：192.168.11.10调度机VIP：eth0:0：192.168.11.20真实机1IP：e......

赞助商

阅读排行

网站主页关于我们联系我们网站地图

本网站内容转载自其他媒体，侵权联系[admin##ips99.com]。

Copyright © 2020-2023 IPS99 版权所有 IPS99