Linux内核设计与实现(第三版) 学习笔记

第2章从内核出发

2.1 内核源码

可以从内核网站中下载Linux的内核源码。可以使用uname -r查看内核release版本号。

也可以使用如下命令查看最新的版本源代码

1
2
3

git clone git://git.kernel.org/pub/scm/linux/kernel/git/torvalds/linux-2.6.git
#更新到最新版本
git pull

也可以直接使用如下命令直接clone最新版本。然后使用git checkout来切换分支

1	git clone git://git.kernel.org/pub/scm/linux/kernel/git/stable/linux-stable.git

Linux中一般使用补丁的形式对发布的代码进行修改，增量补丁可以作为版本转移的桥梁。使用如下代码在内部源码树开始进行增量补丁的添加

1	patch -p1 < .../patch-x.y.z

2.2 内核源码结构

内核源码由很多目录组成，而大多数目录又包含更多的子目录。源码树的根目录及其子目录如下表所示：

目录	描述
arch	特定体系结构的源码如：ARM，AMD64
block	块设备I/O层
crypto	加密API
Documentation	内核源码文档
drivers	设备驱动程序
firmware	使用某些驱动程序而需要的设备的固件
fs	VFS和各种文件系统
include	内核头文件
init	内核引导和初始化
ipc	进程间通信代码
kernel	调度程序等核心子系统
lib	通用内核函数
mm	内存管理子系统和VM
net	网络子系统
samples	示例，示范代码
scripts	编译内核所用的脚本
security	Linux安全模块
sound	语音子系统
usr	早期用户空间代码(所谓的initramfs)
tools	在Linux开发中有用的工具
virt	虚拟化基础结构

2.3 编译内核

略

2.4 内核开发的特点

内核编程时既不能访问c库也不能访问标准的c头文件
1. 完整的C库太大过于低效；
2. 基本头文件在顶级目录下的include目录中；体系结构相关的头文件在arch//include/asm目录下使用#include <asm/ioctl.h>进行头文件的包含。
GNU C
1. 内核开发包括了C99标准以及GNU C扩展特性
2. 内联函数；使用inline内联函数
3. 内联汇编；使用asm volatile("rdtsc":"=a" (low),"=d" (high))嵌入汇编代码
4. 分支声明；使用likely和unlikely对于if-else条件分支选择进行优化
没有内存保护机制
1. 用户程序的非法内存访问由内核兜底并结束进程；内核自己非法内存访问就直接寄了
2. 内核的内存不分页
不要轻易在内核使用浮点数
1. 用户程序的浮点操作会通过内核转换为整数操作
2. 内核本身不能完美地支持浮点操作
内核给每个进程只有一个很小的定长堆栈
1. 内核栈的准确大小随着体系结构而改变，内核栈的大小是两页，32位是8KB，64位是16KB。
需要关注并发和同步
1. Linux是抢占多任务操作系统，内核包含了调度程序，内核必须和这些任务同步
2. Linux支持对称多处理器系统(SMP)，需要考虑多处理器并发访问同一个资源的情况
3. 中断随时都可能发生
4. Linux内核可抢占，没有保护，可能导致几段代码同时访问相同的资源，通常使用自旋锁和信号量来解决
要仔细考虑可移植的特性
1. 注意保持字节序、64位对齐、不假定字长和页面长度等一系列准则等

第3章进程管理

3.1 进程

每一个线程都拥有一个独立的程序计数器、进程栈、一组进程寄存器。内核调度的对象是线程，而不是进程 (从进程和线程了解浏览器的工作原理)；在Linux中对线程和进程的区分度不是很大。
线程之间共享虚拟内存，但是每个线程都拥有自己独立的虚拟处理器。
程序本身不是进程。可以存在多个进程执行同一个程序；多个进程也可以共享诸多资源，比如打开文件或者地址空间
进程一般通过fork()复制现有进程创建新进程；调用结束后，父进程恢复执行，子进程开始执行。fork()系统调用从内核返回两次，一次回到父进程，一次回到子进程。
新的进程可以通过调用exec()创建新的地址空间；程序通过exec()系统调用推出。父进程可以通过wait4()查询子进程是否被终结。

3.2 进程描述符

参考链接： Linux进程描述符task_struct结构体详解;文件描述符（File Descriptor）简介

内核通过任务队列的(双向循环链表)来存放和管理进程列表。其中存放的数据类型是task_struct，即进程描述符，定义在<linux/sched.h>文件中，包含有：打开的文件、进程的地址空间、挂起的信号、进程的状态等信息。

3.2.1 分配进程描述符

Linux 通过slab分配器分配task_struct结构。slab生成一个task_struct,只需要在栈底(向下增长的栈)或栈顶(向上增加的栈)创建一个新的结构thread_info(定义在<asm/thread_info.h>)中内容如下：

struct thread_info{
    struct task_struct  *task;
    struct exec_domain  *exec_domain;
    __u32               flags;
    __u32               status;
    __u32               cpu;
    int fd              preempt_count;
    mm_segment_t        addr_limit;
    struct restart_block    restart_block;
    void                    *sysenter_return;
    int                     uaccess_err;
}

每个任务的thread_info结构在它的内核栈的尾端分配，结构中task域中存放的是指该任务实际task_struct的指针

3.2.2 进程描述符的存放

内核通过唯一的进程标识值(PID)来标识每一个进程。PID类型是pid_t，实际上是int,最大值位32768；不考虑兼容性的情况下可以通过修改/proc/sys/kernel/pid_max提高上限。
内核中的访问任务，通常需要获取其指向task_struct的指针。一般是通过current宏来查找当前正在运行进程的task_struct。不同的硬件体系结构实现的方式不同。一般都是汇编配合专用寄存器来实现的。

3.2.3 进程状态

进程描述符中的state域描述了当前集成的状态。必然是下面的5种情况之一
1. TASK_RUNNING(运行):进程可执行或者正在执行
2. TASK_INTERRUPTIBLE(可中断):进程正在睡眠状态(也就是说它被阻塞)，等待某些条件的达成。就可以从状态回到运行态
3. TASK_UNINTERRUPTIBLE(不可中断):就算接收到信号也不会被唤醒或准备
4. __TASK_TRACED:被其它进程跟踪的进行，例如通过ptrace对调试程序进行跟踪
5. __TASK_STOPPED(停止)：进程停止执行；进程没有投入运行也不能投入运行。

3.2.4 设置进程状态

内核可以使用set_task_state(task,state)或set_current_state(state)函数来更改和设置进程的状态

3.2.5 进程上下文

可执行程序代码是进程的重要组成部分，这些代码从一个可执行文件载入到进程的地址空间执行。
需要注意的是，执行系统调用时，内核“代表进程执行”并处于进程上下文中，此时current宏是有效的；相对的中断上下文中，系统不代表进程执行，而是执行中断处理程序，所以此时不存在进程上下文。

3.2.6 进程家族树

Linux和unix中所有的进程都是PID为1的init进程的后代。内核在系统启动的最后阶段启动init进程。init进程读取系统的初始化脚本(initscript)并执行其它程序，最终完成系统启动的整个过程。

系统中每一个进程必有一个父进程。每个task_struct都包含一个指针指向其父进程task_struct的parent指针。也有一个children的子进程链表。可以通过如下代码依次访问父进程和子进程：

//获取父进程

struct task_struct *my_parent=current->parent;
//依次访问子进程

struct task_struct* task;
struct list_head *list;
list_for_each(list,&current->children){
    task=list_entry(list,struct task_struct,siblings);
}

init进程的进程描述符是作为init_task静态分配的。下面的代码可以很好的演示所有进程之间的关系:

struct task_struct *task;
//一直指向直到查找到init进程

for(task==current;task!=&init_task;task=task->parent){

}

//获取链表的下一个进程

list_entry(task->task.next,struct task_struct task);
//获取前一个进程

list_entry(task->task.prev,struct task_struct task);

3.3 进程创建

Linux使用fork()以及exec()的组合来创建进程。

3.3.1 写拷贝

linux中的fork()使用写时拷贝(copy-on-write)页实现。fork()时内核并不复制整个进程地址空间，而是让父进程和子进程共享一个拷贝。只有在需要写入的时候，数据才会被复制。之前都是以只读方式共享。因此fork()的实际开销在于复制父进程的页表以及给子进程创建唯一的进程描述符。

3.3.2 fork()

fork()函数调用clone()系统调用，再由clone()去调用do_fork(),do_fork()调用copy_process()函数，然后让进程开始运行。copy_process()完成的工作内容如下：

调用dup_task_struct()为新进程创建一个内核栈、thread_info结构和task_struct，这些值与当前进程的值相同。此时，子进程和父进程的描述符是完全相同的
检查确认子进程后，确认当前用户所拥有的进程数目没有超出它分配的资源
子进程开始设置与父进程的差异值。进程描述符中许多成员都要被清0或者重新初始化
子进程状态被设置为TASK_UNINTERRUPTIBLE，防止被投入运行
copy_process()调用copy_flags()以更新task_struct的flags成员。
调用alloc_pid()为新进程分配一个有效的pid
根据clone()函数接收到的参数，为copy_process()拷贝或共享打开的文件、文件系统信息、信号处理函数、进程地址空间和命名空间等
最后，copy_process()做扫尾工作，并返回一个指向子进程的指针。

最终层层调用回归，kernel会优先选择执行子进程，因为一般子进程都会马上调用exec()函数。避免额写拷贝开销。如果父进程先执行，则可能会开开始向地址空间中写入。

3.3.3 vfork()

vfork()不拷贝父进程的页表项，其它基本相同；子进程作为父进程的一个单独的线程在它的地址空间中运行。不过现在基本没什么作用了。

3.4 线程在Linux中的实现

Linux中将所有的线程都当做进程来实现，内核并没有准备特别的线程调度算法或特定数据结构。线程仅仅被视为一个与其它进程共享某些资源的进程。每个线程都拥有唯一一个task_struct。(Windows或者Solaris都在内核中提供了专门的线程支持机制–轻量级进程)

3.4.1 创建线程

创建线程与进程相似，不过是在调用clone时需要传递参数来指明需要共享的资源。

//clone 参数
clone(CLONE_VM|CLONE_FS|CLONE_FILES|CONLE_SIGHAND,0)

//普通fork实现

clone(SIGCHLD,0);
//vfork()实现

clone(CLONE_VFORK|CLONE_VM|SIGCHLD,0);

clone的标志位可选内容如下：

3.4.2 内核线程

内核中也是存在线程，称为内核线程。内核线程没有独立的地址空间(实际上指向地址空间的mm指针被设置为NULL)。他们只在内核空间运行，从来不切换到用户空间去。使用ps -ef可以查看到内核线程。

从现有内核中创建一个新的内核线程的方法如下：

1
2
3

struct task_struct *kthread_create(int (*threadfn)(void *data),void *data,const char namefmt[],...)

struct task_struct *kthread_run(int(*threadfn)(void *data),void data,const char namefmt[],...)

新创建的进程不会主动运行。需要使用kthread_run()函数来让进程运行起来。kthread_run()是以宏实现的具体实现代码如下：


#define kthread_run(threadfn,data,namefmt,...) \ 
({ \ 
	struct task_struct *k; \ 
	k=kthread_create(threadfn,data,namefmt,##__VA_ARGS__); \ 
	if(!IS_ERR(k)) \ 
	wake_up_process(k); \ 
	k; \ 
}) \

内核线程启动之后一直运行知道调用do_exit()退出，或者内核的其他部分调用 kthread_stop()退出。

3.5 进程终结

一般进程的析构是自身引起的，发生在exit()被调用时。C语言编译器会在main函数的return 之后调用exit()函数。exit()函数的主要任务由do_exit()来完成。主要完成下面的几个工作：

将task_struct中的标志成员设置为PF_EXITING;
调用del_timer_sync()删除任一内核定时器。取消CPU排队。
如果BSD()的进程记账功能是开启的，会调用acct_update_integrals()来输出记账信息。
调用exit_mm()来释放进程占用的mm_struct。内存没有被共享就彻底释放他们。
调用sem_exit()函数。取消正在等待的IPC信号队列
调用exit_files()和exit_fs()，分别递减文件描述符、文件系统数据的引用计数。计数为0释放资源
将存放在task_struct中的exit_code成员中的退出代码设置为exit()提供的退出代码。供父进程随时检索
调用exit_notify()向父进程发送信号，并给子进程重新寻找养父(线程组中的其它线程或者init进程)，把进程状态(task_struct结构中的exit_state)设置为EXIT_ZOMBIE。
调用schedule()切换到新的进程。处于EXIT_ZOMBIE状态的进程不会再被调度。

上述操作之后，进程不可运行并处于EXIT_ZOMBIE状态，它存在的唯一目的就是向它的父进程提供信息。父进程检索到信息之后(或通知内核子进程信息是无关信息后)。进程持有的剩余内存(task_struct)被释放。所有资源回归给系统。

3.5.1 删除进程描述符

当父进程收到消息，并且确认进程无用时，就可以进程进程描述符的删除。删除工作主要由release_task()函数完成主要工作内容如下：

调用__exit_signal()函数，它调用__unhash_process(),后者继续调用detach_pid()。从pidhash上删除该进程，即将该进程从任务列表中删除。
__exit_signal()函数释放当前僵死进程所用的所有剩余资源，并进行最终统计和记录。
如果这个进程是线程最后一个进程，并且领头进程已经死掉，那么release_task()将通知僵死的领头进程的父进程。
release_task()调用put_task_ struct()释放进程内核栈和thread_info结构所占的页,并释放task_struct所占的slab高速缓存。

3.5.2 孤儿进程造成的进退维谷

父进程在子进程之前退出，会给子进程在当前线程组内找一个线程作为父亲，如果不行，就让init做他们的父进程（通过这样的方法可以防止这些“孤儿”进程在退出的时候永远处于僵死状态浪费内存）。函数调用顺序如下:do_exit()->exit_notify()->forget_original_parent()->find_new_reaper();find_new_reaper()函数执行过程如下：


static struct task_struct *find_new_reaper(struct task_struct *father)
{
    struct pid_namespace *pid_ns=task_active_pid_ns(father);
    struct task_struct *thread;
    thread=father;
    //遍历每一个线程，寻找最佳的线程

    while_each_thread(father,thread){
        //检查任务是否存在，否则跳过下面的执行

        if(thread->flags&PF_EXITING)
            continue;
        //将它的孩子指针指向father;

        if(unlikely(pid_ns->child_reaper==father))
            pid_ns->child_reaper=thread;
        return thread;
    }
    //pid_ns没有指向father
    if(unlikely(pid_ns->child_reaper==father)){
        //进行任务列表加锁
        
        write_unlock_irq(&tasklist_lock);
        //检查是否是初始化进程

        if(unlikely(pid_ns==&init_pid_ns)){
            panic("Attempted to kill init");
        }
        zap_pid_ns_processes(pid_ns);
        write_lock_irq(&tasklist_lock);

        pid_ns->child_reaper=init_pid_ns.child_reaper;
    }
    return pid_ns->child_reaper;
}

主要是通过对各个进程的遍历，查找可以作为父进程的指针在找到养父进程之后，就可以遍历所有子进程并为他们设置新的父进程：

reaper=find_new_reaper(father);

list_for_each_entry_safe(p,n,&father->children,siblings){
    p->real_parent=reaper;
    if(p->parent==father){
        BUG_ON(p->ptrace);
        p->parent=p->real_parent;
    }
    reparent_thread(p,father);
}

接下来使用ptrace_exit_finish()同样进行新的寻父过程，不过这次是给ptraced的子进程寻找父亲

void exit_ptrace(struct task_struct *tracer){
    struct task_struct *p,*n;
    LIST_HEAD(ptrace_dead);
    //添加任务线程锁

    write_lock_irq(&tasklist_lock);
    list_for_each_entry_safe(p,n,&tracer->ptraced,ptrace_entry){
        if(__ptrace_detach(tracer,p)){
            list_add(&p->ptrace_entry,&ptrace_dead);
        }
    }
    write_unlock_irq(&tasklist_lock);
    BUG_ON(!list_empty(&tracer->ptraced));
    list_for_each_entry_safe(p,n,&tracer->ptraced,ptrace_entry){
        list_del_init(&p->ptrace_entry);
        release_task(p);
    }
}

第四章进程调度

调度程序负责决定将哪一个进程投入运行，何时运行以及运行多长实时间，它的基本原则是：最大限度的利用处理器时间。

4.1 多任务

多任务分类：抢占式和非抢占式。Linux中提供了抢占(强行挂起的动作)式的多任务模式。

4.2 Linux 的进程调度

参考链接：

小林coding调度算法

Linux中从2.5开始使用了O(1)内核调度算法。但是该算法对响应时间敏感的程序有一些先天不足，对于服务器友好，但是对于桌面操作系统不行。因此引用了“翻转楼梯最后期限调度算法”(RSDL)。被称为“完全公平调度算法”或者简称(CFS)。

4.3 策略

策略决定调度程序在何时让什么进程运行。

4.3.1 I/O消耗型和处理器消耗型的选择

进程分为I/O消耗型和处理器消耗型，例如GUI是属于I/O密集型，矩阵运算是处理器消耗密集型。

调度策略需要在两个矛盾的目标中间寻求平衡：进程响应迅速（响应时间短）和最大系统利用率（高吞吐量）

4.3.2 进程优先级

Linux 中采用了两种不同的优先级范围：

nice值，范围是-20到+19，默认值为0；nice值越大意味着优先级越低（说明该进程对其他进程更友好）。低nice值会获得更多的处理器时间。Linux系统中，nice值代表时间片的比例，可以通过ps-el查看系统中的进程列表，Mac OS中，nice值代表分配给进程的时间片的绝对值
实时优先级:是可配置的。默认情况下的变化范围是0到99，越高意味着进程优先级越高。可以通过如下命令查看实时优先级：ps -ao state,uid,pid,ppid,rtprio,time,comm;其中(RTPRIO)表示实时优先级。

4.3.3 时间片

Linux默认的时间片是10ms。

4.4 Linux调度算法

4.4.1 调度器类

Linux调度器是以模块方式提供的，这样做的目的是允许不同类型的进程可以有针对性地选择调度算法。这种模块化结构被称为调度器类(scheduler classes)。它允许多种不同的可添加的调度算法并存，调度器代码定义在kernel/sched.c文件中。完全公平调度(CFS)是针对一个普通进程的调度，在Linux中称SCHED_NORMAL(在POSIX中称为SCHED_OTHER)，CFS定义在文件kernel/sched_fair.c中。

Linux内核设计与实现阅读笔记1

2024-06-05
阅读笔记

Linux内核设计与实现阅读笔记1

Linux内核设计与实现(第三版) 学习笔记

第2章从内核出发

2.1 内核源码

2.2 内核源码结构

2.3 编译内核

2.4 内核开发的特点

第3章进程管理

3.1 进程

3.2 进程描述符

3.2.1 分配进程描述符

3.2.2 进程描述符的存放

3.2.3 进程状态

3.2.4 设置进程状态

3.2.5 进程上下文

3.2.6 进程家族树

3.3 进程创建

3.3.1 写拷贝

3.3.2 fork()

3.3.3 vfork()

3.4 线程在Linux中的实现

3.4.1 创建线程

3.4.2 内核线程

3.5 进程终结

3.5.1 删除进程描述符

3.5.2 孤儿进程造成的进退维谷

第四章进程调度

4.1 多任务

4.2 Linux 的进程调度

4.3 策略

4.3.1 I/O消耗型和处理器消耗型的选择

4.3.2 进程优先级

4.3.3 时间片

4.4 Linux调度算法

4.4.1 调度器类

4.4.3 公平调度

参考链接

Linux内核设计与实现阅读笔记1

Linux内核设计与实现(第三版) 学习笔记

第2章 从内核出发

2.1 内核源码

2.2 内核源码结构

2.3 编译内核

2.4 内核开发的特点

第3章 进程管理

3.1 进程

3.2 进程描述符

3.2.1 分配进程描述符

3.2.2 进程描述符的存放

3.2.3 进程状态

3.2.4 设置进程状态

3.2.5 进程上下文

3.2.6 进程家族树

3.3 进程创建

3.3.1 写拷贝

3.3.2 fork()

3.3.3 vfork()

3.4 线程在Linux中的实现

3.4.1 创建线程

3.4.2 内核线程

3.5 进程终结

3.5.1 删除进程描述符

3.5.2 孤儿进程造成的进退维谷

第四章 进程调度

4.1 多任务

4.2 Linux 的进程调度

4.3 策略

4.3.1 I/O消耗型和处理器消耗型的选择

4.3.2 进程优先级

4.3.3 时间片

4.4 Linux调度算法

4.4.1 调度器类

4.4.3 公平调度

参考链接

第2章从内核出发

第3章进程管理

第四章进程调度