Linux/C++多線程實(shí)例學(xué)習(xí)十字路口車輛調(diào)度
實(shí)例要求:
有兩條道路雙向兩個(gè)車道,即每條路每個(gè)方向只有一個(gè)車道,兩條道路十字交叉。假設(shè)車輛只能向前直行,而不允許轉(zhuǎn)彎和后退。如果有4輛車幾乎同時(shí)到達(dá)這個(gè)十字路口,如圖(a)所示;相互交叉地停下來,如圖(b),此時(shí)4輛車都將不能繼續(xù)向前,這是一個(gè)典型的死鎖問題。從操作系統(tǒng)原理的資源分配觀點(diǎn),如果4輛車都想駛過十字路口,那么對資源的要求如下:
- 向北行駛的車1需要象限a和b;
- 向西行駛的車2需要象限b和c;
- 向南行駛的車3需要象限c和d;
- 向東行駛的車4需要象限d和a。
我們要實(shí)現(xiàn)十字路口交通的車輛同步問題,防止汽車在經(jīng)過十字路口時(shí)產(chǎn)生死鎖和饑餓。在我們的系統(tǒng)中,東西南北各個(gè)方向不斷地有車輛經(jīng)過十字路口(注意:不只有4輛),同一個(gè)方向的車輛依次排隊(duì)通過十字路口。按照交通規(guī)則是右邊車輛優(yōu)先通行,如圖(a)中,若只有car1、car2、car3,那么車輛通過十字路口的順序是car3->car2->car1。
車輛通行總的規(guī)則
1)來自同一個(gè)方向多個(gè)車輛到達(dá)十字路口時(shí),車輛靠右行駛,依次順序通過;
2)有多個(gè)方向的車輛同時(shí)到達(dá)十字路口時(shí),按照右邊車輛優(yōu)先通行規(guī)則,除非該車在十字路口等待時(shí)收到一個(gè)立即通行的信號;
3)避免產(chǎn)生死鎖;
4)避免產(chǎn)生饑餓;
5)任何一個(gè)線程(車輛)不得采用單點(diǎn)調(diào)度策略;
6)由于使用AND型信號量機(jī)制會(huì)使線程(車輛)并發(fā)度降低且引起不公平(部分線程饑餓),本題不得使用AND型信號量機(jī)制,即在上圖中車輛不能要求同時(shí)滿足兩個(gè)象限才能順利通過,如南方車輛不能同時(shí)判斷a和b是否有空。
解決方案
(可能存在一些不足,希望大家指出):
/** *方法:使用四種線程代表四個(gè)方向的車,通過互斥鎖和信號量實(shí)現(xiàn)題目里的要求。 */ #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函數(shù):
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; }
以上就是Linux/C++多線程實(shí)例學(xué)習(xí)十字路口車輛調(diào)度的詳細(xì)內(nèi)容,更多關(guān)于Linux/C++ 多線程車輛調(diào)度的資料請關(guān)注腳本之家其它相關(guān)文章!
相關(guān)文章
基于一個(gè)簡單定長內(nèi)存池的實(shí)現(xiàn)方法詳解
本篇文章對一個(gè)簡單定長內(nèi)存池的實(shí)現(xiàn)方法進(jìn)行了詳細(xì)的分析介紹。需要的朋友參考下2013-05-05C++ 學(xué)習(xí)之旅 Windows程序內(nèi)部運(yùn)行原理
學(xué)習(xí)C++與.net不同的是,一定要搞清楚Windows程序內(nèi)部運(yùn)行原理,因?yàn)樗婕按蠖鄶?shù)是操作系統(tǒng)的調(diào)用,而.net畢竟是在.netFrameWork上唱戲2012-11-11C++中引用的相關(guān)知識點(diǎn)小結(jié)
引用是C++一個(gè)很重要的特性,顧名思義是某一個(gè)變量或?qū)ο蟮膭e名,對引用的操作與對其所綁定的變量或?qū)ο蟮牟僮魍耆葍r(jià),這篇文章主要給大家總結(jié)介紹了C++中引用的相關(guān)知識點(diǎn),需要的朋友可以參考下2022-03-03一文詳解C++中動(dòng)態(tài)內(nèi)存管理
這篇文章主要介紹了一文詳解C++中動(dòng)態(tài)內(nèi)存管理,文章圍繞主題展開詳細(xì)的內(nèi)容介紹,具有一定的參考價(jià)孩子沒需要的朋友可以才可以參考一下2022-07-07淺析C++11中的右值引用、轉(zhuǎn)移語義和完美轉(zhuǎn)發(fā)
對于c++11來說移動(dòng)語義是一個(gè)重要的概念,一直以來我對這個(gè)概念都似懂非懂。最近翻翻資料感覺突然開竅,因此順便記錄下C++11中的右值引用、轉(zhuǎn)移語義和完美轉(zhuǎn)發(fā),方便大家查閱參考。2016-08-08關(guān)于c++ 智能指針及 循環(huán)引用的問題
下面小編就為大家?guī)硪黄P(guān)于c++ 智能指針及 循環(huán)引用的問題。小編覺得挺不錯(cuò)的,現(xiàn)在就分享給大家,也給大家做個(gè)參考。一起跟隨小編過來看看吧2017-01-01