Tuesday, October 5, 2010

The Dining Philosophers Problem

Last Monday we discussed about a solution for the dining philosophers problem in CS2106 Operating System tutorial. I think it represents some elements of the world, its unfairness and dynamic, so I'd record some of my thoughts down here.
The dining philosophers problem is summarized as five philosophers sitting at a table doing one of two things: eating or thinking. While eating, they are not thinking, and while thinking, they are not eating. The five philosophers sit at a circular table with a large bowl of spaghetti in the center. A fork is placed in between each pair of adjacent philosophers, and as such, each philosopher has one fork to his left and one fork to his right. As spaghetti is difficult to serve and eat with a single fork, it is assumed that a philosopher must eat with two forks. Each philosopher can only use the forks on his immediate left and immediate right.
- from http://en.wikipedia.org/wiki/Dining_philosophers_problem

The problem is that, if the each philosopher hold the fork in his left and wait for the fork in his right, no one can proceed. It's called deadlock

So we discussed a solution that allows them to forcefully take a fork from others' hand. There will be 2 kind of philosophers: Senior Philosopher and Junior Philosopher. The senior ones can take fork from the Junior ones (0 < number of senior philosophers < 5). It solves the problem of deadlock because there won't be circular waiting situation, which is one of the conditions for deadlock to happen. However, it introduces another problem: a junior can easily be starved if the senior next to him keep stealing his fork!

How to solve the problem of unfairness? Dynamic priority! The title is not fixed, a senior philosopher that eats too much (compared to thinking) will be demoted to junior, and vice verse.

Actually it makes sense. A senior philosopher is supposed to be a wise thinker. When he eats too much, he will become dumb and should be demoted to junior, while a philosopher concentrates on thinking should get wiser and becomes a senior. (The whole class laughed when I said these sentence =P)


 Now let's see how different kind of philosophers will react to possible situations:


- The wise (senior) philosopher: he realizes that it's thinking that defines him (I think, therefore I am). If he ceases to think, he cease to be a philosopher. So he shouldn't focus on eating, even though he gets the power to do so.

- The potential (junior) philosopher: though currently the situation doesn't favor him, he knows that doing what it defines him (thinking) will eventually make him a senior, and grant him the privileges he doesn't have. So he would focus on thinking instead of eating. Things might change when he actually becomes a senior: he might be wise, might be greedy, or even become an evil one.


- The greedy (senior) philosopher: he would spend a lot of time on accumulating power and become a senior. However, at that moment he got seduced by the power itself, and try to exploit that power. He would try to eat as much as possible. Eventually it will lead to his downfall.

- The stupid (junior) philosopher: he's constantly in the verge of losing what he has, so he'd try to eat whenever he can. He'd always be desperate like that.

- The pessimistic (junior) philosopher: he's constantly left hungry, so he loses hope about life. Eventually he's starved.


- The evil desperate (senior) philosopher: he's an intelligent one. However, he wants to protect his power so much. He realizes that he can keep it by either eating very little, or feed his juniors one, so that they don't realize the need of thinking and won't become wiser. He would try to balance the two things: eat, but would also not left his junior starved. Life won't be much enjoyable because he always live worrying and planning and scheming.

- The evil ambitious (junior) philosopher: he's smart one. He knows that he can become senior by either focus on thinking, or feed his senior so much that he degrades himself to junior (relatively, he'd become a senior). So he'd restrain from eating, and seduce his senior to eat more. Of course he'd think too, but he'd also try to eat as much as possible. He's dangerous.


That's all I can think of for now. Life's much more complicated than that.

4 comments:

  1. If you don't make further assumptions, you may be more likely to be able to solve the stated problem.

    ReplyDelete
  2. Sorry for the confusion, actually the problem we discussed was how to solve the unfairness problem, given that there are seniors and juniors status.
    Anw, there is a reason why the assumptions were there: it's not only to solve the problem but to teach about priority scheduling (in operating system)

    ReplyDelete
  3. Ok. So my thought for this is that you may try to model each person's level by the same function f of two variable x and y . ( x stands for eating and y for thinking). In common sense, f should increases in y and decrease in x. In case you try modeling the amount of food each philosopher eats, then a function g also of such 2 variables comes out which decreases in y and increases in x.
    Just think about it.

    ReplyDelete
  4. STC Technologies also provides placement services and prepare the students by providing aptitude tests, group discussion, technical and HR training. STC Technologies

    ReplyDelete