このテキストは、運営している韓国のブログを日本語に翻訳したものです。
韓国のブログ：https://yunsuu.notion.site/e379eccd32c545419f0651f743c12c13?v=35310b282de24cc5a292fe45cc498a32&pvs=74
この記事は「Operating Systems: Three Easy Pieces」を読んでまとめた本です。
著者が無料で公開しているので、興味のある方はぜひ読んでみてください。
本にある良い問題は解いてgithubにアップロードしています。
github：https://github.com/yunsuu/ostep-homework-solution
本のリンク：https://pages.cs.wisc.edu/~remzi/OSTEP/
公正な割り当て（比例割り当て）スケジューリング
それぞれのプロセスが、オペレーティングシステムから割り当てられたCPUリソースを取得することを指します。
このようなスケジューリング方式の利点は、各プロセスが一定のCPUの割合を保証されることです。
比例に基づいてCPUを配分するために、抽選券という概念を使用します。
例えば、合計100枚の抽選券があると仮定した場合、Aさんに抽選券75枚、Bさんに抽選券25枚があれば、Aさんは賞品の75％を取得する可能性があり、Bさんはその確率が25％になるでしょう。
既存の比例割り当てスケジューリング技術では、各プロセスがCPUをどれだけ受け取るべきかを記録し、管理する必要がありましたが、抽選券方式では必要な抽選券の数だけを知っていればよいため、事前情報を管理する必要がほとんどないという利点があります。
抽選技術
チケット通貨
例えば、ユーザーAとBがそれぞれ100枚の抽選券を受け取ったと仮定します。ユーザーAはA1とA2の2つのタスクを実行中で、それぞれが500枚の抽選券を割り当てられています（合計1000枚の抽選券から）。ユーザーBは1つのタスクを実行中で、自分の基準通貨10枚の中から10枚を割り当てられています。システムは、A1とA2の抽選券をAの基準通貨500枚から全体の基準となる通貨、それぞれ50枚に変換します。同様に、B1の抽選券10枚は全体の基準となる抽選券100枚に変換されます。全体の基準となる抽選券の量（合計200枚）を基に抽選を行います。
チケットの譲渡
CPUが多く必要なプロセスに抽選券を譲渡して、より多くのCPUを割り当てることができる技術です。この機能はクライアント-サーバ環境で有利です。サーバのタスクが多く必要なときに、クライアントが抽選券をサーバに譲渡して、タスクが早くリクエストされるようにします。リクエストが完了したら、サーバは再度クライアントに抽選券を返します。
チケットのインフレ
簡単に言えば、オペレーティングシステムに対してCPUがより多く必要なので、より多くの抽選券をリクエストする手法です。もちろん、この場合、プロセスが互いに競争するシナリオでは意味がありません（互いに継続的に多くの抽選券をリクエストすることになるため）。
実装方法
スケジューリングはどのように実装するか？実装は単純です。
必要なのは乱数生成器、プロセスの集合を表現するデータ構造、抽選券の合計数だけです。
実装コードは次のようになります。
// counter: used to track if we’ve found the winner yet
int counter = 0;
// winner: use some call to a random number generator to
// get a value, between 0 and the total # of tickets
int winner = getrandom(0, totaltickets);
// current: use this to walk through the list of jobs
node_t *current = head;
while (current) {
counter = counter + current->tickets;
if (counter > winner)
break; // found the winner
current = current->next;
}
// ’current’ is the winner: schedule it...
説明
A、B、Cの3つのタスクがあり、それぞれが100枚、50枚、250枚の抽選券を持っていると仮定します。
乱数を生成して、winnerの値が300であると仮定します。winnerよりもcounterの値が大きいときが勝者です。counterは各抽選券の値を累積して保存します。まずAを走査します。Aの値は100なので、300より小さいです。counterに100を加えてからBに移ります。counter + 50 = 150、150は300より小さいです。同様に、値を50でcounterに累積してからCに移ります。Cに行ったときのcounterの値は500で、したがってCが勝者です。
このとき、プロセスが抽選券の値に基づいて昇順に並べられているときが最小の探索回数を保証します。
プロセスの精度測定
抽選スケジューリング方式は、多く実行するほど設計目的によく一致するという点を追加で覚えておく必要があります（1000回ダイスを振ると各数字が出る確率が1/6に近づく原理と同じです）。
しかし、あまりにも実行されない簡単で短いプロセスを実行しなければならない場合はどうでしょうか？ 意図した通りに動作しない可能性があります。だから運に任せるしかありません。
分配はどうすればいいですか？
ストライドスケジューリング
https://www.waldspurger.org/carl/papers/stride-mit-tm528.pdf
このコードは、Waldspurgerが考慮したストライドスケジュールの擬似コードです。
curr = remove_min(queue); // pick client with min pass
schedule(curr); // run for quantum
curr->pass += curr->stride; // update pass using stride
insert(queue, curr); // return curr to queue
3つのプロセスA、B、Cの各抽選券が100、50、250枚だと仮定しましょう。
全抽選券が10,000枚だとすると、ストライドは全抽選券数を各プロセスの抽選券数で割ったものです。
A = 10,000 / 100 = 100
B = 10,000 / 50 = 200
C = 10,000 / 250 = 40
3つの作業（A、B、C）が各自のストライドで実行されます。各pass値はすべて0から始まります。最初はpass値が同じなので、どのプロセスでも実行できます。Aを選んだと仮定します（任意に、最小のプロセスの中から選びます）。Aが実行されます。タイムスライスの間に実行された後、pass値が100に更新されます。次にBが実行され、そのpass値が200に更新されます。最後にCが実行され、pass値が40に更新されます。この時点で、アルゴリズムは最小のpass値を持つCを選び、pass値を80に更新します（Cのストライドは40です）。次にCが再度実行され、120に更新されます。次にAが実行され、200に更新されます（これでBと同じになります）。次にCが2回実行され、pass値が160を経て200に更新されます。次の図を見て理解してみてください。
CFS
もう一つの公平な分配スケジューリングを見てみましょう。それはCompletely Fair Scheduler（CFS）の略です。
Linux 2.6以降では、このスケジューリング方式が導入されて使用されています。このスケジューリングの特徴は二つあります。
- 効率性
- 拡張性
基本的な演算
いくつかの変数を基準に演算を行います。
- virtual runtime：各プロセスがこれまでに実行された時間で、各プセスの実際の実行時間を累積した値です。
- sched_latency：この値と現在のプロセス数を割って実行time sliceを決定します。
- min_granularity（最小のタイムスライス値）：time sliceが最小に持つことができる値を決定します。time sliceがあまりに小さくなると、context switchingが頻繁に発生する可能性があるため、最小値を設定しています。
例えば、プロセス数が100で多く、計算したtime slice値が1秒でも、min_granularity値が6秒なら、sched_latencyの値を破ってでもmin_granularityを守ります。
プロセスの優先順位
プロセスの優先順位はniceという値を利用して付与します。niceが小さいほど不親切なプロセスで、大きいほど親切なプロセスです。この方式の利点は、nice値に関係なく差が一定であれば同じCPU比率を配分するという利点があります。詳しく書くと長くなるので、興味がある読者は以下の式を見て考えてみてください。
レッドブラックツリー
CFSの核心は効率性です。この効率性を保証するためには、どのプロセスを実行するかを迅速に決定することが非常に重要です。単純なリストを使用してプロセスを保存すると、探索するたびに非常に非効率的になります。そのためにレッドブラックツリーというデータ構造を使用します。実行中または実行可能なプロセスだけがこのツリーに保存されます。
レッドブラックツリーについては、この記事では詳しく扱いません。代わりにこのビデオを見てみてください。そうすれば、原理を直感的に理解できるでしょう。
眠りの森のプロセス
さて、眠りの森のプロセスたちに会いに行ってみましょう。これらのプロセスは、王子様（スケジューラー）のキスを待って目覚めるのを期待しています。
A、Bのプロセスがあるとしましょう。Aは10秒間眠っており、Bは常に実行中です。Aが目覚めると、AがCPUを独占し、Bが飢えた状態になるでしょう。これを防ぐために、Aが目覚めたときにAの仮想実行時間（virtual runtime）をそのまま使用するのではなく、現在のプロセスの中で最も少ない仮想実行時間に更新します。
これにより、Aに対してある程度のCPU割り当てを確保し、Bが飢えない程度にCPUを分配することができます。