进程调度与内核数据结构
进程调度
进程调度程序是确保进程能有效工作的一个内核子系统。
多任务操作系统就是能同时并发地交互执行多个进程的操作系统，期可以划分为两类：非抢占式多任务和抢占式多任务。Linux采用的是抢占式多任务。
进程分为I/O消耗型和处理器消耗型，调度策略通常要做到进程响应迅速和最大系统利用率。Linux更倾向于优先调度I/O消耗性进程。
Linux的进程优先级采用两种不同的优先级范围。第一种是用nice值，范围是从-20到+19，默认为0，nice值越高优先级越低；第二种是实时优先级，其值可配置，默认范围是从0到99，数值越大优先级越高，而且任何实时进程优先级都搞与普通进程。
Linux进程调度算法为CFS“完全公平调度算法（CFS）”，它是一个针对普通进程的调度类，算法实现定义在文件kernel/sched_fair.c中。Linux中并未直接分配时间片到进程，而是将处理器的使用比划分给了进程。CFS下每个进程获得的时间片的底线称为最小粒度，默认是1ms。
进程调度主要入口点是schedule()，在进程进行抢占和上下文切换时候都要调用它来完成的。抢占分为用户抢占和内核抢占。用户抢占发生在内核即将返回用户空间的时候即内核从系统调用返回用户空间或者从中断处理程序返回用户空间时，如果内核从检查到need_resched标志被设置，就会调用schedule()选择一个更适合的进程投入运行。Linux完整的支持内核抢占，即只要重新调度是安全的（没有持有锁），内核就可以在任何时间抢占正在执行的任务，内核抢占一般发生在中断处理程序正在执行且返回内核空间之前、内核代码在一次具有可抢占性的时候、内核中的任务显式调用了schedule()或者内核中的任务阻塞。
内核数据结构
数据结构我们之前都学过，本课讲的主要有链表、队列、映射和二叉树。我们都已经十分熟悉，只是在Linux下会有些许不同。
Linux内核中链表实现独树一帜，它不是将数据结构塞入链表，而是将链表节点塞入数据结构。简单来说，Linux内核是将prev和next两个指针封装成为一个list_head的结构体并塞入父结构结点，其中prev和next两个指针分别指向相邻结点的list_head结构体，通过宏container_of()从链表指针找到父结构中包含的任何变量
struct list_head{
struct list list_head *next;
struct list list_head *prev;
}
struct fox{
unsigned long tail_length;
unsigned long weight;
bool is_fantastic;
struct list_head list;
}
容易看出链接起来的只是fox结构中的子结构list_head。
红黑树是一种自平衡二叉搜索树，具有特殊着色属性，或红或黑，有下面六个属性：
- 所有节点要么着红色，要么着黑色；
- 叶子节点都是黑色；
- 叶子节点不包含数据；
- 所有非叶子节点都有两个子节点；
- 如果一个节点是红色，则它的子节点都是黑色；
- 在一个节点到其叶子节点的路径中，如果总是包含同样数目的黑色节点，则该路径相比其他路径是最短的。
网络云课堂学习
Linux内核源码：
其中支持不同CPU源代码在/arch中，/init内核启动相关代码基本都在init目录下；start_kernel相当于普通C中的main函数；lib公用库函数代码；mm内存管理相关代码；net网络相关代码；arch/x86、init、kernel。
idle进程是0号进程，是第一个内核态进程；init是第一个用户态进程，是1号进程。
实验楼中启动内核：
cd LinuxKernel
qemu -kernel linux-3.18.6/arch/x86/boot/bzImage -initrd rootfs.img
内核启动完成后进入menu程序，支持三个命令help、version和quit，也可以添加更多命令。
通过在qemu后添加-s设置端口使用tcp的1234端口，在客户端通过target remote:1234建立和服务器端的链接。通过-S在开始时冻结CPU。
qemu是一种模拟处理器，用它来模拟内核启动。
vmlinuz是可引导的、压缩的内核。“vm”代表“Virtual Memory”。vmlinux是ELF文件，即编译出来的最原始的文件。vmlinuz应该是由ELF文件vmlinux经过OBJCOPY后，并经过压缩后的文件。zImage是vmlinuz经过gzip压缩后的文件，适用于小内核。bzImage是vmlinuz经过gzip压缩后的文件，适用于大内核。通常情况下是不能用vmlinuz解压缩得到vmlinux的。
再打开一个shell，通过break命令设置断点，通过c让被冻结的程序继续执行。
在kernel_init设置断点啊，然后进入函数内部：
通过list命令查看kernel_init附近代码：
通过单步执行进入函数kernel_init_freeable()内部，然后我们来看一个很重要的函数do_basic_setup(),所有直接编译在kernel中的模块都由它启动。
内核挂接根文件系统成功以后，将通过run_init_process()函数执行应用程序。这是一个尝试的过程，如果execute_command存在，则执行execute_command；如果不存在，则顺序执行/sbin/init、/etc/init、/bin/init、/bin/sh，直到有一个执行成功为止。如果都不存在，则会调用panic()上报错误。下面是kernel_init()函数：
static int __ref kernel_init(void *unused)
{
int ret;
kernel_init_freeable();
/* need to finish all async __init code before freeing the memory */
async_synchronize_full();
free_initmem();
mark_rodata_ro();
system_state = SYSTEM_RUNNING;
numa_default_policy();
flush_delayed_fput();
if (ramdisk_execute_command) {
ret = run_init_process(ramdisk_execute_command);
if (!ret)
return 0;
pr_err("Failed to execute %s (error %d)
",
ramdisk_execute_command, ret);
}
/*
* We try each of these until one succeeds.
*
* The Bourne shell can be used instead of init if we are
* trying to recover a really broken machine.
*/
if (execute_command) {
ret = run_init_process(execute_command);
if (!ret)
return 0;
pr_err("Failed to execute %s (error %d). Attempting defaults...
",
execute_command, ret);
}
if (!try_to_run_init_process("/sbin/init") ||
!try_to_run_init_process("/etc/init") ||
!try_to_run_init_process("/bin/init") ||
!try_to_run_init_process("/bin/sh"))
return 0;
panic("No working init found. Try passing init= option to kernel. "
"See Linux Documentation/init.txt for guidance.");
}
start_kernel()函数负责初始化内核各子系统，最后调用 rest_init()，启动一个叫作init的内核线程，继续初始化。在 init 内核线程中实现的功能很多，最重要的是负责完成挂接根文件系统、初始化设备驱动和启动用户空间的init进程等重要工作。
参考内容
http://blog.csdn.net/geekcome/article/details/6558754
http://blog.csdn.net/luomoweilan/article/details/17894473
http://lxr.free-electrons.com/source/init/main.c?v=3.18#L930
http://blog.chinaunix.net/uid-21633169-id-1823331.html
http://blog.csdn.net/liujiaoyage/article/details/37928667