الگوریتم RR چیست؟ – توضیح الگوریتم زمان بندی نوبت گردشی

الگوریتم زمان بندی «راند رابین» (Round-Robin) که به «الگوریتم RR» هم شناخته می‌شود، مفهومی ساده و بسیار قدیمی در دنیای کامپیوتر است. ایده‌ اصلی این روش درباره اختصاص منبع CPU به فرایند‌ها به روش راند رابین است. به عبارت دیگر، فرض کنیم که تعداد N فرایند‌ آماده اجرا داریم. تمام فرایند‌ها نوبت زمانی خود را برای استفاده از CPU با مقدار زمان مساوی دارند. به‌ترتیب، یکی پس از دیگری سی پی یو را در اختیار می‌گیرند. در این رویکرد زمان‌بندی، مطمئن می‌شویم که هر فرایند‌ی به اندازه مقدار ثابت و مساویی از زمان، CPU را در اختیار داشته باشد. این مسئله باعث بدست آمدن عملکرد ثابتی توسط سیستم عامل و CPU می‌شود.

این الگوریتم از اشغال بیش‌ از حد CPU توسط فرایند‌ها جلوگیری می‌کند. در نتیجه اگر پردازشی نیاز به استفاده از CPU به مدت زمان طولانی داشته باشد، تاثیری بر اجرای سایر فرایند‌ها نمی‌گذارد. همچنین، با کمک الگوریتم RR می‌توان عملکرد CPU را با دادن میزان حافظه بیشتر به آن ارتقا داد. در این مطلب از مجله فرادرس، با اصول پایه الگوریتم RR آشنا شده و برای درک روش کار الگوریتم، مثالی را همراه با جزئیات کامل مشاهده می‌کنیم. به همین ترتیب، درباره مزایا و معایب استفاده از این الگوریتم نیز صحبت کرده‌ایم.

الگوریتم RR چیست؟

عبارت RR سرنامی از کلمات Round-Robin است و از اصل راند رابین گرفته شده. در این اصل هر کس، مقدار مساوی از منابع را به نوبت در اختیار می‌گیرد. اصل راند رابین، قدیمی‌ترین و ساده‌ترین الگوریتمی است که برای مدیریت سامانه‌های «چند وظیفه‌ای» (Multi Task) به‌کار برده می‌شود. الگوریتم RR، منابع را به صورت مساوی بین فرایند‌ها توزیع می‌کند. سپس هر قسمت را در صفی حلقه‌وار و بدون در نظر گرفتن هیچ اولویتی پردازش می‌کند. عبارت‌های «زمان کوانتوم» (Time Quantum) و «برش زمانی» (Time Slice) برای توزیع همه منابع به صورت مساوی استفاده می‌شوند.

فیلم آموزش طراحی الگوریتم – جامع و با مفاهیم کلیدی در فرادرس

کلیک کنید

اگر پردازشی به پایان برسد، از صف آماده به اجرای الگوریتم RR حذف می‌شود. در غیر این صورت، برای انجام بقیه مراحل اجرا، به انتهای صف آماده به اجرا منتقل می‌شود. صف آماده به اجرا: فرایند‌هایی را نگهداری می‌کند که منتظر منبع پردازنده برای اجرا شدن هستند و بعد از شروع عملیات پردازش به صف اجرا منتقل می‌شوند. در ادامه به بررسی دقیق‌تر روش کار الگوریتم RR می‌پردازیم.

آموزش طراحی الگوریتم با فرادرس

طراحی الگوریتم یکی از مباحث پایه و اصولی در علوم کامپیوتری است. البته این رشته علمی، حوزه وسیع‌تری از علوم کامپیوتری را پوشش می‌دهد. اما با تاکید بر بخش مدرن و کامپیوتری این علم در فرادرس به تولید فیلم‌های آموزشی مناسب کار برنامه‌نویسان کامپیوتر و حتی دانشجویان برای آمادگی شرکت در آزمون‌های دانشگاهی پرداخته‌ایم. طراحی الگوریتم رابطه‌ای بسیار نزدیک با برنامه‌نویسی و ساختمان داده‌ دارد. به همین منظور با نگرش برنامه‌نویسی در فرادرس به تهیه فیلم‌های آموزشی مربوط به حوزه طراحی الگوریتم‌ها و ساختمان داده پرداخته‌ایم.

در بخش زیر، در ارتباط با طراحی الگوریتم و ساختمان داده، چند فیلم آموزشی را نام برده‌ایم. تسلط به مباحث مطرح شده در این فیلم‌ها یکی از تخصص‌های برجسته برنامه‌نویسان و مهندسان نرم‌افزار است. با کلیک بر روی تصویر بالا می‌توانید وارد صفحه اصلی این مجموعه آموزشی شده و از فیلم‌های بیشتری نیز دیدن کنید.

• فیلم آموزش طراحی الگوریتم به صورت جامع و با مفاهیم کلیدی در فرادرس
• فیلم آموزش طراحی الگوریتم همراه با حل مثال های عملی در فرادرس
• فیلم آموزش حل سوالات آزمون های استخدامی طراحی الگوریتم با فرادرس
• فیلم آموزش رابطه های بازگشتی در طراحی الگوریتم و ساختمان گسسته با فرادرس

مثالی از زمان بندی الگوریتم RR

در این بخش، فرایند کار الگوریتم RR را با کمک مثال بسیار ساده‌ای توضیح و به شکل مصور نمایش داده‌ایم. البته برای این‌که درک بهتری از این مثال داشته باشید، بهتر است با نحوه طراحی الگوریتم نیز آشنا باشید که برای این منظور می‌توانید فیلم آموزش طراحی الگوریتم با مثال‌های عملی فرادرس را مشاهده کنید که لینک آن را در ادامه آورده‌ایم.

فیلم آموزش طراحی الگوریتم + حل مثال های عملی در فرادرس

کلیک کنید

سه فرایند زیر را برای اجرا در نظر بگیرید.

در تصویر زیر شکل قرارگیری این فرایند‌ها را در صف آماده به اجرا می‌بینید.

• مرحله اول: پردازش‌ها با اجرای فرایند اول P1 شروع می‌شوند. تکمیل شدن فرایند اول ۴ واحد زمانی طول می‌کشد. در اینجا هر پردازش در ۲ واحد زمانی اجرا می‌شود. در طول اجرای P1، فرایند‌های P2 وP3 هنوز در صف انتظار هستند.

• مرحله دوم: در زمان ۲، P1 به انتهای «صف آماده اجرا» اضافه شده و P2 به پردازنده رفته و شروع به اجرا می‌کند.

• مرحله سوم: در زمان برابر با ۴، فرایند P2 در پردازنده جای خود را به P3 می‌دهد و به انتهای «صف آماده اجرا»، اضافه می‌شود. اکنون P3 شروع به اجرا می‌کند.

• مرحله چهارم: در زمان ۶، P3 از پردازنده خارج شده و به انتهای صف آماده به اجرا منتقل می‌شود. در این زمان فرایند P1 دوباره برای اجرا پردازنده را تصاحب می‌کند.

• مرحله پنجم: در زمان ۸، P1 به زمان تکمیل فرایند خود - که برابر با ۴ بود - رسیده‌ است. اجرای این عملیات به صورت کامل به پایان می‌رسد و اجرای فرایند P2 شروع می‌شود.

• مرحله ششم: تکمیل عملیات فرایند P2 برابر با ۳ واحد زمانی به طول می‌کشد. این فرایند قبلا به اندازه ۲ واحد از زمان، اجرا شده است. در نتیجه، در زمان ۹، اجرای فرایند P2 تکمیل می‌شود. سپس P3 شروع به اجرا می‌کند تا زمانی که به صورت کامل انجام شده و به پایان برسد.

• مرحله هفتم: در این مرحله میانگین زمانی انتظار را به ازای هر فرایند در مثال بالا محاسبه می‌کنیم.

Wait time 
P1= 0+ 4= 4
P2= 2+4= 6
P3= 4+3= 7

الگوریتم زمان بندی راند رابین چه مشخصاتی دارد؟

در فهرست زیر مهم‌ترین مشخصات الگوریتم زمان‌بندی راند رابین را ارائه داده‌ایم.

• الگوریتم RR از نوع الگوریتم‌های «غیر انحصاری» (Pre-emptive) است.
• بعد از اینکه CPU، بازه زمانی معین شده را بر روی هر فرایند، صرف کرد به صورت خودکار به سراغ فرایند بعدی می‌رود. به این بازه زمانی صرف شده زمان کوانتوم یا برش زمانی می‌گویند.
• فرایندی که نوبت اجرای آن به پایان رسیده اما پردازش آن‌ در سیستم عامل هنوز تمام نشده به انتهای صف آماده به اجرا، منتقل می‌شود.
• الگوریتم RR از نوع مدل‌های هیبرید است و بر اساس زمان مدیریت می‌شود. به این معنا که الگوریتم برای جابه‌جایی بین فرایند‌ها به یک زمان‌سنج متکی است.
•  قطعه‌های زمانی - زمان کوانتوم - باید به اندازه حداقل زمان مورد نیاز فرایند‌ها برای اجرا باشد. البته اندازه دقیق این قطعه‌های زمانی از سیستم عاملی به سیستم عامل دیگر متفاوت است.
• الگوریتم راند رابین، «بلادرنگ» (Real Time) است و به هر رویدادی در زمان مشخص پاسخ می‌دهد.
• الگوریتم RR یکی از قدیمی‌ترین، عادلانه‌ترین و ساده‌ترین الگوریتم‌های زمان‌بندی است.
• این الگوریتم، پر استفاده‌ترین الگوریتم زمان‌بندی در سیستم عامل‌های سنتی است.

پیاده سازی الگوریتم RR

در این بخش از مطلب، این الگوریتم را با استفاده از زبان‌های برنامه‌نویسی C و ++C و جاوا پیاده‌سازی کرده‌ایم. پیاده‌سازی کدهای تکنیک راند رابین را با زبان C شروع می‌کنیم.

پیاده سازی تکنیک راند رابین با زبان C

در کادر زیر، کدهای مربوط به پیاده‌سازی الگوریتم زمان‌بندی RR را با کمک زبان برنامه نویسی C نمایش داده‌ایم.

1// round robin scheduling program in c
2#include<stdio.h>
3
4void main()
5{ 
6    int i, NOP, sum=0,count=0, y, quant, wt=0, tat=0, at[10], bt[10], temp[10];
7    float avg_wt, avg_tat;
8    printf(" Total number of process in the system: ");
9    scanf("%d", &NOP);
10    y = NOP; 
11    
12    for(i=0; i<NOP; i++)
13    {
14        printf("\n Enter the Arrival and Burst time of the Process[%d]\n", i+1);
15        printf(" Enter Arrival time: \t"); 
16        scanf("%d", &at[i]);
17        printf(" \nEnter Burst time: \t"); 
18        scanf("%d", &bt[i]);
19        temp[i] = bt[i]; 
20    }
21
22    printf("Enter the Time Quantum for the process: \t");
23    scanf("%d", &quant);
24    printf("\n Process No \t\t Burst Time \t\t TAT \t\t Waiting Time ");
25    for(sum=0, i = 0; y!=0; )
26    {
27    if(temp[i] <= quant && temp[i] > 0) 
28    {
29        sum = sum + temp[i];
30        temp[i] = 0;
31        count=1;
32        }     
33        else if(temp[i] > 0)  
34        {  
35            temp[i] = temp[i] - quant;
36            sum = sum + quant;
37        }  
38        if(temp[i]==0 && count==1)  
39        {  
40            y--;  
41            printf("\nProcess No[%d] \t\t %d\t\t\t\t %d\t\t\t %d", i+1, bt[i], sum-at[i], sum-at[i]-bt[i]);  
42            wt = wt+sum-at[i]-bt[i];  
43            tat = tat+sum-at[i];  
44            count =0;     
45        }  
46        if(i==NOP-1)  
47        {  
48            i=0;  
49        }  
50        else if(at[i+1]<=sum)  
51        {  
52            i++;  
53        }  
54        else  
55        {  
56            i=0;  
57        }  
58    } 
59}

خروجی حاصل از اجرای کد بالا به صورت زیر به کاربر نمایش داده می‌شود.

Total number of processes in the system: 4
Enter the Arrival and Burst time of the Process[1]
 Enter Arrival time:    0
 Enter Burst time:  5
 Enter the Arrival and Burst time of the Process[2]
 Enter Arrival time:    1
 Enter Burst time:  4
 Enter the Arrival and Burst time of the Process[3]
 Enter Arrival time:    2
 Enter Burst time:  2
 Enter the Arrival and Burst time of the Process[4]
 Enter Arrival time:    4
 Enter Burst time:  1
 Enter the Time Quantum for the process:    2

پیاده سازی تکنیک راند رابین با زبان ++C

++C یکی از زبان‌های خانواده C و بسیار کاربردی است. توجه کنید که الگوریتم‌ها همیشه با ساختمان داده به صورت درهم تنیده کار می‌کنند. یعنی در واقع نوشتن الگوریتم وابسته به ساختمان داده‌هایی است که برنامه‌نویس می‌تواند پیاده‌سازی و استفاده کند. در صورتی که برنامه‌نویس زبان ++C هستید و می‌خواهید با اصول مربوط به طراحی ساختمان داده آشنا شوید، پیشنهاد می‌کنیم که مطلب مبانی ++C برای یادگیری ساختمان داده، به زبان ساده را از مجله فرادرس مطالعه کنید.

در کادر زیر، کدهای مربوط به پیاده‌سازی الگوریتم زمان‌بندی RR را با کمک زبان برنامه نویسی ++C نمایش داده‌ایم.

1// Program implementation in C++ for Round Robin scheduling 
2#include<iostream> 
3using namespace std; 
4
5//The Function to find the waiting time for all processes 
6void fWaitingTime(int processes[], int n, 
7			int bt[], int wt[], int quantum) 
8{ 
9	// Let us Make a copy of burst times bt[] to store remaining burst times
10	
11	int rem_bt[n]; 
12	for (int i = 0 ; i < n ; i++) 
13		rem_bt[i] = bt[i]; 
14
15	int t = 0; // for Current time 
16
17	// Let us keep traverse the processes in the round robin manner until all of them are not done.
18
19	while (1) 
20	{ 
21		bool done = true; 
22
23		//let us Traverse all processes one by one repeatedly 
24		for (int i = 0 ; i < n; i++) 
25		{ 
26			// If burst time of a process is greater than 0 then there is a need to process further
27			if (rem_bt[i] > 0) 
28			{ 
29				done = false; // indicates there is a pending process 
30
31				if (rem_bt[i] > quantum) 
32				{ 
33					// By Increasing the value of t it shows how much time a process has been processed 
34					t += quantum; 
35
36					// Decreasing the burst_time of current process by the quantum
37					rem_bt[i] -= quantum; 
38				} 
39
40				// If burst time is smaller than or equal to the quantum then it is Last cycle for this process 
41				else
42				{ 
43					// Increase the value of t to show how much time a process has been processed 
44					t = t + rem_bt[i]; 
45
46					// Waiting time is current time minus time used by this process.
47					wt[i] = t - bt[i]; 
48
49					// As the process gets fully executed thus remaining burst time becomes 0.
50					
51					rem_bt[i] = 0; 
52				} 
53			} 
54		} 
55
56		// If all the processes are done 
57		if (done == true) 
58		break; 
59	} 
60} 
61
62// Function used to calculate the turn around time 
63void fTurnAroundTime(int processes[], int n, 
64						int bt[], int wt[], int tat[]) 
65{ 
66	// calculating turnaround time by adding bt[i] + wt[i] 
67	for (int i = 0; i < n ; i++) 
68		tat[i] = bt[i] + wt[i]; 
69} 
70
71// Function to calculate the average time 
72void findavgTime(int processes[], int n, int bt[], 
73									int quantum) 
74{ 
75	int wt[n], tat[n], total_wt = 0, total_tat = 0; 
76
77	// Function to find waiting time of all processes 
78	fWaitingTime(processes, n, bt, wt, quantum); 
79
80	// Function to find turn around time for all processes 
81	fTurnAroundTime(processes, n, bt, wt, tat); 
82
83	// Display processes along with all details 
84	cout << "Processes "<< " Burst time "
85		<< " Waiting time " << " Turn around time\n"; 
86
87	// Calculate the total waiting time and total turn 
88	// around time 
89	for (int i=0; i<n; i++) 
90	{ 
91		total_wt = total_wt + wt[i]; 
92		total_tat = total_tat + tat[i]; 
93		cout << " " << i+1 << "\t\t" << bt[i] <<"\t "
94			<< wt[i] <<"\t\t " << tat[i] <<endl; 
95	} 
96
97	cout << "Average waiting time = "
98		<< (float)total_wt / (float)n; 
99	cout << "\nAverage turn around time = "
100		<< (float)total_tat / (float)n; 
101} 
102
103//Given below is the Driver Code
104int main() 
105{ 
106	// process id's 
107	int processes[] = { 1, 2, 3,4}; 
108	int x = sizeof processes / sizeof processes[0]; 
109
110	// Burst time of all processes 
111	int burst_time[] = {21, 13, 6,12}; 
112
113	// Time quantum 
114	int quantum = 2; 
115	findavgTime(processes, x, burst_time, quantum); 
116	return 0; 
117} 

در صورت اجرای کد بالا با زبان ++C، نتیجه به صورت زیر در کنسول خروجی نمایش داده می‌شود.

پیاده سازی تکنیک راند رابین با زبان جاوا

در کادر زیر، کدهای مربوط به پیاده‌سازی الگوریتم زمان‌بندی RR را با کمک زبان برنامه نویسی جاوا نمایش داده‌ایم.

1import java.util.Scanner;
2public class RoundRobin
3{  
4public static void main(String args[])
5{  
6int n,i,qt,count=0,temp,sq=0,bt[],wt[],tat[],rem_bt[];
7float awt=0,atat=0;  
8bt = new int[10];
9wt = new int[10];
10tat = new int[10];
11rem_bt = new int[10];
12Scanner s=new Scanner(System.in);
13System.out.print("Enter the number of process (maximum 10) = ");
14n = s.nextInt();  
15System.out.print("Enter the burst time of the process\n");  
16for (i=0;i<n;i++)  
17{  
18System.out.print("P"+i+" = ");   
19bt[i] = s.nextInt();  
20rem_bt[i] = bt[i];  
21}  
22System.out.print("Enter the quantum time: ");  
23qt = s.nextInt();  
24while(true)  
25{  
26for (i=0,count=0;i<n;i++)  
27{  
28temp = qt;  
29if(rem_bt[i] == 0)  
30{  
31count++;  
32continue;  
33}  
34if(rem_bt[i]>qt)  
35rem_bt[i]= rem_bt[i] - qt;  
36else  
37if(rem_bt[i]>=0)  
38{  
39temp = rem_bt[i];  
40rem_bt[i] = 0;  
41}  
42sq = sq + temp;  
43tat[i] = sq;  
44}  
45if(n == count)  
46break;  
47}  
48System.out.print("--------------------------------------------------------------------------------");
49System.out.print("\nProcess\t      Burst Time\t       Turnaround Time\t          Waiting Time\n");
50System.out.print("--------------------------------------------------------------------------------");
51for(i=0;i<n;i++)  
52{  
53wt[i]=tat[i]-bt[i];  
54awt=awt+wt[i];  
55atat=atat+tat[i];  
56System.out.print("\n "+(i+1)+"\t "+bt[i]+"\t\t "+tat[i]+"\t\t "+wt[i]+"\n");  
57}  
58awt=awt/n;  
59atat=atat/n;  
60System.out.println("\nAverage waiting Time = "+awt+"\n");  
61System.out.println("Average turnaround time = "+atat);  
62}  
63}  

در صورت اجرای کد بالا با زبان جاوا، نتیجه به صورت زیر در کنسول خروجی نمایش داده می‌شود.

مزایا و معایب الگوریتم RR

قبل از صحبت درباره مزایا و معایب الگوریتم RR، می‌خواهیم یکی دیگر از الگوریتم‌های زمان‌بندی به نام SRT را معرفی کنیم. الگوریتم «کوتاه‌ترین کار باقیمانده» (SRT | Shortest Remaining Time) روشی است که فرایندهای دارای کوتاه‌ترین زمان باقی‌مانده اجرا را در اولویت قرار می‌دهد. برای آموزش کوتاه و کامل این روش می‌توانید از فیلم آموزش رایگان روش حل الگوریتم SRT همراه با حل مثال زمانبندی در سیستم عامل از فرادرس بهره‌مند شوید. به منظور کمک به مخاطبان مجله، لینک این فیلم را در ادامه نیز قرار داده‌ایم.

فیلم روش حل الگوریتم SRT + حل مثال زمانبندی در سیستم عامل (رایگان) در فرادرس

کلیک کنید

همه الگوریتم‌های زمان‌بندی مانند الگوریتم HRRN، الگوریتم «اول کوتاه‌ترین فرایند»، الگوریتم «کوتاه‌ترین کار باقیمانده» و غیره دارای معایب و مزایای خاصی هستند که باعث می‌شود بعضی از اوقات به بهترین گزینه و بعضی از اوقات به بدترین گزینه ممکن برای استفاده تبدیل شوند. الگوریتم RR نیز شامل این ماجرا می‌شود. در پایین، مزایا و معایب استفاده از الگوریتم RR را نوشته‌ایم.

مزایای استفاده از الگوریتم زمان بندی RR چیست؟

در این بخش از مطلب، مهم‌ترین مزایای استفاده از این الگوریتم را در زیر، فهرست کرده‌ایم.

• الگوریتم راند رابین با مشکلاتی مانند «گرسنگی» (Starvation) و «اثر کاروان» (Convoy Effect) رو‌به‌رو نمی‌شود.
• همه وظایف به میزان عادلانه‌ای از CPU بهره‌مند می‌شوند.
• با همه پروسه‌ها بدون هیچ اولویت خاصی به صورت یکسان برخورد می‌کند.
• اگر تعداد کل فرایند‌های در حال انتظار در صف آماده را بدانیم، بنابراین می‌توانیم بدترین زمان پاسخ را برای هر پروسه پیش‌بینی کنیم.
• این روش زمان‌بندی، وابسته به زمان تکمیل فعالیت برای فرایندها نیست. به همین دلیل است که به سادگی بر روی سیستم قابل پیاده‌سازی است.
• وقتی که فرایندی به اندازه مجموع زمانی مشخصی اجرا شد، پردازنده را رها کرده و فرایند دیگری پردازنده را به اندازه همان مقدار زمان مشخص شده اشغال می‌کند.
• این الگوریتم به سیستم عامل اجازه می‌دهد تا از روش «تغییر زمینه» (Context Switching) برای نگهداری حالت‌ فرایند‌های منتقل شده به انتها صف آماده، استفاده کند.
• الگوریتم RR درباره میانگین زمان پاسخ، بهترین عملکرد را ارائه می‌دهد.

«تغییر زمینه» (Context switching): شامل ذخیره حالت وضعیت، و مقدار متغیرهای احتمالی فرایند در حال اجرا در CPU و سیستم عامل است. با کمک آن‌ داده‌ها می‌توان در زمان لازم دوباره آن فرایند را بر روی CPU بارگذاری کرد. در این حالت، اجرای آن از همان نقطه توقف از سر گرفته می‌شود.

معایب استفاده از الگوریتم زمان بندی RR چیست؟

اکنون نوبت به بیان معایب استفاده از الگوریتم زمان‌بندی راند رابین رسیده است. استفاده از این الگوریتم شامل معایب فهرست شده در زیر می‌شود.

• اگر «برش زمانی» (Slicing Time) در سیستم عامل کوتاه باشد، خروجی پردازنده هم کاهش پیدا می‌کند.
• در این روش زمان زیادی را برای «تغییر زمینه» صرف می‌کنیم.
• کارایی این الگوریتم به میزان بسیار زیادی به زمان کوانتوم وابسته است.
• برای فرایند‌ها امکان اختصاص اولویت وجود ندارد.
• الگوریتم راند رابین، اولویت خاصی را برای وظایف مهم‌تر قائل نمی‌شود.
• باعث کاهش قدرت درک برنامه می‌شود.
• زمان کوانتوم کوتاه‌تر، باعث افزایش سربار Context Switching می‌شود. در نتیجه کارایی سیستم را کاهش می‌دهد.
• پیدا کردن زمان کوانتوم صحیح در هر سیستم، وظیفه کاملا مشکلی است.

آشنایی با چند مورد از الگوریتم های مدرن

تا به اینجای مطلب با الگوریتم‌ راند رابین آشنا شده و نحوه کار و نوشتن آن را آموختیم. اما برای درک انواع تکنیک‌های تعریف و بهینه‌سازی الگوریتم‌ها به طور کلی، لازم است که با چند مورد دیگر از الگوریتم‌های مدرن و پیش‌رفته‌ نیز آشنا شویم. این الگوریتم‌ها بر روی انواع سیستم‌های حال حاضر جهان در حال استفاده‌اند. درک روش صحیح تعریف و پیاده‌سازی چنین الگوریتم‌هایی در پیاده‌سازی الگوریتم‌های شخصی خودمان کمک بسیار زیادی می‌کند.

فرادرس به عنوان پلتفرم آموزش آنلاین و تولید کننده محتوی ویدئویی در زمینه آموزش، تلاش می‌کند تمام جنبه‌های ممکن از هر صنعت، علم و هنری را با کمک فیلم‌های خود پوشش دهد. الگوریتم‌های زمان‌بندی هم جزو اهداف فرادرس برای آموزش و تولید فیلم مربوط به آن‌ها هستند. به همین منظور، فیلم‌های بسیار مناسبی در زمینه آشنایی و کار با انواع الگوریتم‌های در فرادرس آماده شده که در زیر، می‌توانید چند مورد از آن‌ها را مشاهده کنید.

• فیلم آموزش الگوریتم ژنتیک در متلب با فرادرس
• فیلم آموزش الگوریتم PSO در متلب با فرادرس
• فیلم آموزش بهینه سازی چند هدفه در متلب با فرادرس
• فیلم آموزش الگوریتم بهینه سازی گرگ خاکستری GWO و پیاده سازی در متلب با فرادرس
• فیلم رایگان آموزش الگوریتم بهینه سازی سیاه چاله BH در فرادرس

نکاتی که باید به خاطر داشته باشیم

در این قسمت از مطلب، نکاتی را بیان کرده‌ایم که به عنوان توسعه‌دهنده، در زمان پیاده‌سازی و استفاده این الگوریتم، باید در ذهن داشته باشید.

فیلم آموزش طراحی الگوریتم – جامع و با مفاهیم کلیدی در فرادرس

کلیک کنید

• اگر مقدار زمان کوانتوم رو به افزایش باشد، تکنیک زمان‌بندی راند رابین کم کم به تکنیک زمان‌بندی FCFS شبیه می‌‌شود.
• در این مورد، وقتی که میزان زمان کوانتوم میل به بینهایت پیدا کند، الگوریتم راند رابین به صورت کامل به الگوریتم FCFS تبدیل می‌شود.
• بنابراین عملکرد الگوریتم RR به صورت عمیقی وابسته به مقدار زمان کوانتوم است.
• پس مقدار زمان کوانتوم باید دارای حد متوسطی باشد. زیاد بزرگ و زیاد کوچک شدن این مقدار برای الگوریتم RR مناسب نیست.

افزایش و کاهش مقدار زمان کوانتوم را در ادامه با جزئیات بیشتری توضیح داده‌ایم.

کاهش مقدار زمان کوانتوم

کاهش مقدار زمان کوانتوم، تاثیرات خاصی بر روی عملکرد این الگوریتم می‌گذارد. برای کمک به درک بهتر مطلب، این تاثیرات را در فهرست زیر خلاصه کرده‌ایم.

• تعداد عملیات «تغییر زمینه» (Context Switches) افزایش پیدا می‌کند.
• میزان زمان پاسخ کاهش پیدا می‌کند.
• در این مورد احتمال بروز گرسنگی هم کاهش پیدا می‌کند.

در نتیجه استفاده از زمان کوانتوم کمتر می‌تواند باعث بهبود زمان پاسخ‌گویی برنامه شود و با سرعت بیشتری به هر برنامه نوبت اجرا برسد.

افزایش مقدار زمان کوانتوم

افزایش مقدار زمان کوانتوم نیز تاثیرات خاصی بر روی عملکرد این الگوریتم می‌گذارد. برای کمک به درک بهتر این مطلب، تاثیرات مورد اشاره را در فهرست زیر خلاصه کرده‌ایم.

• تعداد عملیات «تغییر زمینه» (Context Switches) کاهش پیدا می‌کند.
• میزان زمان پاسخ افزایش پیدا می‌کند.
• در این مورد احتمال بروز گرسنگی هم افزایش پیدا می‌کند.

در نتیجه استفاده از زمان کوانتوم بیشتر، می‌تواند باعث کاهش تعداد عملیات تغییر زمینه شود. این اتفاق هم باعث ارتقای عملکرد کلی سیستم می‌شود.

بدترین حالت دیرکرد

عبارت «بدترین حالت دیرکرد» (Worst Case Latency) برای بیشترین زمانی به‌کار می‌رود که برای اجرای همه وظایف لازم است.

• dt: این عبارت مخفف واژه انگلیسی «Detection Time» است و اشاره به زمانی دارد که برای آوردن وظیفه‌ای به لیست صرف می‌شود.
• st: این عبارت مخفف واژه انگلیسی «Switching Time» است و اشاره به زمانی دارد که برای انتقال از روی فرایند در حال اجرا به فرایند بعدی برای اجرا، صرف می‌شود.
• et: این عبارت مخفف واژه انگلیسی «Execution Time» است و اشاره به زمان مورد نیاز برای اجرای هر فرایند دارد.

$$T_{worst} = \left\{(dt_{i}+ st_{i} + et_{i} ) + (dt_{i}+ st_{i} + et_{i} )_{2} +...+ (dt_{i}+ st_{i} + et_{i} )_{N} + (dt_{i}+ st_{i} + et_{i} + et_{i}) N\right\} + t_{ISR}$$

با کمک فرمول بالا می‌توان زمان مورد نیاز «بدترین حالت تاخیر» اجرای فرایند‌ها توسط این عملکرد را بدست آورد.

جمع بندی

در این مطلب از مجله فرادرس با الگوریتم راند رابین یا RR آشنا شدیم. نام این الگوریتم از «اصل راند رابین» (Round-Robin Principle) گرفته شده است. در این اصل هر کسی در نوبت خودش، سهمی به میزان مساوی با بقیه بدست می‌آورد. الگوریتم RR یکی از قدیمی‌ترین الگوریتم‌هایی است که به صورت بسیار ساده و عادلانه برای زمان‌بندی اجرای فرایند‌ها توسط سیستم عامل‌های سنتی به‌کار برده می‌شود. این الگوریتم از نوع الگوریتم‌های غیر انحصاری است. یعنی هیچ وقت CPU به صورت تمام و کمال به هیچ فرایندی اختصاص داده نمی‌شود.

فیلم مجموعه آموزش ساختمان داده و طراحی الگوریتم – از دروس دانشگاهی تا کاربردی در فرادرس

کلیک کنید

یکی از بهترین نکات الگوریتم RR این است که با دانستن تعداد دقیق فرایند‌های در صف آماده، می‌توانیم بدترین حالت دیرکرد را برای هر فرایند محاسبه کنیم. اما در عین حال این متد زمان زیادی را هم صرف تغییر زمینه می‌کند. توسعه‌دهندگان و مخصوصا متخصصان سیستم عامل باید به روال کاری الگوریتم‌های توسعه‌دهنده مسلط باشند تا با انتخاب بهترین مورد بتوانند، سرعت عملکرد سیستم‌های خود را افزایش دهند.