ansaurus

Question

Answer 1

+2 A:

In real life you would solve this problem with a traffic light which is either red-north/green-south, green-north/red-south, or red-north/red-south, and sensors in the approach and exit lanes at both ends of the bridge.

Suppose the light starts out red-north/green-south. Cars can flow from south to north without stopping. When a car approaches from the north, it stops at the red light and triggers the north approach sensor. That makes the light go red-south, but it's still red-north as well. When all the cars currently on the bridge have left (triggering the north exit sensor on their way out) the light can change to green-north. That state persists until another car comes from the south and triggers the south approach sensor.

Think about how you'd translate that into code. (You'll need to use the counting property of semaphores.)

Zack 2010-10-11 16:53:18

by counting property you mean incrementing/decrementing with post/wait, as well as sem_getvalue?

Google 2010-10-11 17:05:20

On second thought, one of the conditions is that when no cars are on the bridge the lights on both ends are green. I thought it would work letting the cars race to the lights and the first one there north or south can enter and make the other end red. However I have been unable to do this effectively with sem_wait and sem_post

Google 2010-10-11 17:14:44

Q1: Yes, by counting property I mean incrementing/decrementing with post/wait. Q2: In real life, you *never ever* make a traffic light be green in conflicting directions simultaneously. Think about what happens if two cars approach the bridge at high speed from both directions at the same time; the driver who loses the race may not have time to stop. A similar situation could occur in your code if the semaphores are ever both "green" at the same time.

Zack 2010-10-11 17:29:57

This should be solved easily by setting sem_init and using value 1 for north and 0 for south, starting north as green and south red. Then as long as your code never makes both green you should be fine I assume. I wonder why the professor said to set both green with no traffic, hmm.

Google 2010-10-11 17:45:33

Answer 2

+1 A:

This is some pseudo python I just whipped up. Basically block one way and let a limited number cars through. Depending on how you're using your variables, this might be totally wrong:

function main():
    while(true):
        if(north_car):
            let_north_cars_through()
        if(south_car):
            let_south_cars_through()


function let_south_cars_through():
    sem_wait(north)
    for(i = 0; i < max cars; i++):
        if(south_car):
            cross_bridge()
        else:
            break;

    sem_post(north)

function let_north_cars_through()
    sem_wait(south)
    for(i = 0; i < max cars; i++):
        if(north_car):
            cross_bridge()
        else:
            break;

    sem_post(south)

MStodd 2010-10-11 16:59:34

This is pretty interesting, but what if the stream of cars is random, like (n = north and s = south) n,n,n,s,s,n,n,n,n,s,s,s,s. This is kind of how I approached it using a thread as random traffic with a switch case for north/south cars.

Google 2010-10-11 17:11:14

Ah. I was thinking that north cars would come into one queue and south would come into another queue. Hmmm..

MStodd 2010-10-11 17:24:39

ansaurus

tags:

views:

answers:

single-lane bridge problem

related questions