multithreading - Are OS schedulers irrelevant to multithreaded algorithms? -

many algorithm cost models (see cormen's third edition, ch. 27) argue schedulers same, , constant in algorithm's order. correct? there no consequence in using o(1) scheduler vs. cfs one? thanks.

many algorithm cost models (see cormen's third edition, ch. 27) argue schedulers same, , constant in algorithm's order.

the simple answer yes. context in said in clrs measure performance of multi-threaded algorithms. obvious example of such measure speed-up achieved parallel/multi-threaded algorithm. job of os scheduler, in multi-processor environment, make sure processor fair share of total work if @ possible in order maximise total performance. doesn't matter scheduling algorithm followed os. because, if there's free processor , there's work done, os scheduler assign work.

let's take example. x total work done(assume it's big gene computations there's enough scope parallelism), have 5 processors. wrote algorithm splits total work 5 almost equal chucks. assume chunks independent , measured speed-up 3.5 (it's not 5 due additional costs thread creation, context-switch , communications etc.)

note when measure speed-up of parallel algorithm, going measure making sure there's no other tasks running apart parallel tasks. it's not hard see speed-up achieved parallel algorithm same os scheduling algorithms have little or no here. irrespective of os scheduler, going speed-up similar 3.5 in example.

will there no consequence in using o(1) scheduler vs. cfs one?

yes, for measuring performance of parallel/multi-threaded algorithm.

the simple parallel algorithm's aim (however difficult may achieve actually) split work optimally make sure processors work towards completing task. it's reasonable assume (parallelized task) threads of same unless make otherwise. os scheduler's task more complicated in general case. because, there going many processes running different priorities @ same , different running times etc. it's in context os scheduler algorithms come play. i.e. how decide on task execute next. , based on different needs , different people's liking have many os scheduling algorithms.

it must noted performance of parallel algorithm may vary depending on os scheduler when running many other tasks different priorities. let's task t split t1, t2, t3, t4 & t5. assume other tasks scheduler has in queue t12, t25, t99, t75, t60 (i used random ids here). total time running of task t dependent on how os scheduler schedules these tasks. if 1 of tasks, t4, scheduled @ last after executing others (t1, t2, t3, t5, t12, t25, t99, t75 & t60) going different running time. , you'll different running times depending on when tasks scheduled & completed. in context, os scheduling algorithm does affect actual run time.