Manpages

SCHED_FIFO: フ ァ ー ス ト イ ン フ ァ ー ス ト ア ウ ト ス ケ ジ ュ ー リ ン グ
SCHED_FIFO は 0 よ り 大 き な 静 的 優 先 度 で の み 使 用 で き る 。 こ の ポ リ シ ー で は 、 SCHED_FIFO ス レ ッ ド が 実 行 可 能 に な っ た 場 合 、 そ の ポ リ シ ー が SCHED_OTHER、 SCHED_BATCH、 SCHED_IDLE の 現 在 実 行 中 の ス レ ッ ド は 直 ち に 実 行 権 を 取 り 上 げ ら れ る 。 SCHED_FIFO は 時 分 割 の な い 単 純 な ス ケ ジ ュ ー リ ン グ ア ル ゴ リ ズ ム で あ る 。 SCHED_FIFO ポ リ シ ー で ス ケ ジ ュ ー リ ン グ さ れ て い る ス レ ッ ド に は 以 下 の ル ー ル が 適 用 さ れ る :

レ ッ ド は そ の 優 先 度 の リ ス ト の 先 頭 に 留 ま り 続 け 、 よ り 高 い 優 先 度 の ス レ ッ ド 全 て が 停 止 (block) し た 場 合 に 実 行 を 再 開 す る 。

そ の 他 の イ ベ ン ト に よ っ て SCHED_FIFO ポ リ シ ー で ス ケ ジ ュ ー リ ン グ さ れ る ス レ ッ ド が 同 じ 優 先 度 の 実 行 可 能 な ス レ ッ ド の 待 ち リ ス ト の 中 を 移 動 す る こ と は な い 。

SCHED_FIFO ス レ ッ ド は I/O 要 求 に よ っ て 停 止 す る か 、 よ り 高 い 優 先 度 の ス レ ッ ド に よ っ て 置 き か え ら れ る か 、 sched_yield(2) を 呼 び 出 す ま で 実 行 を 続 け る 。

SCHED_RR: ラ ウ ン ド ロ ビ ン (round−robin) ス ケ ジ ュ ー リ ン グ
SCHED_RR は SCHED_FIFO の 単 純 な 拡 張 で あ る 。 上 述 さ れ た SCHED_FIFO に 関 す る 記 述 は 全 て SCHED_RR に 適 用 で き る 。 異 な る の は そ れ ぞ れ の ス レ ッ ド は 最 大 時 間 単 位 ま で し か 実 行 で き な い と い う こ と で あ る 。 SCHED_RR ス レ ッ ド が 時 間 単 位 と 同 じ か そ れ よ り 長 い 時 間 実 行 さ れ る と 、 そ の 優 先 度 の リ ス ト の 最 後 に 置 か れ る 。 よ り 高 い 優 先 度 の ス レ ッ ド に よ っ て 置 き か え ら れ 、 そ の 後 実 行 を 再 開 し た SCHED_RR ス レ ッ ド は 、 そ の ラ ウ ン ド ロ ビ ン 時 間 単 位 を 完 全 に 使 い 切 る ま で 実 行 さ れ る 。 そ の 時 間 単 位 の 長 さ は sched_rr_get_interval(2) を 使 っ て 取 得 で き る 。

SCHED_DEADLINE: 散 発 タ ス ク モ デ ル の デ ッ ド ラ イ ン ス ケ ジ ュ ー リ ン グ バ ー ジ ョ ン 3.14 以 降 で は 、 Linux は デ ッ ド ラ イ ン ス ケ ジ ュ ー リ ン グ ポ リ シ ー (SCHED_DEADLINE) が 提 供 さ れ る 。 現 在 の と こ ろ 、 こ の ポ リ シ ー は GEDF (Global Earliest Deadline First) を 使 っ て CBS (Constant Bandwidth Server) と の 組 み 合 わ せ で 実 装 さ れ て い る 。 こ の ポ リ シ ー と 関 連 す る 属 性 の 設 定 、 取 得 を 行 う に は 、 Linux 固 有 の シ ス テ ム コ ー ル sched_setattr(2) と sched_getattr(2) を 使 用 す る 必 要 が あ る 。 散 発 タ ス ク (sporadic task) は ジ ョ ブ 列 を 持 つ タ ス ク で 、 各 ジ ョ ブ は 期 間 (period) あ た り 多 く と も 1 回 だ け 有 効 化 さ れ る 。 各 ジ ョ ブ に は relative deadline (相 対 デ ッ ド ラ イ ン ) と computation time (計 算 時 間 ) が あ る 。 相 対 デ ッ ド ラ イ ン は 、 そ の ジ ョ ブ が そ の デ ッ ド ラ イ ン よ り 前 に 実 行 が 終 了 す べ き で あ る こ と を 示 す 。 計 算 時 間 は 、 こ の ジ ョ ブ を 実 行 す る の に 必 要 な CPU 時 間 で あ る 。 新 し い ジ ョ ブ を 実 行 す る 必 要 が 出 て タ ス ク が 起 こ さ れ る 時 点 は arrival time (到 着 時 刻 ) と 呼 ば れ る (要 求 時 刻 (request time) や 解 放 時 刻 (release time) と 呼 ば れ る こ と も あ る )。 start time は タ ス ク が 実 行 を 開 始 す る 時 刻 で あ る 。 し た が っ て 、 absolute deadline (絶 対 デ ッ ド ラ イ ン ) は 到 着 時 刻 に 相 対 デ ッ ド ラ イ ン を 加 算 す る こ と で 求 め ら れ る 。 以 下 の 図 は こ れ ら の 用 語 を ま と め た も の で あ る 。

arrival/wakeup absolute deadline
| start time |
| | |
v v v
−−−−−x−−−−−−−−xooooooooooooooooo−−−−−−−−x−−−−−−−−x−−−
|<− comp. time −>|
|<−−−−−−− relative deadline −−−−−−>|
|<−−−−−−−−−−−−−− period −−−−−−−−−−−−−−−−−−−>|

sched_setattr(2) を 使 っ て ス レ ッ ド に SCHED_DEADLINE ポ リ シ ー を 設 定 す る 際 、 Runtime, Deadline, Period の 3 つ の パ ラ メ ー タ ー を 指 定 す る こ と が で き る 。 こ れ ら の パ ラ メ ー タ ー は 必 ず し も 上 で 述 べ た 用 語 に 対 応 し て い る わ け で は な い 。 よ く あ る 方 法 と し て は 、 Runtime に 平 均 計 算 時 間 (も し く は ハ ー ド リ ア ル タ イ ム タ ス ク の 場 合 は 最 悪 ケ ー ス の 実 行 時 間 ) よ り も 大 き な 値 を 、 Deadline に 相 対 デ ッ ド ラ イ ン を 、 Period に タ ス ク の 期 間 (period) を 設 定 す る 。 し た が っ て 、 SCHED_DEADLINE ス ケ ジ ュ ー リ ン グ で は 、 以 下 の よ う に な る 。

arrival/wakeup absolute deadline
| start time |
| | |
v v v
−−−−−x−−−−−−−−xooooooooooooooooo−−−−−−−−x−−−−−−−−x−−−
|<−− Runtime −−−−−−−>|
|<−−−−−−−−−−− Deadline −−−−−−−−−−−>|
|<−−−−−−−−−−−−−− Period −−−−−−−−−−−−−−−−−−−>|

3 つ の デ ッ ド ラ イ ン ス ケ ジ ュ ー リ ン グ パ ラ メ ー タ ー は sched_attr 構 造 体 の sched_runtime, sched_deadline, sched_period フ ィ ー ル ド に 対 応 す る 。 こ れ ら の フ ィ ー ル ド は ナ ノ 秒 単 位 の 値 で あ る 。 sched_period に 0 が 指 定 さ れ た 場 合 sched_deadline と 同 じ 値 に な る 。 カ ー ネ ル で は 以 下 の 関 係 が 成 り 立 つ こ と が 求 め ら れ る 。

sched_runtime <= sched_deadline <= sched_period こ れ に 加 え て 、 現 在 の 実 装 で は 、 す べ て の パ ラ メ ー タ ー 値 は 少 な く と も 1024 (実 装 の 粒 度 で あ る 1 マ イ ク ロ 秒 よ り も 少 し だ け 大 き な 値 ) で 2^63 よ り も 小 さ く な け れ ば な ら な い 。 こ れ ら の チ ェ ッ ク の い ず れ か が 失 敗 す る と 、 sched_setattr(2) は エ ラ ー EINVAL で 失 敗 す る 。

CBS に よ り タ ス ク 間 の 干 渉 が な い こ と が 保 証 さ れ る 。 指 定 さ れ た Runtime を 超 え て 実 行 し よ う と し た ス レ ッ ド は 絞 り 込 ま れ る こ と に な る 。 デ ッ ド ラ イ ン ス ケ ジ ュ ー リ ン グ の 保 証 が き ち ん と 機 能 す る た め に は 、 カ ー ネ ル は SCHEDULING ス レ ッ ド の 集 合 が 指 定 さ れ た 制 約 条 件 に お さ ま ら な い (ス ケ ジ ュ ー リ ン グ で き な い ) 状 況 を 防 止 し な け れ ば な ら な い 。 そ の た め 、 カ ー ネ ル は SCHED_DEADLINE ポ リ シ ー と 属 性 を 設 定 、 変 更 す る 際 に 、 受 け 入 れ チ ェ ッ ク (admittance test) を 実 行 す る 。 こ の 受 け 入 れ チ ェ ッ ク は 、 変 更 が 実 行 可 能 か を 計 算 し 、 も し 実 行 で き な い よ う で あ れ ば sched_setattr(2) は エ ラ ー EBUSY で 失 敗 す る 。 例 え ば 、 使 用 率 の 合 計 が 利 用 可 能 な 合 計 CPU 数 以 下 で あ る 必 要 が あ る (た だ し 、 必 ず し も 十 分 と い う わ け で は な い )。 な お 、 各 ス レ ッ ド は 最 大 で Period あ た り Runtime だ け 実 行 さ れ る こ と が あ る の で 、 そ の ス レ ッ ド の 使 用 率 は Runtime を Period で 割 っ た も の と な る 。 ス レ ッ ド が SCHED_DEADLINE ポ リ シ ー に 受 け 入 れ ら れ た 場 合 に 保 証 を 実 現 す る た め 、 SCHED_DEADLINE ス レ ッ ド は シ ス テ ム で (ユ ー ザ ー が 制 御 可 能 な ) 最 高 優 先 度 の ス レ ッ ド と な る 。 い ず れ か の SCHED_DEADLINE ス レ ッ ド が 実 行 可 能 で あ れ ば 、 他 の ポ リ シ ー で ス ケ ジ ュ ー リ ン グ さ れ て い る ス レ ッ ド は す べ て 横 取 り さ れ る 。

SCHED_DEADLINE ポ リ シ ー で ス ケ ジ ュ ー リ ン グ さ れ て い る ス レ ッ ド が fork(2) を 呼 び 出 す と 、 そ の ス レ ッ ド で reset−on−fork フ ラ グ が セ ッ ト さ れ て い る 場 合 (下 記 参 照 ) を 除 き 、 エ ラ ー EAGAIN で 失 敗 す る 。

SCHED_DEADLINE ス レ ッ ド が sched_yield(2) を 呼 び 出 す と 、 現 在 の ジ ョ ブ が CPU を 明 け 渡 し 、 新 し い 期 間 が 開 始 す る の を 待 つ 。

SCHED_OTHER: Linux の デ フ ォ ル ト の 時 分 割 ス ケ ジ ュ ー リ ン グ
SCHED_OTHER は 静 的 優 先 度 0 で の み 使 用 で き る 。 SCHED_OTHER は Linux 標 準 の 時 分 割 ス ケ ジ ュ ー ラ で 、 特 別 な リ ア ル タ イ ム 機 構 を 必 要 と し て い な い 全 て の ス レ ッ ド で 使 用 さ れ る 。 実 行 す る ス レ ッ ド は 、 静 的 優 先 度 0 の リ ス ト か ら 、 こ の リ ス ト の 中 だ け で 決 定 さ れ る 「 動 的 な 」 優 先 度 (dynamic priority) に 基 い て 決 定 さ れ る 。 動 的 な 優 先 度 は (nice(2), setpriority(2), sched_setattr(2) に よ り 設 定 さ れ る ) nice 値 に 基 づ い て 決 定 さ れ る も の で 、 単 位 時 間 毎 に 、 ス レ ッ ド が 実 行 可 能 だ が 、 ス ケ ジ ュ ー ラ に よ り 実 行 が 拒 否 さ れ た 場 合 に イ ン ク リ メ ン ト さ れ る 。 こ れ に よ り 、 全 て の SCHED_OTHER ス レ ッ ド で の 公 平 性 が 保 証 さ れ る 。

SCHED_BATCH: バ ッ チ プ ロ セ ス の ス ケ ジ ュ ー リ ン グ
(Linux 2.6.16 以 降 ) SCHED_BATCH は 静 的 優 先 度 0 で の み 使 用 で き る 。 こ の ポ リ シ ー は (nice 値 に 基 づ く ) 動 的 な 優 先 度 に し た が っ て ス レ ッ ド の ス ケ ジ ュ ー リ ン グ が 行 わ れ る と い う 点 で 、 SCHED_OTHER に 似 て い る 。 異 な る の は 、 こ の ポ リ シ ー で は 、 ス レ ッ ド が 常 に CPU に 負 荷 の か か る (CPU−intensive) 処 理 を 行 う と 、 ス ケ ジ ュ ー ラ が 仮 定 す る 点 で あ る 。 ス ケ ジ ュ ー ラ は ス レ ッ ド を 呼 び 起 こ す 毎 に そ の ス レ ッ ド に ス ケ ジ ュ ー リ ン グ 上 の ペ ナ ル テ ィ を 少 し 課 し 、 そ の 結 果 、 こ の ス レ ッ ド は ス ケ ジ ュ ー リ ン グ の 決 定 で 若 干 冷 遇 さ れ る よ う に な る 。 こ の ポ リ シ ー は 、 非 対 話 的 な 処 理 だ が そ の nice 値 を 下 げ た く な い 処 理 や 、 (処 理 の タ ス ク 間 で ) 余 計 な タ ス ク の 置 き 換 え の 原 因 と あ る 対 話 的 な 処 理 な し で 確 定 的 な (deterministic) ス ケ ジ ュ ー リ ン グ ポ リ シ ー を 適 用 し た い 処 理 に 対 し て 有 効 で あ る 。

SCHED_IDLE: 非 常 に 優 先 度 の 低 い ジ ョ ブ の ス ケ ジ ュ ー リ ン グ
(Linux 2.6.23 以 降 ) SCHED_IDLE は 静 的 優 先 度 0 で の み 使 用 で き る 。 こ の ポ リ シ ー で は プ ロ セ ス の nice 値 は ス ケ ジ ュ ー リ ン グ に 影 響 を 与 え な い 。 非 常 に 低 い 優 先 度 で の ジ ョ ブ の 実 行 を 目 的 と し た も の で あ る (非 常 に 低 い 優 先 度 と は 、 ポ リ シ ー SCHED_OTHER か SCHED_BATCH で の nice 値 +19 よ り さ ら に 低 い 優 先 度 で あ る )。 子 プ ロ セ ス で の ス ケ ジ ュ ー リ ン グ ポ リ シ ー の リ セ ッ ト 各 ス レ ッ ド に は reset−on−fork ス ケ ジ ュ ー リ ン グ フ ラ グ が あ る 。 こ の フ ラ グ が セ ッ ト さ れ る と 、 fork(2) で 作 成 さ れ る 子 プ ロ セ ス は 特 権 ス ケ ジ ュ ー リ ン グ ポ リ シ ー を 継 承 し な い 。 reset−on−fork フ ラ グ は 以 下 の い ず れ か の 方 法 で セ ッ ト で き る 。

こ れ ら の 2 つ の API で 使 用 さ れ る 定 数 は 名 前 が 違 っ て い る 点 に 注 意 す る こ と 。 同 様 に reset−on−fork フ ラ グ の 状 態 は sched_getscheduler(2) と sched_getattr(2) を 使 っ て 取 得 で き る 。

reset−on−fork 機 能 は メ デ ィ ア 再 生 ア プ リ ケ ー シ ョ ン で の 利 用 を 意 図 し た も の で あ る 。 複 数 の 子 プ ロ セ ス を 作 成 す る こ と で 、 ア プ リ ケ ー シ ョ ン は RLIMIT_RTTIME リ ソ ー ス 上 限 (getrlimit(2) を 参 照 ) を 避 け る こ と が で き る 。 よ り 正 確 に は 、 reset−on−fork フ ラ グ が セ ッ ト さ れ た 場 合 、 そ れ 以 降 に 作 成 さ れ る 子 プ ロ セ ス に 以 下 の ル ー ル が 適 用 さ れ る 。

SCHED_RR の 場 合 、 子 プ ロ セ ス の ポ リ シ ー は SCHED_OTHER に リ セ ッ ト さ れ る 。

に リ セ ッ ト さ れ る 。 一 度 reset−on−fork フ ラ グ が 有 効 に さ れ た 後 は 、 こ の フ ラ グ を リ セ ッ ト で き る の は 、 ス レ ッ ド が CAP_SYS_NICE ケ ー パ ビ リ テ ィ を 持 つ 場 合 だ け で あ る 。 こ の フ ラ グ は fork(2) で 作 成 さ れ た 子 プ ロ セ ス で は 無 効 に な る 。 特 権 と リ ソ ー ス 制 限

2.6.12 よ り 前 の バ ー ジ ョ ン の Linux カ ー ネ ル で は 、 特 権 ス レ ッ ド (CAP_SYS_NICE ケ ー パ ビ リ テ ィ を 持 つ ス レ ッ ド ) だ け が 0 以 外 の 静 的 優 先 度 を 設 定 す る (す な わ ち 、 リ ア ル タ イ ム ス ケ ジ ュ ー リ ン グ ポ リ シ ー を 設 定 す る ) こ と が で き る 。 非 特 権 ス レ ッ ド が で き る 変 更 は SCHED_OTHER ポ リ シ ー を 設 定 す る こ と だ け で あ り 、 さ ら に 、 こ の 変 更 を 行 え る の は 、 呼 び 出 し 元 の 実 効 ユ ー ザ ー ID が ポ リ シ ー の 変 更 対 象 ス レ ッ ド (pid で 指 定 さ れ た ス レ ッ ド ) の 実 ユ ー ザ ー ID か 実 効 ユ ー ザ ー ID と 一 致 す る 場 合 だ け で あ る 。

SCHED_DEADLINE ポ リ シ ー を 設 定 、 変 更 す る に は 、 ス レ ッ ド が 特 権 (CAP_SYS_NICE) を 持 っ て い な け れ ば な ら な い 。

Linux 2.6.12 以 降 で は 、 リ ソ ー ス 制 限 RLIMIT_RTPRIO が 定 義 さ れ て お り 、 ス ケ ジ ュ ー リ ン グ ポ リ シ ー が SCHED_RR と SCHED_FIFO の 場 合 の 、 非 特 権 ス レ ッ ド の 静 的 優 先 度 の 上 限 を 定 め て い る 。 ス ケ ジ ュ ー リ ン グ ポ リ シ ー と 優 先 度 を 変 更 す る 際 の ル ー ル は 以 下 の 通 り で あ る 。

る 場 合 、 非 特 権 ス レ ッ ド は そ の ス レ ッ ド の ス ケ ジ ュ ー リ ン グ ポ リ シ ー と 優 先 度 を 変 更 で き る が 、 優 先 度 を 現 在 の 自 身 の 優 先 度 と RLIMIT_RTPRIO ソ フ ト リ ミ ッ ト の 大 き い 方 よ り も 高 い 値 に 設 定 で き な い と い う 制 限 が 課 さ れ る 。