Round-robin (алгоритм)

Эргэх цагираг-процесс (Англи: Round-robin) гэх нэршил нь процессын алгоритмын нэгэн аргачлалыг нэрлэдэг. Нэг дор олон процессод ажиллах үед, үйлдлийн систем аль процессыг нь эхэлж гүйцэтгэхээ шийдэх хэрэгтэй болдог. Энэ шийдвэрийг гаргадаг үйлдлийн системийн хэсгийг Диспетчер гэх ба тооцоолдог алгоритмыг төлөвлөлтийн алгоритм гэнэ. Олон төлөвлөлтийн алгоритм байдаг бөгөөд тэдний нэг нь Эргэх цагираг (Round-robin) төлөвлөлтийн алгоритм юм.

Энэхүү төлөвлөлтийн алгоритм нь компьютерын сүлжээнд өгөгдлийн пакет хуваарилах гэх мэт бусад хуваарилалтын асуудлуудад мөн ашиглагдаж болно. Энэ нь үйлдлийн системийн нэгэн чухал ойлголт юм. "Эргэх цагираг" хуваарилалтын алгоритм нь ихэнх үйлдлийн системд хэрэгжиж болох хамгийн түгээмэл хуваарилалтын алгоритмуудын нэг юм.

Процесс төлөвлөлт

Процесс бүрт дараалан тодорхой хугацаа олох замаар ахин дахин давтан ажилладаг. Дараалалд орж буй бүх процесс бүрт тогтмол хугацаа хуваарилагдана. Энэ тогтсон хугацааг "цаг хугацаа" эсвэл "квант" гэж нэрлэдэг. Цагны тасалдал ашигладаг. Хэрэв процесс дууссан бол төлөвлөлтийг гүйцэтгэхийн тулд дараалалд бэлэн байгаа эхний процессыг сонгоно. Процесс бүр төв процессыг эзэмших хугацаатай тодорхойлогдоно. Оноох хугацаа нь анх хүсэлт илгээсэн үеийн нөхцөлөөс хамаардаг. Хүлээх хугацаа нь процессын тооноос шалтгаална.

Ирж буй анхны процесс нь сонгогдсон бөгөөд процессор уруу илгээгдэнэ.
Хэрэв энэ нь квант буюу өгөгдсөн хугацааны дотор гүйцэтгэлийг гүйцээж чадахгүй бол тасалдлыг автомат "timer" ашиглан үүсгэдэг.
Процесс зогсож, дарааллын төгсгөлд буцаж болно. Энэ үед төлөв санах ойд хадаглагдана. Энэ нь тасалдсан цэгээс үргэлжлүүлэх процессод тусалдаг.
Тооцоологч нь бэлэн дарааллаас өөр процессыг сонгож процессорыг гүйцэтгэлд илгээдэг. Энэ нь квантыг хэтрүүлэх хүртэл гүйцэтгэгдэнэ.
Бүх процесс дуусах хүртэлх адил алхмууд давтана.

Давуу талууд

Зэрэглэл гэж байхгүй учраас гачигдал үүсэхгүй
Энгийн, хэрэгжихэд хялбар, starvation-free байдаг
Бүх ажлыг CPU-ийн шударга хуваарилалтаар хувиаралдаг.

Сул талууд

Бага хугацаанд биелэгдэх олон процесс ачаалагдсан үед нэмэлт тооцолол их шаарддаг.
Хүлээх хугацаа урт байж болох учраас биелэгдэх эцсийн хугацаа тавьж өгөх боломжгүй

Жишээ

Квант = 2

Процесс	Ирэх цаг	Burst хугацаа
P1	0	9
P2	1	5
P3	2	3
P4	3	4

Процесс	Ирэх цаг	Burst хугацаа	Дахин тохируулах цаг (t)	Хэвийн эргэлттэй хугацаа (t / х)	Хүлээх хугацаа
P1	0	9	21	2.34	12
P2	1	5	17	3.4	12
P3	2	3	11	3.67	8
P4	3	4	12	3	8

Дундаж дахин тохируулах цаг (t)= 15.25

Дундаж хэвийн эргэлттэй хугацаа= 3.10

Дундаж Хүлээх хугацаа = 10

Жишээ код

#include<stdio.h> 
 
int main() 
{ 
 
  int count,j,n,time,remain,flag=0,time_quantum; 
  int wait_time=0,turnaround_time=0,at[10],bt[10],rt[10]; 
  printf("Niit Processiig oruulna uu :\t "); 
  scanf("%d",&n); 
  remain=n; 
  for(count=0;count<n;count++) 
  { 
    printf("Ireh Hugatsaa bolon Burst time-iin process-iin toog oruulna uu %d :",count+1); 
    scanf("%d",&at[count]); 
    scanf("%d",&bt[count]); 
    rt[count]=bt[count]; 
  } 
  printf("Quantum Hugatsaag oruulna uu:\t"); 
  scanf("%d",&time_quantum); 
  printf("\n\nProcess\t|Oorchloltiin hugatsaa|huleeltiin hugatsaa\n\n"); 
  for(time=0,count=0;remain!=0;) 
  { 
    if(rt[count]<=time_quantum && rt[count]>0) 
    { 
      time+=rt[count]; 
      rt[count]=0; 
      flag=1; 
    } 
    else if(rt[count]>0) 
    { 
      rt[count]-=time_quantum; 
      time+=time_quantum; 
    } 
    if(rt[count]==0 && flag==1) 
    { 
      remain--; 
      printf("P[%d]\t|\t%d\t|\t%d\n",count+1,time-at[count],time-at[count]-bt[count]); 
      wait_time+=time-at[count]-bt[count]; 
      turnaround_time+=time-at[count]; 
      flag=0; 
    } 
    if(count==n-1) 
      count=0; 
    else if(at[count+1]<=time) 
      count++; 
    else 
      count=0; 
  } 
  printf("\nDundaj huleeltiin hugatsaa= %f\n",wait_time*1.0/n); 
  printf("Dundaj oorchloltiin hugatsaa = %f",turnaround_time*1.0/n); 
  
  return 0; 
}