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

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

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

الگوریتم زمان بندی SSTF چیست؟

الگوریتم زمان بندی SSTF دستورالعملی است که برای «زمان‌بندی ذخیره‌سازی ثانویه» (Secondary Storage Scheduling) استفاده می‌شود. این الگوریتم در زمان ارائه خدمات نوشتن و خواندن دیسک، حرکات سر و بازوی دیسک را کنترل می‌کند. واژه SSTF سرنامی از عبارت انگلیسی «Shortest Seek Time First» به معنی «اول کوتاه‌ترین زمان جست‌وجو» است. SSTF به عنوان الگوریتم زمان بندی دیسک کار می‌کند و از طریق انتخاب درخواست‌هایی که کوتاه‌‌ترین زمان جست‌وجو را نسبت به مکان فعلی «Head» دارند، عملکرد دیسک را بهبود می‌بخشد. این الگوریتم اولویت را به درخواست‌هایی با کوتاه‌ترین زمان جست‌وجو می‌دهد، حتی اگر آن درخواست‌ها در اول صف آماده، قرار نداشته باشند.

فیلم آموزش مدیریت دیسک در سیستم عامل (مرور اجمالی و تست کنکور) (رایگان) در فرادرس

کلیک کنید

توجه: «Head» به سر مخصوص خواندن و نوشتن اطلاعات بر روی دیسک‌های مکانیکی گفته می‌شود. عملکرد این ساختار در دیسک‌های حافظه غیرمکانیکی به صورت دیگری انجام می‌شود.

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

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

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

فرض کنیم که دیسکی با ۱۸۰ شیار مختلف در دست داریم. این شیارها را از شماره ۰ تا ۱۷۹ شماره گذاری کرده‌ایم. به همین‌ ترتیب، صفی از درخواست‌های ورودی و خروجی داده با ترتیب از راست به چپ ۱۵، ۳۹، ۱۵۶، ۶۷، ۱۷۲، ۵۰، ۱۱۰ و ۸۷ بر روی دیسک در انتظار اجرا قرار دارند. موقعیت اول نشانگر «Read/Write head» بر روی شیار ۴۵ قرار داشته و در حال حرکت به سمت چپ است.

اکنون باید با استفاده از الگوریتم SSTF، مجموع حرکات سر مخصوص Read/Write head را بر روی شیارها بدست بیاوریم.

در شکل پایین می‌توان مسیر حرکت نشانگر Read/Write head را تماشا کرد.

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

(50-45) + (50-39) + (39-15) + (67-15) + (87-67) + (110-87) + (156-110) + (172-156) =
 5 + 11 + 14 + 52 + 20 + 23 + 46 + 16 = 187 

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

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

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

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

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

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

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

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

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

کلیک کنید

ویژگی‌ الگوریتم SSTF

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

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

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

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

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

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

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

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

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

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

در این بخش روند کار الگوریتم SSTF را با کمک سه مثال مختلف به صورت دقیق توضیح و نمایش دادیم. با کمک بررسی این مثال‌ها به خوبی موفق به درک فرایند کار این الگوریتم می‌شوید.

مثال اول

در این مثال، صف انتظار دیسکی را در نظر بگیرید که شامل درخواست‌های برای عملیات I/O بر روی بلوک‌های دیسک حافظه است. صف انتظار، شامل شماره شیار‌های {98, 183, 37, 122, 14, 124, 65, 67} است. سر دیسک در حالت اولیه بر روی شیار شماره ۵۳ قرار دارد. اکنون باید از الگوریتم SSTF برای رسیدگی به این درخواست‌ها استفاده کنیم.

داده‌های ورودی در این مسئله شامل صف انتظار به شکل {98, 183, 37, 122, 14, 124, 65, 67} و محل اولیه قرارگیری سر دیسک، برابر با شیار ۵۳ است. مراحل حل این مسئله به ترتیب در زیر بیان شده‌اند.

1. در ابتدا باید همه درخواست‌ها را با ترتیب صعودی به صورت منظم بچینیم. در نتیجه، صف انتظار به شکل { 14, 37, 65, 67, 98, 122, 124, 183 } می‌شود.
2. سر دیسک، نزدیک‌ترین درخواست را از دو طرف خود، پیدا می‌کند. از بین شیار‌های ۳۷ و ۶۵، درخواست شیار ۶۵ نزدیک‌تر است. زیرا 53 - 37 = 16 و 65 - 53 = 12 بنابراین، سر دیسک از خانه فعلی ۵۳ به سمت به خانه ۶۵ که نماینده درخواست بعدی است، حرکت می‌کند. طول مسیر حرکت سر دیسک برابر با 65 - 53 = 12 است.
3. نزدیک‌ترین در خواست به شیار ۶۵ در شیار ۶۷ قرار دارد. بنابراین، سر دیسک از ۶۵ به ۶۷ حرکت می‌کند. در نتیجه، میزان مسیر حرکت شده توسط سر دیسک برابر با 12 + (67 - 65) = 14 می‌شود.
4. به همین‌ ترتیب، نزدیک‌ترین درخواست به شیار ۶۷ در شیار ۳۷ قرار دارد. بنابراین، این بار سر دیسک از ۶۷ به ۳۷ منتقل می‌شود. اکنون در نتیجه، میزان مسیر حرکت شده توسط سر دیسک برابر با 14 + (67 - 37) = 44 است.
5. این بار نزدیک‌ترین درخواست به ۳۷ در ۱۴ قرار دارد. بنابراین، سر دیسک از ۳۷ به ۱۴ حرکت می‌کند. در نتیجه، میزان مسیر حرکت شده توسط سر دیسک برابر با 44 + (37 - 14) = 67 می‌شود.
6. در مرحله بعد، نزدیک‌ترین درخواست به شیار ۱۴ در شیار ۹۸ قرار دارد. بنابراین، این بار سر دیسک از ۱۴ به ۹۸ حرکت می‌کند. در نتیجه، میزان مسیر طی شده توسط سر دیسک برابر با 67 + (98 - 14) = 151 است.
7. طبق روال قبل، نزدیک‌ترین درخواست به شیار ۹۸ در شیار ۱۲۲ قرار دارد. پس این بار سر دیسک از ۹۸ به ۱۲۲ حرکت می‌کند. در نتیجه، میزان مسیر طی شده توسط سر دیسک برابر با 151 + (122 - 98) = 175 است.
8. در مرحله بعد، نزدیک‌ترین درخواست به شیار ۱۲۲ در شیار ۱۲۴ قرار دارد. در نتیجه، این بار سر دیسک از ۱۲۲ به ۱۲۴ حرکت می‌کند. پس میزان مسیر طی شده توسط سر دیسک برابر با 175 + (124 - 122) = 177 شده است.
9. در نهایت‌ هم طبق روال بالا،‌ نزدیک‌ترین درخواست به شیار ۱۲۴ در شیار ۱۸۳ قرار دارد. در نتیجه، این بار سر دیسک از ۱۲۴ به ۱۸۳ حرکت می‌کند. بنابراین، میزان کل مسیر طی شده توسط سر دیسک برابر با 177 + (183 - 124) = 236 می‌شود.
10. از آنجا که خانه ۱۸۳ آخرین درخواست موجود در صف انتظار بود، بعد از رسیدگی به این درخواست، فرایند متوقف خواهد شد. پس مجموع مسیر طی شده توسط سر دیسک به اندازه ۲۳۶ می‌شود.

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

در نتیجه، ترتیب رسیدگی درخواست‌ها به صورت 65, 67, 37, 14, 98, 122, 124, 183 و مجموع مسیر طی شده توسط سر دیسک هم برابر با مقدار ۲۳۶ شد.

در ادامه مثال‌های دیگری را نیز بررسی کرده‌ایم.

مثال دوم

در این مثال، صف انتظار دیسکی را در نظر بگیرید که شامل درخواست‌هایی برای عملیات I/O بر روی بلوک‌های استوانه حافظه است. صف انتظار شماره شیار‌های {95, 180, 34, 119, 11, 123, 62, 64} را شامل می‌شود. سر دیسک در حالت اولیه بر روی شیار شماره ۵۰ قرار گرفته است. اکنون باید از الگوریتم SSTF برای رسیدگی به درخواست‌های خواندن و نوشتن اطلاعات استفاده کنیم.

داده‌های ورودی در این مسئله شامل صف انتظاری به شکل {95, 180, 34, 119, 11, 123, 62, 64} و محل اولیه قرارگیری سر دیسک، برابر با شیار ۵۰ است. مراحل حل این مسئله به ترتیب در زیر بیان شده‌اند.

1. در ابتدا باید همه درخواست‌ها را با ترتیب صعودی به صورت منظم بچینیم. در نتیجه، صف انتظار به شکل { 11, 34, 62, 64, 95, 119, 123, 180 } می‌شود.
2. سر دیسک از موقعیت اولیه خود که بر روی شیار ۵۰ قرار دارد، شروع به حرکت به سمت نزدیک‌ترین درخواست در صف می‌کند. نزدیک‌ترین درخواست در این صف بر روی شیار ۶۲ قرار گرفته است. بعد از ۶۲ سر دیسک به شیار ۶۴ منتقل شده و به همین ترتیب توالی 34, 11, 95, 119, 123, 180 را تا به انتها دنبال می‌کند.

در مثال بالا مجموع کل مسیر طی شده توسط سر دیسک برابر با مقدار محاسبه شده در پایین است.

= (62 - 50) + (64 - 62) + (64 - 34) + (34 - 11) + (95 - 11) + (119 - 95) + (123 - 119) + (180 - 123) 

= 12 + 2 + 30 + 23 + 84 + 24 + 4 + 57

= 236

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

در نتیجه، ترتیب رسیدگی درخواست‌ها به صورت 62, 64, 34, 11, 95, 119, 123, 180 و مجموع مسیر طی شده توسط سر دیسک هم برابر با مقدار ۲۳۶ شد.

در بخش بعد مثال دیگری را در این باره نمایش داده‌ایم.

مثال سوم

در این مثال، صف انتظار دیسکی را در نظر می‌گیریم که شامل درخواست‌هایی برای اجرای عملیات I/O بر روی بلوک‌های حافظه است. صف انتظار شامل شماره شیار‌های {19, 80, 134, 11, 110, 23, 162, 64} می‌شود. سر دیسک در حالت اولیه بر روی شیار شماره ۵۰ قرار دارد. اکنون باید از الگوریتم SSTF برای رسیدگی به درخواست‌های خواندن و نوشتن اطلاعات استفاده کنیم.

داده‌های ورودی در این مسئله شامل صف انتظار به شکل {19, 80, 134, 11, 110, 23, 162, 64} و محل اولیه قرارگیری سر دیسک، برابر با شیار ۵۰ است. در ادامه، مراحل حل این مسئله به ترتیب بیان شده‌اند.

1. در ابتدا باید همه درخواست‌ها را با ترتیب صعودی به صورت منظم بچینیم. در نتیجه، صف انتظار به شکل { 11, 19, 23, 64, 80, 110, 134, 162 } می‌شود.
2. سر دیسک از موقعیت اولیه خود که بر روی شیار ۵۰ قرار دارد، شروع به حرکت به سمت نزدیک‌ترین درخواست در صف می‌کند. نزدیک‌ترین درخواست در این صف بر روی شیار ۶۴ قرار گرفته است. بعد از ۶۴ سر دیسک به شیار ۸۰ منتقل شده و به همین ترتیب، توالی 110, 134, 162, 23, 19, 11 را تا به انتها دنبال می‌کند.

مجموع کل مسیر طی شده توسط سر دیسک در مثال بالا برابر با مقدار محاسبه شده در پایین است.

= (64 - 50) + (80 - 64) + (110 - 80) + (134 - 110) + (162 - 134) + (162 - 23) + (23 - 19) + (19 - 11)

= 14 + 16 + 30 + 24 + 28 + 139 + 4 + 8

= 263

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

در نتیجه، ترتیب رسیدگی درخواست‌ها به صورت 64, 80, 110, 134, 162, 23, 19, 11 و مجموع مسیر طی شده توسط سر دیسک هم برابر با مقدار ۲۶۳ شد.

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

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

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

فیلم آموزش مدیریت دیسک در سیستم عامل (مرور اجمالی و تست کنکور) (رایگان) در فرادرس

کلیک کنید

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

مراحل الگوریتم SSTF

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

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

نمایش روش کار الگوریتم

اکنون از مثال کوچکی استفاده می‌کنیم تا روش کار الگوریتم بالا را نمایش دهیم. فرض کنیم که آرایه درخواست به صورت {176, 79, 34, 60, 92, 11, 41, 114} باشد. موقعیت اولیه head هم برابر با شیار 50 است. در شکل پایین، توالی از حرکت‌های head را می‌بینیم که شیار‌های درخواست شده را بر اساس الگوریتم SSTF پیمایش کرده است. بنابراین، مجموع مسیر جست‌وجو‌های انجام شده به صورت زیر می‌‌شود.

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

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

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

در این قسمت از مطلب، کدهای الگوریتم زمان بندی SSTF را با کمک پنج زبان برنامه نویسی مختلف پیاده‌سازی کرده‌ایم. توجه کنید که در زبان‌های جاوا و #C کلاسی را به نام node ایجاد کردیم. در این کلاس، دو عضو distance ، برای ذخیره‌سازی فاصله بین head و موقعیت شیار مورد نظر و accessed را به صورت یک متغیر بولین تعریف کرده‌ایم. متغیر accessed به برنامه می‌گوید که آیا شیار مورد نظر قبلا مورد دسترسی و اجرای فرایند مربوط به آن، قرار گرفته است یا نه.

پیاده‌سازی این کدها را با زبان ++C شروع می‌کنیم.

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

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

1// C++ program for implementation of 
2// SSTF disk scheduling
3#include <bits/stdc++.h>
4using namespace std;
5
6// Calculates difference of each 
7// track number with the head position 
8void calculatedifference(int request[], int head,
9						int diff[][2], int n)
10{
11	for(int i = 0; i < n; i++)
12	{
13		diff[i][0] = abs(head - request[i]);
14	}
15}
16
17// Find unaccessed track which is 
18// at minimum distance from head 
19int findMIN(int diff[][2], int n)
20{
21	int index = -1;
22	int minimum = 1e9;
23
24	for(int i = 0; i < n; i++)
25	{
26		if (!diff[i][1] && minimum > diff[i][0])
27		{
28			minimum = diff[i][0];
29			index = i;
30		}
31	}
32	return index;
33}
34
35void shortestSeekTimeFirst(int request[], 
36						int head, int n)
37{
38	if (n == 0)
39	{
40		return;
41	}
42	
43	// Create array of objects of class node 
44	int diff[n][2] = { { 0, 0 } };
45	
46	// Count total number of seek operation 
47	int seekcount = 0;
48	
49	// Stores sequence in which disk access is done 
50	int seeksequence[n + 1] = {0};
51	
52	for(int i = 0; i < n; i++)
53	{
54		seeksequence[i] = head;
55		calculatedifference(request, head, diff, n);
56		int index = findMIN(diff, n);
57		diff[index][1] = 1;
58		
59		// Increase the total count 
60		seekcount += diff[index][0]; 
61		
62		// Accessed track is now new head 
63		head = request[index];
64	}
65	seeksequence[n] = head;
66	
67	cout << "Total number of seek operations = "
68		<< seekcount << endl;
69	cout << "Seek sequence is : " << "\n";
70	
71	// Print the sequence 
72	for(int i = 0; i <= n; i++) 
73	{
74		cout << seeksequence[i] << "\n";
75	}
76}
77
78// Driver code
79int main()
80{
81	int n = 8;
82	int proc[n] = { 176, 79, 34, 60, 92, 11, 41, 114 };
83	
84	shortestSeekTimeFirst(proc, 50, n);
85	
86	return 0;
87}

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

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

1// Java program for implementation of 
2// SSTF disk scheduling
3class node {
4	
5	// represent difference between 
6	// head position and track number
7	int distance = 0; 
8	
9	// true if track has been accessed
10	boolean accessed = false; 
11}
12
13public class SSTF {
14	
15	// Calculates difference of each 
16	// track number with the head position
17	public static void calculateDifference(int queue[], 
18										int head, node diff[])
19										
20	{
21		for (int i = 0; i < diff.length; i++)
22			diff[i].distance = Math.abs(queue[i] - head);
23	}
24
25	// find unaccessed track 
26	// which is at minimum distance from head
27	public static int findMin(node diff[])
28	{
29		int index = -1, minimum = Integer.MAX_VALUE;
30
31		for (int i = 0; i < diff.length; i++) {
32			if (!diff[i].accessed && minimum > diff[i].distance) {
33				
34				minimum = diff[i].distance;
35				index = i;
36			}
37		}
38		return index;
39	}
40
41	public static void shortestSeekTimeFirst(int request[], 
42													int head)
43													
44	{
45		if (request.length == 0)
46			return;
47			
48		// create array of objects of class node 
49		node diff[] = new node[request.length]; 
50		
51		// initialize array
52		for (int i = 0; i < diff.length; i++) 
53		
54			diff[i] = new node();
55		
56		// count total number of seek operation 
57		int seek_count = 0; 
58		
59		// stores sequence in which disk access is done
60		int[] seek_sequence = new int[request.length + 1]; 
61		
62		for (int i = 0; i < request.length; i++) {
63			
64			seek_sequence[i] = head;
65			calculateDifference(request, head, diff);
66			
67			int index = findMin(diff);
68			
69			diff[index].accessed = true;
70			
71			// increase the total count
72			seek_count += diff[index].distance; 
73			
74			// accessed track is now new head
75			head = request[index]; 
76		}
77		
78		// for last accessed track
79		seek_sequence[seek_sequence.length - 1] = head; 
80		
81		System.out.println("Total number of seek operations = "
82													+ seek_count);
83													
84		System.out.println("Seek Sequence is");
85		
86		// print the sequence
87		for (int i = 0; i < seek_sequence.length; i++) 
88			System.out.println(seek_sequence[i]);
89	}
90
91	public static void main(String[] args)
92	{
93		// request array
94		int arr[] = { 176, 79, 34, 60, 92, 11, 41, 114 }; 
95		shortestSeekTimeFirst(arr, 50);
96	}
97}

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

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

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

1# Python3 program for implementation of 
2# SSTF disk scheduling 
3
4# Calculates difference of each 
5# track number with the head position
6def calculateDifference(queue, head, diff):
7	for i in range(len(diff)):
8		diff[i][0] = abs(queue[i] - head) 
9	
10# find unaccessed track which is 
11# at minimum distance from head 
12def findMin(diff): 
13
14	index = -1
15	minimum = 999999999
16
17	for i in range(len(diff)):
18		if (not diff[i][1] and
19				minimum > diff[i][0]):
20			minimum = diff[i][0]
21			index = i
22	return index 
23	
24def shortestSeekTimeFirst(request, head):			 
25		if (len(request) == 0): 
26			return
27		
28		l = len(request) 
29		diff = [0] * l
30		
31		# initialize array 
32		for i in range(l):
33			diff[i] = [0, 0]
34		
35		# count total number of seek operation	 
36		seek_count = 0
37		
38		# stores sequence in which disk 
39		# access is done 
40		seek_sequence = [0] * (l + 1) 
41		
42		for i in range(l): 
43			seek_sequence[i] = head 
44			calculateDifference(request, head, diff) 
45			index = findMin(diff) 
46			
47			diff[index][1] = True
48			
49			# increase the total count 
50			seek_count += diff[index][0] 
51			
52			# accessed track is now new head 
53			head = request[index] 
54	
55		# for last accessed track 
56		seek_sequence[len(seek_sequence) - 1] = head 
57		
58		print("Total number of seek operations =", 
59									seek_count) 
60														
61		print("Seek Sequence is") 
62		
63		# print the sequence 
64		for i in range(l + 1):
65			print(seek_sequence[i]) 
66	
67# Driver code 
68if __name__ =="__main__":
69	
70	# request array 
71	proc = [176, 79, 34, 60, 
72			92, 11, 41, 114]
73	shortestSeekTimeFirst(proc, 50)

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

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

1// C# program for implementation of 
2// SSTF disk scheduling
3using System;
4	
5public class node
6{
7	
8	// represent difference between 
9	// head position and track number
10	public int distance = 0; 
11	
12	// true if track has been accessed
13	public Boolean accessed = false; 
14}
15
16public class SSTF 
17{
18	
19	// Calculates difference of each 
20	// track number with the head position
21	public static void calculateDifference(int []queue, 
22										int head, node []diff)
23										
24	{
25		for (int i = 0; i < diff.Length; i++)
26			diff[i].distance = Math.Abs(queue[i] - head);
27	}
28
29	// find unaccessed track 
30	// which is at minimum distance from head
31	public static int findMin(node []diff)
32	{
33		int index = -1, minimum = int.MaxValue;
34
35		for (int i = 0; i < diff.Length; i++)
36		{
37			if (!diff[i].accessed && minimum > diff[i].distance)
38			{
39				
40				minimum = diff[i].distance;
41				index = i;
42			}
43		}
44		return index;
45	}
46
47	public static void shortestSeekTimeFirst(int []request, 
48													int head)
49	{
50		if (request.Length == 0)
51			return;
52			
53		// create array of objects of class node 
54		node []diff = new node[request.Length]; 
55		
56		// initialize array
57		for (int i = 0; i < diff.Length; i++) 
58		
59			diff[i] = new node();
60		
61		// count total number of seek operation 
62		int seek_count = 0; 
63		
64		// stores sequence in which disk access is done
65		int[] seek_sequence = new int[request.Length + 1]; 
66		
67		for (int i = 0; i < request.Length; i++)
68		{
69			
70			seek_sequence[i] = head;
71			calculateDifference(request, head, diff);
72			
73			int index = findMin(diff);
74			
75			diff[index].accessed = true;
76			
77			// increase the total count
78			seek_count += diff[index].distance; 
79			
80			// accessed track is now new head
81			head = request[index]; 
82		}
83		
84		// for last accessed track
85		seek_sequence[seek_sequence.Length - 1] = head; 
86		
87		Console.WriteLine("Total number of seek operations = "
88													+ seek_count);
89													
90		Console.WriteLine("Seek Sequence is");
91		
92		// print the sequence
93		for (int i = 0; i < seek_sequence.Length; i++) 
94			Console.WriteLine(seek_sequence[i]);
95	}
96
97	// Driver code
98	public static void Main(String[] args)
99	{
100		// request array
101		int []arr = { 176, 79, 34, 60, 92, 11, 41, 114 }; 
102		shortestSeekTimeFirst(arr, 50);
103	}
104}

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

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

1// Javascript Program for implementation of 
2// SSTF disk scheduling
3function calculatedifference(request, head, diff, n) {
4	for (let i = 0; i < n; i++) {
5		diff[i][0] = Math.abs(head - request[i]);
6	}
7}
8
9// Find unaccessed track which is 
10// at minimum distance from head 
11function findMIN(diff, n) {
12	let index = -1;
13	let minimum = 1e9;
14
15	for (let i = 0; i < n; i++) {
16		if (!diff[i][1] && minimum > diff[i][0]) {
17			minimum = diff[i][0];
18			index = i;
19		}
20	}
21	return index;
22}
23
24function shortestSeekTimeFirst(request, head, n) {
25	if (n == 0) {
26		return;
27	}
28
29	// Create array of objects of class node 
30	let diff = new Array(n);
31	for (let i = 0; i < n; i++) {
32		diff[i] = new Array(2);
33	}
34
35	// Count total number of seek operation 
36	let seekcount = 0;
37
38	// Stores sequence in which disk access is done 
39	let seeksequence = new Array(n + 1);
40	seeksequence[0] = head;
41
42	for (let i = 0; i < n; i++) {
43		calculatedifference(request, head, diff, n);
44		let index = findMIN(diff, n);
45		diff[index][1] = 1;
46
47		// Increase the total count 
48		seekcount += diff[index][0];
49
50		// Accessed track is now new head 
51		head = request[index];
52		seeksequence[i + 1] = head;
53	}
54
55	console.log("Total number of seek operations = " + seekcount);
56	console.log("Seek sequence is : ");
57
58	// Print the sequence 
59	for (let i = 0; i <= n; i++) {
60		console.log(seeksequence[i]);
61	}
62}
63
64// Driver code
65let n = 8;
66let proc = [176, 79, 34, 60, 92, 11, 41, 114];
67
68shortestSeekTimeFirst(proc, 50, n);

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

Total number of seek operations = 204
Seek Sequence: 50, 41, 34, 11, 60, 79, 92, 114, 176 

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

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

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

• فیلم آموزش طراحی الگوریتم همراه با مرور و تست کنکور ارشد فرادرس
• فیلم آموزش پیشرفته ساختمان داده به همراه حل سوالات کنکور ارشد و دکتری فرادرس
• فیلم آموزش ساختمان داده ها و پیاده سازی در C++‎ فرادرس
• فیلم آموزش رابطه های بازگشتی در طراحی الگوریتم و ساختمان گسسته به‌همراه مرور و تست کنکور ارشد فرادرس
• فیلم آموزش مروری بر پیچیدگی محاسبات با فرادرس

جمع‌بندی

در این مطلب از مجله فرادرس درباره الگوریتم زمان بندی FCFS بحث کرده‌ایم. اکنون می‌دانیم که FCFS دستورالعملی برای محاسبه کوتاه‌ترین زمان جست‌وجو بین شیارهای حاوی داده در دیسک‌ها است. سیستم عامل با کمک این الگوریتم در زمان ارائه خدمات نوشتن و خواندن دیسک، حرکات سر و بازوی دیسک را کنترل می‌کند. نام الگوریتم FCFS از سرنام عبارت «Shortest Seek Time First» گرفته شده است. این الگوریتم زمان‌بندی از طریق انتخاب کردن درخواست‌هایی با کوتاه‌‌ترین زمان جست‌وجو نسبت به مکان فعلی «Head»، فرایند خواندن و نوشتن در حافظه را بهبود می‌بخشد. اولویت اجرا همیشه به درخواست‌هایی با کوتاه‌ترین زمان جست‌وجو می‌رسد، حتی اگر آن درخواست‌ها در اول صف آماده، قرار نداشته باشند.

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

کلیک کنید

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