第一次作业：关于Linux 2.6.20进程模型和O(1)调度器算法的分析

1.写在最前

本文基于 Linux Kernel 2.6.20 的源代码，分析的是本版本linux的进程模型和其O(1) 调度器的基本算法。
源码浏览地址：
https://elixir.bootlin.com/linux/v2.6.20/source/kernel

2.关于进程

2.1进程的定义

从不同的角度，进程可以有不同的定义，比较经典的定义有：

1） 进程是程序的一次执行过程

2） 进程是一个程序及其数据在处理器上顺序执行时所发生的活动。

3） 进程是具有独立功能的程序在一个数据集合上运行的过程，他是系统进行资源分配和调度的一个独立单位。

在引入了进程实体的概念后，我们可以把传统的操作系统中的进程定义为：

“进程是进程实体的运行过程，是系统进行资源分配和调度的一个独立单位”。

2.2看一眼进程

我们可以使用$ps查询正在运行的进程，
比如$ps -eo pid,comm,cmd，
下图为执行结果（部分）:

(-e表示列出全部进程，-o pid,comm,cmd表示我们需要PID，COMMAND，CMD信息)

3.关于进程的组织

linux将进程的列表存放在叫做任务队列的双向循环链表中。
链表中的每一项都是类型为task_struct，称为进程描述符，该结构定义在<linux/sched.h>文件中。
进程描述符中包含一个具体进程的所有信息。
其包含的数据能完整地描述一个正在执行的程序：进程标识符（PID），进程状态，优先级等其他所有信息。

3.1进程标识符

pid_t pid;

*来源：https://elixir.bootlin.com/linux/v2.6.20/source/include/linux/sched.h#L855

PID(process IDentity)是一个整数，每一个进程都有一个唯一的PID来代表自己的身份，进程也可以根据PID来识别其他的进程。
在CONFIG_BASE_SMALL配置为0的情况下，PID的取值范围是0到32767，即系统中的进程数最大为32768个，已可满足普通用户的日常使用。

#define PID_MAX_DEFAULT (CONFIG_BASE_SMALL ? 0x1000 : 0x8000)

*来源：https://elixir.bootlin.com/linux/v2.6.20/source/include/linux/threads.h#L27

3.2进程状态

volatile long state; /* -1 unrunnable, 0 runnable, >0 stopped */

*来源：https://elixir.bootlin.com/linux/v2.6.20/source/include/linux/sched.h#L802

state的可能取值有

#define TASK_RUNNING        0
#define TASK_INTERRUPTIBLE  1
#define TASK_UNINTERRUPTIBLE    2
#define TASK_STOPPED        4
#define TASK_TRACED     8
/* in tsk->exit_state */
#define EXIT_ZOMBIE     16
#define EXIT_DEAD       32
/* in tsk->state again */
#define TASK_NONINTERACTIVE 64
#define TASK_DEAD       128

*来源：https://elixir.bootlin.com/linux/v2.6.20/source/include/linux/sched.h#L143

接下来对几个常用状态进行简单的分析。

状态	描述
TASK_RUNNING	进程正在执行 或者 进程正在准备执行。
TASK_INTERRUPTIBLE	进程由于等待某些条件处于阻塞（挂起的状态），一旦等待的条件成立，便会从该状态变成TASK_RUNNING。这些条件主要包括：硬中断、资源、某些信号等等。
TASK_UNINTERRUPTIBLE	与TASK_INTERRUPTIBLE类似。但我们传递任何信号都无法唤醒它，只有当它所等待的资源可用时，它才被唤醒。
TASK_STOPPED	进程停止执行。当进程接收到SIGSTOP、SIGTTIN、SIGTSTP或者SIGTTOU信号等之后就会进入该状态。
TASK_TRACED	进程被debugger等进程监视。进程执行被调试程序所停止，当一个进程被另外的进程所监视，每一个信号都会让进城进入该状态。
EXIT_ZOMBIE	进程的执行被终止，但其父进程还未使用wait()等系统调用来获取它的终止信息，此时进程成为僵尸进程。
EXIT_DEAD	进程被“杀死”，也就是进程的最终状态。

而进程状态之间的转换，大致如下图。

3.3优先级

int prio, static_prio, normal_prio;

*来源：https://elixir.bootlin.com/linux/v2.6.20/source/include/linux/sched.h#L815

简单分析
字段|描述
---|---
prio|保存动态优先级
static_prio|保存静态优先级
normal_prio|它的值取决于优先策略和静态优先级

4.关于O(1)调度算法

4.1 调度器与进程

调度器：
通常来说，操作系统是应用程序和可用资源之间的媒介。

典型的资源有内存和物理设备。

CPU也可以认为是一个资源，调度器可以临时分配一个任务在上面执行（单位是时间片）。调度器使得我们同时执行多个程序成为可能，因此可以与具有各种需求的用户共享CPU。所以，如何高效地分配CPU时间片，是调度器 的重要目标。

活动进程和过期进程:
调度器为每一个CPU维护了两个进程队列数组：active数组和expire数组。

active进程: 那些还没有用完时间片的进程
expire进程: 那些已经用完时间片的进程

调度程序的工作就是在活动进程集合中选取一个最佳优先级的进程,如果该进程时间片恰好用完,就将该进程放入过期进程集合中.

4.2 满足O(1)的数据结构？

通过在数据结构课上的知识，大多数算法的时间复杂度在O(log N) 基本上就是最好的结果，那么2.6 的 O(1) 调度算法是怎么做到的？

在回答这个问题之前，我们先回顾一下数据结构的四种基本操作以及其时间复杂度：

• access：随机访问。array 是唯一满足 O(1) 随机访问的数据结构。
• search：搜索。hash table 是 O(1) 时间复杂度的，但最坏情况下是 O(N) 的。大部分 tree（b-tree / red-black tree）平均情况和最坏情况都是 O(log N)。
• insert/deletion：插入和删除。linked list，stack，queue 在平均和最坏情况下都是 O(1)。

综上，若想达成 O(1) scheduler 的目标，操作只能包含纯粹的 access，insert 和 deletion，不能有 search。

此外，对于 scheduler，我们应该尽量要选择平均情况和最坏情况表现一致的算法。如果平均情况是 O(1)，最坏情况是 O(n)，那么这个 scheduler 会给系统带来很大的不确定性

所以我们的选择并不多。
对于access 只能用 array，
对于insert / deletion 只能用 linked list / queue / stack。

4.3 算法思路

我们先看一张大神给出的正确答案。

在linux中一共有140 种不同的优先级，所以我们就用长度为 140 的 array 去记录优先级。在每个优先级下使用 FIFO queue 来管理该优先级下的所有 process。新来的插到队尾，先进先出。此时，insert / deletion 都是 O(1)。
但，应该如何找到当前最高优先级下的process？若从优先级 0 开始遍历，算法显然不是O(1)。在 2.6 scheduler 里采用 bitarray，为每种优先级分配一个 bit，若该优先级队列下有 process，那么对相应的 bit 染色，置为 1，否则置为 0。

现在，问题简化成寻找一个 bitarray 中最高位是 1 的 bit（left-most bit）。

4.4 重要数据结构

struct runqueue（运行队列）：每个cpu都有一个运行队列

struct rq {
    spinlock_t lock;
    unsigned long nr_running;
    unsigned long raw_weighted_load;
    unsigned long cpu_load[3];
    unsigned long long nr_switches;
    unsigned long nr_uninterruptible;
    unsigned long expired_timestamp;
    /* Cached timestamp set by update_cpu_clock() */
    unsigned long long most_recent_timestamp;
    struct task_struct *curr, *idle;
    unsigned long next_balance;
    struct mm_struct *prev_mm;
    struct prio_array *active, *expired, arrays[2];
    int best_expired_prio;
    atomic_t nr_iowait;
    ...
    }

*来源：https://elixir.bootlin.com/linux/v2.6.20/source/kernel/sched.c#L205
其中最最重要的部分便是prio_array。
prio_array（优先级数组）
O(1)算法的核心数据结构即为prio_array结构体。

struct prio_array {
    unsigned int nr_active;
    DECLARE_BITMAP(bitmap, MAX_PRIO+1); /* include 1 bit for delimiter */
    struct list_head queue[MAX_PRIO];
};

*来源：https://elixir.bootlin.com/linux/v2.6.20/source/kernel/sched.c#L192

其中

• bitmap：优先级位图，它使用一个位（bit）来代表一个优先级。
• queue：表示进程动态优先级的数组，它包含了每一种优先级进程所形成的链表。

4.5 O(1)调度算法的实现

schedule()是实现进程调度的主要函数，并且负责完成进程切换工作，其用于确定最高优先级进程的代码非常快捷高效。它在kernel/sched.c中的定义如下

asmlinkage void __sched schedule(void)
{
    struct task_struct *prev, *next;
    struct prio_array *array;
    struct list_head *queue;
    unsigned long long now;
    unsigned long run_time;
    int cpu, idx, new_prio;
    long *switch_count;
    struct rq *rq;
    ...
}

*来源:https://elixir.bootlin.com/linux/v2.6.20/source/kernel/sched.c#L3412
其中，选择候选进程的关键代码为：

    idx = sched_find_first_bit(array->bitmap);
    queue = array->queue + idx;
    next = list_entry(queue->next, struct task_struct, run_list);

*来源:https://elixir.bootlin.com/linux/v2.6.20/source/kernel/sched.c#L3509

例如：在queue[i]中，存放的计时优先级为i的进程队列的链表头。而bitmap是用来作为进程队列queue的索引位图。
bitmap的每一位都与queue[i]对应。当queue[i]的进程队列不为空时，bitmap的对应位就为1，否则为0。
现在只需要使用汇编指令按照进程优先级从高到底的方向找到第一个为1的位置idx，idx就是当前运行队列中最高的优先级数（函数sched_find_first_bit()便是用来完成这一功能）。
那么，queue[idx]->next便是我们要找的候选进程。
当active数组中的所有进程都被移到expire数组中后，调度器交换active数组和expire数组。
当进程被移入expire数组时，调度器会重置其时间片，因此新的active数组又恢复了初始情况，而expire数组为空，从而开始新的一轮调度。

4.6 更多细节

除了选取最高优先级进程外，O(1)算法还有其他许多的细节，比如进程动态优先级的计算，调度与抢占时机，由于个人水平原因，无法一一阐述。

5.感受与总结

通过查阅资料我得知在linux2.4版本时，2.4的O(n)scheduler早已被诟病已久。
而在划时代的2.6版本中 O(1)scheduler的出现想必一定让当时的开发者兴奋不已。虽然如今的linux所使用的是更加强调公平性的 CFS（Completely Fair Scheduler），但它依旧用简单的算法和独特的设计取得了自己的地位并且影响更多的开发者。无论任何调度器算法都还无法满足所有应用的需要，CFS也有一些负面的测试报告。相信随着Linux的不断发展，更多开发者的不懈努力，还会出现更好的调度算法。

6.参考资料

1. https://wenku.baidu.com/view/c14310d4b9f3f90f76c61b41.html
2. https://blog.csdn.net/fangjian1204/article/details/39736725
3. http://edsionte.com/techblog/archives/2851
4. http://abcdxyzk.github.io/blog/2015/01/22/kernel-sched-n1/
5. https://www.ibm.com/developerworks/cn/linux/l-cn-scheduler/