1. Assume there are cars driving on one side of the interstate which has two lan

Question

1. Assume there are cars driving on one side of the interstate which has two lanes. At one point along the road there is construction that causes only one lane to continue. We want to be able to merge the cars in the two lanes into one lane without having any accidents. Assume that if a car reaches the merging point, and there is no car in the other lane at the same spot, then the car can continue along the road. If a car reaches the merging point and finds one car already there in the other lane, then it must wait its turn. Whenever there are multiple cars waiting in both lanes, the cars should take turns moving forward. Write pseudocode algorithms using semaphores/counters/etc. for cars in the left and right lanes that will allow the merging to occur as described.

2. There are many one lane bridges in the upper Northeast. Assume such a bridge exists between a set of farms and the fields in which the farmers harvest their crops. Also assume that there are 15 farms on one side of the bridge, and every day each farmer that lives on his farm will want to go back and forth across the bridge, harvesting crops in the field and bringing them back to the farm. Not every farmer works at the same pace. If a farmer gets to the bridge and wants to cross it, the following must occur. If there is nobody else on the bridge, the farmer may drive across. If there is already a farmer driving across the bridge in the other direction, the farmer must wait until the bridge is empty before crossing. If there is already a farmer driving across the bridge in the same direction, the new farmer may follow after him and be on the bridge at the same time.

a) Write a pseudocode algorithm using semaphores/counters/etc. for a farmer's daily actions to control access to the bridge and stop any accidents from happening. Assume the bridge is big enough to hold the cars of all 15 farmers at once if necessary.

b) Now assume the bridge is only big enough to allow three cars onto it at the same time. Show how your algorithm needs to be modified to work in this situation.

3. Assume we were to get a teaching assistant for this course that would hold office hours in B 240. He would sit at one of the cubicles and could only help one student in the class at a time. However, assume there are four chairs in the room that students can sit in to wait for the TA to be available to help them. When nobody is around the TA plays video games. If a student shows up and the TA is playing games, he should stop and help the student. If a student arrives, but the TA is busy, the student will sit down in an empty chair if one exists. When the current student is finished, the student who has waited the longest will be helped next. If there is not an empty chair available, the student will go away and come back later.

a) Write a pseudocode algorithm using semaphores/counters/etc. for both the student and the TA to describe their actions so that everybody gets the help they need.

b) Now assume that we get a second TA for the course and he can also help students in the same room. A waiting student can be helped equally well by either TA. Show how the algorithms for the students and TAs would need to be adjusted to handle this situation.

c) Now assume that the second TA must help students for a different course, but still in the same room with a common set of chairs for students to wait in. So, even if there are students waiting in the room for help, if they are not in the course that a TA is helping with, that TA is free to play video games. Show how the algorithms for a student and a TA would need to be adjusted to handle this situation.

Explanation / Answer

1:

When the Car reaches the merging point, we have following constraints:
If there is no car in the other lane at the same spot, then the car can continue along the road.
If a car reaches the merging point and finds one car already there in the other lane, then it must wait its turn
Whenever there are multiple cars waiting in both lanes, the cars should take turns moving forward

Pseudocode is as follows:

Only one thread (car) can access the shared state at a time.
Cars will be waiting for their turn to continue on the road. Use array with 2 condition variables, waitToContinue[2].
It is required to know the number of cars waiting for their turns (cars, initialise to 0), and the current lane of the cars (call it currentlane). It is required to know the number of cars waiting to continue in each lane; use an array wait[2].

ArriveMerge(int lane) {
lock.acquire();

// while cannot continue, wait
while ((cars == 3) ||
(cars > 0 && currentlane != lane)) {
wait[lane]++;
waitToContinue[lane].wait();
wait[lane]--;
}

// continue on the road
cars++;
currentlane = lane;

lock.release();
}

ExitMerge() {
lock.acquire();

// exit the merge point
cars--;

// if a car in lane 1 wants to go, wake them
if (wait[currentlane] > 0)
waitToContinue[currentlane].signal();
// else if empty, wake car from other lane
else if (cars == 0)
waitToContinue[1-currentlane].broadcast();

lock.release();
}

Related Questions

Navigate

• Browse (All)
• Browse 1
• Subjects

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