الگوریتم های زمان بندی (Scheduling Algorithms) در سیستم عامل — راهنمای جامع

۱۱۸۱۳ بازدید
آخرین به‌روزرسانی: ۲۶ شهریور ۱۴۰۲
زمان مطالعه: ۴ دقیقه
الگوریتم های زمان بندی (Scheduling Algorithms) در سیستم عامل — راهنمای جامع

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

997696
  • زمان‌بندی «اجرا به ترتیب ورود» (First-Come, First-Served) یا به اختصار (FCFS)
  • زمان‌بندی «کوتاه‌ترین کار بعدی» (Shortest-Job-Next) یا به اختصار (SJN)
  • زمان‌بندی اولویت (Priority)
  • زمان‌بندی کوتاه‌ترین زمان باقیمانده (Shortest Remaining Time)
  • زمان‌بندی نوبت گردشی یا راند رابین (Round Robin) یا به اختصار (RR)
  • زمان‌بندی صف‌های چند سطحی (Multiple-Level Queues)

الگوریتم‌های فوی کی از دو حالت «پیش‌دستانه» (preemptive) یا «غیر پیش‌دستانه» (non-preemptive) را دارند. الگوریتم‌های غیر پیش‌دستانه چنان طراحی شده‌اند که وقتی پراسسی وارد حالت اجرایی شد، تا زمانی که زمان تخصیص‌یافته‌اش پایان نیافته است، تخلیه نشود، اما در زمان‌بندی پیش‌دستانه همه چیزبه اولویت‌بندی بستگی دارد و زمانی که یک پراسس با اولویت  بالا وارد حالت آماده‌به‌کار می‌شود، ممکن است پراسس دارای اولویت پایین‌تر خالی شود.

اجرا به ترتیب ورود (FCFS)

این روش زمان‌بندی کارها، خصوصیات زیر را دارد:

  • وظایف به ترتیب ورود اجرا می‌شوند.
  • یک الگوریتم زمان‌بندی غیر preemptive و pre-emptive است.
  • درک و پیاده‌سازی آسانی دارد.
  • پیاده‌سازی آن مبتنی بر صف FIFO است.
  • عملکرد آن پایین است، زیرا میانگین زمان انتظار بالا است.

زمان انتظار هر پردازش به صورت زیر است:

پردازشزمان انتظار: زمان سرویس - زمان رسیدن
P00 - 0 = 0
P15 - 1 = 4
P28 - 2 = 6
P316 - 3 = 13

زمان انتظار میانگین:

(0+4+6+13) / 4 = 5.75

کوتاه‌ترین کار بعدی (SJN)

این الگوریتم خصوصیات زیر را دارد:

  • این روش به نام «ابتدا، کوتاه‌ترین کار» یا SJF نیز نامیده می‌شود.
  • یک الگوریتم زمان‌بندی غیر preemptive و pre-emptive است.
  • رویکرد ساده‌ای برای کاهش زمان انتظار محسوب می‌شود.
  • در سیستم‌های دسته‌ای که زمان مورد نیاز CPU از پیش مشخص نیست به سادگی پیاده‌سازی می‌شود.
  • پیاده‌سازی آن در سیستم‌های تعاملی که زمان مورد نیاز CPU مشخص نیست ناممکن است.
  • پردازنده باید از قبل بداند که پردازش چه مدت طول خواهد کشید.
پردازشزمان رسیدنزمان اجرازمان سرویس
P0050
P1135
P22814
P3368

زمان انتظار هر پردازش به صورت زیر است:

پردازشزمان انتظار: زمان سرویس - زمان رسیدن
P00 - 0 = 0
P15 - 1 = 0
P2114 - 2 = 12
P38 - 3 = 5

میانگین زمان انتظار:

(0+4+12+5) / 4 = 21 / 4 = 5.25

زمان‌بندی مبتنی بر اولویت

این روش خصوصیات زیر را دارد:

  • زمان‌بندی اولویت یک الگویتم غیر preemptive است و یکی از رایج‌ترین الگوریتم‌های زمان‌بندی در سیستم‌های دسته‌ای محسوب می‌شود.
  • هر پردازش یک اولویت دارد. پردازش دارای بالاترین اولویت ابتدا اجرا می‌شود و همین طور تا آخرین پردازش.
  • پردازش‌های دارای اولویت یکسان به روش «اجرا به ترتیب ورود» اجرا می‌شوند.
  • اولویت می‌تواند بر مبنای الزامات حافظه، الزامات زمانی یا هر الزام دیگر برای منابع تعیین شود.

در جدول زیر پردازش‌ها، زمان رسیدن، زمان اجرا و اولویت آن‌ها داده شده است. در این جدول عدد 1 دارای کمترین اولویت است.

پردازشزمان رسیدنزمان اجرااولویتزمان سرویس
P00510
P113211
P228114
P33635

زمان انتظار هر پردازش به صورت زیر است:

پردازشزمان انتظار: زمان سرویس - زمان رسیدن
P00 - 0 = 0
P111 - 1 = 10
P214 - 2 = 12
P35 - 3 = 2

میانگین زمان انتظار به صورت زیر است:

(0 + 10 + 12 + 2)/4 = 24 / 4 = 6

کوتاه‌ترین زمان باقی‌مانده

این روش خصوصیات زیر را دارد:

  • کوتاه‌ترین زمان باقی‌مانده (SRT) نسخه preemptive از الگوریتم SNJ محسوب می‌شود.
  • زمان پردازنده به وظیفه‌ای که خاتمه یافتن آن به کمترین زمان نیاز دارد تخصیص می‌یابد؛ اما می‌تواند به وظیفه جدیدتری که زمان اجرای کوتاه‌تری دارد نیز اختصاص یابد.
  • پیاده‌سازی سیستم‌های تعاملی که در آن زمان مورد نیاز CPU مشخص نباشد در این روش ممکن نیست.
  • این روش غالباً در محیط‌های دسته‌ای که کوتاه‌ترین کار باید بالاترین اولویت را داشته باشد مورد استفاده قرار می‌گیرد.

زمان‌بندی راند رابین یا نوبت گردشی

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

زمان انتظار هر پردازش به صورت زیر است:

پردازشزمان انتظار: زمان سرویس - زمان رسیدن
P0(0 - 0) + (12 - 3) = 9
P1(3 - 1) = 2
P2(6 - 2) + (14 - 9) + (20 - 17) = 12
P3(9 - 3) + (17 - 12) = 11

میانگین زمان انتظار:

(9+2+12+11) / 4 = 8.5

زمان‌بندی صف چند سطحی

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

  • صف‌های چندگانه‌ای برای پردازش‌های دارای خصوصیات مشترک نگهداری می‌شوند.
  • هر صف می‌تواند الگوریتم زمان‌بندی خاص خود را داشته باشد.
  • اولویت‌هایی برای هر صف تعیین می‌شود.

برای مثال کارهای مرتبط با CPU را می‌توان در یک صف زمان‌بندی کرد و همه کارهای مرتبط با I/O را نیز می‌توان در صف دیگری جمع‌بندی نمود. سپس زمان‌بندی پردازش به نوبت وظایف کارها را از هر صف انتخاب می‌کند و آن‌ها را بر اساس الگویتم تعیین شده برای هر صف به CPU تخصیص می‌دهد.

اگر این مطلب برایتان مفید بوده است، آموزش‌های زیر نیز به شما پیشنهاد می‌شوند:

==

بر اساس رای ۳۷ نفر
آیا این مطلب برای شما مفید بود؟
اگر بازخوردی درباره این مطلب دارید یا پرسشی دارید که بدون پاسخ مانده است، آن را از طریق بخش نظرات مطرح کنید.
منابع:
tutorialspoint
۱۵ دیدگاه برای «الگوریتم های زمان بندی (Scheduling Algorithms) در سیستم عامل — راهنمای جامع»

سلام مثال زمان‌بندی مبتنی بر اولویت دارای اشکال هست
در واقع ابتدا p0 یک ثانیه اجرا میشه اما با ورود p1 به دلیل داشتن اولویت بالاتر اون اجرا میشه

با سلام و احترام؛

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

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

برای شما آرزوی سلامتی و موفقیت داریم.

سلام خسته نباشید ممنون ، مطالب تون عالی بود

ببخشید میتونین جواب اینو بگین
سیستمی از روش SRT استفاده میکند ، در صورت اجرای 4 فرایند مطابق جدول زیر اجرای کدام فرایندها دیرتر به اتمام میرسد؟ (سیستم عامل)

P# AT CBT
P1 0 8
P2 2 2
P3 5 5
P4 11 3

سلام محاسبه میانگین زمان برگشت مانند میانگین زمان انتظار باید با هم جمع بشه و تقسیم بر تعداد فرایند بشه؟

سلام؛ از دوستان کسی کدهای پیاده سازی یکی از این الگوریتم ها رو در پایتون داره؟

P1=0 4
P2=0 3
P3=2 2
P4=5 2
زمان انتظار این چقدر هست ممنون میشم جواب بدید

سلام ممنون میشم جواب سوال منم بدین
P0 0 4
P1 2 2
P2 3 3
P3 5 7
P4 6 2
Fcfs.RR.sjf.srt

سلام وققتون بخیر ممنون از مطالب مفید سایتتون خیله وقته دنبال سایت کتابی می گردم که این مفاهیم را بفهمم ولی سایت شما عالی بود .
من در یک مسله گیر کردم ممنون میشم جوابمو بدید
اطلاعات مربوط به چهار فرایند در جدول زیر اورده شده است . با استفاده از الگوریتم زمان بندی hrrn (بالاترین نسبت پاسخ ) نمودار گانت مربوطه را رسم نموده و میانگین زمان انتضار و پاسخ را به دست اورید ؟
زمان اجرا زمان ورود فرایند
12 2 p0
9 2 p1
6 3 p2
3 15 p3
ممنون میشم جوابموه بدید

با سلام و تشکر از مطالب مفیدتون
در قسمت SJN و در خصوصیت چهارم که میگه :
در سیستم‌های دسته‌ای که زمان مورد نیاز CPU از پیش مشخص نیست به سادگی پیاده‌سازی می‌شود.
به نظرم مشکلی هست چون زمان مورد نیاز CPU از پیش مشخص است.

با سلام

مثالها دارای اشکال می باشد.

سلام، وقت شما بخیر؛

مثال‌های مطلب مورد بازبینی قرار گرفتند و اصلاح شدند.

از همراهی شما با مجله فرادرس و ارائه بازخورد برای بهبود آن بسیار سپاسگزاریم.

در مثال های ذکر شده برای الگوریتم مشکل های جزیی وجود داره یا من بلد نیستم؟

ظاهرا مشکل داره.
مطلب برگرفته از این ریفرنس هست:

https://www.tutorialspoint.com/operating_system/os_quick_guide.htm

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

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

نظر شما چیست؟

نشانی ایمیل شما منتشر نخواهد شد. بخش‌های موردنیاز علامت‌گذاری شده‌اند *