商城版手机网站制作,网站建设数据录入,外贸网站建设定制,国际化域名哲学家进餐问题
由荷兰学者Dijkstra提出的哲学家进餐问题(The Dinning Philosophers Problem)是经典的同步问题之一
有五个哲学家#xff0c;他们的生活方式是交替地进行思考和进餐#xff0c;哲学家们共用一张圆桌#xff0c;分别坐在周围的五张椅子上#xff0c;在圆桌…哲学家进餐问题
由荷兰学者Dijkstra提出的哲学家进餐问题(The Dinning Philosophers Problem)是经典的同步问题之一
有五个哲学家他们的生活方式是交替地进行思考和进餐哲学家们共用一张圆桌分别坐在周围的五张椅子上在圆桌上有五个碗和五支筷子平时哲学家进行思考饥饿时便试图取其左、右最靠近他的筷子只有在他拿到两支筷子时才能进餐该哲学家进餐完毕后放下左右两只筷子又继续思考。 约束条件 (1)只有拿到两只筷子时哲学家才能吃饭。 (2)如果筷子已被别人拿走则必须等别人吃完之后才能拿到筷子。 (3)任一哲学家在自己未拿到两只筷子吃完饭前不会放下手中已经拿到的筷子。
接下来用的至少需要C11
死锁
整体思路就是拿左边上锁拿右边上锁
但是有可能5个哲学家同时拿这就导致他们拿完了左边每个人都无法拿右边就g了 尤其是拿完了左边开始sleepsleep越久就越有可能死锁
#include iostream
#include chrono
#include thread
#include mutexint getThinkTime(){return 1;
}int getEatTime(){return 1;
}void think(size_t id){std::cout id starts thinking. std::endl;std::this_thread::sleep_for(std::chrono::seconds(getThinkTime()));std::cout id all done thinking. std::endl;
}void eat(size_t id, std::mutex left, std::mutex right){left.lock();std::this_thread::sleep_for(std::chrono::seconds(2));right.lock();std::cout id starts eating om nom nom nom. std::endl;std::this_thread::sleep_for(std::chrono::seconds(getEatTime()));std::cout id all done eating. std::endl;left.unlock();right.unlock();
}void philosopher(size_t id, std::mutex left, std::mutex right){for(size_t i 0; i 3; i){think(id);eat(id, left, right);}
}int main(){std::mutex forks[5];std::thread philosophers[5];for(size_t i 0; i 5; i){philosophers[i] std::thread(philosopher, i, ref(forks[i]), ref(forks[(i 1) % 5]));}for(auto p:philosophers)p.join();return 0;
}
奇偶
奇数先拿左边偶数先拿右边
那么奇数人就是拿0, 2 偶数人拿1, 3, 0 这样0是不能同时拿就不会死锁了
#include iostream
#include chrono
#include thread
#include mutexint getThinkTime(){return 1;
}int getEatTime(){return 1;
}void think(size_t id){std::cout id starts thinking. std::endl;std::this_thread::sleep_for(std::chrono::seconds(getThinkTime()));std::cout id all done thinking. std::endl;
}void eat(size_t id, std::mutex left, std::mutex right){if(id 1){left.lock();std::this_thread::sleep_for(std::chrono::seconds(2));right.lock();}else{right.lock();std::this_thread::sleep_for(std::chrono::seconds(2));left.lock();}std::cout id starts eating om nom nom nom. std::endl;std::this_thread::sleep_for(std::chrono::seconds(getEatTime()));std::cout id all done eating. std::endl;left.unlock();right.unlock();
}void philosopher(size_t id, std::mutex left, std::mutex right){for(size_t i 0; i 3; i){think(id);eat(id, left, right);}
}int main(){std::mutex forks[5];std::thread philosophers[5];for(size_t i 0; i 5; i){philosophers[i] std::thread(philosopher, i, ref(forks[i]), ref(forks[(i 1) % 5]));}for(auto p:philosophers)p.join();return 0;
}
条件变量
简单来说就是最多同时有4个哲学家操作其实1-4都是可以的只要不要让5个哲学家一起操作就行
我这里用的condition_variable_any不仅可以操作lock_guard还可以操作unique_lock 如果用condition_variable那就只能操作unique_lock
#include iostream
#include chrono
#include thread
#include mutex
#include condition_variableint getThinkTime(){return 1;
}int getEatTime(){return 1;
}void think(size_t id){std::cout id starts thinking. std::endl;std::this_thread::sleep_for(std::chrono::seconds(getThinkTime()));std::cout id all done thinking. std::endl;
}void waitForPermission(size_t permits, std::condition_variable_any cv, std::mutex m){std::lock_guardstd::mutex lg(m);cv.wait(m, [permits](){return permits 0;});--permits;
}void grantPermission(size_t permits, std::condition_variable_any cv, std::mutex m){std::lock_guardstd::mutex lg(m);permits;if(permits 1)cv.notify_all();
}void eat(size_t id, std::mutex left, std::mutex right, size_t permits, std::condition_variable_any cv, std::mutex m){waitForPermission(permits, cv, m);left.lock();std::this_thread::sleep_for(std::chrono::seconds(2));right.lock();std::cout id starts eating om nom nom nom. std::endl;std::this_thread::sleep_for(std::chrono::seconds(getEatTime()));std::cout id all done eating. std::endl;grantPermission(permits, cv, m);left.unlock();right.unlock();
}void philosopher(size_t id, std::mutex left, std::mutex right, size_t permits, std::condition_variable_any cv, std::mutex m){for(size_t i 0; i 3; i){think(id);eat(id, left, right, permits, cv, m);}
}int main(){size_t permits 4;std::condition_variable_any cv;std::mutex forks[5], m;std::thread philosophers[5];for(size_t i 0; i 5; i){philosophers[i] std::thread(philosopher, i, std::ref(forks[i]), std::ref(forks[(i 1) % 5]), std::ref(permits), std::ref(cv), std::ref(m));}for(auto p:philosophers)p.join();return 0;
}
信号量
这个需要C20思路和上面差不多
#include iostream
#include chrono
#include thread
#include mutex
#include semaphoreconst int N 5;int getThinkTime(){return 1;
}int getEatTime(){return 1;
}void think(size_t id){std::cout id starts thinking. std::endl;std::this_thread::sleep_for(std::chrono::seconds(getThinkTime()));std::cout id all done thinking. std::endl;
}void eat(size_t id, std::mutex left, std::mutex right, std::counting_semaphoreN - 1 permits){permits.acquire();left.lock();std::this_thread::sleep_for(std::chrono::seconds(2));right.lock();std::cout id starts eating om nom nom nom. std::endl;std::this_thread::sleep_for(std::chrono::seconds(getEatTime()));std::cout id all done eating. std::endl;permits.release();left.unlock();right.unlock();
}void philosopher(size_t id, std::mutex left, std::mutex right, std::counting_semaphoreN - 1 permits){for(size_t i 0; i 3; i){think(id);eat(id, left, right, permits);}
}int main(){std::counting_semaphoreN - 1 permits(4);std::mutex forks[5];std::thread philosophers[5];for(size_t i 0; i 5; i){philosophers[i] std::thread(philosopher, i, std::ref(forks[i]), std::ref(forks[(i 1) % 5]), std::ref(permits));}for(auto p:philosophers)p.join();return 0;
}
Leetcode1226
奇偶
class DiningPhilosophers {
public:const int N 5;vectormutex forks;DiningPhilosophers():forks(N) {}void wantsToEat(int philosopher,functionvoid() pickLeftFork,functionvoid() pickRightFork,functionvoid() eat,functionvoid() putLeftFork,functionvoid() putRightFork) {int left philosopher, right (philosopher 1) % N;if(philosopher 1){forks[left].lock();forks[right].lock();pickLeftFork();pickRightFork();}else{forks[right].lock();forks[left].lock();pickRightFork();pickLeftFork();}eat();putLeftFork();putRightFork();forks[left].unlock();forks[right].unlock();}
};条件变量
其实就是模拟信号量
这里注意
[cnt cnt](){return cnt 0;}这个匿名函数需要C14低于14可以[this]不然lambda搜索不到cnt
class Semaphore{
private:int cnt;mutex m;condition_variable_any cv;
public:Semaphore(int cnt):cnt(cnt){}void wait(){lock_guardmutex lg(m);cv.wait(m, [cnt cnt](){return cnt 0;});--cnt;}void signal(){lock_guardmutex lg(m);cnt;if(cnt 1)cv.notify_all();}
};
class DiningPhilosophers {
public:const static int N 5;vectormutex forks;Semaphore permits;DiningPhilosophers():forks(N), permits(N - 1) {}void wantsToEat(int philosopher,functionvoid() pickLeftFork,functionvoid() pickRightFork,functionvoid() eat,functionvoid() putLeftFork,functionvoid() putRightFork) {int left philosopher, right (philosopher 1) % N;permits.wait();forks[left].lock();forks[right].lock();pickLeftFork();pickRightFork();eat();putLeftFork();putRightFork();permits.signal();forks[left].unlock();forks[right].unlock();}
};信号量
需要C20
class DiningPhilosophers {
public:const static int N 5;vectormutex forks;counting_semaphoreN - 1 permits;DiningPhilosophers():forks(N), permits(N - 1) {}void wantsToEat(int philosopher,functionvoid() pickLeftFork,functionvoid() pickRightFork,functionvoid() eat,functionvoid() putLeftFork,functionvoid() putRightFork) {int left philosopher, right (philosopher 1) % N;permits.acquire();forks[left].lock();forks[right].lock();pickLeftFork();pickRightFork();eat();putLeftFork();putRightFork();permits.release();forks[left].unlock();forks[right].unlock();}
};https://web.stanford.edu/class/archive/cs/cs110/cs110.1204/static/lectures/10-threads-and-mutexes.pdf https://blog.csdn.net/tomjobs/article/details/113921067
