There is an intersection with cars (threads) turning right, left and straight. H

Question

There is an intersection with cars (threads) turning right, left and straight. How to implement a concurrent thread program that only uses mutex locks.

I can create any number of locks.

I have the functions with arguments = gostraight(car direction, car#), goright(car direction, car#), goleft(car direction, car#).

I need to avoid deadlocks!!!.

I also have an approachintersection function with (int car number) argument. This function randomly selects a turn direction and type of turn.Every time a thread/car is created this function is called to randomly create direction and select turn type.

I need a help thinking of how to implement this without causing any race conditions or deadlocks. Pseudo code would be great, or just an explanation of how the locks should be set.

Thanks.

Explanation / Answer

to solve this you should first model the intersection dividing it into 4 quarters and identifiying each quarter with whic lane enteres the intersection through that portion as shown in the above diagram.

Suppose we are driving on the right of the road. Turns are reprsented by a progression through one, two, or three portions of the intersections. Assume that U turns do not occur in the intersection. So if a car approaches from North, depending on where it is going, it proceeds through the intersection as follows:

| ! + ^ |

| ! + ! |

| v + ! |

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

<------------| NW + NE | <------------

| + |

+++++++++++++++++++++++++++

| + |

------------> | SW + SE | -------------->

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

| ! + ^ |

| ! + ! |

| v + ! |

So, which ever car will come first at the intersection, will proceed first. No two cars will be in the same portion of the intersection at the same time or will pass the intersection in the same way. If two cars arrive in the same direction and head in the same direction, the first car at the intersection will reach the destion first. No two cars will jump over each other in the intersection. Each car should print a message whenever approaching at the interssction and entering on or two regions and leaving the intersection. The message should include Car number, Approach direction and destination direction.

Cars approaching the intersection from a give direction should reach the intersection in the same order. Do not simply print approaching just before entering region1 of the intersetion. There are no ordering requirements of the cars approaching from different directions. Two or more cars should be allowed to be in the intersection at a time without allowing any traffic to starve traffic from any other direction.

Create 20 cars and pass them to approach intersection and assign each car a random direction. Do this in approach intersection as well.

Following routines can be used in the code:

#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 ",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 carapproaches 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 carapproaches 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:
* 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 ",
strerror(error)
);
}
}

return 0;
}

Related Questions

Navigate

• Browse (All)
• Browse T
• Subjects

Integrity-first tutoring: explanations and feedback only — we do not complete graded work. Learn more.