الگوریتم های زمان بندی در سیستم عامل — ۱۰ الگوریتم زمان بندی پردازنده

مقدمه

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

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

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

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

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

جهت آشنایی شما با واحد پردازش مرکزی کامپیوتر و داشتن ارائه‌ای جذاب و مخاطب پسند در این زمینه می‌توانید از فایل پاورپوینت آماده شده در لینک زیر بهره مند شوید.

• پاورپوینت سی پی یو CPU — ساختار و کارکرد آن — کلیک کنید.

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

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

1. الگوریتم‌های انحصاری
2. الگوریتم‌های غیر انحصاری

الگوریتم‌های انحصاری (Non Preemptive)

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

الگوریتم‌های غیر انحصاری (Preemptive)

در این الگوریتم‌ها یک فرآیند که در حال اجراست ممکن است توسط سیستم عامل متوقف‌شده و به حالت آماده منتقل شود. این کار برای اختصاص پردازنده به یک فرآیند دیگر و یا انجام عملیات I/O و وقفه انجام می‌شود. به‌عبارت‌دیگر در این نوع از الگوریتم‌ها، فرآیندها ممکن است به چند بخش تقسیم‌شده و در چند مرحله عملیات تخصیص پردازنده انجام‌گرفته و اجرا شود. الگوریتم‌های RR, SRTF, MLFQ از این نوع هستند.

الگوریتم های زمان بندی مختلف

در ادامه آموزش الگوریتم های زمان بندی در سیستم عامل فهرستی از الگوریتم های زمان بندی سیستم عامل وجود دارد که در مورد آنها صحبت خواهیم کرد:

۱. الگوریتم First-Come, First-Served (FCFS)

این الگوریتم ساده‌ترین و آسان‌ترین نوع  الگوریتم های زمان بندی در سیستم عامل است. در این الگوریتم، فرآیندی که ابتدا CPU را درخواست می‌کند،متقابلاً زودتر CPU را برای اجرا در اختیار می‌گیرد. این الگوریتم را می‌توان آن را با استفاده از روش FIFO (First-In, First-Out) Queue پیاده‌سازی کرد. ویژگی‌های این الگوریتم عبارتند از:

۱. اجرای آن آسان است.
2. CPU همیشه بر اساس First-come و First-serve تخصیص داده می‌شود.
3. اما، این الگوریتم عملکرد ضعیفی دارد زیرا میانگین زمان انتظار آن بسیار بالاست.

و کد نویسی آن در زبان #C به‌صورت زیر است:

class MainClass
    {
        public static void Main (string[] args)
        {
            int[] processes = { 1, 2, 3 };
            int n = processes.Length;
            int[] burst_time = { 5, 9, 6 };
            int[] arrival_time = { 0, 3, 6 };
            int[] wt = new int[n];
            int[] tat = new int[n];
            findWaitingTime(processes, n, burst_time, wt, arrival_time);
            findTurnAroundTime(processes, n, burst_time, wt, tat);
            Display(n, burst_time, arrival_time, wt, tat);
            findavgTime(n, wt, tat);
            Console.WriteLine ("Press any key to Finish ...");
            Console.ReadKey ();
        }
        static void findWaitingTime(int[] processes, int n, int[] bt, int[] wt
            , int[] at) {
            int[] service_time = new int[n];
            service_time[0] = 0;
            wt[0] = 0;
            for (int i = 1; i < n; i++) {
                service_time[i] = service_time[i - 1] + bt[i - 1];
                wt[i] = service_time[i] - at[i];
                if (wt[i] < 0)
                    wt[i] = 0;
            }
        }
        static void findTurnAroundTime
(int[] processes, int n, int[] bt,
            int[] wt, int[] tat) {
            for (int i = 0; i < n; i++)
                tat[i] = bt[i] + wt[i];
        }
        static void findavgTime(int n, int[] wt, int[] tat) {
            int total_wt = 0, total_tat = 0;
            for (int i = 0; i < n; i++) {
                total_wt = total_wt + wt[i];
                total_tat = total_tat + tat[i];
            }
            Console.Write("Average waiting time =
 " + (float) total_wt / (float) n);
            Console.WriteLine("\nAverage turn around time =
 " + (float) total_tat / (float) n);
        }
        public static void
Display(int n, int[] burst_time, int[] arrival_time,
            int[] wt, int[] tat) {
            Console.Write
("Processes " + " Burst Time " + " Arrival Time " +
                " Waiting Time " + " Turn-Around Time "
                + " Completion Time \n");
            for (int i = 0; i < n; i++) {
                int compl_time = tat[i] + arrival_time[i];
                Console.WriteLine
(i + 1 + "\t\t" + burst_time[i] + "\t\t" + arrival_time[i]
                    + "\t\t" + wt[i] + "\t\t "
                    + tat[i] + "\t\t " + compl_time);
            }
        }
             
    }

۲. الگوریتم Shortest-Job-Next (SJN)

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

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

۳. الگوریتم Priority Scheduling

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

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

۴. الگوریتم Shortest Remaining Time

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

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

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

۵. الگوریتم Round Robin(RR)

زمان‌بند یک واحد زمان ثابت را به هر فرآیند اختصاص می‌دهد و آن‌ها را طی می‌کند. اگر فرآیند در آن بازه زمانی کامل شود، خاتمه می‌یابد، در غیر این صورت، پس از دادن فرصت به سایر فرآیندها، مجدداً زمان‌بندی می‌شود. برنامه‌ریزی RR شامل سربار گسترده‌ای است، به‌خصوص اگر یک واحد زمانی کوچک در نظر گرفته شود. به دلیل زمان انتظار بالا، ضرب‌الاجل‌ها به‌ندرت در یک سیستم RR خالص رعایت می‌شود.
گرسنگی هرگز نمی‌تواند رخ دهد، زیرا هیچ اولویتی داده نمی‌شود. ترتیب تخصیص واحد زمان‌بر اساس زمان رسیدن فرآیند، مشابه FIFO است. اگر Time-Slice بزرگ باشد به FCFS /FIFO یا اگر کوتاه باشد تبدیل به SJF/SRTF می‌شود. جهت آشنایی بیشتر با این الگوریتم زمانبندی پیشنهاد می‌کنیم مقاله موجود در لینک زیر مطالعه کنید.

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

۶. الگوریتم Multiple-Level Queues (MLQ)

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

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

هر سه نوع مختلف فرآیند دارای صف خاص خود هستند. هر صف الگوریتم زمان‌بندی خاص خود را دارد. به‌عنوان‌مثال، صف ۱ و صف ۲ از Round Robin استفاده می‌کنند درحالی‌که صف ۳ می‌تواند از FCFS برای برنامه‌ریزی فرآیندهای خود استفاده کند.

۷. الگوریتم Multi level Feedback Queues (MLFQ)

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

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

۸. الگوریتم Highest Response Ratio Next (HRRN)

الگوریتم زمان‌بندی HRRN وظیفه یافتن میانگین زمان انتظار و میانگین زمان چرخش با توجه به n فرآیند بازمان رسیدن و زمان انفجار را دارد. ما باید نسبت پاسخ تمام فرآیندهای موجود را پیداکرده و آن را که بالاترین نسبت پاسخ را دارد انتخاب کنیم. یک فرآیند پس از مرحله انتخاب، تا تکمیل فرآیند اجرا خواهد شد. در t = 0 ما فقط یک فرآیند در دسترس داریم، بنابراین A زمان‌بندی می‌شود. به طور مشابه در t = 3 ما فقط یک فرآیند در دسترس داریم، بنابراین B زمانبندی می‌شود.

اکنون در t = 9 ما ۳ فرآیند C، D و E در دسترس داریم. زیرا C، D و E به ترتیب پس از ۴، ۶ و ۸ واحد در دسترس بودند. بنابراین، زمان انتظار برای C، D و E به ترتیب ۵ = (۴ – ۹)،  ۳ = (۶ – ۹) ۳، و ۱ = (۸ – ۹) واحد است.

با استفاده از فرمول داده‌شده در زیر، نسبت‌های پاسخ C، D و E را به ترتیب ۲.۲۵، ۱.۶ و ۱.۵ محاسبه می‌کنیم. واضح است که C بالاترین نسبت پاسخ را  دارد و بنابراین زمان‌بندی می‌شود. بعد در t = 13 ما ۲ فرآیند در دسترس D و E داریم. نسبت پاسخ D و E به ترتیب ۲.۴ و ۳.۵ است. بنابراین فرآیند E در مرحله بعدی و فرآیند D در آخر انتخاب می‌شود.

۹. الگوریتم (Fixed priority pre-emptive (FPPS

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

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

سخن پایانی در مورد الگوریتم های زمان بندی در سیستم عامل

برای یک سیستم عامل مهم‌ترین و اساسی‌ترین وظیفه، برنامه‌ریزی و زمان‌بندی است. برای اینکه CPU بیکار نماند سیستم عامل باید رویه‌ای را با استفاده از الگوریتم های زمان بندی در پیش بگیرد. برای آشنایی با این الگوریتم‌ها آموزش الگوریتم های زمان بندی در سیستم عامل ارائه شد. بررسی الگوریتم های زمان بندی و بهینه‌سازی این الگوریتم‌ها باعث تسریع در پردازش فرآیندها می‌گردد.

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

مدیریت تخصیص حافظه در سیستم عامل — آموزش ۶ الگوریتم تخصیص حافظه همراه با مثال

مدیریت تخصیص حافظه در سیستم عامل — آموزش ۶ الگوریتم تخصیص حافظه همراه با مثال

کلیک کنید