＜Linux＞（极简关键、省时省力）《Linux操作系统原理分析之Linux 进程管理 3》（7）

4 Linux 进程管理

4.3 Linux 的进程调度

4.3.1 Linux 进程调度策略

Linux 在进程调度中采用的是可抢占的调度方式。

Linux 中的进程分为普通进程和实时进程。实时进程的优先级高于普通进程。对实时进程和普通进程采用不同的调度策略。

Linux 为每个进程都规定了一种调度策略，并记录在其任务结构体 policy 成员项中。Linux 调度策略有3 种，它们以符合常量的形式定义

在/include/linux/sched.h 中，其定义及意义如下所示：
#define SCHED_OTHER 0 普通进程的时间片轮转算法（根据优先权选择下一个进程）
#define SCHED_FIFO 1 实时进程的先进先出算法（适用于响应时间要求比较严格的短小进程）
#define SCHED_RR 2 实时进程的时间片轮转算法（适用于响应时间要求比较严格的较大进程）
1
2
3
4

因此在 linux 的可运行队列中，从调度策略来分 SCHED_FIFO 的实时进程具有最高优先级，其次是SCHED_RR 的实时进程，而 SCHED_OTHER 的普通进程优先级最低。

4.3.2 Linux 进程调度依据

Linux 的进程调度采用了优先级和权值的方法。Linux 用以下四个数据作为调度依据，它们记录在进程的任务结构体中：

👉Policy 是进程的调度策略
👉Priority 是普通进程的优先级。它是[0~70]之间的数，数值越大优先级越高。Priority 除表示进程的优先级，还表示分配给进程使用 CPU 的时间片。
👉Rt_Priority 是实时进程的优先级。策略为 SCHED_FIFO 的实时进程的 rt_Priority 大于 SCHED_ RR 实时进程
👉Counter 中存放的是进程还需要使用 CPU 运行时间的计数值，它是动态变化的，它的初始值就是Priority。

4.3.3Linux 进程调度的加权处理

加权处理的方法：在进程调度过程中，每次选取下一个运行进程时，调度程序首先给可运行队列的每个进
程赋予一个权值（weight）。普通进程的权值就是它的 counter 值，而实时进程的权值是它的 rt_Priority 值
加 1000。Linux 使用内核函数 goodness（）对进程进行加权处理，它的源程序在/kernel/sched.c 中，下面给出了
去掉其中多处理机（SMP）部分后简化的程序代码。

Static inline goodness(struct task_struct *p, struct task_struct *prev, int this_cpu)
{
Int weight;
If(p->policy!=SCHED_OTHER) /*若当前进程是实时进程*/
Return 1000+p->rt_Priority; /*返回权值为 rt_Priority +1000*/
Weight=p->counter; /*若当前进程是普通进程*/
………
………
Return weight; /*返回权值为 counter */
}
1
2
3
4
5
6
7
8
9
10

4.3.4 Linux 进程调度方法

实时进程的优先级大于普通进程的优先级，故只有当可运行队列的所有实时进程都运行完成后，普通进程才能得到运行。
linux 普通进程的优先级由 Priority 和 counter 共同决定。在进程运行过程中 Priority 保持不变，体现了进程的静态优先级概念；而 counter 不断减少，表示了进程的动态优先级。采用动态优先级的方法，使得一个进程占用 CPU 的时间越长，counter 的值越小。这样使得每个进程都可以公平地分配到 CPU。

4.3.5 Linux 进程调度时机

Linux 进程调度是由 Schedule（）完成的。该函数定义在/kernel/sched.c 中。执行该函数 的情况可以分
为两种：

在某些系统调用函数中直接调用 Schedule（）。
在系统运行过程中，通过检查调度标志而执行该函数。进程调度标志是一个名为 need_resched 的 全局变量，当它的值为 1 时，表明需要执行调度函数。

1．进程状态发生变化时
Linux 进程状态不断发生变化，在下列状态转换是需要执行进程调度：
1）当前进程进入等待状态
例如，运行态的进程可以通过执行系统调用 sleep_on（）主动放弃 CPU 而进入等待状态 。

Sleep_on()的部分源代码如下：
Current->state=state; /* 把当前进程状态设置为等待状态*/
Save_flags(flags);
_add_wait_queue(p,&wait); /*把当前进程加入等待队列*/
Sti（）；
Schedule(); /*执行进程调度*/
Cli();
1
2
3
4
5
6
7

2）运行态下的进程运行结束后 运行态下的进程运行结束后
一般通过调用内核函数 do_exit()终止运行进程并转入僵死状态。该函数部分源码：

……
Current->state = TASK_ZOMBIE; /*把当前进程设置为僵死状态*/
……
Schedule（）；/*执行调度程序*/
……
1
2
3
4
5

3）使用使用 wake_up_process()将处于等待状态的进程唤醒，然后将它置于可运行状态 然后将它置于可运行状态。该函数部分源码：

Save_flags(flafs);
Cli();
p->state = TASK_RUNNING; /*把进程置为可运行态*/
if（！p—>next_run）
add_to_runqueue(p); /*加入到可运行队列*/
restore_flags(flags);
if(p->counter>current->counter+3)
need_resched =1; /*调度标志置位，执行进程调度*/
1
2
3
4
5
6
7
8

4）当一个进程的程序接受调试时 当一个进程的程序接受调试时，调式进程向被调试进程发送 SIGSTOP 信号，被调试进程处理该信号时调用内核函数 do_signal()。
部分源码：

Current->state = TASK_STOPPED /*把当前进程置为暂停态*/
Notify_parent(current)；
Schedule（）；/*执行进程调度*/
1
2
3

5）当被调试的进程接收到调试进程发送的 SIGCONT 信号时，执行 send_sig（），其中使用wake_up_process()解除被调试进程的暂停态而重新进入可运行态。

If（sig==SOGKILL||sig==SIGCONT））
{
If(p->state==TASK_STOPPED) /*若进程为暂停态*/
wake_up_process(p)；
1
2
3
4

2．当前进程时间片用完时

在进程时间片运行完时，需要将 CPU 重新分配给下一个被选中的进程，这个过程是在时钟中断中实现。在时钟中断处理程序中调用了内核函数 update_process_times(),它用于更新进程的各个时间信息，其中包括下面语句：

p->counter -= ticks
if(p->counter<0)
{
P->counter=0;
Need_resched=1;
}
1
2
3
4
5
6

3．进程从系统调用返回用户态时
当进程从系统调用返回用户态时，需要执行内核的汇编例程 ret_from_sys_call，其中包括对need_resched 标志进行检测的指令。

Cmpl ＄0，need_resched
Jne reschedule
当 need_resched=1 时，就转移到 reschedule。
Reschedule：
Call SYMBOL_NAME(schedule)
1
2
3
4
5

4．中断处理后，进程返回用户态时
同 3，当中断处理结束后，也需要执行内核的汇编例程 ret_from_sys_call