In the Serengeti National Park in Tanzania, Africa, there is a deep canyon that can only be crossed by the baboons living in the park using a rope that has been fastened on both sides by the park administration. Several baboons can cross at the same time, provided they are all going in the same direction. If eastward-moving and westward-moving baboons ever get onto the rope at the same time, the baboons will get stuck in a deadlock because it is impossible for one baboon to climb over another one while suspended over the canyon.

a) Using Java semaphores or Java synchronisation, design an algorithm that prevents deadlock. Implement and test your algorithm by designing two threads, one representing an eastwardmoving baboon and the other representing a westward-moving baboon. Once baboons are on the rope, each will sleep for a random period of time to simulate traveling across the rope. Initially, do not be concerned about starvation (the situation in which eastward-moving baboons hold up westward-moving baboons indefinitely, or vice-versa).

b) Modify your algorithm in (a) so that it is starvation-free, implement and test it. You also need to take the efficiency of the algorithm into account.