So I have another post for today. I promised that I would make up for my lack of a Saturday post and I plan to deliver. Like the postman! And it’s not even about Ponies!
Last Monday one of my lectures covered a brain teaser and it came up again in a different subject’s lecture today. It is Edsger Dijkstra’s Dining Philosophers Problem.
It goes like this. There are 5 Philosophers sitting at a round dining table. There is a bowl of rice in the middle which anyone can eat from (philosophers don’t care much for flavour) but only if they have two chopsticks. The problem is that there are only five chopsticks which are placed between each philosopher. Each philosopher can only pick up the chopsticks to their left and right. Apparently Philosophers can only eat or think. Talking is not an option for them. So you need to find a system to let everyone eat from the bowl of rice. It is also assumed that there is an infinite amount of rice in the bowl.
Most peoples reflex action would presume the answer is for each philosopher to pick up a chopstick and wait until the other one is available. This will quickly end in a deadlock where everyone would be holding onto a chopstick and refusing to put it down because no other chopsticks are available.
Last week I came up with a solution that wasn’t elegant but it was a solution none the less. All the philosophers need a process that they must follow.
1. Pick up the right chopstick if it is available (currently in deadlock on the first iteration).
2. Hold onto the chopstick and pick up the left chopstick if it is available within 5 seconds (still in deadlock on the first iteration).
3. If after 5 seconds the left chopstick is not available then put the right chopstick down. Pick a number between 1 and 5 and wait that many seconds (this is the point where the deadlock can be broken). Wait another 5 seconds and proceed back to step 1.
4. If you did pick up the left chopstick then eat from the bowl for 30 seconds. Put both chopsticks down, wait for 15 seconds then proceed back to step one.
I know it has floors. For example, if during step 3 everyone always picks the same number (1 because they are hungry) then there will always be a deadlock. This may not result in each philosopher having an equal share of the rice but everyone does have the chance to eat.
Afterward we were shown Dijkstra’s original solution to the problem. I won’t put it up here but it is on Wikipedia. However I’d love to see if you have a more elegant solution to the one I came up with. Ultimately you want to come up with a queue so that all philosophers have equal share. So get thinking and post your answer. I will be judging you!
But don’t worry too much because the solution provided by the lecturer I had today was horrible. Either that or we was just really bad at explaining it. First you number the philosophers from 0 to 4 (programmers always start at 0). You then let the odd numbered philosophers pick up the chopsticks and eat (so far so good) then after they have finished you let the even other philosophers eat. It’s that easy! Except it’s wrong! That doesn’t work because you have three philosophers (requiring 6 chopsticks) trying to eat with 5 chopsticks! But there is definitely a way to improve that which I’ll let you work out if you wish.
So Until Tomorrow,
Have Fun and Stay Sexy!
I'd probably advocate a system where the philosophers all trust one of the team to feed everyone in turn, given that most of their time is spent chewing/swallowing and talking too much, this would probably be a pretty efficient system. I'd personally trust Diogenes to do the food handling, as he'd have trouble finding people's faces and that would be hilarious. The system could of course be improved by having two servers on some kind of roster system, say three times round the table then pass on the chopsticks, but keeping it simple might be the best bet.
ReplyDelete