Bug Vanquisher

28 August 2007

Of Paging and Buses

Filed under: Computer Theory, Fun — Tanveer Badar @ 6:20 PM

This bus has nothing to do with this bus or this. I was referring to this bus instead. So, you got up in the morning and walked to bus stop and hitched a ride to office/school/college in that public bus.

Given the messy time it is in morning, everyone very busy with themselves on the roads, people bustling here and there, buses full to bursting point, it is hard to find a seat in the bus. What means do you employ to gain hold of a seat? Pushing, feigning a sick health ( :-) ), asking someone to sit up and give you their seat, bullying as the last resort? Whatever means you use, you will surely benefit if you had read a little about how operating systems do paging.

Different algorithms used to paging have a variety of characteristics and performance guarantees associated with them. They can also help you make your decision about where to sit, what to do to grab a seat and certainly, what to avoid.

  • Perhaps the best is the one which replaces the page which won’t be needed for the longest. Analogous to this, you should seek the passenger who will leave their seat the earliest,  use whatever means to gain hold. This strategy suffers the same problem as that algorithm mentioned, you cannot know beforehand who is going to leave when, unless you employ heuristics. For example, you may consider standing near school/college students when their institute is nearing, they will leave in a hurry.

  • Then, the worst choice is FIFO. You cannot expect people to play fair and offer you a seat if they can do otherwise.

  • Try going for the least recent arrival, corresponding page replacement algorithm is LRU. The person who is sitting the longest is likely to get off in near future as compared to others.

  • Given your specific route, most people will tend to get on and off quite quickly or they may stick with you for a long time. Choose wisely. The person who get into the vehicle recently is likely to leave after a short time.

  • Pick a random seat and stand near them. Here again, you can use some heuristics. People usually start to look on the road pretty closely when they are about to get off the bus. You may want to choose such a passenger.

  • Consider assigning a certain likelihood to the nearby passengers. If they are busy reading, their stop is far from your comfort. If someone is talking non-stop, their stop is no where near their recognition of surroundings!

  • Don’t go anywhere near old people and those visibly sick. They will have higher precedence than you when a seat needs to be filled. You will waste your time and chance which would be better utilized some place else.

  • [Update: 18/09/2007] Large groups of people tend to get off the bus near community places like shopping malls, something religious, hospitals [ :) ], schools, colleges etc. Spot such a group if some community place is on your path.

  • [Update: 07/11/2007] People do not actively seek vacant seats but instead tend to stay at one place. This call for spatial locality.

  • [Update: 07/11/2007] If you regularly take a route, you can remember people’s faces and easily predict who gets off when. Hence, the temporal locality.

Leave a Comment »

No comments yet.

RSS feed for comments on this post. TrackBack URI

Leave a Reply

Please log in using one of these methods to post your comment:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out /  Change )

Twitter picture

You are commenting using your Twitter account. Log Out /  Change )

Facebook photo

You are commenting using your Facebook account. Log Out /  Change )

Connecting to %s

Create a free website or blog at WordPress.com.

%d bloggers like this: