ՍԿԱՆ (վերելակ) սկավառակի պլանավորման ալգորիթմ

Օպերացիոն համակարգում ծրագրերի կամ հավելվածների մուտքագրման կամ ելքի հարցումները մշակվում են սկավառակի պլանավորման ալգորիթմների միջոցով: Համակարգը ստանում է անհամար թվով հարցումներ տարբեր ծրագրերից, և միայն մեկ հարցումը կարող է միաժամանակ մշակվել համակարգի կողմից, իսկ մնացած բոլոր հարցումները պետք է հերթագրվեն: Սկավառակի պլանավորման հիմնական աշխատանքը համակարգի արդյունավետության բարձրացումն է՝ նվազեցնելով որոնման ժամանակը, պտտվող ուշացումը և փոխանցման ժամանակը: Այս գործընթացների համար օգտագործվում են տարբեր ալգորիթմներ, որոնցից մեկը SCAN-ն է (Elevator):

Սկան սկավառակի պլանավորման ալգորիթմ

Scan Disk Scheduling ալգորիթմը կոչվում է նաև վերելակի ալգորիթմ՝ իր աշխատանքային ձևի պատճառով: Վերելակը շարժվում է վեր ու վար՝ տարբեր հարկերում գտնվող տարբեր անձանց խնդրանքների հիման վրա: Երբ վերելակը հասնի կամ վերջին հարկ, կամ առաջին հարկ, այն կփոխի իր ուղղությունը և կսկսի շարժվել հակառակ ուղղությամբ:

Վերոհիշյալ գործողության նման, սկավառակի թեւը շարժվում է ետ ու առաջ սկավառակի միջով` ճանապարհին հետքերով սպասարկելու հարցումների հիման վրա:

Սկան սկավառակի պլանավորման ալգորիթմի բնութագրերը

• Միջին միջակայքի հարցումներն ավելի շատ սպասարկվում են, և նրանք, ովքեր ժամանում են սկավառակի թևի հետևում, պետք է սպասեն:

• Այս ալգորիթմը պարզ է.

• Այն չունի սով, քանի որ գործընթացները բաշխվում են ռեսուրսներով, քանի որ սկավառակը անընդհատ շարժվում է:

• Դա շատ ավելի լավ է, քան First Come First Serve ալգորիթմը:

SCAN սկավառակի պլանավորման ալգորիթմի օրինակ −

Ալգորիթմ

Քայլ 1 − Զանգվածն ունի այն տարրերը, որոնք պահանջել են ռեսուրսներ տարբեր պրոցեսներից՝ ըստ ժամանման ժամանակի աճման կարգի:

Քայլ 2 − Սկավառակի թեւը սկսվում է սկավառակի մի ծայրից և շարժվում դեպի մյուս ծայրը:

Քայլ 3 − Երբ սկավառակը շարժվում է այս ուղղությամբ, այն կսպասարկի բոլոր հետքերը մեկ առ մեկ՝ հիմնվելով հարցման վրա:

Քայլ 4 − Այնուհետև հաշվարկեք գլխից անցած ընդհանուր հեռավորությունը:

Քայլ 5 − Նոր պաշտոնը ճանաչվում է ներկայումս սպասարկվող հարցումով

Քայլ 6 − Այնուհետև քայլ 3-ը կրկնվում է, երբ այն հասնում է սկավառակի մի ծայրին:

Քայլ 7 − Երբ վերջնակետին հասնի, այն կփոխի ուղղությունը և կվերադառնա քայլ 2, երբ ամբողջ հարցումը սպասարկվի:

Մոտեցում. C ծրագիր՝ SCAN սկավառակի պլանավորման ալգորիթմը իրականացնելու համար

Ծրագիր, Կոդ.

#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 սկավառակի պլանավորման հայեցակարգը ներկայացված է այս հոդվածում օրինակի հետ միասին: Այն օգտագործվում է ծրագրերը պլանավորելու համար՝ հիմնվելով ուղղակի մուտքի խնդրանքի վրա: Ուղղակի մուտքն այն պարամետրն է, որն ավելի շատ ժամանակ է պահանջում օպերացիոն համակարգում, և դրա հիմնական նպատակն է նվազագույնի հասցնել որոնման և փոխանցման ժամանակը և բարձրացնել դրա կատարումը: