الگوریتم FCFS چیست؟ – توضیح به زبان ساده با مثال و کد

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

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

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

الگوریتم FCFS یکی از الگوریتم‌های زمان‌بندی است. اما برای اینکه به صورت دقیق‌تری بدانیم الگوریتم FCFS چیست، مهم‌ترین ویژگی‌های این الگوریتم را در فهرست زیر به صورت خلاصه و دقیق بیان کرده‌ایم.

فیلم آموزش الگوریتم زمانبندی FCFS + پیاده‌ سازی در جاوا JAVA در فرادرس

کلیک کنید

• این الگوریتم به سیستم عامل‌ها و شبکه‌ها کمک می‌کند که به صورت خودکار و کارآمد، وظایف محوله خود را پردازش کرده و درخواست‌ها را با همان ترتیب وارد شده به صف آماده، پاسخ دهند.
• الگوریتم FCFS را با نام‌های الگوریتم «اولین ورود، اولین خروج» (First-In, First-Out) با واژه مخفف FIFO یا «اولین ورود، اولین انتخاب» (First-Come, First-Choice) با واژه مخفف FCFC نیز می‌شناسند.
• الگوریتم‌های FCFS بخاطر سادگی که دارند وظایف ارسال شده را به صورت قابل پیش‌بینی انجام می‌دهند.
• الگوریتم‌های FCFS از روی موقعیت‌های مربوط به خدمات مشتری در دنیای واقعی - مانند صف خرید کالا در فروشگاه‌ها - شبیه‌سازی شده‌اند. زیرا در این حالت زمان برای رتبه‌بندی وظایف بر اساس مقدار پیچیدگی یا اولویت آن‌ها تلف نمی‌شود.
• در نتیجه الگوریتم FCFS در میان خودمختارترین و بهره‌ورترین الگوریتم‌های زمان‌بندی، دسته‌بندی می‌شود.

نوشتن الگوریتم با کمک فرادرس

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

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

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

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

روش کار الگوریتم FCFS چیست؟

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

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

کلیک کنید

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

در ادامه این بخش با کمک مثالی ساده‌ و کوچک خواهیم دید که روش کار الگوریتم FCFS چیست ولی در ابتدا با کلمات کلیدی رایج در الگوریتم‌های زمان‌بندی آشنا می‌شویم.

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

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

• «زمان رسیدن» (Arrival Time | AT): به زمانی گفته می‌شود که فرایند به «صف آماده به اجرا» یا به صورت خلاصه «صف آماده‌» وارد می‌شود.
• «زمان انجام فعالیت» (Burst Time | BT): زمان انجام فعالیت، به میزان واحد زمانی گفته می‌شود که هر فرایند برای تکمیل اجرای فعالیت خود به صورت کامل به آن نیاز دارد. به زمان مورد نیاز CPU برای اجرای هر پردازش به صورت کامل هم می‌توان گفت.
• «زمان تکمیل عملیات» (Completion Time | CT): زمان تکمیل عملیات به زمانی گفته می‌شود که علمیات پردازش یک فرایند به طور کامل به پایان رسیده و از CPU خارج می‌شود.
• «زمان مورد نیاز برای انجام فعالیت» (Turn-around Time | TAT): به مقدار زمان بین رسیدن یک فرایند به صف آماده تا پایان تکمیل عملیات، زمان مورد نیاز برای انجام فعالیت گفته می‌شود.
• «زمان انتظار» (Waiting Time | WT): زمان انتظار به میزان زمانی گفته می‌شود که فرایند بعد از رسیدن به صف آماده باید تا رسیدن به CPU صبر کند. در این زمان CPU حتما توسط فرایند دیگری اشغال شده است.
• «زمان پاسخ» (Response Time | RT): زمان پاسخ به میزان زمانی گفته می‌شود که از لحظه رسیدن فرایند به صف آماده تا لحظه‌ای که CPU برای اولین بار به فرایند اختصاص داده می‌شود، طول می‌کشد. در الگوریتم‌های «انحصاری» (Non-Preemptive) این زمان با زمان انتظار برابر است.
• نمودار Gantt: مصورسازی داده‌هایی است که با کمک آن‌ها زمان‌بندی و مدیریت وظایف مشخص در پروژه ممکن می‌شود. در هنگام حل کردن مسائل زمان‌بندی از این نمودار استفاده می‌شود. با کمک این نمودار می‌توان درکی از روش تخصیص CPU به الگوریتم‌های مختلف بدست آورد.

مثالی برای درک روش کار الگوریتم FCFS

در این بخش برای بهتر متوجه شدن روش کار الگوریتم FCFS، مثالی را به صورت مصور نمایش داده‌ایم. در مثال زیر، ۵ فرایند مجزا از هم داریم که هر کدام زمان انجام فعالیت مختلفی دارند.

با استفاده از الگوریتم FCFS این فرایند‌ها به صورتی مدیریت می‌شوند که در ادامه توضیح داده‌ایم.

مرحله اول: عملیات تخصیص CPU با فرایند P4 شروع می‌شود. زیرا این فرایند در زمان ۰ به صف آماده وارد شده است. در واقع اولین عملیات در صف است.

مرحله دوم: در زمان ۱، P3 به صف آماده می‌رسد. فرایند P4 هنوز در حال پردازش است. بنابراین P3 باید در صف آماده نگهداشته شود.

در تصویر زیر نمودار Gantt را می‌بینید که کم کم در حال پُر شدن است.

مرحله سوم: در زمان ۲، فرایند P1 به صف می‌رسد، این فرایند هم باید در صف نگهداشته شود.

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

مرحله چهارم: در زمان ۳، اجرای فرایند P4 کامل شده است. یا به عبارت دیگر، زمان تکمیل عملیات P4 رسیده است.

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

در تصویر زیر، هم فرایندهای درون صف آماده - P1 و P5 - را می‌بینید و هم اینکه فرایند P3 وارد نمودار Gantt شده است.

مرحله ششم: در زمان ۵، فرایند P2 می‌رسد و در صف نگهداشته می‌شود.

در تصویر زیر هم فرایندهای موجود در صف آماده دیده می‌شوند و هم نمودار Gantt را می‌تواند در زمان ۵ دید.

مرحله هفتم: در زمان ۱۱، عملیات فرایند P3 به پایان رسیده و از CPU خارج می‌شود. یعنی زمان CT برای P3 برابر با ۱۱ است.

مرحله هشتم: در زمان ۱۱ همزمان با خروج فرایند P3 از پردازنده، فرایند P1، سی پی یو را در اختیار گرفته و اجرای فعالیت خود را شروع می‌کند. از آنجا که زمان انجام فعالیت یا BT برای P1 برابر با ۶ واحد زمانی است، پس تکمیل عملیات این فرایند در زمان ۱۷ به پایان می‌رسد.

مرحله نهم: در زمان ۱۷، تکمیل عملیات فرایند P1 به پایان رسیده و فرایند P5 شروع به اجرای فعالیت خود می‌کند. از آنجا که زمان انجام فعالیت برای این فرایند به اندازه ۴ واحد زمانی طول می‌کشد، تکمیل عملیات فرایند P1 در زمان ۲۱ انجام می‌شود.

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

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

«زمان انتظار» (Waiting Time) = «زمان رسیدن» (Arrival Time) - «زمان شروع پردازش» (Start Time)

با توجه به محاسبات پایین:

• P4 = 0-0 = 0
• P3 = 3-1 = 2
• P1 = 11-2 = 9
• P5= 17-4 = 13
• P2= 21-5= 16

میانگین زمان انتظار برابر با مقدار زیر می‌شود.

$$\frac{0+2+9+13+16}{5} =\frac{40}{5}=8$$

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

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

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

کلیک کنید

کدهای الگوریتم FCFS در زبان ++C

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

1#include <iostream>
2using namespace std;
3
4// Function to Calculate waiting time
5// and average waiting time
6void CalculateWaitingTime(int at[],
7						int bt[], int N)
8{
9
10	// Declare the array for waiting
11	// time
12	int wt[N];
13
14	// Waiting time for first process
15	// is 0
16	wt[0] = 0;
17
18	// Print waiting time process 1
19	cout << "PN\t\tAT\t\t"
20		<< "BT\t\tWT\n\n";
21	cout << "1"
22		<< "\t\t" << at[0] << "\t\t"
23		<< bt[0] << "\t\t" << wt[0] << endl;
24
25	// Calculating waiting time for
26	// each process from the given
27	// formula
28	for (int i = 1; i < 5; i++) {
29		wt[i] = (at[i - 1] + bt[i - 1]
30				+ wt[i - 1]) - at[i];
31
32		// Print the waiting time for
33		// each process
34		cout << i + 1 << "\t\t" << at[i]
35			<< "\t\t" << bt[i] << "\t\t"
36			<< wt[i] << endl;
37	}
38
39	// Declare variable to calculate
40	// average
41	float average;
42	float sum = 0;
43
44	// Loop to calculate sum of all
45	// waiting time
46	for (int i = 0; i < 5; i++) {
47		sum = sum + wt[i];
48	}
49
50	// Find average waiting time
51	// by dividing it by no. of process
52	average = sum / 5;
53
54	// Print Average Waiting Time
55	cout << "\nAverage waiting time = "
56		<< average;
57}
58
59// Driver code
60int main()
61{
62	// Number of process
63	int N = 5;
64
65	// Array for Arrival time
66	int at[] = { 0, 1, 2, 3, 4 };
67
68	// Array for Burst Time
69	int bt[] = { 4, 3, 1, 2, 5 };
70
71	// Function call to find
72	// waiting time
73	CalculateWaitingTime(at, bt, N);
74	return 0;
75}

کدهای الگوریتم FCFS در زبان جاوا

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

فیلم آموزش الگوریتم زمانبندی FCFS + پیاده‌ سازی در جاوا JAVA در فرادرس

کلیک کنید

با کمک این کدها می‌توانید روش کار الگوریتم FCFS را در کامپیوتر خود بررسی کنید.

1#include <iostream>
2using namespace std;
3
4// Function to Calculate waiting time
5// and average waiting time
6void CalculateWaitingTime(int at[],
7						int bt[], int N)
8{
9
10	// Declare the array for waiting
11	// time
12	int wt[N];
13
14	// Waiting time for first process
15	// is 0
16	wt[0] = 0;
17
18	// Print waiting time process 1
19	cout << "PN\t\tAT\t\t"
20		<< "BT\t\tWT\n\n";
21	cout << "1"
22		<< "\t\t" << at[0] << "\t\t"
23		<< bt[0] << "\t\t" << wt[0] << endl;
24
25	// Calculating waiting time for
26	// each process from the given
27	// formula
28	for (int i = 1; i < 5; i++) {
29		wt[i] = (at[i - 1] + bt[i - 1]
30				+ wt[i - 1]) - at[i];
31
32		// Print the waiting time for
33		// each process
34		cout << i + 1 << "\t\t" << at[i]
35			<< "\t\t" << bt[i] << "\t\t"
36			<< wt[i] << endl;
37	}
38
39	// Declare variable to calculate
40	// average
41	float average;
42	float sum = 0;
43
44	// Loop to calculate sum of all
45	// waiting time
46	for (int i = 0; i < 5; i++) {
47		sum = sum + wt[i];
48	}
49
50	// Find average waiting time
51	// by dividing it by no. of process
52	average = sum / 5;
53
54	// Print Average Waiting Time
55	cout << "\nAverage waiting time = "
56		<< average;
57}
58
59// Driver code
60int main()
61{
62	// Number of process
63	int N = 5;
64
65	// Array for Arrival time
66	int at[] = { 0, 1, 2, 3, 4 };
67
68	// Array for Burst Time
69	int bt[] = { 4, 3, 1, 2, 5 };
70
71	// Function call to find
72	// waiting time
73	CalculateWaitingTime(at, bt, N);
74	return 0;
75}

کدهای الگوریتم FCFS در زبان پایتون

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

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

1def CalculateWaitingTime(at, bt, N):
2
3	# Declare the array for waiting
4	# time
5	wt = [0]*N;
6
7	# Waiting time for first process
8	# is 0
9	wt[0] = 0;
10
11	# Print waiting time process 1
12	print("P.No.\tArrival Time\t" , "Burst Time\tWaiting Time");
13	print("1" , "\t\t" , at[0] , "\t\t" , bt[0] , "\t\t" , wt[0]);
14
15	# Calculating waiting time for
16	# each process from the given
17	# formula
18	for i in range(1,5):
19		wt[i] = (at[i - 1] + bt[i - 1] + wt[i - 1]) - at[i];
20
21		# Print the waiting time for
22		# each process
23		print(i + 1 , "\t\t" , at[i] , "\t\t" , bt[i] , "\t\t" , wt[i]);
24	
25
26	# Declare variable to calculate
27	# average
28	average = 0.0;
29	sum = 0;
30
31	# Loop to calculate sum of all
32	# waiting time
33	for i in range(5):
34		sum = sum + wt[i];
35	
36	# Find average waiting time
37	# by dividing it by no. of process
38	average = sum / 5;
39
40	# Print Average Waiting Time
41	print("Average waiting time = " , average);
42
43
44# Driver code
45if __name__ == '__main__':
46	# Number of process
47	N = 5;
48
49	# Array for Arrival time
50	at = [ 0, 1, 2, 3, 4 ];
51
52	# Array for Burst Time
53	bt = [ 4, 3, 1, 2, 5 ];
54
55	# Function call to find
56	# waiting time
57	CalculateWaitingTime(at, bt, N);

کدهای الگوریتم FCFS در زبان #C

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

1using System;
2
3class GFG
4{
5
6// Function to Calculate waiting time
7// and average waiting time
8static void CalculateWaitingTime(int []at,
9						int []bt, int N)
10{
11
12	// Declare the array for waiting
13	// time
14	int []wt = new int[N];
15
16	// Waiting time for first process
17	// is 0
18	wt[0] = 0;
19
20	// Print waiting time process 1
21	Console.Write("P.No.\tArrival Time\t"
22		+ "Burst Time\tWaiting Time\n");
23	Console.Write("1"
24		+ "\t\t" + at[0]+ "\t\t"
25		+ bt[0]+ "\t\t" + wt[0] +"\n");
26
27	// Calculating waiting time for
28	// each process from the given
29	// formula
30	for (int i = 1; i < 5; i++) {
31		wt[i] = (at[i - 1] + bt[i - 1] + wt[i - 1]) - at[i];
32
33		// Print the waiting time for
34		// each process
35		Console.Write(i + 1+ "\t\t" + at[i]
36			+ "\t\t" + bt[i]+ "\t\t"
37			+ wt[i] +"\n");
38	}
39
40	// Declare variable to calculate
41	// average
42	float average;
43	float sum = 0;
44
45	// Loop to calculate sum of all
46	// waiting time
47	for (int i = 0; i < 5; i++) {
48		sum = sum + wt[i];
49	}
50
51	// Find average waiting time
52	// by dividing it by no. of process
53	average = sum / 5;
54
55	// Print Average Waiting Time
56	Console.Write("Average waiting time = "
57		+ average);
58}
59
60// Driver code
61public static void Main(String[] args)
62{
63	// Number of process
64	int N = 5;
65
66	// Array for Arrival time
67	int []at = { 0, 1, 2, 3, 4 };
68
69	// Array for Burst Time
70	int []bt = { 4, 3, 1, 2, 5 };
71
72	// Function call to find
73	// waiting time
74	CalculateWaitingTime(at, bt, N);
75}
76}

کدهای الگوریتم FCFS در زبان جاوا اسکریپت

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

1function calculateWaitingTime(at, bt, n) {
2// Declare the array for waiting time
3let wt = new Array(n);
4
5// Waiting time for first process is 0
6wt[0] = 0;
7
8// Print waiting time for process 1
9console.log("PN\t\tAT\t\tBT\t\tWT\n\n");
10console.log(`1\t\t${at[0]}\t\t${bt[0]}\t\t${wt[0]}\n`);
11
12// Calculate waiting time for each process from the given formula
13for (let i = 1; i < n; i++) {
14	wt[i] = (at[i - 1] + bt[i - 1] + wt[i - 1]) - at[i];
15
16	// Print the waiting time for each process
17	console.log(`${i + 1}\t\t${at[i]}\t\t${bt[i]}\t\t${wt[i]}\n`);
18}
19
20// Declare variable to calculate average
21let average;
22let sum = 0;
23
24// Loop to calculate sum of all waiting time
25for (let i = 0; i < n; i++) {
26	sum = sum + wt[i];
27}
28
29// Find average waiting time by dividing it by no. of process
30average = sum / n;
31
32// Print Average Waiting Time
33console.log(`\nAverage waiting time = ${average}`);
34}
35
36// Driver code
37function main() {
38// Number of processes
39let n = 5;
40
41// Array for arrival time
42let at = [0, 1, 2, 3, 4];
43
44// Array for burst time
45let bt = [4, 3, 1, 2, 5];
46
47// Function call to find waiting time
48calculateWaitingTime(at, bt, n);
49}
50
51// Call the main function
52main();

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

P.No.	Arrival Time	 Burst Time	Waiting Time
1 		 0 		 4 		 0
2 		 1 		 3 		 3
3 		 2 		 1 		 5
4 		 3 		 2 		 5
5 		 4 		 5 		 6
Average waiting time =  3.8

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

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

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

• فیلم آموزش مبانی محاسبات تکاملی و بهینه سازی هوشمند با فرادرس
• فیلم آموزش مقدماتی پیاده سازی مسائل بهینه سازی در پایتون با فرادرس
• فیلم آموزش الگوریتم بهینه سازی ملخ GOA و پیاده سازی آن در MATLAB با فرادرس
• فیلم آموزش الگوریتم بهینه سازی گرگ خاکستری GWO و پیاده سازی در متلب با فرادرس
• فیلم رایگان آموزش الگوریتم بهینه سازی سیاه چاله BH در فرادرس

ویژگی ها، مزایا و معایب الگوریتم FCFS

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

فیلم آموزش الگوریتم زمانبندی FCFS + پیاده‌ سازی در جاوا JAVA در فرادرس

کلیک کنید

ویژگی های الگوریتم FCFS

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

1. پیاده‌سازی این الگوریتم بسیار ساده است.
2. در زمان استفاده شامل هیچ مشکل خاصی نمی‌شود.
3. این الگوریتم را می‌توان با استراتژی‌های غیرانحصاری و انحصاری سازگار کرد.
4. هر فرایند را با همان ترتیبی که رسیده است، اجرا می‌کند.
5. زمان رسیدن به عنوان معیار انتخاب برای فرایندها استفاده می‌شود.

رویکرد غیر انحصاری

در حالت «زمان‌بندی غیر انحصاری پردازش‌ها» (Pre Emptive Process Scheduling)، سیستم عامل منابع را به هر فرایند به اندازه بازه زمانی مشخصی اختصاص می‌دهد. در طول این زمان، فرایند می‌تواند از حالت اجرا به حالت آماده یا از حالت انتظار به حالت آماده تغییر وضعیت دهد. علت اصلی روی دادن این تغییر وضعیت این است که در زمان اجرا ممکن است CPU اولویت بالاتری را به فرایند دیگری بدهد. در نتیجه، فرایند در حال اجرا را با فرایند دیگری جایگزین می‌کند.

رویکرد انحصاری

در رویکرد «زمان‌بندی انحصاری پردازش‌ها» (Non Pre Emptive Process Scheduling) منابع را نمی‌توان تا زمان به پایان رسیدن انجام کامل فرایند‌ها از آن‌ها گرفت. وقتی که فرایند در حال اجرا، به پایان می‌رسد و به حالت انتظار منتقل می‌شود، منابع آزاد شده و به فرایند دیگری اختصاص داده می‌شوند.

مزایای الگوریتم FCFS

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

1. با هدف تخصیص منابع از صف شناخته شده «اولین ورودی، اولین خروجی» یا «FIFO» استفاده می‌کند.
2. فرایند زمان‌بندی پردازنده با روش FCFS، بسیار سرراست است و پیاده‌سازی ساده‌ای هم دارد.
3. به دلیل رویکرد انحصاری الگوریتم FCFS در ارسال فرایند‌ها به CPU، هیچ احتمالی برای وقوع گرسنگی وجود ندارد.
4. از آنجا که هیچ ملاحظه‌ای درباره اولویت‌های فرایند‌ها انجام نمی‌شود، FCFS به عنوان الگوریتمی منصفانه شناخته می‌شود.

معایب الگوریتم FCFS

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

1. الگوریتم زمان‌بندی FCFS دارای زمان انتظار بسیار زیادی است.
2. اگلوریتم زمان‌بندی FCFS پردازش‌های CPU را نسبت به پردازش‌های مربوط به عملیات ورودی و خروجی سیستم ارجح می‌داند.
3. احتمال روی دادن مشکل Convoy Effect یا «اثر کاروان» در این الگوریتم زیاد است.
4. از آن‌جا که تکنیک FCFS برای زمان‌بندی CPU بسیار سرراست و ساده است، معمولا خیلی موثر واقع نمی‌شود. این الگوریتم می‌تواند باعث به وجود آمدن زمان‌های انتظار بسیار طولانی شود. اگر CPU مشغول اجرای وظیفه زمان‌بری شود باقی فرایندها به صورت بیکار و منتظر باقی می‌مانند.

اثر کاروان در الگوریتم FCFS

«اثر کاروان» (The Convoy Effect) یکی از نقاط ضعف این الگوریتم است. برای درک این مفهوم، موقعیتی از دنیای واقعی را در نظر بگیرید که کاروانی از وسایل نقیله در حال مسافرت با هم به صورت یک واحد منسجم و حتی به هم متصل هستند. اگر در این کاروان یکی از وسایل نقلیه با سرعت بسیار کندی حرکت کند، سایر وسایل نقلیه پشت سر آن نیز سرعت خود را از دست می‌دهند. در نتیجه بقیه کاروان هم باید با سرعت این وسیله حرکت کرده و سرعت کلی کاروان کاهش پیدا می‌کند.

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

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

جمع بندی

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

• FCFS الگوریتمی است که به صورت خودکار درخواست‌های صف‌بندی شده را به ترتیبی که رسیده‌اند اجرا می‌کند.
• این الگوریتم از هردو حالت زمان‌بندی غیر انحصاری و انحصاری پشتیبانی می‌کند.
• FCFS ساده‌ترین مورد در بین الگوریتم‌های زمان‌بندی است.

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

کلیک کنید

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