シム ウク

シム ウク

物作り精神に憧れ、楽しんでプログラミングをしているSEエンジニア

OS(operating system)

2 minute read

OS system

プロセスとスレッドの違い

プロセス(Process)

プロセスとは、実行中のプログラムで、ディスクからメモリに読み込まれ、CPUの割り当てを受けられるものを指します。オペレーティングシステムからアドレス空間、ファイル、メモリなどを割り当てられ、これらを総称してプロセスと呼びます。具体的には、プロセスには、関数の引数、戻りアドレス、ローカル変数などの一時的なデータを含むプロセススタックと、グローバル変数を含むデータセクションが含まれます。さらに、プロセスには、プロセス実行中に動的に割り当てられるメモリであるヒープが含まれます。

プロセス制御ブロック(Process Control Block, PCB)

PCBは、特定のプロセスに関する重要な情報を保存しているオペレーティングシステムのデータ構造です。オペレーティングシステムは、プロセスを管理するために、プロセスの生成と同時に独自のPCBを作成します。プロセスはCPUを割り当てられて作業を処理している最中にも、プロセスの切り替えが発生すると、進行中の作業を保存してCPUを返却する必要があります。このとき、作業の進行状況をすべてPCBに保存することになります。そして再びCPUを割り当てられると、PCBに保存されていた内容を呼び出して、前回終了した時点から作業を再開します。

  • PCBに保存される情報
    • プロセス識別子(Process ID, PID)：プロセス識別番号
    • プロセスの状態：new、ready、running、waiting、terminatedなどの状態を保存
    • プログラムカウンタ：プロセスが次に実行する命令のアドレス
    • CPUレジスタ
    • CPUスケジューリング情報：プロセスの優先度、スケジュールキューに対するポインタなど
    • メモリ管理情報：ページテーブルやセグメントテーブルなどの情報を含む
    • 入出力状態情報：プロセスに割り当てられた入出力デバイスと開いているファイルのリスト
    • アカウンティング情報：使用されたCPU時間、時間制限、アカウント番号など

スレッド(Thread)

スレッドは、プロセスの実行単位と言えます。プロセス内で動作する複数の実行フローで、プロセス内のアドレス空間やリソースを共有することができます。スレッドは、スレッドID、プログラムカウンタ、レジスタセット、およびスタックから構成されます。同じプロセスに属する他のスレッドとコード、データセクション、および開いているファイルやシグナルなどのオペレーティングシステムのリソースを共有します。1つのプロセスを複数の実行単位に区別してリソースを共有し、リソースの生成と管理の重複を最小限に抑えてパフォーマンスを向上させることをマルチスレッディングと呼びます。この場合、各スレッドは独立した作業を行う必要があるため、それぞれ独自のスタックとPCレジスタ値を持っています。

スレッドごとにスタックを独立して割り当てる理由

スタックは、関数呼び出し時に渡される引数、戻るアドレス、および関数内で宣言される変数などを保存するために使用されるメモリスペースであるため、スタックメモリスペースが独立していることは、独立した関数呼び出しが可能であることを意味し、これは独立した実行フローが追加されることを意味します。したがって、スレッドの定義に従い、独立した実行フローを追加するための最小条件として、独立したスタックを割り当てます。

PC レジスタをスレッドごとに独立的に割り当てる理由

PC 値は、スレッドが命令をどこまで実行したかを示すために使用されます。スレッドは CPU を割り当てられて処理を行い、スケジューラによって再度プリエンプションされることがあります。そのため、命令が連続して実行されず、どこまで実行したかを覚えておく必要があります。したがって、PC レジスタを独立して割り当てる必要があります。

マルチスレッド

マルチスレッドの利点

プロセスを利用して同時に処理していた作業をスレッドで実装することで、メモリ空間とシステムリソースの消費が減少します。スレッド間の通信が必要な場合にも、別のリソースを利用するのではなく、グローバル変数の領域または動的に割り当てられた領域であるヒープ領域を利用してデータをやり取りすることができます。そのため、プロセス間通信に比べてスレッド間通信の方法がはるかに簡単です。さらに、スレッドのコンテキストスイッチは、プロセスのコンテキストスイッチとは異なり、キャッシュメモリをクリアする必要がないため、より高速です。そのため、システムのスループットが向上し、リソース消費が減少し、プログラムの応答時間が短くなります。これらの利点のため、複数のプロセスで実行できる作業を1つのプロセスでスレッドに分けて実行することができるようになりました。

マルチスレッドの問題点

マルチプロセスベースでプログラムを作成する場合、プロセス間で共有するリソースがないため、同じリソースに同時にアクセスすることはありませんでしたが、マルチスレッドベースでプログラムを作成する場合は、この部分に注意する必要があります。異なるスレッドがデータとヒープ領域を共有するため、あるスレッドが他のスレッドで使用中の変数やデータ構造にアクセスして、間違った値を読み取ったり変更したりすることができます。

そのため、マルチスレッド環境では同期作業が必要です。同期を通じて、作業の処理順序を制御し、共有リソースへのアクセスを制御することができます。しかし、これにより、ボトルネック現象が発生し、性能が低下する可能性が高くなります。そのため、過剰なロックによるボトルネック現象を減らす必要があります。

マルチスレッド vs マルチプロセス

マルチスレッドはマルチプロセスよりもメモリスペースを少なく占有し、コンテキストスイッチが速いという利点がありますが、エラーによって1つのスレッドが終了すると全体のスレッドが終了する可能性があるという点と同期問題を抱えています。一方、マルチプロセス方式は1つのプロセスが死んでも他のプロセスに影響を与えずに正常に実行されるという利点がありますが、マルチスレッドよりも多くのメモリスペースとCPU時間を占有するという欠点が存在します。これら2つは同時に複数のタスクを実行する点で同じですが、適用すべきシステムによって適合/不適合が区別されます。したがって、対象システムの特性に合わせて適切な動作方式を選択して適用する必要があります。

スケジューラ

プロセスをスケジューリングするためのキューには、3つの種類があります。

  • ジョブキュー：現在システム内にあるすべてのプロセスのセット
  • レディキュー：現在メモリ内にあり、CPUを占有して実行を待っているプロセスのセット
  • デバイスキュー：デバイスI/O操作を待っているプロセスのセット

プロセスをキューに入れ、取り出すためのスケジューラには、大きく 3つの種類 があります。

長期スケジューラ (Long-term scheduler or job scheduler)

メモリが限られているにもかかわらず、多数のプロセスが一度にメモリに乗ると、大容量メモリ（通常はディスク）に一時的に保存されます。このプールに保存されているプロセスのうち、どのプロセスにメモリを割り当ててready queueに送るかを決定する役割を担います。

  • メモリとディスクの間のスケジューリングを担当します。
  • プロセスにメモリ（およびその他のリソース）を割り当てます（admit）。
  • degree of Multiprogrammingを制御します（実行中のプロセスの数を制御します）。
  • プロセスの状態 new -> ready（メモリに格納）

cf) メモリにプログラムをたくさん乗せすぎても、あまりに少なくても、性能は良くないです。なお、タイムシェアリングシステムでは、長期スケジューラは存在しません。すぐにメモリに乗ってready状態になります。

短期スケジューラ(Short-term scheduler or CPU scheduler)

  • CPUとメモリー間のスケジューリングを担当する。
  • Ready Queueに存在するプロセスの中からどのプロセスをrunningさせるかを決定する。
  • プロセスにCPUを割り当てる(scheduler dispatch)
  • プロセスの状態 ready -> running -> waiting -> ready

中期スケジューラ(Medium-term scheduler or Swapper)

  • 余裕のある空間を確保するために、プロセスをまるごとメモリからディスクに移動(swapping)する。
  • プロセスからmemoryを解放(deallocate)
  • degree of Multiprogrammingを制御
  • 現在のシステムでメモリに同時に多くのプログラムがロードされすぎないように調整するスケジューラ。
  • プロセスの状態 ready -> suspended

プロセス状態 - suspended

Suspended(stopped) : 外部的な理由でプロセスの実行が停止され、メモリから降ろされた状態を意味する。プロセス全体がディスクにswap outされる。blocked状態は他のI/O処理を待っている状態であるため、自らready stateに戻ることができるが、この状態は外部的な理由で中断されたため、自ら戻ることはできない

CPUスケジューラー

スケジューリングの対象は、Ready Queue にあるプロセスです。

FCFS(First Come First Served)

特徴

  • 先着順で処理を行う方式。つまり、最初に到着したものから順に処理します。
  • 非抜き取り(Non-Preemptive)スケジューリング 一度CPUを獲得したプロセスは、CPUバーストが完了するまでCPUを返却しません。割り当てられたCPUが返却されたときにのみスケジューリングが行われます。

問題点

  • 車列効果(convoy effect) 時間がかかるプロセスが先に到着し、効率を下げる現象が発生します。

SJF(Shortest - Job - First)

特徴

  • 他のプロセスが先に到着しても、CPUバースト時間が短いプロセスに優先的に割り当てます。
  • 非抜き取り(Non-Preemptive)スケジューリング

問題点

  • 飢餓状態 効率性を追求することが最も重要ですが、あるプロセスが極端に差別されるべきではありません。このスケジューリングは、CPU使用時間が短いジョブを極端に優先します。したがって、使用時間が長いプロセスはほとんど永遠にCPUを割り当てられません。

SRTF(Shortest Remaining Time First)

特徴

  • 新しいプロセスが到着するたびに新しいスケジューリングが行われる。
  • プリエンプティブ(Preemptive)スケジューリング 現在実行中のプロセスの残りのCPUバースト時間よりも短いCPUバースト時間を持つ新しいプロセスが到着すると、CPUを奪われる。

問題点

  • スターベーション
  • 新しいプロセスが到着するたびにスケジューリングを再度行うため、CPUバースト時間を測定することができない。

優先度スケジューリング

特徴

  • 優先度が最も高いプロセスにCPUを割り当てるスケジューリング。優先度は整数で表され、小さい数字ほど優先度が高い。
  • 前半スケジューリング（Preemptive）方式 より高い優先度のプロセスが到着すると、実行中のプロセスを停止し、CPUを奪う。
  • 非前半スケジューリング（Non-Preemptive）方式 より高い優先度のプロセスが到着すると、Ready Queueの先頭に入れる。

問題点

  • 飢餓現象
  • 無期限ブロック（Indefinite blocking） 実行準備はできているが、CPUを使用できないプロセスをCPUが無期限に待機する状態

解決策

  • エージング どんなに優先度が低いプロセスでも、長く待っていると優先度を上げてあげよう。

Round Robin

特徴

  • 現代的なCPUスケジューリング方法
  • 各プロセスは同じサイズのタイムスライス（タイムクオンタム）を持つ
  • 割り当てられた時間が経過すると、プロセスはプリエンプションされ、再びready queueの末尾に移動して列に並ぶ
  • RRはCPU使用時間がランダムなプロセスが混在している場合に効率的である
  • RRが可能なのは、プロセスのコンテキストを保存できるためである

利点

  • Response timeが短くなる ready queueにn個のプロセスがあり、割り当て時間がq（タイムクオンタム）である場合、各プロセスはCPU時間の1 / nをq単位で取得する。つまり、どのプロセスも（n-1）q時間単位以上待たない。
  • プロセスが待つ時間がCPUを使用する時間に比例するようになる 公正なスケジューリングと言える。

注意点

設定したtime quantumが大きすぎるとFCFSと同じになります。また、小さすぎる場合はスケジューリングアルゴリズムの目的には理想的かもしれませんが、頻繁なコンテキストスイッチによりオーバーヘッドが発生します。したがって、適切なtime quantumを設定することが重要です。

同期と非同期の違い

比喩による簡単な説明

やらなければならないタスクが洗濯、食器洗い、掃除の3つだと仮定します。これらの仕事を同期的に処理する場合、洗濯をして、食器洗いをして、掃除をします。非同期的に処理する場合、洗濯会社に洗濯を頼み、食器洗い代行会社に食器洗いを頼み、掃除代行会社に掃除を頼みます。どれが最初に完了するかはわかりません。すべての作業が完了した代行会社から通知を受けたら、別の作業をすることができます。この場合、バックグラウンドスレッドでその作業を処理する場合の非同期を意味します。

Sync vs Async

一般的に、同期と非同期の違いは、メソッドを実行すると同時に期待される戻り値がある場合を 同期 と表現し、そうでない場合に 非同期 と表現します。同時というのは、実行されたときに値が返されるまで blocking されるということを意味します。非同期の場合は、blocking されずにイベントキューに入れたり、バックグラウンドスレッドにそのタスクを委任したりして、すぐに次のコードを実行するため、期待される値がすぐに返されるわけではありません。

プロセス同期化

Critical Section（臨界区間）

マルチスレッドにおいて、同時にアクセスする作業（共有する変数を使用したり、同じファイルを使用したりする）を実行するコード領域を臨界区間と呼びます。

Critical Section Problem（臨界区間問題）

プロセスが臨界区間を共有できるプロトコルを設計することです。

Requirements（解決するための基本条件）

  • 相互排除（Mutual Exclusion） プロセスP1が臨界区間で実行中である場合、他のプロセスは彼らが持つ臨界区間で実行されることはできません。
  • 進捗（Progress） 臨界区間で実行中のプロセスがいなく、別の動作がないプロセスのみが臨界区間への入場候補として参加できます。
  • 有界待ち（Bounded Waiting） P1が臨界区間への入場をリクエストしてから受け入れられるまで、他のプロセスが臨界区間に入る回数には制限がある必要があります。

解決策

Mutex Lock（ミューテックス・ロック）

  • 同時に共有リソースにアクセスすることを防ぐため、Critical Section に入るプロセスは Lock を取得し、Critical Section を抜ける際に Lock を解放することによって、同時にアクセスされないようにする。
制限
  • マルチプロセッサ環境では、時間的な効率性の面で適用できない。

セマフォ（Semaphores）

  • ソフトウェア上で Critical Section 問題を解決するための同期ツール
種類

OS は、Counting/Binary セマフォを区別する。

  • カウンティングセマフォ 使用可能な数を持つリソースに対するアクセス制御用に使用され、セマフォはその使用可能な リソースの数 で初期化される。リソースを使用すると、セマフォが減少し、解放するとセマフォが増加する。
  • バイナリセマフォ MUTEX とも呼ばれ、相互排除（Mutual Exclusion）の頭文字から作られた。その名の通り、0 と 1 の間の値しか取り得ず、複数のプロセス間の Critical Section 問題を解決するために使用される。

問題点

  • Busy Waiting(忙しい待ち) Spin lockと呼ばれるSemaphore初期バージョンでは、Critical Sectionに入る必要があるプロセスは入るコードを繰り返し実行する必要があり、CPU時間を浪費しました。これをBusy Waitingと呼び、特殊な状況でなければ効率的ではありません。通常、SemaphoreではCritical Sectionに入ろうとしたが失敗したプロセスをブロックし、Critical Sectionに空きができたときに再び起こす方法が使用されます。この場合、Busy Waitingによる時間の浪費問題は解決されます。

Deadlock(デッドロック)

  • セマフォがReady Queueを持ち、2つ以上のプロセスがCritical Section進入を無限に待機しており、Critical Sectionで実行されるプロセスは進入待機中のプロセスが実行されなければ出てこれない状況を指します。

モニタ

  • 高級言語の設計構造物として、開発者のコードを相互排他的にするように作られた抽象化されたデータ形式です。
  • 共有リソースにアクセスするためのキー取得とリソース使用後の解放をすべて処理します。（セマフォは直接キー解放と共有リソースへのアクセス処理が必要です。）

メモリ管理戦略

メモリ管理の背景

各々のプロセスは独立したメモリ空間を持っており、オペレーティングシステムまたは他のプロセスのメモリ空間にアクセスできない制限がかかっています。ただし、オペレーティングシステムのみがオペレーティングシステムメモリ領域とユーザメモリ領域へのアクセスに制限を受けません。

スワッピング(Swapping): メモリの管理に使用される技術。標準的なスワッピング方法では、ラウンドロビンなどのマルチプログラミング環境で、CPU割り当て時間が終了したプロセスのメモリを補助記憶装置(例えばハードディスク)に送り出し、他のプロセスのメモリを読み込むことができます。

このプロセスをスワップ(スワップする)と呼びます。主記憶装置(RAM)に読み込むプロセスをスワップイン(スワップイン)、補助記憶装置から送り出すプロセスをスワップアウトと呼びます。スワップには大きなディスク転送時間が必要なため、現在ではメモリスペースが不足した場合にスワッピングが開始されます。

フラグメンテーション(Fragmentation) : プロセスがメモリにロードされ、削除されると、プロセスが占めるメモリの間に使用できないほど小さなフリースペースが増えるため、これをフラグメンテーションと呼びます。フラグメンテーションには2つの種類があります。

| Process A | free | Process B | free | Process C | free | | ———– | —- | ———– | —- | ———– | —- |

  • 外部フラグメンテーション（External Fragmentation）: メモリ空間の一部が使用できなくなる現象。物理メモリ（RAM）の中に散在する、一つひとつは十分な容量がある自由な空き領域が、バラバラになって存在する場合に発生すると言える。
  • 内部フラグメンテーション（Internal Fragmentation）: プロセスが使用するメモリ空間に含まれる余白部分。例えば、メモリ分割の自由空間が10,000Bあり、Process Aが9,998B使用すると、2Bという差があり、この現象を内部フラグメンテーションと呼ぶ。

圧縮: 外部フラグメンテーションを解消するため、プロセスが使用する空間を一つの側に寄せ、自由領域を確保する手法であるが、作業効率は良くない。(上のメモリの状況が圧縮によって、下の図のように変わる効果がある)

| Process A | Process B | Process C | Process D | free | | ———– | ———– | ———– | ———– | —- |

ページング

プロセスが使用するメモリ空間が連続している必要があるという制約をなくすメモリ管理方法です。外部フラグメンテーションや圧縮処理を解決するために生まれた方法論で、物理メモリはフレームという固定サイズに分割され、論理メモリ(プロセスが占有する)はページと呼ばれる固定サイズのブロックに分割されます。(ページ置換アルゴリズムに含まれるページ)

ページング技術を使用することにより、論理メモリは物理メモリに保存される際、連続して保存する必要がなく、物理メモリの余ったフレームに適切に配置されるため、外部フラグメンテーションを解決する大きな利点があります。

1つのプロセスが使用する空間は、複数のページに分割されて管理されます(論理メモリ上)。個々のページは、順序に関係なく物理メモリ上のフレームにマッピングされて保存されると考えることができます。

  • 欠点：内部フラグメンテーション問題の比率が高くなります。例えば、ページサイズが1,024Bで、プロセスAが3,172Bのメモリを要求した場合、3つのページフレーム(1,024 * 3 = 3,072)でも100Bが余るため、合計4つのページフレームが必要になります。結論として、4番目のページフレームには、残りの924B(1,024 - 100)の余裕が生じ、内部フラグメンテーション問題が発生します。

セグメンテーション

ページングと同様に、論理メモリと物理メモリを同じサイズのブロックではなく、異なるサイズの論理的な単位であるセグメント(segment)に分割するメモリ管理方法です。ユーザーは2つのアドレスで指定します(セグメント番号+オフセット)。セグメントテーブルには、各セグメントのベース(セグメントの開始物理アドレス)とリミット(セグメントの長さ)が保存されます。

  • デメリット: 異なるサイズのセグメントがメモリに読み込まれ、削除されることが繰り返されると、自由なスペースが多数の小さな断片に分割され、使用できなくなることがある（外部フラグメンテーション）。

仮想メモリ

多重プログラミングを実現するには、多くのプロセスを同時にメモリに配置する必要があります。 仮想メモリは、プロセス全体をメモリに読み込まなくても実行できるようにする技術で、プログラムが物理メモリよりも大きくても実行できるという主な利点があります。

仮想メモリの開発背景

実行されるコードの全体を物理メモリに存在させる必要があったため、メモリ容量よりも大きなプログラムは実行できませんでした。また、複数のプログラムを同時にメモリに読み込むことには容量の限界やページ交換などのパフォーマンスの問題が発生しました。また、まれにしか使用されないコードが占めるメモリを確認できるため、全体のプログラムがメモリに常駐する必要はないことがわかります。

プログラムの一部だけをメモリに配置できれば…

  • 物理メモリのサイズに制約されなくなります。
  • より多くのプログラムを同時に実行できるようになります。これにより、レスポンスタイムは維持され、CPU利用率とスループットは向上します。
  • swapに必要な入出力が減少するため、プログラムが迅速に実行されます。

仮想メモリが行うこと

仮想メモリは、実際の物理メモリの概念とユーザーの論理メモリの概念を分離することにより、小さなメモリでもプログラマに大きな仮想アドレス空間を提供することができます。

仮想アドレス空間

  • 1つのプロセスがメモリに保存される論理的なイメージを実現するための仮想メモリ内で提供される領域です。仮想メモリが提供するプロセスの要求するメモリ空間により、現在直接必要でないメモリ空間は物理メモリにはロードされないため、物理メモリを節約することができます。
  • 例えば、あるプログラムが実行され、論理メモリに100KBが必要とされたとします。しかし、実行までに必要なメモリ空間(Heap領域、Stack領域、コード、データ)の合計が40KBである場合、実際の物理メモリには40KBだけがロードされ、残りの60KBは必要に応じて物理メモリに要求されると理解できます。

| Stack | free (60KB) | Heap | Data | Code | | ——- | ———– | —— | —— | —— |

プロセス間のページ共有

仮想メモリは…

  • システムライブラリが複数のプロセス間で共有されることができるようにする。各プロセスは共有ライブラリを自分の仮想アドレス空間に配置して使用するように見えるが、実際にはライブラリが格納されている物理メモリページはすべてのプロセスで共有されている。
  • プロセス間でメモリを共有できるようにし、プロセスは共有メモリを介して通信できる。これも、各プロセスが自分自身のアドレス空間のように認識するが、実際の物理メモリは共有されている。
  • fork()によるプロセスの生成時にページが共有されることが可能になる。

Demand Paging（要求ページング）

プログラムを実行開始するとき、プログラム全体をディスクから物理メモリに読み込むのではなく、初期に必要なものだけを読み込む戦略を要求ページングと呼び、仮想メモリシステムでよく使用されています。そして、仮想メモリは通常、ページで管理されます。要求ページングを使用する仮想メモリでは、実行中に必要になるページが読み込まれます。一度もアクセスされなかったページは物理メモリに読み込まれません。

プロセス内の個々のページは、ページャ(pager)によって管理されます。ページャは、プロセスの実行に実際に必要なページだけをメモリに読み込むことで、使用されないページを読み込む時間の浪費とメモリの浪費を減らすことができます。

Page fault trap(ページフォルトトラップ)

ページ置換

「要求ページング」によって、プログラムの全ての項目が物理メモリに読み込まれるわけではないため、プロセスの動作に必要なページを要求する過程で「page fault（ページフォルト）」が発生することがあります。この場合、必要なページを補助記憶装置から読み込むことになります。ただし、物理メモリがすべて使用中である場合は、ページ置換が行われる必要があります（または、オペレーティングシステムがプロセスを強制的に終了する方法があります）。

基本的な方法

物理メモリがすべて使用中である場合のメモリ置換の流れは次のようになります。

  1. 必要なページの場所をディスクから探します。
  2. 空のページフレームを探します。
    1. ページ置換アルゴリズムを使用して、犠牲になる（victim）ページを選択します。
    2. 犠牲になるページをディスクに書き込み、関連するページテーブルを変更します。
  3. 新しく空いたページテーブル内のフレームに新しいページを読み込み、フレームテーブルを変更します。
  4. ユーザープロセスを再起動します。

ページ置換アルゴリズム

FIFO ページ置換

最も単純なページ置換アルゴリズムで、FIFO（先入れ先出し）の流れを持っています。つまり、最初に物理メモリに入ったページがページ置換のタイミングで最初に出て行くということです。

  • 利点
    • 理解しやすく、プログラムも作りやすいです。
  • 欠点
    • 古いページが必要のない情報を含んでいないことがある（初期変数など）
    • 最初から活発に使用されるページを置き換えることで、ページ欠落率を高める副作用をもたらす可能性があります。
    • 「Beladyのパラドックス」：ページを保存できるページフレームの数を増やしても、むしろページ欠落がより多く発生するパラドックスが存在します。
最適ページ置換(Optimal Page Replacement)

「Beladyのパラドックス」を確認した後、最適な置換アルゴリズムに対する探究が進められ、すべてのアルゴリズムより低いページ欠落率を示し、Beladyのパラドックスが発生しません。このアルゴリズムの核心は、「将来的に最も長く使用されないページを見つけて置換する」ことです。主に比較研究の目的で使用されます。

  • 利点
    • アルゴリズムの中で最も低いページ欠落率を保証します。
  • 欠点
    • 実装の難しさがあります。すべてのプロセスのメモリ参照の計画を事前に把握する方法がないためです。
LRU ページ置換 (LRU Page Replacement)

LRU: Least-Recently-Used 最適アルゴリズムの近似アルゴリズムで、最も長く使用されていないページを選択して置き換えます。

  • 特徴
    • 一般的に FIFO アルゴリズム より優れており、 OPTアルゴリズム よりはそうでもないように見えます。
LFU ページ置換 (LFU Page Replacement)

LFU: Least Frequently Used 参照回数が最も少ないページを置換する方法です。活発に使用されるページは参照回数が増えるという仮定に基づいて作成されたアルゴリズムです。

  • 特徴
    • あるプロセスが特定のページを集中的に使用していたが、別の機能を使用すると使用しなくなっても、引き続きメモリにとどまり、初期の仮定に反する時点が発生する可能性があります。
    • 最適 (OPT) ページ置換を適切に近似できないため、あまり使用されません。
MFU ページ置換 (MFU Page Replacement)

MFU: Most Frequently Used 参照回数が最も少ないページが最近メモリにロードされ、今後も使用されるという仮定に基づいています。

  • 特徴
    • 最適 (OPT) ページ置換を適切に近似できないため、あまり使用されません。

キャッシュの局所性

キャッシュの局所性の原理

キャッシュメモリは、高速なデバイスと低速なデバイスの間のボトルネック現象を減らすための汎用メモリです。これを実現するためには、CPUがどのようなデータを必要とするかをある程度予測できる必要があります。キャッシュの性能は、小さな容量のキャッシュメモリにCPUが後で参照することができる有用な情報がどの程度含まれているかによって左右されるためです。

この場合、 ヒット率（Hit rate）を最大化するために、データの 局所性（Locality）の原理を使用します。局所性の前提条件として、プログラムがすべてのコードやデータを均等にアクセスしないという特性が基本になります。つまり、 Localityとは、記憶装置内の情報を均一にアクセスするのではなく、ある一定の時点で特定の部分に集中的に参照する特性であるということです。

このデータの局所性は、主に時間的局所性（Temporal Locality）と空間的局所性（Spatial Locality）に分けられます。

  • 時間的局所性：最近参照されたアドレスの内容は、すぐに再度参照される傾向がある特性。
  • 空間的局所性：ほとんどの実際のプログラムが参照されたアドレスと隣接するアドレスの内容が再度参照される傾向がある特性。

キャッシュライン

述べたように、キャッシュはプロセッサの近くに位置しながら頻繁に使用されるデータを保管する場所です。しかし、目的のデータがどこに保存されているか分からない場合、すべてのデータを探す必要があり、時間がかかってしまいます。つまり、キャッシュに目的のデータが保存されている場合、すぐにアクセスして出力できる必要があるため、キャッシュが意味を持つことになります。

したがって、キャッシュにデータを保存する際には、特定のデータ構造を使用して「束」として保存されます。これを キャッシュライン と呼びます。プロセスは、さまざまなアドレスにあるデータを使用するため、頻繁に使用されるデータのアドレスも散在しています。したがって、キャッシュに保存するデータには、データのメモリアドレスなどを記録したタグを付ける必要があります。これらのタグの束をキャッシュラインと呼び、メモリから取得するときもキャッシュラインを基準に取得します。代表的な種類は、次の3つがあります。

  1. Full Associative
  2. Set Associative
  3. Direct Map

Comments

You May Also Enjoy

less than 1 minute read