セマフォ同期を実装する次の問題を解決するにはどうすればよいですか...
この問題の目的のために、交差点を上記のようにモデル化し、交差点を四分の一に分割し、その部分を通って交差点に入る車線の各四分の一を識別します。(明確にするために: 道路の右側を運転しています。) ターンは、交差点の 1 つ、2 つ、または 3 つの部分を通る進行によって表されます (簡単にするために、交差点では U ターンが発生しないと仮定します)。 . そのため、車が北から近づいてきた場合、行き先に応じて次のように交差点を進みます。
| ! + ^ |
| ! + ! |
| v + ! |
--------------------------
<----|NW + NE| <----
| + |
++++++++++++++++++++++++++
| + |
----> |SW + SE| ---->
--------------------------
| ! + ^ |
| ! + ! |
| v + ! |
Right: NW
Straight: NW-SW
Left: NW-SW-SE
交差点に最初に到着した人が先に進みます。
2 台の車が同時に交差点の同じ部分にいることはできません。同じようにすれ違うな。2 台の車が同じ方向から近づき、同じ方向に向かっている場合、最初に交差点に到着した車が最初に目的地に到着するはずです。同様に、車は交差点で互いに「飛び越える」べきではありません。たとえば、車が交差点に入って直進しているとします。次に、別の車が同じ方向から交差点に入り、左に進んでいます。2 番目の車は、最初の車の後に交差点を出る必要があります。しかし、車が交差点に入って左に進んでいるとします。別の車が同じ方向から交差点に進入し、右に進んでいる場合、1 台目の車が 2 台目の車の前にあるにもかかわらず、先に交差点を離れることがあります。まだ左折できないかもしれません。各車は、交差点に近づく (approaching)、交差点の 1 つ以上の領域 ((region1)、region2、および region3) に入り、交差点を離れる (exit) ときに、車の番号、進入方向、および目的地を示すメッセージを出力する必要があります。方向。
ある方向から交差点に接近する車は、同じ順序で交差点に進入する必要があります。車が交差点に近づいて速度を落とす前に、同期をとってはならないことに注意してください。言い換えると、交差点の region1 に入る直前に近づいていることを単純に出力しないでください。たとえば、2 つのイベント間に同期プリミティブが必要です。その他の注文要件はありません。たとえば、異なる方向から接近する車の順序要件はありません。一度に 2 台以上の車が交差点にいることを許可し、どの方向からの交通も他の方向からの交通を枯渇させないようにする必要があります。
createcars は 20 台の車を作成し、それぞれにランダムな方向を割り当てる approachintersection に渡します。それらにランダムなターン方向を割り当てる必要があります。アプローチ交差点でもこれを行うことができます。
このソリューションの実装に役立つ場合とそうでない場合があるその他のルーチンは、直進、右折、左折です。使うことも捨てることもできます。
以下は、東から到着して西に向かっている 1 台の車 (8 号車) の出力例です。領域 (例: region1) は、各車に対して相対的に定義されることに注意してください。右に行く車は region1 を出力します。直進する車は、region1 と region2 を出力します。左に行く車は、region1、region2、および region3 を出力します。
approaching: car = 8, direction = E, destination = W
region1: car = 8, direction = E, destination = W
region2: car = 8, direction = E, destination = W
leaving: car = 8, direction = E, destination = W
以下は、私が持っているルーチンです..
#include <types.h>
#include <lib.h>
#include <test.h>
#include <thread.h>
/*
* Number of cars created.
*/
#define NCARS 20
/*
*
* Function Definitions
*
*/
static const char *directions[] = { "N", "E", "S", "W" };
static const char *msgs[] = {
"approaching:",
"region1: ",
"region2: ",
"region3: ",
"leaving: "
};
/* use these constants for the first parameter of message */
enum { APPROACHING, REGION1, REGION2, REGION3, LEAVING };
static void
message(int msg_nr, int carnumber, int cardirection, int destdirection)
{
kprintf("%s car = %2d, direction = %s, destination = %s\n",
msgs[msg_nr], carnumber,
directions[cardirection], directions[destdirection]);
}
/*
* gostraight()
*
* Arguments:
* unsigned long cardirection: the direction from which the car
* approaches the intersection.
* unsigned long carnumber: the car id number for printing purposes.
*
* Returns:
* nothing.
*
* Notes:
* This function should implement passing straight through the
* intersection from any direction.
* Write and comment this function.
*/
static void gostraight(unsigned long cardirection, unsigned long carnumber)
{
/*
* Avoid unused variable warnings.
*/
(void) cardirection;
(void) carnumber;
}
/*
* turnleft()
*
* Arguments:
* unsigned long cardirection: the direction from which the car
* approaches the intersection.
* unsigned long carnumber: the car id number for printing purposes.
*
* Returns:
* nothing.
*
* Notes:
* This function should implement making a left turn through the
* intersection from any direction.
* Write and comment this function.
*/
static void turnleft(unsigned long cardirection, unsigned long carnumber)
{
/*
* Avoid unused variable warnings.
*/
(void) cardirection;
(void) carnumber;
}
/*
* turnright()
*
* Arguments:
* unsigned long cardirection: the direction from which the car
* approaches the intersection.
* unsigned long carnumber: the car id number for printing purposes.
*
* Returns:
* nothing.
*
* Notes:
* This function should implement making a right turn through the
* intersection from any direction.
* Write and comment this function.
*/
static void turnright(unsigned long cardirection, unsigned long carnumber)
{
/*
* Avoid unused variable warnings.
*/
(void) cardirection;
(void) carnumber;
}
/*
* approachintersection()
*
* Arguments:
* void * unusedpointer: currently unused.
* unsigned long carnumber: holds car id number.
*
* Returns:
* nothing.
*
* Notes:
* I need to change this function to implement sempahore synchronization. These
* threads are created by createcars(). Each one must choose a direction
* randomly, approach the intersection, choose a turn randomly, and then
* complete that turn. The code to choose a direction randomly is
* provided, the rest is left to you to implement. Making a turn
* or going straight should be done by calling one of the functions
* above.
*/
static void approachintersection(void * unusedpointer, unsigned long carnumber)
{
int cardirection;
/*
* Avoid unused variable and function warnings.
*/
(void) unusedpointer;
(void) carnumber;
(void) gostraight;
(void) turnleft;
(void) turnright;
/*
* cardirection is set randomly.
*/
cardirection = random() % 4;
}
/*
* createcars()
*
* Arguments:
* int nargs: unused.
* char ** args: unused.
*
* Returns:
* 0 on success.
*
* Notes:
* Driver code to start up the approachintersection() threads.
* I can modify this code as well for my solution..
*/
int createcars(int nargs, char ** args)
{
int index, error;
/*
* Avoid unused variable warnings.
*/
(void) nargs;
(void) args;
/*
* Start NCARS approachintersection() threads.
*/
for (index = 0; index < NCARS; index++) {
error = thread_fork("approachintersection thread",
NULL,
index,
approachintersection,
NULL
);
/*
* panic() on error.
*/
if (error) {
panic("approachintersection: thread_fork failed: %s\n",
strerror(error)
);
}
}
return 0;
}
[1]: http://i.stack.imgur.com/1389H.gif