大家好，我是极客范的本期栏目编辑小友，现在为大家讲解基于嵌入式系统对Linux实现高效和灵活的进程调度方法分析问题。
Linux是一个类似Unix的操作系统，可以自由使用和传播。它是一个基于POSIX和UNIX的多用户、多任务、多线程、多CPU的操作系统。它可以运行主要的UNIX工具软件、应用程序和网络协议。
1.前言
处理器是整个计算机系统的核心资源。在多进程操作系统中，进程的数量往往大于处理器的数量，这将导致每个进程争夺处理器。进程调度对系统功能的实现和性能的各个方面都有决定性的影响。其本质是公平、合理、高效地为每个进程分配处理器。调度是实现多任务并发执行的必要手段。不同的操作系统有不同的调度目标。在传统的类Unix分时系统中，保证多个进程公平使用系统资源，提供更好的响应时间是调度的主要目标。在强实时操作系统中，高优先级的任务总是首先获得处理器的使用权。
Linux内核稳定、功能强大、可还原、成本低廉，非常适合嵌入式应用。但是Linux内核本身没有很强的实时性，内核体积大。因此，如果要在嵌入式系统中使用Linux，它必须是实时的和嵌入式的。结合实时进程和非实时进程(普通进程)的特点，Linux集成了上述调度策略，实现了高效灵活的进程调度。
2.Linux进程调度分析。
2.1 Linux进程状态描述。
Linux进程状态描述为以下五种类型：
任务运行：可运行状态。处于这种状态的进程可以被调度执行并成为当前进程。
可中断睡眠状态。当所需资源可用时，处于这种状态的进程被唤醒，或者它们可以被信号或定时中断唤醒。
不间断睡眠状态。只有当所需资源可用时，处于这种状态的进程才会被唤醒。
任务_僵尸：僵尸状态。指示进程结束并已释放资源，但其task _ STruct尚未释放。
任务_停止：暂停状态。处于这种状态的进程只能被来自其他进程的信号唤醒。
2.2调度模式
Linux中的每个进程都被分配了一个相对独立的虚拟地址空间。虚拟内存空间分为两部分：用户空间包含进程本身的代码和数据；内核空间包含操作系统的代码和数据。
Linux采用“条件剥夺”调度模式。对于普通进程，当它们的时间片结束时，调度器选择处于TASK_RUNNING状态的下一个进程作为当前进程(自愿调度)。对于实时进程，如果它的优先级足够高，它将从当前运行的进程中抢占CPU，成为新的当前进程(强制调度)。当发生强制调度时，如果进程在用户空间运行，会直接被剥夺CPU。如果一个进程在内核空间运行，直到从其系统空间返回的前夕才被剥夺CPU，即使迫切需要放弃CPU。
3.调度策略。
3.1三种调度策略。
SCHED _ OTHER .SCHED_OTHER是一种针对普通进程的时间片轮换策略。通过这种策略，系统为处于TASK_RUNNING状态的每个进程分配一个时间片。当时间片用完时，进程调度器选择优先级相对较高的下一个进程，并授予CPU使用它的权利。
(2)先进先出.SCHED_FIFO策略适用于响应时间高、运行时间短的实时进程。通过这种策略，每个实时进程根据其进入可运行队列的顺序依次获得CPU。除了等待一个事件主动放弃CPU，或者剥夺CPU一个优先级更高的进程，这个进程始终会占用CPU。
SCHED _ RR .SCHED_RR策略适用于响应时间高、运行时间长的实时进程。采用这种策略，每个实时进程按照时间片依次使用CPU。当正在运行的进程的时间片用完时，进程调度器停止其运行，并将其放在可运行队列的末尾。
3.2工艺调度依据。
Linux只有一个可运行队列，实时进程和TASK_RUNNING状态的普通进程都加入这个可运行队列。Linux进程调度采用动态优先级和权重控制的方法，既能实现以上三种调度策略，又能保证实时进程始终先于普通进程使用CPU。以下数据在描述流程的数据结构task_struct中用作调度基础：
结构任务
……
volaTIle LOng request _ resched；长计数器；
长的不错；无符号长策略；
无符号长rt _ priority.
};
计数器的值是动态变化的。当进程运行时，它的值将在每个时钟周期后减少1。当计数器值为0时，意味着进程的时间片已经用完，进程返回到可运行队列，等待重新调度。
p>为保证实时进程优于普通进程，Linux采取加权处理法。在进程调度过程中，每次选取下一个运行进程时，调度程序首先给可运行队列中的每个进程赋予一个权 值weight。普通进程的权值就是其counter和优先级nice的综合，而实时进程的权值是它的rt_priority的值加1000，确保实时进 程的权值总能大于普通进程。调度程序检查可运行队列中所有进程的权值，选取权值最大者作为下一个运行进程，保证了实时 进程优先于普通进程获得CPU。 Linux使用内核函数goodness（）对进程进行加权处理：
StaTIc inline goodness （struct task_struct * pint this_cpu， struct mm_struct *this_mm）{
Int weight;
Weight=-1;
If （p-》policy & SCHED_YIELD）
goto out;
If （p-》policy==SCHED_OTHER）{
weight=p-》counter; If （！ weight）
Goto out;
#Ifdef CONFIG_SMP
If （p-》processor==this_cpu）
Weight+=PROC_CHANGE_PENALTY;
#Endif
If （p-》mm==this_mm||！ p-》mm）
Weight+=1;
Weight+=20-p-》nice;
Goto out;
}
Weight=1000+p-》rt_priority;
Out：
return weight;
}
从goodness（）函数可以看出，对于普通进程，其权值主要取决于剩余的时间配额和nice两个因素。nice的规定取值范围为19～-20，只有特 权用户才能把nice值设为负数，而表达式（20-p-》nice）掉转方向成为1～40。所以，综合的权值在时间片尚未用完时基本上是两者之和。 如果是内核进程，或者其用户空间与当前进程相同，则权值将额外加1作为奖励。对于实时进程，其权值为1000+p-》rt_priority，当 p-》counter达到0时该进程将移到队列的尾部，但其优先级仍不少于1000。可见当有实时进程就绪时，普通进程是没机会运行的。
由此可以看出，通过goodness（）函数，Linux从优先考虑实时进程出发，实现了多种调度策略的统一处理，其设计思想可谓非常巧妙。
3.3 进程调度
Linux的进程调度由调度程序schedule（）完成，通过对schedule（）的分析能更好理解调度的过程。schedule（）首先判断当前运行进程是否具有SCHED_RR 标志，本文取一部分加以分析：
if （prev-》policy==SCHED_RR） Goto move_rr_last;
……
Move_rr_last：
If （！ prev-》counter）{ Prev-》counter=NICE_TO_TICKS （prev-》nice）;Move_last_runqueue （prev）;
}
Goto move_rr_back;
prev-》counter代表当前进程的运行时间配额，其值逐渐减小。一旦减至0，就要从可执行队列runqueue中当前的位置移到末尾，宏操 作NICE_TO_TICKS根据系统时钟的精度将进程的优先级别换算成可以运行的时间配额，即恢复其初始的时间配额。把该进程移到末尾意味着：如果没有 权值更高的进程，但是有一个权值与这相同的进程存在，那么，那个权值相同而排列在前的进程就会被选中，从而顾全了大局。
接下来调度函数查询当前运行进程的状态是否改变：
Move_rr_back：
switch（prev-》state）{ Case TASK_INTERRUPTIBLE：
if （signal pending（prev））{ Prev-》state=TASK_RUNNING;
Break;
}
default： Del_from_runqueue （prev）;
Case TASK_RUNNING：
}
Prev-》need_resched=0;
容易理解：如果发现进程处于TASK_INTERRUPTIBLE状态且有信号等待处理，则内核将其状态设为TASK_RUNNING，让其处理完信号， 接下来仍有机会获得CPU;如果没有信号等待，则将其从可运行队列中撤下来;如果处于TASK_RUNNING状态，则继续进行。然后，将 prev-》need_resched的值恢复成0，因为所需的调度已经在运行。
Repeat schedule （）：
next=idle_task（this_cpu）; c=-1000; If （prev-》state==TASK_RUNNING）
Goto still_running;
Still_running_back：
List_for_each （tmp， &runqueue_head）{
P=list_entry （tmp， struct task_struct， run_list）;if （can_schedule（p，this_cpu））{ Int weight=goodness （p， this_cpu， prev-》active_mm）;if （weight》c）
C=weight， next=p;
}
}
调度之前，将待调度的进程默认为0号进程，权值置为-1000。0号进程比较特别，既不会睡眠，又不能被杀死。接下来内核遍历可执行队列run queue中的每个进程，为每个进程通过goodness（）函数计算出它当前所具有的权值，然后与当前的最高值c相比。如果两个进程具有相同权值的话， 那么排在前面的进程胜出。
Still_running：
C=goodness （prev， this_cpu， prev-》active_mm）;Next=prev;
Goto still_running_back;
上面的代码告诉我们，如果当前进程想要继续运行，那么在挑选进程时以当前进程此刻的权值开始。这意味着，相对于权值相同的其他进程来说，当前进程优先。
若发现当前已选进程的权值为0，则需要重新计算各个进程的时间配额，schedule（）将转入recalculate部分。限于篇幅，在此不再展开。
4.结束语
以上结合代码简要介绍了Linux中进程调度的基本思想、依据和策略，容易发现Linux高效率和较强支持并发进程等特点。近年来，嵌入式Linux的研 究正在成为一个热点，理解Linux进程调度的原理，并在此基础上改进调度算法可能存在的缺陷，可以进一步增强其对实时性的支持，使之进一步适应在嵌入式 系统领域内的应用。
责任编辑：gt
Linux是一套免费使用和自由传播的类Unix操作系统，是一个基于POSIX和UNIX的多用户、多任务、支持多线程和多CPU的操作系统。它能运行主要的UNIX工具软件、应用程序和网络协议。
1.前言
处理机（CPU）是整个计算机系统的核心资源，在多进程的操作系统中，进程数往往多于处理机数，这将导致各进程互相争夺处理机。进程调度对系统功能的实现 及各方面的性能都有着决定性的影响，其实质就是把处理机公平、合理、高效地分配给各个进程。调度是实现多任务并发执行的必要手段，不同的操作系统有着不同 的调度目标。在传统的Unix类分时系统中，保证多个进程公平地使用系统资源，提供较好的响应时间是调度的主要目标;而在强实时操作系统中，总是优先级高 的任务优先获得处理机的使用权。
Linux具有内核稳定、功能强大、可裁减、低成本等特点，非常适合嵌入式应用。但是Linux内核本身并不具备 强实时特性，且内核体积较大，因此，想要把Linux用于嵌入式系统，必须对Linux进行实时化、嵌入式化。Linux结合实时进程和非实时进程（普通 进程）自身的特点，综合了上述几种调度策略，实现了高效、灵活的进程调度。
2.Linux进程调度分析
2.1Linux进程状态的描述
Linux将进程状态描述为如下五种：
TASK_RUNNING：可运行状态。处于该状态的进程可以被调度执行而成为当前进程。
TASK_INTERRUPTIBLE：可中断的睡眠状态。处于该状态的进程在所需资源有效时被唤醒，也可以通过信号或定时中断唤醒。
TASK_UNINTERRUPTIBLE：不可中断的睡眠状态。处于该状态的进程仅当所需资源有效时被唤醒。
TASK_ZOMBIE：僵尸状态。表示进程结束且已释放资源，但其task_STruct仍未释放。
TASK_STOPPED：暂停状态。处于该状态的进程通过其他进程的信号才能被唤醒。
2.2调度方式
Linux中的每个进程都分配有一个相对独立的虚拟地址空间。该虚存空间分为两部分：用户空间包含了进程本身的代码和数据;内核空间包含了操作系统的代码和数据。
Linux采用“有条件的可剥夺”调度方式。对于普通进程，当其时间片结束时，调度程序挑选出下一个处于TASK_RUNNING状态的进程作为当前进程 （自愿调度）。对于实时进程，若其优先级足够高，则会从当前的运行进程中抢占CPU成为新的当前进程（强制调度）。发生强制调度时，若进程在用户空间中运 行，就会直接被剥夺CPU;若进程在内核空间中运行，即使迫切需要其放弃CPU，也仍要等到从它系统空间返回的前夕才被剥夺CPU。
3.调度策略
3.1三种调度策略
（1）SCHED_OTHER。SCHED_OTHER是面向普通进程的时间片轮转策略。采用该策略时，系统为处于TASK_RUNNING状态的每个进程分配一个时间片。当时间片用完时，进程调度程序再选择下一个优先级相对较高的进程，并授予CPU使用权。
（2）SCHED_FIFO。SCHED_FIFO策略适用于对响应时间要求比较高，运行所需时间比较短的实时进程。采用该策略时，各实时进程按其进入可 运行队列的顺序依次获得CPU。除了因等待某个事件主动放弃CPU，或者出现优先级更高的进程而剥夺其CPU之外，该进程将一直占用CPU运行。
（3）SCHED_RR。SCHED_RR策略适用于对响应时间要求比较高，运行所需时间比较长的实时进程。采用该策略时，各实时进程按时间片轮流使用CPU。当一个运行进程的时间片用完后，进程调度程序停止其运行并将其置于可运行队列的末尾。
3.2 进程调度依据
Linux只有一个可运行队列，处于TASK_RUNNING状态的实时进程和普通进程都加入到这个可运行队列中。Linux的进程调度采用了动态优先级 和权值调控的方法，既可实现上述三种调度策略，又能保证实时进程总是比普通进程优先使用CPU。描述进程的数据结构task_struct中用以下几个数 据作为调度依据：
Struct task_struct {
……
volaTIle lONg need_resched; long counter;
long nice; unsigned long policy;
unsigned long rt_priority; ……
};
counter的值是动态变化的，进程运行时，每一个时钟滴答后，其值减1。当counter值为0时，表示该进程时间片已用完，该进程回到可运行队列中，等待再次调度。
为保证实时进程优于普通进程，Linux采取加权处理法。在进程调度过程中，每次选取下一个运行进程时，调度程序首先给可运行队列中的每个进程赋予一个权 值weight。普通进程的权值就是其counter和优先级nice的综合，而实时进程的权值是它的rt_priority的值加1000，确保实时进 程的权值总能大于普通进程。调度程序检查可运行队列中所有进程的权值，选取权值最大者作为下一个运行进程，保证了实时 进程优先于普通进程获得CPU。 Linux使用内核函数goodness（）对进程进行加权处理：
StaTIc inline goodness （struct task_struct * pint this_cpu， struct mm_struct *this_mm）{
Int weight;
Weight=-1;
If （p-》policy & SCHED_YIELD）
goto out;
If （p-》policy==SCHED_OTHER）{
weight=p-》counter; If （！ weight）
Goto out;
#Ifdef CONFIG_SMP
If （p-》processor==this_cpu）
Weight+=PROC_CHANGE_PENALTY;
#Endif
If （p-》mm==this_mm||！ p-》mm）
Weight+=1;
Weight+=20-p-》nice;
Goto out;
}
Weight=1000+p-》rt_priority;
Out：
return weight;
}
从goodness（）函数可以看出，对于普通进程，其权值主要取决于剩余的时间配额和nice两个因素。nice的规定取值范围为19～-20，只有特 权用户才能把nice值设为负数，而表达式（20-p-》nice）掉转方向成为1～40。所以，综合的权值在时间片尚未用完时基本上是两者之和。 如果是内核进程，或者其用户空间与当前进程相同，则权值将额外加1作为奖励。对于实时进程，其权值为1000+p-》rt_priority，当 p-》counter达到0时该进程将移到队列的尾部，但其优先级仍不少于1000。可见当有实时进程就绪时，普通进程是没机会运行的。
由此可以看出，通过goodness（）函数，Linux从优先考虑实时进程出发，实现了多种调度策略的统一处理，其设计思想可谓非常巧妙。
3.3 进程调度
Linux的进程调度由调度程序schedule（）完成，通过对schedule（）的分析能更好理解调度的过程。schedule（）首先判断当前运行进程是否具有SCHED_RR 标志，本文取一部分加以分析：
if （prev-》policy==SCHED_RR） Goto move_rr_last;
……
Move_rr_last：
If （！ prev-》counter）{ Prev-》counter=NICE_TO_TICKS （prev-》nice）;Move_last_runqueue （prev）;
}
Goto move_rr_back;
prev-》counter代表当前进程的运行时间配额，其值逐渐减小。一旦减至0，就要从可执行队列runqueue中当前的位置移到末尾，宏操 作NICE_TO_TICKS根据系统时钟的精度将进程的优先级别换算成可以运行的时间配额，即恢复其初始的时间配额。把该进程移到末尾意味着：如果没有 权值更高的进程，但是有一个权值与这相同的进程存在，那么，那个权值相同而排列在前的进程就会被选中，从而顾全了大局。
接下来调度函数查询当前运行进程的状态是否改变：
Move_rr_back：
switch（prev-》state）{ Case TASK_INTERRUPTIBLE：
if （signal pending（prev））{ Prev-》state=TASK_RUNNING;
Break;
}
default： Del_from_runqueue （prev）;
Case TASK_RUNNING：
}
Prev-》need_resched=0;
容易理解：如果发现进程处于TASK_INTERRUPTIBLE状态且有信号等待处理，则内核将其状态设为TASK_RUNNING，让其处理完信号， 接下来仍有机会获得CPU;如果没有信号等待，则将其从可运行队列中撤下来;如果处于TASK_RUNNING状态，则继续进行。然后，将 prev-》need_resched的值恢复成0，因为所需的调度已经在运行。
Repeat schedule （）：
next=idle_task（this_cpu）; c=-1000; If （prev-》state==TASK_RUNNING）
Goto still_running;
Still_running_back：
List_for_each （tmp， &runqueue_head）{
P=list_entry （tmp， struct task_struct， run_list）;if （can_schedule（p，this_cpu））{ Int weight=goodness （p， this_cpu， prev-》active_mm）;if （weight》c）
C=weight， next=p;
}
}
调度之前，将待调度的进程默认为0号进程，权值置为-1000。0号进程比较特别，既不会睡眠，又不能被杀死。接下来内核遍历可执行队列run queue中的每个进程，为每个进程通过goodness（）函数计算出它当前所具有的权值，然后与当前的最高值c相比。如果两个进程具有相同权值的话， 那么排在前面的进程胜出。
Still_running：
C=goodness （prev， this_cpu， prev-》active_mm）;Next=prev;
Goto still_running_back;
上面的代码告诉我们，如果当前进程想要继续运行，那么在挑选进程时以当前进程此刻的权值开始。这意味着，相对于权值相同的其他进程来说，当前进程优先。
若发现当前已选进程的权值为0，则需要重新计算各个进程的时间配额，schedule（）将转入recalculate部分。限于篇幅，在此不再展开。
4.结束语
以上结合代码简要介绍了Linux中进程调度的基本思想、依据和策略，容易发现Linux高效率和较强支持并发进程等特点。近年来，嵌入式Linux的研 究正在成为一个热点，理解Linux进程调度的原理，并在此基础上改进调度算法可能存在的缺陷，可以进一步增强其对实时性的支持，使之进一步适应在嵌入式 系统领域内的应用。
责任编辑：gt
.dfma { position: relative; width: 1000px; margin: 0 auto; } .dfma a::after { position: absolute; left: 0; bottom: 0; width: 30px; line-height: 1.4; text-align: center; background-color: rgba(0, 0, 0, .5); color: #fff; font-size: 12px; content:"广告"; } .dfma img { display: block; }