5

我正在尝试使用线程和互斥锁来模拟交叉点。

我有过海峡,左转,右转的功能。现在,我有一个接近十字路口的功能。这会产生一个随机的方向和转弯。每个线程共享即将到来的交叉点。

我已经为各个方向的所有汽车定义了所有锁。

采取海峡两岸功能。它有一个 switch 语句,只打印什么车当时正在做什么。现在,我只是不知道该锁定什么功能。如果汽车是朝北的方向,我会锁定东西方向,并且与汽车朝南的方向相同吗?

这是我的锁,它只是调用一个函数来锁定或解锁

#define NUMCARS 30

#define lock_NW(CAR) lock(CAR, NW_mutex)
#define lock_NE(CAR) lock(CAR, NE_mutex)
#define lock_SW(CAR) lock(CAR, SW_mutex)
#define lock_SE(CAR) lock(CAR, SE_mutex)

#define unlock_NW(CAR) unlock(CAR, NW_mutex)
#define unlock_NE(CAR) unlock(CAR, NE_mutex)
#define unlock_SW(CAR) unlock(CAR, SW_mutex)
#define unlock_SE(CAR) unlock(CAR, SE_mutex)

这是主要的

int main(int argc, char **argv){
/* Initial variables*/
int index, tid;
unsigned int carids[NUMCARS];
pthread_t carthreads[NUMCARS];

/* Start up a thread for each car*/ 
for(index = 0; index <NUMCARS; index++){
carids[index] = index;
tid = pthread_create(&carthreads[index], NULL, approachintersection,  (void*)&carids[index]);
}

/* Wait for every car thread to finish */
for(index = 0; index <NUMCARS; index++){
pthread_join(carthreads[index], NULL);
}
printf("Done\n");
return 1;
}

这是调用函数的接近交叉点

static void * approachintersection(void* arg){
unsigned int * carnumberptr;
unsigned int carnumber;
orientation_t cardir = (orientation_t)random()%4;
unsigned long turn = random()%3;

carnumberptr = (unsigned int*) arg;
carnumber = (unsigned int) *carnumberptr;

if(turn==LEFT){
turnleft(cardir, carnumber);
} else if(turn==RIGHT){
turnright(cardir, carnumber);
} else {//straight
gostraight(cardir, carnumber);
}

return (void*)carnumberptr;
}

现在,这是我要锁定适当方向的海峡功能。

 /*
  cardirection - The direction the car is pointing.  If it is pointing NORTH,
  it is starting from the South-Eastern corner of the intersection
  and "going straight" means it wants to move SOUTH to NORTH.

  valid options: NORTH, SOUTH, EAST, WEST

 carnumber -    The car identifier
*/


static void gostraight(orientation_t cardirection, unsigned int carnumber){

switch(cardirection){
case NORTH:
printf("Car %d, Moving South-North\n", carnumber);
break;
case SOUTH:
printf("Car %d, Moving North-South\n", carnumber);
break;
case EAST:
printf("Car %d, Moving West-East\n", carnumber);
break;
case WEST:
printf("Car %d, Moving East-West\n", carnumber);
break;
}
}

所以,如果接近的汽车从南指向北,那么这辆车就是 SE 车,我会用 lock_SE(CAR) 锁定箱体东、西打印功能?防止其他线程进入和打印?所以我会锁定解锁打印语句?

还是我会锁定整个 switch 语句?

** 编辑:这会是这样做的方法吗?**

static void turnleft(orientation_t cardirection, unsigned int carnumber){

int CAR;
CAR = carnumber;


  switch(cardirection){
  case NORTH:
  lock_SE(CAR)
  printf("Car %d, Moving South-West\n", carnumber);
  unlock_SE(CAR)
  break;
  case SOUTH:
  lock_NW(CAR)
  printf("Car %d, Moving North-East\n", carnumber);
  unlock_NW(CAR)
  break;
  case EAST:
  lock_SW(CAR)
  printf("Car %d, Moving West-North\n", carnumber);
  unlock_SW(CAR)
  break;
  case WEST:
  lock_NE(CAR)
  printf("Car %d, Moving East-South\n", carnumber);
  unlock_NE(CAR)
  break;
  }

}

4

3 回答 3

3

这不是一个容易的问题。我将尝试展示两种解决方案。

第一个明显的:整个交集的一个互斥锁,在turnleft, turnright, gostraightadd的开头lock(car, intersection_mutex);,就在每个函数结束之前释放所说的互斥锁。这一次只能让一辆车通过十字路口。这样做的好处是易于理解并且不会导致死锁。缺点是一次只能有一辆车进入,但众所周知,两辆行驶在不相交路径的汽车可以毫无问题地进入。这是一个示例go_straight()(其他人遵循相同的方法):

static void gostraight(orientation_t cardirection, unsigned int carnumber){
    pthread_mutex_lock(&intersection_mutex);
    switch(cardirection){
        case NORTH:
            printf("Car %d, Moving South-North\n", carnumber);
            break;
        case SOUTH:
            printf("Car %d, Moving North-South\n", carnumber);
            break;
        case EAST:
            printf("Car %d, Moving West-East\n", carnumber);
            break;
        case WEST:
            printf("Car %d, Moving East-West\n", carnumber);
            break;
        }
    }
    pthread_mutex_unlock(&intersection_mutex);
}

为了一次让不止一辆汽车进入,我们需要一种细粒度的方法。细粒度方法的问题在于它更难实现和正确。两者都go_straight需要turn_left锁定两个互斥锁(您可能会争辩说左转需要三个......)。因此,如果您不能同时获得两个互斥锁,则需要退出。将其转化为驾驶规则:

you must not enter the intersection before you can exit it. 

因此,要直行,我们必须首先获得离您最近的互斥体,然后才能退出路径中的下一个互斥体。如果我们不能同时获得两者,我们必须释放我们锁定的那个。如果我们不释放它,我们将死锁。

为此,我将添加两个辅助函数:

static void lock_two(pthread_mutex_t *a, pthread_mutex_t *b) {
    while(1) { 
        pthread_mutex_lock(a);
        if(pthread_mutex_trylock(b) == 0) 
            break;
        else
        /* We must release the previously taken mutex so we don't dead lock the intersection */
            pthread_mutex_unlock(a);                            
        pthread_yield(); /* so we don't spin over lock/try-lock failed */
    }
}
static void unlock_two(pthread_mutex_t *a, pthread_mutex_t *b) {
    pthread_mutex_unlock(a);
    pthread_mutex_unlock(b);
}

这是我的直接版本:

static void gostraight(orientation_t cardirection, unsigned int carnumber){  
    switch(cardirection){
        case NORTH:
            lock_two(&SE_mutex, &NE_mutex); 
            printf("Car %d, Moving South-North\n", carnumber);
            unlock_two(&SE_mutex, &NE_mutex); 
            break;
        case SOUTH:
            lock_two(&NW_mutex, &SW_mutex); 
            printf("Car %d, Moving North-South\n", carnumber);
            unlock_two(&NW_mutex, &SW_mutex); 
            break;
        case EAST:
            lock_two(&SW_mutex, &SE_mutex); 
            printf("Car %d, Moving West-East\n", carnumber);
            unlock_two(&SW_mutex, &SE_mutex); 
       break;
       case WEST:
            lock_two(&NE_mutex, &NW_mutex); 
            printf("Car %d, Moving East-West\n", carnumber);
            unlock_two(&NE_mutex, &NW_mutex); 
            break;
    }
}

turn_left然后将需要遵循相同的方法。

于 2012-11-30T21:04:18.917 回答
1

那么这样的事情将适用于直行功能: -

static void gostraight(orientation_t cardirection, unsigned int carnumber){
  int CAR;
  cAR = carnumber;

  switch(cardirection){
    case NORTH:
      lock_SE(CAR);
      lock_NE(CAR);
      printf("Car %d, Moving South-North\n", carnumber);
      unlock_NE(CAR);
      unlock_SE(CAR);
      break;
    case SOUTH:
      lock_NW(CAR);
      lock_SW(CAR);
      printf("Car %d, Moving North-South\n", carnumber);
      unlock_SW(CAR);
      unlock_NW(CAR);
      break;
    case EAST:
      lock_SE(CAR);
      lock_SW(CAR);
      printf("Car %d, Moving West-East\n", carnumber);
      unlock_SE(CAR);
      unlock_SW(CAR);
      break;
    case WEST:
      lock_NE(CAR);
      lock_NW(CAR);
      printf("Car %d, Moving East-West\n", carnumber);
      unlock_NW(CAR);
      unlock_NE(CAR);
      break;
  }
}

对于左转,(仅举一个例子):-

switch(cardirection) {
  case NORTH:
    lock_SE(CAR);
    lock_NE(CAR);
    lock_NW(CAR);
    printf("Car %d, Moving South-West\n", carnumber);
    unlock_NW(CAR);
    unlock_NE(CAR);
    unlock_SE(CAR);
    break;
}

对于右转(又是一个例子):-

switch(cardirection) {
  case EAST:
    lock_SW(CAR);
    printf("Car %d, Moving East-South\n", carnumber);
    unlock_SW(CAR);
    break;
}

请注意,为了避免死锁,我总是以 SE、NE、NW、SW 的任意顺序锁定它们。

为什么这行得通?例如,乘坐一辆想要直行向南的汽车和另一辆向北行驶并左转向西的汽车。那么如果左转车先到,它会依次锁定SE、NE和NW,而直行车将无法锁定NW。但是,向东行驶并右转向南的汽车将能够锁定 SW。

因此,该方案将起作用。它不会出现死锁,因为每个函数都以给定的顺序获取锁。因此,永远不会有循环的线程链竞争角点。基本上,如果线程 1 正在等待线程 2 释放锁,那么这意味着线程 2 不需要线程 1 已经获得的任何锁。因此不会出现死锁。

于 2012-11-30T20:33:28.967 回答
0

我不太确定我理解你需要做什么,但我会尝试解释我的推理。我将从设计开始,因为我想这就是您的问题所在。

你假设一个普通的十字路口,两条路,没有灯,没有标志。任何一辆车都可以从北、南、东、西四个不同方向到达交叉口,每辆车在通过交叉口时可以选择三个不同方向之一。这样,您4 * 3 = 12就必须考虑不同的路段,所有路段都不同。

如果汽车在某个时刻穿过某条路径上的交叉路口,它会在 0 个或多个,理论上最多 11 个不同的路段阻塞交通(实际上,至少有两个路段保持空闲,因此限制为 9 个)。这些你必须阻止。顺便说一句,如果你为 12 个不同的部分拍一张照片,它会有所帮助。

如果您想使用互斥锁,则每个部分都需要一个(不一定是汽车)。假设一个右手,左前右的驾驶场景,一辆从南方来的打算直行的汽车会阻塞:

  • 一辆从东边直行的汽车;
  • 一辆来自东方的汽车向左行驶;
  • 一辆从东边驶来的汽车向右行驶;
  • 一辆从西边直行的汽车;
  • 一辆从西边来的汽车向左行驶;
  • 一辆从北方来的汽车向左行驶;

所有其他部分对其他车辆免费。您可以为每个到达/方向对创建此块列表。[您必须指定两辆从相反方向左转的汽车如何相互通过,即从北向左转的汽车是否会阻挡从南向左转的汽车,或者它们是否可以相互通过]

代表每辆车(阅读:线程)阻塞这么多互斥锁(每个部分一个)会带来一个问题:死锁。为了在这里解决这个问题,我建议您为整个交叉点创建一个额外的“主”互斥锁。一辆车到了,

  1. 它试图阻止主互斥锁;如果不成功,它会阻塞。
  2. 然后它会尝试阻止它需要的每个部分互斥体;如果不成功,释放所有成功锁定的互斥体,解锁主互斥体,等待,然后从1开始重试。
  3. 如果它成功阻止了所有需要的部分互斥锁,则解锁主互斥锁,并通过交叉路口(花费时间)。

过了路口后,车

  1. 试图阻止主互斥锁;如果不成功,它会阻塞。
  2. 它解锁所有获得的部分互斥锁。
  3. 它再次解锁主互斥锁。
  4. 继续朝着新的方向前进。

[编辑澄清,pthread 互斥体允许尝试锁定和退出] 主互斥体总是很快释放,仅用于查看汽车是否可以获得所有必要的部分互斥体。无论哪种方式,主互斥锁都会在此之后立即释放。

如果没有主互斥锁,您只能通过使用严格的获取互斥锁的顺序来避免死锁。这将使交叉路口局部化:如果两辆车同时到达,一个方向/转弯组合总是会胜过另一辆车。主互斥体避免了这种情况。

于 2012-11-30T20:14:30.523 回答