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 loopNow 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 loopThis 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:
Deadlock occurs in the given code if 8 trucks each execute their first Acquire(bridge) statement, and all wait on the second Acquire(bridge) statement. Here are two ways that this situation can arise. The first one is unlikely, only arising with an unlikely timing of context switches. The second situation causes deadlock without needing context switches at a particular time.
First scenario: 8 trucks arrive at an empty bridge. The first truck executes the first Acquire(bridge), then there is a context switch to the second truck, which executes one Acquire(bridge), and so on. After all 8 trucks do this, the bridge semaphore value is 0, and all 8 trucks are stuck at Acquire(bridge) statements. All future cars and trucks that arrive will also get stuck at Acquire(bridge). Since there are no cars or trucks on the bridge, no process is going to Release(bridge) in the future. This is deadlock.
Second scenario: 8 trucks arrive (not necessarily at the same time) when the bridge is full. This results in deadlock, no matter what the detailed timing is. To see this, imagine the situation where the bridge has 8 cars on it (actually, it could be any mix of cars and trucks that sums to a load of 8). Now truck T1 arrives, and waits at its first Acquire(bridge) statement. A while later truck T2 arrives, and so on. So the situation is that we have 8 cars on the bridge and 8 trucks (or more) queued waiting for their first Acquire(bridge) statement. Eventually the 8 cars start exiting the bridge. The cars might exit the bridge at about the same time, or their exits might be spaced out a bit. Either way, with FIFO semaphore queues, the Release(bridge) from the first exiting car is received by truck T1. Then truck T1 executes its second Acquire(bridge), getting into the end of the semaphore queue, behind trucks T2 to T8. The Release(bridge) from the second exiting car is received by truck T2, and so on. At the end, all car traffic has left the bridge, and all 8 trucks are stuck waiting for their second Acquire(bridge). Deadlock!
Note: the given code also has traffic ordering problems. For example, suppose 8 cars are on the bridge, and then 10 trucks show up, followed by 10 more cars. The 10 cars will get onto the bridge before the 10 trucks do. This is because the trucks have to go through the Acquire(bridge) queue twice, so the second time they queue up, they end up behind the 10 cars.
Solution 1: mutual exclusion for bridge entry
The deadlock problem arises because a truck can get "halfway" onto the bridge, and be interrupted by another
arriving vehicle. Thus, we should put a mutual-exclusion semaphore around the
Acquire(bridge) statements for the truck.
Watch out! We also need to put the same mutual-exclusion semaphore into the car process. This is to
preserve traffic order. When Truck T gets past
its first Acquire(bridge) it moves on to the second Acquire(bridge). At this
point, Truck T should be first in line in this semaphore queue. It should
not be waiting behind a bunch of other vehicles that arrived after Truck T did.
The following code achieves this by making sure that the "bridge" semaphore
always has at most one vehicle waiting in it. All other vehicles wait at
Acquire(BridgeEntryQueue).
var bridge: semaphore = 8;
BridggeEntryQueue: semaphore = 1; // Only one vehicle at a time can wait for the "bridge" semaphore.
// The other vehicles wait using Acquire(BridgeEntryQueue).
Car process
-----------
loop
sleep(long time)
Acquire(BridgeEntryQueue)
Acquire(bridge)
Release(BridgeEntryQueue)
sleep(short time) // now the car is on the bridge
Release(bridge)
end loop
Truck process
--------------
loop
sleep(long time)
Acquire(BridgeEntryQueue)
Acquire(bridge)
Acquire(bridge)
Release(BridgeEntryQueue)
sleep(short time) // now the truck is on the bridge
Release(bridge)
Release(bridge)
end loop
Solution 2: allow at most 7 trucks to compete for bridge entry
This is inspired by the Dining Philosophers, where a deadlock-free solution can be achieved by allowing at most four philosophers to compete for chopsticks at any one time. If we allow at most 7 trucks to compete for bridge entry, then there cannot be deadlock. However, traffic order is not preserved: cars can move ahead of trucks, either while the trucks are waiting for TruckCrowdControl, or when trucks get into the bridge semaphore queue a second time.
var bridge: semaphore = 8;
TruckCrowdControl: semaphore = 7; // Allow at most 7 trucks to compete for bridge entry
Car process is unchanged: same as in the given code.
Truck process
--------------
loop
sleep(long time)
Acquire(TruckCrowdControl)
Acquire(bridge)
Acquire(bridge)
Release(TruckCrowdControl)
sleep(short time) // now the truck is on the bridge
Release(bridge)
Release(bridge)
end loop
Solution 3: use shared counters; only do a semaphore Acquire in the case where the bridge is already full
In this solution, shared counters (with mutex protection) are used to enforce the load limit on the bridge. The semaphore BridgeWait is only used when arriving traffic finds that the bridge is already full.
It is tricky to code this solution properly. Things to watch out for include the following.
(1) Make sure that Acquire() and Release() are balanced, occurring in equal
numbers.
If an entering car only *sometimes*
executes Acquire(Sem), then it is incorrect if the exiting car *always* gives
a Release(Sem). The Sem value
will become much too large as car processes execute this code.
(2) Mutex protection must be used when updating counter values
(e.g. "LoadOnBridge++"). It also needs to be
used when there is a test of a counter value (e.g. "if LoadOnBridge>7")
followed by an action (where the action depends on the outcome of the test).
(3) It is important to use one semaphore (such as BridgeWait) for both cars and trucks. If separate
semaphores CarWait and TruckWait are used, it is very hard to preserve traffic order. The car/truck that
exits the bridge has a hard time figuring out whether to signal CarWait or TruckWait.
(4) Special care must be taken to signal the "second half" of a truck properly. If a car exits a full
bridge, and a truck is waiting, that truck can only get onto the bridge halfway. The next car or truck that
exits the bridge must signal the "second half" of this truck. It is tricky to find a way for the exiting
car/truck to correctly test whether or not there is a truck that's already
"half on the bridge".
While this approach is tricky to code correctly, it is a perfectly valid approach. It's a sensible thing to
try, if you happen not to think of Solution 1 above.
Here's the best I could come up with. Maybe someone else can find a simpler way to code this. Let me know!
No student was able to code a correct
solution of this type during the midterm exam. But quite a few students made
good starts given the time constraints of the exam, and I gave them almost full credit for their answer.
var mutex: semaphore = 1 // Provides mutual exclusion for counters and boolean variables.
LoadOnBridge: integer = 0 // The current load on the bridge. Value ranges from 0 to 8.
NumTrucksWaiting: integer = 0 // The number of trucks that are waiting.
NumCarsWaiting: integer = 0 // The number of cars that are waiting.
BridgeWait: semaphore = 0 // Cars and trucks wait here, if the bridge is full when they arrive.
TruckSecondHalf: semaphore = 0 // A truck executes Acquire(BridgeWait) and then Acquire(TruckSecondHalf).
TruckHalfOn: boolean = false // TruckHalfOn is true when a truck has completed Acquire(BridgeWait) and
// is waiting at Acquire(TruckSecondHalf).
BridgeSignalReceived: semaphore = 0 // When a process gets past Acquire(BridgeWait), it replies
// with Release(BridgeSignalReceived). This sort of signal+reply
// arrangement is called "handshaking".
TruckSignalReceived: semaphore = 0 // When a process gets past Acquire(TruckSecondHalf), it replies
// with Release(TruckSignalReceived).
Car process
------------
loop
sleep(long time)
Acquire(mutex)
if LoadOnBridge==8 {
NumCarsWaiting++
Release(mutex)
// Wait until the car can get onto the bridge.
// You may be surprised to see that the next lines of code update NumCarsWaiting without
// first executing Acquire(mutex). Here's how this works: some other
// process executes Acquire(mutex) and then calls procedure TakeLoadOffBridge().
// That procedure executes "Release(BridgeWait)" followed by "Acquire(BridgeSignalReceived)".
// So in our code here, once we got past the Acquire(BridegeWait), we know that the
// other process is holding mutex, and doing nothing until we execute "Release(BridgeSignalReceived)".
Acquire(BridgeWait) // We wait here until some process executes Release (BridgeWait).
NumCarsWaiting--
Release(BridgeSignalReceived) // The process that is holding mutex can now continue.
}
else { // The car does not have to wait. Get onto the bridge.
LoadOnBridge++
Release(mutex)
}
sleep(short time) // now the car is on the bridge
Acquire(mutex)
TakeLoadOffBridge() // This procedure is defined below
Release(mutex)
end loop
Truck process
--------------
loop
sleep(long time)
Acquire(mutex)
if LoadOnBridge>=7 {
NumTrucksWaiting++
Release(mutex)
// Wait until the first half of the truck can get onto the bridge.
Acquire(BridgeWait) // The process that executes Release(BridgeWait) holds mutex.
TruckHalfOn = true
Release(BridgeSignalReceived) // The process that is holding mutex can now continue.
// Wait until the second half of the truck can get onto the bridge.
Acquire(TruckSecondHalf) // The process that executes Release(TruckSecondHalf) holds mutex.
TruckHalfOn = false
NumTrucksWaiting--
Release(TruckSignalReceived) // The process that holds mutex can now continue
}
else { // The truck does not have to wait. Get onto the bridge.
LoadOnBridge = LoadOnBridge+2
Release(mutex)
}
sleep(short time) // now the truck is on the bridge
Acquire(mutex)
TakeLoadOffBridge() // This procedure is defined below
TakeLoadOffBridge()
Release(mutex)
end loop
Procedure TakeLoadOffBridge
---------------------------
// The calling process already holds mutex, at the time that TakeLoadOffBridge() is called
Procedure TakeLoadOffBridge() {
if TruckHalfOn {
Release(TruckSecondHalf) // Let the truck get completely onto the bridge
// LoadOnBridge does not have to be changed: the second half of the truck
// replaces the load we are taking off of the bridge.
Acquire(TruckSignalReceived) // Wait until the truck process finishes updating shared variables.
// (Next, we will exit procedure TakeLoadOffBridge, and release mutex.)
}
else if (NumTrucksWaiting>0 || NumCarsWaiting>0) {
Release(BridgeWait) // Let a car enter the bridge, or a truck half-enter the bridge.
// LoadOnBridge does not have to be changed: the new car or half-truck
// replaces the load we are taking off of the bridge.
Acquire(BridgeSignalReceived)// Wait until the car or truck finishes updating shared variables.
}
else
LoadOnBridge=LoadOnBridge-1
} // end of procedure TakeLoadOffBridge