Cinderella and the Prince are getting divorced. To divide their property, they h

Question

Cinderella and the Prince are getting divorced. To divide their property, they have agreed on the following algorithm. Every morning, each one may send a letter to the other’s lawyer requesting one item of property. Since it takes a day for letters to be delivered, they have agreed that if both discover that they have requested the same item on the same day, the next day they will send a letter canceling the request. Among their property is their dog, Woofer, Woofer’s doghouse, their canary, Tweeter, and Tweeter’s cage. The animals love their houses, so it has been agreed that any division of property separating an animal from its house is invalid, requiring the whole division to start over from scratch. Both Cinderella and the Prince desperately want Woofer. So they can go on (separate) vacation, each spouse has programmed a PC to handle the negotiation. When they come back from vacation, the computers are still negotiating. Why? Is the deadlock Possible? Is the starvation possible? Discuss shortly.

Explanation / Answer

If both programs ask for Woofer first, the computers will starve with endless sequence: request Woofer, cancel request, request Woofer, cancel request, etc. If one of them asks for the doghouse and the other asks for the dog, we have a deadlock, which is detected by both parties and then broken, but it is just repeated on the next cycle. Either way, if both computers have been programmed to go after the dog or the doghouse first, either starvation or deadlock ensues. There is not really much difference between the two here. In most deadlock problems, starvation does not seem serious because introduction random delays will usually make it very unlikely. That approach does not work here.

If both parties always request the same item (eg Woofer), livelock occurs because the transactions are

always cancelled.

Cinderella requests Prince requests End Result

Woofer Woofer Cancels after a day because both want the same thing.

Woofer Woofer’s House Have to start over (after a day) because the dog and his house cannot

be separated.

Woofer’s House Woofer Have to start over (after a day) because the dog and his house cannot

be separated.

Woofer’s House Woofer’s House Cancels after a day because both want the same thing.

Deadlock is not possible because illegal settlements restart the negotiations (same for starvation).

Related Questions

Navigate

• Browse (All)
• Browse C
• Subjects

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