The most efficient algorithm to scan a bitmap
Yesterday in class, we were learning about the linux scheduler. How you can have several different algorithms for scheduling, etc. All very nice. The actual scheduler used in linux 2.6 has 140 FIFO queues; one for each possible priority. The scheduler takes the first job from the highest priority queue. The queues have a 140 bit bitmap. Because the bitmap gets scanned every single time there is a new quantum, the algorithm for scanning the bitmap needs to be very fast. Our professor asked how we would go about scanning the bitmap. As an example, he put up an algorithm that would compare a single bit, then shift the bits left and keep track of the number of shifts. Obviously room for improvement there. I suggested that the algorithm should be just an integer base 2 log function. To which the professor asked me how I would implement it. I wanted to say: "in hardware", but he was already moving forward. But really, the question of "what is the most significant bit?" ...