Cars and Trucks on a Bridge problem

This is a review problem for the CISC324 midterm exam.

Problem statement

Here is a simulation of a bridge with a load-limit of 8 cars. Cars always cross the bridge eastbound: a car crosses the bridge and then drives around in a big loop to get back to the bridge entrance, to cross the bridge eastbound again.

bridge: semaphore = 8;

car thread  // many car threads are created in the main program
----------
loop
sleep(long time)    // This simulates that the car is driving around until it reaches the bridge.
Acquire(bridge)     // Get onto the bridge (may involve waiting)
sleep(short time)   // This simulates that the car is crossing the bridge
Release(bridge)     // Leave the bridge
end loop

Now we define a truck thread. Trucks act just like cars (sleep, then cross the bridge; repeat). A truck weighs twice as much as a car, so the bridge can hold up to four trucks. Or, the bridge can hold one truck and up to six cars, etc.

(a) Here is a proposed solution. Keep the car thread the same as above, use the same "bridge" semaphore, and add this truck thread.

truck thread  // many truck threads are created in the main program
------------
loop
sleep(long time)  // The truck is driving around until it reaches the bridge.
Acquire(bridge)     
Acquire(bridge)     
sleep(short time) // The truck is crossing the bridge
Release(bridge)
Release(bridge)
end loop

This code can deadlock. Give an example of how deadlock can arise.

(b) Write code to solve this problem correctly. (Show initial values for semaphores and other variables you use. Show your new code for the truck and car threads.) A correct solution:

prevents deadlock
respects the load limit (doesn't overload the bridge)
does not make a car or truck wait needlessly (when the bridge isn't full)
preserves the order of traffic arrival (the car or truck that arrived first is allowed onto the bridge first). You may assume that semaphore queues are First In First Out.