第一次作业：Linux深入源码分析进程模型

前言

本文为操作系统课程作业，对Linux源码进行进程模型分析。

操作系统中最核心的概念就是进程：这是对正在运行程序的一个抽象。操作系统的其他所有内容都是围绕着进程的概念展开的，因此透彻地理解进程对学习操作系统是非常重要的。

源码基于linux-2.6.10。下载地址：https://mirrors.edge.kernel.org/pub/linux/kernel/v2.6/linux-2.6.10.tar.bz2

正文

1、进程的定义

　　Process-a program in execution.（执行中的程序）

　　　　进程（Process）是计算机中的程序关于某数据集合上的一次运行活动，是系统进行资源分配和调度的基本单位，是操作系统结构的基础。在早期面向进程设计的计算机结构中，进程是程序的基本执行实体；在当代面向线程设计的计算机结构中，进程是线程的容器。程序是指令、数据及其组织形式的描述，进程是程序的实体。

　　　　进程是一个动态的概念，包含了三个维度：

这个进程在执行的程序
这个进程在处理的数据
这个进程处于的运行状态

　　　　在Linux下可以使用ps命令查看进程。

第一次作业：Linux深入源码分析进程模型

　　　　在内核中由名为task_struct（/include/linux/sched.h）的结构体表示，一个非常大的数据结构，也就是我们常说的PCB(Process Control Block)，包含所有表示此进程所必需的数据。

　　　　那接下来我们由PCB开始进入源码，更深入地理解进程。

2.从PCB中看进程的组织

　　　2.1进程队列

　　　组织进程首先要给进程先定好数据结构，就如同我们使用变量前先定义数据类型。

　　　　struct task_struct *next_task,*prev_task;

　　　进程队列是一个双向链表。链表中的每一项都是task_struct类型，并通过指针next_task和pres_task连接前后的进程，使得所有进程连接成一个双向链表。所有的进程会加入到该双向列表内，因此可以通过这个变量访问当前系统内的所有进程。

第一次作业：Linux深入源码分析进程模型

　　　2.2PID

　　　　每一个进程都通过一个唯一的进程标识值（process identification value），也就是PID，每创建一个新的线程时会赋予一个新的PID来标识一个唯一的进程。在task_struct中pid是如下表示：

    pid_t pid;

　　　　我们都知道pid实际上是一个整数类型数据，这里却是一个pid_t类型，那进一步查看pid_t的定义（在visual sutdio下按住ctrl后点击pid_t），进入types.h看到pid_t的定义：

　　typedef __kernel_pid_t        pid_t;

　　　pid_t实际上是__kernel_pid_t的typeof定义类型，在posix_types.h继续查看__kernel_pid_t的定义：

　　　typedef int             __kernel_pid_t;

　　　　pid实际上就是int类型。

　　　　2.3进程的状态

　　　　2.3.1进程创建

　　　　　　一个进程是在是在创建它的时刻开始存活，在Linux系统中通常是调用fork()系统的结果，该系统调用是通过复制一个现有进程来创建一个全新的进程，调用fork()的进程称为新的进程的父进程struct task_struct *parent;，新的进程为子进程struct list_head children; ，fork()系统调用从内核返回两次：一次回到父进程，另一次回到新建的子进程。

　　　　2.3.1STATE　

　　　　进程的当前状态在PCB中定义为：

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

　　　　标志值的取值不同代表不同的状态：

-1 ，不可执行
0 ，可执行
>0，多种暂停状态

　　　　代码中包含对不同值的不同定义：

#define TASK_RUNNING        0
#define TASK_INTERRUPTIBLE    1
#define TASK_UNINTERRUPTIBLE    2
#define TASK_STOPPED        4
#define TASK_TRACED        8
#define EXIT_ZOMBIE        16
#define EXIT_DEAD        32

　　以下是查阅资料对每个不同状态的说明：

TASK_RUNNING：进程是可执行的；它或者正在执行，或者在运行队列中等待执行。这是进程在用户空间中执行唯一可能的状态；也可以应用到内核空间中长在执行的进程。
TASK_INTERRUPTIBLE：进程正在睡眠（也就是说它被阻塞），等待某些条件的达成。一旦这些条件达成，内核就会把进程状态设置为运行。处于此状态的进程也会因为接收到信号而提前被唤醒并投入运行。
TASK_UNINTERRUPTIBLE：除了不会因为接收到信号而被唤醒从而投入运行外，这个状态与可打断状态相同。这个状态通常在进程必须在等待时不受干扰或等待事件很快就会发生时出现。由于处于此状态的任务对信号不作响应，所以较之可中断状态，使用得较少。
TASK_STOPPED：进程停止执行；进程没有投入运行也不能投入运行。通常这种状态发生在接收到SIGSTOP、SIGTSTP、SIGTTIN、SIGTTOU等信号的时候。此外，在调试期间接收到任何信号，都会使进程进入这种状态。
TASK_ZOMBIE：该进程已经结束了，但是其父进程还没有调用wait4()系统调用。为了父进程能够获知它的消息，子进程的进程描述符仍然被保留着。一旦父进程调用了wait4()，进程描述符就会被释放。
TASK_TRACED：该进程正在被其他进程追踪，例如通过ptrace对调试程序进行跟踪。
EXIT_ZOMBIE：进程已终止，它正等待其父进程手机关于它的一些统计信息。
EXIT_DEAD：该进程正从系统中删除。

　　　　2.3.2进程状态的转换

　　图片引用自《Linux内核设计与实现thrid edition》　　　

　　　　2.3.3FALG　

　　　　　　FALG也是进程状态字的一个标志，例如创建进程时需要载入程序代码，但是磁盘不处于空闲状态，需要等待磁盘，处于一种在创建而又未创建完毕的状态，而上面的state不能表示这以一时期的状态，因此进程又加入了一个状态字FALG来表示这些其他的状态。

#define PF_ALIGNWARN    0x00000001    /* Print alignment warning msgs */
                    /* Not implemented yet, only for 486*/
#define PF_STARTING    0x00000002    /* being created */
#define PF_EXITING    0x00000004    /* getting shut down */
#define PF_DEAD        0x00000008    /* Dead */
#define PF_FORKNOEXEC    0x00000040    /* forked but didn't exec */
#define PF_SUPERPRIV    0x00000100    /* used super-user privileges */
#define PF_DUMPCORE    0x00000200    /* dumped core */
#define PF_SIGNALED    0x00000400    /* killed by a signal */
#define PF_MEMALLOC    0x00000800    /* Allocating memory */
#define PF_MEMDIE    0x00001000    /* Killed for out-of-memory */
#define PF_FLUSHER    0x00002000    /* responsible for disk writeback */
...

3.进程调度

　3.1调度方式

　　　首先对于Linux系统地调度方式是抢占式的，进程无论处于用户态或内核态，都有可能被抢占。

　　3.2调度算法

　　　在task_struct中与与进程调度相关的变量有：

    unsigned long policy;

　　　　该变量代表了在进程调度时使用的调度策略，在同一个文件中有变量值的定义：

/*
 * Scheduling policies
 */
#define SCHED_NORMAL        0
#define SCHED_FIFO        1
#define SCHED_RR        2

符号变量	意义
SCHED_NORMAL	普通进程的时间片轮转算法
SCHED_FIFO	实时进程的先进先出算法
SCHED_RR	实时进程的时间片轮转算法

　　　　接下来我们通过kernal/sched.c深入了解调度程序的源代码！

　　3.3Linux O(1)进程调度算法

　　　Linux2.6.10内核O(1)调度算法是抢占的、基于优先级的算法。进程设置140个优先级，实时进程优先级为0-99，普通进程优先级100-139的数，这两个范围印射到全局优先级，其中数值越小表明优先级越高，0为最高优先级，139为最低优先级。

　　　优先级分为静态优先级和动态优先级。调度程序根据动态优先级来选择新进程运行。静态优先级本质上决定了进程的基本时间片，即每次系统分配给进程的时间片长度。静态优先级和时间片的关系用下列公式确定：

　　　　base time quantum(ms):

　(140-static_proiroty) * 20 if static_priority<120
(140-static_priority) * 5 if static_priority>=120

　　　3.3.1运行队列

　　　调度程序中最基本的数据结构是运行队列(runqueue)。运行队列是给定处理器上的可执行进程的链表，每个处理器一个。且每个进程归属唯一一个运行队列。包含了每个处理器上的调度信息，是一个处理器最重要的数据结构。由结构体runqueue表示：

 1 struct runqueue {
 2     spinlock_t lock;                      /*保护运行队列的自旋锁*/
 3     unsigned long nr_running;             /*可运行任务数目*/
 4 #ifdef CONFIG_SMP
 5     unsigned long cpu_load;
 6 #endif
 7     unsigned long long nr_switches;       /*上下文切换数目*/
 8     unsigned long nr_uninterruptible; 　　 /*处于不可中断睡眠状态的任务数目*/
 9     unsigned long expired_timestamp;　　　　/*队列最后被换出时间*/
10     unsigned long long timestamp_last_tick; /*最后一个调度程序的节拍*/
11     task_t *curr, *idle;　　　　　　　　　　  /*当前运行任务、该处理器的空任务*/　　
12     struct mm_struct *prev_mm;　　　　　　　　　/*最后运行任务的mm_struct结构体*/
13     prio_array_t *active, *expired, arrays[2]; /*活动优先级队列、超时优先级队列、实际优先级数组*/
14     int best_expired_prio;　　　　　　　　　　　
15     atomic_t nr_iowait;　　　　　　　　　　　　/*等待io操作的任务数目*/
16 
17 #ifdef CONFIG_SMP
18     struct sched_domain *sd;
19 
20     /* For active balancing */
21     int active_balance;
22     int push_cpu;
23 
24     task_t *migration_thread;　　　　　　　　/*移出线程*/
25     struct list_head migration_queue;　　　　/*移出队列*/
26 #endif
27 
28 #ifdef CONFIG_SCHEDSTATS
29     /* latency stats */
30     struct sched_info rq_sched_info;
31 
32     /* sys_sched_yield() stats */
33     unsigned long yld_exp_empty;
34     unsigned long yld_act_empty;
35     unsigned long yld_both_empty;
36     unsigned long yld_cnt;
37 
38     /* schedule() stats */
39     unsigned long sched_noswitch;
40     unsigned long sched_switch;
41     unsigned long sched_cnt;
42     unsigned long sched_goidle;
43 
44     /* pull_task() stats */
45     unsigned long pt_gained[MAX_IDLE_TYPES];
46     unsigned long pt_lost[MAX_IDLE_TYPES];
47 
48     /* active_load_balance() stats */
49     unsigned long alb_cnt;
50     unsigned long alb_lost;
51     unsigned long alb_gained;
52     unsigned long alb_failed;
53 
54     /* try_to_wake_up() stats */
55     unsigned long ttwu_cnt;
56     unsigned long ttwu_attempts;
57     unsigned long ttwu_moved;
58 
59     /* wake_up_new_task() stats */
60     unsigned long wunt_cnt;
61     unsigned long wunt_moved;
62 
63     /* sched_migrate_task() stats */
64     unsigned long smt_cnt;
65 
66     /* sched_balance_exec() stats */
67     unsigned long sbe_cnt;
68 #endif
69 };

　　3.3.2优先级数组

　　　每个队列含有两个优先级数组，active指向时间片没用完、当前可被调度的就绪进程，expired指向时间片已用完的就绪进程，被定义为prio_array的结构体：

prio_array_t *active, *expired, arrays[2];

struct prio_array {
    unsigned int nr_active;     /*本组中的进程数*/
    unsigned long bitmap[BITMAP_SIZE];  
    struct list_head queue[MAX_PRIO];
};

　　　3.3.3schedule（）函数

　　　进程调度由schedule()函数实现。

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

　　　schedule()通过调用sched_find_first_bit()函数找到当前CPU就绪队列runqueue的active进程数组中第一个非空的就绪进程链表。这个链表中的进程具有最高优先级，schedule()选择链表中的第一个进程最为调度器下一时刻将要运行的进程。

idx = sched_find_first_bit(array->bitmap);

　　　如果当前进程和将要运行的进程不是同一个进程，schedule()调用context_switch()上下文切换将CPU切换到next进程运行。

if (likely(prev != next)) {
        next->timestamp = now;
        rq->nr_switches++;
        rq->curr = next;
        ++*switch_count;

        prepare_arch_switch(rq, next);
        prev = context_switch(rq, prev, next);
        barrier();

        finish_task_switch(prev);
}

　　　　至此，简单介绍了进程调度完成了优先级时间片设置，调度器到选择下一个运行的程序，到完成上下文切换的所有步骤。　　　　

4.总结

　　该版本的进程调度算法相比于之前2.5版重新写了，与之前版本的内核中的调度程序区别很大，由O(n)大幅提升至O(1)，不管由多少进程，新的调度程序采用的每个算法都能在恒定时间内完成。而在2.6.23版至目前的内核版本中增加了一种称为完全公平调度算法CFS，由于时间问题就不在本篇中继续分析。

　　　通过本次对Linux2.6.10的源码分析，也是本人第一次接触到了操作系统内部，也是第一次接触如此巨大代码量的程序，从理论到实践对操作系统有了更深的认识。进程调度时内核的重要组成部分，然而满足进程调度的各种需求，总是需要在各个方面进行平衡，很难完成完美的算法，因此进程的调度也是在不断平衡中寻求最“完美”的解决方案。

5.参考文献

　　《Linux内核设计与实现second edition》Robert Love

　　　《Linux内核设计与实现thrid edition》Robert Love

　　　　https://blog.csdn.net/liuxiaowu19911121/article/details/47010721

　　　　《操作系统》浙江大学李善平

秒客网

第一次作业：Linux深入源码分析进程模型

相关文章