{"id":32730,"date":"2019-10-31T21:48:36","date_gmt":"2019-10-31T18:48:36","guid":{"rendered":"https:\/\/prohoster.info\/blog\/operating-systems-three-easy-pieces-part-5-planirovanie-multi-level-feedback-queue-perevod\/"},"modified":"2021-02-08T11:40:35","modified_gmt":"2021-02-08T09:40:35","slug":"operating-systems-three-easy-pieces-part-5-planirovanie-multi-level-feedback-queue-perevod","status":"publish","type":"post","link":"https:\/\/prohoster.info\/en\/blog\/administrirovanie\/operating-systems-three-easy-pieces-part-5-planirovanie-multi-level-feedback-queue-perevod","title":{"rendered":"Operating Systems: Three Easy Pieces. Part 5: Scheduling: Multi-Level Feedback Queue (translation)","gt_translate_keys":[{"key":"rendered","format":"text"}]},"content":{"rendered":"<h1>Introduction to Operating Systems<\/h1>\n<p>Hello, Habr! I would like to present to your attention a series of translation articles of some interesting literature in my opinion \u2014 OSTEP. This material dives deeply into the workings of Unix-like operating systems, specifically \u2014 working with processes, various schedulers, memory, and other similar components that make up a modern OS. You can view the original materials here <noindex><a rel=\"nofollow\" href=\"http:\/\/pages.cs.wisc.edu\/~remzi\/OSTEP\/\">here<\/a><\/noindex>. Please note that the translation is done non-professionally (rather freely), but I hope I preserved the overall meaning.<\/p>\n<p>Laboratory work on this subject can be found here:<\/p>\n<ul>\n<li><noindex><a rel=\"nofollow\" href=\"http:\/\/pages.cs.wisc.edu\/~remzi\/OSTEP\/Homework\/homework.html\">original<\/a><\/noindex><\/li>\n<li><noindex><a rel=\"nofollow\" href=\"https:\/\/github.com\/remzi-arpacidusseau\/ostep-code\">original<\/a><\/noindex><\/li>\n<li><noindex><a rel=\"nofollow\" href=\"https:\/\/github.com\/bykvaadm\/OS\/tree\/master\/ostep\">my personal adaptation<\/a><\/noindex><\/li>\n<\/ul>\n<p>Other parts:<\/p>\n<ul>\n<li><noindex><a rel=\"nofollow\" href=\"https:\/\/habr.com\/en\/post\/446340\/\">Part 1: Intro<\/a><\/noindex><\/li>\n<li><noindex><a rel=\"nofollow\" href=\"https:\/\/habr.com\/en\/post\/446866\/\">Part 2: Abstraction: process<\/a><\/noindex><\/li>\n<li><noindex><a rel=\"nofollow\" href=\"https:\/\/habr.com\/en\/post\/447182\/\">Part 3: Introduction to Process API<\/a><\/noindex><\/li>\n<li><noindex><a rel=\"nofollow\" href=\"https:\/\/habr.com\/en\/post\/449026\/\">Part 4: Introduction to the Scheduler<\/a><\/noindex><\/li>\n<li><noindex><a rel=\"nofollow\" href=\"https:\/\/habr.com\/en\/post\/450116\/\">Part 5: MLFQ Scheduler<\/a><\/noindex><\/li>\n<\/ul>\n<p>You can also check out my channel on <noindex><a rel=\"nofollow\" href=\"https:\/\/t.me\/bykvaadm\">Telegram<\/a><\/noindex> =)<br \/>\n<noindex><a rel=\"nofollow\" name=\"habracut\"><\/a><\/noindex><\/p>\n<h2>Scheduling: Multi-Level Feedback Queue<\/h2>\n<p>In this lecture, we will discuss the issues of developing one of the most well-known approaches to<br \/>\nscheduling, which is called <b>Multi-Level Feedback Queue<\/b> (MLFQ). The MLFQ scheduler was first described in 1962 by Fernando J. Corbat\u00f3 in a system called<br \/>\nCompatible Time-Sharing System (CTSS). This work (including later work on<br \/>\nMultics) was subsequently presented for the Turing Award. The scheduler was<br \/>\nlater improved and took on a form that can be found in<br \/>\nsome modern systems.<\/p>\n<p>The MLFQ algorithm attempts to solve two fundamental overlapping problems.<br \/>\n<b>Firstly<\/b>, it tries to optimize turnaround time, which as we discussed in the previous lecture, is optimized by running the shortest<br \/>\njobs at the front of the queue. However, the OS does not know how long each process will take, which is<br \/>\nnecessary knowledge for SJF and STCF algorithms. <b>Secondly<\/b>, MLFQ tries to<br \/>\nmake the system responsive for users (for example, those who are sitting and<br \/>\nstaring at the screen waiting for a task to complete) and thus minimize the<br \/>\nresponse time. Unfortunately, algorithms like RR reduce response time, but have a very<br \/>\npoor impact on the turnaround time metric. Hence our problem: How to design a<br \/>\nscheduler that meets our requirements while knowing nothing about the<br \/>\nnature of the process, in general? How can the scheduler learn the characteristics of the<br \/>\ntasks it is running and thus make better scheduling decisions?<\/p>\n<p><u>The essence of the problem: How to schedule tasks without perfect knowledge?<br \/>\nHow to develop a scheduler that minimizes response time<br \/>\nfor interactive tasks while also minimizing turnaround time without prior<br \/>\nknowledge of task execution time?<\/u><\/p>\n<p>Note: learning from past events<\/p>\n<p>The MLFQ queue is a great example of a system that learns from<br \/>\npast events to predict the future. Such approaches are often<br \/>\nfound in OS (and many other fields in computer science, including branches of<br \/>\npredictions in hardware and caching algorithms). Such approaches<br \/>\nwork well when tasks have behavioral phases and are thus predictable.<br \/>\nHowever, one must be cautious with such techniques, as predictions can easily<br \/>\nturn out to be incorrect and lead the system to make worse decisions than<br \/>\nit would have without any knowledge at all.<\/p>\n<h3>MLFQ: Basic Rules<\/h3>\n<p>Let's look at the basic rules of the MLFQ algorithm. While there are several<br \/>\nimplementations of this algorithm, the fundamental approaches are similar.<br \/>\nIn the implementation we will examine, MLFQ will have several<br \/>\nseparate queues, each with a different priority. At any given time,<br \/>\na task ready for execution is in one of the queues. MLFQ uses priorities<br \/>\nto determine which task to execute, meaning the task with the higher<br \/>\npriority (the task from the queue with the highest priority) will be executed first.<br \/>\nCertainly, there can be more than one task in a specific queue, so<br \/>\nthey will have the same priority. In this case, the RR mechanism will be used<br \/>\nfor scheduling execution among these tasks.<br \/>\nThus, we arrive at two fundamental rules for MLFQ:<br \/>\nRule 1: If Priority(A) &gt; Priority(B), task A will be executed (B will not)<\/p>\n<ul>\n<li> Rule 2: If Priority(A) = Priority(B), A and B are executed using RR<\/li>\n<li> Based on the aforementioned, the key elements for MLFQ scheduling<\/li>\n<\/ul>\n<p>are priorities. Instead of assigning a fixed priority to each<br \/>\ntask, MLFQ adjusts its priority based on observed behavior.<br \/>\nFor instance, if a task constantly yields CPU work waiting for keyboard input,<br \/>\nMLFQ will maintain the process's priority at a high level, because that is how<br \/>\nan interactive process should function. Conversely, if a task constantly and<br \/>\nintensively utilizes the CPU for a long period, MLFQ will lower its<br \/>\npriority. Thus, MLFQ will learn the behavior of processes during their operation<br \/>\nand use this behavior.<br \/>\nLet's illustrate how the queues might look at a certain moment<br \/>\nin time, resulting in something like this:<br \/>\nIn this scheme, processes A and B are in the highest priority queue. Process<br \/>\n<img decoding=\"async\" alt=\"Operating Systems: Three Easy Pieces. Part 5: Scheduling: Multi-Level Feedback Queue (translation)\" src=\"\/wp-content\/uploads\/2019\/04\/3598e9ca43a56049625bdcf3074de472.png\" style=\"display:block;margin: 0 auto;\"><\/p>\n<p>C is somewhere in the middle, while process D is at the end of the queue. According to the descriptions above,<br \/>\nthe MLFQ scheduler will execute tasks only from the highest priority.<br \/>\nIn the descriptions of the MLFQ algorithm, the scheduler will execute tasks only with the highest priority.<br \/>\nthe priority according to RR, while tasks C and D will not be prioritized.<br \/>\nNaturally, a static snapshot will not provide a complete picture of how MLFQ operates.<br \/>\nIt is important to understand how the picture changes over time.<\/p>\n<h4>Attempt 1: How to change priority<\/h4>\n<p>At this point, it is necessary to decide how MLFQ will adjust the priority level<br \/>\nof tasks (and thus their position in the queue) throughout their lifecycle. To<br \/>\ndo this, it is essential to keep in mind the workflow: a certain number of<br \/>\ninteractive tasks with short execution times (and thus frequent CPU releases)<br \/>\nand several long tasks that utilize the CPU for their entire working time, where<br \/>\nthe response time for such tasks is not critical. Thus, a first attempt can be made to<br \/>\nimplement the MLFQ algorithm with the following rules:<\/p>\n<ul>\n<li> Rule3: When a task enters the system, it is placed in the highest priority queue.<\/li>\n<li>priority.<\/li>\n<li>Rule4a: If a task fully uses its allocated time slice, its priority is lowered.<\/li>\n<li>Rule4b: If a task releases the CPU before its time slice expires, it<\/li>\n<li>retains its previous priority.<\/li>\n<li>Example 1: A single long-running task<\/li>\n<\/ul>\n<p><b>As seen in this example, when the task arrives, it is assigned the highest<\/b><\/p>\n<p>priority. After a time slice of 10ms, the process is deprioritized by the<br \/>\nscheduler. After the next time slice, the task is finally deprioritized to<br \/>\nthe lowest priority in the system, where it remains.<br \/>\nExample 2: A short task arrives<br \/>\n<img decoding=\"async\" alt=\"Operating Systems: Three Easy Pieces. Part 5: Scheduling: Multi-Level Feedback Queue (translation)\" src=\"\/wp-content\/uploads\/2019\/04\/9b4ee6de03aa92d7957d50b4ffa73949.png\" style=\"display:block;margin: 0 auto;\"><\/p>\n<p><b>Now let's look at an example of how MLFQ tries to get close to SJF. In this<\/b><\/p>\n<p>example, there are two tasks: A, which is a long-running task constantly<br \/>\noccupying the CPU, and B, which is a short interactive task. Let's assume that<br \/>\nA has already been running for some time by the time task B arrives.<br \/>\nThe results of this scenario are shown in the graph. Task A, like any task that<br \/>\n<img decoding=\"async\" alt=\"Operating Systems: Three Easy Pieces. Part 5: Scheduling: Multi-Level Feedback Queue (translation)\" src=\"\/wp-content\/uploads\/2019\/04\/19c299b0519585fd1076a341a71f048b.png\" style=\"display:block;margin: 0 auto;\"><\/p>\n<p>utilizes the CPU, is at the bottom. Task B will arrive at time T=100 and will be<br \/>\nplaced in the highest priority queue. Since its execution time is short, it<br \/>\nwill finish before reaching the last queue.<br \/>\nFrom this example, the main goal of the algorithm can be understood: since the algorithm does not<\/p>\n<p>know whether a task is long or short, it initially assumes that the task<br \/>\nKnowing whether a task is long or short, it first assumes that the task is short.<br \/>\nshort and gives it the highest priority. If it is indeed a short task, then<br \/>\nit will complete quickly, otherwise if it is a long task, it will proceed slowly<br \/>\nin priority downwards and will soon prove that it is indeed a long task that does not<br \/>\nrequire a response.<\/p>\n<p><b>Example 3: What about input-output?<\/b><\/p>\n<p>Now let's look at an example with input-output. As stated in rule 4b,<br \/>\nif a process releases the processor without fully utilizing its processor time,<br \/>\nit stays at its previous priority level. The intentions of this rule are quite simple<br \/>\n\u2014 if an interactive task performs many input-output operations, for example, waiting<br \/>\nfor user key presses or mouse actions, such a task will release the processor<br \/>\nearlier than the allocated window. We wouldn\u2019t want to lower such a task's priority,<br \/>\nand thus it will remain at the same level.<br \/>\n<img decoding=\"async\" alt=\"Operating Systems: Three Easy Pieces. Part 5: Scheduling: Multi-Level Feedback Queue (translation)\" src=\"\/wp-content\/uploads\/2019\/04\/480d33a670fb62a639e5938dd59e30a1.png\" style=\"display:block;margin: 0 auto;\"><\/p>\n<p>This example shows how the algorithm will work with such processes \u2014 interactive task B, which only needs the CPU for 1ms before performing<br \/>\nan input-output process and long task A, which utilizes the CPU all its time.<br \/>\nMLFQ keeps process B at the highest priority as it continuously<br \/>\nreleases the CPU. If B is an interactive task, then in this case the algorithm achieves<br \/>\nits goal of running interactive tasks quickly.<\/p>\n<p><b>Issues with the current MLFQ algorithm<\/b><\/p>\n<p>In the previous examples, we built a basic version of MLFQ. And it seems that it<br \/>\ndoes its job well and fairly, distributing processor time honestly between<br \/>\nlong tasks and allowing short tasks or tasks that intensively use<br \/>\ninput-output to execute quickly. Unfortunately, this approach has several<br \/>\nserious problems.<br \/>\n<b>Firstly<\/b>, starvation problem: if there are many interactive<br \/>\ntasks in the system, they will consume all the processor time and thus no long<br \/>\ntask will get the opportunity to execute (they starve).<\/p>\n<p><b>Secondly<\/b>, clever users could write their programs to<br \/>\nfool the scheduler. The trick lies in doing something to make<br \/>\nthe scheduler allocate more processor time to the process. The algorithm that<br \/>\ndescribed above is quite vulnerable to such attacks: before the time window almost<br \/>\nexpires, it is necessary to perform an input\/output operation (to some file, no matter which)<br \/>\nand thus free up the CPU. Such behavior will allow it to stay in the same<br \/>\nqueue and again receive a larger percentage of CPU time. If done<br \/>\ncorrectly (for example, executing 99% of the time within the window before freeing the CPU),<br \/>\nsuch a task can simply monopolize the processor.<\/p>\n<p>Finally, a program can change its behavior over time. Those tasks that<br \/>\nused the CPU may become interactive. In our example, such<br \/>\ntasks will not receive proper attention from the scheduler, as other<br \/>\n(initial) interactive tasks would.<\/p>\n<p><u>Question to the audience: what attacks on the scheduler could be carried out in the modern world?<br \/>\n<\/u><\/p>\n<h4>Attempt 2: Priority Elevation<\/h4>\n<p>Let's try to change the rules and see if we can avoid starvation issues.<br \/>\nWhat could we do to ensure that CPU-bound tasks get their time (even if not for long)?<br \/>\nAs a simple solution to the problem, one could periodically<br \/>\nraise the priority of all such tasks in the system. There are many ways<br \/>\nto achieve this; let\u2019s try to implement something simple as an example: moving<br \/>\nall tasks to the highest priority at once, hence the new rule:<br \/>\nRule5<\/p>\n<ul>\n<li><b>: After a certain period S, move all tasks in the system to the highest queue.<\/b>Our new rule solves two problems at once. Firstly, processes<\/li>\n<\/ul>\n<p>are guaranteed not to starve: tasks in the highest queue will share<br \/>\nthe CPU time according to the RR algorithm, and thus all processes will receive<br \/>\nCPU time. Secondly, if a process that previously only used the<br \/>\nCPU becomes interactive, it will remain in the queue with higher<br \/>\npriority after it has once received an elevation to the highest.<br \/>\nLet's consider an example. In this scenario, let's consider one process using<br \/>\nConsider an example. In this scenario, let's examine a single process utilizing<br \/>\n<img decoding=\"async\" alt=\"Operating Systems: Three Easy Pieces. Part 5: Scheduling: Multi-Level Feedback Queue (translation)\" src=\"\/wp-content\/uploads\/2019\/04\/3b8d879ab4479622684b126ec5af6af3.png\" style=\"display:block;margin: 0 auto;\"><\/p>\n<p>The CPU and two interactive, short processes. The left image shows the behavior without priority boosting, and thus a long task begins to starve after two interactive tasks arrive in the system. The right image shows that every 50 ms a priority boost occurs, ensuring that all processes receive CPU time and are executed periodically. Here, 50 ms is used for illustration; the actual number is somewhat larger.<br \/>\nIt is evident that adding the periodic boost time S leads to<br \/>\nthe inevitable question: what value should be set? One of the esteemed<br \/>\nsystem engineers, John Ousterhout, referred to such values in systems as voo-doo<br \/>\nconstants, as they somewhat required black magic for correct<br \/>\nconfiguration. And unfortunately, S has that scent. If set too<br \/>\nhigh, long tasks will start to starve. Conversely, if set too low,<br \/>\ninteractive tasks won't receive adequate CPU time.<\/p>\n<h4>Attempt 3: Better Accounting<\/h4>\n<p>Now we have another problem to solve: how to prevent<br \/>\nour scheduler from being deceived? The culprits are the<br \/>\nrules 4a and 4b, which allow a job to maintain priority by freeing the CPU<br \/>\nbefore its allocated time expires. How to deal with this?<br \/>\nIn this case, the solution can be considered as better accounting of CPU time at each<br \/>\nMLFQ level. Instead of forgetting the time the program used<br \/>\nthe CPU in the allocated time frame, it should be accounted for and stored. Once<br \/>\na process has used its allocated time, it should be demoted to the next<br \/>\npriority level. Now it doesn't matter how the process utilizes its time \u2014 whether<br \/>\nconstantly computing on the CPU or through multiple calls. Thus,<br \/>\nrule 4 should be rewritten as follows:<\/p>\n<ul>\n<li><b>Rule 4<\/b>: After a task has consumed its allocated time in the current queue (regardless of how many times it has freed the CPU), the priority of that task is lowered (it moves down the queue).<\/li>\n<\/ul>\n<p>Let's look at an example:<br \/>\n<img decoding=\"async\" alt=\"Operating Systems: Three Easy Pieces. Part 5: Scheduling: Multi-Level Feedback Queue (translation)\" src=\"\/wp-content\/uploads\/2019\/04\/18c53e62b9b342d14a23995bd422ef5e.png\" style=\"display:block;margin: 0 auto;\">&gt;<\/p>\n<p>The image shows what happens if you try to deceive the scheduler, as<br \/>\nif there were with the previous rules 4a, 4b, the result would be on the left. With the new<br \/>\nrule \u2014 the result is on the right. Before protection, any process could invoke I\/O until completion and<br \/>\nthus dominate the CPU, after enabling protection, regardless of I\/O behavior, it will still be moved down the queues and therefore cannot unfairly<br \/>\nseize CPU resources.<br \/>\nEnhancing MLFQ and other issues<\/p>\n<h4>With the improvements mentioned above, new problems arise: one of the main<\/h4>\n<p>questions is how to parameterize such a scheduler? That is, how many should there be<br \/>\nqueues? What should be the size of the working window of the program within the queue? How<br \/>\noften should the program's priority be raised to avoid starvation and<br \/>\nconsider changes in the program's behavior? There are no simple<br \/>\nanswers to these questions, and only experiments with loads and subsequent configuration<br \/>\nof the scheduler can lead to some satisfactory balance.<br \/>\nFor example, most implementations of MLFQ allow assigning different<\/p>\n<p>time slices to different queues. High-priority queues are usually<br \/>\nassigned short slices. These queues consist of interactive tasks,<br \/>\nswitching between which is quite sensitive and should take 10 milliseconds or less.<br \/>\nIn contrast, low-priority queues consist of long tasks that use<br \/>\nCPU. In this case, long time slices are very suitable (100 ms).<br \/>\nIn this example, there are 2 tasks that have run in the high-priority queue for 20<br \/>\n<img decoding=\"async\" alt=\"Operating Systems: Three Easy Pieces. Part 5: Scheduling: Multi-Level Feedback Queue (translation)\" src=\"\/wp-content\/uploads\/2019\/04\/4eb6c6669034adeb1615c29454fbb1dc.png\" style=\"display:block;margin: 0 auto;\"><\/p>\n<p>ms, split into windows of 10 ms each. 40 ms in the medium queue (window of 20 ms) and in the low-priority<br \/>\nqueue, the time window became 40 ms, where tasks completed their work.<br \/>\nThe implementation of MLFQ in the Solaris OS \u2014 a class of schedulers that are time-sharing.<\/p>\n<p>The scheduler provides a set of tables that precisely define how the<br \/>\nprocess priority should change over its lifetime, what the size of the<br \/>\nallocated window should be, and how often task priorities need to be raised. The system<br \/>\nadministrator can interact with this table and force the scheduler to behave<br \/>\ndifferently. By default, this table contains 60 queues with gradually increasing<br \/>\nwindow sizes from 20 ms (high priority) to several hundred ms (low priority), and<br \/>\na window size ranging from 20ms (high priority) to several hundred ms (lowest priority), and<br \/>\nalso with a boost for all tasks every second.<\/p>\n<p>Other MLFQ schedulers do not use a table or any specific<br \/>\nrules that are described in this lecture; instead, they calculate priorities using<br \/>\nmathematical formulas. For example, the scheduler in FreeBSD uses a formula to<br \/>\ncalculate the current task priority based on how much CPU the process<br \/>\nhas used. Additionally, CPU usage decays over time, and thus<br \/>\nthe priority increase occurs somewhat differently than described above. These are the<br \/>\nso-called decay algorithms. Starting from version 7.1, FreeBSD uses the ULE scheduler.<\/p>\n<p>Finally, many schedulers have other features. For instance, some<br \/>\nschedulers reserve the highest levels for operating system tasks, and thus<br \/>\nno user process can achieve the highest priority in<br \/>\nthe system. Some systems allow giving hints to help<br \/>\nthe scheduler set priorities correctly. For example, using a command <b>nice<\/b><br \/>\nyou can increase or decrease the task's priority and thus raise or<br \/>\nlower the program's chances of CPU time.<\/p>\n<h3>MLFQ: Summary<\/h3>\n<p>We have outlined an approach to scheduling called MLFQ. Its name<br \/>\nreflects its working principle\u2014it has multiple queues and uses feedback<br \/>\nto determine the task's priority.<br \/>\nThe final appearance of the rules will be as follows:<\/p>\n<ul>\n<li><b>Rule1<\/b>: If Priority(A) &gt; Priority(B), task A will be run (B will not be)<\/li>\n<li><b>Rule2<\/b>: If Priority(A) = Priority(B), A and B run using RR<\/li>\n<li><b>Rule3<\/b>: When a task enters the system, it is placed in the highest priority queue.<\/li>\n<li><b>Rule 4<\/b>: After a task has consumed its allocated time in the current queue (regardless of how many times it has freed the CPU), the priority of that task is lowered (it moves down the queue).<\/li>\n<li><b>: After a certain period S, move all tasks in the system to the highest queue.<\/b>Our new rule solves two problems at once. Firstly, processes<\/li>\n<\/ul>\n<p>MLFQ is interesting for the following reason\u2014instead of requiring knowledge about<br \/>\nthe nature of the task in advance, the algorithm learns the past behavior of the task and assigns<br \/>\npriorities accordingly. Thus, it aims to sit on two chairs at once\u2014achieve performance for small tasks (SJF, STCF) while fairly scheduling long,<br \/>\nCPU-intensive jobs. Therefore, many systems, including BSD and its derivatives,<br \/>\nSolaris, Windows, and Mac use some form of the MLFQ algorithm<br \/>\nas a fundamental basis.<\/p>\n<h4>Additional materials:<\/h4>\n<ol>\n<li><noindex><a rel=\"nofollow\" href=\"https:\/\/manpages.debian.org\/stretch\/manpages\/sched.7.en.html\">manpages.debian.org\/stretch\/manpages\/sched.7.en.html<\/a><\/noindex><\/li>\n<li><noindex><a rel=\"nofollow\" href=\"https:\/\/en.wikipedia.org\/wiki\/Scheduling_\">en.wikipedia.org\/wiki\/Scheduling_<\/a><\/noindex>(computing)<\/li>\n<li><noindex><a rel=\"nofollow\" href=\"https:\/\/pages.lip6.fr\/Julia.Lawall\/atc18-bouron.pdf\">pages.lip6.fr\/Julia.Lawall\/atc18-bouron.pdf<\/a><\/noindex><\/li>\n<li><noindex><a rel=\"nofollow\" href=\"https:\/\/www.usenix.org\/legacy\/event\/bsdcon03\/tech\/full_papers\/roberson\/roberson.pdf\">www.usenix.org\/legacy\/event\/bsdcon03\/tech\/full_papers\/roberson\/roberson.pdf<\/a><\/noindex><\/li>\n<li><noindex><a rel=\"nofollow\" href=\"https:\/\/chebykin.org\/freebsd-process-scheduling\">chebykin.org\/freebsd-process-scheduling<\/a><\/noindex><\/li>\n<\/ol>\n<p>Source: <a content=\"nofollow\" rel=\"nofollow\" href=\"https:\/\/habr.com\/ru\/post\/450116\/\">habr.com<\/a><\/p>","protected":false,"gt_translate_keys":[{"key":"rendered","format":"html"}]},"excerpt":{"rendered":"<p>\u0412\u0432\u0435\u0434\u0435\u043d\u0438\u0435 \u0432 \u043e\u043f\u0435\u0440\u0430\u0446\u0438\u043e\u043d\u043d\u044b\u0435 \u0441\u0438\u0441\u0442\u0435\u043c\u044b \u041f\u0440\u0438\u0432\u0435\u0442, \u0425\u0430\u0431\u0440! \u0425\u043e\u0447\u0443 \u043f\u0440\u0435\u0434\u0441\u0442\u0430\u0432\u0438\u0442\u044c \u0432\u0430\u0448\u0435\u043c\u0443 \u0432\u043d\u0438\u043c\u0430\u043d\u0438\u044e \u0441\u0435\u0440\u0438\u044e \u0441\u0442\u0430\u0442\u0435\u0439-\u043f\u0435\u0440\u0435\u0432\u043e\u0434\u043e\u0432 \u043e\u0434\u043d\u043e\u0439 \u0438\u043d\u0442\u0435\u0440\u0435\u0441\u043d\u043e\u0439 \u043d\u0430 \u043c\u043e\u0439 \u0432\u0437\u0433\u043b\u044f\u0434 \u043b\u0438\u0442\u0435\u0440\u0430\u0442\u0443\u0440\u044b \u2014 OSTEP. \u0412 \u044d\u0442\u043e\u043c \u043c\u0430\u0442\u0435\u0440\u0438\u0430\u043b\u0435 \u0440\u0430\u0441\u0441\u043c\u0430\u0442\u0440\u0438\u0432\u0430\u0435\u0442\u0441\u044f \u0434\u043e\u0441\u0442\u0430\u0442\u043e\u0447\u043d\u043e \u0433\u043b\u0443\u0431\u043e\u043a\u043e \u0440\u0430\u0431\u043e\u0442\u0430 unix-\u043f\u043e\u0434\u043e\u0431\u043d\u044b\u0445 \u043e\u043f\u0435\u0440\u0430\u0446\u0438\u043e\u043d\u043d\u044b\u0445 \u0441\u0438\u0441\u0442\u0435\u043c, \u0430 \u0438\u043c\u0435\u043d\u043d\u043e \u2014 \u0440\u0430\u0431\u043e\u0442\u0430 \u0441 \u043f\u0440\u043e\u0446\u0435\u0441\u0441\u0430\u043c\u0438, \u0440\u0430\u0437\u043b\u0438\u0447\u043d\u044b\u043c\u0438 \u043f\u043b\u0430\u043d\u0438\u0440\u043e\u0432\u0449\u0438\u043a\u0430\u043c\u0438, \u043f\u0430\u043c\u044f\u0442\u044c\u044e \u0438 \u043f\u0440\u043e\u0447\u0438\u0438\u043c\u0438 \u043f\u043e\u0434\u043e\u0431\u043d\u044b\u043c\u0438 \u043a\u043e\u043c\u043f\u043e\u043d\u0435\u043d\u0442\u0430\u043c\u0438, \u043a\u043e\u0442\u043e\u0440\u044b\u0435 \u0441\u043e\u0441\u0442\u0430\u0432\u043b\u044f\u044e\u0442 \u0441\u043e\u0432\u0440\u0435\u043c\u0435\u043d\u043d\u0443\u044e \u041e\u0421. \u041e\u0440\u0438\u0433\u0438\u043d\u0430\u043b \u0432\u0441\u0435\u0445 \u043c\u0430\u0442\u0435\u0440\u0438\u0430\u043b\u043e\u0432 \u0432\u044b \u043c\u043e\u0436\u0435\u0442\u0435 \u043f\u043e\u0441\u043c\u043e\u0442\u0440\u0435\u0442\u044c \u0432\u043e\u0442 \u0442\u0443\u0442. [&hellip;]<\/p>\n","protected":false,"gt_translate_keys":[{"key":"rendered","format":"html"}]},"author":1,"featured_media":24514,"comment_status":"closed","ping_status":"closed","sticky":false,"template":"","format":"standard","meta":{"footnotes":""},"categories":[688],"tags":[],"class_list":["post-32730","post","type-post","status-publish","format-standard","has-post-thumbnail","hentry","category-administrirovanie"],"aioseo_notices":[],"aioseo_head":"\n\t\t<!-- All in One SEO 5.0.1.1 - aioseo.com -->\n\t<meta name=\"description\" content=\"\u0412\u0432\u0435\u0434\u0435\u043d\u0438\u0435 \u0432 \u043e\u043f\u0435\u0440\u0430\u0446\u0438\u043e\u043d\u043d\u044b\u0435 \u0441\u0438\u0441\u0442\u0435\u043c\u044b \u041f\u0440\u0438\u0432\u0435\u0442, \u0425\u0430\u0431\u0440! \u0425\u043e\u0447\u0443 \u043f\u0440\u0435\u0434\u0441\u0442\u0430\u0432\u0438\u0442\u044c \u0432\u0430\u0448\u0435\u043c\u0443 \u0432\u043d\u0438\u043c\u0430\u043d\u0438\u044e \u0441\u0435\u0440\u0438\u044e \u0441\u0442\u0430\u0442\u0435\u0439-\u043f\u0435\u0440\u0435\u0432\u043e\u0434\u043e\u0432 \u043e\u0434\u043d\u043e\u0439 \u0438\u043d\u0442\u0435\u0440\u0435\u0441\u043d\u043e\u0439 \u043d\u0430 \u043c\u043e\u0439 \u0432\u0437\u0433\u043b\u044f\u0434 \u043b\u0438\u0442\u0435\u0440\u0430\u0442\u0443\u0440\u044b \u2014 OSTEP.\" \/>\n\t<meta name=\"robots\" content=\"max-image-preview:large\" \/>\n\t<meta name=\"author\" content=\"Yuri Gagarin\"\/>\n\t<link rel=\"canonical\" href=\"https:\/\/prohoster.info\/en\/blog\/administrirovanie\/operating-systems-three-easy-pieces-part-5-planirovanie-multi-level-feedback-queue-perevod\" \/>\n\t<meta name=\"generator\" content=\"All in One SEO (AIOSEO) 5.0.1.1\" \/>\n\t\t<meta property=\"og:locale\" content=\"en_US\" \/>\n\t\t<meta property=\"og:site_name\" content=\"ProHoster | \u041a\u0443\u043f\u0438\u0442\u044c \u043d\u0430\u0434\u0435\u0436\u043d\u044b\u0439 \u0445\u043e\u0441\u0442\u0438\u043d\u0433 \u0434\u043b\u044f \u0441\u0430\u0439\u0442\u043e\u0432 \u0441 \u0437\u0430\u0449\u0438\u0442\u043e\u0439 \u043e\u0442 DDoS, VPS VDS \u0441\u0435\u0440\u0432\u0435\u0440\u044b\" \/>\n\t\t<meta property=\"og:type\" content=\"article\" \/>\n\t\t<meta property=\"og:title\" content=\"\ud83e\udd47Operating Systems: Three Easy Pieces. Part 5: \u041f\u043b\u0430\u043d\u0438\u0440\u043e\u0432\u0430\u043d\u0438\u0435: Multi-Level Feedback Queue (\u043f\u0435\u0440\u0435\u0432\u043e\u0434) | ProHoster\" \/>\n\t\t<meta property=\"og:description\" content=\"\u0412\u0432\u0435\u0434\u0435\u043d\u0438\u0435 \u0432 \u043e\u043f\u0435\u0440\u0430\u0446\u0438\u043e\u043d\u043d\u044b\u0435 \u0441\u0438\u0441\u0442\u0435\u043c\u044b \u041f\u0440\u0438\u0432\u0435\u0442, \u0425\u0430\u0431\u0440! \u0425\u043e\u0447\u0443 \u043f\u0440\u0435\u0434\u0441\u0442\u0430\u0432\u0438\u0442\u044c \u0432\u0430\u0448\u0435\u043c\u0443 \u0432\u043d\u0438\u043c\u0430\u043d\u0438\u044e \u0441\u0435\u0440\u0438\u044e \u0441\u0442\u0430\u0442\u0435\u0439-\u043f\u0435\u0440\u0435\u0432\u043e\u0434\u043e\u0432 \u043e\u0434\u043d\u043e\u0439 \u0438\u043d\u0442\u0435\u0440\u0435\u0441\u043d\u043e\u0439 \u043d\u0430 \u043c\u043e\u0439 \u0432\u0437\u0433\u043b\u044f\u0434 \u043b\u0438\u0442\u0435\u0440\u0430\u0442\u0443\u0440\u044b \u2014 OSTEP.\" \/>\n\t\t<meta property=\"og:url\" content=\"https:\/\/prohoster.info\/en\/blog\/administrirovanie\/operating-systems-three-easy-pieces-part-5-planirovanie-multi-level-feedback-queue-perevod\" \/>\n\t\t<meta property=\"og:image\" content=\"https:\/\/prohoster.info\/wp-content\/uploads\/2021\/11\/logo-350.jpg\" \/>\n\t\t<meta property=\"og:image:secure_url\" content=\"https:\/\/prohoster.info\/wp-content\/uploads\/2021\/11\/logo-350.jpg\" \/>\n\t\t<meta property=\"og:image:width\" content=\"350\" \/>\n\t\t<meta property=\"og:image:height\" content=\"350\" \/>\n\t\t<meta property=\"article:published_time\" content=\"2019-10-31T18:48:36+00:00\" \/>\n\t\t<meta property=\"article:modified_time\" content=\"2021-02-08T09:40:35+00:00\" \/>\n\t\t<meta property=\"article:publisher\" content=\"https:\/\/www.facebook.com\/prohoster\" \/>\n\t\t<meta property=\"article:author\" content=\"https:\/\/www.facebook.com\/prohoster\" \/>\n\t\t<!-- All in One SEO -->\n\n","aioseo_head_json":{"title":"\ud83e\udd47Operating Systems: Three Easy Pieces. Part 5: Planning: Multi-Level Feedback Queue (translation) | ProHoster","description":"Introduction to Operating Systems Hello, Habr! I would like to present to you a series of translated articles based on some literature that I find interesting \u2014 OSTEP.","canonical_url":"https:\/\/prohoster.info\/en\/blog\/administrirovanie\/operating-systems-three-easy-pieces-part-5-planirovanie-multi-level-feedback-queue-perevod","robots":"max-image-preview:large","keywords":"","webmasterTools":{"miscellaneous":""},"schema":null,"og:locale":"en_US","og:site_name":"ProHoster | \u041a\u0443\u043f\u0438\u0442\u044c \u043d\u0430\u0434\u0435\u0436\u043d\u044b\u0439 \u0445\u043e\u0441\u0442\u0438\u043d\u0433 \u0434\u043b\u044f \u0441\u0430\u0439\u0442\u043e\u0432 \u0441 \u0437\u0430\u0449\u0438\u0442\u043e\u0439 \u043e\u0442 DDoS, VPS VDS \u0441\u0435\u0440\u0432\u0435\u0440\u044b","og:type":"article","og:title":"\ud83e\udd47Operating Systems: Three Easy Pieces. Part 5: \u041f\u043b\u0430\u043d\u0438\u0440\u043e\u0432\u0430\u043d\u0438\u0435: Multi-Level Feedback Queue (\u043f\u0435\u0440\u0435\u0432\u043e\u0434) | ProHoster","og:description":"\u0412\u0432\u0435\u0434\u0435\u043d\u0438\u0435 \u0432 \u043e\u043f\u0435\u0440\u0430\u0446\u0438\u043e\u043d\u043d\u044b\u0435 \u0441\u0438\u0441\u0442\u0435\u043c\u044b \u041f\u0440\u0438\u0432\u0435\u0442, \u0425\u0430\u0431\u0440! \u0425\u043e\u0447\u0443 \u043f\u0440\u0435\u0434\u0441\u0442\u0430\u0432\u0438\u0442\u044c \u0432\u0430\u0448\u0435\u043c\u0443 \u0432\u043d\u0438\u043c\u0430\u043d\u0438\u044e \u0441\u0435\u0440\u0438\u044e \u0441\u0442\u0430\u0442\u0435\u0439-\u043f\u0435\u0440\u0435\u0432\u043e\u0434\u043e\u0432 \u043e\u0434\u043d\u043e\u0439 \u0438\u043d\u0442\u0435\u0440\u0435\u0441\u043d\u043e\u0439 \u043d\u0430 \u043c\u043e\u0439 \u0432\u0437\u0433\u043b\u044f\u0434 \u043b\u0438\u0442\u0435\u0440\u0430\u0442\u0443\u0440\u044b \u2014 OSTEP.","og:url":"https:\/\/prohoster.info\/en\/blog\/administrirovanie\/operating-systems-three-easy-pieces-part-5-planirovanie-multi-level-feedback-queue-perevod","og:image":"https:\/\/prohoster.info\/wp-content\/uploads\/2021\/11\/logo-350.jpg","og:image:secure_url":"https:\/\/prohoster.info\/wp-content\/uploads\/2021\/11\/logo-350.jpg","og:image:width":350,"og:image:height":350,"article:published_time":"2019-10-31T18:48:36+00:00","article:modified_time":"2021-02-08T09:40:35+00:00","article:publisher":"https:\/\/www.facebook.com\/prohoster","article:author":"https:\/\/www.facebook.com\/prohoster"},"aioseo_meta_data":{"post_id":"32730","title":null,"description":"","keywords":"","keyphrases":null,"primary_term":null,"canonical_url":"","og_title":null,"og_description":null,"og_object_type":"default","og_image_type":"default","og_image_url":null,"og_image_width":null,"og_image_height":null,"og_image_custom_url":null,"og_image_custom_fields":null,"og_video":null,"og_custom_url":null,"og_article_section":null,"og_article_tags":null,"twitter_use_og":false,"twitter_card":"default","twitter_image_type":"default","twitter_image_url":null,"twitter_image_custom_url":null,"twitter_image_custom_fields":null,"twitter_title":null,"twitter_description":null,"schema":{"blockGraphs":[],"customGraphs":[],"default":{"data":{"Article":[],"Course":[],"Dataset":[],"FAQPage":[],"Movie":[],"Person":[],"Product":[],"ProductReview":[],"Car":[],"Recipe":[],"Service":[],"SoftwareApplication":[],"WebPage":[]},"graphName":"","isEnabled":true},"graphs":[]},"schema_type":null,"schema_type_options":null,"pillar_content":false,"robots_default":true,"robots_noindex":false,"robots_noarchive":false,"robots_nosnippet":false,"robots_nofollow":false,"robots_noimageindex":false,"robots_noodp":false,"robots_notranslate":false,"robots_max_snippet":null,"robots_max_videopreview":null,"robots_max_imagepreview":"large","priority":null,"frequency":null,"local_seo":null,"seo_analyzer_scan_date":"2026-01-21 12:18:19","breadcrumb_settings":null,"limit_modified_date":false,"reviewed_by":null,"ai":null,"created":"2021-03-01 02:53:25","updated":"2026-01-21 12:18:19","focus_keyword":null,"additional_keywords":null,"truseo_locale":null},"gt_translate_keys":[{"key":"link","format":"url"}],"_links":{"self":[{"href":"https:\/\/prohoster.info\/en\/wp-json\/wp\/v2\/posts\/32730","targetHints":{"allow":["GET"]}}],"collection":[{"href":"https:\/\/prohoster.info\/en\/wp-json\/wp\/v2\/posts"}],"about":[{"href":"https:\/\/prohoster.info\/en\/wp-json\/wp\/v2\/types\/post"}],"author":[{"embeddable":true,"href":"https:\/\/prohoster.info\/en\/wp-json\/wp\/v2\/users\/1"}],"replies":[{"embeddable":true,"href":"https:\/\/prohoster.info\/en\/wp-json\/wp\/v2\/comments?post=32730"}],"version-history":[{"count":0,"href":"https:\/\/prohoster.info\/en\/wp-json\/wp\/v2\/posts\/32730\/revisions"}],"wp:featuredmedia":[{"embeddable":true,"href":"https:\/\/prohoster.info\/en\/wp-json\/wp\/v2\/media\/24514"}],"wp:attachment":[{"href":"https:\/\/prohoster.info\/en\/wp-json\/wp\/v2\/media?parent=32730"}],"wp:term":[{"taxonomy":"category","embeddable":true,"href":"https:\/\/prohoster.info\/en\/wp-json\/wp\/v2\/categories?post=32730"},{"taxonomy":"post_tag","embeddable":true,"href":"https:\/\/prohoster.info\/en\/wp-json\/wp\/v2\/tags?post=32730"}],"curies":[{"name":"wp","href":"https:\/\/api.w.org\/{rel}","templated":true}]}}