الگوریتم های زمانبندی پردازنده در سیستم عامل | فرمول الگوریتم های زمانبندی CPU
در ویدیو بالا به طور کلی الگوریتم های زمانبندی پردازنده در سیستم عامل را معرفی کردیم .در ادامه به بررسی تخصصی هر یک از الگوریتم های زمانبندی در پردازنده میپردازیم .
در یک سیستم کامپیوتری هزاران و شاید میلیونها پردازش در یک لحظه در حال اجرا باشند. اگر پردازنده بخواهد همه کارها را به ترتیب انجام دهد، دیگر نخواهیم توانست به طور همزمان با برنامههای مختلف کار کنیم! زمانبندی پردازنده یا به طور دقیقتر، الگوریتمهای زمانبندی در سیستم عامل برای مدیریت درست فرآیندها در هنگام پردازش به وجود آمدهاند.
در این مقاله قصد داریم الگوریتمهای زمانبندی پردازنده را با هم بررسی کرده و مزایا و معایب هر الگوریتم را بررسی کنیم. هر کدام از الگوریتمهایی که در ادامه درباره آنها صحبت میکنیم، به تنهایی میتوانند یک موضوع طولانی و با ریزهکاریهای زیاد باشند. درمورد میانگین عمر قطعات کامپیوتر بیشتر بدانید !
پردازنده چیست ؟
پردازنده (Processor) یا میکروپروسسور (Microprocessor)، سختافزاری است که وظیفه اجرای دستورات و عملیاتهای محاسباتی را در یک سیستم کامپیوتری بر عهده دارد. پردازنده، بخش اصلی و مهم ترین قسمت سیستم کامپیوتری محسوب میشود و تمامی عملیاتها و پردازشهای انجام شده در سیستم، از طریق آن صورت میگیرد.
پردازندهها برای انواع مختلف سیستمهای کامپیوتری و دیگر دستگاههای الکترونیکی مانند تلفنهای همراه، تبلتها، کنسولهای بازی و… طراحی و ساخته میشوند. پردازندهها با توجه به سطح عملکرد و قدرت پردازشی، به دستههایی مانند پردازندههای موبایل، لپتاپ، دسکتاپ و سرور تقسیم میشوند.
در طراحی پردازنده، از مدارهای الکترونیکی پیچیده و متعددی استفاده میشود که در کنار هم قادر به انجام تعداد بسیار زیادی از دستورات و عملیاتهای مختلف محاسباتی هستند. به طور خلاصه، پردازنده یکی از اصلیترین قسمتهای سختافزاری سیستم کامپیوتری است که برای اجرای دستورات و عملیاتهای محاسباتی به کار میرود.
الگوریتم زمانبندی پردازنده چیست ؟
الگوریتم زمانبندی پردازنده (Processor Scheduling Algorithm)، الگوریتمی است که برای تعیین ترتیب اجرای فرآیندهای مختلف در سیستم عامل به کار میرود. هدف این الگوریتم، بهینهسازی استفاده از منابع سیستم و افزایش عملکرد سیستم است.
در الگوریتم زمانبندی پردازنده، پردازنده بین فرآیندهای مختلف تقسیم میشود و به هر فرآیند زمان مشخصی برای اجرا اختصاص داده میشود. این الگوریتم، تعیین کننده ترتیب اجرای فرآیندهای موجود در صف انتظار پردازش است.
الگوریتمهای زمانبندی پردازنده مختلفی وجود دارند که برای موارد مختلف مانند سیستمهای بلادرنگ (Real-time Systems)، سیستمهای چند وظیفهای (Multitasking Systems) و غیره مناسب هستند. برخی از الگوریتمهای معروف زمانبندی پردازنده عبارتند از:
- First-Come, First-Served (FCFS)
- Shortest Job First (SJF)
- Priority Scheduling
- Round Robin (RR)
- Multilevel Queue Scheduling
- Multilevel Feedback Queue Scheduling
هر الگوریتم زمانبندی پردازنده مزایا و معایب خود را دارد و باید با توجه به نیازها و محدودیتهای سیستم، الگوریتم مناسبی انتخاب شود.
آیا الگوریتمهای زمانبندی پردازنده میتوانند باعث تاخیر در اجرای فرآیندها شوند؟
بله، الگوریتمهای زمانبندی پردازنده میتوانند باعث تاخیر در اجرای فرآیندها شوند. در واقع، هدف این الگوریتمها بهینهسازی استفاده از پردازنده و بهبود عملکرد سیستم است. اما در نتیجه استفاده از الگوریتمهای زمانبندی، ممکن است برخی از فرآیندها به دلیل تأخیر در اجرا، نتوانند به موقع انجام شوند.
علاوه بر این، الگوریتمهای زمانبندی پردازنده باید به گونهای باشند که تاخیر در اجرای فرآیندها به حداقل برسد و اجرای همزمان چندین فرآیند را ممکن سازند. برای مثال، الگوریتمهایی مانند Round Robin که زمان لازم برای اجرای هر فرآیند را محدود میکنند و به ترتیب به هر فرآیند زمان اختصاص میدهند، میتوانند باعث کاهش تاخیر در اجرای فرآیندها شوند.
به طور کلی، الگوریتمهای زمانبندی پردازنده باید به گونهای طراحی شوند که بهبود عملکرد سیستم را فراهم کنند و در عین حال تاخیر در اجرای فرآیندها را به حداقل برسانند.
آیا الگوریتمهای زمانبندی پردازنده در سیستمهای بزرگ هم استفاده میشوند؟
بله، الگوریتمهای زمانبندی پردازنده در سیستمهای بزرگ نیز به کار میروند. در واقع، الگوریتمهای زمانبندی پردازنده در سیستمهای بزرگ بسیار مهم هستند چرا که در این سیستمها تعداد فرآیندهای قابل اجرا به شدت بالاست و برای مدیریت و تخصیص منابع بهینهای به هر فرآیند نیاز داریم.
سیستمهای بزرگ مانند سرورهای دیتاسنتر، سیستمهای توزیع شده، سیستمهای پردازش داده و… با تعداد فرآیندهای بسیار زیاد، نیاز به الگوریتمهای زمانبندی پردازنده دارند تا تخصیص منابع بهینهای به هر فرآیند انجام شود و عملکرد سیستم را بهبود بخشند.
در سیستمهای بزرگ، الگوریتمهای زمانبندی پردازنده با توجه به نیازهای سیستم و نوع فرآیندها انتخاب میشوند. برای مثال، در سیستمهای بلادرنگ، الگوریتمهایی مانند Rate Monotonic Scheduling و Earliest Deadline First Scheduling برای تخصیص منابع به فرآیندها استفاده میشوند. در سیستمهای پردازش داده، الگوریتمهایی مانند Fair Share Scheduling و Weighted Fair Queuing Scheduling برای تخصیص منابع به دادهها و کاربران استفاده میشوند.
بنابراین، الگوریتمهای زمانبندی پردازنده در سیستمهای بزرگ نقش مهمی در بهبود عملکرد و تخصیص منابع بهینه به فرآیندها دارند.
قحطی زدگی در الگوریتم های زمانبندی پردازنده به چه معناست ؟
قحطی زدگی (Starvation) در الگوریتمهای زمانبندی پردازنده به معنای این است که یک فرآیند به طور مداوم مورد تأخیر در اجرای الگوریتم قرار میگیرد و نمیتواند به موقع اجرای خود برسد. به عبارت دیگر، در این وضعیت، فرآیند مشخصی به دلیل عدم تخصیص منابع کافی به آن، نمیتواند به موقع اجرای خود برسد و به صورت مداوم به تأخیر میافتد.
این مشکل معمولاً در الگوریتمهای زمانبندی پردازنده با الگوی اولویتبندی برای تخصیص منابع به فرآیندها رخ میدهد. در این الگوریتمها، فرآیندهای با اولویت بالاتر، به زودیتر منابع را دریافت و به اجرای خود میرسند و فرآیندهای با اولویت پایینتر به تأخیر میافتند. اگر یک فرآیند به طور مداوم به تأخیر بیفتد و هیچ منبعی به آن تخصیص داده نشود، در نتیجه با قحطی زدگی مواجه میشود.
برای جلوگیری از قحطی زدگی در الگوریتمهای زمانبندی پردازنده، میتوان از روشهای مختلفی مانند تخصیص منابع به صورت منصفانه (Fairness) و یا استفاده از الگوریتمهای زمانبندی پویا (Dynamic Scheduling) استفاده کرد. در الگوریتمهای زمانبندی پویا، تخصیص منابع به فرآیندها بر اساس وضعیت جاری سیستم و شرایط مختلف تغییر میکند، بنابراین فرآیندها به صورت منصفانه به منابع دسترسی دارند و قحطی زدگی کاهش مییابد.
فرآیند پردازنده چیست ؟
یک فرآیند (Process) اساساً یک برنامهی در حال اجراست. منظور از برنامه در حال اجرا، کاری است که توسط زمانبندِ کار، انتخاب و وارد گردونهی اجرا شده است ولی هنوز پایان نیافته و از سیستم خارج نشده است. این فرآیند الزاماً در حال حاضر CPU را در اختیار ندارد.
الگوریتمهای زمان بندی پردازنده یکی از مواردی است که باید در مورد مدیریت فرآیندها در سیستم عامل مورد بررسی قرار بگیرد.
هدف الگوریتم های زمانبندی پردازنده
هدف از زمانبندی پردازنده، تخصیص فرآیندها به پردازنده در طول زمان است که گونهای که هدفهای سیستم از قبیل زمان پاسخ، توان عملیاتی و کارایی پردازنده را برآورده سازد. زمانبندی پردازنده، اساس سیستمهای عامل چند برنامهای است.
معیارهای زمانبندی پردازنده
قبل از بررسی الگوریتمهای زمانبندی پردازنده، لازم است تا با معیارهای مقایسه الگوریتمهای زمان بندی پردازنده آشنا شومی.
به طور کلی این معیارها به دو دسته تقسیمبندی میشوند.
- معیارهای از دید کاربر (مانند زمان پاسخ)
- معیارهای از دید سیستم (مانند توان عملیاتی و بهرهوری پردازنده)
چهار معیار مقایسه الگوریتمهای زمانبند
1- اولین معیار، زمان انتظار هر فرآیند است.
زمان انتظار فرآیند به میزان زمانی گفته میشود که فرآیند باید منتظر بماند تا پردازنده (CPU) به آن تعلق بگیرد.
فرض کنید یک فرآیند وارد چرخه کار شده و چند ثانیه منتظر تخصیصی پردازنده میماند. پس از چند لحظه، CPU از آن گرفته شده و فرآیند میبایست منتظر تخصیص پردازنده بماند. به مجموع تمام این زمانها زمان انتظار فرآیند یا پردازش گفته میشود.
2- دومین معیار، توان عملیاتی (Throughput) پردازنده است. منظور از توان عملیاتی پردازنده، تعداد کار انجام شده در واحد زمان توسط پردازنده است.
3- زمان بازگشت (Turn Around Time): فاصله زمانی بین لحظه تحویل تا تکمیل فرآیند؛ به عبارت دیگر مدت زمانی که Job در سیستم قرار دارد.
4- زمان پاسخگویی (Response Time): فاصله زمانی ورود پردازش به سیستم تا شروع دریافت اولین پاسخ آن .
انواع الگوریتم های زمانبندی پردازنده در سیستم عامل
الگوریتمهای زمانبندی پردازنده در مدیریت فرآیندهای سیستم عامل به دو گروه اصلی تقسیم میشوند.
- الگوریتمهای انحصاری
- الگوریتمهای غیر انحصاری
الگوریتمهای انحصاری (Non Preemptive)
در الگوریتمهای انحصاری زمانبندی پردازنده، همین که یک فرآیند در حالت اجرا قرار گرفت، آنقدر به اجرای خود ادامه میدهد تا به اتمام رسیده یا به صورت داوطلبانه مسدود شود.
در اینگونه الگوریتمها فرآیندها به یکباره اجرا شده و اجرای آنها به چند بخش کوچکتر تقسیمبندی نخواهد شد.
چند الگوریتم انحصاری زمانبندی پردازنده عبارتاند از:
- الگوریتم FCFS
- الگوریتم SJF
- الگوریتم HRRN
الگوریتمهای غیرانحصاری (Preemptive)
در الگوریتمهای غیرانحصاری زمانبندی پردازنده، ممکن است یک فرآیند که در حال اجراست توسط سیستم عامل کامپیوتر متوقف شده و به حالت آماده منتقل شود. این عمل برای تخصیص پردازنده به یک فرآیند دیگر و یا انجام عملیاتهای I/O و وقفه صورت میگیرد.
در اینگونه الگوریتمها، اجرای فرآیندها ممکن است به چند بخش تقسیم شده و در چند بار عملیات تخصیص پردازنده صورت بگیرد.
چند الگوریتم غیرانحصاری زمانبندی پردازنده عبارتاند از:
- الگوریتم RR
- الگوریتم SRTF
- الگوریتم MLFQ
الگوریتم های زمانبندی پردازنده در سیستم عامل
در ادامه مهمترین و اصلیترین الگوریتمهای زمانبندی پردازنده در سیستم عامل را با هم بررسی میکنیم.
الگوریتم زمانبندی FCFS (FIFO) ؛ first come first self
نوبتی مانند صف نونوایی . این الگوریتم ساده ترین الگوریتم زمانبندی است . در این روش کار ها با همان ترتیب ورود به سیستم در صف قرار گرفته و از ابتدا صف به ترتیب پردازنده را در اختیار میگیرد .
نکته ؛ FCFS یک الگوریتم انحصاری است . این الگوریتم مشکل قحطی زدگی ندارند ( ۴ فرایند P1 , P2 , P3 , P4 که ب ترتیب وارد شدند . #میانگین_زمان_انتظار میشه ۵ . فرایندP1 به محض ورود پردازنده را در اختیار گرفته بنابراین زمان انتظار صفر می باشد . فرایند p2 چهار میلی ثانیه و p3 هفت و p4 نه میلی ثانیه منتظر می مامند . بنابراین میانگین زمان انتظار فرایند ها ۵ میلی ثانیه می باشد . در واقا زمان انتظار هی فرایند برابر است با جمع « زمان انتظار همون فرایند و جمع فرایند های قبلی »)
مزایای الگوریتم FCFS در سیستم عامل
- سادگی اجرا
- نوعی انصاف و عدالت در اجرا
- عدم وجود قحطی (گرسنگی)
- حداقل بودن سربار اجرایی (زیرا نیازی به اطلاعات قبلی یا اضافه در مورد فرآیندها ندارد)
معایب الگوریتم FCFS (ترتیب ورود)
- میانگین زمان انتظار برای فرآیندها بسیار بالا
- بالا بودن میانگین زمان برگشت
- برای اجرا روی یک سیستم تک پردازندهای، روش خوبی نیست.
الگوریتم SJF ؛ short job first
کوتاه ترین کار اول وارد میشه ! در این روش ابتدا کاری برای اجرا انتخاب می شود که از همه #زمان_اجرا کمتری مصرف میکند
نکته : این الگوریتم را SPN یا SPT هم میگویند .یک الگوریتم انحصاری است . یک نقص عمده این الگوریتم این است که ممکن است باعث قحطی زدگی فرایند طولانی طولانی شود . ب این ترتیب ک اگر همواره تعدادی فرایند کوچک وارد سیستم شود . اجرا فرایند های بزرگ ب طور متناوب به تعویق می افتد .این روال حتی ممکن است تا بی نهایت ادامه یابد و هیچگاه نوبت به اجرا فرایند های بزرگ نرسد .در این روش اگر ۲ فرایند مدت زمان اجرا برابری داشته باشند بر اساس FCFS زمانبندی می شوند . مثل ۴ فرایند با زمان اجرا ( CBT ) ۲ میلی ثانیه )
در محاسبه زمان اجرا ، آخری از سمت راست حساب میشه و صفر اول حساب نمیشه ( مانند زمان انتظار )
نکته : هدف الگوریتم SJF به حداقل رساندن میانگین زمان انتظار و زمان اجرا و در نتیجه میانگین زمان گردش کار ها است . در عمل نمی توان الگوریتم SJF را پیاده سازی کرد زیرا ؛ سیستم عامل زمان اجرا فرایند ها را از قبل نمی داند و تنها کاری که میتواند انجام دهد ، این است که زمان اجرا فرایند ها را فقط حدس زده و به طور تقریبی بدست آورد .
مزایای الگوریتم SJF
اگر کارها به طور همزمان وارد سیستم شوند، میانگین زمان برگشت و زمان انتظار، حداقل خواهد بود.
معایب الگوریتم SJF در سیستم عامل
یکی از بزرگترین مشکلات الگوریتم SJF نیاز به دانستن زمان پردازش هر فرآیند است. در حالت عادی و پیش از اجرای کامل یک فرآیند، زمان دقیق آن را نمیدانیم. به همین دلیل باید زمان اجرای پردازش را تخمین زد.
سایر مشکلات این الگوریتم عبارتاند از:
- امکان گرسنگی فرآیندهای طولانی وجود دارد.
- این الگوریتم برای محیطهای اشتراک زمانی، چندان مناسب نیست.
الگوریتم RR ؛ round robin
این الگوریتم نوبت چرخشی یکی از پرکاربرد ترین الگوریتم در سیستم اشتراک زمانی می باشد . قحطی زدگی ندارد . نحوه عملکرد آن غیر انحصاری می باشد . همچنان این الگوریتم نسخه غیر انحصاری FCFS است . در این الگوریتم ، زمان پردازنده را به برش های زمانی کوتاهی ( Time slice ) تقسیم میکنیم . همانند آلگوریتم FCFS فرآیند ها ب سیستم تحویل داده می شوند .
و به انتها یک صف وارد می شوند . سپس پردازنده از ابتدا صف شروع کرده و ب هر فرایند حداکثر ب اندازع ۱ برش زمانی سرویس می دهد . در واقع پس از اینکه برش زمانب یک فرایند ب پایان رسید ، پردازنده ان فرایند را رها کرده به سراغ فرایند بعد موجود در صف می رود .این عمل انقدر تکرار می شود تا پردازنده به انتها صف فرآیند های اماده برسد. ب عبارتی دیگر فرآیند ها در یک صف دایره ای ، سازماندهی می شوند و پردازنده بصورت #دوار در این صف حرکت کرده و ب هر فرایند فقط یک اسلایس سرویس می دهد .
نکته ؛ ب برش زمانی, کوانتوم زمانی می گویند.
مثال ؛ ( ۳ فرایند P1 , P2 ,P3 را در نظر بگیرید .با استفاده از الگوریتم RR و با برش زمانی ۱ میلی ثانیه میانگین زمان انتظار و میانگین زمان پاسخ فرایند ها را بدست اورید . فرآیند ها در لحظه صفر و به ترتیب نام وارد شدند)
نکته: یکی از اهداف مهم الگوریتم RR رعایت عدالت و مساوات است . الگوریتم RR در سیستم های اشتراک زمانی به خوبی استفاده می شود .
مزایای الگوریتم RR
- تضمین زمان پاسخ مطلوب برای کارهای معمولی کوچک
- نداشتن قحطی و گرسنگی در سیستم
- سادگی اجرا
- عملکرد عادلانه
معایب الگوریتم rr در سیستم عامل
انتخاب برهه زمانی (مدت زمان کوانتوم) یکی از معیارهای مشخصکننده عملکرد الگوریتم rr است. اگر کوانتوم زمانی خیلی کوچک باشد، توان عملیاتی (throughput سیستم عامل) کم خواهد شد.
دو مورد از معایب دیگر الگوریتم round robin عبارتاند از:
- سربار تعداد زیاد تعویض میان اجرای فرآیندها
- میانگین زمان اجرای نسبتاً بالا در پردازشهای طولانی
الگوریتم SRT
در این الگوریتم اگر حین اجرای یک فرایند ، فرایندی وارد شود که زمان اجرای کوتاه تری داشته باشد، در این زمان ، پردازنده را در اختیار میگیرد. این الگوریتم را به نام های srpt , srtf و srtn می شناسند.
نکته : اگر لحضه ورود همه فرایند ها یکی باشد، الگوریتم srt مشابه sjf میباشد.
نکته : در این الگوریتم نیز همانند الگوریتم sjf احتمال قحطی برای کار های بزرگ وجود دارد.
- در این الگوریتم زمانهای برگشت و انتظار حداقل است.
- الگوریتم SRTF مشکلاتی نظیر پیادهسازی (نیاز به زمان اجرای کارها) و گرسنگی کارهای طولانی دارد.
الگوریتم زمانبندی HRN – HRRN
الگوریتم های sjf و srt مشکل قحطی زدگی دارند، در این الگوریتم ها به فرایند های کوچک بیش از اندازه توجه میشود. برای رفع این مشکل الگوریتم HRRN مورد استفاده قرار میگیرد، در این الگوریتم الویت برای اجرا ، فقط اندازه آنها نیست ، بلکه برای تعیین الویت بین فرایند ها ، از فرمول زیر استفاده میشود :
الویت : زمان اجرا + زمان پاسخ تقسیم بر زمان اجرا
نکته : در این فرمول از آنجا که زمان اجرا در مخرج کسر قرار دارد ، در نتیجه فرایند های کوچک تر الویت بالاتری دارند ، اما از انجا که زمان انتظار در صورت کسر قرار دارد، هرچه یک فرایند بیشتر منتظر دریافت پردازنده باشد، الویت بالاتری به دست میآورد، با این روش هم زمان اجرای یک فرایند در تعیین الویت آن تاثیر دارد و هم مدت زمانی که منتظر بماند.
نکته مهم : الگوریتم HRRN قحطی زدگی ندارد و همچنین یک الگوریتم انحصاری است ( خواست سیستم های دسته ای میباشد )
روش حل :
در لحضه 0 فقط p1 وارد میشود
بنابراین به صورت انحصاری پردازنده را در اختیار میگیرد. و زمانی که اجرای آن به پایان رسید ، برای تمام فرایند های موجود الویت مجددا محاسبه میشود و فرایندی انتخاب میشود که از همه الویت بالاتری داشته باشد.
در این الگوریتم زمانبندی پردازنده نیز مانند الگوریتم SJF کارهای کوتاهتر در شرایط مساوی (زمان انتظار یکسان)، نسبت به کارهای طولانی اولویت دارند. زیرا مخرج کسر w/s برای آنها کوچکتر است. با این رفتار، الگوریتم HRRN میانگین زمان انتظار خود را کاهش میدهد.
البته برای اینکه این مزیت به قیمت ایجاد قحطی (گرسنگی) تمام نشود، مشابه الگوریتم FCFS به کارهایی که برای اجرا بیشتر منتظر ماندهاند نیز اهمیت میدهد. در حقیقت آنهایی که صورت کسر w/s برایشان بزرگتر است اهمیت بیشتری پیدا میکنند.
الگوریتم Prority
در این روش هر یک از فرایند ها الویت مخصوص به خود را دارند ، این الویت معمولا از خارج سیستم مشخص میشود.
یعنی هر فرایند باید یک الویت داشته باشد، و در هر لحضه فرایندی اجرا میشود که بالاترین الویت را دارد.
- این الگوریتم هم انحصاری و هم غیر انحصاری میباشد.
- در این نوع الگوریتم فرایند های با الویت کمتر ، دچار قحطی زدگی میشوند.
- یک الویت میتواند هم استاتیک باشد هم داینامیک.
استاتیک : الویتی که هیچ گاه تغییر نمیکند ، به همین دلیل پیاده سازی یا implement آن آسان میباشد.
داینامیک : یعنی بر اثر تغییرات ، تغییر میکند. ( پویا )
نکته آخر :
در این نوع الگوریتم جهت مقابله با مشکل قحطی زدگی برخی از فرایند ها، میتوان از تکنیکی به نام سال خوردگی یا اصطلاحا ( Aging ) استفاده کرد ( سال خوردگی یعنی پردازش هایی که مدت زیادی در انتظار بودند، اولویتش افزایش مییابند).
الگوریتم MLQ
هم انحصاری و هن غیر انحصاری است . در این روش ک ب آن صفحات چند سطحی گویند ، فرایند ها را به چند دسته تقسیم کرده و فرایند های موجود در هر دسته را در یک صف قرار میدهیم . قحطی زدگی دارد .در این حالت هر صف اولویت خاص خود را دارد و صف ها به ترتیب اولویت چیده می شوند .هر صف در داخل خود می تواند از الگوریتم زمان بندی جداگانه استفاده کند .
مثال ؛ همه فرایند های سیستم در یکی از گونه ها زیر قرار دارند ؛
- فرایند های سیستمی
- فرایند های محاوره ای ( غیر انحصاری)
- فرایند عای دسته ای ( انحصاری)
روش حل : در این حالت سیستم عامل برای هر گروه یک صف جداگانه تشکیل می دهد . و فرایند های جدید را با توجه به نوعشان به صف مورد نظر هدایت می کند . و هر یک از صف ها اولویت خاص خود را دارد . در این مثال صف فرآیند های سیستمی از بالاترین اولویت برخوردار است .
الگوریتم MLFQ
فرایند ها بین صف ها حرکت می کند . و در واقع تغییر یافته MLQ است . قحطی زدگی ندارد .غیر انحصاری.
در الگوریتم MLQ یک فرایند پس از ورود به یک صف خاص تا پایان در همان صف می ماند . اما در روش MLFQ فرایند ها با توجه به رفتارشان بین صف ها حرکت می کنند .
به عنوان مثال ؛ فرایندی که در یک صف با اولویت بالا قرار دارد ، و زمان پردازنده را زیاد مصرف کند ، به صف پایین تر منتقل می شود و با فرایندی که در یک صف با الویت پایین بیش از حد انتظار منتظر باشد ، به صف بالا تر منتقل می شود .
مزایای الگوریتم MLFQ
- تضمین زمان پاسخ مطلوب برای کارهای کوچک
- کاهش لگاریتمی نرخ تعویض متن
- اهمیت دادن به کارهای محدود به I/O
- اهمیت دادن به کارهای کوچک، بدون نیاز به دانستن زمان سرویس فرآیند از قبل یا نیاز به تخمین آن
معایب الگوریتم MLFQ در سیستم عامل
- گرسنگی کارهای طولانی
- پیچیدگی نسبتاً بالا در پیادهسازی
- میانگین زمان پاسخ و انتظار بالا برای برخی فرآیندها
الگوریتم LPT
در این روش معمولا به صورت انحصاری است . چون به تایم بالا ها اهمیت می دهد . قحطی زدگی دارد . در این روش بر عکس روش SJF می باشد . ب این معنا که پردازنده از بین کار های موجود ، طولانی ترین کار را انتخاب میکند .
نکته ؛ در این الگوریتم مشکل قحطی زدگی برای کار های کوچیک وجود دارد .
نکته ؛ این الگوریتم میانگین زمان پاسخ و انتظار را حداکثر میکند .
الگوریتم Lottery
ایده این الگوریتم از ایده بخت ازمایی است .
در این روش لاتاری ، تعداد بلیط بین فرایند ها تقسیم شده و سپس در ابتدا هر برش زمانی یکی از بلیط ها ب طور تصادفی برنده اعلام می شود . و فرایندی که آن بلیط را در اختیار دارد ، پردازنده را برای آن برش زمانی در اختیار می گیرد .
- در این روش فرآیند های با اولویت بالاتر هستند که بلیط های بیشتری داشته باشند .
- الگوریتم لاتاری ، مشکل قحطی زدگی ندارد ( زیرا تقسیم شده و محدود نشده )
- فرایند ها می توانند بلیط های خود را با هم مبادله کنند .
- دلیل غیر انحصاری بودن الگوریتم لاتاری ، ان است که که هنگامی یک فرایند پردازنده را در اختیار دارد . پس از پایان برش زمانی پردازنده ، از وی گرفته شده و به فرایند دیگری ک بلیط را دارد ، داده می شود .
- درمورد سیستم عامل ایرانی پای ابر بیشتر بدانید !
الگوریتم graneted
زمان بندی تضمین شده . یکی از روش های متفاوت در زمانبندی گارانتی اسکژولینگ می باشد . در این روش ابتدا با کاربران درباره سهمشان از پردازنده توافق شده . سپس سهم هر یک دادع می شود . به این معنا که دقیقا بداند هر فرایند از ابتدا تاکنون چه مدت از پردازنده را استفاده کرده و همچنین چ مقدار از سهم توافق شده باقی مانده است .غیر انحصاری و قحطی زدگی ندارد .
درمورد کاهش لگ بازی بیشتر بدانید !
الگوریتم FSS
زمانبندی سهم عادلانه. یعنی فرایند متعلق به چه کسی است؟
در الگوریتم FSS قبل از زمانبندی فرایند ها باید این نکته را در نظر گرفت که هر فرایند متعلق به چه کسی است . این حالت سهم هر کاربر است .و زمانبند به گونه فرایند ها را انتخاب کند که این سهم رعایت شود . پس غیر انحصاری و قحطی ندارد .
آیا این مقاله برای شما مفید بود ؟ چنانچه سوالی دارید ، از سید علی ابراهیمی بپرسید ! درمورد توابع کاربردی اکسل بیشتر بدانید ! آیا از معایب فالوور فیک خبر دارید ؟