📄 scheduler.html
字号:
<!DOCTYPE html PUBLIC "-//W3C//DTD XHTML 1.0 Transitional//EN" "http://www.w3.org/TR/xhtml1/DTD/xhtml1-transitional.dtd"><html><head> <title></title> <link rel="stylesheet" media="screen" type="text/css" href="./style.css" /> <link rel="stylesheet" media="screen" type="text/css" href="./design.css" /> <link rel="stylesheet" media="print" type="text/css" href="./print.css" /> <meta http-equiv="Content-Type" content="text/html; charset=utf-8" /></head><body><a href=start.html>start</a></br><div class="toc"><div class="tocheader toctoggle" id="toc__header">Table of Contents</div><div id="toc__inside"><ul class="toc"><li class="clear"><ul class="toc"><li class="level2"><div class="li"><span class="li"><a href="#the_2.6_kernel_scheduler" class="toc">The 2.6 Kernel Scheduler</a></span></div><ul class="toc"><li class="level3"><div class="li"><span class="li"><a href="#scheduler_basics" class="toc">Scheduler Basics</a></span></div></li><li class="level3"><div class="li"><span class="li"><a href="#time_slices" class="toc">Time Slices</a></span></div></li><li class="level3"><div class="li"><span class="li"><a href="#goodness_and_static_priority" class="toc">Goodness and Static Priority</a></span></div></li><li class="level3"><div class="li"><span class="li"><a href="#real_time_tasks" class="toc">Real Time Tasks</a></span></div></li><li class="level3"><div class="li"><span class="li"><a href="#kernel_preemption" class="toc">Kernel Preemption</a></span></div></li><li class="level3"><div class="li"><span class="li"><a href="#the_o1_scheduler" class="toc">The O1 scheduler</a></span></div></li></ul></li></ul></li></ul></div></div><h2><a name="the_2.6_kernel_scheduler" id="the_2.6_kernel_scheduler">The 2.6 Kernel Scheduler</a></h2><div class="level2"><p>The 2.6 Kernel introduces some new ( to Linux ) scheduling concepts. In a quest to improve system performance and responsiveness several kernel systems have been reworked and improved.</p></div><!-- SECTION [1-226] --><h3><a name="scheduler_basics" id="scheduler_basics">Scheduler Basics</a></h3><div class="level3"><p> The system tasks are organized into a number of queues. The queues are ordered by priority and <strong>goodness</strong>. Each queue is assigned to a single bit in a 32 bit word. The first bit set in the word represents the first queue to run. The first task on the selected queue is the next to run in that queue.</p><p>Since there are more than 32 possible queues a high order word is assigned to monitor 32 low order words. A bit set in the high order word means that one or more queues in the low order word have tasks ready to run.</p><p>The task selection process then boils down to two bit searches.</p><pre class="code c"> high order work - index of low order words low order word - index of task queues by priority * find the first not zero bit in the high order word this gives the index of the low order word assigned to the queues index <span class="nu0">0</span> <span class="kw1">for</span> queues <span class="nu0">0</span> to <span class="nu0">31</span> index <span class="nu0">1</span> <span class="kw1">for</span> queues <span class="nu0">32</span> to <span class="nu0">63</span> etc * find the first non zero bit in the low order word. <span class="me1">gives</span> the index of the run queue with the next active task. * run the first task in the selected queue<span class="st0">'s active list. </span></pre></div><!-- SECTION [227-1346] --><h3><a name="time_slices" id="time_slices">Time Slices</a></h3><div class="level3"><p> A task is given a time slice. Once the time slice is used up the task will not be rescheduled until all other tasks in the run list have used their timeslice.</p><p>Each run queue has an <strong>active</strong> list and an <strong>expired</strong> list. When a task has used up its CPU time slice it is moved from the active to the expired list.</p><p>When there are no more active tasks the active and expired lists are swapped.</p><pre class="code c"> Min Timeslice the larger of <span class="nu0">1</span> jiffie or <span class="nu0">5</span> mSecs Max Timeslice <span class="nu0">800</span> mSecs <span class="kw1">Default</span> Timeslice <span class="nu0">100</span> mSecs </pre></div><!-- SECTION [1347-1931] --><h3><a name="goodness_and_static_priority" id="goodness_and_static_priority">Goodness and Static Priority</a></h3><div class="level3"><p> Linux has a concept of <strong>goodness</strong> associated with tasks at user priority 0.</p><p>If a task does not use up its timeslice it must have decided to sleep waiting to be woken up by I/O activity or another task. The goodness value will provide preference to tasks that seem to execute quickly. This is done by defining a <strong>static priority</strong> and an adjustment range for that priority. The static priority is in the range of 0..39 with an adjustment of -5 to +5. (NOTE the adjustment does not go beyond the 0..39 limits).</p></div><!-- SECTION [1932-2500] --><h3><a name="real_time_tasks" id="real_time_tasks">Real Time Tasks</a></h3><div class="level3"><p> Privileged users can assign a task a <strong>real time</strong> priority greater than 0.</p><p>These tasks are not <strong>tuned</strong> by the system, their relative priorities are not changed by the scheduler.</p><p>The number of Real Time priorities is set at compile time. The default range is 1..99. In addition the kernel has a small number of even higher priority task options for its own use.</p><p> Real time tasks can also be defined as <strong>round robin</strong> or <strong>FIFO</strong>. A round robin task will be assigned a timeslice. When it has used the timeslice up it will be rescheduled to allow other tasks to execute at the same (or higher) priority.</p><p> A FIFO task will execute until its completion unless preempted by a higher priority task.</p></div><!-- SECTION [2501-3230] --><h3><a name="kernel_preemption" id="kernel_preemption">Kernel Preemption</a></h3><div class="level3"><p> In the old days When a Unix task was interrupted while executing in kernel mode the system would restore that task’s execution until the task attempted to return to user space. At that time the scheduler would be revisited to possibly schedule another task.</p><p>This meant that once you got into kernel space. as a result of a system call,the CPU was yours until your system call was finished.</p><p>The preemptible kernel patch broke this behavior and allowed the kernel to reschedule the system at any return from exception. This behavior can be disabled when needed but the concept remains that preemption is on by default at all times.</p><p>Preemption means that device drivers that presumed atomic behavior could possibly be broken. On Multi Processor systems you could even switch the CPU you are running on due to a preemption event. In most cases this is not a problem. If in doubt, temporarily disable preemption in critical code areas.</p></div><!-- SECTION [3231-4197] --><h3><a name="the_o1_scheduler" id="the_o1_scheduler">The O1 scheduler</a></h3><div class="level3"><p> Originally coded by Ingo Molnar in 2002 the O1 Scheduler adds a layer of common sense to the kernel scheduling policy.</p><p>One of the keys to the new scheduler is the use of many queues to manage task scheduling one que is provided for each priority level including the dynamic priorities defined for the non real time priority 0.</p><p> The priority array structure is shown here.</p><pre class="code c"> <span class="co2">#define BITMAP_SIZE ((((MAX_PRIO+1+7)/8)+sizeof(long)-1)/sizeof(long))</span> <span class="kw4">struct</span> prio_array <span class="br0">{</span> <span class="kw4">unsigned</span> <span class="kw4">int</span> nr_active; <span class="kw4">unsigned</span> <span class="kw4">long</span> bitmap<span class="br0">[</span>BITMAP_SIZE<span class="br0">]</span>; <span class="kw4">struct</span> list_head queue<span class="br0">[</span>MAX_PRIO<span class="br0">]</span>;<span class="br0">}</span>; <span class="co1">// Part of the runqueue</span><span class="kw4">struct</span> runqueue <span class="br0">{</span> task_t *curr, *idle; prio_array_t *active, *expired, arrays<span class="br0">[</span><span class="nu0">2</span><span class="br0">]</span>;<span class="br0">}</span>; <span class="co1">// one runqueue per CPU</span><span class="kw4">static</span> DEFINE_PER_CPU<span class="br0">(</span><span class="kw4">struct</span> runqueue, runqueues<span class="br0">)</span>;<span class="co1">// schedule fcn selects the high order bits and thus the index of the</span><span class="co1">//next active run queue</span> idx = sched_find_first_bit<span class="br0">(</span>array->bitmap<span class="br0">)</span>; queue = array->queue + idx; next = list_entry<span class="br0">(</span>queue->next, task_t, run_list<span class="br0">)</span>; </pre><p>The dequeue and enqueue functions are used to remove and add tasks to a given priority array.</p><pre class="code c"><span class="coMULTI">/* * Adding/removing a task to/from a priority array: */</span><span class="kw4">static</span> <span class="kw4">void</span> dequeue_task<span class="br0">(</span><span class="kw4">struct</span> task_struct *p, prio_array_t *array<span class="br0">)</span><span class="br0">{</span> array->nr_active--; list_del<span class="br0">(</span>&p->run_list<span class="br0">)</span>; <span class="kw1">if</span> <span class="br0">(</span>list_empty<span class="br0">(</span>array->queue + p->prio<span class="br0">)</span><span class="br0">)</span> __clear_bit<span class="br0">(</span>p->prio, array->bitmap<span class="br0">)</span>; <span class="br0">}</span><span class="kw4">static</span> <span class="kw4">void</span> enqueue_task<span class="br0">(</span><span class="kw4">struct</span> task_struct *p, prio_array_t *array<span class="br0">)</span><span class="br0">{</span> list_add_tail<span class="br0">(</span>&p->run_list, array->queue + p->prio<span class="br0">)</span>; __set_bit<span class="br0">(</span>p->prio, array->bitmap<span class="br0">)</span>; array->nr_active++; p->array = array; <span class="br0">}</span></pre></div><!-- SECTION [4198-] --></body></html>⌨️ 快捷键说明
复制代码
Ctrl + C
搜索代码
Ctrl + F
全屏模式
F11
切换主题
Ctrl + Shift + D
显示快捷键
?
增大字号
Ctrl + =
减小字号
Ctrl + -