آشنایی با الگوریتم های زمان بندی دیسک
همانگونه که می دانید نقش عمده دسترسی به اطلاعات زمان مربوط به جست و جو می باشد (پیدا کردن شیار مورد نظر)
در ادامه با چند الگوریتم زمان بندی مطرح آشنا می شویم.
1- الگوریتم خروج به ترتیب ورود(FIFO یا FCFS)
در این روش ، درخواست ها با توجه به زمانشان به صف، سرویس می گیرند.این روش عادلانه ترین روش است ولی غالباً سریعترین روش نیست. مشکل این روش آن است که هد ممکن است حرکتهای شدیدی بکند مثلاً ا ز 122 به 14 برود و دوباره به 124 برگردد.
مثال:فرض کنید شیار های درخواستی موجود در صف 55،58،39،18،90،160 باشد و هد بر روی شیار 100 باشد و زمان حرکت بازو 10 میلی ثانیه طول بکشد متوسط زمان جست و جو برابراست با:
100 ---45--->55----3---->58----19---->39----21---->18----72---->90----70--->160
تعداد کل حرکات: 45+3+19+21+72+70=230
متوسط تعداد حرکات : 230/6=38.33
383.3ns
2- الگوریتم ابتدا کوتاهترین زمان جستجو:(SSTF)
ین الگوریتم اولویت انتخاب را به درخواستی می دهد که کمترین زمان پیگرد را نسبت به موقعیت فعلی دیسک دارد. زیرا زمان پیگرد با تعداد شیارهایی که توسط هد پیمایش می شود ‚ افزایش می یابد پس این الگوریتم درخواستی را انتخاب می کند که به موقعیت فعلی هد نزدیکتر باشد
زمانبندی SSTF مانند زمانبندی SJF بوده و مانند آن مشکل قحطی زدگی (Starvation) دارد.
مثلا فرض کنید در صف درخواست 124 و 14 را داشته باشیم و دیسک در حال سرویس دهی به سیلندر 14 است. در این حال درخواستهای 17 و 23 و غیره که نزدیک هستند وارد می شوند. بدین ترتیب درخواست 124 به عقب می افتد.
3- الگوریتم مرور(SCAN)
در این روش هد دیسک مرتباً از یک انتهای دیسک به سمت انتهای دیگر حرکت می کند و هر بار که به سیلندری برسد که نیاز به سرویس دهی دارد به آن سرویس می دهد. در شروع این روش علاوه بر دا نستن مکان جاری هد باید جهت شروع حرکت هد را نیز بدانیم .
الگوریتم SCAN به الگوریتم آسانسور نیز معروف است چرا که مانند آسانسور یک ساختمان عمل می کند.
در این روش اگر درخواستی به صف برسد که جلوی هد باشد این درخواست سریعاً سرو یس داده می شود ولی اگر درخواست پشت سرهد باشد بایستی صبر کند تا هد به انتهای دیسک رفته تغییر جهت داده و برگردد.
بنابراین مشکل این روش آن است که تقاضایی که بلافاصله پس از عبور هد از یک سیلندر برای آن سیلندر دریافت می شود به تعویق می افتد.4- الگوریتم مرور مدور(C-SCAN)
این روش که مخفف Circular Scan یا پویش چرخشی است نسبت به روش قبلی زمان انتظار یکنواختی را پدید می آورد.در روش C-Scan مانند SCAN هد در یک جهت مثلاً از داخل به خارج حرکت کرده و در مسیر خود به تمام درخواستها سرویس می دهد ولی هنگامی که به انتهای دیسک رسید سریعاً به اول دیسک برمیگردد و در این حرکت برگشتی سریع، هیچ سرویس دهی انجام نمی دهد.
اصلاح شده دو روش SCAN و C-SCAN ، look و C-Look می باشند که در آنها الزاماً حرکت از ابتدای دیسک شروع نمی شود و تا آخرین سیلندر نیز ادامه نمی یابد بلکه از اولین درخواست شروع شده و به آخرین درخواست ختم میگردد. یعنی اگر تعداد کل سیلندر ها 300 باشد در روش SCAN یا C-SCAN پس از سرویس دهی به سیلندر 183 هد به سراغ سیلند ر 300 رفته و دوباره به سمت دیگر دیسک بر می گردد. ولی در روش LOOK پس از سرویس دهی به سیلندر 183 چون جلوتر از خود سیلندر منتظر سرویسی را نمی بیند از همان جا بر میگردد.
5- الگوریتم مرور N گامی(N-Step-SCAN)
در این الگوریتم به جای یک صف درخواستی ، تعدادی زیر صف به طول N وجود دارد که درخواست های درون هر زیر صف به روش SCAN زمان بندی می شوند و در طی پردازش یک صف، درخواست های جدید به صف های دیگر وارذ می شوند.
امیدوارم مفید واقع بشه
برگرفته از کتاب سیستم عامل پوران پژوهش (کتاب خوبیه!!! :-) )
عاااااااااااااالی بوووود