大企業面接のための iAsk の「スケジュールアルゴリズム」、写真 20 枚が当たる

[[341122]]

この記事はWeChatの公開アカウント「Xiao Lin Coding」から転載したもので、著者はXiao Lin Codingです。この記事を転載する場合は、Xiaolin Codingの公式アカウントまでご連絡ください。

オリジナルURL: https://mp.weixin.qq.com/s/JWj6_BF9Xc84kQcyx6Nf_g

序文

最近、私はこっそりと様々な技術系グループに潜んでいます。秋の採用が近づいていることもあり、大企業の面接体験談をシェアしている友人をたくさん見かけます。

すると、OSのテストには知識のポイントがかなり多く、大企業では基礎知識について質問されることが分かりました。その中で、オペレーティングシステムの「スケジューリングアルゴリズム」もよく調べられています。

そこで、オペレーティングシステムの3大スケジューリング機構である「プロセススケジューリング/ページ置換/ディスクスケジューリングアルゴリズム」についてまとめてみましたので、ぜひご覧ください。秋の採用では、皆さんが夢の内定を得られることを願っています。

文章

プロセススケジューリングアルゴリズム

プロセススケジューリングアルゴリズムは CPU スケジューリングアルゴリズムとも呼ばれ、プロセスは CPU によってスケジュールされます。

CPU がアイドル状態のとき、オペレーティングシステムはメモリ内の「準備完了状態」のプロセスを選択し、それに CPU を割り当てます。

CPU スケジューリングはいつ行われるのでしょうか? 通常、次のような状況があります。

プロセスが実行状態から待機状態に移行するとき。
プロセスが実行状態から準備完了状態に移行するとき。
プロセスが待機状態から準備完了状態に移行するとき。
プロセスが実行状態から終了状態に移行するとき。

状況 1 と 4 で発生するスケジューリングは「非プリエンプティブスケジューリング」と呼ばれ、状況 2 と 3 で発生するスケジューリングは「プリエンプティブスケジューリング」と呼ばれます。

非プリエンプティブとは、プロセスの実行中、プロセスが完了するかイベントによってブロックされるまで実行が継続され、その後 CPU が他のプロセスに渡されることを意味します。

プリエンプティブスケジューリングとは、その名前が示すように、プロセスの実行中に中断して CPU を他のプロセスに譲ることができることを意味します。一般に、プリエンプションには、タイムスライス原則、優先順位原則、およびショートジョブ優先順位原則という 3 つの原則があります。

3 番目のケースでも CPU スケジューリングが行われるのはなぜか、不思議に思われるかもしれません。待機状態のプロセスがあり、その優先度が比較的高いとします。プロセスが待機しているイベントが発生すると、準備完了状態に切り替わります。準備完了状態に切り替わると、スケジューリングアルゴリズムが優先度に基づいてスケジュールされている場合、実行中のプロセスを直ちにプリエンプトするため、この時点で CPU スケジューリングが行われます。

2 番目の状態は通常、タイムスライスの有効期限が切れたときです。タイムスライスの有効期限が切れると、割り込みが発生し、実行中のプロセスがプリエンプトされて CPU が占有されるためです。

スケジューリングアルゴリズムは待機時間 (プロセスがスケジューリングのために準備完了キューで待機する合計時間) に影響しますが、プロセスが実際に CPU を使用する時間と I/O 時間には影響しません。

次に、一般的なスケジューリングアルゴリズムについて説明します。

先着順スケジューリングアルゴリズム
最短ジョブ優先スケジューリングアルゴリズム
高応答率優先スケジューリングアルゴリズム
タイムスライスラウンドロビンスケジューリングアルゴリズム
最高優先度のスケジューリングアルゴリズム
マルチレベルフィードバックキュースケジューリングアルゴリズム

先着順スケジューリングアルゴリズム

最も単純なスケジューリングアルゴリズムは、非プリエンプティブな First Come First Serve (FCFS) アルゴリズムです。

FCFS スケジューリングアルゴリズム

名前が示すように、先着順です。毎回、キューに入る最初のプロセスが準備完了キューから選択され、プロセスが終了するかブロックされるまで実行され、その後、キューから最初のプロセスが選択されて実行されます。

これは公平に思えますが、長いジョブが最初に実行されると、後続の短いジョブは長時間待機する必要があり、短いジョブには不利になります。

FCFS は長時間のジョブに適しており、CPU を集中的に使用するジョブを実行するシステムには適していますが、I/O を集中的に使用するジョブを実行するシステムには適していません。

最短ジョブ優先スケジューリングアルゴリズム

Shortest Job First (SJF) スケジューリングアルゴリズムは、その名前が示すように、実行時間が最も短いプロセスを優先し、システムのスループットの向上に役立ちます。

SJF スケジューリングアルゴリズム

これは明らかに長期的な作業には役立たず、簡単に極端な現象につながる可能性があります。

たとえば、長いジョブが準備完了キューで実行を待機していて、準備完了キューに短いジョブが多数ある場合、長いジョブは継続的に押し戻され、ターンアラウンドタイムが長くなり、長いジョブは長時間実行されません。

高応答率優先スケジューリングアルゴリズム

従来の「先着順スケジューリングアルゴリズム」と「最短ジョブ優先スケジューリングアルゴリズム」では、短いジョブと長いジョブのバランスが取れていません。

次に、Highest Response Ratio Next (HRRN) スケジューリングアルゴリズムは、主に短いジョブと長いジョブのバランスをとります。

プロセスがスケジュールされるたびに、まず「応答率優先度」が計算され、「応答率優先度」が最も高いプロセスが実行されます。「応答率優先度」の計算式は次のとおりです。

上記の式から、次のことがわかります。

2 つのプロセスの「待機時間」が同じ場合、「必要なサービス時間」が短いほど、「応答率」が高くなるため、ジョブが短いプロセスが実行対象として選択される可能性が高くなります。
2 つのプロセスの「必要なサービス時間」が同じ場合、「待機時間」が長いほど、「応答率」が高くなります。これは、待機時間が長くなるにつれてプロセスの応答率が向上するため、長いジョブプロセスを考慮した値です。待機時間が十分に長い場合、応答率を非常に高いレベルまで上げることができ、実行の機会が得られます。

タイムスライスラウンドロビンスケジューリングアルゴリズム

最も古く、最も単純で、最も公平かつ最も広く使用されているアルゴリズムは、ラウンドロビン (RR) スケジューリングアルゴリズムです。

RR スケジューリングアルゴリズム

各プロセスには、タイムスライス (Quantum) と呼ばれる期間が割り当てられます。これは、その期間中にプロセスを実行できることを意味します。

タイムスライスが使い果たされてもプロセスがまだ実行中の場合、プロセスは CPU から解放され、CPU は別のプロセスに割り当てられます。
プロセスがブロックされるか、タイムスライスが終了する前に終了した場合、CPU は直ちに切り替えられます。

さらに、タイムスライスの長さも重要なポイントです。

タイムスライスが短すぎると、プロセスコンテキストの切り替えが頻繁に発生し、CPU 効率が低下します。
設定値が長すぎると、短いジョブプロセスの応答時間が長くなる可能性があります。

通常、タイムスライスを 20ms ～ 50ms に設定すると、妥当な妥協値になります。

最高優先度のスケジューリングアルゴリズム

以前の「タイムスライスローテーションアルゴリズム」では、すべてのプロセスが同等に重要であり、特定のプロセスが優遇されることはなく、すべてのプロセスの実行時間は同じであると想定されていました。

しかし、マルチユーザーコンピュータシステムでは、異なる考え方が採用されています。マルチユーザーコンピュータシステムでは、スケジューリングに優先順位が付けられることを期待しています。つまり、スケジューラが実行可能なキューから最も優先度の高いプロセスを選択して実行できることを期待しています。これは、最高優先度優先 (HPF) スケジューリングアルゴリズムと呼ばれます。

プロセスの優先度は、静的または動的のいずれかに分類できます。

静的優先度: プロセスが作成されるときに優先度が決定され、実行時間全体にわたって優先度は変更されません。
動的優先度: プロセスの動的な変化に応じて優先度を調整します。たとえば、プロセスの実行時間が長くなった場合は、優先度を下げます。プロセスの待機時間 (準備完了キューの待機時間) が長くなった場合は、優先度を上げます。つまり、待機中のプロセスの優先度を時間の経過とともに上げます。

このアルゴリズムには、高優先度を処理するための非プリエンプティブとプリエンプティブの 2 つの方法もあります。

非プリエンプティブ: 優先度の高いプロセスが準備キューに表示された場合は、優先度の高いプロセスが選択される前に、現在のプロセスが完了するまで実行されます。
プリエンプティブ: 優先度の高いプロセスが準備完了キューに現れると、現在のプロセスは中断され、優先度の高いプロセスの実行がスケジュールされます。

ただし、優先度の低いプロセスが実行されない可能性があるという欠点がまだあります。

マルチレベルフィードバックキュースケジューリングアルゴリズム

マルチレベルフィードバックキュースケジューリングアルゴリズムは、「タイムスライスラウンドロビンアルゴリズム」と「最高優先度アルゴリズム」を組み合わせて開発したものです。

名前が示す通り:

「マルチレベル」とは、複数のキューが存在し、各キューの優先度は高から低までの範囲であることを意味します。同時に、優先度が高いほど、タイムスライスは短くなります。
「フィードバック」とは、新しいプロセスが高優先度キューに参加した場合、現在実行中のプロセスが直ちに停止され、代わりに高優先度キューが実行されることを意味します。

マルチレベルフィードバックキュー

どのように動作するか見てみましょう:

複数のキューが設定され、各キューには異なる優先度が与えられます。各キューの優先度は高いものから低いものの順になっており、優先度が高いほどタイムスライスは短くなります。
新しいプロセスは第 1 レベルのキューの最後尾に配置され、先着順にスケジュールされるのを待機します。第 1 レベルのキューで指定されたタイムスライスが完了していない場合は、第 2 レベルのキューの最後に転送され、完了するまでこれが繰り返されます。
優先度の高いキューが空の場合、優先度の低いキューのプロセスが実行されるようにスケジュールされます。プロセスの実行中に新しいプロセスがより高い優先度のキューに入ると、現在実行中のプロセスは停止され、元のキューの末尾に移動され、その後、より高い優先度のプロセスの実行が許可されます。

短いジョブは第 1 レベルのキューで迅速に処理できることがわかります。長いジョブの場合、第 1 レベルのキューで完全に処理できない場合は、次のキューに移動して実行を待機できます。待機時間は長くなりますが、実行時間も長くなります。したがって、このアルゴリズムは長いジョブと短いジョブを適切に考慮し、応答時間が良好になります。

メモリページ置換アルゴリズム

メモリページ置換アルゴリズムを理解する前に、ページフォールト例外 (ページフォールト割り込み) について説明する必要があります。

CPU がアクセスしたページが物理メモリ内にない場合、ページフォールト割り込みが生成され、オペレーティングシステムにフォールトしたページを物理メモリにロードするように要求します。一般的な割り込みとの主な違いは次のとおりです。

ページフォルト割り込みは命令実行中に割り込み信号を生成して処理しますが、一般割り込みは命令実行後に割り込み信号をチェックして処理します。
ページフォルト割り込みは命令の先頭に戻り、「命令」を再実行しますが、一般的な割り込みは命令の「次の命令」に戻って実行します。

下図のように、ページフォルト割り込みの処理フローを見てみましょう。

ページフォルト割り込み処理フロー

CPU で Load M 命令にアクセスすると、CPU は M に対応するページテーブルエントリを検索します。
ページテーブルエントリのステータスビットが「有効」の場合、CPU は物理メモリに直接アクセスできます。ステータスビットが「無効」の場合、CPU はページフォールト割り込み要求を送信します。
オペレーティングシステムはページフォールト割り込みを受信すると、ページフォールト割り込みハンドラーを実行し、まずディスク上のページの位置を検索します。
ディスク上で対応するページを見つけたら、そのページを物理メモリにスワップする必要があります。ただし、スワップインする前に、物理メモリ内に空きページが見つかる必要があります。空きページが見つかると、そのページは物理メモリにスワップされます。
ページがディスクから物理メモリにスワップされた後、ページテーブルエントリのステータスビットが「有効」に変更されます。
最後に、CPU はページフォールト例外の原因となった命令を再実行します。

上記のプロセスでは、ステップ 4 は物理メモリ内に空きページが見つかるケースです。見つからない場合はどうなるでしょうか?

空きページが見つからない場合は、メモリがいっぱいであることを意味します。このとき、物理ページを選択するために「ページ置換アルゴリズム」が必要です。物理ページが変更されている場合（ダーティページ）、ディスクにスワップアウトされ、スワップアウトされるページテーブルエントリのステータスが「無効」に変更され、最終的にアクセス中のページがこの物理ページにロードされます。

ここで言及する価値があるのは、ページテーブルエントリには通常、次のフィールドがあるということです。

その中で：

ステータスビット: プログラムがページにアクセスするときに参照するために、ページが有効かどうか、つまり物理メモリ内にあるかどうかを示すために使用されます。
アクセスフィールド: ページ置換アルゴリズムがページを選択するときに参照するために、一定期間内にページがアクセスされた回数を記録するために使用されます。
変更ビット: ページがメモリにロードされた後に変更されたかどうかを示します。メモリ内の各ページはディスク上にコピーを保持しているため、変更されていない場合は、ページを置き換えるときにページをディスクに書き戻す必要がなく、システムのオーバーヘッドが削減されます。変更されている場合は、ページがディスクに書き直され、常に最新のコピーがディスク上に保持されます。
ハードディスクアドレス: ハードディスク上のページのアドレス (通常は物理ブロック番号) を示すために使用され、ページを呼び出すときに使用されます。

ここでは仮想メモリ管理のプロセス全体を整理しました。下の図から確認できます。

仮想メモリプロセス

したがって、ページ置換アルゴリズムの機能は、ページフォールト例外が発生し、新しいページを呼び出す必要があるがメモリがいっぱいの場合に、置換する物理ページを選択することです。つまり、ディスクにスワップアウトする物理ページを選択し、アクセスする必要があるページを物理ページにスワップします。

アルゴリズムの目的は、ページスワップの数を可能な限り減らすことです。一般的なページ置換アルゴリズムは次のとおりです。

最適ページ置換アルゴリズム (OPT)
先入れ先出し置換アルゴリズム (FIFO)
最も最近使われていない（LRU）置換アルゴリズム
クロックページ置換アルゴリズム（ロック）
最も使用頻度の低い代替品 (LFU)
最適なページ置換アルゴリズム

最適なページ置換アルゴリズム

基本的な考え方は、最も長い間アクセスされないページを「将来」に置き換えることです。

したがって、アルゴリズムの実装では、メモリ内の各論理ページの「次の」アクセス時間を計算し、比較して、将来最も長い時間アクセスされないページを選択する必要があります。

たとえば、最初に 3 つの空き物理ページがあり、その後に要求されたページシーケンスがある場合、その置換プロセスは次のようになります。

最適なページ置換アルゴリズム

この要求されたページシーケンスでは、ページフォールトが 7 回発生し (3 つの空きページがスワップインされ、4 つの最適ページが置き換えられました)、ページの置換が 4 回発生しました。

これは理想的ですが、プログラムは動的にページにアクセスし、「次の」アクセスまでの各ページの待機時間を予測できないため、実際のシステムでは実装できません。

したがって、最適なページ置換アルゴリズムの役割は、アルゴリズムの効率を測定することです。アルゴリズムの効率がこのアルゴリズムの効率に近いほど、アルゴリズムの効率が高くなります。

FIFO置換アルゴリズム

ページへの次のアクセスまでの待ち時間を予測することはできないため、メモリ内に長時間保存されているページを置き換えることを選択できます。これが、「先入れ先出し置換」アルゴリズムの考え方です。

前回のリクエストのページシーケンスを引き続き例にとり、先入れ先出し置換アルゴリズムが使用されていると仮定すると、プロセスは次のようになります。

FIFO置換アルゴリズム

この要求されたページシーケンスでは、ページフォールトが 10 回、ページ置換が 7 回発生しました。最適なページ置換アルゴリズムと比較すると、パフォーマンスは大幅に低下しています。

最も最近使用されていない置換アルゴリズム

LRU 置換アルゴリズムの基本的な考え方は、ページフォールトが発生したときに、最も長い時間アクセスされていないページが置換対象として選択されるというものです。つまり、このアルゴリズムでは、長期間使用されていないページは、将来も長期間使用されないままになる可能性が高いと想定しています。

このアルゴリズムは、最適置換アルゴリズムに似ています。最適置換アルゴリズムは、「将来の」使用状況に基づいて削除するページを推測しますが、LRU は、「過去の」使用状況に基づいて削除するページを推測します。

前回要求されたページシーケンスを例に挙げてみましょう。最も最近使用されていない置換アルゴリズムが使用されていると仮定すると、プロセスは次のようになります。

最も最近使用されていない置換アルゴリズム

このリクエストのページシーケンスでは、ページフォールトが 9 回発生し、ページ置換が 6 回発生しました。先入れ先出し置換アルゴリズムと比較すると、パフォーマンスがわずかに向上しています。

LRU は理論的には可能ですが、非常に高価です。 LRU を完全に実装するには、メモリ内のすべてのページのリンクリストを維持し、最も最近使用されたページをリストの先頭に、最も最近使用されなかったページをリストの末尾に配置する必要があります。

難しいのは、メモリにアクセスするたびに「リンクリスト全体」を更新する必要があることです。リンクリスト内のページを検索し、それを削除して、リストの先頭に移動する操作は非常に時間がかかります。

したがって、LRU は見た目は良いものの、オーバーヘッドが大きいため、実際のアプリケーションではほとんど使用されません。

時計ページ置換アルゴリズム

順列の数を最適化でき、実装が簡単なアルゴリズムはありますか?

クロックページ置換アルゴリズムは、両方を実現できます。これは LRU に似ており、FIFO を改良したものです。

このアルゴリズムの考え方は、すべてのページを時計の文字盤に似た「循環リンクリスト」に保存し、針が最も古いページを指すようにすることです。

ページフォールトが発生すると、アルゴリズムはまずポインターが指すページをチェックします。

アクセスビットが 0 の場合、ページは削除され、新しいページがこの位置に挿入され、ポインターが 1 つ前方に移動します。
アクセスビットが 1 の場合、アクセスビットをクリアしてポインターを 1 つ前方に移動し、アクセスビットが 0 のページが見つかるまでこのプロセスを繰り返します。

時計ページ置換アルゴリズムがどのように機能するかを図に描きました。以下をご覧ください。

時計ページ置換アルゴリズム

このアルゴリズムの仕組みを理解すると、なぜクロックアルゴリズムと呼ばれるのかがわかります。

最も使用頻度の低いアルゴリズム

最も頻繁に使用されない (LFU) アルゴリズム。名前はやんちゃに聞こえますが、このアルゴリズムが一般的に使用されていないという意味ではなく、ページフォールトが発生すると、「アクセス回数」が最も少ないページが選択され、排除されるという意味です。

実装方法は、各ページに「訪問カウンター」を設定することです。ページが訪問されるたびに、ページのアクセスカウンターが 1 ずつ増加します。ページフォールトが発生すると、カウンター値が最も小さいページが削除されます。

一見シンプルに見え、各ページにカウンターを追加することで実装できますが、OS に実装する場合は効率やハードウェアコストを考慮する必要があります。

これを実現するには、比較的高いハードウェアコストがかかるカウンターを追加する必要があります。さらに、このカウンターを使用して、どのページの訪問数が最も少ないかを調べ、リンクリスト自体を検索する必要がある場合、リンクリストが非常に長いと、非常に時間がかかり、非効率的になります。

しかし、まだ問題が残っています。LFU アルゴリズムは頻度の問題のみを考慮しており、時間の問題は考慮していません。たとえば、一部のページは過去に頻繁にアクセスされていましたが、現在はアクセスされていません。現在頻繁にアクセスされているページは、これらのページほど頻繁にアクセスされていません。ページフォールトが発生すると、現在頻繁にアクセスされているが、あまり頻繁にアクセスされていないページが誤って破損する可能性があります。

この問題には解決策があります。定期的に訪問回数を減らすことです。例えば、時間中断が発生したら、過去に訪問したページの訪問回数を2で割ります。つまり、時間が経つにつれて、過去の訪問回数が多かったページが徐々に減っていくので、置き換えられる確率が高くなるのと同等です。

ディスクスケジューリングアルゴリズム

以下に示すように、ディスク構造を見てみましょう。

ディスク構造

一般的な機械式ディスクは、上の写真の左側のようなものです。真ん中の丸い部分がディスクプラッターです。通常、プラッターは複数あり、各ディスクには独自のヘッドがあります。右の図はディスクの構造です。ディスクの各層は複数のトラックに分かれており、各トラックは複数のセクターに分かれており、各セクターは 512 バイトです。そして、同じ番号の複数のトラックがシリンダーを形成し、上の図の中央に示すように、ディスクのシリンダーと呼ばれます。

ディスクスケジューリングアルゴリズムの目的は非常に単純で、ディスクのアクセスパフォーマンスを向上させることです。これは通常、ディスクアクセス要求の順序を最適化することによって実現されます。

シーク時間はディスクアクセスの中で最も時間のかかる部分です。要求順序が適切に最適化されていれば、不要なシーク時間を節約でき、ディスクアクセスのパフォーマンスが向上します。

次の一連のリクエストを想定します。各番号はトラックの位置を表します。

98、183、37、122、14、124、65、67

初期ヘッドの現在の位置はトラック 53 です。

次に、上記のシーケンスを各スケジューリングアルゴリズムの例として取り上げます。一般的なディスクスケジューリングアルゴリズムは次のとおりです。

先着順アルゴリズム
最短シークタイム優先アルゴリズム
スキャンアルゴリズム
巡回スキャンアルゴリズム
LOOK および C-LOOK アルゴリズム

先着順

先着順 (FCFS) は、その名前が示すように、最初に到着したリクエストが最初に処理されます。

次に、この順序に従います。

98、183、37、122、14、124、65、67

次に、ディスクは以下に示すように左から右の順に書き込まれます。

先着順

先着順アルゴリズムは、合計 640 トラックの距離を移動します。一見すると、このアルゴリズムは比較的単純で粗雑です。ただし、多数のプロセスがディスクの使用を競う場合、アクセスを要求されたトラックが非常に分散することがあり、先着順アルゴリズムはシーク時間が長すぎるため、パフォーマンスが非常に悪いように見えます。

最短のシーク時間を優先

Shortest Seek First (SSF) アルゴリズムは、現在のヘッド位置からのシーク時間が最も短いリクエストを優先することによって機能します。次のシーケンスを例に挙げてみましょう。

98、183、37、122、14、124、65、67

次に、先頭に最も近いリクエスト (位置 53) のアルゴリズムに従って、特定のリクエストは左から右に次の順序になります。

65、67、37、14、98、122、124、183

最短のシーク時間を優先

ヘッドが移動する総距離は 236 トラックで、先着順のパフォーマンスに比べて大幅に向上しています。

ただし、このアルゴリズムでは、一部のリクエストでスタベーションが発生する可能性があります。この例では静的シーケンスを使用しているため、問題は確認できません。動的リクエストであると仮定すると、後続のリクエストがすべてトラック 183 より小さい場合、トラック 183 に応答されない可能性があり、スタベーションが発生します。ここでスタベーションが発生する理由は、ヘッドが狭い領域で前後に移動するからです。

スキャンアルゴリズム

最短シーク時間を優先するアルゴリズムがスターベーションを引き起こす理由は、ヘッドが狭い領域で前後に移動する可能性があるためです。

この問題を防ぐには、ヘッドが一方向に移動してすべての未完了の要求にアクセスし、その方向の最後のトラックに到達したら方向を変えるように規定することができます。これがスキャンアルゴリズムです。

このアルゴリズムはエレベーターアルゴリズムとも呼ばれ、たとえば、エレベーターは、その方向に要求がなくなるまで一方向に移動し、その後方向を変えます。

このシーケンスを例に挙げると、ヘッドの初期位置は 53 です。

98、183、37、122、14、124、65、67

次に、スキャンスケジューラが最初にトラック番号が減少する方向に移動すると仮定すると、特定の要求は左から右に次の順序になります。

37、14、0、65、67、98、122、124、183

スキャンアルゴリズム

ヘッドは最初に左からの要求に応答し、左端 (トラック 0) に到達した後にのみ、右からの要求に応答するために反対方向に移動し始めます。

スキャンスケジューリングアルゴリズムはパフォーマンスが良好で、スタベーションは発生しませんが、中間部分のトラックが有利になり、中間部分の応答周波数が他の部分よりも高くなる、つまり、各トラックの応答周波数に差が生じるという問題があります。

巡回スキャンアルゴリズム

スキャンアルゴリズムにより、各トラックの応答周波数に違いが生じます。この問題を最適化するには、各トラックの応答周波数が基本的に同じになるように、常に同じ方向にスキャンします。

循環スキャン (CSCAN) では、トラックアクセス要求はヘッドが特定の方向に移動するときにのみ処理され、戻るときはエッジに最も近いトラックに直接すばやく移動する、つまりヘッドをリセットすることを規定しています。このプロセスは非常に高速で、戻る途中で要求が処理されることはありません。このアルゴリズムの特徴は、トラックが一方向の要求にのみ応答することです。

このシーケンスを例に挙げると、ヘッドの初期位置は 53 です。

98、183、37、122、14、124、65、67

次に、循環スキャンスケジューラが最初にトラックを増やす方向に移動すると仮定すると、特定の要求は左から右に次の順序になります。

65、67、98、122、124、183、199、0、14、37

巡回スキャンアルゴリズム

ヘッドは、右端のトラック 199 に触れるまで、まず右から要求に応答し、その後すぐにディスクの先頭 (トラック 0) に戻りますが、最初のトラックに到達するまで戻る途中ではいかなる要求にも応答せず、その後は右から順番に要求に応答し続けます。

スキャンアルゴリズムと比較すると、サイクリックスキャンアルゴリズムは、各トラック位置に対する応答周波数が比較的平均的です。

LOOK および C-LOOK アルゴリズム

前述のスキャンアルゴリズムと循環スキャンアルゴリズムはどちらも、ヘッドがディスクの「先頭または末尾」に移動したときにのみ方向の変更を開始します。

これは実際に最適化できます。ディスクヘッドが「最も遠い要求」の位置に移動し、その後すぐに反対方向に移動するという考え方です。

SCAN アルゴリズムの最適化は、LOOK アルゴリズムと呼ばれます。その動作は、ヘッドが各方向で要求された最も遠い位置までのみ移動し、その後すぐに反対方向に移動し、ディスクの先頭または末尾に移動することはありません。逆方向への移動中に要求に応答します。

LOOKアルゴリズム