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

これは簡単な問題ではありません。2 つの解決策を示します。

最初の明白なもの: turnleft, turnright, gostraightaddの先頭でlock(car, intersection_mutex);、各関数の終了直前にミューテックスを解放する、交差点全体の 1 つのミューテックス。これにより、一度に 1 台の車だけが交差点を通過できます。これの利点は、理解しやすく、デッドロックが発生しないことです。欠点は、一度に 1 台の車しか進入できないことですが、ご存知のように、交差しないパスを移動する 2 台の車は問題なく進入できます。以下に例を示し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_straightturn_left2 つのミューテックスをロックする必要があります (左に回すには 3 つ必要だと主張できます..)。したがって、両方のミューテックスを取得できない場合は、バックオフする必要があります。これを運転規則に変換します。

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

したがって、まっすぐ進むには、最初に最も近いミューテックスを取得し、次にパス内の次のミューテックスを取得して終了できるようにする必要があります。両方を取得できない場合は、ロックした方を解放する必要があります。解放しないとデッドロックします。

これを行うには、次の 2 つのヘルパー関数を追加します。

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をロックできなくなります。ただし、東に向かって右に曲がって南に曲がる車は、南西にロックをかけることができます。

したがって、このスキームは機能します。各関数は指定された順序でロックを取得するため、デッドロックは発生しません。したがって、コーナーをめぐって競合するスレッドの循環チェーンは存在し得ません。基本的に、スレッド1がスレッド2のロック解除を待機している場合、スレッド2はスレッド1によって既に取得されているロックを必要としないことを意味します。したがって、デッドロックは発生しません。

于 2012-11-30T20:33:28.967 に答える
0

あなたが何をする必要があるのか​​よくわかりませんが、私の理由を説明してみます。それがあなたの問題があると思うので、私はデザインから始めます。

単純な交差点、2つの道路、ライト、標識がないと想定します。どの車も北、南、東、西の4方向から交差点に到着でき、交差点を通過するときに各車は3つの異なる方向のいずれかを取ることができます。このように、4 * 3 = 12考慮しなければならないさまざまな道路セクションがあり、すべてが異なります。

車が特定の瞬間に特定のパスで交差点を横断する場合、ゼロ以上、理論的には最大11の異なるセクションでトラフィックをブロックします(実際には、少なくとも2つのセクションが空いているため、制限は9です)。これらはブロックする必要があります。ところで、12の異なるセクションの写真を作成すると役立ちます。

ミューテックスを使用する場合は、セクションごとに1つ必要です(必ずしも車用である必要はありません)。右ハンドル、右前の運転シナリオを想定すると、南から直進しようとしている車がブロックされます。

  • 東から来る車が直進します。
  • 東から来た車が左に行きます。
  • 東から右に行く車。
  • 西から来た車が直進します。
  • 西から来た車が左に行きます。
  • 北から左に行く車。

他のすべてのセクションは他の車のために無料です。到着/方向のペアごとに、このブロックのリストを作成できます。[反対方向から左折する2台の車がどのようにすれ違うかを指定する必要があります。つまり、左に曲がる北から来る車が左に曲がる南から来る車をブロックするかどうか、または互いに先行して通過できるかどうかを指定する必要があります]

各車(読み取り:スレッド)に代わって非常に多くのミューテックス(セクションごとに1つ)をブロックすると、問題が発生します:デッドロック。ここでその問題を解決するために、交差点全体に追加の「マスター」ミューテックスを作成することをお勧めします。車が到着すると、

  1. マスターミューテックスをブロックしようとします。失敗した場合はブロックします。
  2. 次に、必要な各セクションミューテックスをブロックしようとします。失敗した場合は、正常にロックされたミューテックスをすべて解放し、マスターミューテックスのロックを解除して待機してから、1からやり直してください。
  3. 必要なすべてのセクションミューテックスをブロックすることに成功した場合は、マスターミューテックスのロックを解除し、交差点を通過します(時間がかかります)。

交差点を通過した後、車

  1. マスターミューテックスをブロックしようとします。失敗した場合はブロックします。
  2. 取得したすべてのセクションミューテックスのロックを解除します。
  3. マスターミューテックスのロックを再び解除します。
  4. 新しい方向に進み続けます。

[明確にするために編集され、pthreadミューテックスはロックとバックオフを試みることができます]マスターミューテックスは常に非常に迅速に解放され、車が必要なすべてのセクションミューテックスを取得できるかどうかを確認するためにのみ使用されます。いずれにせよ、マスターミューテックスはその直後にリリースされます。

マスターミューテックスがないと、ミューテックスを取得するための厳密な順序を使用することによってのみデッドロックを回避できます。これにより、交差点が部分的になります。2台の車が同時に到着した場合、1つの方向/方向の組み合わせが常に別の車に勝ちます。マスターミューテックスはそれを回避します。

于 2012-11-30T20:14:30.523 に答える