欢迎来到天天文库
浏览记录
ID:15401123
大小:3.16 MB
页数:122页
时间:2018-08-03
《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
此文档下载收益归作者所有