一、linux内核

系统调用接口

SCI 层提供了某些机制执行从用户空间到内核的函数调用。SCI 实际上是一个非常有用的函数调用多路复用和多路分解服务。在 ./linux/kernel 中您可以找到 SCI 的实现，并在 ./linux/arch 中找到依赖于体系结构的部分。

进程管理

进程管理的重点是进程的执行。在内核中，这些进程称为线程，代表了单独的处理器虚拟化（线程代码、数据、堆栈和 CPU寄存器）。在用户空间，通常使用进程 这个术语，不过 Linux 实现并没有区分这两个概念（进程和线程）。内核通过 SCI 提供了一个应用程序编程（API）来创建一个新进程（fork、exec 或 Portable Operating System Interface [POSⅨ] 函数），停止进程（kill、exit），并在它们之间进行通信和同步（signal 或者 POSⅨ 机制）。 进程管理还包括处理活动进程之间共享 CPU 的需求。内核实现了一种新型的调度算法，不管有多少个线程在竞争 CPU，这种算法都可以在固定时间内进行操作。这种算法就称为 O⑴ 调度程序，这个名字就表示它调度多个线程所使用的时间和调度一个线程所使用的时间是相同的。O⑴ 调度程序也可以支持多处理器（称为对称多处理器或 SMP）。您可以在 ./linux/kernel 中找到进程管理的源代码，在 ./linux/arch 中可以找到依赖于体系结构的源代码。

内存管理

内核所管理的另外一个重要资源是内存。Linux 包括了管理可用内存的方式，以及物理和虚拟映射所使用的硬件机制。不过内存管理，要管理的可不止 4KB缓冲区。Linux 提供了对 4KB缓冲区的抽象，例如 slab 分配器。这种内存管理模式使用 4KB缓冲区为基数，然后从中分配结构，并跟踪内存页使用情况，比如哪些内存页是满的，哪些页面没有完全使用，哪些页面为空。这样就允许该模式根据系统需要来动态调整内存使用。

 

 

为了支持多个用户使用内存，有时会出现可用内存被消耗光的情况。由于这个原因，页面可以移出内存并放入磁盘中。这个过程称为交换，因为页面会被从内存交换到硬盘上。内存管理的源代码可以在 ./linux/mm 中找到。

虚拟文件系统

虚拟文件系统（VFS）是 Linux 内核中非常有用的一个方面，因为它为文件系统提供了一个通用的接口抽象。VFS 在 SCI 和内核所支持的文件系统之间提供了一个交换层。 VFS 在用户和文件系统之间提供了一个交换层 在 VFS 上面，是对诸如 open、close、read 和 write 之类的函数的一个通用 API 抽象。在 VFS 下面是文件系统抽象，它定义了上层函数的实现方式。它们是给定文件系统（超过 50 个）的插件。文件系统的源代码可以在 ./linux/fs 中找到。 文件系统层之下是缓冲区缓存，它为文件系统层提供了一个通用函数集（与具体文件系统无关）。这个缓存层通过将数据保留一段时间（或者随即预先读取数据以便在需要是就可用）优化了对物理设备的访问。缓冲区缓存之下是设备驱动程序，它实现了特定物理设备的接口。

二、进程的转换

(1)运行状态（TASK_RUNNING）
当进程正在被CPU执行，或已经准备就绪随时可由调度程序执行，则称该进程为处于运行状态（running）。进程可以在内核态运行，也可以在用户态运行。当系统资源已经可用时，进程就被唤醒而进入准备运行状态，该状态称为就绪态。这些状态（图中中间一列）在内核中表示方法相同，都被成为处于TASK_RUNNING状态。

(2)可中断睡眠状态（TASK_INTERRUPTIBLE）
当进程处于可中断等待状态时，系统不会调度该进程执行。当系统产生一个中断或者释放了进程正在等待的资源，或者进程收到一个信号，都可以唤醒进程转换到就绪状态（运行状态）。

(3)不可中断睡眠状态（TASK_UNINTERRUPTIBLE）
与可中断睡眠状态类似。但处于该状态的进程只有被使用wake_up()函数明确唤醒时才能转换到可运行的就绪状态。

(4)暂停状态（TASK_STOPPED）
当进程收到信号SIGSTOP、SIGTSTP、SIGTTIN或SIGTTOU时就会进入暂停状态。可向其发送SIGCONT信号让进程转换到可运行状态。在Linux 0.11中，还未实现对该状态的转换处理。处于该状态的进程将被作为进程终止来处理。

(5)僵死状态（TASK_ZOMBIE）
当进程已停止运行，但其父进程还没有询问其状态时，则称该进程处于僵死状态。
当一个进程的运行时间片用完，系统就会使用调度程序强制切换到其它的进程去执行。另外，如果进程在内核态执行时需要等待系统的某个资源，此时该进程就会调用sleep_on()或sleep_on_interruptible()自愿地放弃CPU的使用权，而让调度程序去执行其它进程。进程则进入睡眠状态（TASK_UNINTERRUPTIBLE或TASK_INTERRUPTIBLE）。
只有当进程从“内核运行态”转移到“睡眠状态”时，内核才会进行进程切换操作。在内核态下运行的进程不能被其它进程抢占，而且一个进程不能改变另一个进程的状态。为了避免进程切换时造成内核数据错误，内核在执行临界区代码时会禁止一切中断。

 

 

 

三、进程的调度

 

　　Linux O(1)调度器(O(1) scheduler) 是历史上一个流行的Linux系统调度程序。命名为这个名字是因为它能够在常数时间内执行任务调度，例如从执行队列中选择一个任务或将一个任务加入执行队列，这与系统中的任务总数有关。

　（1） O(1)调度器

　　在O(1)调度中，要问最重要的数据结构是运行队列。运行队列描绘了进程队列的结构，在内核源码中用runqueue结构体表示。

struct runqueue 
{   unsigned long nr_running; 
    task_t *curr;
    prio_array_t *active,*expired,arrays[2]; 
};

　（2）优先级数组

　　O(1)算法的另一个核心数据结构即为prio_array结构体。该结构体中有一个用来表示进程动态优先级的数组queue，它包含了每一种优先级进程所形成的链表。

#define
 MAX_USER_RT_PRIO        100
#define
 MAX_RT_PRIO             MAX_USER_RT_PRIO
#define
 MAX_PRIO                (MAX_RT_PRIO + 40)
typedef struct prio_array
 prio_array_t;
struct prio_array
 {
      unsigned int nr_active;
      unsigned long bitmap[BITMAP_SIZE];
      struct list_head
 queue[MAX_PRIO];
};

　（3）静态优先级和动态优先级

　　进程有两个优先级,一个是静态优先级,一个是动态优先级.静态优先级是用来计算进程运行的时间片长度的,动态优先级是在调度器进行调度时用到的,调度器每次都选取动态优先级最高的进程运行.

静态优先级的计算:
nice值和静态优先级之间的关系是：静态优先级=100+nice+20
而nice值的范围是-20～19，所以普通进程的静态优先级的范围是100～139

动态优先级的计算:
动态优先级=max(100 , min(静态优先级 – bonus + 5 , 139))

　（4）时间片

　　O(1)算法采用过期进程数组和活跃进程数组解决以往调度算法所带来的O(n)复杂度问题。过期数组中的进程都已经用完了时间片，而活跃数组的进程还拥有时间片。当一个进程用完自己的时间片后，它就被移动到过期进程数组中，同时这个过期进程在被移动之前就已经计算好了新的时间片。可以看到O(1)调度算法是采用分散计算时间片的方法，并不像以往算法中集中为所有可运行进程重新计算时间片。当活跃进程数组中没有任何进程时，说明此时所有可运行的进程都用完了自己的时间片。那么此时只需要交换一下两个数组即可将过期进程切换为活跃进程，进而继续被调度程序所调度。两个数组之间的切换其实就是指针之间的交换，因此花费的时间是恒定的。

struct prop_array *array = rq->active;
if (array->nr_active != 0) {
    rq->active = rq->expired;
    rq->expired = array;
}

　　上面的代码说明了两个数组之间的交换，通过分散计算时间片、交换过期和活跃两个进程集合的方法可以使得O(1)算法在恒定的时间内为每个进程重新计算好时间片。

进程运行的时间片长度的计算
静态优先级<120，基本时间片=max((140-静态优先级)*20, MIN_TIMESLICE)
静态优先级>=120，基本时间片=max((140-静态优先级)*5, MIN_TIMESLICE)

　（5）调度算法

在每次进程切换时，内核依次扫描就绪队列上的每一个进程，计算每个进程的优先级，再选择出优先级最高的进程来运行；尽管这个算法理解简单，但是它花费在选择优先级最高进程上的时间却不容忽视。系统中可运行的进程越多，花费的时间就越大，时间复杂度为O(n)。

伪代码：

for (系统中的每个进程){

　　　　重新计算时间片;

　　　　重新计算优先级;

　　}

 

四、课后反思

课上介绍了很多深入源码的分析，但是仅仅课堂上时间还不能完全消化吸收，只能有如上浅显的理解。在考试之前一定要对课程进行更加深入的复习。总体来说，老师辛苦备课和讲解，通过课堂学习了操作系统的基本架构思想，也对源码实现有了更深入认识，收获颇丰。