SCAN (電梯) 磁碟排程演算法

在作業系統中，程式或應用程式的輸入或輸出請求由磁碟排程演算法處理。系統接收來自不同程式的大量請求，並且系統一次只能處理一個請求，所有其他請求都必須在佇列中等待。磁碟排程的主要工作是透過減少尋道時間、旋轉延遲和傳輸時間來提高系統性能。對於這些過程，使用了不同的演算法，其中之一就是 SCAN（電梯）。

掃描磁碟排程演算法

掃描磁碟排程演算法也稱為電梯演算法，因為它的工作方式類似於電梯。電梯根據不同樓層不同人的請求上下移動。當電梯到達頂層或底層時，它會改變方向並開始向相反方向移動。

類似於上述功能，磁碟臂根據沿途對磁軌的服務請求在磁碟上前後移動。

掃描磁碟排程演算法的特點

  • 中間範圍的請求得到更多服務，而到達磁碟臂後面的請求將不得不等待。

  • 此演算法簡單。

  • 它沒有飢餓現象，因為隨著磁碟持續移動，程序會分配資源。

  • 它比先到先服務演算法好得多。

掃描磁碟排程演算法示例 -

演算法

步驟 1 - 陣列包含根據到達時間按升序排列的不同程序請求資源的元素。

步驟 2 - 磁碟臂從磁碟的一端開始，向另一端移動。

步驟 3 - 當磁碟沿此方向移動時，它將根據請求逐一服務所有磁軌。

步驟 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 磁碟排程的概念以及一個示例。它用於根據直接訪問的請求安排程式。直接訪問是在作業系統中花費更多時間的引數，其主要目的是最大限度地減少尋道時間和傳輸時間並提高其效能。

更新於: 2023-07-17

3K+ 瀏覽量

開啟你的 職業生涯

透過完成課程獲得認證

開始學習
廣告

© . All rights reserved.