در «الگوریتم زمان‌بندی آسانسور» (Elevator Disk Scheduling Algorithm)یا SCAN، سر دیسک حرکت خود را از یک سمت انتهایی دیسک شروع کرده و به سمت انتهای دیگر حرکت می‌کند. در طول حرکت خود تمام درخواست‌های موجود در شیارهای دیسک را یک به یک تا زمان رسیدن به سر دیگر پردازش می‌کند. سپس در انتهای دیسک جهت حرکت سر برعکس شده و همین رفتار تکرار می‌شود. الگوریتم‌های زمان‌بندی بخش مهمی از سیستم‌های کامپیوتری مدرن هستند. کیفیت این الگوریتم‌ها به صورت مستقیم بر روی کارایی کل فرایند‌های سیستم تاثیر می‌گذارد. تقاضای دائمی و ثابت برای سیستم‌هایی با اجرای بهتر عملیات I/O و فراخوانی سریع‌تر داده، فرایند توسعه انواع الگوریتم‌ها را ضروری ساخته است. این الگوریتم‌ها برای زمان‌بندی اجرای نوبتی عملیات بر روی دیسک‌ استفاده می‌شوند. علاوه‌بر این، کارایی سیستم‌ها به طرز چشم‌گیری از انتخاب الگوریتم‌ها تاثیر می‌گیرد. الگوریتم آسانسور یکی از الگوریتم‌های مخصوص زمان‌بندی دیسک است.

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

الگوریتم آسانسور چیست؟

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

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

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

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

فراگیری طراحی الگوریتم با کمک فرادرس

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

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

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

الگوریتم آسانسور چگونه کار می‌کند؟

دو اصل عملیاتی مهم، روال کاری الگوریتم آسانسور را هدایت می‌کنند.

1. حرکت شبیه آسانسور
2. انتخاب بر اساس اولویت

حرکت شبیه آسانسور

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

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

انتخاب بر اساس اولویت

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

شبه کد الگوریتم SCAN

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

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

algorithm SCANScheduling(queue, initial_position, direction):
    if direction = "right":
        queue = queue.append(0)
    else:
        queue = queue.append(disk_size - 1)
    
    sort(queue)  // Sort the queue in ascending order
    
    While queue is not empty:
        If direction = "right":
            current_position <- initial_position
            while current_position <= maximum_position:
                for request in queue:
                    if request >= current_position:
                        process_request(request)
                        current_position <- request
                        remove request from queue
                        break
                current_position <- current_position + 1
            direction <- "left"  // Change direction to left
        
        if direction = "left":
            current_position <- initial_position
            while current_position >= minimum_position:
                for request in reversed(queue):
                    if request <= current_position:
                        process_request(request)
                        current_position <- request
                        remove request from queue
                        break
                current_position = current_position - 1
            direction = "right"  // change direction to right

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

توضیح

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

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

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

مثالی برای درک بهتر الگوریتم آسانسور

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

برای کمک به درک بهتر روش کار این الگوریتم در این بخش مثال ساده‌ای را ارائه داده‌ایم. دیسک مورد استفاده در این مثال، شامل ۲۵۱ شیار می‌شود. صف درخواست‌های ارسال شده به دیسک به صورت زیر  است.

{240, 94, 179, 51, 118, 15, 137, 29 , 75}

در ابتدای کار فرض می‌کنیم که سر دیسک برای اجرای عملیات خواندن و نوشتن بر روی شیار ۵۵ به نام C قرار گرفته و به سمت راست حرکت می‌کند.

حرکت سر دیسک به سمت راست در آخرین شیار – برابر با شماره ۲۵۰ – متوقف می‌شود. حتی با اینکه هیچ درخواستی در شیار ۲۵۰ وجود ندارد. سپس مسیر حرکت را تغییر داده و حرکت خود را روی آخرین درخواست در شیار ۱۵ به پایان می‌رساند. بنابر این «مجموع حرکات سر» (Total Head Movement | THM) برابر با مقدار محاسبه شده در زیر است.

$$THM = (250-55) + (250-15) = 195 + 235 = 430$$

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

در حرکت سر به سمت چپ هم با اینکه هیچ درخواستی در انتهای دیسک وجود ندارد، اما تا به آنجا ادامه پیدا کرده و در انتهای دیسک متوقف می‌شود. یعنی بر روی شیار شماره ۰ و بعد از آن تغییر جهت داده و تا شیار شمار ۲۴۰ که محل آخرین درخواست است به پیش می‌رود. بنابراین مجموع حرکات سر با این جهت اولیه، برابر با مقدار محاسبه شده در زیر است.

$$THM = (55-0) + (240-0) = 55 + 240 = 295$$

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

پیاده‌سازی الگوریتم زمان بندی آسانسور

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

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

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

Request sequence = {176, 79, 34, 60, 92, 11, 41, 114}
Initial head position = 50
Direction = left (We are moving from right to left)

الگوریتم بعد از اجرای عملیات خود باید خروجی به صورت زیر داشته باشد.

Total number of seek operations = 226
Seek Sequence is
41
34
11
0
60
79
92
114
176

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

در نتیجه مجموع مسافت طی شده برای رسیدگی به همه درخواست‌ها به صورت زیر محاسبه می‌شود.

= (50-41) + (41-34) + (34-11) + (11-0) + (60-0) + (79-60) + (92-79) + (114-92) + (176-114)
= 226

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

در این بخش از مطلب، الگوریتم زمان‌بندی آسانسور را با کمک پنج زبان برنامه نویسی مختلف کدنویسی کرده‌ایم. توجه کنید که در کدهای پیاده‌سازی شده متغیر distance برای ذخیره‌سازی قدر مطلق فاصله بین سر دیسک و مکان شیار درخواست بعدی استفاده شده است. متغیر disk_size اندازه دیسک را نمایش می‌دهد. Vector left و Vector right به ترتیب برای ذخیره‌سازی درخواست‌های سمت چپ و راست مکان اولیه سر دیسک استفاده شده‌اند.

پیاده سازی الگوریتم آسانسور در زبان ++C

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

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

1// C++ program to demonstrate
2// SCAN Disk Scheduling algorithm
3
4#include <bits/stdc++.h>
5using namespace std;
6
7int size = 8;
8int disk_size = 200;
9
10void SCAN(int arr[], int head, string direction)
11{
12	int seek_count = 0;
13	int distance, cur_track;
14	vector<int> left, right;
15	vector<int> seek_sequence;
16
17	// appending end values
18	// which has to be visited
19	// before reversing the direction
20	if (direction == "left")
21		left.push_back(0);
22	else if (direction == "right")
23		right.push_back(disk_size - 1);
24
25	for (int i = 0; i < size; i++) {
26		if (arr[i] < head)
27			left.push_back(arr[i]);
28		if (arr[i] > head)
29			right.push_back(arr[i]);
30	}
31
32	// sorting left and right vectors
33	std::sort(left.begin(), left.end());
34	std::sort(right.begin(), right.end());
35
36	// run the while loop two times.
37	// one by one scanning right
38	// and left of the head
39	int run = 2;
40	while (run--) {
41		if (direction == "left") {
42			for (int i = left.size() - 1; i >= 0; i--) {
43				cur_track = left[i];
44
45				// appending current track to seek sequence
46				seek_sequence.push_back(cur_track);
47
48				// calculate absolute distance
49				distance = abs(cur_track - head);
50
51				// increase the total count
52				seek_count += distance;
53
54				// accessed track is now the new head
55				head = cur_track;
56			}
57			direction = "right";
58		}
59		else if (direction == "right") {
60			for (int i = 0; i < right.size(); i++) {
61				cur_track = right[i];
62				// appending current track to seek sequence
63				seek_sequence.push_back(cur_track);
64
65				// calculate absolute distance
66				distance = abs(cur_track - head);
67
68				// increase the total count
69				seek_count += distance;
70
71				// accessed track is now new head
72				head = cur_track;
73			}
74			direction = "left";
75		}
76	}
77
78	cout << "Total number of seek operations = "
79		<< seek_count << endl;
80
81	cout << "Seek Sequence is" << endl;
82
83	for (int i = 0; i < seek_sequence.size(); i++) {
84		cout << seek_sequence[i] << endl;
85	}
86}
87
88// Driver code
89int main()
90{
91
92	// request array
93	int arr[size] = { 176, 79, 34, 60,
94					92, 11, 41, 114 };
95	int head = 50;
96	string direction = "left";
97
98	SCAN(arr, head, direction);
99
100	return 0;
101}

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

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

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

1// Java program to demonstrate
2// SCAN Disk Scheduling algorithm
3import java.util.*;
4
5class GFG
6{
7
8static int size = 8;
9static int disk_size = 200;
10
11static void SCAN(int arr[], int head, String direction)
12{
13	int seek_count = 0;
14	int distance, cur_track;
15	Vector<Integer> left = new Vector<Integer>(),
16					right = new Vector<Integer>();
17	Vector<Integer> seek_sequence = new Vector<Integer>();
18
19	// appending end values
20	// which has to be visited
21	// before reversing the direction
22	if (direction == "left")
23		left.add(0);
24	else if (direction == "right")
25		right.add(disk_size - 1);
26
27	for (int i = 0; i < size; i++) 
28	{
29		if (arr[i] < head)
30			left.add(arr[i]);
31		if (arr[i] > head)
32			right.add(arr[i]);
33	}
34
35	// sorting left and right vectors
36	Collections.sort(left);
37	Collections.sort(right);
38
39	// run the while loop two times.
40	// one by one scanning right
41	// and left of the head
42	int run = 2;
43	while (run-- >0)
44	{
45		if (direction == "left") 
46		{
47			for (int i = left.size() - 1; i >= 0; i--) 
48			{
49				cur_track = left.get(i);
50
51				// appending current track to seek sequence
52				seek_sequence.add(cur_track);
53
54				// calculate absolute distance
55				distance = Math.abs(cur_track - head);
56
57				// increase the total count
58				seek_count += distance;
59
60				// accessed track is now the new head
61				head = cur_track;
62			}
63			direction = "right";
64		}
65		else if (direction == "right") 
66		{
67			for (int i = 0; i < right.size(); i++) 
68			{
69				cur_track = right.get(i);
70				
71				// appending current track to seek sequence
72				seek_sequence.add(cur_track);
73
74				// calculate absolute distance
75				distance = Math.abs(cur_track - head);
76
77				// increase the total count
78				seek_count += distance;
79
80				// accessed track is now new head
81				head = cur_track;
82			}
83			direction = "left";
84		}
85	}
86
87	System.out.print("Total number of seek operations = "
88						+ seek_count + "n");
89
90	System.out.print("Seek Sequence is" + "n");
91
92	for (int i = 0; i < seek_sequence.size(); i++)
93	{
94		System.out.print(seek_sequence.get(i) + "n");
95	}
96}
97
98// Driver code
99public static void main(String[] args)
100{
101
102	// request array
103	int arr[] = { 176, 79, 34, 60,
104					92, 11, 41, 114 };
105	int head = 50;
106	String direction = "left";
107
108	SCAN(arr, head, direction);
109}
110}

پیاده سازی الگوریتم آسانسور در زبان پایتون

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

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

1# Python3 program to demonstrate
2# SCAN Disk Scheduling algorithm
3size = 8
4disk_size = 200
5
6def SCAN(arr, head, direction):
7
8	seek_count = 0
9	distance, cur_track = 0, 0
10	left = []
11	right = []
12	seek_sequence = []
13
14	# Appending end values
15	# which has to be visited
16	# before reversing the direction
17	if (direction == "left"):
18		left.append(0)
19	elif (direction == "right"):
20		right.append(disk_size - 1)
21
22	for i in range(size):
23		if (arr[i] < head):
24			left.append(arr[i])
25		if (arr[i] > head):
26			right.append(arr[i])
27
28	# Sorting left and right vectors
29	left.sort()
30	right.sort()
31
32	# Run the while loop two times.
33	# one by one scanning right
34	# and left of the head
35	run = 2
36	while (run != 0):
37		if (direction == "left"):
38			for i in range(len(left) - 1, -1, -1):
39				cur_track = left[i]
40
41				# Appending current track to 
42				# seek sequence
43				seek_sequence.append(cur_track)
44
45				# Calculate absolute distance
46				distance = abs(cur_track - head)
47
48				# Increase the total count
49				seek_count += distance
50
51				# Accessed track is now the new head
52				head = cur_track
53			
54			direction = "right"
55	
56		elif (direction == "right"):
57			for i in range(len(right)):
58				cur_track = right[i]
59				
60				# Appending current track to seek 
61				# sequence
62				seek_sequence.append(cur_track)
63
64				# Calculate absolute distance
65				distance = abs(cur_track - head)
66
67				# Increase the total count
68				seek_count += distance
69
70				# Accessed track is now new head
71				head = cur_track
72			
73			direction = "left"
74		
75		run -= 1
76
77	print("Total number of seek operations =", 
78		seek_count)
79
80	print("Seek Sequence is")
81
82	for i in range(len(seek_sequence)):
83		print(seek_sequence[i])
84
85# Driver code
86
87# request array
88arr = [ 176, 79, 34, 60,
89		92, 11, 41, 114 ]
90head = 50
91direction = "left"
92
93SCAN(arr, head, direction)

پیاده سازی الگوریتم آسانسور در زبان #C

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

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

1// C# program to demonstrate
2// SCAN Disk Scheduling algorithm
3using System;
4using System.Collections.Generic;
5
6class GFG
7{
8
9static int size = 8;
10static int disk_size = 200;
11
12static void SCAN(int []arr, int head, String direction)
13{
14	int seek_count = 0;
15	int distance, cur_track;
16	List<int> left = new List<int>(),
17					right = new List<int>();
18	List<int> seek_sequence = new List<int>();
19
20	// appending end values
21	// which has to be visited
22	// before reversing the direction
23	if (direction == "left")
24		left.Add(0);
25	else if (direction == "right")
26		right.Add(disk_size - 1);
27
28	for (int i = 0; i < size; i++) 
29	{
30		if (arr[i] < head)
31			left.Add(arr[i]);
32		if (arr[i] > head)
33			right.Add(arr[i]);
34	}
35
36	// sorting left and right vectors
37	left.Sort();
38	right.Sort();
39
40	// run the while loop two times.
41	// one by one scanning right
42	// and left of the head
43	int run = 2;
44	while (run-- >0)
45	{
46		if (direction == "left") 
47		{
48			for (int i = left.Count - 1; i >= 0; i--) 
49			{
50				cur_track = left[i];
51
52				// appending current track to seek sequence
53				seek_sequence.Add(cur_track);
54
55				// calculate absolute distance
56				distance = Math.Abs(cur_track - head);
57
58				// increase the total count
59				seek_count += distance;
60
61				// accessed track is now the new head
62				head = cur_track;
63			}
64			direction = "right";
65		}
66		else if (direction == "right") 
67		{
68			for (int i = 0; i < right.Count; i++) 
69			{
70				cur_track = right[i];
71				
72				// appending current track to seek sequence
73				seek_sequence.Add(cur_track);
74
75				// calculate absolute distance
76				distance = Math.Abs(cur_track - head);
77
78				// increase the total count
79				seek_count += distance;
80
81				// accessed track is now new head
82				head = cur_track;
83			}
84			direction = "left";
85		}
86	}
87
88	Console.Write("Total number of seek operations = "
89						+ seek_count + "n");
90	Console.Write("Seek Sequence is" + "n");
91	for (int i = 0; i < seek_sequence.Count; i++)
92	{
93		Console.Write(seek_sequence[i] + "n");
94	}
95}
96
97// Driver code
98public static void Main(String[] args)
99{
100
101	// request array
102	int []arr = { 176, 79, 34, 60,
103					92, 11, 41, 114 };
104	int head = 50;
105	String direction = "left";
106
107	SCAN(arr, head, direction);
108}
109}

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

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

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

1<script>
2
3	// Javascript program to demonstrate
4	// SCAN Disk Scheduling algorithm
5	
6	let size = 8;
7	let disk_size = 200;
8
9	function SCAN(arr, head, direction)
10	{
11		let seek_count = 0;
12		let distance, cur_track;
13		let left = [], right = [];
14		let seek_sequence = [];
15
16		// appending end values
17		// which has to be visited
18		// before reversing the direction
19		if (direction == "left")
20			left.push(0);
21		else if (direction == "right")
22			right.push(disk_size - 1);
23
24		for (let i = 0; i < size; i++)
25		{
26			if (arr[i] < head)
27				left.push(arr[i]);
28			if (arr[i] > head)
29				right.push(arr[i]);
30		}
31
32		// sorting left and right vectors
33		left.sort(function(a, b){return a - b});
34		right.sort(function(a, b){return a - b});
35
36		// run the while loop two times.
37		// one by one scanning right
38		// and left of the head
39		let run = 2;
40		while (run-- >0)
41		{
42			if (direction == "left")
43			{
44				for (let i = left.length - 1; i >= 0; i--)
45				{
46					cur_track = left[i];
47
48					// appending current track to seek sequence
49					seek_sequence.push(cur_track);
50
51					// calculate absolute distance
52					distance = Math.abs(cur_track - head);
53
54					// increase the total count
55					seek_count += distance;
56
57					// accessed track is now the new head
58					head = cur_track;
59				}
60				direction = "right";
61			}
62			else if (direction == "right")
63			{
64				for (let i = 0; i < right.length; i++)
65				{
66					cur_track = right[i];
67
68					// appending current track to seek sequence
69					seek_sequence.push(cur_track);
70
71					// calculate absolute distance
72					distance = Math.abs(cur_track - head);
73
74					// increase the total count
75					seek_count += distance;
76
77					// accessed track is now new head
78					head = cur_track;
79				}
80				direction = "left";
81			}
82		}
83
84		document.write("Total number of seek operations = "
85							+ seek_count + "</br>");
86		document.write("Seek Sequence is" + "</br>");
87		for (let i = 0; i < seek_sequence.length; i++)
88		{
89			document.write(seek_sequence[i] + "</br>");
90		}
91	}
92	
93	// request array
94	
95	let arr = [ 176, 79, 34, 60, 92, 11, 41, 114 ];
96	let head = 50;
97	let direction = "left";
98
99	SCAN(arr, head, direction);
100	
101</script>

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

Total number of seek operations = 226
Seek Sequence is
41
34
11
0
60
79
92
114
176

دروس آکادمیک الگوریتم ها و ساختمان داده

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

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

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

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

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

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

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

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

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

برعکس الگوریتم‌هایی مانند الگوریتم «اول کوتاه‌ترین زمان جست‌وجو» (Shortest Seek Time First | SSTF)، الگوریتم آسانسور با پردازش همه درخواست‌ها در طول زمان از روی‌دادن گرسنگی جلوگیری می‌کند. آسانسور تضمین می‌کند که درخواست‌های قدیمی‌تر نیز بالاخره مورد رسیدگی قرار بگیرند. در نهایت هم SCAN با الگوی اسکن کردن عقب و جلویی که ارائه داده، رفتاری کاملا قابل پیش‌بینی دارد. این مسئله به پیش‌بینی زمان اجرای درخواست‌ها با نظم مشخص کمک می‌کند. این نوع از داده‌‌ها می‌توانند کاربردهای بسیار خاصی داشته باشند.

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

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

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

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

جمع‌بندی

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

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