Linux/C++多线程实例学习十字路口车辆调度
makebo · 169浏览 · 发布于2023-05-15
这篇文章主要为大家介绍了Linux/C++多线程实例学习十字路口车辆调度示例详解，有需要的朋友可以借鉴参考下，希望能够有所帮助，祝大家多多进步，早日升职加薪
实例要求：
有两条道路双向两个车道，即每条路每个方向只有一个车道，两条道路十字交叉。假设车辆只能向前直行，而不允许转弯和后退。如果有4辆车几乎同时到达这个十字路口，如图（a）所示；相互交叉地停下来，如图（b），此时4辆车都将不能继续向前，这是一个典型的死锁问题。从操作系统原理的资源分配观点，如果4辆车都想驶过十字路口，那么对资源的要求如下：
向北行驶的车1需要象限a和b；
向西行驶的车2需要象限b和c；
向南行驶的车3需要象限c和d；
向东行驶的车4需要象限d和a。
我们要实现十字路口交通的车辆同步问题，防止汽车在经过十字路口时产生死锁和饥饿。在我们的系统中，东西南北各个方向不断地有车辆经过十字路口（注意：不只有4辆），同一个方向的车辆依次排队通过十字路口。按照交通规则是右边车辆优先通行，如图(a)中，若只有car1、car2、car3，那么车辆通过十字路口的顺序是car3->car2->car1。
车辆通行总的规则
1)来自同一个方向多个车辆到达十字路口时，车辆靠右行驶，依次顺序通过；
2)有多个方向的车辆同时到达十字路口时，按照右边车辆优先通行规则，除非该车在十字路口等待时收到一个立即通行的信号；
3)避免产生死锁；
4)避免产生饥饿；
5)任何一个线程（车辆）不得采用单点调度策略；
6)由于使用AND型信号量机制会使线程（车辆）并发度降低且引起不公平（部分线程饥饿），本题不得使用AND型信号量机制，即在上图中车辆不能要求同时满足两个象限才能顺利通过，如南方车辆不能同时判断a和b是否有空。
解决方案
（可能存在一些不足，希望大家指出）：
/**
*方法：使用四种线程代表四个方向的车，通过互斥锁和信号量实现题目里的要求。
*/
#include "../lib/myhead.h"
#include <pthread.h>
#include <queue>
#define SLEEP_MS(ms) usleep((ms)*1000)
using std::queue;
enum Direction{
NORTH = 1,
EAST = 2,
SOUTH = 3,
WEST = 4
};
/* generate mutex and cond that are required */
template<typename T> struct NormalMutex{
T val; //store some value that you can use
bool flag; //control wether using cond
pthread_mutex_t mutex;
pthread_cond_t cond;
NormalMutex():flag(false){
int err = pthread_mutex_init(&mutex,nullptr);
if(err!=0)
err_exit(err,"mutex init failed");
}
/* if you need cond, please set flag true */
NormalMutex(bool flag):NormalMutex(){
this->flag = flag;
if(flag){
int err = pthread_cond_init(&cond,nullptr);
if(err!=0)
err_exit(err,"cond init failed");
}
}
~NormalMutex(){
pthread_mutex_destroy(&mutex);
if(flag)
pthread_cond_destroy(&cond);
}
};
/* define the struct containing mutex and cond */
NormalMutex< queue<int> > q_north(true), q_south(true), q_west(true), q_east(true);
NormalMutex<bool> f_north(true), f_south(true), f_west(true), f_east(true);
NormalMutex<int> r_a, r_b, r_c, r_d;
/* define the integer to store the current car in four direction */
NormalMutex<long long> cur_n, cur_s, cur_e, cur_w;
/* define bool to make sure wether a direction has car */
NormalMutex<bool> isin_n, isin_s, isin_e, isin_w;
/* mark the remaining road*/
NormalMutex<int> resource;
/* mark the end of deadlock*/
NormalMutex<bool> dl_over(true);
/* signal four of few val to go firstly */
void init_car(){
if(q_north.val.size()>0){ //if there are val waiting in the queue, pop one and let it go
cur_n.val = q_north.val.front(); //pop
q_north.val.pop();
pthread_cond_broadcast(&q_north.cond); //let it go
}
if(q_south.val.size()>0){
cur_s.val = q_south.val.front();
q_south.val.pop();
pthread_cond_broadcast(&q_south.cond);
}
if(q_west.val.size()>0){
cur_w.val = q_west.val.front();
q_west.val.pop();
pthread_cond_broadcast(&q_west.cond);
}
if(q_east.val.size()>0){
cur_e.val = q_east.val.front();
q_east.val.pop();
pthread_cond_broadcast(&q_east.cond);
}
}
int enterTheCrossing(Direction dir,const long long &car_no){
NormalMutex<int> *road;
NormalMutex<bool> *isin;
string direction;
switch(dir){
case NORTH:
road = &r_c; isin = &isin_n; direction = "North"; break;
case EAST:
road = &r_b; isin = &isin_e; direction = "East"; break;
case SOUTH:
road = &r_a; isin = &isin_s; direction = "South"; break;
case WEST:
road = &r_d; isin = &isin_w; direction = "West"; break;
}
/* enter the crossing */
pthread_mutex_lock(&(road->mutex));
printf("car %lld from %s arrives at crossing\n",car_no,direction.c_str());
/* things to do after lock the first road */
isin->val = true; //mark that there is car in north direction
pthread_mutex_lock(&resource.mutex);
int tem_re = --resource.val; //let the resource minus one
pthread_mutex_unlock(&resource.mutex);
return tem_re;
}
void detectDeadlock(Direction dir,int tem_re){
if(tem_re!=0) return ;
string direction;
NormalMutex<int> *road;
NormalMutex<bool> *first, *isin;
switch(dir){
case NORTH:
direction = "East"; road = &r_c;isin = &isin_n; first = &f_east; break;
case EAST:
direction = "South"; road = &r_b;isin = &isin_e; first = &f_south; break;
case SOUTH:
direction = "West"; road = &r_a;isin = &isin_s; first = &f_west; break;
case WEST:
direction = "North"; road = &r_d;isin = &isin_w first = &f_north; break;
}
printf("DEADLOCK car jam detected. signal %s to go\n",direction.c_str());
dl_over.val = false;
/* deal with the deadlock by making left car go */
pthread_mutex_unlock(&(road->mutex)); //release the road
isin->val = false; //let left car go first
pthread_cond_signal(&(first->cond));// send the signal to left car
/* wait the end of deadlock */
pthread_mutex_lock(&dl_over.mutex);
while(dl_over.val==false)
pthread_cond_wait(&dl_over.cond,&dl_over.mutex);
pthread_mutex_unlock(&dl_over.mutex);
/* recover from deadlock */
pthread_mutex_lock(&(road->mutex));
isin->val = true;
}
void judgeRight(Direction dir){
NormalMutex<bool> *isin;
NormalMutex<bool> *first;
switch(dir){
case NORTH:
isin = &isin_w; first = &f_north; break;
case EAST:
isin = &isin_n; first = &f_east; break;
case SOUTH:
isin = &isin_e; first = &f_south; break;
case WEST:
isin = &isin_s; first = &f_west; break;
}
/* juage that if car can go first */
pthread_mutex_lock(&(first->mutex));
while(isin->val)
pthread_cond_wait(&(first->cond),&(first->mutex));
pthread_mutex_unlock(&(first->mutex));
}
void gotoNextRoad(Direction dir,const long long & car_no){
string direction;
NormalMutex<int> *r1,*r2;
NormalMutex<bool> *isin,*lisin,*first;
switch(dir){
case NORTH:
r1 = &r_c; r2 = &r_d; isin = &isin_n;lisin = &isin_e; first = &f_east;
direction = "North";
break;
case EAST:
r1 = &r_b; r2 = &r_c; isin = &isin_e;lisin = &isin_s; first = &f_south;
direction = "East";
break;
case SOUTH:
r1 = &r_a; r2 = &r_b; isin = &isin_s;lisin = &isin_w; first = &f_west;
direction = "South";
break;
case WEST:
r1 = &r_d; r2 = &r_a; isin = &isin_w;lisin = &isin_n; first = &f_north;
direction = "West";
break;
}
/* go to next road */
pthread_mutex_lock(&(r2->mutex));
/* unlock the first road */
pthread_mutex_unlock(&(r1->mutex));
printf("car %lld from %s leaving crossing\n",car_no,direction.c_str());
/* things to do after unlocking the first road */
pthread_mutex_lock(&resource.mutex);
resource.val++; //resource plus one
pthread_mutex_unlock(&resource.mutex);
/* out of the deadlock */
dl_over.val = true;
pthread_cond_signal(&dl_over.cond);
/* unlock the second road */
pthread_mutex_unlock(&(r2->mutex));
isin->val = false; //the road don't have car
/* if left direction has waiting car,let it go first*/
pthread_mutex_lock(&(first->mutex));
first->val = true; //let left car go first, if exist
pthread_mutex_unlock(&(first->mutex));
pthread_cond_signal(&first->cond); //send signal to left car
}
void doAfterGo(Direction dir){
NormalMutex<queue<int> > *qu;
NormalMutex<long long> *cur;
switch(dir){
case NORTH:
qu = &q_north; cur = &cur_n; break;
case EAST:
qu = &q_east; cur = &cur_e; break;
case SOUTH:
qu = &q_south; cur = &cur_s; break;
case WEST:
qu = &q_west; cur = &cur_w; break;
}
/* let the next car in the same direction to go */
pthread_mutex_lock(&(qu->mutex));
pthread_mutex_lock(&(cur->mutex));
cur->val = qu->val.front(); //set next car to go
qu->val.pop(); //leave the queue
pthread_mutex_unlock(&(qu->mutex));
pthread_mutex_unlock(&(cur->mutex));
pthread_cond_broadcast(&(qu->cond));
}
void * n_car(void *arg){
/* get the car_no from arg*/
long long car_no = reinterpret_cast<long long>(arg);
/* block and wait the signal from init_car() or val over it */
pthread_mutex_lock(&q_north.mutex);
while(cur_n.val != car_no){
pthread_cond_wait(&q_north.cond,&q_north.mutex);
}
pthread_mutex_unlock(&q_north.mutex);
int tem_re = enterTheCrossing(NORTH,car_no);
detectDeadlock(NORTH,tem_re);
judgeRight(NORTH);
gotoNextRoad(NORTH,car_no);
doAfterGo(NORTH);
return nullptr;
}
/* the thread representing the car coming from east */
void * e_car(void *arg){
/* get the car_no from arg*/
long long car_no = reinterpret_cast<long long>(arg);
pthread_mutex_lock(&q_east.mutex);
while(cur_e.val != car_no){
pthread_cond_wait(&q_east.cond,&q_east.mutex);
}
pthread_mutex_unlock(&q_east.mutex);
int tem_re = enterTheCrossing(EAST,car_no);
detectDeadlock(EAST,tem_re);
judgeRight(EAST);
gotoNextRoad(EAST,car_no);
doAfterGo(EAST);
return nullptr;
}
/* the thread representing the car from south */
void * s_car(void *arg){
/* get the car_no from arg*/
long long car_no = reinterpret_cast<long long>(arg);
pthread_mutex_lock(&q_south.mutex);
while(cur_s.val != car_no){
pthread_cond_wait(&q_south.cond,&q_south.mutex);
}
pthread_mutex_unlock(&q_south.mutex);
int tem_re = enterTheCrossing(SOUTH,car_no);
detectDeadlock(SOUTH,tem_re);
judgeRight(SOUTH);
gotoNextRoad(SOUTH,car_no);
doAfterGo(SOUTH);
return nullptr;
}
/* the thread representing the car from west */
void * w_car(void *arg){
/* get the car_no from arg*/
long long car_no = reinterpret_cast<long long>(arg);
pthread_mutex_lock(&q_west.mutex);
while(cur_w.val != car_no){
pthread_cond_wait(&q_west.cond,&q_west.mutex);
}
pthread_mutex_unlock(&q_west.mutex);
int tem_re = enterTheCrossing(WEST,car_no);
detectDeadlock(WEST,tem_re);
judgeRight(WEST);
gotoNextRoad(WEST,car_no);
doAfterGo(WEST);
return nullptr;
}
int main(int argc,char *argv[]){
/* check the argv */
if(argc!=2){
cout<<"Please input the car stream."<<endl;
exit(0);
}
/* initialize the variable */
cur_n.val = cur_s.val = cur_e.val = cur_w.val = 0;
isin_n.val = isin_s.val = isin_e.val = isin_w.val = false;
resource.val = 4;
int err = 0;
int carNumber = strlen(argv[1]);
pthread_t tids[carNumber+1];
/* create all cars and push them into queue */
for(int i=1;i<=carNumber;++i){
switch(argv[1][i-1]){
case 'n':
q_north.val.push(i);
err = pthread_create(&tids[i],nullptr,n_car,reinterpret_cast<void *>(i));
if(err!=0)
err_exit(err,"can't create thread");
break;
case 'w':
q_west.val.push(i);
err = pthread_create(&tids[i],nullptr,w_car,reinterpret_cast<void *>(i));
if(err!=0)
err_exit(err,"can't create thread");
break;
case 's':
q_south.val.push(i);
err = pthread_create(&tids[i],nullptr,s_car,reinterpret_cast<void *>(i));
if(err!=0)
err_exit(err,"can't create thread");
break;
case 'e':
q_east.val.push(i);
err = pthread_create(&tids[i],nullptr,e_car,reinterpret_cast<void *>(i));
if(err!=0)
err_exit(err,"can't create thread");
break;
}
}
/* wake up the car in front of queue */
init_car();
/* join threads */
for(int i=1;i<=carNumber;++i){
err = pthread_join(tids[i],nullptr);
if(err!=0)
err_exit(err,"can't join thread %d",i);
}
exit(0);
}代码中使用到的error handler函数：
static void
err_doit(bool, int, const char *, va_list);
void
err_exit(int error, const char *fmt,...){
va_list ap;
va_start(ap,fmt);
err_doit(true,error,fmt,ap);
va_end(ap);
exit(1);
}
static void
err_doit(bool errnoflag, int error, const char *fmt, va_list ap){
char buf[MAXLINE];
vsnprintf(buf,MAXLINE-1,fmt,ap);
if(errnoflag)
snprintf(buf+strlen(buf),MAXLINE-strlen(buf)-1,": %s",strerror(error));
cerr<<buf<<endl;
}相关推荐
将Fedora 29升级到Fedora 30
吴振华 · 704浏览 · 2019-05-14 22:00:02
吴振华 · 704浏览 · 2019-05-14 22:00:02
有效避免数据丢失！Redis持久化方案选择详解
manongba · 921浏览 · 2019-05-15 10:58:03
manongba · 921浏览 · 2019-05-15 10:58:03
使用Nginx反向代理到go-fastdfs
iamitnan · 727浏览 · 2019-05-23 13:42:00
iamitnan · 727浏览 · 2019-05-23 13:42:00
利用VLC搭建组播流服务器
追忆似水年华 · 2693浏览 · 2019-06-14 11:27:06
追忆似水年华 · 2693浏览 · 2019-06-14 11:27:06
如何设计一个优秀的分布式系统？重要因素、工具、策略都在这里
chenguangming9 · 712浏览 · 2019-06-18 11:00:10
chenguangming9 · 712浏览 · 2019-06-18 11:00:10
用Bash脚本监控Linux上的内存使用情况
吴振华 · 974浏览 · 2019-06-24 11:27:02
吴振华 · 974浏览 · 2019-06-24 11:27:02
分类专栏
最新发布
最热排行
0评论