Linux Kernel Development

1. Process Management

The Process

Process: program code, open files, pending signals, internal kernel data, processor state, memory address space, memory mapping, threads, data section(global variables). 也就是说，程序本身并不是进程，而是执行的程序，包括了相关的资源。进程的生命周期开始于进程的建立，在Linux中使用系统调用 fork() 复制一个已经存在的进程。调用 fork() 的是父进程，新进程是子进程。因此，fork() 很特殊的一点在于一次调用返回两次，一个在父进程返回，指向子进程的正数ID，一个在子进程返回（没有子进程了），返回0。在Linux内核中，fork() 是通过系统调用 clone() 实现的。最后进程通过系统调用 exit() 退出。

进程存储

The kernel staores the list of processes in s circulalr doubly linked list call the task list. Each element of the list is a process descriptor of the type struct task_struct. 内核中有大量关于这个结构体的操作，使用宏 current 可以快速获得当前进程的指针。

结构体 task_struct 不直接存储在进程栈中，而是将一个结构体 thread_info 存储在栈的底部，这个结构体有一个指针指向当前进程的 tack_struct，

在内核中有很多关于 tack_struct 的操作，都是通过访问栈底这个结构体来访问的，根据栈的大小，可以快速访问到这个位置。

进程状态

进程一共有5个状态:

• TASK_RUNNING：当前进程是正在运行或者正在执行的队列中，这是用户空间进程的唯一状态；
• TASK_INTERRUPTIBLE：当前进程在休眠，等待一些条件退出，当退出后，内核将状态置为TASK_RUNNING;
• TASK_UNINTERRUPTIBLE：和上一个状态相同，除了它得到信号后不会被唤醒变为runnable；
• __TASK_TRACED：The process is being trace by other process, such as debugger.
• _TASK_STOPPED：进程被终止了，不在执行，也不会被执行。
  内核一般使用函数set_current_state(state)来改变进程的状态，这个函数位于源码的include/linux/sched.h中，结构体task_struct也一样。进程的一个重要部分就是来自可执行文件的程序代码，普通进程在用户空间执行，如果执行了系统调用或者抛出异常，进程就会进入内核空间执行。

  进程树

  所有进程都是 init 进程的后代，init 进程的 PID 是 1。内核在 boot 进程的最后一步执行 init 进程。系统中的每个进程都只有唯一的父进程，可以有多个子进程或者没有子进程。task_struct 中有一个指针parent执行父进程的结构体，同时有一系列的children。可以使用current指针获取父进程、子进程

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

对于任何进程来说，一直不断地找自己地爹，最后总能找到 init 进程，此谓之进程祖宗：

struct task_struct *task;
for ( task = current; task != &init_task; task = task->parent);

通过这种方法，一个进程可以找到系统中任何进程，当然更加简单地方法是，由于进程存储在双循环linked list中，一直往前或者往后找，也可以找到全部进程。

创建进程

Unix系统创建进程地方式很特殊，其他地系统一般来说都是相当于用一个进程生产者机制在用户空间中创建一个新的进程，读入一个可执行文件，然后开始执行。Unix系统则将创建进程分为两步：fork() 和 exec()。
fork()：创建一个复制当前进程地子进程，仅仅有PID、PPID(爹地ID)、待定地信号、资源等不同。
exec()：加载新的可执行文件进到内存空间中，然后开始执行。

copy-on-write(COW)

写时复制，如果fork()直接复制父进程的所有资源给子进程，那么会造成时间上的浪费。首先，有些资源事实上是可以共享的；其次，如果子进程马上就要执行新的可执行文件，那所有的复制都浪费了。COW是一种延迟复制机制，父子进程共享一个进程地址空间，而不是马上就复制一份给子进程，等到有数据被写了，复制才会执行，父子进程才会得到一份独享的被写过的资源，一直这样，有被写的数据就才会复制，直到他们之间只共享只读数据。这样就可以预防进程数据根本不被写，共享就可以了，比如fork()之后马上执行exec()，这样父子进程之间没有差别。fork()产生的开销就是复制了一份父进程的页表以及创建了一个结构体task_struct(以后称为task descriptor)。

forking

Linux使用系统调用clone()实现fork()、vfork()、__clone()，clone()调用do_fork()。Forking的大部分工作都是在do_fork()中执行的，而do_fork()中interesting work是由copy_process()完成的。
fork() vfork() -> clone() -> do_fork() -> copy_process()

long do_fork(unsigned long clone_flags,
	      unsigned long stack_start,
	      struct pt_regs *regs,
	      unsigned long stack_size,
	      int __user *parent_tidptr,
	      int __user *child_tidptr)
{
	struct task_struct *p;
	int trace = 0;
	// 为子进程分配一个唯一PID
	struct pid *pid = alloc_pid();
	long nr;

	if (!pid)
		return -EAGAIN;
	nr = pid->nr;
	if (unlikely(current->ptrace)) {
		trace = fork_traceflag (clone_flags);
		if (trace)
			clone_flags |= CLONE_PTRACE;
	}
    
    // 关键工作
	p = copy_process(clone_flags, stack_start, regs, stack_size, parent_tidptr, child_tidptr, pid);
	/*
	 * Do this prior waking up the new thread - the thread pointer
	 * might get invalid after that point, if the thread exits quickly.
	 */
	 // 子进程p
	if (!IS_ERR(p)) {
		struct completion vfork;

		if (clone_flags & CLONE_VFORK) {
			p->vfork_done = &vfork;
			init_completion(&vfork);
		}


static struct task_struct *copy_process(unsigned long clone_flags,
                        unsigned long stack_start,
                        struct pt_reg *regs,
                        unsigned long stack_size,
                        int __user *parent_tidptr,
                        int __user *child_tidptr,
                        struct pid *pid) {
    // 1. 调用 dup_task_struct(), 为新的进程创建一个新的内核栈、结构体 thread_info、task_struct。新的值和当前进程都是一样的（COW），此时，父子进程是一样的。
    struct task_struct *p = NULL;
    ...
    p = dup_task_struct(current);

    // 2. 检查当前用户的进程数量是否已经超过限制
    if (atomic_read(&p->user->processes) >=
			p->signal->rlim[RLIMIT_NPROC].rlim_cur) {
		if (!capable(CAP_SYS_ADMIN) && !capable(CAP_SYS_RESOURCE) &&
		    p->user != current->nsproxy->user_ns->root_user)
			goto bad_fork_free;
	}
	// 3. 设置子进程结构体process descriptor自己的一些成员，设置为初始值，但是大部分的成员还是保持和父进程一致；
	
	// 4. 子进程状态设置为 TASK_UNINTERRUPTIBLE 以确保子进程还没有还是执行；

	// 5. 调用 copy_flags() 更新 task_struct 的 flags 成员，比如PF_SUPERPRIV flag表示这进程不是使用超级用户权限，PF_FORKNOEXEC flag表示这个进程还没有调用exec()。
	copy_flags(clone_flags, p);

    static inline void copy_flags(unsigned long clone_flags, struct task_struct *p)
    {
        unsigned long new_flags = p->flags;

        new_flags &= ~PF_SUPERPRIV;
        new_flags |= PF_FORKNOEXEC;
        if (!(clone_flags & CLONE_PTRACE))
            p->ptrace = 0;
        p->flags = new_flags;
    }

	// 6. 返回子进程指针 p
    total_forks++;
	spin_unlock(&current->sighand->siglock);
	write_unlock_irq(&tasklist_lock);
	proc_fork_connector(p);
	return p;
}

再来看完整的do_fork()函数：

long do_fork(unsigned long clone_flags,
	      unsigned long stack_start,
	      struct pt_regs *regs,
	      unsigned long stack_size,
	      int __user *parent_tidptr,
	      int __user *child_tidptr) {
	struct task_struct *p;
	int trace = 0;
	struct pid *pid = alloc_pid();
	long nr;

	if (!pid)
		return -EAGAIN;
	nr = pid->nr;
	if (unlikely(current->ptrace)) {
		trace = fork_traceflag (clone_flags);
		if (trace)
			clone_flags |= CLONE_PTRACE;
	}

	p = copy_process(clone_flags, stack_start, regs, stack_size, parent_tidptr, child_tidptr, pid);
	/*
	 * Do this prior waking up the new thread - the thread pointer
	 * might get invalid after that point, if the thread exits quickly.
	 */
	if (!IS_ERR(p)) {
		struct completion vfork;

		if (clone_flags & CLONE_VFORK) {
			p->vfork_done = &vfork;
			init_completion(&vfork);
		}

		if ((p->ptrace & PT_PTRACED) || (clone_flags & CLONE_STOPPED)) {
			/*
			 * We'll start up with an immediate SIGSTOP.
			 */
			sigaddset(&p->pending.signal, SIGSTOP);
			set_tsk_thread_flag(p, TIF_SIGPENDING);
		}
        
        // 唤醒子进程
		if (!(clone_flags & CLONE_STOPPED))
			wake_up_new_task(p, clone_flags);
		else
			p->state = TASK_STOPPED;

		if (unlikely (trace)) {
			current->ptrace_message = nr;
			ptrace_notify ((trace << 8) | SIGTRAP);
		}

		if (clone_flags & CLONE_VFORK) {
			freezer_do_not_count();
			wait_for_completion(&vfork);
			freezer_count();
			if (unlikely (current->ptrace & PT_TRACE_VFORK_DONE)) {
				current->ptrace_message = nr;
				ptrace_notify ((PTRACE_EVENT_VFORK_DONE << 8) | SIGTRAP);
			}
		}
	} else {
		free_pid(pid);
		nr = PTR_ERR(p);
	}
	return nr;
}

The Linux Implementation of Threads

Threads: Linux对于线程有特殊的实现，线程在Linux中不过就是一种特殊的进程，两者没有什么区别。线程有独立的program counter，process stack，a set of processor registers。Linux有特殊的线程实现方式，事实上Linux中并没有线程，Linux将所有的线程都都是标标准准的进程。并没有什么另外的类似于 task_struct 之类的线程的结构体，一个线程在Linux中仅仅是一个进程但是和别的进程共享当前的资源，比如内存空间，打开的文件等资源。对内核来说，进程线程没有区别。这和别的系统实现有很大的不同，别的操作系统，线程是一个轻量级的进程，但是在Linux中，线程就是一个进程（这个task_struct就够大的了）。虽然Linux没有真正的线程，这种做法的好处在于，如果有线程的结构，比如一个进程有四个线程，那么task_struct需要四个指针指向他们，而且他们也都需要表示这些共享的资源。但是在Linux中，他们就仅仅是5个不同的进程共享了资源而已。very elegant！

创建线程

因为线程就是进程，线程的创建方式和进程一样，不同的仅仅在于调用clone函数的时候，传入表示要共享的资源的flags。

Process Termination

进程会被终结，内核释放进程的资源，然后通知进程的爹，这个子进程已经死了。一般来说，进程自杀的，也就是自己调用exit()系统调用，可以是显示调用，也可以是编译器在main函数return之后加入一个对exit()的调用。exit()的大部分工作都在kernel/exit.c中的do_exit()中完成。大概完成的工作如下：

fastcall NORET_TYPE void do_exit(long code) {
    // 当前进程
	struct task_struct *tsk = current;

    // 1. 设置flags中的PF_EXITING
	spin_lock_irq(&tsk->pi_lock);
	tsk->flags |= PF_EXITING;
	spin_unlock_irq(&tsk->pi_lock);

    // 2. write out process accounting information 
    // process accounting 是一种安全的奇数，跟踪系统资源
	acct_update_integrals(tsk);
	if (tsk->mm) {
		update_hiwater_rss(tsk->mm);
		update_hiwater_vm(tsk->mm);
	}

    // 3. 调用exit_mm()，释放进程的 mm_struct
    // mm_struct 内存描述符
	exit_mm(tsk);

	// 4. 调用 exit_sem()，进程在等待进程间信号IPC
	// 会在这里出队
    exit_sem(tsk);
    
    // 5. 调用exit_files(), exit_fs(), 减少对文件描述符的引用
    // 如果减到0，文件等对象可以被释放
	exit_sem(tsk);
	__exit_files(tsk);
	__exit_fs(tsk);

	// 6. 调用exit_notify()将自己要死了的信号告诉爹，将儿子们的
	// 的爹设置为其他的吸纳成或者进程, 并将自己的状态在task_struct
	// 中设置为EXIT_ZOMBIE.
	exit_notify(tsk);
	
	// 7. 所有工作完成，将进程状态设置为死了
	tsk->state = TASK_DEAD;
    
    // 8. 很重要的一步，调用schedule()切换到新的进程， 因为当前进程
    // 已经无法被调度了，因此这个调用是这个进程的最后的动作，因此
    // do_exit()永远不会返回
	schedule();
}

在完成do_exit()之后，task_struct结构体还存在于进程双循环链表之中，还要释放掉这个task descriptor。

2. Process Scheduling

进程调度指的是让哪一个进程执行，什么时候执行，执行多久。进程调度器是类似于多任务操作系统Linux的基础，调度器将有限的CPU时间在可执行的进程之间分开。进程调度器通过决定哪个进程要执行让用户觉得有多个CPU在同时工作。

Multitasking

并行parallel，多个处理器同时交错执行程序;
并发concurrently，一个处理器通过交错执行给用户以多个处理器的假象；
Linux系统中，内存中会有很多进程，但是仅有一个是在runnable状态，其他的进程不是被block就是sleep状态，等待一些事件，比如键盘输入，网络数据等等。
多任务操作系统系统有两个流派：

• 抢占式：preemptive multitasking，Linux或者其他的现在操作系统都是抢占式，每个进程的执行时间（timeslice）会被调度器预先设定；
• 非抢占式：cooperative multitasking，每个进程决定自己占用多久的CPU时间直到自己不想用了；

Linux Process Scheduler

kernel version 2.6 以后，调度器又名O(1) scheduler，因为这个调度器表现优秀，能在O(1)时间处理进程调度无论当前有多少进程。

Policy

I/O bound versus CPU bound process

I/O密集型：这种进程花大量时间在提交和等待I/O请求上，运行的时间很少。大部分的GUI应用都是I/O bound的，因为他们要花费大量时间等待用户从键盘或者鼠标输入。
计算密集型：processor-bound process花费大量的时间执行代码，一般都执行到他们被抢占CPU时间，因为不经常会由于I/O请求而被block。比如ssh-keygen和matlab都是计算密集型的进程。
Unix系统通常优先支持processor-bound进程，这样能提高CPU响应时间，而Linux系统目标在于提供更好的交互响应，因此优先支持I/O-bound进程。

Process Priority

一种进程调度算法是基于进程优先级的，一种简单的做法是高优先级先于低优先级执行，同等优先级使用轮转round-robin的方法。在一些系统中，高优先级继承也会获得更长的时间片。Linux实现了两种优先级计算方法：

• nice value：进程的nice值从-20至+19，初始化为0，大的nice值表示低优先级。高优先级有更大几率获得CPU时间。这种方式是Unix系统的标准方法。
• real-time priority：值可以被配置，初始化为0-99的值，与上一种方法相反，高数值表示高优先级。所有的real-time process（实时进程）的优先级都高于普通进程。

Timeslice

太长的时间片导致交互性能差，让系统看起来不一个并发系统，太短的时间片导致更多的时间被花费在进程切换上，增加开销。而I/O bound进程不需要长的时间片，因为他们大部分时间都不是在运行，而process-bound进程需要更长的时间片，因为这样可以保证进程的cache的可用性（cache hot）。在Linux中，CFS scheduler将进程的nice value作为权重，计算改变进程时间片的概率，高nice value更低比例的时间片，而低nice value获得更高比例时间片。
一个文本编辑器和视频编码器怎么分配时间？首先文本编辑器是I/O bound的，视频编码器是process-bound的，但是不能简单认为给更多时间视频编码器，因为文本编辑器需要交互我们希望用户输入的时候能够马上处理，而视频编码器无论什么时候使用CPU都可以只要最后能够完成工作，没有什么交互性。更多的时间给文本编辑器不在于它是计算密集的，而是希望能尽快处理用户输入。

Linux Scheduling Algorighm

2.4以后Linux进程调度器是Completely Fair Scheduler（CFS），定义在 kernel/sched_fair.c 中。
在Unix中，nice value到执行时间的映射看起来很简单，比如最高优先级-19获得的时间片为100ms，最低优先级20获得的时间片为5ms，当目前只有两个最低优先级进程的时候，100ms内就需要多次切换进程。第二个问题是比如两个进程nice value分别是0和1，那么对应的时间片是95ms和100ms（O(1)调度器就这么做的）。这样相近的优先级看起来获得的事件很接近。但是如果另一种请况两个进程的nice value分别是18，19，那么时间片分别是10ms和5ms，这里两个优先级相近的进程，其中一个是另一个的两倍时间！！！因此用优先级映射固定时间片的做法很欠妥当，CFS则是按照优先级给进程分配CUP实际按比例，而不是固定时间片。

Fair Scheduling

CFS要做的是公平、公平、还是他妈的公平！在理想情况下，有n个进程，那么每个进程1/n的CPU时间就最公平了。CFS会为每个进程分配一定的CPU时间，然后round-Robin这些进程，每次取出最远执行的进程，而不是分配固定的时间片，这个时间是计算的。CFS使用nice value作为权重计算继承的CPU时间比例，高值获得低权重，低值获得高权重。

Linux Scheduling Implementation

CFS的实现：

Time Accounting

每一个进程调度器都会计算进程需要运行的时间，Unix系统给进程一个时间片，时间片结束后则进程被抢占。CFS没有时间片的概念，但是同样需要计算时间，CFS使用sched_entity结构体跟踪进程的执行：

struct sched_entity {
	struct load_weight	load;		/* for load-balancing */
	struct rb_node		run_node;
	struct list_head	group_node;
	unsigned int		on_rq;

	u64			exec_start;
	u64			sum_exec_runtime;
	u64			vruntime; // 
	u64			prev_sum_exec_runtime;

	u64			last_wakeup;
	u64			avg_overlap;

	u64			nr_migrations;

	u64			start_runtime;
	u64			avg_wakeup;
};

vruntime用来衡量哪个进程最值得被调度，CFS就绪队列是一颗以vruntime为键值的红黑树，vruntime越小，就越位于红黑树的最左端，CFS每次选择最左端进程。vruntime是通过实际运行时间和权重计算出来的。 设定一个调度周期（sched_latency_ns），目标是让每个进程在这个周期内至少有机会运行一次，换一种说法就是每个进程等待CPU的时间最长不超过这个调度周期；然后根据进程的数量，大家平分这个调度周期内的CPU使用权，由于进程的优先级即nice值不同，分割调度周期的时候要加权；每个进程的累计运行时间保存在自己的vruntime字段里，哪个进程的vruntime最小就获得本轮运行的权利。

Process Selection

进程选择，CFS每次都选择最小的vruntime的进程，选择最小的vruntime进程是如何实现的？vruntime作为RB-tree的键，CFS每次选择树的最左端的节点恰好就是最小的键，就是从根节点一致往左边走。算法很简单：很显然，CFS没有这么笨每次都这么在树上做这个操作，而是将最小节点缓存在rb_leftmost中，如果是nullptr就表明没有可以运行的进程了，CFS转而调度空闲进程（idle process）。

static struct sched_entity *__pick_next_entity(struct cfs_rq *cfs_rq)
{
	struct rb_node *left = cfs_rq->rb_leftmost;

	if (!left)
		return NULL;

	return rb_entry(left, struct sched_entity, run_node);
}

当一个进程被fork()复制出来，或者状态是runnable的，那么就可以加入到RB-tree中，操作红黑树看起来也不是很麻烦，找到正确的位置插入，然后更新leftmost节点缓存。

/*
* 更新时间然后调用函数插入节点
*/
static void enqueue_entity(struct cfs_rq *cfs_rq, struct sched_entity *se, int flags)
{
	if (!(flags & ENQUEUE_WAKEUP) || (flags & ENQUEUE_MIGRATE))
		se->vruntime += cfs_rq->min_vruntime;

	/*
	 * Update run-time statistics of the 'current'.
	 */
	update_curr(cfs_rq);
	account_entity_enqueue(cfs_rq, se);

	if (flags & ENQUEUE_WAKEUP) {
		place_entity(cfs_rq, se, 0);
		enqueue_sleeper(cfs_rq, se);
	}

	update_stats_enqueue(cfs_rq, se);
	check_spread(cfs_rq, se);
	// 插入一个进程se
	if (se != cfs_rq->curr)
		__enqueue_entity(cfs_rq, se);
}

/*
 * Enqueue an entity into the rb-tree:
 */
static void __enqueue_entity(struct cfs_rq *cfs_rq, struct sched_entity *se)
{
	struct rb_node **link = &cfs_rq->tasks_timeline.rb_node;
	struct rb_node *parent = NULL;
	struct sched_entity *entry;
	s64 key = entity_key(cfs_rq, se);
	int leftmost = 1;

	/*
	 * Find the right place in the rbtree:
	 */
	while (*link) {
		parent = *link;
		entry = rb_entry(parent, struct sched_entity, run_node);
		/*
		 * We dont care about collisions. Nodes with
		 * the same key stay together.
		 */
		if (key < entity_key(cfs_rq, entry)) {
			link = &parent->rb_left;
		} else {
		    // 如果往右边走了，那么最小的节点就保持不变，leftmost不用更新
			link = &parent->rb_right;
			leftmost = 0;
		}
		// 一直到link为null
	}
    // 更新leftmost
	if (leftmost)
		cfs_rq->rb_leftmost = &se->run_node;
    
    // 插入节点,插入一个孩子
	rb_link_node(&se->run_node, parent, link);
	// 设置节点的颜色
	rb_insert_color(&se->run_node, &cfs_rq->tasks_timeline);
}

删除节点：当一个进程blocks或者结束了，就可以删除了，这个节点此时肯定是最左边节点。

static void dequeue_entity(struct cfs_rq *cfs_rq, struct sched_entity *se, int sleep)
{
	/*
	 * Update run-time statistics of the 'current'.
	 */
	update_curr(cfs_rq);

	update_stats_dequeue(cfs_rq, se);
	if (sleep) {
#ifdef CONFIG_SCHEDSTATS
		if (entity_is_task(se)) {
			struct task_struct *tsk = task_of(se);

			if (tsk->state & TASK_INTERRUPTIBLE)
				se->sleep_start = rq_of(cfs_rq)->clock;
			if (tsk->state & TASK_UNINTERRUPTIBLE)
				se->block_start = rq_of(cfs_rq)->clock;
		}
#endif
	}

	clear_buddies(cfs_rq, se);

	if (se != cfs_rq->curr)
		__dequeue_entity(cfs_rq, se);
	account_entity_dequeue(cfs_rq, se);
	update_min_vruntime(cfs_rq);

	/*
	 * Normalize the entity after updating the min_vruntime because the
	 * update can refer to the ->curr item and we need to reflect this
	 * movement in our normalized position.
	 */
	if (!sleep)
		se->vruntime -= cfs_rq->min_vruntime;
}


static void __dequeue_entity(struct cfs_rq *cfs_rq, struct sched_entity *se)
{
	if (cfs_rq->rb_leftmost == &se->run_node) {
		struct rb_node *next_node;

        // 最小节点更新为下一个节点
		next_node = rb_next(&se->run_node);
		cfs_rq->rb_leftmost = next_node;
	}

	rb_erase(&se->run_node, &cfs_rq->tasks_timeline);
}

The Scheduler Entry Point

调度器的入口函数：整个调度器主要的入口函数在kernel/sched.c中

/*
 * schedule() is the main scheduler function.
 */
asmlinkage void __sched schedule(void)
{
    ...
    // 主要工作
    next = pick_next_task(rq);
    ...
}

/*
 * Pick up the highest-prio task:
 */
static inline struct task_struct *
pick_next_task(struct rq *rq)
{
	const struct sched_class *class;
	struct task_struct *p;

	/*
	 * Optimization: we know that if all tasks are in
	 * the fair class we can call that function directly:
	 */
	if (likely(rq->nr_running == rq->cfs.nr_running)) {
		p = fair_sched_class.pick_next_task(rq);
		if (likely(p))
			return p;
	}

	class = sched_class_highest;
	for ( ; ; ) {
		p = class->pick_next_task(rq);
		if (p)
			return p;
		/*
		 * Will never be NULL as the idle class always
		 * returns a non-NULL p:
		 */
		class = class->next;
	}
}

Sleeping and Waking Up

blocked(sleeping)是进程的一种不可执行的状态，进程休眠有很多种原因，大部分原因都是在等待事件，比如文件I/O，硬件事件等等。进程在等待事件的时候将自己设置为sleeping状态，然后加入等待队列，从调度的红黑树中移除，然后执行schedule()选择一个新的进程来执行。唤醒进程则相反。

等待队列：
休眠是通过等待队列管理的，等待队列就是一个等待事件的sleeping的进程链表。

唤醒：
尝试唤醒进程，将进程设置为TASK_RUNNING状态，从等待队列中取下，调用enqueue_task()将进程加入调度的红黑树。

Preemption and Context Switching

抢占和上下文切换

进程切换通过kernel/sched.c的context_switch()来实现从一个可执行的进程切换到另一个可执行的进程。

/*
 * context_switch - switch to the new MM and the new
 * thread's register state.
 */
static inline void
context_switch(struct rq *rq, struct task_struct *prev,
	       struct task_struct *next)
{
    // 1. switch(), 从前一个进程的虚拟内存切换到下一个进程
	if (likely(!mm)) {
		next->active_mm = oldmm;
		atomic_inc(&oldmm->mm_count);
		enter_lazy_tlb(oldmm, next);
	} else
		switch_mm(oldmm, mm, next);

	/* Here we just switch the register state and the stack. */
	// 2. 切换到下一个进程
	switch_to(prev, next, prev);

	barrier();
	/*
	 * this_rq must be evaluated again because prev may have moved
	 * CPUs since it called schedule(), thus the 'rq' on its stack
	 * frame will be invalid.
	 */
	finish_task_switch(this_rq(), prev);
}

User Preemption

用户态抢占
当内核从一个中断或者系统调用之后返回到用户空间，调度器需要选择一个进程来执行，也就是说两种请况会导致用户态抢占：

• 从系统调用返回用户空间
• 从中断处理返回用户空间

Kernel Preemption

内核态抢占
在其他的类Unix系统中，不像Linux是完全抢占式的，其他操作系统在执行内核代码的时候会一直执行直到结束，调度器无法在内核代码在运行的时候重新调度，无法抢占。Linux是可以抢占内核的，只要内核在一个可以调度的安全状态。

• 中断处理退出，返回到内核空间之前；
• 内核代码可被抢占；
• 内核的进程显式调用schedule();
• 内核进程进入block状态，导致调用schedule();

Real-Time Scheduling Policies

3. System Calls

内核提供了一组接口给用户空间进程用来和内核交互，这些接口相当于应用程序和内核的信使，应用程序向内核提出要求，内核完成工作，让应用程序无法任意直接做他们像做的事情。

3.1 Conmunicating with the Kernel

System calls 在硬件和用户空间进程之间加入了一层，这起码有2个意图：

1. 给用户空间提供一个抽象的硬件接口，用户进程不用关心硬件类型；
2. 系统调用保证系统的安全和稳定性；

3.2 APIs, POSIX, C library

一般来说，用户程序是面对用户空间实现的API编程的，而不是直接使用系统调用，这些API可以通过多个系统调用实现，或者根本不需要通过系统调用。比如一个printf()的调用：

Linux中的系统调用接口大多都是C library的一部分，对于程序员来说，系统调用是不相关的，程序员只和API打交道，而内核只关注系统调用。

3.3 Syscalls

System calls(syscalls) 提供一个long类型的返回值，负数表示错误，0表示成功返回，系统调用执行很快。

3.4 System call Handler

用户空间应用无法直接执行内核代码，不能直接调用一个内核空间的函数，因为内核在存在于保护的内存中。因此，用户空间程序为了执行系统调用就要有方法通知内核，让系统切换到内核模式。这种通知内核的机制是software interrupt：首先引发一个异常，然后系统切换到内核模式执行异常处理函数（exception handler）。这个异常处理函数事实上正是系统调用处理函数system_call()。x86的系统调用处理函数是系统调用号128，通过指令 int 0x80触发。这个指令将系统切换到内核模式然后执行异常向量（exception vector 128），这个128号异常处理函数正是系统调用处理函数。仅仅进入到内核空间还不足够还需要告诉内核要执行哪个系统调用，x86是通过寄存器eax传递系统调用号的。system_call()首先检查系统调用号的合法性。

3.5 System Call Implementation

系统调用的实现
在Linux中，系统调用应该只能有一个功能，多路复用系统调用（multiplexing syscalls，一个单一的系统调用实现了多个功能，通过flag参数来决定做什么事情）是不被Linux所鼓励的。ioctl()函数就是一种多路复用的函数。系统调用的实现要考虑目光要长远，考虑到这个新的系统调用很长事件稳定使用，其次参数要校验，比如文件句柄、PID等合法性。

3.6 System Call Context

在执行系统调用的过程中，内核是进程的上下文，此时current指针指向调用系统调用的进程。

4. Kernel Data Structure

4.1 Linked Lists

• Singly and Doubly Linked Lists
• Circular Linked Lists
  Linux kernel的实现：
  一般来说，链表的节点都是数据成员，然后加入前向或者后向节点。Linux为了提高代码复用性，定义了一个简单的节点，只包含前后指针：

struct list_head {
	struct list_head *next, *prev;
};

这样看起来没什么用，但是这样一组合便可以 node.list.next 访问前一个节点，说到底是提高代码复用性了。

struct Node {
    int val;
    struct list_head list;
}

在include/linux/list.h中定义了关于链表的数据结构，链表的节点加入、节点删除、节点替换、遍历节点等操作。

4.2 Queues

Queues数据结构、以及相关操作定义在kernel/kfifo.c中。内核中的队列叫kfifo，入队操作(in)，出队操作(out)。kfifo对象维护两个变量in offset和out offset用来表示下一次入队出队的位置。

struct kfifo {
	unsigned char *buffer;	/* the buffer holding the data */
	unsigned int size;	/* the size of the allocated buffer */
	unsigned int in;	/* data is added at offset (in % size) */
	unsigned int out;	/* data is extracted from off. (out % size) */
};

// 队列初始化
static void _kfifo_init(struct kfifo *fifo, void *buffer,
		unsigned int size)
{
	fifo->buffer = buffer;
	fifo->size = size;

	kfifo_reset(fifo);
}

// 入队
unsigned int kfifo_in(struct kfifo *fifo, const void *from,
				unsigned int len)
{
	len = min(kfifo_avail(fifo), len);

	__kfifo_in_data(fifo, from, len, 0);
	__kfifo_add_in(fifo, len);
	return len;
}

// 出队
unsigned int kfifo_out(struct kfifo *fifo, void *to, unsigned int len)
{
	len = min(kfifo_len(fifo), len);

	__kfifo_out_data(fifo, to, len, 0);
	__kfifo_add_out(fifo, len);

	return len;
}

4.3 Maps

4.4 Binary Trees

• Binary Search Trees
• Self-Balancing Binary Trees
  • Red-Black Trees
    • All nodes are either red or black
    • Leaf nodes are black
    • Leaf nodes do not contain data
    • All non-leaf nodes have two children
    • If a node if red, both of its children are black
    • 对每个节点，从该节点到其所有后代叶结点的简单路径上，均包含相同数目的黑色节点

Linux的红黑树定义在linux/rbtree.h中，实现在kernel/rbtree.c中。看起来，rb_node没有定义节点的颜色，这里的巧妙之处在于rb_parent_color是unsigned long类型，在32位机器上要在64位的long上左对齐，低位肯定都是0，这里就是使用低1位作为颜色表示。在这种技巧下，下面几个宏定义就很清楚了。

struct rb_node
{
	unsigned long  rb_parent_color;
#define	RB_RED		0
#define	RB_BLACK	1
	struct rb_node *rb_right;
	struct rb_node *rb_left;
} __attribute__((aligned(sizeof(long))));
    /* The alignment might seem pointless, but allegedly CRIS needs it */

struct rb_root
{
	struct rb_node *rb_node;
};

                        // 低两位清零
#define rb_parent(r)   ((struct rb_node *)((r)->rb_parent_color & ~3))
                        // 取颜色
#define rb_color(r)   ((r)->rb_parent_color & 1)
                        // 判断颜色
#define rb_is_red(r)   (!rb_color(r))
#define rb_is_black(r) rb_color(r)
                        // 设置颜色
#define rb_set_red(r)  do { (r)->rb_parent_color &= ~1; } while (0)
#define rb_set_black(r)  do { (r)->rb_parent_color |= 1; } while (0)

static inline void rb_set_parent(struct rb_node *rb, struct rb_node *p)
{
	rb->rb_parent_color = (rb->rb_parent_color & 3) | (unsigned long)p;
}
static inline void rb_set_color(struct rb_node *rb, int color)
{
	rb->rb_parent_color = (rb->rb_parent_color & ~1) | color;
}

5. Interrupts and Interrupt Handlers

操作系统的核心任务之一就是管理计算机的硬件，而CPU速度比硬件快很多，如果CPU处理一个硬件请求之后再等待硬件响应是很不明智地，因此处理器要在这段时间里去做其他事情，等硬件做完事情有响应了再通知处理器。总而言之、言而总之尽量别闲着处理器，累死处理器。这种通知就是interrupt，处理interrupt地就是interrupt handlers。

5.1 Interrupts

硬件的中断关于处理器时钟是异步的，不能在任何事件都产生一个硬件中断，这样才可以随机中断内核处理这个硬件中断。

5.2 Interrupt Handlers

响应特定中断的函数时Interrupt Handler，或者interrupt service routine。interrupt handler和其他函数的区别在于它运行时特定的context，interrupt context或者叫atomic context，正是因为运行在这种context中的代码无法被block。

5.3 Top Halves Versus Bottom Halves

一般来说，我们希望中断处理程序能够执行的快，因为中断正是中断了别的代码的执行，我们希望能快点执行完然后返回，但是中断处理程序又有很多工作要做，难以做到快速完成，这两个显然是冲突的。因此中断处理程序被分为两个部分，top half 和 bottom half。top half仅仅负责处理那些time_critical的工作，比如接收中断信号，重新设置硬件等。bottom half则负责处理 time convenient 的工作，将来再执行。比如一个网卡从网络中接收到数据，网卡向内核发起一个中断，而且希望能够被快速处理完以便继续接受数据以免time out。内核执行网卡注册的相应的中断，将数据从网卡复制到内存中，然后重设网卡可以重新接收数据。这些工作是十分重要而且time-critical，网卡的内存很小因此也要尽快复制到计算机内存。做完这些工作，内核何以返回了。top half完成。接下来不那么重要的工作可以中断处理程序结束后慢慢做，比如处理数据，这是bottom half。

5.4 Registering an Interrupt Handler

每个硬件都有对应的驱动程序driver，硬件需要使用中断，则driver必须注册中断处理register a interrupt handler。

5.5 Interrupt Context

process context 是进程执行的后半部分，也就是进程进入内核模式执行系统调用或者内核线程，process context和进程绑定，此时的current指针指向在执行的进程，因此可以sleep，之后轮到了再执行。
interrupt context 不和进程绑定，current指针是无关的，不用返回到某个进程，因此interrupt context无法sleep(因为没有和进程绑定，连task_struct都没有)，因此interrupt handler调用的函数不能是那些可以sleep或者block的函数。

6. Bottom Halves and Deferrring Work