موضوع مقاله: الگوریتم آسانسور | مخاطب: عمومی | لحن: دانشنامه‌ای | ساختار: عنوان، مقدمه، 3 بخش، جمع‌بندی | مقاله: | # الگوریتم آسانسور | مقدمه: الگوریتم آسانسور مانند scan یک الگوریتم زمان بندی دیسک است که تعیین کننده حرکت آرم و هد دیسک در سرویس دهی به درخواست‌های خواندنی و نوشتنی می‌باشد. | ## بخش 1: الگوریتم آسانسور | این الگوریتم بعد از ساخت آسانسور نامیده می‌شود جایی که آسانسور ادامه می‌یابد تا در مسیر جدید حرکت کند (بالا یا پائین) تا زمانی که خالی شود و از کار بیفتد، فقط به خاطر این که به شخص اجازه بدهد یا عنوان شخص جدید را در همان جهت انتخاب کند. از دیدگاه پیاده سازی، گرداننده بافر معوق درخواست‌های خواندن / نوشتن در مقابل تعداد تقاضای سیلندر پیوسته را حفظ می‌کند. شماره استوانه‌های پائین تر نشان دهنده این است که استوانه به میله نزدیک تر می‌شود و در مقابل شماره بالاتر به دور بودن استوانه از میله اشاره دارد. تشریح الگوریتم وقتی که یک درخواست جدید می‌رسد، هنگامی که گرداننده بلا استفاده است، حرکت هد/ آرم اولیه در جهت استوانه خواهد بود، جایی که داده‌ها و اطلاعات در آن ذخیره شده‌اند. هنگامی که درخواست‌های اضافی می‌رسند، درخواست‌ها فقط در جهت متداول حرکت آرم تا رسیدن به لبهٔ دیسک برسند سرویس دهی می‌شوند. وقتی که این اتفاق می‌افتد، جهت حرکت آرم معکوس می‌شود و درخواست‌های باقی‌مانده در جهت مخالف سرویس دهی می‌شوند و به همین ترتیب آن فرایند ادامه می‌یابد. | ## بخش 2: الگوریتم آسانسور | متغیرهای الگوریتم یک تغییر این روش تضمین می‌کند که همه درخواست‌ها فقط در یک جهت سرویس دهی می‌شوند، به محض این که هد به لبهٔ خارجی دیسک رسید، هد برمی گردد و شروع و سرویس دهی درخواست جدید را فقط در یک جهت انجام می‌دهد. این امر منجر به عملکرد هم ارز بیشتر برای همه موقعیت‌های هد می‌شود، هنگامی که فاصله مورد انتظار از هد همیشه نصف فاصله بیشینه است، متفاوت از الگوریتم آسانسور استاندارد که سیلندرها در میانه‌ها هستند، سرویس دهی به بیرونی‌ترین و داخلی‌ترین سیلندرها اغلب به صورت مضاعف صورت می‌پذیرد. لیست معوق درخواست‌های دیسک (لیست شده با شماره مسیر): ۱۰۰،۵۰،۱۰،۲۰،۷۵ شروع شمارهٔ مسیر برای مثال‌ها ۳۵ خواهد بود. لیست نیاز خواهد داشت به مرتب شدن صعودی: ۱۰،۲۰،۵۰،۷۵،۱۰۰ هر دو الگوریتم SCAN و C-SCAN با روش یکسانی عمل خواهند کرد تا زمانی که به آخرین صف مسیر می‌رسند. به خاطر این مثال اجازه دهید که فرض کنیم الگوریتم SCAN در حال حاضر در حال حرکت کردن از یک شماره مسیر پائین تر به یک شماره مسیر بالاتر است (شبیه C-SCAN). برای هر دو الگوریتم اختلاف در اندازه (یعنی مقدار مطلق) بین درخواست مسیر بعدی و مسیر جاری روی می‌دهد. | ## بخش 3: الگوریتم آسانسور | Seek ۱: ۵۰ − ۳۵ = ۱۵ Seek ۲: ۷۵ − ۵۰ = ۲۵ Seek ۳: ۱۰۰ − ۷۵ = ۲۵ در این نقطه هر دو الگوریتم به بالاترین درخواست می‌رسند، SCAN فقط جهت معکوس خواهد داشت و به نزدیک‌ترین درخواست دیسک بعدی سرویس مس دهد (در این مثال ۲۰) و C-SCAN همیسه به مسیر ۰ (صفر) بر می‌گردد و شروع درخواست‌های مسیر بالاتر را دنبال می‌کند. تعریف C-SCAN: C-SCAN هد را از انتهای دیسک به انتهای دیگر دیسک حرکت می‌دهد، درخواست‌های سرویس دهی را در مسیر راه انجام می‌دهد. هد برای رسیدن به انتهای دیگر بدون هیچ گونه سرویس دهی به هر درخواستی طی مسیر برگشت فوراً به نقطه شروع دیسک بر می‌گردد. آنالیز الگوریتم حرکت آرم همیشه کمتر از دو برابر تعداد سیلندرهای کل است، برای هر دو گونه الگوریتم آسانسور، متغیرها مزیت داشتن اختلاف کوچک تر در زمان پاسخگوئی دارند. اگر چه الگوریتم آسانسور همیشه بهتر از کوتاهترین جستجوی اولیه نیست، اما تا اندازه‌ای نزدیک تر به مقدار بهینه است. این منجر به اختلاف زیاد در زمان پاسخگوئی و همچنین فقدان می‌شود بالاخص زمانی که درخواست جدید به‌طور پیوسته قبل از درخواست‌های موجود سرویس دهی شود. | ## جمع‌بندی | تکنیک ضد فقدان می‌تواند به الگوریتم جستجوی کوتاه‌ترین زمان اولیه اعمال شود تا زمان پاسخگوئی بهینه را مورد ضمانت قرار دهد.