20169207《Linux内核原理与分析》第五周作业 这周的任务主要分为两个方面，第一方面，学习MOOC网上视频第三讲并完成配套的实验。第二方面，学习课本的第四章和第六章。 阅读课本的第四章和第六章。首先，在进程调度章节，结合本科期间操作系统的进程调度，对抢占式和非抢占式多任务，进程调度算法以及实现，抢占和上下文切换，实时调度策略这些概念有了全新的认识。 在内核数据结构章节，介绍了链表，队列，映射，二叉树等结构。然后在讲了他们在linux内核中的具体实现。这些知识点在本科期间的或多或少的涉及过一部分。结合本科期间的知识和现在的新资料，让我对计算机的内部结构和运行方式又加深了了解。数据结构我们之前都学过，本课讲的主要有链表、队列、映射和二叉树。我们都已经十分熟悉，只是在Linux下会有些许不同。
首先从实验开始讲起，前期我们对Linux内核的源码做了一个简单的了解。包括Main函数是Linux内核运行的起点，具体是Start_kernel，就相当与C语言的Main函数。还介绍了一些和安全，网络，声音，脚本，和工具相关的包。包括介绍了一些Linux的历史和发展。
接下来启动内核进入menu程序。
接下来要使用gdb跟踪调试内核.
vmlinux 它是是未压缩的内核，即编译出来的最原始的文件
用于kernel调试，产生system.map符号表，不能用于直接加载，
bzImage 压缩的内核映像
initrd 是在系统引导过程中挂载的一个临时根文件系统
这里的S是用来冻结cpu运行的，
s是用来指定端口的，若不想使用1234端口，则可以使用-gdb tcp:xxxx来取代-s选项。
这里需要再打开一个shell窗口，开始使用gdb跟踪调试内核。
(gdb) file linux-3.18.6/vmlinux #在gdb界面中targe remote之前加载符号表，打开gdb需要调试得文件。
将带有调试信息得linux镜像加载进来。
(gdb) target remote:1234#建立gdb和gdbserver之间的连接，按c 让qemu上的linux继续进行。
链接到我们刚才启动得冻结得linux系统。
(gdb)break start_kernel#断点的设置可以在target remote之前，也可以在之后。
按c之后开始启动内核。按n单步执行。s进入函数，finish结束掉当前函数。
list命令显示当前的代码。break可跳到自己需要观察的代码段！然后逐步的观察运行情况。
内核挂接根文件系统成功以后，将通过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进程等重要工作。
阅读课本的第四章和第六章。首先，在进程调度章节，结合本科期间操作系统的进程调度，对抢占式和非抢占式多任务，进程调度算法以及实现，抢占和上下文切换，实时调度策略这些概念有了全新的认识。
进程调度程序是确保进程能有效工作的一个内核子系统。
多任务操作系统就是能同时并发地交互执行多个进程的操作系统，期可以划分为两类：非抢占式多任务和抢占式多任务。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内核中链表实现独树一帜，它不是将数据结构塞入链表，而是将链表节点塞入数据结构。简单来说，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。
红黑树是一种自平衡二叉搜索树，具有特殊着色属性，或红或黑，有下面六个属性：
•所有节点要么着红色，要么着黑色；
•叶子节点都是黑色；
•叶子节点不包含数据；
•所有非叶子节点都有两个子节点；
•如果一个节点是红色，则它的子节点都是黑色；
•在一个节点到其叶子节点的路径中，如果总是包含同样数目的黑色节点，则该路径相比其他路径是最短的。