Linux进程的调度

上回书说到 Linux进程的由来 和 Linux进程的创建 ，其实在同一时刻只能支持有限个进程或线程同时运行(这取决于CPU核数量，基本上一个进程对应一个CPU)，在一个运行的 *** 作系统上可能运行着很多进程，如果运行的进程占据CPU的时间很长，就有可能导致其他进程饿死。为了解决这种问题， *** 作系统引入了 进程调度器 来进行进程的切换，轮流让各个进程使用CPU资源。

1）rq： 进程的运行队列( runqueue)， 每个CPU对应一个 ，包含自旋锁(spinlock)、进程数量、用于公平调度的CFS信息结构、当前运行的进程描述符等。实际的进程队列用红黑树来维护(通过CFS信息结构来访问)。

2）cfs_rq： cfs调度的进程运行队列信息 ，包含红黑树的根结点、正在运行的进程指针、用于负载均衡的叶子队列等。

3）sched_entity： 把需要调度的东西抽象成调度实体 ，调度实体可以是进程、进程组、用户等。这里包含负载权重值、对应红黑树结点、 虚拟运行时vruntime 等。

4）sched_class：把 调度策略(算法)抽象成调度类 ，包含一组通用的调度 *** 作接口。接口和实现是分离，可以根据调度接口去实现不同的调度算法，使一个Linux调度程序可以有多个不同的调度策略。

1） 关闭内核抢占 ，初始化部分变量。获取当前CPU的ID号，并赋值给局部变量CPU， 使rq指向CPU对应的运行队列 。 标识当前CPU发生任务切换 ，通知RCU更新状态，如果当前CPU处于rcu_read_lock状态，当前进程将会放入rnp->blkd_tasks阻塞队列，并呈现在rnp->gp_tasks链表中。 关闭本地中断 ，获取所要保护的运行队列的自旋锁， 为查找可运行进程做准备 。

2） 检查prev的状态，更新运行队列 。如果不是可运行状态，而且在内核态没被抢占，应该从运行队列中 删除prev进程 。如果是非阻塞挂起信号，而且状态为TASK_INTER-RUPTIBLE，就把该进程的状态设置为TASK_RUNNING，并将它 插入到运行队列 。

3）task_on_rq_queued(prev) 将pre进程插入到运行队列的队尾。

4）pick_next_task 选取将要执行的next进程。

5）context_switch(rq, prev, next)进行 进程上下文切换 。

1) 该进程分配的CPU时间片用完。

2) 该进程主动放弃CPU(例如IO *** 作)。

3) 某一进程抢占CPU获得执行机会。

Linux并没有使用x86 CPU自带的任务切换机制，需要通过手工的方式实现了切换。

进程创建后在内核的数据结构为task_struct ， 该结构中有掩码属性cpus_allowed，4个核的CPU可以有4位掩码，如果CPU开启超线程，有一个8位掩码，进程可以运行在掩码位设置为1的CPU上。

Linux内核API提供了两个系统调用 ，让用户可以修改和查看当前的掩码：

1) sched_setaffinity()：用来修改位掩码。

2) sched_getaffinity()：用来查看当前的位掩码。

在下次task被唤醒时，select_task_rq_fair根据cpu_allowed里的掩码来确定将其置于哪个CPU的运行队列，一个进程在某一时刻只能存在于一个CPU的运行队列里。

在Nginx中，使用了CPU亲和度来完成某些场景的工作：

worker_processes      4

worker_cpu_affinity 0001001001001000

上面这个配置说明了4个工作进程中的每一个和一个CPU核挂钩。如果这个内容写入Nginx的配置文件中，然后Nginx启动或者重新加载配置的时候，若worker_process是4，就会启用4个worker，然后把worker_cpu_affinity后面的4个值当作4个cpu affinity mask，分别调用ngx_setaffinity，然后就把4个worker进程分别绑定到CPU0～3上。

worker_processes      2

worker_cpu_affinity 01011010

上面这个配置则说明了两个工作进程中的每一个和2个核挂钩。

System V init启动过程

概括地讲,Linux/Unix系统一般有两种不同的初始化启动方式.

1) BSD system init

2) System V init

大多数发行套件的Linux使用了与System V init相仿的init也就是Sys V init,它比传统的BSD system init更容易且更加灵活。

System V init的主要思想是定义了不同的"运行级别(runlevel)"。通过配置文件/etc/inittab定义了系统引导时的运行级别, 进入或者切换到一个运行级别时做什么。每个运行级别对应于一个子目录/etc/rc.d/rcX.d。

每个rcX.d目录中都是一些以S或K开头的文件链接。这些链接指向的脚本都 可以接收start和stop参数，S开头的链接会传入start参数，一般是开启一项服务，K会传入stop参数，一般是停止某服务。

以下是一个大致的System V init过程:

(1)init 过程执行的第一个脚本是 /etc/rc.d/rc.sysinit，它主要做在各个运行级别中进行初始化工作,包括: 启动交换分区检查磁盘设置主机名检查并挂载文件系统加载并初始化硬件模块.

(2)执行缺省的运行级别模式。 这一步的内容主要在/etc/inittab中体现, inittab文件会告诉init进程要进入什么运行级别,以及在哪里可以找到该运行级别的配置文件.

(3)执行/etc/rc.d/rc.local脚本文件。 这也是init过程中执行的最后一个脚本文件,所以用户可以在这个文件中添加一些需要在登录之前执行的命令.

(4)执行/bin/login程序

注意：

System V init只是一种模式，每个系统初始化都有差异，但大体上不会相差太多。如busybox执行的第一个启动脚本就是/etc/init.d/rcS，而且不可以改变，与上面讲的不同。

LFS文件系统初始化示例

inittab文件

由下内容可以看出，最先执行的是/etc/rc.d/init.d/rc文件，给这个文件传入的参数是一个数字，rc会由传入的数字合成rcX.d目录的路径，然后执行其中的所有脚本链接。当然这只是一部分功能。

# Begin /etc/inittab

id:3:initdefault:

<em><strong>si::sysinit:/etc/rc.d/init.d/rc sysinit</strong></em>#可以设定初始化脚本

l0:0:wait:/etc/rc.d/init.d/rc 0

l1:S1:wait:/etc/rc.d/init.d/rc 1

l2:2:wait:/etc/rc.d/init.d/rc 2

...

ca:12345:ctrlaltdel:/sbin/shutdown -t1 -a -r now

su:S016:once:/sbin/sulogin

1:2345:respawn:/sbin/agetty tty1 9600

2:2345:respawn:/sbin/agetty tty2 9600

...

# End /etc/inittab

etc目录结构

只是一部分，有删减。

.

├── fstab

├── <em>inittab</em>

├── inputrc

├── profile

├── rc.d

│ ├── init.d

│ │ ├── checkfs

│ │ ├── cleanfs

...

│ │ ├── modules

│ │ ├── mountfs

│ │ ├── mountkernfs

│ │ ├── network

│ │ ├── rc#when boot, run.

│ │ ├── reboot

...

│ ├── rc0.d

│ │ ├── K80network ->../init.d/network

│ │ ├── K90sysklogd ->../init.d/sysklogd

│ │ ├── S60sendsignals ->../init.d/sendsignals

│ │ ├── S70mountfs ->../init.d/mountfs

│ │ ├── S80swap ->../init.d/swap

│ │ ├── S90localnet ->../init.d/localnet

│ │ └── S99halt ->../init.d/halt

│ ├── rc1.d

│ │ ├── K80network ->../init.d/network

│ │ └── K90sysklogd ->../init.d/sysklogd

│ ├── rc2.d

│ │ ├── K80network ->../init.d/network

│ │ └── K90sysklogd ->../init.d/sysklogd

│ ├── rc3.d

│ │ ├── S10sysklogd ->../init.d/sysklogd

│ │ └── S20network ->../init.d/network

│ ├── rc4.d

│ │ ├── S10sysklogd ->../init.d/sysklogd

│ │ └── S20network ->../init.d/network

│ ├── rc5.d

│ │ ├── S10sysklogd ->../init.d/sysklogd

│ │ └── S20network ->../init.d/network

│ ├── rc6.d

│ │ ├── K80network ->../init.d/network

│ │ ├── K90sysklogd ->../init.d/sysklogd

│ │ ├── S60sendsignals ->../init.d/sendsignals

│ │ ├── S70mountfs ->../init.d/mountfs

│ │ ├── S80swap ->../init.d/swap

│ │ ├── S90localnet ->../init.d/localnet

│ │ └── S99reboot ->../init.d/reboot

│ └── rcsysinit.d

│ ├── S00mountkernfs ->../init.d/mountkernfs

│ ├── S02consolelog ->../init.d/consolelog

│ ├── S05modules ->../init.d/modules

...

├── udev

│ ├── rules.d

│ │ └── 55-lfs.rules

│ └── udev.conf

└── vimrc

network脚本

#!/bin/sh

. /etc/sysconfig/rc

. ${rc_functions}

. /etc/sysconfig/network

case "${1}" in

start)

# Start all network interfaces

for file in ${network_devices}/ifconfig.*

do

interface=${file##*/ifconfig.}

# skip if $file is * (because nothing was found)

if [ "${interface}" = "*" ]

then

continue

fi

IN_BOOT=1 ${network_devices}/ifup ${interface}

done

stop)

# Reverse list

FILES=""

for file in ${network_devices}/ifconfig.*

do

FILES="${file} ${FILES}"

done

# Stop all network interfaces

for file in ${FILES}

do

interface=${file##*/ifconfig.}

# skip if $file is * (because nothing was found)

if [ "${interface}" = "*" ]

then

continue

fi

IN_BOOT=1 ${network_devices}/ifdown ${interface}

done

restart)

${0} stop

sleep 1

${0} start

*)

echo "Usage: ${0} {start|stop|restart}"

exit 1

esac

# End /etc/rc.d/init.d/network



        进程大致可分为I/O密集型和 CPU密集型。

        调度依据 动态优先级 ，所谓动态优先级就是初始化时给出一个基础优先级，随后优先级可被调度程序动态的增减。高优先级进程也获得较长的时间片。I/O密集型通常被提升优先级，而CPU密集型则被降低。            

        Linux系统有两种独立的优先级范围。第一种是 Nice 值，返回是[-20, 19]，默认值为0。数值越高优先级越低。Nice值影响了时间片的分配。如果进程拥有-20的Nice值，那么该进程将被分配理论最长的时间片。Nice值是所有Unix系统的标准优先级。

        Linux的第二种优先级范围是 实时优先级 。这个优先级的值是可配置的。通常来说范围在[0,99]。 所有实时进程的优先级都高于普通进程 。(实时进程是什么？)

        时间片是一个数值，决定了进程被抢占前可运行的时间。必须为进程分配合适长度的时间片。时间片太长会影响系统的交互性，时间片太短则会导致系统花费大量的时间用于进程的切换。同时还要兼顾I/O密集型和 CPU密集型进程的矛盾。因为I/O密集型无需长时间片，却渴望经常运行。而Linux却提供了相对较长的默认时间片——100毫秒。   

        注意到，进程不必在每次被调度运行后就花光自己所有的时间片。举例来说，如果一个进程拥有长达100毫秒的时间片，那么它可以在五个不同时段运行，每次花费20毫秒的时间片。这么做的好处是，一个拥有长时间片的进程（尽管它本身不需要如此长的时间片），可以尽可能长时间的保持运行状态。而不会过早地被丢入等待调度的队列中（稍后说到）。这就好比键盘驱动进程的实现方法。

        当某进程的状态变为TASK_RUNNING的时候，内核会检查它的优先级是否高于当前正在执行的任务。如果是，调度进程就会使该进程抢占CPU。另外，如果一个进程的时间片变成0（意味着用尽了所有时间片，只能等待所有进程时间片为0才会重新分配），调度进程会被再次调用，选择一个新的进程运行。

        个人猜测 ：这里拿文字软件和音乐播放软件来举例。CPU在每条指令执行结束后检查中断引脚。如果检测到键盘的活动，就会引发中断而将键盘输入程序的状态设置为TASK_RUNNING，然后执行上述的检查程序。因为文字软件的优先级高于音乐播放软件，所以文字软件将立即得到执行，将键入字符输入在屏幕中。完成这一工作后，文字软件将设置自身状态或是其他方法，使得音乐播放软件可以抢占CPU？

---