the past and the future of linux scheduler

《the past and the future of linux scheduler》由会员上传分享，免费在线阅读，更多相关内容在学术论文-天天文库。

1、ThepastandthefutureofLinuxSchedulerO(1),CFS,BFS,RealtimeandSMPBarrySong宋宝华Background宋宝华Real-TimeResponsevs.Throughput!EfficiencyandResponsivenessareInverselyRelated–OverheadforReal-TimePreemption•MutexOperationsmorecomplex

2、thanspinlockoperations•PriorityInheritanceonMutexincreasestaskswitching•PriorityInheritanceincreasesworst-caseexecutiontime•Interruptoverhead–AdditionalTaskSwitching–InterruptPreemption"InterruptthroughputreductionThroughputHighresponsivenessGeneralProcessClassifications!Twosche

3、mesforclassifying:–Traditionalclasses•IObound•CPUbound–Alternativeclasses•Interactive•Batch•Real-time–Video,robotics,sensor-based–Batch–Realtime!Hardrealtime-!determinism!LinuxSchedulerHistoryO(1)Background!Briefly–theschedulermaintainedtworunqueuesforeachCPU,withaprioritylinked

4、listforeachprioritylevel(140total).!Tasksareenqueuedintothecorrespondingprioritylist.!Thescheduleronlyneedstolookatthehighestprioritylisttoschedulethenexttask.!Assignstimeslicesforeachtask.!Hadtotracksleeptimes,processinteractivity,etc.Non-RTschedulinginO(1)!Everyprocesshasa“sta

5、tic”priority–100(highest)–139(lowest)–Variablevianice()andsetpriority()!Basequantum(notaconstant!)–Ifsp<120•20*(140-staticpriority)–Ifsp>=120•5*(140-staticpriority)!Dynamicpriority(also100-139)–Max(100,min(sp-bonus+5,139))–0<=bonus<=10宋宝华Dynamicpriorityfornon-

6、RTinO(1)!Bonus–0-5isapenalty–6-10isaprize–Relatedtoaveragesleeptime•OFTHISPROCESS(notofallProcesses)•Basedonpasthistory•Somesamplevalues:AveragesleeptimeBonus0<=N<100ms0300<=N<400ms3600<=N<7006900<=N<10009宋宝华Priority'Array'and'Bitmaps'in'O(1)'!Whenaprioritylev

7、elhasaTASK_RUNNINGprocess,thatbitinthebitmapissetto1."!Thefirstbitpositiontobe1isthequeueinthelistofqueuesonwhichtheavailableprocessisstored."10TwoSetsofRunnableProcessesintherunqueueStructure!TworunqueuesperCPU:oneactive,oneexpired.Ifaprocesshasn'tuseditsentiretimeslice,it'sonth

8、eactivequeue;ifithas,it'sexpired.Tasksareswappe