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

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

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

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

متغیرهای الگوریتم

یک تغییر این روش تضمین می‌کند که همه درخواست‌ها فقط در یک جهت سرویس دهی می‌شوند، به محض این که هد به لبهٔ خارجی دیسک رسید، هد برمی گردد و شروع و سرویس دهی درخواست جدید را فقط در یک جهت انجام می‌دهد. این به عنوان الگوریتم آسانسور چرخشی یا C-SCAN شناخته می‌شود. این امر منجر به عملکرد هم ارز بیشتر برای همه موقعیت‌های هد می‌شود، هنگامی که فاصله مورد انتظار از هد همیشه نصف فاصله بیشینه است، متفاوت از الگوریتم آسانسور استاندارد که سیلندرها در میانه‌ها هستند، سرویس دهی به بیرونی‌ترین و داخلی‌ترین سیلندرها اغلب به صورت مضاعف صورت می‌پذیرد. دیگر متغیرها شامل موارد زیر می‌شود: FSCAN LOOK (و C-LOOK) N-Step-SCAN مثال در دنباله مثالی آورده شده که چگونگی میانگین زمان‌های جستجوی دیسک را برای هر دو الگوریتم SCAN و C-SCAN را محاسبه می‌کند. لیست معوق درخواست‌های دیسک (لیست شده با شماره مسیر): ۱۰۰،۵۰،۱۰،۲۰،۷۵ شروع شمارهٔ مسیر برای مثال‌ها ۳۵ خواهد بود. لیست نیاز خواهد داشت به مرتب شدن صعودی: ۱۰،۲۰،۵۰،۷۵،۱۰۰ هر دو الگوریتم SCAN و C-SCAN با روش یکسانی عمل خواهند کرد تا زمانی که به آخرین صف مسیر می‌رسند. به خاطر این مثال اجازه دهید که فرض کنیم الگوریتم SCAN در حال حاضر در حال حرکت کردن از یک شماره مسیر پائین تر به یک شماره مسیر بالاتر است (شبیه C-SCAN). برای هر دو الگوریتم اختلاف در اندازه (یعنی مقدار مطلق) بین درخواست مسیر بعدی و مسیر جاری روی می‌دهد.

• Seek ۱: ۵۰ − ۳۵ = ۱۵
• Seek ۲: ۷۵ − ۵۰ = ۲۵
• Seek ۳: ۱۰۰ − ۷۵ = ۲۵

در این نقطه هر دو الگوریتم به بالاترین درخواست می‌رسند، SCAN فقط جهت معکوس خواهد داشت و به نزدیک‌ترین درخواست دیسک بعدی سرویس مس دهد (در این مثال ۲۰) و C-SCAN همیسه به مسیر ۰ (صفر) بر می‌گردد و شروع درخواست‌های مسیر بالاتر را دنبال می‌کند.

• Seek 4 (SCAN): ۲۰ − ۱۰۰ = ۸۰
• Seek 5 (SCAN): ۱۰ − ۲۰ = ۱۰
• Total (SCAN): ۱۵۵
• Average (SCAN): ۱۵۵ ÷ ۵ = ۳۱
• Seek 4 (C-SCAN): ۰ − ۱۰۰ = 100 (C-SCAN always goes back to the first track)
• Seek 5 (C-SCAN): ۱۰ − ۰ = ۱۰
• Seek 6 (C-SCAN): ۲۰ − ۱۰ = ۱۰
• Total (C-SCAN): ۱۸۵
• Average (C-SCAN): ۱۸۵ ÷ ۵ = ۳۷

نکته

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

آنالیز الگوریتم

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

منابع

مشارکت‌کنندگان ویکی‌پدیا. «Elevator algorithm». در دانشنامهٔ ویکی‌پدیای انگلیسی.