LKD 笔记 2

Chapter 4 schedule

调度程序是内核的组成部分，它负责选择下一个要运行的程序.
在可运行态进程之间分配有限的处理器时间资源的内核子系统.
最大限度利用处理器时间的原则是，只要有可执行的进程，那么总会有进程正在执行。
但只要系统中可执行进程数比cpu个数多，在某一给定时刻会有一些进程不能运行。

I/O消耗型和处理器消耗型进程

调度策略实现目标： 进程响应迅速，最大的系统利用率.
linux为了保证交互式应用,更倾向于优先调度I/O消耗型进程

优先级:
调度程序选择时间片未用尽而且优先级最高的进程运行.
linux基于上述思想，实现了一种基于动态优先级的调度方法.
调度程序根据进程需要 动态调整优先级。

linux 提供两种独立的优先级
1. nice值 (-20~19, 默认是0. nice 越大优先级越低. being nice for others)
同时nice也用来决定分配给进程的时间片的长短。 -20

优先级:
调度程序选择时间片未用尽而且优先级最高的进程运行.
linux基于上述思想，实现了一种基于动态优先级的调度方法.
调度程序根据进程需要 动态调整优先级。

linux 提供两种独立的优先级
1. nice值 （-20~19 默认0, 值越大优先级越低, "being nice for others")
nice值也决定时间片的大小，-20的进程可能获得的时间片最长
2. 实时优先级 可配置 默认0～99。 任何实时进程的优先级都高于普通进程。
linux提供对posix实时优先级的支持

当一个进程时间片耗尽了， 就不会被再执行. unless 所有其他进程都耗尽了他们的时间片，那时所有进程的时间片会被重新计算.

preempt
当一个进程进入TASK_RUNNING状态，内核会检查他的优先级是否高于当前正在执行的进程。如果是，则唤醒调度程序，抢占当前正在运行的进程并执行新的可运行进程
此外，当一个进程的时间片为0的时候，他会被抢占，调度程序被唤醒选择一个新的进程

I/O消耗型 与处理器消耗型相比 应该高优先级,长时间片. 可以在需要时抢占处理器消耗型的进程. 同时保证他有足够的时间片可用

linux调度算法
调度算法实现以下目标:
a.充分实现O(1)调度，不管有多少进程，调度程序采用的每个算法都能在恒定的时间内完成.
b.全面实现SMP的可扩展性，每个处理器有自己的锁和可执行队列
c.尽量将同一组任务分配给一个cpu连续执行，只有在需要平衡任务队列大小的时候才在cpu之间移动进程
d.加强交互性能，即使cpu处在相当负载的情况下 也能保证系统的响应，并立即调度交互式进程
e.保证公平，在合理设定的时间范围内，没有进程会处长期得不到执行，也没有进程能不公平的得到大量的时间片
f.多处理器多进程优化

调度程序中最基本的数据结构是运行队列,是给定处理器上可执行进程链表，每个处理器一个.
每个可投入运行的进程都唯一归属于一个可执行队列。 可执行队列还包含每个处理器的调度信息

cpu_rq(processor)返回给定处理器的可执行队列指针
this_rq() 返回当前处理器的可执行队列
task_rq() 返回给定任务所在队列指针

队列操作锁
task_rq_lock()
task_rq_unlock()

为了避免死锁，要锁住多个运行队列的代码必须总是按照同样的顺序来获取这些锁：按照可执行队列地址从低到高的顺序。
if (rq1 == rq2) {
spin_lock(&rq1->lock);
} else {
if (rq1 < rq2) {
spin_lock(&rq1->lock);
spin_lock(&rq2->lock);
} else {
spin_lock(&rq2->lock);
spin_lock(&rq1->lock);
}
}

spin_unlock(&rq1->lock);
if (rq1 != rq2)
spin_unlock(&rq2->lock);

以上为double_rq_lock(rq1, rq2) double_rq_unlock(rq1, rq2)实现的核心部分

优先级数组 nr_active /*任务数*/ bitmap[] /*优先级位图*/ queue[] /*优先级队列*/
schedule() 通过sched_find_first_bit() 找到bitmap中最高的可执行优先级，调度相应的queue. 所以schedule时间恒定

进程拥有一个初始的优先级，叫nice值（-20~19,默认为0), 19最低 -20最高
这个值放在task_struct->static_prio. 这个值从一开始由用户指定，不能改变

动态优先级存放在prio域， 由一个关于静态优先级和进程交互性的函数关系计算而来.

effective_prio() 返回进程的动态优先级

如果一个进程大部分时间在休眠 是I/O型， 反之如果一个进程执行的时间比休眠长 则是处理器消耗型

task_struct->sleep_avg 用于统计进程休眠和执行时间, 当一个进程恢复运行的时候, sleep_avg会根据它休眠时间长短而增加, 相反进程每执行一个时钟节拍, sleep_avg
就做相应递减。
新建子进程和父进程均分父进程剩余的时间片

load_balance() 处理多处理器负载平衡.

context_switch() 完成进程的上下文切换， 完成switch_mm() 虚拟内存映射 switch_to() 从上一个进程处理器状态切换到新进程处理器状态. 保存 恢复栈信息 寄存器信息

内核返回用户空间的时候， 如果need_resched被设置, 就有可能发生用户抢占
用户抢占发生情况：
1. 从系统调用返回用户空间
2. 从中断处理程序返回用户空间

内核抢占
preempt_count 为0时 可以内核抢占， 为1时 说明当前任务持有锁 抢占不安全 不能抢占
显示的调用schedule()，那么调用者应该清楚自己是可以安全的被抢占的
内核抢占:
1. 中断处理程序正在执行， 返回内核空间之前
2. 内核再一次具有可抢占性的时候
3. 内核任务显示调用schedule()
4. 内核中的任务阻塞

sched_yield() 显示的将处理器时间让给其他进程