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

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

الگوریتم آسانسور مانند scan یک الگوریتم زمان بندی دیسک است که تعیین کننده حرکت آرم و هد دیسک در سرویس دهی به درخواست های خواندنی و نوشتنی می باشد. 

این الگوریتم بعد از ساخت آسانسور نامیده می شود جائی که آسانسور ادامه می یابد تا در مسیر جدید حرکت کند ( بالا یا پائین ) تا زمانی که خالی شود و از کار بیفتد، فقط به خاطر این که به شخص اجازه بدهد یا عنوان شخص جدید را در همان جهت انتخاب کند. از دیدگاه پیاده سازی ، گرداننده بافر معوق درخواست های خواندن / نوشتن در مقابل تعداد تقاضای سیلندر پیوسته را حفظ می کند. شماره استوانه های پائین تر نشان دهنده این است که استوانه به میله نزدیک تر می شود و در مقابل شماره بالاتر به دور بودن استوانه از میله اشاره دارد. تشریح الگوریتم وقتی که یک درخواست جدید می رسد، هنگامی که گرداننده بلا استفاده است ، حرکت هد/ آرم اولیه در جهت استوانه خواهد بود ، جائی که داده ها و اطلاعات در آن ذخیره شده‌اند. هنگامی که درخواست های اضافی می رسند، درخواست ها فقط در جهت متداول حرکت آرم تا رسیدن به لبه ی دیسک برسند سرویس دهی می شوند. وقتی که این اتفاق می افتد ، جهت حرکت آرم معکوس می شود و درخواست های باقی‌مانده در جهت مخالف سرویس دهی می شوند و به همین ترتیب آن فرایند ادامه می یابد. متغیرها ی الگوریتم یک تغییر این روش تضمین می کند که همه درخواست ها فقط در یک جهت سرویس دهی می شوند، به محض این که هد به لبه ی خارجی دیسک رسید، هد برمی گردد و شروع و سرویس دهی درخواست جدید را فقط در یک جهت انجام می دهد. این به عنوان الگوریتم آسانسور چرخشی یا C-SCAN شناخته می شود. این امر منجر به عملکرد هم ارز بیشتر برای همه موقعیت های هد می شود، هنگامی که فاصله مورد انتظار از هد همیشه نصف فاصله بیشینه است ، متفاوت از الگوریتم آسانسور استاندارد که سیلندرها در میانه ها هستند، سرویس دهی به بیرونی ترین و داخلی ترین سیلندرها اغلب به صورت مضاعف صورت می پذیرد. دیگر متغیر ها شامل موارد زیر می شود : FSCAN LOOK ( و C-LOOK ) N-Step-SCAN مثال در دنباله مثالی آورده شده که چگونگی میانگین زمان های جستجوی دیسک را برای هر دو الگوریتم SCAN و C-SCAN را محاسبه می کند. لیست معوق درخواست های دیسک ( لیست شده با شماره مسیر ) : 100،50،10،20،75 شروع شماره ی مسیر برای مثال ها 35 خواهد بود. لیست نیاز خواهد داشت به مرتب شدن صعودی : 10،20،50،75،100 هر دو الگوریتم SCAN و C-SCAN با روش یکسانی عمل خواهند کرد تا زمانی که به آخرین صف مسیر می رسند. به خاطر این مثال اجازه دهید که فرض کنیم الگوریتم SCAN در حال حاضر در حال حرکت کردن از یک شماره مسیر پائین تر به یک شماره مسیر بالاتر است ( شبیه C-SCAN ) . برای هر دو الگوریتم اختلاف در اندازه ( یعنی مقدار مطلق ) بین درخواست مسیر بعدی و مسیر جاری روی می دهد.

• Seek 1: 50 − 35 = 15
• Seek 2: 75 − 50 = 25
• Seek 3: 100 − 75 = 25

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

• Seek 4 (SCAN): 20 − 100 = 80
• Seek 5 (SCAN): 10 − 20 = 10
• Total (SCAN): 155
• Average (SCAN): 155 ÷ 5 = 31
• Seek 4 (C-SCAN): 0 − 100 = 100 (C-SCAN always goes back to the first track)
• Seek 5 (C-SCAN): 10 − 0 = 10
• Seek 6 (C-SCAN): 20 − 10 = 10
• Total (C-SCAN): 185
• Average (C-SCAN): 185 ÷ 5 = 37

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

منابع

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