摘要:假设车辆只能向前直行,而不允许转弯和后退。我们要实现十字路口交通的车辆同步问题,防止汽车在经过十字路口时产生死锁和饥饿。在我们的系统中,东西南北各个方向不断地有车辆经过十字路口注意不只有辆,同一个方向的车辆依次排队通过十字路口。
实例要求:
有两条道路双向两个车道,即每条路每个方向只有一个车道,两条道路十字交叉。假设车辆只能向前直行,而不允许转弯和后退。如果有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#include #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 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 > q_north(true), q_south(true), q_west(true), q_east(true); NormalMutex f_north(true), f_south(true), f_west(true), f_east(true); NormalMutex r_a, r_b, r_c, r_d; /* define the integer to store the current car in four direction */ NormalMutex cur_n, cur_s, cur_e, cur_w; /* define bool to make sure wether a direction has car */ NormalMutex isin_n, isin_s, isin_e, isin_w; /* mark the remaining road*/ NormalMutex resource; /* mark the end of deadlock*/ NormalMutex 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 *road; NormalMutex *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 ",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 *road; NormalMutex *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 ",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 *isin; NormalMutex *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 *r1,*r2; NormalMutex *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 ",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 > *qu; NormalMutex *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 (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 (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 (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 (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."< (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 (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 (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 (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<
文章版权归作者所有,未经允许请勿转载,若此文章存在违规行为,您可以联系管理员删除。
转载请注明本文地址:https://www.ucloud.cn/yun/9675.html
摘要:前言在上一篇文章中多线程奇幻之旅算法实现线程安全,我们介绍了和方式实现线程安全类的方法,两种方式一个是锁定阻塞方式,一个是非阻塞方式。 前言 在上一篇文章中《Java多线程奇幻之旅——CAS算法实现线程安全》,我们介绍了Synchronized和CAS方式实现线程安全类的方法,两种方式一个是锁定阻塞方式,一个是非阻塞方式。本文专注于两种实现方式效率问题。本文是上篇文章的延续,会借用到上...
摘要:一,智慧园区建设的核心价值,三维可视化应用,未来智慧园区管理发展方向。,应急指挥预案可视化通过对应急预案的资源流程事件预案进行可视化管理,为园区重大危险事故提供高效调度指挥管理手段。获取智慧园区三维可视化系统源码 一,智慧园区建设的核心价值 1,三维可视化应用,未来智慧园区管理发展方向。 ...
摘要:其中判断信号灯的和车辆的位置关系可以通过,车辆的航向角信息,以及车辆的经纬度信息,目标点的经纬度信息,进行计算和处理后可以获取目标点和车辆的相对位置。 首先简单说明一下闯红灯预警算法流程图,总共分为7步如下图所示: 背景技术: 本算法主要是基于V2X通信技术,在道路交通中,车辆与车辆之间,...
摘要:年月日上午阿里云消息服,队列消息发送以及消费的并发测试解析配置文件二者等价线程数并发数程序入口准备工作发送消息线程池一个计数信号量。但是,不使用实际的许可对象,只对可用许可的号码进行计数,并采取相应的行动。 package com.study.mq.aliyunmns; import java.io.BufferedInputStream; import java.io.FileIn...
摘要:剩余问题当固定了线程池的线程数量后,仍然存在一个严重的问题实际情况下,很多连接都是长连接,这意味着一个线程在处理一个请求时,到的数据将会是是不连续的。 Linux C 线程池实现 学习网络编程时,自己动手实现一个Web Server是一个很有意思的经历。大多数Web Server都有一个特点:在单位时间内需要处理大量的请求,并且处理这些请求的时间往往还很短。《深入理解计算机系统》 (C...
阅读 1156·2021-11-04 16:11
阅读 4256·2021-10-14 09:42
阅读 2808·2021-10-12 10:11
阅读 2588·2021-09-29 09:47
阅读 1359·2021-09-22 15:40
阅读 897·2019-08-29 15:43
阅读 2653·2019-08-29 13:50
阅读 1446·2019-08-29 13:28