Friday, December 22, 2006

The toilet

1- Say, there is a common toilet with many doors.
2- A person can enter from only one of these doors at any time i.e. the door to enter is fixed for him.
3- A door can be used for entry into the toilet by many persons i.e. it is a common entrance for some persons.
4- Only one person can use the toilet at a time.
5- There is a toilet supervisor whose job is to see that persons behave properly.
6- The supervisor gives each of the persons who use that toilet a number so he can recognize them when they come to use the toilet.
7-The higher the number the higher the chance of the person getting to use the toilet.
8- If a person is using the toilet and another person comes up whose number is bigger, the supervisor kicks the first person out and lets the second person to use the toilet. The kicked one get to use the toilet once the bigger number person is finished. The same fate awaits the second person if another person with even bigger number comes. In this case however, the first kicked person has to wait even longer. If the small number person is one unlucky guy he will find all persons coming with numbers bigger than his and he never gets to use the toilet or may have to wait for too long.
9- Seeing the plight of persons with small numbers the supervisor decides to help them out. He now puts a lock on each door. A person with small number now has option to lock as many doors from inside as he wants.
10- A door is open unless someone is using the toilet and has locked it from inside.
11- Any person can enter if his door is not locked and no higher number person is using the toilet. If a smaller number person is using the toilet when higher number comes and the door is not locked, the supervisor kicks the smaller person out and the higher number person uses it. The smaller person can reenter once the higher number person is done.
Now the supervisor is happy. The person who got small numbers can happily use the toilet if they lock the doors. But the person using the toilet often don't lock all the doors, so they still get kicked out by higher number person whose door they didn't lock.
This also cause another problem. Now sometimes the higher number person can't use the toilet because his door is locked by smaller number person who got kicked up by another person with a number somewhat in the middle of the other two. The highest number person should be using the toilet but the door is locked so he can't. Instead the middle person is using it. The supervisor didn't like it but he can't do anything with present rules so he does something else to help out the highest number person in such cases.
12- Now when a smaller number person goes in the toilet and locks a door, and a higher number person comes to that door, the supervisor exchanges the numbers of the two persons for the time while the small number person is using the toilet.
13- Once the person using the toilet is done, the two get their numbers back. The smaller person opens the door and comes out. And the higher number person enters the toilet.
14- If a person with a number somewhere in the middle comes before the (original) small number person finishes, he sees that a bigger number person is using the toilet since smaller and higher guys have exchanged their numbers. After the guys is done, the real higher number guy gets his number back and enters the toilet. So the middle guy has to wait for both the other two persons and gets a chance to use the toilet after them.

Now substitute the toilet with processor, supervisor with scheduler, persons with processes, and numbers with priorities. 1- to 8- describe the priority based scheduling with preemption. 8- is known as process starving. 9, 10, and 11- constitute what is known as priority inversion.
12, 13, and 14- are examples of priority inheritance.

The analogy isn't perfect though, and there might be some loopholes.

No comments: