SCAN (Elevator) एल्गोरिथ्म क्या है? Source Code के साथ पूरी जानकारी

SCAN एल्गोरिथ्म (Elevator एल्गोरिथ्म) क्या है? सोर्स कोड के साथ पूरी जानकारी

SCAN एल्गोरिदम को एक ‘Elevator Algorithm’ के रूप में भी जाना जाता है, क्योंकि यह डिस्क के Collected डेटा को एक अंत से दूसरे अंत तक ले जाता है जैसे कि एक लिफ्ट करती है । यह Disk Scheduling Algorithm का एक part है जो Computer मे Hard Disk से Data को access करने मे मदद करते है। इन Algorithm का इस्तेमाल ऑपरेटिंग सिस्टम मे किया जाता है ताकि Data को बहुत तेजी से और प्रभावी तरीकों से पहुँचाया जा सके ।

SCAN (Elevator एल्गोरिथम)

  • Speed: Hard Disk Head दोनों दिशाओं में चलता है, रास्ते में आने वाले Request को पूरा करता है। यह एक Building में ऊपर-नीचे जाने वाले लिफ्ट (Elevator) के समान कार्य करता है ।
  • Process:
    1. Head अपनी Initial Position से शुरू होता है।
    2. यह एक दिशा (Left Side, मान लीजिए) में चलता है और Route में आने वाले सभी Request को पूरा करता है, जब तक यह Disk के अंत (Maximum Cylinder नंबर) तक नहीं पहुंच जाता।
    3. फिर, यह दिशा बदल देता है (Right Side) और वापस Starting Point पर जाने के दौरान सभी शेष Request पूरा करता है।
  • Repeat: यह प्रक्रिया लगातार Repeat की जाती है – हेड एक दिशा में चलता है, Requests को पूरा करता है, दिशा बदलता है, और वापसी यात्रा में Reminder Request को पूरा करता है।
  • फायदा: SCAN Algorithm कुछ एल्गोरिदम की तुलना में Seek टाइम को कम करता है क्योंकि यह दोनों दिशाओं में Request को पूरा करता है।
Elevator (SCAN) Algorithm

[Advantage] स्कैन ऐल्गरिदम के कुछ फायदे

  • SCAN (Elevator) Algorithm समझने मे बहुत ज्यादा सरल है ।
  • SCAN Algorithm मे कोई भी Starvation* नहीं है ।
  • यह Algorithm FCFS Algorithm से ज्यादा Better है ।

[Disadvantage] स्कैन ऐल्गरिदम के कुछ नुकसान

  • Elevator Algorithm समझने मे जितना आसान है इसे लागू करना उतना ही जटिल है ।
  • यह ऐल्गरिदम कई बार उचित नहीं होता क्युकी ये head द्वारा हाल ही मे visit किए गए cylinders का waiting time बढ़ा देता है ।
  • SCAN Algorithm Head को डिस्क के अंत तक ले जाने का कारण बनता है जिससे arm के आगे आने वाले request को तुरंत process कर लिया जाएगा पर पीछे रहने वाले request का waiting Time बढ़ जाएगा ।

SCAN (Elevator) Algorithm Pseudocode

यहा आपको SCAN (Elevator) एल्गोरिथ्म Step by Step बताया गया है ।

Step 1: Initialization

  • current_position: डिस्क हेड की वर्तमान स्थिति (Track Number)
  • pending_requests: Pending Read/Write Request की Queue (Track Number के अनुसार Sorted करना)
  • start: डिस्क का Starting ट्रैक (सबसे कम ट्रैक नंबर)
  • end: डिस्क का Last ट्रैक (सबसे अधिक ट्रैक नंबर)
  • direction: हेड की दिशा (Inward या Outward) – Starting रूप से Inward (आंतरिक) माना जा सकता है

Step 2: Request को पूरा करना

  • जब तक pending_requests खाली न हो जाए या current_position start या end तक पहुँच न जाए तब तक दोहराएँ:
    • pending_requests से अगले ट्रैक नंबर को target_position के Form में निकालें।
    • यदि current_position != target_position तब
      • हेड को target_position की ओर ले जाएँ। (Seek operation)
      • current_position को target_position के बराबर Updates करें।
    • pending_requests से target_position को हटाएँ.।
  • target_position पर Read/Write ऑपरेशन करें.

Step 3: Direction बदलना

  • यदि current_position == end तब
    • direction को Outward (बाहरी) में बदलें।
  • यदि current_position == start और direction == Inward तब
    • direction को Outward (बाहरी) में बदलें।

Step 4: प्रक्रिया को दोहराएँ

Step 2 और 3 पर वापस जाएँ और तब तक दोहराएँ जब तक सभी Pending Request को पूरा नहीं कर लिया जाता है।

नोट:

  • यह एल्गोरिथ्म मानता है कि Pending Request पहले से ही ट्रैक नंबरों के Ascending Order में Sorted हैं।
  • आप Inward दिशा से शुरू करने के बजाय Outward दिशा से भी शुरू कर सकते हैं – इससे कोई फर्क नहीं पड़ता, बस प्रारंभिक direction को Accordingly सेट करें।

Example

Input: 
Request sequence = {170, 75, 36, 58, 92, 11, 49, 115}
Initial head position = 50
Direction = left (We are moving from right to left)
Output:
Total number of seek operations = 220
Seek Sequence is
49
36
11
0
58
75
92
115
170

आप नीचे दिए गए image को देख कर scan {Elevator} ऐल्गरिदम के working को समझ सकते है ।

SCAN (Elevator) Algorithm

Calculate Seek Time

Seek time = (50-49) + (49-36) +(36-11) + (11-0) + (58-0) + (75-58) + (92-75) + (115-92) +(170-115) = 220

Source Code of SCAN [Elevator] Algorithm in C

#include <stdio.h>

void scan(int arr[], int n, int head, char direction) {
  int i;

  // Sort the request array (ascending order)
  for (i = 0; i < n - 1; i++) {
    for (int j = 0; j < n - i - 1; j++) {
      if (arr[j] > arr[j + 1]) {
        int temp = arr[j];
        arr[j] = arr[j + 1];
        arr[j + 1] = temp;
      }
    }
  }

  // Move head according to direction
  if (direction == 'I') {
    for (i = 0; i < n && arr[i] <= head; i++) {
      if (arr[i] == head) {
        printf("Servicing request at track %d\n", head);
      }
    }

    for (i = i; i < n; i++) {
      printf("Head moving from %d to %d\n", head, arr[i]);
      head = arr[i];
      printf("Servicing request at track %d\n", head);
    }
  } else {
    for (i = n - 1; i >= 0 && arr[i] >= head; i--) {
      if (arr[i] == head) {
        printf("Servicing request at track %d\n", head);
      }
    }

    for (i = i - 1; i >= 0; i--) {
      printf("Head moving from %d to %d\n", head, arr[i]);
      head = arr[i];
      printf("Servicing request at track %d\n", head);
    }
  }
}

int main() {
  int arr[] = {170, 43, 140, 240, 100, 70};
  int n = sizeof(arr) / sizeof(arr[0]);
  int head = 80;
  char direction = 'I'; // Change to 'O' for outward direction

  printf("SCAN Algorithm\n");
  printf("Initial head position: %d\n", head);
  printf("Request queue: ");
  for (int i = 0; i < n; i++) {
    printf("%d ", arr[i]);
  }
  printf("\n");
  printf("Direction: %c\n", direction);

  scan(arr, n, head, direction);

  return 0;
}

Output

SCAN Algorithm
Initial head position: 80
Request queue: 170 43 140 240 100 70 
Direction: I

Servicing request at track 80
Head moving from 80 to 100
Servicing request at track 100
Head moving from 100 to 140
Servicing request at track 140
Head moving from 140 to 170
Servicing request at track 170
Head moving from 170 to 70
Servicing request at track 70
Head moving from 70 to 43
Servicing request at track 43
Head moving from 43 to 240
Servicing request at track 240

जैसा की आप देख सकते है की ये Program SCAN Algorithm को simulate करता है । डिस्क Head 80 से Start होता है और इन्वर्ड direction (Increasing track num) मे service Request तब तक भेजता है जब तक यह end (170) तक नहीं पहुच जाता । उसके बाद यह दिशा को Reverse करता है और तब तक Service Request भेजता है जब तक वह Beginning(43) मे नहीं पहुच जाता ।

निष्कर्ष

दोस्तों जैसा की हमने जाना की scan (Elevator) Algorithm क्या है ? और साथ ही इसके source code को समझा। SCAN (Elevator) Algorithm एक डिस्क scheduling ऐल्गरिदम का एक हिस्सा है जो हमे data को एक part से दूसरे part मे ले जाता है जैसा की एक लिफ्ट करती है इसलिए इसे Elevator Algorithm भी बोलते है । यह FCFS से तो बेहतर काम करता है पर इसमे Waiting Time भी अधिक है । अतः जहा पर टाइम इतना important न हो वह इसे आसानी से Implement किया जा सकता है ।

दोस्तों याद रखे कोई भी algorithm 100% Ideal नहीं होता, यह कुछ Conditions पे depend करता है ओर उसी आधार पर हम दूसरे ऐल्गरिदम को चुनते है जैसे – FCFS, SSTF, SCAN etc.

How useful was this post?

Click on a star to rate it!

Average rating 5 / 5. Vote count: 1

No votes so far! Be the first to rate this post.

As you found this post useful...

Follow us on social media!

We are sorry that this post was not useful for you!

Let us improve this post!

Tell us how we can improve this post?

4 thoughts on “SCAN (Elevator) एल्गोरिथ्म क्या है? Source Code के साथ पूरी जानकारी”

Leave a Comment