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輛車都想駛過十字路口，那么對(duì)資源的要求如下：

• 向北行駛的車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è)立即通行的信號(hào)；

3)避免產(chǎn)生死鎖；

4)避免產(chǎn)生饑餓；

5)任何一個(gè)線程（車輛）不得采用單點(diǎn)調(diào)度策略；

6)由于使用and型信號(hào)量機(jī)制會(huì)使線程（車輛）并發(fā)度降低且引起不公平（部分線程饑餓），本題不得使用and型信號(hào)量機(jī)制，即在上圖中車輛不能要求同時(shí)滿足兩個(gè)象限才能順利通過，如南方車輛不能同時(shí)判斷a和b是否有空。

解決方案

（可能存在一些不足，希望大家指出）：

/**
*方法：使用四種線程代表四個(gè)方向的車，通過互斥鎖和信號(hào)量實(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)度的資料請(qǐng)關(guān)注碩編程其它相關(guān)文章！