十字路口车辆调度

https://segmentfault.com/a/1190000007606710

有两条道路双向两个车道，即每条路每个方向只有一个车道，两条道路十字交叉。假设车辆只能向前直行，而不允许转弯和后退。如果有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是否有空。

https://blog.csdn.net/ZJU_fish1996/article/details/52971428

编写程序实现避免产生死锁和饥饿的车辆通过十字路口方案，并给出详细的设计方案，程序中要有详细的注释。

        1) 每一辆车的行为设计为一个单独的线程。由于有4个不同方向的车辆，需要4种不同类型的线程。

        2) 使用pthread的互斥锁和条件变量解决车辆的同步与互斥。

        3) 对4个不同方向的车辆，要设置车辆队列条件变量如： queueNorth、queueEast、queueSouth、queueWest。比如说，当一辆车从北方来的时候已经在过十字路口，另一辆从北方驶来的车就要等在queueNorth队列中。每一个方向都需要一个计数器来跟踪等待排队的车辆数量。

        4) 按照右边车辆优先通行规则，当一辆车在等待通过路口而它右边不断有车辆到达时，这辆车及这个方向车辆队列会导致饥饿。为了防止饥饿，我们要让刚刚通过路口的A车辆发一个信号给它左边等待的B车辆，接下去让B车辆通行。需要设置下次通行车辆的条件变量firstNorth， firstEast， firstSouth，firstWest

        5) 每一车辆到达十字路口时，要检测是否有死锁发生，当发生死锁时，死锁检测线程必须发出一种信号，例如：从北方来的车辆先行。

        6) 假设我们设计的可执行程序文件名为p1-1，可以用'e'、'w'、's'、'n'来标识东西南北4个方向驶来的车辆，程序p1-1运行时有如下显示（你的程序不一定是这样相同的输出）：

$ ./ p1-1 nsewwewn

car 4 from West arrives at crossing

car 2 from South arrives at crossing

car 1 from North arrives at crossing

car 3 from East arrives at crossing

DEADLOCK: car jam detected, signalling North to go

car 1 from North leaving crossing

car 3 from East leaving crossing

car 2 from South leaving crossing

car 4 from West leaving crossing

car 6 from East arrives at crossing

car 5 from West arrives at crossing

car 8 from North arrives at crossing

car 5 from West leaving crossing

car 6 from East leaving crossing

car 8 from North leaving crossing

car 7 from West arrives at crossing

car 7 from West leaving crossing

     

      

         

对于题目中要求的车辆优先权的理解：

      

 

        两车都希望占据路口a，由于西边的车（W1车）在北边车（N车）的右边，它具有优先权，将先行。

        W1车离开后，虽然对于N车来说，右边还有车，但是离开的车有必要告诉N车让其优先通行。

  实际上是这样处理的：设计了一个布尔量，每个方向各有一个，当车辆处在就绪状态（如左图的W1车），或者进入第一个路口时，标记布尔量为真，离开第一个路口时，标记布尔量为假。当车辆想要进入第二个路口时，需要检查它右边车的布尔量。如果为真，那么该车停等。

       该布尔量在小车进入就绪队列时就设为真，如果它当时还不为真，就认为这辆车还没有进入就绪状态，也就不是同时到达路口，所以不会出现不同步现象。

        N车过路口d（发现右边有车，等待）

        W1车过路口a

        W1车过路口b（唤醒N车）

        N车过路口a（接到信号，过第二个路口，发送一个信号唤醒W2车）

        W2车过路口a（接到信号，过路口a）

新的车谁来唤醒：

 

        新的车有两种唤醒方式：

       1.如果当前方向的车离开后，左边没有车等待，那么它自己唤醒当前方向的一辆车。

       2.如果当前方向的车离开后，左边有车等待，那么它唤醒左边的车，并由左边的车来唤醒其方向的一辆车。

       由于左边要么有车等待，要么没有车等待，所以总会有一个结果被执行，因此我们保证了一定会有新的车被唤醒。

--------------------- 

作者：ZJU_fish1996 

来源：CSDN 

原文：https://blog.csdn.net/ZJU_fish1996/article/details/52971428 

版权声明：本文为博主原创文章，转载请附上博文链接！

 差不多是这个题 不过是横竖两个方向 没有四个方向那么复杂...其实好好准备下多线程相关准备一个周末也能捡起来 但是实在完全没有准备 过去两个月都是准备算法和OOD

/**
 *方法：使用四种线程代表四个方向的车，通过互斥锁和信号量实现题目里的要求。
 */
#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);
}

d