Are OS schedulers irrelevant to multithreaded algorithms?

Question

Many algorithm cost models (see Cormen's Third Edition, Ch. 27) argue that schedulers are all the same, and thus basically a constant in some algorithm's order. Is this correct? Will there be no consequence in using a O(1) scheduler vs. a CFS one?

Answer 1

Many algorithm cost models (see Cormen's Third Edition, Ch. 27) argue that schedulers are all the same, and thus basically a constant in some algorithm's order.

The simple answer is yes. The context in which this was said in CLRS was to measure the performance of the multi-threaded algorithms. The most obvious example of such measure is the speed-up achieved by the parallel/multi-threaded algorithm. The job of OS scheduler, especially in a multi-processor environment, is make sure all the processor do the fair share of the total work if at all possible in order to maximise the total performance. It doesn't matter what scheduling algorithm is followed by the OS. Because, if there's a free processor and there's work to be done, the OS scheduler will always assign some work.

Let's take an example. X is the total work to be done(assume it's very big like gene computations so that there's enough scope for parallelism), you have 5 processors. You wrote an algorithm that splits the total work into 5 almost equal chucks. Assume that the chunks are independent and your measured speed-up is 3.5 (It's not 5 due to additional costs for thread creation, context-switch and some communications etc.)

Note that when you measure the speed-up of a parallel algorithm, you are always going to measure it by making sure there's no other tasks are running apart from your parallel tasks. It's not hard to see that speed-up achieved by a parallel algorithm will be nearly same as the OS scheduling algorithms have little or no say here. So irrespective of the OS scheduler, your are always going to get the speed-up that the almost similar to 3.5 in this example.

Will there be no consequence in using a O(1) scheduler vs. a CFS one?

Yes, for measuring the performance of a parallel/multi-threaded algorithm.

The simple parallel algorithm's aim (however difficult it may be to achieve it actually) is split the work optimally to make sure all the processors work towards completing the task. It's reasonable to assume that all your (parallelized task) threads are of same unless you do something to make it otherwise. But the OS scheduler's task is more complicated in general case. Because, there are always going to be many processes running with different priorities at the same and different running times etc. It's in this context OS scheduler algorithms come into play. i.e. How they decide on which task to execute next. And based on different needs and different people's liking we have many OS scheduling algorithms.

It must be noted that performance of a parallel algorithm may vary depending on the OS scheduler when running with many other tasks with different priorities. Let's your task is T which is split into t1, t2, t3, t4 & t5. Assume the other tasks that the scheduler has in its queue are t12, t25, t99, t75, t60 (I used some random ids here). Then the total time running of your task T is dependent on how OS scheduler schedules all these tasks. So if one of your tasks, say t4, is scheduled at last after executing all others (t1, t2, t3, t5, t12, t25, t99, t75 & t60) then you are going to get different running time. And you'll be get different running times depending on when all your tasks are scheduled & completed. In this context, the OS scheduling algorithm does affect the actual run time.