PV操作经典例题

提示：文章写完后，目录可以自动生成，如何生成可参考右边的帮助文档

文章目录

  • 一、前言🚀🚀🚀
  • 二、正文☀️☀️☀️
    • 1.水果问题
    • 2.和尚打水问题
    • 3.餐厅职员问题
    • 4.汽车站点问题
    • 5.观察者-报告者问题
    • 6..阅览室问题
  • 三、总结🍓🍓🍓

一、前言🚀🚀🚀

在这里插入图片描述
像极了程序员修BUG

二、正文☀️☀️☀️

1.水果问题

桌上有一个盘子，可以放一个水果；
父亲总是放苹果到盘子中；
母亲总是放香蕉到盘子中。
一个儿子专等吃盘中的香蕉；
而一个女儿专等吃盘中的苹果。
父母只放水果不吃，儿女只吃水果不放。
实现父亲，母亲，儿子，女儿的进程同步。
用PV操作实现下述问题的解

在这个问题中，我们可以定义以下信号量：

empty：表示盘子是否为空，初始值为1（盘子初始为空）
apple：表示是否有一个苹果在盘子中，初始值为0（没有苹果）
banana：表示是否有一个香蕉在盘子中，初始值为0（没有香蕉）	

semaphore empty = 1;  // 盘子为空  
semaphore apple = 0;  // 盘子中没有苹果  
semaphore banana = 0; // 盘子中没有香蕉  // 父亲的进程  
father() {  while (true) {  P(empty);  // 等待盘子为空  // 放置苹果到盘子中  V(apple);  // 盘子中有苹果了  // 父亲不吃苹果，继续循环  }  
}  // 母亲的进程  
mother() {  while (true) {  P(empty);  // 等待盘子为空  // 放置香蕉到盘子中  V(banana); // 盘子中有香蕉了  // 母亲不吃香蕉，继续循环  }  
}  // 儿子的进程  
son() {  while (true) {  P(banana); // 等待盘子中有香蕉  // 从盘子中取出香蕉吃  V(empty);  // 盘子空了  // 儿子吃完香蕉，继续等待下一个香蕉  }  
}  // 女儿的进程  
daughter() {  while (true) {  P(apple);  // 等待盘子中有苹果  // 从盘子中取出苹果吃  V(empty);  // 盘子空了  // 女儿吃完苹果，继续等待下一个苹果  }  
}

在这个实现中，P(empty)操作确保在放置新的水果之前盘子是空的，V(apple)或V(banana)操作表示已经在盘子中放置了苹果或香蕉，并且P(apple)或P(banana)操作确保在取出水果吃之前它确实在盘子中。V(empty)操作是在吃完水果后执行的，表示盘子再次变空

2.和尚打水问题

为了解决这个问题，我们可以使用信号量来控制小和尚和老和尚对水缸的访问，确保每次只有一个和尚在打水或取水，同时保证水缸中的水不会超过其容量，也不会在取水时变为空。

首先，我们定义以下信号量：

empty：表示水缸中的空位数量，初始化为10（因为水缸可以放10桶水）。
full：表示水缸中已装满的水桶数量，初始化为0。
mutex：互斥信号量，用于确保在任何时候只有一个和尚在操作水缸。

初始化() {  semaphore empty = 10;  // 水缸初始为空位10个  semaphore full = 0;    // 水缸初始为0桶水  semaphore mutex = 1;   // 初始时有一个互斥锁可用  
}

小和尚打水() {  P(empty); // 等待水缸有空位  P(mutex); // 请求互斥锁  // 从井里打一桶水放入水缸  V(full);  // 水缸中的水桶数量增加  V(mutex); // 释放互斥锁  
}  小和尚循环打水() {  while (true) {  小和尚打水(); // 重复打水直到被停止或其他条件  // ... 可能存在的其他逻辑，如休息、等待指示等  }  
}

老和尚取水() {  P(full);  // 等待水缸中有水  P(mutex); // 请求互斥锁  // 从水缸中取出一桶水饮用  V(empty); // 水缸中的空位数量增加  V(mutex); // 释放互斥锁  
}  老和尚循环取水() {  while (true) {  老和尚取水(); // 重复取水直到被停止或其他条件  // ... 可能存在的其他逻辑，如休息、等待指示等  }  
}

3.餐厅职员问题

一个快餐厅有4类职员：
（1）领班：接受顾客点菜，出菜单；
（2）厨师：根据菜单，准备顾客的饭菜；
（3）打包工：将做好的饭菜打包；
（4）出纳员：收款并提交食品。
每个职员可被看作一个进程，试用一种同步机制写出能让四类职员正确并发运行的程序

// 定义信号量  
semaphore menuQueue = 0; // 菜单队列，初始为空  
semaphore foodQueue = 0; // 饭菜队列，初始为空  
semaphore mutex = 1;     // 互斥信号量，保护共享资源  // 领班进程  
void headwaiter() {  while (true) {  // 接收顾客点菜，出菜单  Menu menu = receiveOrderFromCustomer();  // 放置菜单到队列中  P(mutex); // 请求互斥锁  addToMenuQueue(menu);  V(mutex); // 释放互斥锁  // 通知厨师有新的菜单  V(menuQueue);  }  
}  // 厨师进程  
void chef() {  while (true) {  P(menuQueue); // 等待菜单  // 取出菜单并准备饭菜  Menu menu;  P(mutex); // 请求互斥锁  menu = takeFromMenuQueue();  V(mutex); // 释放互斥锁  Food food = prepareFood(menu);  // 放置饭菜到队列中  P(mutex); // 请求互斥锁  addToFoodQueue(food);  V(mutex); // 释放互斥锁  // 通知打包工有新的饭菜  V(foodQueue);  }  
}  // 打包工进程  
void packer() {  while (true) {  P(foodQueue); // 等待饭菜  // 取出饭菜并打包  Food food;  P(mutex); // 请求互斥锁  food = takeFromFoodQueue();  V(mutex); // 释放互斥锁  PackedFood packedFood = packFood(food);  // 通知出纳员有新的打包食品  // 在这个简单的模型中，打包和提交给顾客可能是连续的，因此不需要额外的信号量  // 如果打包和收款是分开的，那么可以添加一个信号量来同步  }  
}  // 出纳员进程  
void cashier() {  while (true) {  // 假设打包工已经完成了打包工作，并且直接提交给出纳员  // 出纳员收款并提交食品给顾客  PackedFood packedFood = getPackedFoodFromPacker(); // 假设有这样一个函数调用  collectMoneyFromCustomer(packedFood);  deliverFoodToCustomer(packedFood);  }  
}  // ... 其他必要的函数定义，如addToMenuQueue, takeFromMenuQueue, prepareFood等 ...  // 主程序或启动函数  
void main() {  // 创建并启动进程  createProcess(headwaiter);  createProcess(chef);  createProcess(packer);  createProcess(cashier);  // 等待所有进程结束（在实际系统中，可能需要更复杂的进程管理）  // ...  
}

在这个模型中，我们假设receiveOrderFromCustomer, addToMenuQueue, takeFromMenuQueue, prepareFood, addToFoodQueue, takeFromFoodQueue, packFood, collectMoneyFromCustomer, deliverFoodToCustomer等函数都是已经定义好的，并且它们能够正确地处理各自的职责。

menuQueue和foodQueue信号量用于控制菜单和饭菜队列的访问，确保厨师不会在没有菜单时工作，打包工不会在没有饭菜时工作。

mutex互斥信号量用于保护对共享资源的访问（如菜单队列和饭菜队列），确保在任何时候只有一个进程能够修改这些资源。

出纳员进程在这个模型中假设与打包工紧密合作，因此没有引入额外的同步机制。在实际情况中，如果打包和收款是分开的，那么可能需要添加额外的信号量来同步这两个进程。

4.汽车站点问题

在公共汽车上，司机和售票员的活动分别是：
司机的活动：启动车辆，正常行车，到站停车。
售票员的活动：上下乘客，关车门，售票，开车门，上下乘客。
在汽车不停的到站，停站，行驶过程中，这两个活动有什么同步关系？用信号量和P，V操作实现它们的同步。

首先，我们定义以下信号量：

start：表示司机是否可以启动车辆，初始值为0，售票员准备好后才能启动。
door：表示车门的状态，初始值为1，表示车门是关闭的。
当车门需要打开时，其值变为0，表示车门正在打开或已	经打开；当车门关闭时，其值变回1。

司机进程 {  while (true) {  P(start); // 等待售票员准备好  启动车辆();  正常行车();  // 到站停车  到站();  P(door); // 等待车门关闭  停车();  // 售票员准备好后继续行驶  }  
}

售票员进程 {  while (true) {  // 假设到站时自动触发以下活动  上下乘客();  关车门();  V(door); // 通知司机车门已关闭  售票();  // 假设到达下一站前需要通知司机可以启动  V(start); // 通知司机可以启动  // 准备打开车门迎接下一波乘客  开车门();  上下乘客();  // ...（重复上述过程）  }  
}

P(start)：司机等待start信号量变为非零值，然后将其减1。如果start为0，则司机阻塞，直到售票员通过V(start)将其加1。
V(start)：售票员增加start信号量的值，通知司机可以启动车辆。
P(door)：司机等待door信号量变为非零值，然后将其减1。如果door为0，则司机阻塞，直到售票员通过V(door)将其加1。
V(door)：售票员在关闭车门后增加door信号量的值，通知司机车门已关闭，可以安全停车或启动。

5.观察者-报告者问题

用P，V操作实现下述问题的解：
观察者和报告者是两个并发执行的进程，观察者不断观察并对通过的卡车计数，报告者定时的将观察者的计数值打印，打印完毕，将计数值清零。

为了使用P（等待）和V（信号）操作实现观察者-报告者问题，我们需要一个共享变量来存储卡车的计数值，以及一个信号量来同步两个进程。我们可以使用一个互斥信号量mutex来确保对计数值的互斥访问，以及一个条件变量reportReady来通知报告者可以打印计数值。
不过，需要注意的是，在标准的P，V操作中并没有直接的条件变量。但我们可以使用信号量和循环等待（忙等待）来模拟条件变量的行为。在这个例子中，我们可以使用两个信号量：mutex用于互斥访问，reportReady用于报告者检查观察者是否准备好了新的计数值。

semaphore mutex = 1; // 互斥信号量，用于保护对计数值的访问  
semaphore reportReady = 0; // 报告者等待信号量，初始化为0，表示还没有新的计数值  
int truckCount = 0; // 共享变量，用于存储卡车计数值  // 观察者进程  
void observer() {  while (true) {  // 观察到一辆卡车  observeTruck();  // 增加计数值，需要互斥访问  P(mutex);  truckCount++;  V(mutex);  // 通知报告者有新计数值可以打印  V(reportReady);  }  
}  // 报告者进程  
void reporter() {  while (true) {  // 等待观察者通知有新计数值  P(reportReady);  // 打印计数值，需要互斥访问  P(mutex);  printTruckCount(truckCount);  truckCount = 0; // 清零计数值  V(mutex);  // 等待一段时间再次检查  sleep(reportingInterval); // 假设有一个函数可以设置等待时间  }  
}  // 主程序或启动函数  
void main() {  // 创建并启动进程  createProcess(observer);  createProcess(reporter);  // ... 其他必要的初始化和等待进程结束的代码 ...  
}  // 假设的函数定义  
void observeTruck() {  // 假设的实现，表示观察到一辆卡车  
}  void printTruckCount(int count) {  // 假设的实现，用于打印计数值  
}  void sleep(int interval) {  // 假设的实现，用于让进程休眠一段时间  
}  // ... 其他必要的函数定义 ...

在这个实现中，reportReady信号量用于同步报告者和观察者。每当观察者观察到一辆卡车并增加计数值后，它会释放reportReady信号量，通知报告者可以打印计数值了。报告者在打印完计数值后会等待一段时间，然后再次检查reportReady信号量，等待观察者提供新的计数值。

6…阅览室问题

假定阅览室最多可同时容纳100个人阅读，读者进入时，必须在阅览室门口的一个登记表上登记，内容包括姓名、座号等，离开时要撤掉登记内容。
用P、V操作描述读者进程的同步算法

为了使用P（等待）和V（信号）操作来描述阅览室问题的读者进程同步算法，我们需要一个信号量来限制同时进入阅览室的读者数量。在这个例子中，我们假设阅览室最多可以容纳100个人，所以我们需要一个信号量roomSize，其初始值设置为100。

此外，为了模拟登记和撤掉登记内容的操作，我们还需要一个互斥信号量mutex来确保登记表的互斥访问。

semaphore roomSize = 100; // 控制进入阅览室的读者数量  
semaphore mutex = 1; // 控制对登记表的互斥访问  // 读者进程  
void readerProcess(string name, int seatNumber) {  while (true) { // 假设读者可以多次进出阅览室  // 请求进入阅览室  P(roomSize); // 等待阅览室有空位  // 登记进入阅览室  P(mutex); // 请求对登记表的互斥访问  registerEntry(name, seatNumber); // 登记姓名和座号  V(mutex); // 释放对登记表的互斥访问  // 在阅览室阅读...  readInLibrary();  // 准备离开阅览室  P(mutex); // 请求对登记表的互斥访问  removeEntry(name, seatNumber); // 撤掉登记内容  V(mutex); // 释放对登记表的互斥访问  // 离开阅览室，释放一个位置  V(roomSize); // 通知其他读者阅览室有空位了  // 读者可以选择继续阅读或结束进程  // ...  }  
}  // 假设的函数定义  
void registerEntry(string name, int seatNumber) {  // 实现登记的逻辑，比如将姓名和座号写入文件或数据库  
}  void removeEntry(string name, int seatNumber) {  // 实现撤掉登记的逻辑，比如从文件或数据库中删除姓名和座号  
}  void readInLibrary() {  // 读者在阅览室阅读的逻辑  
}  // 主程序或启动函数  
void main() {  // 创建并启动多个读者进程  // ...  // 等待所有读者进程结束或执行其他管理操作  // ...  
}

三、总结🍓🍓🍓

在这里插入图片描述

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

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

相关文章

DEBOPIE框架：打造最好的ChatGPT交易机器人

DEBOPIE框架：打造最好的ChatGPT交易机器人

本文介绍了如何利用 DEBOPIE 框架并基于 ChatGPT 创建高效交易机器人，并强调了在使用 AI 辅助交易时需要注意的限制以及操作步骤。原文: Build the Best ChatGPT Trading Bots with my “DEBOPIE” Framework 如今有大量文章介绍如何通过 ChatGPT 帮助决定如何以及在…
阅读更多...
win10修改远程桌面端口，Windows 10下修改远程桌面端口及服务器关闭445端口的操作指南

win10修改远程桌面端口，Windows 10下修改远程桌面端口及服务器关闭445端口的操作指南

Windows 10下修改远程桌面端口及服务器关闭445端口的操作指南 一、修改Windows 10远程桌面端口 在Windows 10系统中，远程桌面连接默认使用3389端口。为了安全起见，建议修改此端口以减少潜在的安全风险。以下是修改远程桌面端口的步骤： 1. 打…
阅读更多...
任务调度器——任务切换

任务调度器——任务切换

一、开启任务调度器 函数原型： void vTaskStartScheduler( void ) 作用：用于启动任务调度器，任务调度器启动后， FreeRTOS 便会开始进行任务调度 内部实现机制（以动态创建为例）： &#xff0…
阅读更多...
web学习笔记（七十二）

web学习笔记（七十二）

目录 1.vue2通过$parent实现组件传值——父传子 2.vue2 通过$children实现组件传值——子传父 3. provide和inject传值（依赖注入） 4.vue2如何操作dom 5.vue2如何拿到最新的dom 6.filters过滤器 7.vue2的生命周期 8.vuex的用法 1.vue2通过$parent…
阅读更多...
LLDP 基本原理

LLDP 基本原理

LLDP 简介 定义 LLDP（Link Layer Discovery Protocol，链路层发现协议）是 IEEE 802.1ab 中定义的第二层发现（Layer 2 Discovery）协议。 LLDP 提供了一种标准的链路层发现方式，可以将本端设备的主要能力、…
阅读更多...
Wp-scan一键扫描wordpress网页（KALI工具系列三十二）

Wp-scan一键扫描wordpress网页（KALI工具系列三十二）

目录 1、KALI LINUX 简介 2、Wp-scan工具简介 3、信息收集 3.1 目标IP（服务器) 3.2kali的IP 4、操作实例 4.1 基本扫描 4.2 扫描已知漏洞 4.3 扫描目标主题 4.4 列出用户 4.5 输出扫描文件 4.6 输出详细结果 5、总结 1、KALI LINUX 简介 Kali Linux 是一…
阅读更多...
决策树划分属性依据

决策树划分属性依据

划分依据 基尼系数基尼系数的应用信息熵信息增益信息增益的使用信息增益准则的局限性 最近在学习项目的时候经常用到随机森林，所以对决策树进行探索学习。 基尼系数 基尼系数用来判断不确定性或不纯度，数值范围在0~0.5之间，数值越低&#x…
阅读更多...
shark云原生-日志管理体系-filebeat

shark云原生-日志管理体系-filebeat

文章目录 1. deploy 文件1.1 RBAC1.2. DaemonSet1.2.1. Elasticsearch 连接信息1.2.2. Volume 1.3. ConfigMap1.3.1. 日志收集路径1.3.2. 日志事件输出目标 2. 在控制平面节点上运行Filebeat3. 查看输出3.1. 关于处理器 processors 4. 日志收集配置4.1. 手动指定日志收集路径4.…
阅读更多...
简单多状态DP问题

简单多状态DP问题

这里写目录标题 什么是多状态DP解决多状态DP问题应该怎么做？关于多状态DP问题的几道题1.按摩师2.打家劫舍Ⅱ3.删除并获得点数4.粉刷房子5.买卖股票的最佳时期含手冷冻期 总结 什么是多状态DP 多状态动态规划（Multi-State Dynamic Programming, Multi-St…
阅读更多...
数据结构-顺序表的插入排序

数据结构-顺序表的插入排序

顺序表的排序可以看作数组排序的拓展。基本逻辑和数组排序的逻辑大同小异。 由于顺序表中可以存放不同种的数据类型，进而和结构体排序又有相似之处。其中要注意的是（->）和（.）的区别。 -> 符号是针对指针进行的操…
阅读更多...
实现了Map接口的HashMap

实现了Map接口的HashMap

HashMap 底层主要由以下几个部分组成&#xff1a; 数组 (Node<K,V>[] table): 这是一个数组&#xff0c;存储的是链表的头节点。默认大小为 16。链表 (Linked List): 当发生哈希冲突时&#xff0c;即不同的键具有相同的哈希值&#xff0c;HashMap 使用链表来解决冲突。链…
阅读更多...
计网之IP

计网之IP

IP IP基本认识 不使用NAT时&#xff0c;源IP地址和目的IP地址不变&#xff0c;只要源MAC和目的MAC地址在变化 IP地址 D类是组播地址&#xff0c;E类是保留地址 无分类地址CIDR 解决直接分类的B类65536太多&#xff0c;C类256太少a.b.c.d/x的前x位属于网路号&#xff0c;剩…
阅读更多...
分治精炼宝库-----快速排序运用(⌯꒪꒫꒪)੭

分治精炼宝库-----快速排序运用(⌯꒪꒫꒪)੭

目录 一.基本概念: 一.颜色分类&#xff1a; 二.排序数组&#xff1a; 三.数组中的第k个最大元素&#xff1a; 解法一&#xff1a;快速选择算法 解法二&#xff1a;简单粗暴优先级队列 四.库存管理Ⅲ&#xff1a; 解法一&#xff1a;快速选择 解法二&#xff1a;简单粗…
阅读更多...
Github 2024-06-21 开源项目日报 Top10

Github 2024-06-21 开源项目日报 Top10

根据Github Trendings的统计，今日(2024-06-21统计)共有10个项目上榜。根据开发语言中项目的数量，汇总情况如下： 开发语言项目数量TypeScript项目3Python项目3Java项目2非开发语言项目2JavaScript项目1Rust项目1Dart项目1HTML项目1Vue项目1C++项目1TensorFlow: 机器学习的开源…
阅读更多...
【Linux】IO多路复用——select，poll，epoll的概念和使用，三种模型的特点和优缺点，epoll的工作模式

【Linux】IO多路复用——select，poll，epoll的概念和使用，三种模型的特点和优缺点，epoll的工作模式

文章目录 Linux多路复用1. select1.1 select的概念1.2 select的函数使用1.3 select的优缺点 2. poll2.1 poll的概念2.2 poll的函数使用2.3 poll的优缺点 3. epoll3.1 epoll的概念3.2 epoll的函数使用3.3 epoll的优点3.4 epoll工作模式 Linux多路复用 IO多路复用是一种操作系统的…
阅读更多...
算力时代，算能（SOPHGO）的算力芯片/智算板卡/服务器选型

算力时代，算能（SOPHGO）的算力芯片/智算板卡/服务器选型

数字经济时代&#xff0c;算力成为支撑经济社会发展新的关键生产力&#xff0c;全球主要经济体都在加快推进算力战略布局。随着大模型持续选代&#xff0c;模型能力不断增强&#xff0c;带来算力需求持续增长。算力对数字经济和GDP的提高有显著的带动作用&#xff0c;根据IDC、…
阅读更多...
EasyExcel数据导入

EasyExcel数据导入

前言&#xff1a; 我先讲一种网上信息的获取方式把&#xff0c;虽然我感觉和后面的EasyExcel没有什么关系&#xff0c;可能是因为这个项目这个操作很难实现&#xff0c;不过也可以在此记录一下&#xff0c;如果需要再拆出来也行。 看上了网页信息&#xff0c;怎么抓到&#x…
阅读更多...
C++:typeid4种cast转换

C++:typeid4种cast转换

typeid typeid typeid是C标准库中提供的一种运算符&#xff0c;它用于获取类型的信息。它主要用于类型检查和动态类型识别。当你对一个变量或对象使用typeid运算符时&#xff0c;它会返回一个指向std::type_info类型的指针&#xff0c;这个信息包含了关于该类型名称、大小、基…
阅读更多...
【嵌入式Linux】i.MX6ULL 时钟树——理论分析

【嵌入式Linux】i.MX6ULL 时钟树——理论分析

文章目录 0. 时钟树结构0.1 参考手册 Chapter 18​: Clock Controller Module (CCM)0.2 时钟信号路径 1. 时钟源——晶振1.1 外部低频时钟 - CKIL1.1.1 CKIL 同步到 IPG_CLK 解释 1.2 外部高频时钟 - CKIH 和 内部振荡器1.3 总结1.4 缩写补充 2. PLL时钟2.1 i.MX6U 芯片 PLL 时…
阅读更多...
【ESP32】打造全网最强esp-idf基础教程——14.VFS与SPIFFS文件系统

【ESP32】打造全网最强esp-idf基础教程——14.VFS与SPIFFS文件系统

VFS与SPIFFS文件系统 这几天忙着搬砖&#xff0c;差点没时间更新博客了&#xff0c;所谓一日未脱贫&#xff0c;打工不能停&#xff0c;搬砖不狠&#xff0c;明天地位不稳呀。 不多说了&#xff0c;且看以下内容吧~ 一、VFS虚拟文件系统 先来看下文件系统的定义&#x…
阅读更多...
最新文章
推荐文章

Copyright @ 2022~2023