进程的概念

• 任务的实体
• 程序在内存的运行实例
• 计算机资源的管理者与拥有者

进程与线程的区别

• 为了充分利用SMP资源，在进程中衍生了线程，提高并行处理能力
• 一个进程由一个主线程与零个或多个线程组成
• 主线程与线程在内核映射为独立的任务体与调度对象。
• 内核没有线程概念，没有另外的调度算法与数据结构来表示线程
• 线程与所属进程共享地址空间，共享资源
• 内核线程即是没有用户空间在内核中运行的线程

进程在内核的表示

不管是进程或线程在内核中以struct task表示，struct task在<linux/sched.h>定义如下：

其中struct thread_info定义如下：

内核进程链表

在X86架构中可以通过current_thread_info()快速定位到当前task结构，如下图表示：

进程状态

进程在内核中的有几种状态：就绪状态、运行状态、休眠状态（分为“可中断”与“不可中断”）、僵死状态。

进度调用策略

• 策略：linux什么时候以什么样的方式选择一个进程投入运行的规则。
• 普通进程的策略：SCHED_NORMAL (算法：动态优先级 + 时间片，2.6.23版本以后的CFS）
• 实时进程的策略：SCHED_FIFO（一直运行除非让出CPU） , SCHED_RR（时间片轮询）

调度算法

算法一：动态优先级与时间片

算法复杂度：O(1)

静态优先级与nice：静态优先级 = MAX_RT_PRIO(100) + nice + 20

NICE = 静态优先级 – MAX_RT_RPIO(100) – 20

动态(有效)优先级：动态优先级 = 静态优先级 + 实时性奖罚（-5~5）

时间片计算：与静态优先级成比例缩放，19 ~ 5ms 0~100ms -20~800

每个运行队列有两个优先级数组：active 与expired优先级数组范围0 ~139，0~99为实时进程使用，100~139为普通进程使用

schedule()函数流程：

调度条件与抢占：

用户抢占

• 内核返回用户空间，并且need_reshed()返回真值；
• 中断程序返回用户空间，并且need_reshed()返回真值

内核抢占

• 中断返回内核空间，并且need_reshed()返回真值与preempt_count计数为0；
• 内核再此具有抢占性时；
• 内核任务阻塞时，或显性调用schedule()

算法二：CFS(完全公平调度)（2.6.23版本之后）

去掉时间片分配，动态优先级概念，不区分IO消耗型与CPU消耗型进程，引入模块化设计，fair 与rt 调度类,调度实体sched_entry,虚拟运行时间vruntime等概念；

复杂度：O(logn)

原理：每个se使用cpu的顺序由它们已使用的cpu虚拟时间（vruntime）决定的，已使用的虚拟时间越少，它在运行队列的位置越靠左，那么它再次被调度执行的概率也就越高

优先级与权重映射关系，权重越大，虚拟时间减缓就慢，在一个调度周期内可运行时间就越大。

schedule()函数流程：

用户抢占

• 内核返回用户空间，并且need_reshed()返回真值；
• 中断程序返回用户空间，并且need_reshed()返回真值

内核抢占

• 中断返回内核空间，并且need_reshed()返回真值与preempt_count计数为0；
• 内核再此具有抢占性时；
• 内核任务阻塞时，或显性调用schedule()

SMP与负载均衡程序

在对称多处理器中，每个处理器都有自己的运行队列与锁，调度系统对每个处理器是独立的，出于效率的考虑，应该有一个负载均衡程序来均衡各个处理器的运行进程数。

与调度相关的系统调用

总结

本文概括性地对Linux内核进程与调度原理简单进行介绍，涉及到内核新老两种调度算法。具体的一些概念与细节还是要多读读相关书籍与源码。