【CPU】Linux のプロセススケジューラの基礎

jobs
Photo by GAGA

映画『スティーブ・ジョブズ』の感想

製品に関するエピソードはmacintoshまでで, CEO復帰後のiMac, iPod, iPhoneの話はでてこないので, 期待していたシーンがなかったという人もでてくるかもしれないですが, 個人的には90’sまでの話が厚くて良かったです。

独裁とも言われるリーダーシップがいつも正しいとは限らない(特に平時の時)と思いますが, 一貫した美学とコンセプトは意思を持って従わせるには充分だったと思います。

印象に残ったのは, フロッピーディスクドライブ(FDD)のイジェクトボタンを外したという話。

今の会社で働いてわかったのは, 機能追加より機能削減の方がいかに難しいかという点。

機能追加は社内会議で通りやすい。何故なら, 既存ユーザが困ることはないしカタログスペックも上がるから。

一方で機能削減は、何故やめるのか?操作がわからず困る人がでるのでは?と批判に遭うのが(今の会社では)容易に想像できます。

結果, 無難な選択として機能は残る。日本的文化の中では, イジェクトボタンを外すという決断は難しいと思いました。

同時期, 日本製テレビのリモコンが多機能に進んでいったのも偶然ではないと思います。

Think Different

“Here’s to the crazy ones. The misfits. The rebels. The troublemakers.
The round pegs in the square holes. The ones who see things differently.
They’re not fond of rules. And they have no respect for the status quo. You can quote them, disagree with them, glorify or vilify them.
About the only thing you can’t do is ignore them. Because they change things. They push the human race forward. While some may see them as the crazy ones, we see genius. Because the people who are crazy enough to think they can change the world, are the ones who do.”

この言葉, 良いですね。(youtube)

MIT Media Labの石井教授の講演で, ライフスパンの話になり Vision (100y) > Needs (~10y) > Technology (1~2y) であるという話がありました。

たしかに100年間続いた企業はありますが、たったひとつの技術やNeedsだけを追って100年続いた企業はなさそうです。一方で, 企業理念(Vision)というのは変わっていないと思います。

時代が変わればNeedsが変化し, Technologyも変化する。

Apple創業から紆余曲折がありましたが, スティーブ・ジョブズはVisionを提示できる経営者だったと思います。

プロセススケジューラ

前置きが長かったですが, LinuxのプロセススケジューラとI/Oスケジューラについてです。

はじめに, kernelソースコードリーディングにはLinux Cross Referenceが便利です。
膨大なKernelのソースコードをどこから読み始めたら良いかですが, Web上ではプロセススケジューラやデバイスドライバを薦めている意見が多いように感じました。上記理由の中では, ソースが閉じており横断的に読む必要がないという意見がありました。

1つのCPUを持つシステムでは瞬間的に実行できるプロセスの数は1つですが, Linuxは複数のプロセスが実行可能です。
実際には, タイムスライスと呼ばれる短い時間でCPUに割り当てるプロセスを切り替えているためで, ミリ秒~ナノ秒オーダでプロセスを切り替えており, 見かけ上は複数のプロセスが同時に動いているように見えます。

RUN Queue

CPUは RUN Queueという待ち行列に登録されたタスクをひとつずつ実行していきます。
このQueueから単にひとつ取得するために検索のオーダが常に1となるため O(1)スケジューラと言われるものもあります。

Kernel 2.6以降では2種類のRUN Queueがあり、CPUごとにQueueを持っています。

  • Active Queue : 実行可能で実行割り当て時間を待っているプロセス
  • Expired Queue : 実行可能状態だが実行割り当て時間を使い果たしてしまったプロセス

実行割り当て時間を使い切ってしまったプロセスはactiveQueueからexpiredQueueへ移動し, activeQueueがない場合にはexpiredQueueが実行されます。

Completely Fair Scheduler

タスクスケジューラがどのCPUコアでそれをどれくらいの時間で使用するかというのを決めていて, ナノ秒単位でタスクの切り替えを行っています。

Completely Fair Scheduler (CFS) はKernel 2.6.16 で導入されたタスクスケジューラです。
CPU実行時間をできるだけ均等にタスクに振り分けます。実際には, プロセスの種類 (shell or not), タスク優先度 (nice etc)など単純ではありませんが, おおまかにはタスクごとに公平という思想になっています。

例えば, CFSはタスクをできるだけ公平にCPU時間を割り当てようとするために, 多数の子プロセスを生むアプリケーションが稼働していると全体のプロセスに占めるそのアプリケーションの割合が相対的に上がり, 他のアプリケーションの応答性が悪くなることがあります。

詳しくは kernel/shced/ を参照。

Auto Group Scheduling

Kernel 2.6.38で導入されたAutogroup Schedulingでは, プロセス親子関係などを基にSession IDというグループとしてまとめてそのグループごとに均等にCPU時間を割当てるようにします。また, グループ内のそれぞれのプロセスにも均等にCPU時間を割当てます。

これはCFSの欠点であったfork(2)を多用した場合, このタスク群が全体に占める割合が大きくなることを防ぐためかと思います。

詳細はこちらの情報から追っていくと良いと思いますが, “the patch that does wonders”, “200 lines Patch”と呼ばれるほどのパッチでGUIが相当速くなったという報告もあるので, 場合によってはかなりの体感速度改善につながると思われます。

この設定は /proc/sys/kernel/sched_autogroup_enabled の数字を書き換えることで可能です。

debianとubuntuのデフォルト設定は以下でした。

# debian7
/proc/sys/kernel$ cat sched_autogroup_enabled 
0
# ubuntu13.04
/proc/sys/kernel$ cat sched_autogroup_enabled 
1

task_group構造体は下記。(kernel/shced/shced.h)

228 /* task group related information */
229 struct task_group {
230         struct cgroup_subsys_state css;
231 
232 #ifdef CONFIG_FAIR_GROUP_SCHED
233         /* schedulable entities of this group on each cpu */
234         struct sched_entity **se;
235         /* runqueue "owned" by this group on each cpu */
236         struct cfs_rq **cfs_rq;
237         unsigned long shares;
238 
239 #ifdef  CONFIG_SMP
240         atomic_long_t load_avg;
241         atomic_t runnable_avg;
242 #endif
243 #endif
244 
245 #ifdef CONFIG_RT_GROUP_SCHED
246         struct sched_rt_entity **rt_se;
247         struct rt_rq **rt_rq;
248 
249         struct rt_bandwidth rt_bandwidth;
250 #endif
251 
252         struct rcu_head rcu;
253         struct list_head list;
254 
255         struct task_group *parent;
256         struct list_head siblings;
257         struct list_head children;
258 
259 #ifdef CONFIG_SCHED_AUTOGROUP
260         struct autogroup *autogroup;
261 #endif
262 
263         struct cfs_bandwidth cfs_bandwidth;
264 };
265 

ブロックデバイスへのI/Oスケジューラ

I/Oスケジューラについて。I/Oを伴うデバイスは大きく, キャラクタデバイスとブロックデバイスに分類されます。

セクタ単位で管理されているブロックデバイスのI/Oスケジューリングの種類は, noop (No Optimization), CFS, deadline, anticipatoryがあり, sdaの場合は /sys/block/queue/scheduler で設定できます。


[1] Completely Fair Scheduler によるマルチプロセッシング
[2] Linux カーネルに関する知識