-
哲学家干饭问题 C++
哲学家干饭问题 C++
哲学家就餐问题可以这样表述，假设有五位哲学家围坐在一张圆形餐桌旁，做以下两件事情之一：吃饭，或者思考。吃东西的时候，他们就停止思考，思考的时候也停止吃东西。餐桌上有五碗意大利面，每位哲学家之间各有一支餐叉。因为用一支餐叉很难吃到意大利面，所以假设哲学家必须用两支餐叉吃东西。他们只能使用自己左右手边的那两支餐叉。哲学家就餐问题有时也用米饭和五根筷子而不是意大利面和餐叉来描述，因为吃米饭必须用两根筷子。
这个问题不考虑意大利面有多少，也不考虑哲学家的胃有多大。假设两者都是无限大。
问题在于如何设计一套规则，使得在哲学家们在完全不交谈，也就是无法知道其他人可能在什么时候要吃饭或者思考的情况下，可以在这两种状态下永远交替下去。
使用忙等待获取资源
#include#include #include #include #include #include #include #include #include #include #include #include #include #include #include using namespace std; std::random_device rd_device; std::mt19937_64 rd_engine(rd_device()); //生成随机数 int generate_random_number(int min, int max) { std::uniform_int_distribution<int> dist(min, max); return dist(rd_engine); } void lock(std::atomic<int>& resource_number) { while (resource_number); //忙等待 resource_number = 1; } void unlock(std::atomic<int>& resource_number) { resource_number = 0; } void feast_think(int n, std::atomic<int>& a, std::atomic<int>& b) { while (true) { int duration = generate_random_number(1000, 1500); std::cout << std::format("{} 思考{}ms \n", n, duration); std::this_thread::sleep_for(std::chrono::milliseconds(duration)); // 思考 lock(a); std::cout << std::format("{} 获取a筷子\n", n); std::this_thread::sleep_for(std::chrono::milliseconds(1000)); lock(b); std::cout << std::format("{} 获取b筷子\n", n); duration = generate_random_number(1000, 1500); std::cout << std::format("{} 干饭时间：{} ms \n", n, duration); std::this_thread::sleep_for(std::chrono::milliseconds(duration)); unlock(b); unlock(a); std::cout << "\n\n"; } } int main(int argc, char* argv[]) { std::atomic<int> m1{0}, m2{0}, m3{0}, m4{0}; std::thread t1{[&]() { feast_think(1, m1, m2); }}; std::thread t2{[&]() { feast_think(2, m2, m3); }}; std::thread t3{[&]() { feast_think(3, m3, m4); }}; std::thread t4{[&]() { feast_think(4, m1, m4); }}; t1.join(); t2.join(); t3.join(); t4.join(); } - 1
- 2
- 3
- 4
- 5
- 6
- 7
- 8
- 9
- 10
- 11
- 12
- 13
- 14
- 15
- 16
- 17
- 18
- 19
- 20
- 21
- 22
- 23
- 24
- 25
- 26
- 27
- 28
- 29
- 30
- 31
- 32
- 33
- 34
- 35
- 36
- 37
- 38
- 39
- 40
- 41
- 42
- 43
- 44
- 45
- 46
- 47
- 48
- 49
- 50
- 51
- 52
- 53
- 54
- 55
- 56
- 57
- 58
- 59
- 60
- 61
- 62
- 63
- 64
- 65
- 66
- 67
- 68
- 69
- 70
- 71
- 72
- 73
- 74
- 75
- 76
- 77
- 78
- 79
- 80
- 81
- 82
- 83
我们使用
lock|unlock获取和释放资源， 但是在这之间，线程调度可能会导致线程切换，出现一些难以发现的问题优化使用忙等待获取资源
std::random_device rd_device; std::mt19937_64 rd_engine(rd_device()); //生成随机数 int generate_random_number(int min, int max) { std::uniform_int_distribution<int> dist(min, max); return dist(rd_engine); } void lock(std::atomic_flag& resource_flag) { while (resource_flag.test_and_set()); //忙等待 } void unlock(std::atomic_flag& resource_flag) { resource_flag.clear(); } void feast_think(int n, std::atomic_flag& a, std::atomic_flag& b) { while (true) { int duration = generate_random_number(100, 200); std::cout << std::format("{} 思考{}ms \n", n, duration); std::this_thread::sleep_for(std::chrono::milliseconds(duration)); // 思考 lock(a); std::cout << std::format("{} 获取a筷子\n", n); std::this_thread::sleep_for(std::chrono::milliseconds(100)); lock(b); std::cout << std::format("{} 获取b筷子\n", n); duration = generate_random_number(100, 200); std::cout << std::format("{} 干饭时间：{} ms \n", n, duration); std::this_thread::sleep_for(std::chrono::milliseconds(duration)); unlock(b); unlock(a); std::cout << "\n\n"; } } int main(int argc, char* argv[]) { std::atomic_flag m1, m2, m3, m4; std::thread t1{[&]() { feast_think(1, m1, m2); }}; std::thread t2{[&]() { feast_think(2, m2, m3); }}; std::thread t3{[&]() { feast_think(3, m3, m4); }}; std::thread t4{[&]() { feast_think(4, m1, m4); }}; t1.join(); t2.join(); t3.join(); t4.join(); }- 1
- 2
- 3
- 4
- 5
- 6
- 7
- 8
- 9
- 10
- 11
- 12
- 13
- 14
- 15
- 16
- 17
- 18
- 19
- 20
- 21
- 22
- 23
- 24
- 25
- 26
- 27
- 28
- 29
- 30
- 31
- 32
- 33
- 34
- 35
- 36
- 37
- 38
- 39
- 40
- 41
- 42
- 43
- 44
- 45
- 46
- 47
- 48
- 49
- 50
- 51
- 52
- 53
- 54
- 55
- 56
- 57
- 58
- 59
- 60
- 61
- 62
lock中使用循环浪费了大量的CPU，可以使用sleep_for短暂的暂停循环来节约CPU
降低CPU占用率
添加
while (resource_flag.test_and_set()) { std::this_thread::sleep_for(std::chrono::milliseconds(8)); }- 1
- 2
- 3
- 4
CPU占用几乎为零
使用
std::mutex关于自旋锁与互斥量的区别：Waiting Thread - an overview | ScienceDirect Topics
简单说：自旋锁等待另一个线程，互斥量等待系统调度，所以互斥量不会占用大量的CPU周期，自旋锁会占用大量的CPU周期
void feast_think(int n, std::mutex& a, std::mutex& b) { while (true) { int duration = generate_random_number(100, 200); std::cout << std::format("{} 思考{}ms \n", n, duration); std::this_thread::sleep_for(std::chrono::milliseconds(duration)); // 思考 a.lock(); std::cout << std::format("{} 获取a筷子\n", n); std::this_thread::sleep_for(std::chrono::milliseconds(100)); b.lock(); std::cout << std::format("{} 获取b筷子\n", n); duration = generate_random_number(100, 200); std::cout << std::format("{} 干饭时间：{} ms \n", n, duration); std::this_thread::sleep_for(std::chrono::milliseconds(duration)); b.unlock(); a.unlock(); std::cout << "\n\n"; } } int main(int argc, char* argv[]) { std::mutex m1, m2, m3, m4; std::thread t1{[&]() { feast_think(1, m1, m2); }}; std::thread t2{[&]() { feast_think(2, m2, m3); }}; std::thread t3{[&]() { feast_think(3, m3, m4); }}; std::thread t4{[&]() { feast_think(4, m1, m4); }}; t1.join(); t2.join(); t3.join(); t4.join(); }- 1
- 2
- 3
- 4
- 5
- 6
- 7
- 8
- 9
- 10
- 11
- 12
- 13
- 14
- 15
- 16
- 17
- 18
- 19
- 20
- 21
- 22
- 23
- 24
- 25
- 26
- 27
- 28
- 29
- 30
- 31
- 32
- 33
- 34
- 35
- 36
- 37
- 38
- 39
- 40
使用
std::unique_lock以及std::defer_lock标志我们可以使用一步操作，同时获取两个互斥量，这样就不会有死锁的风险
为了保证输出同步，添加一个
mutex mousing namespace std; std::random_device rd_device; std::mt19937_64 rd_engine(rd_device()); //生成随机数 int generate_random_number(int min, int max) { std::uniform_int_distribution<int> dist(min, max); return dist(rd_engine); } std::mutex mo; void feast_think(int n, std::mutex& a, std::mutex& b) { while (true) { int duration = generate_random_number(1000, 2000); { std::lock_guard<std::mutex> g(mo); std::cout << std::format("{} 思考{}ms \n", n, duration); } std::this_thread::sleep_for(std::chrono::milliseconds(duration)); // 思考 std::unique_lock<std::mutex> ga(a, std::defer_lock); { std::lock_guard<std::mutex> g(mo); std::cout << std::format("{} 获取a筷子\n", n); } std::this_thread::sleep_for(std::chrono::milliseconds(1000)); std::unique_lock<std::mutex> gb(b, std::defer_lock); std::lock(ga, gb); { std::lock_guard<std::mutex> g(mo); std::cout << std::format("{} 获取b筷子\n", n); } duration = generate_random_number(1000, 2000); { std::lock_guard<std::mutex> g(mo); std::cout << std::format("{} 干饭时间：{} ms \n", n, duration); } std::this_thread::sleep_for(std::chrono::milliseconds(duration)); std::cout << "\n\n"; } } int main(int argc, char* argv[]) { std::mutex m1, m2, m3, m4; std::thread t1{[&]() { feast_think(1, m1, m2); }}; std::thread t2{[&]() { feast_think(2, m2, m3); }}; std::thread t3{[&]() { feast_think(3, m3, m4); }}; std::thread t4{[&]() { feast_think(4, m1, m4); }}; t1.join(); t2.join(); t3.join(); t4.join(); }- 1
- 2
- 3
- 4
- 5
- 6
- 7
- 8
- 9
- 10
- 11
- 12
- 13
- 14
- 15
- 16
- 17
- 18
- 19
- 20
- 21
- 22
- 23
- 24
- 25
- 26
- 27
- 28
- 29
- 30
- 31
- 32
- 33
- 34
- 35
- 36
- 37
- 38
- 39
- 40
- 41
- 42
- 43
- 44
- 45
- 46
- 47
- 48
- 49
- 50
- 51
- 52
- 53
- 54
- 55
- 56
- 57
- 58
- 59
- 60
- 61
- 62
- 63
- 64
- 65
- 66
- 67
- 68
- 69
- 70
- 71
-
相关阅读:
最新！两步 永久禁止谷歌浏览器 Google Chrome 自动更新
中国312个历史文化名镇及景区空间点位数据集
十、【分布式微服务企业快速架构】SpringCloud分布式、微服务、云架构之Eclipse 创建 Java 包
【Java】判断语句if.....&选择语句switch......
网络安全（黑客）自学
软件工程与计算总结（十五）详细设计中面向对象方法下的信息隐藏
HACK ME PLEASE: 1实战演练
姿态估计评价指标
敏捷开发的优势
ROS文件系统以及相关命令
- 原文地址：https://blog.csdn.net/qq_42896106/article/details/126917511
