マルチプロセッサ·スキャズリング

このテキストは、運営している韓国のブログを日本語に翻訳したものです。

韓国のブログ：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/

マルチプロセッサ

前の記事では、1つのCPUが様々な作業をどのように処理するかを中心にスケジューリングについて理解しました。単一のCPUは一度に一つの作業しか実行できないため、その特性に合わせて様々なスケジューリング技術を紹介しました。しかし、マルチプロセッサシステムでは話は異なります。複数のCPUが同時にさまざまな作業を処理できるため、単一CPUシステムで使用されるスケジューリング方法はここでは適していない可能性があります。

並列処理とスレッド

マルチプロセッサシステムでの重要な概念は**「並列処理」**です。並列処理とは、複数のCPUが同時に異なる作業を行うことで、全体のシステムの処理能力を向上させます。このような並列処理を可能にするのが「スレッド」です。スレッドについては、後の記事で詳しく取り扱います。

マルチプロセッサの問題点

マルチプロセッサシステムでは、キャッシュの整合性問題は非常に重要なテーマです。このシステムでは、すべてのCPUが共有メモリを共有し、各CPUは自分のキャッシュを持っています。

問題は、複数のCPUが同時に同じメモリデータにアクセスしようとするときに発生します。たとえば、CPU1がデータAを修正して自分のキャッシュに保存したとしましょう。しかし、CPU2も同じデータAにアクセスしようとすると、CPU2のキャッシュにはまだ古いデータが残っている可能性があります。このようになると、データの整合性が壊れます。

この問題を解決するための一つの方法は、キャッシュ整合性プロトコルです。ここには、二つの主なアプローチがあります：

  1. バススヌーピング方式：この方式では、すべてのキャッシュがバスを通じて他のキャッシュの動作を監視（スヌーピング）します。例えば、CPU1がデータAを変更すると、その変更がバスを通じて伝えられます。他のCPUのキャッシュはこの変更を検知し、自分のキャッシュにある該当するデータAを無効化したり更新します。この方式はキャッシュ間の整合性を保持するのを助けます。
  2. ロック（Lock）メカニズム：CPUがメモリの特定の部分にアクセスするとき、その部分にロックをかけて他のCPUが同時にアクセスするのを防ぎます。この方法はデータの整合性を保証しますが、システムの並列処理能力を低下させる可能性があります。特にコア数が多ければ多いほど、パフォーマンスの低下幅が大きくなります。

これらの方法は、マルチプロセッサシステムでキャッシュの整合性を保ち、データの整合性を保証するために使用されます。

（ロックが必要な例のコードをJavaで使用する）

キャッシュ親和性

マルチプロセッサスケジューリングを考慮する際には、キャッシュ親和性も考慮しなければなりません。キャッシュ親和性（Cache Affinity）とは、プロセスまたはスレッドが特定のCPUと親密であることを意味します。親密であるとは具体的にどういう意味でしょうか？

これを理解するためには、CPUとキャッシュの動作方式を理解する必要があります。CPUキャッシュは、頻繁に使用されるデータと命令を迅速にアクセスできるように保存する小さなメモリです。

プロセスがCPUで実行されるとき、必要なデータがキャッシュにロードされます。もし同じプロセスが後に再び実行され、同じCPUで実行されるなら、既にキャッシュにロードされているデータを再利用できるため、パフォーマンスが向上します。これが親密であるという意味です。

逆に、プロセスやスレッドが他のCPUに移動すると、新しいCPUのキャッシュに必要なデータと命令を再度ロードする必要があります。これによりキャッシュミス（Cache Miss）が発生し、結果的にメモリアクセス時間が増加し、パフォーマンスが低下します。

キャッシュ親和性が重要な理由

  1. パフォーマンス向上：同じCPUで連続して実行されると、キャッシュヒット（Cache Hit）の確率が高まり、処理速度が速くなります。
  2. データアクセス時間の短縮：すでにデータがキャッシュにロードされていれば、メモリからデータを取得する時間が短縮されます。
  3. リソース利用の最大化：CPUキャッシュは限られたリソースです。自然を大切にするように、CPUのリソースも大切に使わなければなりません。

シングルキューマルチプロセッサスケジューリング

SQMSは、複数のマルチプロセッサが単一の作業キューからタスクを取り出し、各プロセッサに分配する作業です。

問題点

  • コア数が多いほど、ロックがかかったときのパフォーマンス低下が深刻になる
    • キューが停止すると、CPUに仕事を分配できず、CPU数に比例してリソースの無駄遣いが発生する
  • キャッシュ親和性が保たれにくい
    • 複数のスケジューラがCPUで均等に実行されるため、逆に親和性が高いプロセスが重なる可能性がある

キャッシュ親和性を高めるために、同じプロセッサに同じ作業が行くように実装します。

もし実装に成功すれば、次の画像のように分配されますが、ここでEを見ると全てのプロセッサを移動する点が見られます。これは、Eについての情報を各プロセッサのキャッシュに適応させようとする試みであり、各プロセッサが順番に回って適応させる過程を経ることができます。しかし、このような方法は実装が複雑になる可能性があります。

マルチキューマルチプロセッサスケジューリング

これは、CPUの数だけタスクキューを設けるスケジューリング方法を指します。各キューは、これまで学んだFIFO、SJFなどの各種スケジューリングを適用することができますが、今回は便宜上、すべてのキューがラウンドロビンポリシーを使用するとします。図を見ると、Q0のプロセスがCPU0でスケジューリングされていることがわかります。このようにすると、スケーラビリティの利点が生まれます。従来の単一キューでは、CPUが増えるとロックによる無駄なコストが増えましたが、マルチキューでは、CPUの数に応じてキューを増やすと、このような問題は発生しません。

しかし、マルチキューにも問題が存在します。問題は、ワークロードの不均衡が発生するときです。

不均衡が発生する場合のケース1

不均衡が発生する場合のケース2

不均衡を防ぐ方法

不均衡を防ぐ方法の一つは、キュー内のプロセスを移動（Migration）させることです。移動させることでワークロードのバランスを達成します。

図を見ると、最初はAがCPU 0に一人でいて、BとDがCPU 1で交互に実行されています。数回のタイムスライスの後、BがCPU 0に移動し、Aと競合します。その間、DはCPU 1で数回のタイムスライスを単独で実行します。その結果、ワークロードのバランスが取れます。

まとめ

マルチプロセッサスケジューリングに関する要約情報を表形式でまとめました：

特性 シングルキュー方式 マルチキュー方式
実装の難易度 簡単 難しい
ワークロードのバランス 容易 難しい
スケーラビリティ 良くない 良い
キャッシュ親和性 良くない 良い
  • シングルキュー方式：実装が簡単でワークロードのバランスが容易ですが、スケーラビリティとキャッシュ親和性は良くありません。
  • マルチキュー方式：スケーラビリティとキャッシュ親和性は良いですが、実装の難易度が高く、ワークロードのバランスを取るのが難しいです。