搜索

[26481] 2021-07-22_肝翻Linux进程调度所有知识点

文档创建者：s7ckTeam
浏览次数：1
最后更新：2025-01-19
2021-07-22_肝翻Linux进程调度所有知识点 肝 翻   L i n u x   进 程 调 度 所 有 知 识 点 L i n u x 学 习   2 0 2 1 - 0 7 - 2 2 以 下 文 章 来 源 于 人 人 都 是 极 客   ， 作 者 布 道 师 P e t e r 来 自 公 众 号 ： 来 自 公 众 号 ： 人 人 都 是 极 客 人 人 都 是 极 客 前 面 我 们 重 点 分 析 了 如 何 通 过   f o r k ,   v f o r k ,   p t h r e a d _ c r e a t e   去 创 建 一 个 进 程 或 者 线 程 ， 以 及 后 面 说 了 它 们 共 同 调 用   d o _ f o r k   的 实 现 。 现 在 已 经 知 道 一 个 进 程 是 如 何 创 建 的 ， 但 是 进 程 何 时 被 执 行 ， 需 要 调 度 器 来 选 择 。 所 以 这 一 节 我 们 介 绍 下 进 程 调 度 和 进 程 切 换 的 详 情 。 进 程 的 分 类 进 程 的 分 类 在   C P U   的 角 度 看 进 程 行 为 的 话 ， 可 以 分 为 两 类 ： C P U   消 耗 型 ： 此 类 进 程 就 是 一 直 占 用   C P U   计 算 ， C P U   利 用 率 很 高 I O   消 耗 型 ： 此 类 进 程 会 涉 及 到   I O ， 需 要 和 用 户 交 互 ， 比 如 键 盘 输 入 ， 占 用   C P U 不 是 很 高 ， 只 需 要   C P U   的 一 部 分 计 算 ， 大 多 数 时 间 是 在 等 待   I O C P U   消 耗 型 进 程 需 要 高 的 吞 吐 率 ， I O   消 耗 型 进 程 需 要 强 的 响 应 性 ， 这 两 点 都 是 调 度 器 需 要 考 虑 的 。 为 了 更 快 响 应   I O   消 耗 型 进 程 ， 内 核 提 供 了 一 个 抢 占 ( p r e e m p t ) 机 制 ， 使 优 先 级 更 高 的 进 程 ， 去 抢 占 优 先 级 低 的 进 程 运 行 。 内 核 用 以 下 宏 来 选 择 内 核 是 否 打 开 抢 占 机 制 ： C O N F I G _ P R E E M P T _ N O N E :   不 打 开 抢 占 ， 主 要 是 面 向 服 务 器 。 此 配 置 下 ， C P U 在 计 算 时 ， 当 输 入 键 盘 之 后 ， 因 为 没 有 抢 占 ， 可 能 需 要 一 段 时 间 等 待 键 盘 输 入 的 进 程 才 会 被   C P U   调 度 。 C O N F I G _ P R E E M P T   :   打 开 抢 占 ， 一 般 多 用 于 手 机 设 备 。 此 配 置 下 ， 虽 然 会 影 响 吞 吐 率 ， 但 可 以 及 时 响 应 用 户 的 输 入 操 作 。 调 度 相 关 的 数 据 结 构 调 度 相 关 的 数 据 结 构 先 来 看 几 个 相 关 的 数 据 结 构 ： t a s k _ s t r u c t 我 们 先 把   t a s k _ s t r u c t   中 和 调 度 相 关 的 结 构 拎 出 来 ： 人 人 都 是 极 客 人 人 都 是 极 客   . 号 主 P e t e r   L i u ， N X P 资 深 系 统 工 程 师 ， 谷 歌 优 秀 讲 师 ， C S D N 博 客 专 家 。 主 要 分 享 A R M ， L i n u x ， A n d r o i d 等 技 术 和 职 业 发 展 与 项 目 管 理 。
s t r u c t   s c h e d _ c l a s s ： 对 调 度 器 进 行 抽 象 ， 一 共 分 为 5 类 。 1 .   S t o p 调 度 器 ： 优 先 级 最 高 的 调 度 类 ， 可 以 抢 占 其 他 所 有 进 程 ， 不 能 被 其 他 进 程 抢 占 ； 2 .   D e a d l i n e 调 度 器 ： 使 用 红 黑 树 ， 把 进 程 按 照 绝 对 截 止 期 限 进 行 排 序 ， 选 择 最 小 进 程 进 行 调 度 运 行 ； 3 .   R T 调 度 器 ： 为 每 个 优 先 级 维 护 一 个 队 列 ； 4 .   C F S 调 度 器 ： 采 用 完 全 公 平 调 度 算 法 ， 引 入 虚 拟 运 行 时 间 概 念 ； 5 .   I D L E - T a s k 调 度 器 ： 每 个 C P U 都 会 有 一 个 i d l e 线 程 ， 当 没 有 其 他 进 程 可 以 调 度 时 ， 调 度 运 行 i d l e 线 程 ； u n s i g n e d   i n t   p o l i c y ： 进 程 的 调 度 策 略 有 6 种 ， 用 户 可 以 调 用 调 度 器 里 的 不 同 调 度 策 略 。 1 .   S C H E D _ D E A D L I N E ： 使 t a s k 选 择 D e a d l i n e 调 度 器 来 调 度 运 行 2 .   S C H E D _ R R ： 时 间 片 轮 转 ， 进 程 用 完 时 间 片 后 加 入 优 先 级 对 应 运 行 队 列 的 尾 部 ， 把 C P U 让 给 同 优 先 级 的 其 他 进 程 ； 3 .   S C H E D _ F I F O ： 先 进 先 出 调 度 没 有 时 间 片 ， 没 有 更 高 优 先 级 的 情 况 下 ， 只 能 等 待 主 动 让 出 C P U ； 4 .   S C H E D _ N O R M A L ： 使 t a s k 选 择 C F S 调 度 器 来 调 度 运 行 ； 5 .   S C H E D _ B A T C H ： 批 量 处 理 ， 使 t a s k 选 择 C F S 调 度 器 来 调 度 运 行 ； 6 .   S C H E D _ I D L E ： 使 t a s k 以 最 低 优 先 级 选 择 C F S 调 度 器 来 调 度 运 行 ； s t r u c t   t a s k _ s t r u c t   {   . . . . . .   c o n s t   s t r u c t   s c h e d _ c l a s s   * s c h e d _ c l a s s ;   s t r u c t   s c h e d _ e n t i t y     s e ;   s t r u c t   s c h e d _ r t _ e n t i t y     r t ;   . . . . . .   s t r u c t   s c h e d _ d l _ e n t i t y     d l ;   . . . . . .   u n s i g n e d   i n t       p o l i c y ;   . . . . . . }
s t r u c t   s c h e d _ e n t i t y   s e ： 采 用 C F S 算 法 调 度 的 普 通 非 实 时 进 程 的 调 度 实 体 。 s t r u c t   s c h e d _ r t _ e n t i t y   r t ： 采 用 R o o u n d - R o b i n 或 者 F I F O 算 法 调 度 的 实 时 调 度 实 体 。 s t r u c t   s c h e d _ d l _ e n t i t y   d l ： 采 用 E D F 算 法 调 度 的 实 时 调 度 实 体 。 分 配 给   C P U   的   t a s k ， 作 为 调 度 实 体 加 入 到 运 行 队 列 中 。 r u n q u e u e   运 行 队 列 运 行 队 列 r u n q u e u e   运 行 队 列 是 本   C P U   上 所 有 可 运 行 进 程 的 队 列 集 合 。 每 个   C P U   都 有 一 个 运 行 队 列 ， 每 个 运 行 队 列 中 有 三 个 调 度 队 列 ， t a s k   作 为 调 度 实 体 加 入 到 各 自 的 调 度 队 列 中 。 三 个 调 度 队 列 ： s t r u c t   r q   {   . . . . . .   s t r u c t   c f s _ r q   c f s ;   s t r u c t   r t _ r q   r t ;   s t r u c t   d l _ r q   d l ;   . . . . . . }
s t r u c t   c f s _ r q   c f s ： C F S 调 度 队 列 s t r u c t   r t _ r q   r t ： R T 调 度 队 列 s t r u c t   d l _ r q   d l ： D L 调 度 队 列 c f s _ r q ： 跟 踪 就 绪 队 列 信 息 以 及 管 理 就 绪 态 调 度 实 体 ， 并 维 护 一 棵 按 照 虚 拟 时 间 排 序 的 红 黑 树 。 t a s k s _ t i m e l i n e - > r b _ r o o t 是 红 黑 树 的 根 ， t a s k s _ t i m e l i n e - > r b _ l e f t m o s t 指 向 红 黑 树 中 最 左 边 的 调 度 实 体 ， 即 虚 拟 时 间 最 小 的 调 度 实 体 。 s c h e d _ e n t i t y ： 可 被 内 核 调 度 的 实 体 。 每 个 就 绪 态 的 调 度 实 体 s c h e d _ e n t i t y 包 含 插 入 红 黑 树 中 使 用 的 节 点 r b _ n o d e ， 同 时 v r u n t i m e 成 员 记 录 已 经 运 行 的 虚 拟 时 间 。 这 些 数 据 结 构 的 关 系 如 下 图 所 示 ： s t r u c t   c f s _ r q   {     . . .     s t r u c t   r b _ r o o t _ c a c h e d   t a s k s _ t i m e l i n e     . . . } ; s t r u c t   s c h e d _ e n t i t y   {     . . .     s t r u c t   r b _ n o d e         r u n _ n o d e ;                 . . .     u 6 4                     v r u n t i m e ;                                 . . . } ;
调 度 时 刻 调 度 时 刻 调 度 的 本 质 就 是 选 择 下 一 个 进 程 ， 然 后 切 换 。 在 执 行 调 度 之 前 需 要 设 置 调 度 标 记   T I F _ N E E D _ R E S C H E D ， 然 后 在 调 度 的 时 候 会 判 断 当 前 进 程 有 没 有 被 设 置   T I F _ N E E D _ R E S C H E D ， 如 果 设 置 则 调 用 函 数   s c h e d u l e   来 进 行 调 度 。 1 .   设 置 调 度 标 记 设 置 调 度 标 记 为   C P U   上 正 在 运 行 的 进 程   t h r e a d _ i n f o   结 构 体 里 的   f l a g s   成 员 设 置   T I F _ N E E D _ R E S C H E D 。 那 么 ， 什 么 时 候 设 置 T I F _ N E E D _ R E S C H E D 呢   ？ 1 .   s c h e d u l e r _ t i c k   时 钟 中 断 2 .   w a k e _ u p _ p r o c e s s   唤 醒 进 程 的 时 候
3 .   d o _ f o r k   创 建 新 进 程 的 时 候 4 .   s e t _ u s e r _ n i c e   修 改 进 程 n i c e 值 的 时 候 5 .   s m p _ s e n d _ r e s c h e d u l e   负 载 均 衡 的 时 候 2 .   执 行 调 度 执 行 调 度 K e r n e l   判 断 当 前 进 程 标 记 是 否 为   T I F _ N E E D _ R E S C H E D ， 是 的 话 调 用   s c h e d u l e   函 数 ， 执 行 调 度 ， 切 换 上 下 文 ， 这 也 是 上 面 抢 占 ( p r e e m p t ) 机 制 的 本 质 。 那 么 在 哪 些 情 况 下 会 执 行   s c h e d u l e   呢 ？ 1 .   用 户 态 抢 占 r e t _ t o _ u s e r   是 异 常 触 发 ， 系 统 调 用 ， 中 断 处 理 完 成 后 都 会 调 用 的 函 数 。
2 .   内 核 态 抢 占 可 以 看 出 无 论 是 用 户 态 抢 占 ， 还 是 内 核 态 抢 占 ， 最 终 都 会 调 用   s c h e d u l e   函 数 来 执 行 真 正 的 调 度 ： 还 记 得 调 度 的 本 质 吗 ？ 调 度 的 本 质 就 是 选 择 下 一 个 进 程 ， 然 后 切 换 。 如 上 图 所 示 ， 用 函 数   p i c k _ n e x t _ t a s k   选 择 下 一 个 进 程 ， 其 本 质 就 是 调 度 算 法 的 实 现 ； 用 函 数   c o n t e x t _ s w i t c h   完 成 进 程 的 切 换 ， 即 进 程 上 下 文 的 切 换 。 下 面 我 们 分 别 看 下 这 两 个 核 心 功 能 。
调 度 算 法 调 度 算 法 字 段 字 段 版 本 版 本 O ( n )   调 度 器 l i n u x 0 . 1 1   -   2 . 4 O ( 1 )   调 度 器 l i n u x 2 . 6 C F S 调 度 器 l i n u x 2 . 6 至 今 O ( n ) O ( n )   调 度 器 是 在 内 核 2 . 4 以 及 更 早 期 版 本 采 用 的 算 法 ， O ( n )   代 表 的 是 寻 找 一 个 合 适 的 任 务 的 时 间 复 杂 度 。 调 度 器 定 义 了 一 个 r u n q u e u e   的 运 行 队 列 ， 将 进 程 的 状 态 变 为   R u n n i n g   的 都 会 添 加 到 此 运 行 队 列 中 ， 但 是 不 管 是 实 时 进 程 ， 还 是 普 通 进 程 都 会 添 加 到 这 个 运 行 队 列 中 。 当 需 要 从 运 行 队 列 中 选 择 一 个 合 适 的 任 务 时 ， 就 需 要 从 队 列 的 头 遍 历 到 尾 部 ， 这 个 时 间 复 杂 度 是 O ( n ) ， 运 行 队 列 中 的 任 务 数 目 越 大 ， 调 度 器 的 效 率 就 越 低 。 所 以   O ( n )   调 度 器 有 如 下 缺 陷 ： 时 间 复 杂 度 是   O ( n ) ， 运 行 队 列 中 的 任 务 数 目 越 大 ， 调 度 器 的 效 率 就 越 低 。 实 时 进 程 不 能 及 时 调 度 ， 因 为 实 时 进 程 和 普 通 进 程 在 一 个 列 表 中 ， 每 次 查 实 时 进 程 时 ， 都 需 要 全 部 扫 描 整 个 列 表 ， 所 以 实 时 进 程 不 是 很 “ 实 时 ” 。 S M P   系 统 不 好 ， 因 为 只 有 一 个   r u n q u e u e ， 选 择 下 一 个 任 务 时 ， 需 要 对 这 个 r u n q u e u e   队 列 进 行 加 锁 操 作 ， 当 任 务 较 多 的 时 候 ， 则 在 临 界 区 的 时 间 就 比 较 长 ， 导 致 其 余 的   C P U   自 旋 浪 费 。 C P U 空 转 的 现 象 存 在 ， 因 为 系 统 中 只 有 一 个 r u n q u e u e ， 当 运 行 队 列 中 的 任 务 少 于 C P U   的 个 数 时 ， 其 余 的   C P U   则 是   i d l e   状 态 。 O ( 1 ) 内 核 2 . 6 采 用 了 O ( 1 )   调 度 器 ， 让 每 个   C P U   维 护 一 个 自 己 的   r u n q u e u e ， 从 而 减 少 了 锁 的 竞 争 。 每 一 个 r u n q u e u e   运 行 队 列 维 护 两 个 链 表 ， 一 个 是   a c t i v e   链 表 ， 表 示 运 行 的 进 程 都 挂 载   a c t i v e   链 表 中 ； 一 个 是   e x p i r e d   链 表 ， 表 示 所 有 时 间 片 用 完 的 进 程 都 挂 载   e x p i r e d 链 表 中 。 当   a c i t v e   中 无 进 程 可 运 行 时 ， 说 明 系 统 中 所 有 进 程 的 时 间 片 都 已 经 耗 光 ， 这 时 候 则 只 需 要 调 整   a c t i v e   和   e x p i r e d   的 指 针 即 可 。 每 个 优 先 级 数 组 包 含 1 4 0 个 优 先 级 队 列 ， 也 就 是 每 个 优 先 级 对 应 一 个 队 列 ， 其 中 前 1 0 0 个 对 应 实 时 进 程 ， 后 4 0 个 对 应 普 通 进
程 。 如 下 图 所 示 ： 总 的 来 说   O ( 1 )   调 度 器 的 出 现 是 为 了 解 决   O ( n )   调 度 器 不 能 解 决 的 问 题 ， 但   O ( 1 )   调 度 器 有 个 问 题 ， 一 个 高 优 先 级 多 线 程 的 应 用 会 比 低 优 先 级 单 线 程 的 应 用 获 得 更 多 的 资 源 ， 这 就 会 导 致 一 个 调 度 周 期 内 ， 低 优 先 级 的 应 用 可 能 一 直 无 法 响 应 ， 直 到 高 优 先 级 应 用 结 束 。 C F S 调 度 器 就 是 站 在 一 视 同 仁 的 角 度 解 决 了 这 个 问 题 ， 保 证 在 一 个 调 度 周 期 内 每 个 任 务 都 有 执 行 的 机 会 ， 执 行 时 间 的 长 短 ， 取 决 于 任 务 的 权 重 。 下 面 详 细 看 下 C F S 调 度 器 是 如 何 动 态 调 整 任 务 的 运 行 时 间 ， 达 到 公 平 调 度 的 。 C F S   调 度 器 调 度 器 C F S 是   C o m p l e t e l y   F a i r   S c h e d u l e r   简 称 ， 即 完 全 公 平 调 度 器 。 C F S   调 度 器 和 以 往 的 调 度 器 不 同 之 处 在 于 没 有 固 定 时 间 片 的 概 念 ， 而 是 公 平 分 配   C P U   使 用 的 时 间 。 比 如 ： 2 个 优 先 级 相 同 的 任 务 在 一 个   C P U   上 运 行 ， 那 么 每 个 任 务 都 将 会 分 配 一 半 的   C P U   运 行 时 间 ， 这 就 是 要 实 现 的 公 平 。 但 现 实 中 ， 必 然 是 有 的 任 务 优 先 级 高 ， 有 的 任 务 优 先 级 低 。 C F S   调 度 器 引 入 权 重   w e i g h t   的 概 念 ， 用   w e i g h t   代 表 任 务 的 优 先 级 ， 各 个 任 务 按 照   w e i g h t   的 比 例 分 配   C P U   的 时 间 。 比 如 ： 2 个 任 务 A 和 B ， A 的 权 重 是 1 0 2 4 ， B 的 权 重 是 2 0 4 8 ， 则 A 占   1 0 2 4 / ( 1 0 2 4 + 2 0 4 8 ) =   3 3 . 3 %   的   C P U   时 间 ， B 占   2 0 4 8 / ( 1 0 2 4 + 2 0 4 8 ) = 6 6 . 7 %   的   C P U   时 间 。 在 引 入 权 重 之 后 ， 分 配 给 进 程 的 时 间 计 算 公 式 如 下 ： 实 际 运 行 时 间 实 际 运 行 时 间   =   调 度 周 期 调 度 周 期   *   进 程 权 重 进 程 权 重   /   所 有 进 程 权 重 之 和 所 有 进 程 权 重 之 和 C F S   调 度 器 用 n i c e 值 表 示 优 先 级 ， 取 值 范 围 是 [ - 2 0 ,   1 9 ] ， n i c e 和 权 重 是 一 一 对 应 的 关 系 。 数 值 越 小 代 表 优 先 级 越 大 ， 同 时 也 意 味 着 权 重 值 越 大 ， n i c e 值 和 权 重 之 间 的 转 换 关 系 ：
数 组 值 计 算 公 式 是 ： w e i g h t   =   1 0 2 4   /   1 . 2 5 n i c e 。 调 度 周 期 调 度 周 期 如 果 一 个   C P U   上 有   N   个 优 先 级 相 同 的 进 程 ， 那 么 每 个 进 程 会 得 到   1 / N   的 执 行 机 会 ， 每 个 进 程 执 行 一 段 时 间 后 ， 就 被 调 出 ， 换 下 一 个 进 程 执 行 。 如 果 这 个   N   的 数 量 太 大 ， 导 致 每 个 进 程 执 行 的 时 间 很 短 ， 就 要 调 度 出 去 ， 那 么 系 统 的 资 源 就 消 耗 在 进 程 上 下 文 切 换 上 去 了 。 所 以 对 于 此 问 题 在   C F S   中 则 引 入 了 调 度 周 期 ， 使 进 程 至 少 保 证 执 行 0 . 7 5 m s 。 调 度 周 期 的 计 算 通 过 如 下 代 码 ： 当 进 程 数 目 小 于 8 时 ， 则 调 度 周 期 等 于 6 m s 。 当 进 程 数 目 大 于 8 时 ， 则 调 度 周 期 等 于 进 程 的 数 目 乘 以 0 . 7 5 m s 。 虚 拟 运 行 时 间 虚 拟 运 行 时 间 根 据 上 面 进 程 实 际 运 行 时 间 的 公 式 ， 可 以 看 出 ， 权 重 不 同 的 2 个 进 程 的 实 际 执 行 时 间 是 不 相 等 的 ， 但 是   C F S   想 保 证 每 个 进 程 运 行 时 间 相 等 ， 因 此   C F S   引 入 了 虚 拟 时 间 的 概 念 。 虚 拟 时 间 ( v r i t u r e _ r u n t i m e ) 和 实 际 时 间 ( w a l l _ t i m e ) 转 换 公 式 如 下 ： v r i t u r e _ r u n t i m e   =   ( w a l l _ t i m e   *   N I C E 0 _ T O _ w e i g h t )   /   w e i g h t 其 中 ， N I C E 0 _ T O _ w e i g h t   代 表 的 是   n i c e   值 等 于 0 对 应 的 权 重 ， 即 1 0 2 4 ， w e i g h t   是 该 任 务 对 应 的 权 重 。 c o n s t   i n t   s c h e d _ p r i o _ t o _ w e i g h t [ 4 0 ]   =   {   / *   - 2 0   * /           8 8 7 6 1 ,           7 1 7 5 5 ,           5 6 4 8 3 ,           4 6 2 7 3 ,           3 6 2 9 1 ,   / *   - 1 5   * /           2 9 1 5 4 ,           2 3 2 5 4 ,           1 8 7 0 5 ,           1 4 9 4 9 ,           1 1 9 1 6 ,   / *   - 1 0   * /             9 5 4 8 ,             7 6 2 0 ,             6 1 0 0 ,             4 9 0 4 ,             3 9 0 6 ,   / *     - 5   * /             3 1 2 1 ,             2 5 0 1 ,             1 9 9 1 ,             1 5 8 6 ,             1 2 7 7 ,   / *       0   * /             1 0 2 4 ,               8 2 0 ,               6 5 5 ,               5 2 6 ,               4 2 3 ,   / *       5   * /               3 3 5 ,               2 7 2 ,               2 1 5 ,               1 7 2 ,               1 3 7 ,   / *     1 0   * /               1 1 0 ,                 8 7 ,                 7 0 ,                 5 6 ,                 4 5 ,   / *     1 5   * /                 3 6 ,                 2 9 ,                 2 3 ,                 1 8 ,                 1 5 , } ;   s t a t i c   u 6 4   _ _ s c h e d _ p e r i o d ( u n s i g n e d   l o n g   n r _ r u n n i n g ) {   i f   ( u n l i k e l y ( n r _ r u n n i n g   >   s c h e d _ n r _ l a t e n c y ) )     r e t u r n   n r _ r u n n i n g   *   s y s c t l _ s c h e d _ m i n _ g r a n u l a r i t y ;   e l s e     r e t u r n   s y s c t l _ s c h e d _ l a t e n c y ; }   s t a t i c   u n s i g n e d   i n t   s c h e d _ n r _ l a t e n c y   =   8 ; u n s i g n e d   i n t   s y s c t l _ s c h e d _ l a t e n c y       =   6 0 0 0 0 0 0 U L L ; u n s i g n e d   i n t   s y s c t l _ s c h e d _ m i n _ g r a n u l a r i t y       =   7 5 0 0 0 0 U L L ;
回复

举报

高级模式
B Color Image Link Quote Code Smilies
您需要登录后才可以回帖 登录 | 立即注册

本版积分规则

使用Markdown编辑器编辑 使用富文本编辑器编辑

Archiver| 手机版| 小黑屋|
Powered by Discuz! X3.4 Copyright © 2001-2020, Tencent Cloud. 商业源码建议获取授权，如侵犯您的权益，请联系客服处理