进程的概念
- 任务的实体
- 程序在内存的运行实例
- 计算机资源的管理者与拥有者
进程示意图
进程与线程的区别
- 为了充分利用SMP资源，在进程中衍生了线程，提高并行处理能力
- 一个进程由一个主线程与零个或多个线程组成
- 主线程与线程在内核映射为独立的任务体与调度对象。
- 内核没有线程概念，没有另外的调度算法与数据结构来表示线程
- 线程与所属进程共享地址空间，共享资源
- 内核线程即是没有用户空间在内核中运行的线程
linux进程与线程关系
进程在内核的表示
不管是进程或线程在内核中以struct task表示，struct task在<linux/sched.h>定义如下：
其中struct thread_info定义如下：
内核进程链表
在X86架构中可以通过current_thread_info()快速定位到当前task结构，如下图表示：
struct 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()函数流程：
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）决定的，已使用的虚拟时间越少，它在运行队列的位置越靠左，那么它再次被调度执行的概率也就越高
优先级与权重映射关系，权重越大，虚拟时间减缓就慢，在一个调度周期内可运行时间就越大。
CFS调度的算法示意图
schedule()函数流程：
用户抢占
- 内核返回用户空间，并且need_reshed()返回真值；
- 中断程序返回用户空间，并且need_reshed()返回真值
内核抢占
- 中断返回内核空间，并且need_reshed()返回真值与preempt_count计数为0；
- 内核再此具有抢占性时；
- 内核任务阻塞时，或显性调用schedule()
SMP与负载均衡程序
在对称多处理器中，每个处理器都有自己的运行队列与锁，调度系统对每个处理器是独立的，出于效率的考虑，应该有一个负载均衡程序来均衡各个处理器的运行进程数。
多处理器的负载均衡程序示意图
与调度相关的系统调用
总结
本文概括性地对Linux内核进程与调度原理简单进行介绍，涉及到内核新老两种调度算法。具体的一些概念与细节还是要多读读相关书籍与源码。