第一次作业：基于Linux操作系统深入源码进程模型分析

1.前言

本文基于Linux-2.6.34.1，主要分析其进程模型，其中主要内容包含进程的组织、转换、调度，以及在分析过程中对其一点小看法

付源码下载地址：https://mirrors.edge.kernel.org/pub/linux/kernel/v2.6/

2.进程是什么

2.1 进程的概念

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

2.2 进程与线程

--联系

一个线程可以创建和撤销另一个线程;同一个进程中的多个线程之间可以并发执行.相对进程而言，线程是一个更加接近于执行体的概念，它可以与同进程中的其他线程共享数据，但拥有自己的栈空间，拥有独立的执行序列。

--区别

进程和线程的主要差别在于它们是不同的操作系统资源管理方式。进程有独立的地址空间，一个进程崩溃后，在保护模式下不会对其它进程产生影响，而线程只是一个进程中的不同执行路径。线程有自己的堆栈和局部变量，但线程之间没有单独的地址空间，一个线程死掉就等于整个进程死掉，所以多进程的程序要比多线程的程序健壮，但在进程切换时，耗费资源较大，效率要差一些。但对于一些要求同时进行并且又要共享某些变量的并发操作，只能用线程，不能用进程。

3.进程的组织

linux内核通过task_struct(进程描述符)结构体来管理进程，这个结构体包含了一个进程所需要的所有信息。它定义在目录linux-2.6.34\include\linux\sched.h文件中

3.1进程的状态

 1 /*
 2  * Task state bitmask. NOTE! These bits are also
 3  * encoded in fs/proc/array.c: get_task_state().
 4  *
 5  * We have two separate sets of flags: task->state
 6  * is about runnability, while task->exit_state are
 7  * about the task exiting. Confusing, but this way
 8  * modifying one set can't modify the other one by
 9  * mistake.
10  */
11 #define TASK_RUNNING        0
12 #define TASK_INTERRUPTIBLE    1
13 #define TASK_UNINTERRUPTIBLE    2
14 #define __TASK_STOPPED        4
15 #define __TASK_TRACED        8
16 /* in tsk->exit_state */
17 #define EXIT_ZOMBIE        16
18 #define EXIT_DEAD        32
19 /* in tsk->state again */
20 #define TASK_DEAD        64
21 #define TASK_WAKEKILL        128
22 #define TASK_WAKING        256
23 #define TASK_STATE_MAX        512

上图为Linux 2.6.34有关于进程定义的相关代码，从中可看出进程的状态分为两大类，分别为 struct_task 中成员 state（关于运行的状态）和 exit_state（关于退出的状态），其主要有如下几个状态。

第一次作业：基于Linux操作系统深入源码进程模型分析

TASK_RUNNING（运行态）：表示进程要么正在执行，要么正要准备执行（该时刻进程实际占用CPU）
TASK_INTERRUPTIBLE（可运行态）：E表示进程被阻塞（睡眠），直到某个条件变为真。条件一旦达成，进程的状态就被设置为TASK_RUNNING。（可运行，但因为其他进程正在运行而暂时停止）
TASK_UNINTERRUPTIBLE（阻塞态）：TASK_UNINTERRUPTIBLE的意义与TASK_INTERRUPTIBLE类似，除了不能通过接受一个信号来唤醒。（除非某种外部事件发生，否则进程不能进行）
__TASK_STOPPED（暂停态）：表示进程被停止执行。
EXIT_ZOMBIE（僵死状态）：表示进程的执行被终止，但是其父进程还没有使用wait()等系统调用来获知它的终止信息。

第一次作业：基于Linux操作系统深入源码进程模型分析

3.2 进程的创建与撤销

--3.2.1 进程创建

用户空间内可以通过执行一个程序、或者在程序内调用fork（或exec）系统调用来创建进程，fork调用会导致创建一个子进程，而exec调用则会用新程序代替当前进程上下文。一个新进程的诞生还可以分别通过vfork()和clone()。fork、vfork和clone三个用户态函数均由libc库提供，它们分别会调用Linux内核提供的同名系统调用fork,vfork和clone。

fork系统调用在unistd.h中的宏关联如下

#define __NR_fork 1079  
#ifdef CONFIG_MMU  
__SYSCALL(__NR_fork, sys_fork)  
#else  
__SYSCALL(__NR_fork, sys_ni_syscall)  
#endif

对名为sys_fork的内核函数的系统调用如下

1 int sys_fork(struct pt_regs *regs)  
2 {  
3     return do_fork(SIGCHLD, regs->sp, regs, 0, NULL, NULL);  
4 }

可以看出 do_fork 是进程创建的基础，主要工作就是复制原来的进程成为另一个新的进程，它完成了整个进程创建中的大部分工作

--3.2.2 进程撤销

进程通过调用exit()退出执行，这个函数会终结进程并释放所有的资源。父进程可以通过wait4()查询子进程是否终结。进程退出执行后处于僵死状态，直到它的父进程调用wait()或者waitpid()为止。父进程退出时，内核会指定线程组的其他进程或者init进程作为其子进程的新父进程。当进程接收到一个不能处理或忽视的信号时，或当在内核态产生一个不可恢复的CPU异常而内核此时正代表该进程在运行，内核可以强迫进程终止。

3.3 进程的管理

在Linux中，每个进程都有自己的task_struct结构。为了对系统中的很多进程及处于不同状态的进程进行管理，Linux采用了以下几种组织方式来管理进程：

（1）哈希表：linux用一个宏pid_hashfn()将PID转换成表的索引，通过pid_hashfn()可以把进程的PID均匀的散列在哈希表中。

（2）进程链表：每个进程task_struct结构中的prev_task和next_task成员用来实现这种链表，链表的头和尾都是init_task（即0号进程），这个进程永远不会被撤销地被静态分配在内核数据段中。

（3）就绪队列：把所有可运行状态的进程组成的一个双向链表叫做就绪队列，该队列通过task_struct结构中的两个指针run_list链表来维护

3.4 进程的相关标识符

系统通过PID来唯一的标识每个进程。由于进程与进程描述符之间有严格的一对一的对应关系，使得每个进程都有一个唯一的标识符，内核通过这个标识符来识别不同的进程，同时，进程标识符PID也是内核提供给用户程序的接口，用户程序通过PID对进程发号施令。相关定义如下：

 1 struct pid
 2 {
 3     atomic_t count;
 4     unsigned int level;
 5     /* lists of tasks that use this pid */
 6     struct hlist_head tasks[PIDTYPE_MAX];
 7     struct rcu_head rcu;
 8     struct upid numbers[1];
 9 };
10 * What is struct pid?
11 *
12 * A struct pid is the kernel's internal notion of a process identifier.
13 * It refers to individual tasks, process groups, and sessions. While
14 * there are processes attached to it the struct pid lives in a hash
15 * table, so it and then the processes that it refers to can be found
16 * quickly from the numeric pid value. The attached processes may be
17 * quickly accessed by following pointers from struct pid.

3.5 进程优先级

内核允许用户通过使用一个名为nice的数值来影响调度程序关于优先级的调度，nice值越高,有效优先级就越低，nice值越低,有效优先级就越高。

其中优先级又分为以下几种不同类型：

（1）动态优先级：prio

（2）静态优先级：static_prio

（3）普通优先级：normal_prio

（4）实时优先级：rt_priority

4.进程的转换

进程的转换主要涉及在 3.1 中介绍的几种状态，主要转换的四种过程如下：

（1）运行态→等待态：当进程请求某一资源（如外设）的使用和分配或等待某一事件的发生（如I/O操作的完成）时，它就从运行状态转换为等待状态。

（2）等待态→就绪态：当进程等待的事件到来时（如I/O操作结束或中断结束），中断处理程序必须把相应进程的状态由等待状态转换为就绪状态。

（3）运行态→就绪态：处于运行状态的进程在时间片用完后，不得不让出处理机，从而进程由运行状态转换为就绪状态。

（4）就绪态→运行态：处于就绪状态的进程被调度后，获得处理机资源（分派处理机时间片），于是进程由就绪状态转换为运行状态。

进程状态转换图如下：

第一次作业：基于Linux操作系统深入源码进程模型分析

5.进程的调度

当计算机系统是多道程序设计系统时，通常就会有多个进程或线程同时竞争CPU。只要有两个或更多的进程处于就绪状态，这种情况就会发生。如果只有一个CPU可用，那么就必须选择下一个要运行的进程。所以就有了要完成这个工作的调度程序，和其使用的调度算法。

5.1 调度方式

（1）非剥夺调度方式（非抢占方式）：实现简单，系统开销小，适用于大多数的批处理系统，但它不能用于分时系统和大多数的实时系统。

（2）剥夺调度方式（抢占方式）：要遵循一定的原则，主要有：优先级、短进程优先和时间片原则。

5.2 调度算法

（1）先来先服务（FCFS first come first serve）：属于不可剥夺算法。算法每次从后备作业队列中选择最先进入该队列的一个或几个作业进行处理。

特点：算法简单，效率低，对长作业有利，对短作业不利。

（2）短作业优先（SJF short job first）:算法从后备队列中选择一个或若干个估计运行时间最短的作业处理。直到完成作业或发生某事件而阻塞时，才释放处理机。

缺点：（1）对长作业不利，造成“饥饿”现象（2）未考虑作业紧迫程度（3）由于运行时间是估计所得，所以并不一定能做到短作业优先。

（3）优先级：可分为（1）非剥夺式（2）剥夺式；其中优先级可分为：（1）静态优先级（2）动态优先级

（4）高响应比优先：响应比=（等待时间+处理时间）/处理时间=1+等待时间/处理时间

（5）时间片轮转

5.3 调度器

依据其调度策略的不同实现了以下5个调度器类

stop_sched_class：发生在cpu_stop_cpu_callback 进行cpu之间任务migration，HOTPLUG_CPU的情况下关闭任务，不需要调度普通进程。
dl_sched_class：采用EDF最早截至时间优先算法调度实时进程，对应调度策略为SCHED_DEADLINE。
rt_sched_class：采用提供 Roound-Robin算法或者FIFO算法调度实时进程，具体调度策略由进程的task_struct->policy指定，对应的调度策略为SCHED_FIFO, SCHED_RR。
fair_sched_clas：采用CFS算法调度普通的非实时进程，对应的调度策略为SCHED_NORMAL, SCHED_BATCH。
idle_sched_class：采用CFS算法调度idle进程, 每个cup的第一个pid=0线程：swapper，是一个静态线程。调度类属于：idel_sched_class，所以在ps里面是看不到的。一般运行在开机过程和cpu异常的时候做dump，对应的调度策略为SCHED_IDLE。
5.4 CFS调度器

--主要设计思想

    全公平调度器（CFS）的设计思想是：在一个真实的硬件上模型化一个理想的、精确的多任务CPU。该理想CPU模型运行在100%的负荷、在精确平等速度下并行运行每个任务，每个任务运行在1/n速度下，即理想CPU有n个任务运行，每个任务的速度为CPU整个负荷的1/n。

      由于真实硬件上，每次只能运行一个任务，这就得引入"虚拟运行时间"（virtual runtime）的概念，虚拟运行时间为一个任务在理想CPU模型上执行的下一个时间片(timeslice)。实际上，一个任务的虚拟运行时间为考虑到运行任务总数的实际运行时间。

      CFS 背后的主要想法是维护为任务提供处理器时间方面的平衡（公平性）。CFS为了体现的公平表现在2个方面
(1)进程的运行时间相等
      CFS 在叫做虚拟运行时 的地方维持提供给某个任务的时间量。任务的虚拟运行时越小，意味着任务被允许访问服务器的时间越短 — 其对处理器的需求越高。
            假设runqueue中有n个进程，当前进程运行了 10ms。在“完全理想的多任务处理器”中，10ms应该平分给n个进程(不考虑各个进程的nice值)，因此当前进程应得的时间是(10/n)ms，但是它却运行了10ms。所以CFS将惩罚当前进程，使其它进程能够在下次调度时尽可能取代当前进程。最终实现所有进程的公平调度。

(2)睡眠的进程进行补偿
      CFS 还包含睡眠公平概念以便确保那些目前没有运行的任务（例如，等待 I/O）在其最终需要时获得相当份额的处理器。

      CFS调度器的运行时间是O(logN)，而以前的调度器的运行时间是O(1)，这是不是就是说CFS的效率比O(1)的更差呢？
      答案并不是那样，我们知道 CFS调度

器下的运行队列是基于红黑树组织的，找出下一个进程就是截下左下角的节点，固定时间完成，所谓的O(logN)指的是插入时间，可是红黑树的统计性能是不错的，没有多大概率真的用得了那么多时间，因为红节点和黑节点的特殊排列方式既保证了树的一定程度的平衡，又不至于花太多的时间来维持这种平衡，插入操作大多数情况下都可以很快的完成，特别是对于组织得相当好的数据。

红黑树：

CFS内部原理：

--相关代码结构

调度实体sched_entity：

 1 struct sched_entity {
 2     struct load_weight    load;        /* for load-balancing */
 3     struct rb_node        run_node;　　
 4     struct list_head    group_node; 
 5     unsigned int        on_rq;　　   
 6 
 7     u64            exec_start;
 8     u64            sum_exec_runtime;
 9     u64            vruntime;
10     u64            prev_sum_exec_runtime;
11 　　 
12     u64            last_wakeup;
13     u64            avg_overlap;
14 
15     u64            nr_migrations;
16 
17     u64            start_runtime;
18     u64            avg_wakeup;
19 
20 #ifdef CONFIG_SCHEDSTATS
21     u64            wait_start;
22     u64            wait_max;
23     u64            wait_count;
24     u64            wait_sum;
25     u64            iowait_count;
26     u64            iowait_sum;
27 
28     u64            sleep_start;
29     u64            sleep_max;
30     s64            sum_sleep_runtime;
31 
32     u64            block_start;
33     u64            block_max;
34     u64            exec_max;
35     u64            slice_max;
36 
37     u64            nr_migrations_cold;
38     u64            nr_failed_migrations_affine;
39     u64            nr_failed_migrations_running;
40     u64            nr_failed_migrations_hot;
41     u64            nr_forced_migrations;
42 
43     u64            nr_wakeups;
44     u64            nr_wakeups_sync;
45     u64            nr_wakeups_migrate;
46     u64            nr_wakeups_local;
47     u64            nr_wakeups_remote;
48     u64            nr_wakeups_affine;
49     u64            nr_wakeups_affine_attempts;
50     u64            nr_wakeups_passive;
51     u64            nr_wakeups_idle;
52 #endif

调度器类sched_class：

 1 struct sched_class {
 2     const struct sched_class *next; 
 3 
 4     void (*enqueue_task) (struct rq *rq, struct task_struct *p, int wakeup,
 5                   bool head);
 6     void (*dequeue_task) (struct rq *rq, struct task_struct *p, int sleep);
 7     void (*yield_task) (struct rq *rq);
 8 
 9     void (*check_preempt_curr) (struct rq *rq, struct task_struct *p, int flags);
10 
11     struct task_struct * (*pick_next_task) (struct rq *rq);
12     void (*put_prev_task) (struct rq *rq, struct task_struct *p);
13 
14 #ifdef CONFIG_SMP
15     int  (*select_task_rq)(struct task_struct *p, int sd_flag, int flags);
16 
17     void (*pre_schedule) (struct rq *this_rq, struct task_struct *task);
18     void (*post_schedule) (struct rq *this_rq);
19     void (*task_waking) (struct rq *this_rq, struct task_struct *task);
20     void (*task_woken) (struct rq *this_rq, struct task_struct *task);
21 
22     void (*set_cpus_allowed)(struct task_struct *p,
23                  const struct cpumask *newmask);
24 
25     void (*rq_online)(struct rq *rq);
26     void (*rq_offline)(struct rq *rq);
27 #endif
28 
29     void (*set_curr_task) (struct rq *rq);
30     void (*task_tick) (struct rq *rq, struct task_struct *p, int queued);
31     void (*task_fork) (struct task_struct *p);
32 
33     void (*switched_from) (struct rq *this_rq, struct task_struct *task,
34                    int running);
35     void (*switched_to) (struct rq *this_rq, struct task_struct *task,
36                  int running);
37     void (*prio_changed) (struct rq *this_rq, struct task_struct *task,
38                  int oldprio, int running);
39 
40     unsigned int (*get_rr_interval) (struct rq *rq,
41                      struct task_struct *task);
42 
43 #ifdef CONFIG_FAIR_GROUP_SCHED
44     void (*moved_group) (struct task_struct *p, int on_rq);
45 #endif
46 };

调度队列cfs_rq：

 1 struct cfs_rq {
 2     struct load_weight load;
 3     unsigned long nr_running;
 4 
 5     u64 exec_clock;
 6     u64 min_vruntime; 
 7 
 8     struct rb_root tasks_timeline;
 9     struct rb_node *rb_leftmost;
10 
11     struct list_head tasks;
12     struct list_head *balance_iterator;
13 
14     /*
15      * 'curr' points to currently running entity on this cfs_rq.
16      * It is set to NULL otherwise (i.e when none are currently running).
17      */
18     struct sched_entity *curr, *next, *last;
19 
20     unsigned int nr_spread_over;
21 
22 #ifdef CONFIG_FAIR_GROUP_SCHED
23     struct rq *rq;    /* cpu runqueue to which this cfs_rq is attached */
24 
25     /*
26      * leaf cfs_rqs are those that hold tasks (lowest schedulable entity in
27      * a hierarchy). Non-leaf lrqs hold other higher schedulable entities
28      * (like users, containers etc.)
29      *
30      * leaf_cfs_rq_list ties together list of leaf cfs_rq's in a cpu. This
31      * list is used during load balance.
32      */
33     struct list_head leaf_cfs_rq_list;
34     struct task_group *tg;    /* group that "owns" this runqueue */
35 
36 #ifdef CONFIG_SMP
37     /*
38      * the part of load.weight contributed by tasks
39      */
40     unsigned long task_weight;
41 
42     /*
43      *   h_load = weight * f(tg)
44      *
45      * Where f(tg) is the recursive weight fraction assigned to
46      * this group.
47      */
48     unsigned long h_load;
49 
50     /*
51      * this cpu's part of tg->shares
52      */
53     unsigned long shares;
54 
55     /*
56      * load.weight at the time we set shares
57      */
58     unsigned long rq_weight;
59 #endif
60 #endif
61 };

调度操作：

 1 static void update_curr(struct cfs_rq *cfs_rq)
 2 {
 3     struct sched_entity *curr = cfs_rq->curr;
 4     u64 now = rq_of(cfs_rq)->clock;
 5     unsigned long delta_exec;
 6 
 7     if (unlikely(!curr))
 8         return;
 9 
10     /*
11      * Get the amount of time the current task was running
12      * since the last time we changed load (this cannot
13      * overflow on 32 bits):
14      */
15     delta_exec = (unsigned long)(now - curr->exec_start);
16     if (!delta_exec)
17         return;
18 
19     __update_curr(cfs_rq, curr, delta_exec);
20     curr->exec_start = now;
21 
22     if (entity_is_task(curr)) {
23         struct task_struct *curtask = task_of(curr);
24 
25         trace_sched_stat_runtime(curtask, delta_exec, curr->vruntime);
26         cpuacct_charge(curtask, delta_exec);
27         account_group_exec_runtime(curtask, delta_exec);
28     }
29 }

 1 asmlinkage void __sched schedule(void)
 2 {
 3     struct task_struct *prev, *next;  
 4     unsigned long *switch_count;
 5     struct rq *rq;
 6     int cpu;
 7 
 8 need_resched:
 9     preempt_disable();
10     cpu = smp_processor_id();
11     rq = cpu_rq(cpu);
12     rcu_sched_qs(cpu);
13     prev = rq->curr;
14     switch_count = &prev->nivcsw;
15 
16     release_kernel_lock(prev);
17 need_resched_nonpreemptible:
18 
19     schedule_debug(prev);
20 
21     if (sched_feat(HRTICK))
22         hrtick_clear(rq);
23 
24     raw_spin_lock_irq(&rq->lock);
25     update_rq_clock(rq);
26     clear_tsk_need_resched(prev);
27 
28     if (prev->state && !(preempt_count() & PREEMPT_ACTIVE)) {
29         if (unlikely(signal_pending_state(prev->state, prev)))
30             prev->state = TASK_RUNNING;
31         else
32             deactivate_task(rq, prev, 1);
33         switch_count = &prev->nvcsw;
34     }
35 
36     pre_schedule(rq, prev);
37 
38     if (unlikely(!rq->nr_running))
39         idle_balance(cpu, rq);
40 
41     put_prev_task(rq, prev);
42     next = pick_next_task(rq);
43 
44     if (likely(prev != next)) {
45         sched_info_switch(prev, next);
46         perf_event_task_sched_out(prev, next);
47 
48         rq->nr_switches++;
49         rq->curr = next;
50         ++*switch_count;
51                
52         context_switch(rq, prev, next); /* unlocks the rq */
53     ……

6.感想与看法

在进程调度方面，没有绝对的公平，也没有绝对的高效率，我们能做的就是将这二者最大的平衡化。现在采用的CFS调度是用全部进程优先级的比重来计算每一个进程的时间片的，是相对的而不是绝对的。虽然称为完全公平调度算法，也无法做到真的绝对公平。但CFS调度已经做的十分好了，在之前的调度器中每个进程都只有在用完了时间片或者属于自己的时间配额之后才被抢占，而CFS则在每次tick都进行检查，如果当前进程不再处于红黑树的左边，就被抢占。即所谓的调度粒度小，很好的提高了调度性能。

7.参考资料.

https://www.cnblogs.com/yysblog/archive/2012/11/20/2779120.html

http://www.bubuko.com/infodetail-2581724.html

https://baike.baidu.com/item/%E8%BF%9B%E7%A8%8B/382503?fr=aladdin

https://blog.csdn.net/yaosiming2011/article/details/44280797/

https://blog.csdn.net/tiankong_/article/details/75570911

https://blog.csdn.net/u013291303/article/details/68954599

https://blog.csdn.net/kkfd1002/article/details/80153665

秒客网

第一次作业：基于Linux操作系统深入源码进程模型分析

1.前言

2.进程是什么

2.1 进程的概念

2.2 进程与线程

--联系

--区别

3.进程的组织

3.1进程的状态

3.2 进程的创建与撤销

--3.2.1 进程创建

--3.2.2 进程撤销

3.3 进程的管理

3.4 进程的相关标识符

3.5 进程优先级

4.进程的转换

5.进程的调度

5.1 调度方式

5.2 调度算法

5.3 调度器

5.4 CFS调度器

--主要设计思想

--相关代码结构

6.感想与看法

7.参考资料.

相关文章