当前位置: 首页 > news >正文

通过哲学家进餐问题学习线程间协作(代码实现以leetcode1226为例)

哲学家进餐问题

    • (代码实现以leetcode1226为例)
      • 问题场景
      • 解决思路
      • 解决死锁问题
      • 代码实现
        • c++
        • go

(代码实现以leetcode1226为例)

提到多线程和锁解决问题,就想到了os中哲学家进餐问题。

问题场景

回想该问题产生场景,五个哲学家共用一张圆桌,分别坐在周围的五张椅子上,在圆桌上有五个碗和五只筷子,他们的生活方式是交替的进行思考和进餐。平时,一个哲学家进行思考,饥饿时便试图取用其左右最靠近他的筷子,只有在他拿到两只筷子时才能进餐。进餐完毕,放下筷子继续思考。

解决思路

由于五位哲学家应相互独立,因此可以创建五个线程分别代表五位哲学家,相互独立(异步),依次编号为0~4。

对于资源(筷子),应该认为这是五种临界资源,而不是一种临界资源。因为每位哲学家只能使用自己面前的两个筷子。同样对五只筷子进行资源编号0~4,并且定义第i位哲学家左侧的筷子编号为i,哲学家右侧的筷子编号为(i+1)%5(这里要注意对编号为0的进行特殊处理)。

临界资源的定义,一次只允许一个线程使用的公共资源。所以当一只筷子被一位哲学家使用时应该加锁。

形成一种解决思路如下:

while(1){think()hungry()p(左筷子)p(右筷子)eat()v(左筷子)v(右筷子)
}

显而易见这种解决办法会出现死锁问题,即当每位哲学家获取左筷子后,永久陷入了等待右筷子状态,且每个人都不会主动放弃获取的临界资源。

解决死锁问题

①我们可以只允许四个哲学家都拿起同一边的筷子,这样会保证一位哲学家可以得到两边筷子完成进食,释放临界资源,保证别的哲学家可以进行相应的线程。

这里要新增一个信号量,控制拿起同一边筷子的哲学家数量。

修改后的解决思路如下:

while(1){think()hungry()p(还可以拿起一边筷子)p(左筷子)p(右筷子)eat()v(左筷子)v(拿起一边筷子的名额)v(右筷子)
}

②采用AND信号量机制,即当一个线程要执行时一次性将所需的资源全部给他,否则不分给他资源。

新的解决思路如下:

while(1){think()hungry()Swait(左筷子,右筷子)eat()Spost(左筷子,右筷子)
}

针对不用的代码语言,当不支持and信号量机制时,可以考虑增加新的互斥信号量来实现。全局互斥信号量,当一个哲学家企图拿筷子时候,就将全部资源锁住。

修改后的解决思路如下:

while(1){think()hungry()p(lock)p(左筷子)p(右筷子)v(lock)eat()v(左筷子)v(右筷子)
}

③区分奇数偶数哲学家,规定奇数号哲学家先拿起他左边的筷子,然后再去拿他右边的筷子,而偶数号的哲学家则相反,这样的话总能保证一个哲学家能获得两根筷子完成进餐,从而释放其所占用的资源。

解决思路如下:

while(1){think(i)hungry(i)if(i % 2 == 0){p(左筷子)p(右筷子)eat()v(右筷子)v(左筷子)}else{p(右筷子)p(左筷子)eat()v(左筷子)v(右筷子)}
}

代码实现

c++

①只允许四个哲学家都拿起同一边的筷子 room信号量4

#include<semaphore.h>
class DiningPhilosophers {
public:DiningPhilosophers() {fork = vector<sem_t>(5);sem_init(&room,0,4);for(int i = 0;i < 5;i++){sem_init(&(fork[i]),0,1);}}void wantsToEat(int philosopher,function<void()> pickLeftFork,function<void()> pickRightFork,function<void()> eat,function<void()> putLeftFork,function<void()> putRightFork) {sem_wait(&room);sem_wait(&(fork[philosopher]));sem_wait(&(fork[(philosopher+1)%5]));pickLeftFork();pickRightFork();eat();putRightFork();putLeftFork();sem_post(&(fork[(philosopher+1)%5]));sem_post(&(fork[philosopher]));sem_post(&room);}vector<sem_t> fork;sem_t room;
};

②AND信号量方式

#include<semaphore.h>
class DiningPhilosophers {
public:DiningPhilosophers() {fork = vector<sem_t>(5);for(int i = 0;i < 5;i++){sem_init(&(fork[i]),0,1);}sem_init(&mutex,0,1);}void wantsToEat(int philosopher,function<void()> pickLeftFork,function<void()> pickRightFork,function<void()> eat,function<void()> putLeftFork,function<void()> putRightFork) {sem_wait(&mutex);sem_wait(&(fork[philosopher]));sem_wait(&(fork[(philosopher+1)%5]));pickLeftFork();pickRightFork();sem_post(&mutex);eat();putRightFork();putLeftFork();sem_post(&(fork[(philosopher+1)%5]));sem_post(&(fork[philosopher]));}vector<sem_t> fork;sem_t mutex;
};

③奇偶数

#include<semaphore.h>
class DiningPhilosophers {
public:DiningPhilosophers() {fork = vector<sem_t>(5);for(int i = 0;i < 5;i++){sem_init(&(fork[i]),0,1);}}void wantsToEat(int philosopher,function<void()> pickLeftFork,function<void()> pickRightFork,function<void()> eat,function<void()> putLeftFork,function<void()> putRightFork) {if(philosopher % 2 == 0){sem_wait(&(fork[philosopher]));sem_wait(&(fork[(philosopher+1)%5]));pickLeftFork();pickRightFork();eat();putRightFork();putLeftFork();sem_post(&(fork[(philosopher+1)%5]));sem_post(&(fork[philosopher]));}else{sem_wait(&(fork[(philosopher+1)%5]));sem_wait(&(fork[philosopher]));pickLeftFork();pickRightFork();eat();putRightFork();putLeftFork();sem_post(&(fork[philosopher]));sem_post(&(fork[(philosopher+1)%5]));}}vector<sem_t> fork;
};

go

奇偶数

package mainimport ("fmt""sync"
)type DiningPhilosophers struct {getkey    []chan intendsSgnal *sync.WaitGroup
}func pickLeftFork(i int) {fmt.Printf("philosopher %d pickLeftFork\n", i)
}
func pickRightFork(i int) {fmt.Printf("philosopher %d pickRightFork\n", i)
}
func eat(i int) {fmt.Printf("philosopher %d eat\n", i)
}
func putLeftFork(i int) {fmt.Printf("philosopher %d putLeftFork\n", i)
}
func putRightFork(i int) {fmt.Printf("philosopher %d putRightFork\n", i)
}func (s *DiningPhilosophers) wantsToEat(philosopher int, pickLeftFork func(int), pickRightFork func(int), eat func(int), putLeftFork func(int), putRightFork func(int)) {if philosopher%2 == 0 {<-s.getkey[philosopher]pickLeftFork(philosopher)<-s.getkey[(philosopher+1)%5]pickRightFork(philosopher)eat(philosopher)putRightFork(philosopher)s.getkey[(philosopher+1)%5] <- 1putLeftFork(philosopher)s.getkey[philosopher] <- 1} else {<-s.getkey[(philosopher+1)%5]pickRightFork(philosopher)<-s.getkey[philosopher]pickLeftFork(philosopher)eat(philosopher)putLeftFork(philosopher)s.getkey[philosopher] <- 1putRightFork(philosopher)s.getkey[(philosopher+1)%5] <- 1}s.endsSgnal.Done()
}func main() {s := &DiningPhilosophers{getkey:    make([]chan int, 5),endsSgnal: &sync.WaitGroup{},}for i := 0; i < len(s.getkey); i++ {s.getkey[i] = make(chan int, 1)s.getkey[i] <- 1}n := 100for i := 0; i < n; i++ {s.endsSgnal.Add(5)go s.wantsToEat(0, pickLeftFork, pickRightFork, eat, putLeftFork, putRightFork)go s.wantsToEat(1, pickLeftFork, pickRightFork, eat, putLeftFork, putRightFork)go s.wantsToEat(2, pickLeftFork, pickRightFork, eat, putLeftFork, putRightFork)go s.wantsToEat(3, pickLeftFork, pickRightFork, eat, putLeftFork, putRightFork)go s.wantsToEat(4, pickLeftFork, pickRightFork, eat, putLeftFork, putRightFork)}s.endsSgnal.Wait()
}

相关文章:

通过哲学家进餐问题学习线程间协作(代码实现以leetcode1226为例)

哲学家进餐问题(代码实现以leetcode1226为例)问题场景解决思路解决死锁问题代码实现cgo(代码实现以leetcode1226为例) 提到多线程和锁解决问题&#xff0c;就想到了os中哲学家进餐问题。 问题场景 回想该问题产生场景&#xff0c;五个哲学家共用一张圆桌&#xff0c;分别坐在…...

消息队列--Kafka

Kafka简介集群部署配置Kafka测试Kafka1.Kafka简介 数据缓冲队列。同时提高了可扩展性。具有峰值处理能力&#xff0c;使用消息队列能够使关键组件顶住突发的访问压力&#xff0c;而不会因为突发的超负荷的请求而完全崩溃。 Kafka是一个分布式、支持分区的&#xff08;partition…...

外盘国际期货:我国当代年轻人结婚逐年下降

我国当代年轻人 结婚现状结婚少了 结婚晚了 2013年后结婚人数逐年下降 结婚少了 离婚多了 结婚年龄越来越迟 以30岁为界线&#xff0c;30岁之后结婚占比逐年增加 2018 20-24岁&#xff1a;435.6万人 25-29岁&#xff1a;736.2万人 30-34岁&#xff1a;314.7万人 35-3…...

Ubuntu 22.04.2 发布,可更新至 Linux Kernel 5.19

Ubuntu 22.04 LTS (Jammy Jellyfish) Ubuntu 22.04.2 发布&#xff0c;可更新至 Linux Kernel 5.19 请访问原文链接&#xff1a;Ubuntu 22.04 LTS (Jammy Jellyfish)&#xff0c;查看最新版。原创作品&#xff0c;转载请保留出处。 作者主页&#xff1a;www.sysin.org 发行说…...

论文阅读笔记——《室内服务机器人的实时场景分割算法》

一、主要工作 通过深度可分离卷积、膨胀卷积和通道注意力机制设计轻量级的高准确度特征提取模块。融合浅层特征与深层语义特征获得更丰富的图像特征。在NYUDv2和CamVid数据集上的MIoU分别达到72.7%和59.9%&#xff0c;模型的计算力为4.2GFLOPs&#xff0c;参数量为8.3Mb。 二…...

Hive学习——自定义函数UDFUDTF

目录 一、添加依赖 二、编写自定义UDF函数 (一)自定义首字母大写函数 1.java代码 2.hive中运行 (二)自定义字符串全部小写的函数 1.java代码 2.hive运行 (三)创建解析JSON字符串的函数 1.java代码 三、自定义编写UDTF函数 1.java编写 2.hive运行 虽然Hive中内置了…...

自学前端,你必须要掌握的3种定时任务

当你看到这篇博客的时候&#xff0c;一定会和狗哥结下不解之缘&#xff0c;因为狗哥的博客里不仅仅有代码&#xff0c;还有很多代码之外的东西&#xff0c;如果你可以看到最底部&#xff0c;看到投票环节&#xff0c;我相信你一定感觉到了&#xff0c;狗哥的真诚&#xff0c;狗…...

__stack_chk_fail问题分析

一、问题进程收到SIGABRT信号异常退出&#xff0c;异常调用栈显示__stack_chk_fail*** *** *** *** *** *** *** *** *** *** *** *** *** *** *** *** Build fingerprint: Pico/A7H10/PICOA7H10:10/5.5.0/smartcm.1676912090:userdebug/dev-keys Revision: 0 ABI: arm64 Times…...

linux 查看当前系统用户

1.查看当前登录账号(whoami) whoami ---------------------- root2.查看当前账号信息(id) id --------------------------- uid0(root) gid0(root) groups0(root)3.查看/etc/passwd文件 可以看到每行记录对应着一个用户信息&#xff0c;每条记录 共7段 用 冒号: 拼接&#xf…...

AI算法创新赛-人车目标检测竞赛总结05

队伍&#xff1a;AI0000043 1. 算法方案 由于赛题同时要求速度和精度&#xff0c;所以我们优先考虑小模型&#xff0c;在保证模型速度的同时通过模型调优稳 定提升模型精度。此外&#xff0c;由于图片分辨率比较大&#xff0c;且数据集中小目标占比高&#xff0c;我们计划使用…...

CSS 浮动【快速掌握知识点】

目录 前言 一、设置浮动属性 二、确定浮动元素的宽度 三、清除浮动 总结&#xff1a; 前言 CSS浮动是一种布局技术&#xff0c;它允许元素浮动到其父元素的左侧或右侧&#xff0c;从而腾出空间给其他元素。 一、设置浮动属性 使用CSS float属性将元素设置为浮动。例如&…...

在做自动化测试前需要知道的

什么是自动化测试&#xff1f; 做测试好几年了&#xff0c;真正学习和实践自动化测试一年&#xff0c;自我感觉这一个年中收获许多。一直想动笔写一篇文章分享自动化测试实践中的一些经验。终于决定花点时间来做这件事儿。 首先理清自动化测试的概念&#xff0c;广义上来讲&a…...

机器人学习的坚持与收获-2023

所有的机会都需要自己努力去争取&#xff0c;毕竟天会下雨下雪&#xff0c;但是不会掉馅饼。之前写过关于毕业生的一些博文。机器人工程ROS方向应用型本科毕业设计重点课题学生验收成果&#xff08;暂缓通过&#xff09;机器人工程ROS方向应用型本科毕业设计重点课题学生验收成…...

RSA签名加密解密

目录Java 接口RSAUtils.java示例中的依赖生成密钥对示例签名示例验证签名示例加密和解密示例Javascript 接口引入依赖生成密钥对示例签名示例验证签名示例加密和解密示例说在最后Java 接口 支持的密钥长度包括4种 RSA512、RSA1024、RSA2048、RSA4096支持的签名算法包括7种 MD2…...

【C语言】数据的存储

☃️内容专栏&#xff1a;【C语言】进阶部分 ☃️本文概括&#xff1a; C语言中的数据类型及其存储方式。 ☃️本文作者&#xff1a;花香碟自来_ ☃️发布时间&#xff1a;2023.2.24 目录 一、数据类型详细介绍 1.1 基本的数据类型 1.2 整型家族 1.3 构造类型 1.4 指针类型…...

「RISC-V Arch」SBI 规范解读(上)

术语 SBI&#xff0c;Supervisor Binary Interface&#xff0c;管理二进制接口 U-Mode&#xff0c;User mode&#xff0c;用户模式 S-Mode&#xff0c;Supervisor mode&#xff0c;监督模式 VS-Mode&#xff0c;Virtualization Supervisor mode&#xff0c;虚拟机监督模式 …...

2023年全国最新二级建造师精选真题及答案5

百分百题库提供二级建造师考试试题、二建考试预测题、二级建造师考试真题、二建证考试题库等&#xff0c;提供在线做题刷题&#xff0c;在线模拟考试&#xff0c;助你考试轻松过关。 51.下列国有资金占控股或者主导地位的依法必须进行招标的项目&#xff0c;可以采取邀请招标的…...

365智能云打印怎么样?365小票无线订单打印机好用吗?

365智能云打印怎么样&#xff1f;365智能云打印是有赞官方首推的订单小票打印机&#xff0c;荣获2016年有赞最佳硬件服务商。可以实现远程云打印&#xff0c;无需连接电脑&#xff0c;只需通过GPRS流量或者WIFI即可连接&#xff0c;不受地理位置和距离限制。365小票无线订单打印…...

细说react源码中的合成事件

最近在做一个功能&#xff0c;然后不小心踩到了 React 合成事件 的坑&#xff0c;好奇心的驱使&#xff0c;去看了 React 官网合成事件 的解释&#xff0c;这不看不知道&#xff0c;一看吓一跳… SyntheticEvent是个什么鬼&#xff1f;咋冒出来了个事件池&#xff1f; 我就一…...

【架构师】零基础到精通——架构演进

博客昵称&#xff1a;架构师Cool 最喜欢的座右铭&#xff1a;一以贯之的努力&#xff0c;不得懈怠的人生。 作者简介&#xff1a;一名Coder&#xff0c;软件设计师/鸿蒙高级工程师认证&#xff0c;在备战高级架构师/系统分析师&#xff0c;欢迎关注小弟&#xff01; 博主小留言…...

基于大模型的 UI 自动化系统

基于大模型的 UI 自动化系统 下面是一个完整的 Python 系统,利用大模型实现智能 UI 自动化,结合计算机视觉和自然语言处理技术,实现"看屏操作"的能力。 系统架构设计 #mermaid-svg-2gn2GRvh5WCP2ktF {font-family:"trebuchet ms",verdana,arial,sans-…...

【JavaEE】-- HTTP

1. HTTP是什么&#xff1f; HTTP&#xff08;全称为"超文本传输协议"&#xff09;是一种应用非常广泛的应用层协议&#xff0c;HTTP是基于TCP协议的一种应用层协议。 应用层协议&#xff1a;是计算机网络协议栈中最高层的协议&#xff0c;它定义了运行在不同主机上…...

在HarmonyOS ArkTS ArkUI-X 5.0及以上版本中,手势开发全攻略:

在 HarmonyOS 应用开发中&#xff0c;手势交互是连接用户与设备的核心纽带。ArkTS 框架提供了丰富的手势处理能力&#xff0c;既支持点击、长按、拖拽等基础单一手势的精细控制&#xff0c;也能通过多种绑定策略解决父子组件的手势竞争问题。本文将结合官方开发文档&#xff0c…...

Cilium动手实验室: 精通之旅---20.Isovalent Enterprise for Cilium: Zero Trust Visibility

Cilium动手实验室: 精通之旅---20.Isovalent Enterprise for Cilium: Zero Trust Visibility 1. 实验室环境1.1 实验室环境1.2 小测试 2. The Endor System2.1 部署应用2.2 检查现有策略 3. Cilium 策略实体3.1 创建 allow-all 网络策略3.2 在 Hubble CLI 中验证网络策略源3.3 …...

生成 Git SSH 证书

&#x1f511; 1. ​​生成 SSH 密钥对​​ 在终端&#xff08;Windows 使用 Git Bash&#xff0c;Mac/Linux 使用 Terminal&#xff09;执行命令&#xff1a; ssh-keygen -t rsa -b 4096 -C "your_emailexample.com" ​​参数说明​​&#xff1a; -t rsa&#x…...

uniapp微信小程序视频实时流+pc端预览方案

方案类型技术实现是否免费优点缺点适用场景延迟范围开发复杂度​WebSocket图片帧​定时拍照Base64传输✅ 完全免费无需服务器 纯前端实现高延迟高流量 帧率极低个人demo测试 超低频监控500ms-2s⭐⭐​RTMP推流​TRTC/即构SDK推流❌ 付费方案 &#xff08;部分有免费额度&#x…...

【碎碎念】宝可梦 Mesh GO : 基于MESH网络的口袋妖怪 宝可梦GO游戏自组网系统

目录 游戏说明《宝可梦 Mesh GO》 —— 局域宝可梦探索Pokmon GO 类游戏核心理念应用场景Mesh 特性 宝可梦玩法融合设计游戏构想要素1. 地图探索&#xff08;基于物理空间 广播范围&#xff09;2. 野生宝可梦生成与广播3. 对战系统4. 道具与通信5. 延伸玩法 安全性设计 技术选…...

ip子接口配置及删除

配置永久生效的子接口&#xff0c;2个IP 都可以登录你这一台服务器。重启不失效。 永久的 [应用] vi /etc/sysconfig/network-scripts/ifcfg-eth0修改文件内内容 TYPE"Ethernet" BOOTPROTO"none" NAME"eth0" DEVICE"eth0" ONBOOT&q…...

代码随想录刷题day30

1、零钱兑换II 给你一个整数数组 coins 表示不同面额的硬币&#xff0c;另给一个整数 amount 表示总金额。 请你计算并返回可以凑成总金额的硬币组合数。如果任何硬币组合都无法凑出总金额&#xff0c;返回 0 。 假设每一种面额的硬币有无限个。 题目数据保证结果符合 32 位带…...

scikit-learn机器学习

# 同时添加如下代码, 这样每次环境(kernel)启动的时候只要运行下方代码即可: # Also add the following code, # so that every time the environment (kernel) starts, # just run the following code: import sys sys.path.append(/home/aistudio/external-libraries)机…...