Deadlocked Cats And Dogs

Computer Science Level 1

Alice and Bob are best friends living in houses separated by a field. However, they have a problem. Alice owns a cat and Bob owns a dog, and their pets do not get along. As a result they can never let both their pets loose in the field together.

They set up the following protocol to decide when to let their pets out:

  • Alice's Algorithm:
    1. Raise a red flag on the terrace.
    2. Wait while Bob has a blue flag raised on his terrace.
    3. Let the cat out for an hour.
    4. Lower the red flag.
  • Bob's Algorithm:
    1. Raise a blue flag on the terrace.
    2. Wait while Alice has a red flag raised on her terrace.
    3. Let the dog out for an hour.
    4. Lower the blue flag.

Provided that Alice and Bob strictly follow the protocol, is it guaranteed that whenever either owner wants to let their pet out, they will eventually be able to do so?

Low Level Concurrency by Olena Syrota .
Yes No

Agnishom Chattopadhyay by Agnishom Chattopadhyay , 22, India

This section requires Javascript.
You are seeing this because something didn't load right. We suggest you, (a) try refreshing the page, (b) enabling javascript if it is disabled on your browser and, finally, (c) loading the non-javascript version of this page . We're sorry about the hassle.

2 solutions

Emily Namm
Sep 26, 2016

If Alice and Bob both have their flags raised, but neither has their pet out, then they will wait indefinitely. Alice does not let her pet out while Bob's flag is raised, and the same for Bob, and neither will lower their flag until after they've let out their pets.

Such a situation could occur if, for example, both Alice and Bob were to raise their flags at the same time.

14 Helpful 1 Interesting 1 Brilliant 0 Confused

Yes, that is unfortunate. Can you think of a solution for Alice and Bob that makes sure that they both eventually succeed?

Agnishom Chattopadhyay - 4 years, 8 months ago

Well one thing that comes to mind is to make one pet owner "dominant" so to speak. Were you to change Bob's algorithm so that he doesn't wait for Alice's flag to go down (just take out 2), you would never get the problem where they wait indefinitely. To avoid the problem where Bob releases his dog while Alice's cat is out you can add a conditional after letting the cat out: if Bob raises his flag at any time bring the cat back in. This isn't exactly fair in how the time is split, but I beleive it would solve the problem.

Another thing you could try is to change Bob's algorithm so that while Alice's flag is up he waits not only to release his pet but also to raise his flag (switch 1 and 2), then you wouldn't have the situation where they both have flags up at the same time. It still would be impossible for their pets to be out at the same because Bob's flag is always up while his dog is out, he won't release his dog while Alice's flag is up.

Emily Namm - 4 years, 8 months ago

Log in to reply

The first idea is definitely possible if it was okay to give a pet more importance than the other. The second idea also seems to be very interesting. As far as I can see, it protects against deadlocks as well.

I will soon post another clever solution to this problem as a problem

Agnishom Chattopadhyay - 4 years, 8 months ago

First of all according to the protocol set by both the friends, they would not be able to get their pets out if the other has his flag raised. Next-, if both of them raise their flags at the same time then none will be able to get their pets out as according to the protocol --- they cannot get their pets out if the other has his flag raised.

0 Helpful 0 Interesting 0 Brilliant 0 Confused

0 pending reports

×

Problem Loading...

Note Loading...

Set Loading...