ウェブサイト検索

SCAN (エレベーター) ディスク スケジューリング アルゴリズム

オペレーティング システムでは、プログラムまたはアプリケーションの入力または出力からの要求は、ディスク スケジューリング アルゴリズムによって処理されます。システムはさまざまなプログラムから無数のリクエストを受け取りますが、システムが一度に処理できるリクエストは 1 つだけで、他のすべてのリクエストはキューで待機する必要があります。ディスク スケジューリングの主な作業は、シーク時間、回転待ち時間、および転送時間を短縮してシステムのパフォーマンスを向上させることです。これらの処理にはさまざまなアルゴリズムが使用されますが、その中の 1 つが SCAN (エレベーター) です。

スキャンディスクのスケジュールアルゴリズム

スキャン ディスク スケジューリング アルゴリズムは、その動作方法からエレベーター アルゴリズムとも呼ばれます。エレベーターは、異なるフロアの異なる人の要求に基づいて上下に移動します。エレベーターが最終階または地上階に到着すると、方向を変えて逆方向に動き始めます。

上記の機能と同様に、ディスク アームは、途中のトラックのサービス要求に基づいてディスク上を前後に移動します。

スキャンディスクスケジュールアルゴリズムの特徴

  • 中間範囲でのリクエストはさらに処理され、ディスク アームの後ろに到着するリクエストは待つ必要があります。

  • このアルゴリズムは単純です。

  • ディスクが継続的に移動するときにプロセスにリソースが割り当てられるため、飢餓が発生しません。

  • これは、先着順アルゴリズムよりもはるかに優れています。

SCANディスクスケジュールアルゴリズムの例-

アルゴリズム

ステップ 1 - 配列には、さまざまなプロセスからリソースを要求した要素が、到着時間に基づいて昇順で格納されます。

ステップ 2 - ディスク アームはディスクの一端から開始し、もう一方の端に向かって移動します。

ステップ 3 - ディスクがこの方向に移動すると、リクエストに基づいてすべてのトラックが 1 つずつ処理されます。

ステップ 4 - 次に、ヘッドからの総移動距離を計算します。

ステップ 5 - 現在処理されているリクエストによって新しい位置が特定されます

ステップ 6 - ディスクの一端に到達すると、ステップ 3 が繰り返されます。

ステップ 7 - エンドポイントに到達すると、方向が逆転し、リクエスト全体が処理されるとステップ 2 に戻ります。

アプローチ: SCAN ディスク スケジューリング アルゴリズムを実装する C プログラム

プログラム、コード:

#include <stdio.h>
#include <stdlib.h>
#include <string.h>

#define size 10
#define disk_size 200
int comp(const void * l, const void * n) {
   return (*(int*)l - *(int*)n);
}
void SCAN(int arr[], int head, char* dn){
   int seek_num = 0;
   int dt, cur_track;
   int leftside[size], rightside[size];
   int seek_seq[size + 3];
   int m_scan = 0, s_scan = 0;
   if (strcmp(dn, "leftside") == 0)
      leftside[m_scan++] = 0;
   else if (strcmp(dn, "rightside") == 0)
      rightside[s_scan++] = disk_size - 1;
   for (int p_s = 0; p_s < size; p_s++) {
      if (arr[p_s] < head)
         leftside[m_scan++] = arr[p_s];
      if (arr[p_s] > head)
         rightside[s_scan++] = arr[p_s];
   }
   qsort(leftside, m_scan, sizeof(int), comp);
   qsort(rightside, s_scan, sizeof(int), comp);
   int go = 2;
   int ind = 0;
   while (go--) {
      if (strcmp(dn, "leftside") == 0) {
         for (int p_s = m_scan - 1; p_s >= 0; p_s--) {
            cur_track = leftside[p_s];
            seek_seq[ind++] = cur_track;
            dt = abs(cur_track - head);
            seek_num += dt;
            head = cur_track;
        }
        dn = "rightside";
      }
      else if (strcmp(dn, "rightside") == 0) {
         for (int p_s = 0; p_s < s_scan; p_s++) {
            cur_track = rightside[p_s];
            seek_seq[ind++] = cur_track;
            dt = abs(cur_track - head);
            seek_num += dt;
            head = cur_track;
         }
         dn = "leftside";
      }
   }
   printf("Num of seek process = %d
", seek_num);
   printf("Sequence is
");
   for (int p_s = 0; p_s < ind; p_s++) {
      printf("%d
", seek_seq[p_s]);
   }
}
int main(){
   int arr[size] = { 126, 90, 14, 50, 25, 42, 51, 78, 102, 100 };
   int head = 42;
   char dn[] = "leftside";
   SCAN(arr, head, dn);
   return 0;
}

出力

Num of seek process = 168
Sequence is
25
14
0
50
51
78
90
100
102
126

結論

この記事では、SCAN ディスク スケジューリングの概念を例とともに説明します。直接アクセスからのリクエストに基づいて番組をスケジュールするために使用されます。直接アクセスはオペレーティング システムでより時間がかかるパラメータであり、その主な目的はシーク時間と転送時間を最小限に抑え、パフォーマンスを向上させることです。

関連記事: