الگوریتم های زمان بندی دیسک — ۶ الگوریتم بررسی درخواست های دیسک

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

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

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

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

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

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

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

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

الگوریتم FCFS (First Come First Serve) در الگوریتم های زمان بندی دیسک

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

• بررسی و مقایسه الگوریتم های زمانبندی در سیستم عامل—کلیک کنید.

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

مثال: فرض کنید یک دیسک با ۲۰۰ ترک (از ۰ تا ۱۹۹) و توالی درخواست‌های دیسک (۸۲،۱۷۰،۴۳،۱۴۰،۲۴،۱۶،۱۹۰) با سر دیسک در درخواست ۵۰ وجود دارد.

توضیحات: در تصویر بالا، مشاهده می‌شود که سر دیسک از موقعیت ۵۰ شروع می‌کند و به درخواست ۸۲ حرکت می‌کند. پس از رسیدگی به این درخواست‌ها، بازوی دیسک به سمت درخواست دوم یعنی ۱۷۰ حرکت می‌کند و سپس به درخواست ۴۳ و به همین ترتیب. در این الگوریتم، بازوی دیسک درخواست‌ها را به ترتیب ورود به صورت رسیدگی می‌کند. به این ترتیب، تا زمان اجرای فرآیند، همه درخواست‌ها به ترتیب ورود پاسخ داده می‌شوند.

“زمان جستجو” با جمع اختلاف حرکت بازوی دیسک بین همه درخواست‌ها محاسبه می‌شود:

(۸۲-۵۰) + (۱۷۰-۸۲) + (۱۷۰-۴۳) + (۱۴۰-۴۳) + (۱۴۰-۲۴) + (۲۴-۱۶) + (۱۹۰-۱۶) = 642

مزایا:

• پیاده‌سازی آسان است.
• امکان وقوع گرسنگی وجود ندارد.

معایب:

• “زمان جستجو” افزایش می‌یابد.
• کارآیی زیادی ندارد.

الگوریتم SSTF (Shortest Seek Time First) در الگوریتم های زمان بندی دیسک

این الگوریتم بر اساس کمترین زمان جستجوی دیسک برای داده‌ها کار می‌کند. با انتخاب داده‌هایی که کمترین زمان جستجو را نیاز دارند، دسترسی به داده‌ها بهبود می‌یابد. این الگوریتم به مراتب بهینه‌تر از FIFO است و مشکلات تاخیر در دسترسی به داده‌ها را کاهش می‌دهد. اما در برخی موارد، ممکن است منجر به ایجاد تبادل‌های پیوسته دیسک (Disk Thrashing) شود که باعث کاهش عملکرد کلی سیستم می‌شود.

Shortest Seek Time First به معنای “کوتاه‌ترین زمان جستجو اول” است. همانطور که از نامش پیداست، درخواست‌هایی که کمترین “زمان جستجو” را دارند پیدا و ابتدا اجرا می‌شوند. این الگوریتم “زمان جستجو” کمتری نسبت به الگوریتم FCFS دارد.

مثال: فرض کنید یک دیسک با ۲۰۰ ترک (از ۰ تا ۱۹۹) و توالی درخواست‌های دیسک (۸۲،۱۷۰،۴۳،۱۴۰،۲۴،۱۶،۱۹۰) و سر دیسک در موقعیت ۵۰ وجود دارد.

توضیحات: بازوی دیسک به دنبال درخواستی می‌گردد که کمترین اختلاف در حرکت بازو دیسک را داشته باشد. بنابراین، کمترین اختلاف (۵۰-۴۳) است. اینجا اختلاف مربوط به کمترین مقدار نیست، بلکه مربوط به کوتاه‌ترین زمانی است که بازوی دیسک برای رسیدن به درخواست بعدی نزدیکترین آن را طی می‌کند. بنابراین، پس از ۴۳، بازوی دیسک به نزدیکترین درخواست ۲۴ حرکت می‌کند و از اینجا بازوی دیسک به نزدیکترین درخواست ۱۶ حرکت می‌کند. پس از ۱۶، نزدیکترین درخواست ۸۲ است، بنابراین بازوی دیسک به سمت پاسخ دادن به درخواست ۸۲ حرکت می‌کند و به همین ترتیب ادامه می‌دهد.

بنابراین، محاسبه زمان جستجو بدین صورت خواهد بود:

(۵۰-۴۳) + (۴۳-۲۴) + (۲۴-۱۶) + (۸۲-۱۶) + (۱۴۰-۸۲) + (۱۷۰-۱۴۰) + (۱۹۰-۱۷۰) = 208

مزایا:

• در این الگوریتم، زمان پاسخ دیسک کمتر است.
• موثرتر از FCFS است.

معایب:

• سرعت اجرای الگوریتم کمتر است.
• ممکن است گرسنگی رخ دهد.

الگوریتم SCAN (آسانسور) در الگوریتم های زمان بندی دیسک

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

در این الگوریتم، سر دیسک ابتدا همه درخواست‌ها را در یک جهت اسکن می‌کند و تا انتهای دیسک می‌رسد. پس از آن، جهت خود را معکوس کرده و دوباره درخواست‌ها را در مسیر خود اسکن کرده و به آن‌ها رسیدگی می‌کند. به دلیل این ویژگی، این الگوریتم به عنوان “الگوریتم آسانسور” نیز شناخته می‌شود.

مثال: فرض کنید یک دیسک با ۲۰۰ ترک (از ۰ تا ۱۹۹) و توالی درخواست‌های دیسک (۸۲،۱۷۰،۴۳،۱۴۰،۲۴،۱۶،۱۹۰) و سر دیسک در موقعیت ۵۰ وجود دارد. “بازوی دیسک” ابتدا به سمت مقادیر بزرگ‌تر حرکت می‌کند.

توضیحات: در تصویر بالا، می‌توانیم ببینیم که بازوی دیسک از موقعیت ۵۰ شروع می‌کند و در یک جهت تا زمانی که به انتهای دیسک یعنی موقعیت درخواست ۱۹۹ می‌رسد، حرکت می‌کند. پس از آن، جهت خود را معکوس کرده و در جهت مخالف به درخواست‌ها پاسخ می‌دهد تا به انتهای دیگر دیسک برسد. این فرآیند تا زمان اجرای فرآیند ادامه می‌یابد. بنابراین، محاسبه “زمان جستجو” به شکل زیر خواهد بود:

(۱۹۹-۵۰) + (۱۹۹-۱۶) =۳۳۲

مزایا:

• پیاده‌سازی آسان است.
• درخواست‌ها نیازی به انتظار در یک صف ندارند.

معایب:

• سر دیسک حتی اگر در آن جهت درخواستی نباشد همچنان به انتهای آن حرکت می‌کند.

الگوریتم C-SCAN (چرخش) در الگوریتم های زمان بندی دیسک

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

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

الگوریتم راند رابین در سیستم عامل – آموزش کامل الگوریتم راند رابین همراه با ۲ مثال

کلیک کنید

مثال: فرض کنید یک دیسک با ۲۰۰ ترک (از ۰ تا ۱۹۹) و توالی درخواست‌های دیسک (۸۲،۱۷۰،۴۳،۱۴۰،۲۴،۱۶،۱۹۰) و سر دیسک در موقعیت ۵۰ وجود دارد.

توضیحات: در تصویر بالا، بازوی دیسک از موقعیت ۵۰ شروع می‌کند و به انتهای دیسک (۱۹۹) می‌رسد و همه درخواست‌ها را در مسیر رسیدگی می‌کند. سپس جهت خود را معکوس کرده و به سمت انتهای دیگر دیسک یعنی ۰ حرکت می‌کند و در مسیر هیچ درخواستی را پاسخ نمی‌دهد. پس از رسیدن به ۰، دوباره به سمت بزرگ‌ترین مقدار باقی‌مانده یعنی ۴۳ حرکت می‌کند. بنابراین، سر دیسک از ۰ شروع می‌کند و به درخواست ۴۳ حرکت کرده و همه درخواست‌های موجود در مسیر را رسیدگی می‌کند و این فرآیند ادامه دارد.

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

(۱۹۹-۵۰) + (۱۹۹-۰) + (۴۳-۰) =۳۹۱

مزایا:

• زمان انتظار به طور یکنواخت بین درخواست‌ها توزیع می‌شود.
• زمان پاسخ در آن مناسب است.

معایب:

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

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

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

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

مثال: فرض کنید یک دیسک با ۲۰۰ ترک (از ۰ تا ۱۹۹) و توالی درخواست‌های دیسک (۸۲،۱۷۰،۴۳،۱۴۰،۲۴،۱۶،۱۹۰) و سر دیسک در موقعیت ۵۰ وجود دارد.

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

(۱۹۰-۵۰) + (۱۹۰-۱۶) =۳۱۴

مزایا:

• گرسنگی رخ نمی‌دهد.
• زمانی که بازوی دیسک به انتهای دیسک نمی‌رود، زمان هدر رفته نیست.

معایب:

• بازو باید به دقت درخواست‌های آخر را پیدا کند.

الگوریتم C-LOOK در الگوریتم های زمان بندی دیسک

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

مثال: فرض کنید یک دیسک با ۲۰۰ ترک (از ۰ تا ۱۹۹) و توالی درخواست‌های دیسک (۸۲،۱۷۰،۴۳،۱۴۰،۲۴،۱۶،۱۹۰) و سر دیسک در موقعیت ۵۰ وجود دارد.

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

(۱۹۰-۵۰) + (۱۹۰-۱۶) + (۴۳-۱۶) =۳۴۱

مزایا:

• زمان انتظار کاهش می‌یابد.
• اگر تا انتهای دیسک درخواستی وجود نداشته باشد، سر دیسک فوراً جهت خود را معکوس می‌کند.
• گرسنگی رخ نمی‌دهد.
• زمانی که بازوی دیسک برای یافتن محل مورد نظر استفاده می‌شود، کمتر است.

معایب:

• بازو باید به طور دقیق درخواست‌های آخر را پیدا کند.

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

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

با توجه به نوع الگوریتم، به محدودیت‌هایی مانند زمان جستجو، اختلاف حرکت بازوی دیسک و ایجاد گرسنگی توجه می‌شود. الگوریتم‌های مختلف شامل First-Come-First-Served (FCFS)، Shortest Seek Time First (SSTF)، Scan، C-Scan و C-Look هستند که هر کدام ویژگی‌ها و مزایا و معایب خود را دارند.

پاورپوینت انواع سیستم عامل از لحاظ عملکرد

پاورپوینت انواع سیستم عامل از لحاظ عملکرد

کلیک کنید