الگوریتم SJF چیست؟ در سیستم عامل چه کاربردی دارد؟

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

الگوریتم SJF چیست؟

الگوریتم SJF در واقع از کلمات «Shortest Job First» گرفته شده است. این در واقع به این معنی است که در کار با این الگوریتم همیشه اول کوتاه‌ترین کار انجام می‌شود. همان طور که گفتیم از این الگوریتم برای زمان‌بندی منابع سخت‌افزاری مورد استفاده، مانند CPU، حافظه و ماژول‌های ورودی و خروجی استفاده می‌شود. به طور کلی الگوریتم SJF با دو استراتژی انحصاری و غیر انحصاری کار می‌کند و میانگین زمان انتظار برای انجام شدن فعالیت‌ها را کاهش می‌دهد.

برخی از رقیب‌های سرسخت این الگوریتم که برای زمان‌بندی فرآیند‌ها مورد استفاده قرار می‌گیرند، شامل الگوریتم‌های جستجوی شکار (HUS)، RR، FCFS و HRRN هستند. این الگوریتم برای کارکرد صحیح لازم است، زمان تکمیل فرآیند‌ها را به درستی تعیین کند تا بتواند کار‌های با زمان کمتر را زودتر به سیستم عامل دهد. از آن جایی که تعیین زمان مورد نیاز برای انجام فرآیند‌ها کار دشواری است، این مسأله به یکی چالش‌های کار با این الگوریتم تبدیل می‌شود که در ادامه این مطلب روش‌های مدیریت این چالش را بررسی کرده‌ایم.

استخدام برنامه نویس متلب

زمان تکمیل فرآیند‌ها در الگوریتم SJF چگونه محاسبه می‌شود؟

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

روش های‌ ایستا

در کار با روش‌های‌ ایستا می‌توان از دو تکنیک مختلف استفاده کرد که شامل موارد زیر هستند.

اندازه فرآیند

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

نوع فرآیند

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

روش‌های پویا

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

الگوریتم SJF دارای چه ویژگی‌هایی است؟

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

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

مطلب پیشنهادی: الگوریتم علف هرز (IWO) چیست؟

الگوریتم SJF در سیستم عامل چگونه کار می‌کند؟

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

1. در اولین قدم باید تمام فرآیند‌ها باید بر اساس زمان رسیدن و زمان تقریبی انجام مرتب شوند تا سیستم بتواند، فرآیند‌های دارای کمترین زمان انجام را که زودتر از بقیه رسیده‌اند در اولویت انجام قرار دهد.
2. در دومین قدم می‌توانیم به جای بررسی تک به تک از ساختمان داده درخت بازه‌ها استفاده کنیم و فرآیند‌های مختلف را بر اساس کمترین زمان انجام مرتب کنیم.
3. بعد از پیدا کردن فرایند دارای صلاحیت ارسال به CPU، از اطلاعات «زمان رسیدن» (Arrival Time | AT) به صف و «زمان تکمیل فرایند» (Burst Time | BT) برای محاسبه زمان‌های مختلف استفاده می‌کنیم.

زمان‌های مختلف مربوط به انجام هر فرآیند در الگوریتم SJF چگونه محاسبه می‌شوند؟

در انجام هر فرآیندی با زمان‌های مختلفی از جمله زمان تکمیل عملیات، زمان انجام فعالیت و زمان انتظار رو به رو هستیم.

زمان تکمیل عملیات CT

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

زمان مورد نیاز برای انجام فعالیت TAT

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

زمان انتظار WT

این زمان در واقع نشان دهنده تفاوت بین زمان مورد نیاز برای انجام فعالیت و زمان تکمیل کار فرآیند گفته می‌شود.

الگوریتم SJF در سیستم عامل دارای چه استراتژی‌هایی است؟

الگوریتم SJF دارای دو استراتژی بسیار رایج است که شامل رویکرد‌های انحصاری و غیر انحصاری هستند که این‌ها را در ادامه بررسی می‌کنیم.

رویکرد انحصاری

در رویکرد انحصاری زمانی که یک فرآیند توسط CPU آغاز می‌شود تا زمان به پایان رسیدن فرآیند متوقف نمی‌شود، مگر در صورتی که یک دستور توقف از بیرون و توسط کاربر صادر شود.

رویکرد غیر انحصاری

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

مطلب پیشنهادی: الگوریتم علی بابا و چهل دزد

الگوریتم SJF دارای چه مزایایی است؟

1. این الگوریتم دارای مزایای فراوانی است که باعث محبوبیت و کاربرد فراوان آن شده است. برخی از مهم‌ترین مزایای این الگوریتم شامل موارد زیر هستند.
2.  الگوریتم SJF نسبت به الگوریتم‌های زمان‌بندی دیگر مانند FCFS دارای میانگین زمان انتظار کوتاه‌تری است.
3. از این الگوریتم می‌توان برای انجام زمان‌بندی در تایم‌های طولانی نیز استفاده کرد.
4. الگوریتم SJF یک گزینه مناسب برای فرآیند‌هایی است که به صورت دسته‌ای ارسال می‌شوند و زمان اجرای آن‌ها از قبل مشخص شده است.

معایب الگوریتم SJF چیست؟

1.  الگوریتم SJF نیز مانند الگوریتم‌های دیگر در کنار مزایای فراوانی که دارد دارای معایبی نیز هست که مهم‌ترین آن‌ها را در ادامه برایتان ذکر می‌کنیم.
2. در الگوریتم SJF بر اساس انجام سریع‌تر کار‌ها با زمان تکمیل کمتر طراحی شده است و این می‌تواند باعث افزایش زمان تکمیل کار‌های زمان بر‌تر شود و باعث ایجاد گرسنگی در این فعالیت‌ها می‌شود.
3. این الگوریتم برای کار خود نیاز به تعیین تایم انجام کار‌ها دارد که این فرآیند، در بسیاری از مواقع می‌تواند سخت و چالش برانگیز باشد.
4. همان طور که گفتیم تنها می‌توان زمان انجام فعالیت‌ها را تخمین زد و نمی‌توان آن‌ها را به طور دقیق تعیین کرد به همین دلیل نیز نمی‌توان از این الگوریتم برای زمان‌بندی‌های کوتاه مدت در CPU استفاده کرد.
5. در الگوریتم SJF نمی‌توان برای انجام فرآیند‌ها اولویت دیگری تعیین کرد.

مطلب پیشنهادی: الگوریتم کروسکال چیست؟

سخن نهایی

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