.. SPDX-License-Identifier: GPL-2.0 .. include:: ../disclaimer-zh_CN.rst :Original: Documentation/scheduler/sched-design-CFS.rst :翻译: å”艺舟 Tang Yizhou <tangyeechou@gmail.com> =============== 完全公平调度器 =============== 1. 概述 ======= CFS表示“完全公平调度器â€ï¼Œå®ƒæ˜¯ä¸ºæ¡Œé¢æ–°è®¾è®¡çš„进程调度器,由Ingo Molnar实现并åˆå…¥Linux 2.6.23。它替代了之å‰åŽŸå§‹è°ƒåº¦å™¨ä¸SCHED_OTHERç–略的交互å¼ä»£ç 。 CFS 80%的设计å¯ä»¥æ€»ç»“为一å¥è¯ï¼šCFS在真实硬件上建模了一个“ç†æƒ³çš„,精确的多任务CPUâ€ã€‚ “ç†æƒ³çš„多任务CPUâ€æ˜¯ä¸€ç§ï¼ˆä¸å˜åœ¨çš„ :-))具有100%物ç†ç®—力的CPU,它能让æ¯ä¸ªä»»åŠ¡ç²¾ç¡®åœ°ä»¥ 相åŒçš„速度并行è¿è¡Œï¼Œé€Ÿåº¦å‡ä¸º1/nr_running。举例æ¥è¯´ï¼Œå¦‚果有两个任务æ£åœ¨è¿è¡Œï¼Œé‚£ä¹ˆæ¯ä¸ª 任务获得50%物ç†ç®—力。 --- 也就是说,真æ£çš„并行。 在真实的硬件上,一次åªèƒ½è¿è¡Œä¸€ä¸ªä»»åŠ¡ï¼Œæ‰€ä»¥æˆ‘们需è¦ä»‹ç»â€œè™šæ‹Ÿè¿è¡Œæ—¶é—´â€çš„概念。任务的虚拟 è¿è¡Œæ—¶é—´è¡¨æ˜Žï¼Œå®ƒçš„下一个时间片将在上文æè¿°çš„ç†æƒ³å¤šä»»åŠ¡CPU上开始执行。在实践ä¸ï¼Œä»»åŠ¡çš„ 虚拟è¿è¡Œæ—¶é—´ç”±å®ƒçš„真实è¿è¡Œæ—¶é—´ç›¸è¾ƒæ£åœ¨è¿è¡Œçš„任务总数归一化计算得到。 2. 一些实现细节 =============== 在CFSä¸ï¼Œè™šæ‹Ÿè¿è¡Œæ—¶é—´ç”±æ¯ä¸ªä»»åŠ¡çš„p->se.vruntime(å•ä½ä¸ºçº³ç§’ï¼‰çš„å€¼è¡¨è¾¾å’Œè·Ÿè¸ªã€‚å› æ¤ï¼Œ 精确地计时和测é‡ä¸€ä¸ªä»»åŠ¡åº”得的“预期的CPU时间â€æ˜¯å¯èƒ½çš„。 一些细节:在“ç†æƒ³çš„â€ç¡¬ä»¶ä¸Šï¼Œæ‰€æœ‰çš„ä»»åŠ¡åœ¨ä»»ä½•æ—¶åˆ»éƒ½åº”è¯¥å…·æœ‰ä¸€æ ·çš„p->se.vruntime值, --- 也就是说,任务应当åŒæ—¶æ‰§è¡Œï¼Œæ²¡æœ‰ä»»åŠ¡ä¼šåœ¨â€œç†æƒ³çš„â€CPU分时ä¸å˜å¾—“ä¸å¹³è¡¡â€ã€‚ CFS的任务选择逻辑基于p->se.vruntimeçš„å€¼ï¼Œå› æ¤éžå¸¸ç®€å•ï¼šæ€»æ˜¯è¯•å›¾é€‰æ‹©p->se.vruntime值 最å°çš„任务è¿è¡Œï¼ˆä¹Ÿå°±æ˜¯è¯´ï¼Œè‡³ä»Šæ‰§è¡Œæ—¶é—´æœ€å°‘的任务)。CFS总是尽å¯èƒ½å°è¯•æŒ‰â€œç†æƒ³å¤šä»»åŠ¡ç¡¬ä»¶â€ é‚£æ ·å°†CPU时间在å¯è¿è¡Œä»»åŠ¡ä¸å‡åˆ†ã€‚ CFS剩下的其它设计,一般脱离了这个简å•çš„æ¦‚å¿µï¼Œé™„åŠ çš„è®¾è®¡åŒ…æ‹¬nice级别,多处ç†ï¼Œä»¥åŠå„ç§ ç”¨æ¥è¯†åˆ«å·²ç¡çœ 任务的算法å˜ä½“。 3. çº¢é»‘æ ‘ ========= CFS的设计éžå¸¸æ¿€è¿›ï¼šå®ƒä¸ä½¿ç”¨è¿è¡Œé˜Ÿåˆ—的旧数æ®ç»“构,而是使用按时间排åºçš„çº¢é»‘æ ‘ï¼Œæž„å»ºå‡º 任务未æ¥æ‰§è¡Œçš„“时间线â€ã€‚å› æ¤æ²¡æœ‰ä»»ä½•â€œæ•°ç»„切æ¢â€çš„旧包袱(之å‰çš„原始调度器和RSDL/SD都 被它影å“)。 CFSåŒæ ·ç»´æŠ¤äº†rq->cfs.min_vruntime值,它是å•è°ƒé€’增的,跟踪è¿è¡Œé˜Ÿåˆ—ä¸çš„æ‰€æœ‰ä»»åŠ¡çš„æœ€å° è™šæ‹Ÿè¿è¡Œæ—¶é—´å€¼ã€‚系统åšçš„全部工作是:使用min_vruntime跟踪,然åŽç”¨å®ƒçš„值将新激活的调度 实体尽å¯èƒ½åœ°æ”¾åœ¨çº¢é»‘æ ‘çš„å·¦ä¾§ã€‚ è¿è¡Œé˜Ÿåˆ—ä¸æ£åœ¨è¿è¡Œçš„任务的总数由rq->cfs.load计数,它是è¿è¡Œé˜Ÿåˆ—ä¸çš„任务的æƒå€¼ä¹‹å’Œã€‚ CFS维护了一个按时间排åºçš„çº¢é»‘æ ‘ï¼Œæ‰€æœ‰å¯è¿è¡Œä»»åŠ¡ä»¥p->se.vruntime为键值排åºã€‚CFS从这颗 æ ‘ä¸Šé€‰æ‹©â€œæœ€å·¦ä¾§â€çš„任务并è¿è¡Œã€‚系统继ç»è¿è¡Œï¼Œè¢«æ‰§è¡Œè¿‡çš„任务越æ¥è¶Šè¢«æ”¾åˆ°æ ‘çš„å³ä¾§ --- 缓慢, 但很明确æ¯ä¸ªä»»åŠ¡éƒ½æœ‰æˆä¸ºâ€œæœ€å·¦ä¾§ä»»åŠ¡â€çš„æœºä¼šï¼Œå› æ¤ä»»åŠ¡å°†ç¡®å®šæ€§åœ°èŽ·å¾—一定é‡CPU时间。 总结一下,CFS工作方å¼åƒè¿™æ ·ï¼šå®ƒè¿è¡Œä¸€ä¸ªä»»åŠ¡ä¸€ä¼šå„¿ï¼Œå½“任务å‘ç”Ÿè°ƒåº¦ï¼ˆæˆ–è€…è°ƒåº¦å™¨æ—¶é’Ÿæ»´ç” tick产生),就会考虑任务的CPU使用率:任务刚刚花在物ç†CPU上的(少é‡ï¼‰æ—¶é—´è¢«åŠ 到 p->se.vruntime。一旦p->se.vruntimeå˜å¾—足够大,其它的任务将æˆä¸ºæŒ‰æ—¶é—´æŽ’åºçš„çº¢é»‘æ ‘çš„ “最左侧任务â€ï¼ˆç›¸è¾ƒæœ€å·¦ä¾§çš„任务,还è¦åŠ 上一个很å°çš„“粒度â€é‡ï¼Œä½¿å¾—我们ä¸ä¼šå¯¹ä»»åŠ¡è¿‡åº¦è°ƒåº¦ï¼Œ 导致缓å˜é¢ 簸),然åŽæ–°çš„最左侧任务将被选ä¸ï¼Œå½“å‰ä»»åŠ¡è¢«æŠ¢å 。 4. CFSçš„ä¸€äº›ç‰¹å¾ ================ CFS使用纳秒粒度的计时,ä¸ä¾èµ–于任何jiffies或HZçš„ç»†èŠ‚ã€‚å› æ¤CFS并ä¸åƒä¹‹å‰çš„è°ƒåº¦å™¨é‚£æ · 有“时间片â€çš„概念,也没有任何å¯å‘å¼çš„设计。唯一å¯è°ƒçš„å‚æ•°ï¼ˆä½ éœ€è¦æ‰“å¼€CONFIG_SCHED_DEBUG)是: /proc/sys/kernel/sched_min_granularity_ns 它å¯ä»¥ç”¨æ¥å°†è°ƒåº¦å™¨ä»Žâ€œæ¡Œé¢â€æ¨¡å¼ï¼ˆä¹Ÿå°±æ˜¯ä½Žæ—¶å»¶ï¼‰è°ƒèŠ‚为“æœåŠ¡å™¨â€ï¼ˆä¹Ÿå°±æ˜¯é«˜æ‰¹å¤„ç†ï¼‰æ¨¡å¼ã€‚ 它的默认设置是适åˆæ¡Œé¢çš„工作负载。SCHED_BATCH也被CFS调度器模å—处ç†ã€‚ CFS的设计ä¸æ˜“å—到当å‰å˜åœ¨çš„任何针对stock调度器的“攻击â€çš„å½±å“,包括fiftyp.c,thud.c, chew.c,ring-test.c,massive_intr.c,它们都能很好地è¿è¡Œï¼Œä¸ä¼šå½±å“交互性,将产生 符åˆé¢„期的行为。 CFS调度器处ç†nice级别和SCHED_BATCH的能力比之å‰çš„原始调度器更强:两ç§ç±»åž‹çš„工作负载 都被更激进地隔离了。 SMPè´Ÿè½½å‡è¡¡è¢«é‡åš/清ç†è¿‡ï¼šé历è¿è¡Œé˜Ÿåˆ—çš„å‡è®¾å·²ç»ä»Žè´Ÿè½½å‡è¡¡çš„代ç ä¸ç§»é™¤ï¼Œä½¿ç”¨è°ƒåº¦æ¨¡å— çš„è¿ä»£å™¨ã€‚结果是,负载å‡è¡¡ä»£ç å˜å¾—简å•ä¸å°‘。 5. 调度ç–ç•¥ =========== CFS实现了三ç§è°ƒåº¦ç–略: - SCHED_NORMALï¼šï¼ˆä¼ ç»Ÿè¢«ç§°ä¸ºSCHED_OTHER):该调度ç–略用于普通任务。 - SCHED_BATCH:抢å ä¸åƒæ™®é€šä»»åŠ¡é‚£æ ·é¢‘ç¹ï¼Œå› æ¤å…许任务è¿è¡Œæ›´é•¿æ—¶é—´ï¼Œæ›´å¥½åœ°åˆ©ç”¨ç¼“å˜ï¼Œ ä¸è¿‡è¦ä»¥äº¤äº’性为代价。它很适åˆæ‰¹å¤„ç†å·¥ä½œã€‚ - SCHED_IDLE:它比nice 19更弱,ä¸è¿‡å®ƒä¸æ˜¯çœŸæ£çš„idleå®šæ—¶å™¨è°ƒåº¦å™¨ï¼Œå› ä¸ºè¦é¿å…给机器 带æ¥æ»é”的优先级å转问题。 SCHED_FIFO/_RR被实现在sched/rt.cä¸ï¼Œå®ƒä»¬ç”±POSIX具体说明。 util-linux-ng 2.13.1.1ä¸çš„chrt命令å¯ä»¥è®¾ç½®ä»¥ä¸Šæ‰€æœ‰ç–略,除了SCHED_IDLE。 6. 调度类 ========= æ–°çš„CFS调度器被设计æˆæ”¯æŒâ€œè°ƒåº¦ç±»â€ï¼Œä¸€ç§è°ƒåº¦æ¨¡å—çš„å¯æ‰©å±•å±‚次结构。这些模å—å°è£…了调度ç–ç•¥ ç»†èŠ‚ï¼Œç”±è°ƒåº¦å™¨æ ¸å¿ƒä»£ç 处ç†ï¼Œä¸”æ— éœ€å¯¹å®ƒä»¬åšå¤ªå¤šå‡è®¾ã€‚ sched/fair.c 实现了上文æè¿°çš„CFS调度器。 sched/rt.c 实现了SCHED_FIFOå’ŒSCHED_RRè¯ä¹‰ï¼Œä¸”比之å‰çš„原始调度器更简æ´ã€‚它使用了100个 è¿è¡Œé˜Ÿåˆ—(总共100个实时优先级,替代了之å‰è°ƒåº¦å™¨çš„140个),且ä¸éœ€è¦è¿‡æœŸæ•°ç»„(expired array)。 调度类由sched_class结构体实现,它包括一些函数钩å,当感兴趣的事件å‘生时,钩å被调用。 这是(部分)钩å的列表: - enqueue_task(...) 当任务进入å¯è¿è¡ŒçŠ¶æ€æ—¶ï¼Œè¢«è°ƒç”¨ã€‚å®ƒå°†è°ƒåº¦å®žä½“ï¼ˆä»»åŠ¡ï¼‰æ”¾åˆ°çº¢é»‘æ ‘ä¸ï¼Œå¢žåŠ nr_runningå˜é‡ 的值。 - dequeue_task(...) 当任务ä¸å†å¯è¿è¡Œæ—¶ï¼Œè¿™ä¸ªå‡½æ•°è¢«è°ƒç”¨ï¼Œå¯¹åº”çš„è°ƒåº¦å®žä½“è¢«ç§»å‡ºçº¢é»‘æ ‘ã€‚å®ƒå‡å°‘nr_runningå˜é‡ 的值。 - yield_task(...) 这个函数的行为基本上是出队,紧接ç€å…¥é˜Ÿï¼Œé™¤éžcompat_yield sysctl被开å¯ã€‚在那ç§æƒ…况下, å®ƒå°†è°ƒåº¦å®žä½“æ”¾åœ¨çº¢é»‘æ ‘çš„æœ€å³ç«¯ã€‚ - check_preempt_curr(...) 这个函数检查进入å¯è¿è¡ŒçŠ¶æ€çš„任务能å¦æŠ¢å 当å‰æ£åœ¨è¿è¡Œçš„任务。 - pick_next_task(...) 这个函数选择接下æ¥æœ€é€‚åˆè¿è¡Œçš„任务。 - set_curr_task(...) 这个函数在任务改å˜è°ƒåº¦ç±»æˆ–改å˜ä»»åŠ¡ç»„时被调用。 - task_tick(...) 这个函数最常被时间滴ç”函数调用,它å¯èƒ½å¯¼è‡´è¿›ç¨‹åˆ‡æ¢ã€‚这驱动了è¿è¡Œæ—¶æŠ¢å 。 7. CFS的组调度扩展 ================== 通常,调度器æ“作粒度为任务,努力为æ¯ä¸ªä»»åŠ¡æ供公平的CPU时间。有时å¯èƒ½å¸Œæœ›å°†ä»»åŠ¡ç¼–组, 并为æ¯ä¸ªç»„æ供公平的CPU时间。举例æ¥è¯´ï¼Œå¯èƒ½é¦–先希望为系统ä¸çš„æ¯ä¸ªç”¨æˆ·æ供公平的CPU 时间,接下æ¥æ‰æ˜¯æŸä¸ªç”¨æˆ·çš„æ¯ä¸ªä»»åŠ¡ã€‚ CONFIG_CGROUP_SCHED 力求实现它。它将任务编组,并为这些组公平地分é…CPU时间。 CONFIG_RT_GROUP_SCHED å…许将实时(也就是说,SCHED_FIFOå’ŒSCHED_RR)任务编组。 CONFIG_FAIR_GROUP_SCHED å…许将CFS(也就是说,SCHED_NORMALå’ŒSCHED_BATCH)任务编组。 这些编译选项è¦æ±‚CONFIG_CGROUPS被定义,然åŽç®¡ç†å‘˜èƒ½ä½¿ç”¨cgroup伪文件系统任æ„创建任务组。 关于该文件系统的更多信æ¯ï¼Œå‚è§Documentation/admin-guide/cgroup-v1/cgroups.rst 当CONFIG_FAIR_GROUP_SCHED被定义åŽï¼Œé€šè¿‡ä¼ªæ–‡ä»¶ç³»ç»Ÿï¼Œæ¯ä¸ªç»„被创建一个“cpu.sharesâ€æ–‡ä»¶ã€‚ å‚è§ä¸‹é¢çš„例åæ¥åˆ›å»ºä»»åŠ¡ç»„,并通过“cgroupâ€ä¼ªæ–‡ä»¶ç³»ç»Ÿä¿®æ”¹å®ƒä»¬çš„CPU份é¢:: # mount -t tmpfs cgroup_root /sys/fs/cgroup # mkdir /sys/fs/cgroup/cpu # mount -t cgroup -ocpu none /sys/fs/cgroup/cpu # cd /sys/fs/cgroup/cpu # mkdir multimedia # 创建 "multimedia" 任务组 # mkdir browser # 创建 "browser" 任务组 # #é…ç½®multimedia组,令其获得browser组两å€CPU带宽 # echo 2048 > multimedia/cpu.shares # echo 1024 > browser/cpu.shares # firefox & # å¯åŠ¨firefox并把它移到 "browser" 组 # echo <firefox_pid> > browser/tasks # #å¯åŠ¨gmplayerï¼ˆæˆ–è€…ä½ æœ€å–œæ¬¢çš„ç”µå½±æ’放器) # echo <movie_player_pid> > multimedia/tasks