第一次作业：基于Linux进程模型分析

时间：2021-08-02 16:46:51

一 进程

1.1 进程的定义

  • 狭义定义：进程是正在运行的程序的实例（an instance of a computer program that is being executed）。
  • 广义定义：进程是一个具有一定独立功能的程序关于某个数据集合的一次运行活动。它是操作系统动态执行的基本单元，在传统的操作系统中，进程既是基本的分配单元，也是基本的执行单元。

1.2进程的特征

  • 动态性：进程的实质是程序在多道程序系统中的一次执行过程，进程是动态产生，动态消亡的。
  • 并发性：任何进程都可以同其他进程一起并发执行。
  • 独立性：进程是一个能独立运行的基本单位，同时也是系统分配资源和调度的独立单位。
  • 异步性：由于进程间的相互制约，使进程具有执行的间断性，即进程按各自独立的、不可预知的速度向前推进。
  • 结构特征：进程由程序、数据和进程控制块三部分组成。

二 进程的组织

2.1进程控制块

进程控制块（Processing Control Block），是操作系统核心中一种数据结构，主要表示进程状态。其作用是使一个在多道程序环境下不能独立运行的程序（含数据），成为一个能独立运行的基本单位或与其它进程并发执行的进程。而Linux 内核通过 task_struct 结构体来描述进程，它包含了一个进程的所有信息，该结构体被定义在 include/linux/sched.h文件中。

task_struct 结构体源码成员

  • 标识符：与进程相关的唯一标识符，用来区别正在执行的进程和其他进程。
  • 状态：描述进程的状态，因为进程有挂起，阻塞，运行等好几个状态，所以都有个标识符来记录进程的执行状态。
  • 优先级：如果有好几个进程正在执行，就涉及到进程被执行的先后顺序的问题，这和进程优先级这个标识符有关。
  • 程序计数器：程序中即将被执行的下一条指令的地址。
  • 内存指针：程序代码和进程相关数据的指针。
  • 上下文数据：进程执行时处理器的寄存器中的数据。
  • I/O状态信息：包括显示的I/O请求，分配给进程的I/O设备和被进程使用的文件列表等。
  • 记账信息：包括处理器的时间总和，记账号等等。

2.2 程序段

程序段就是能被进程调度程序调度到CPU执行的程序代码段。注意，程序可以被多个进程共享，就是说多个进程可以运行同一个程序。

2.3 数据段

一个进程的数据段，可以是进程对应的程序加工处理的原始数据，也可以是程序执行时产生的中间或最终结果。

三 进程的状态

3.1 进程的状态

  • Linux进程状态：R (TASK_RUNNING)，可执行状态。

         只有在该状态的进程才可能在CPU上运行。这些进程的task_struct结构（进程控制块）被放入对应CPU的可执行队列中（一个进程最多只能出现在一个CPU的可执行队列中）。进程调度器的任务就是从各个CPU的可执行队列中分别选择一个进程在该CPU上运行。

  • Linux进程状态：S (TASK_INTERRUPTIBLE)，可中断的睡眠状态。

         处于这个状态的进程因为等待某某事件的发生（比如等待socket连接、等待信号量），而被挂起。这些进程的task_struct结构被放入对应事件的等待队列中。当这些事件发生时（由外部中断触发、或由其他进程触发），对应的等待队列中的一个或多个进程将被唤醒。

  • Linux进程状态：D (TASK_UNINTERRUPTIBLE)，不可中断的睡眠状态。

          不可中断，指的并不是CPU不响应外部硬件的中断，而是指进程不响应异步信号。

  • Linux进程状态：T (TASK_STOPPED or TASK_TRACED)，暂停状态或跟踪状态。

          TASK_STOPPED和TASK_TRACED状态很类似，都是表示进程暂停下来。而TASK_TRACED状态相当于在TASK_STOPPED之上多了一层保护，处于TASK_TRACED状态的进程不能响应SIGCONT信号而被唤醒。

  • Linux进程状态：Z (TASK_DEAD – EXIT_ZOMBIE)，退出状态，进程成为僵尸进程。       

          进程在退出的过程中，处于TASK_DEAD状态。在这个退出过程中，进程占有的所有资源将被回收，除了task_struct结构（以及少数资源）以外。于是进程就只剩下task_struct这么个空壳，故称为僵尸。

  • Linux进程状态：X (TASK_DEAD – EXIT_DEAD)，退出状态，进程即将被销毁。

          进程被置于EXIT_DEAD退出状态意味着接下来的代码立即就会将该进程彻底释放。EXIT_DEAD状态是非常短暂的，几乎不可能通过ps命令捕捉到。

3.2 进程状态的转化

最基本的状态包括以下三种：

  • 运行态：进程占用CPU，并在CPU上运行；
  • 就绪态：进程已经具备运行条件，但是CPU还没有分配过来；
  • 阻塞态：进程因等待某件事发生而暂时不能运行。

三种状态之间的转化：

  • 运行---》就绪：这是有调度引起的，主要是进程占用CPU的时间过长
  • 就绪---》运行：运行的进程的时间片用完，调度就转到就绪队列中选择合适的进程分配CPU
  • 运行---》阻塞：发生了I/O请求或等待某件事的发生
  • 阻塞---》就绪:进程所等待的事件发生，就进入就绪队列

3.3 进程状态转化图 

第一次作业：基于Linux进程模型分析

四 进程的调度

4.1 有关调度的概念

调度程序负责决定哪个进程投入运行，何时运行及运行多长时间。进程调度程序就是在可运行态进程之间分配有限的处理器时间资源的内核子系统。 调度器的任务：1、分配时间给进程     2、上下文切换

4.2 调度器的结构

在Linux内核中，调度器可以分成两个层级，在进程中被直接调用的成为通用调度器或者核心调度器，他们作为一个组件和进程其他部分分开，而通用调度器和进程并没有直接关系，其通过第二层的具体的调度器类来直接管理进程。具体架构如下图：

第一次作业：基于Linux进程模型分析

4.3 调度算法

完全公平调度算法（CFS）是针对普通进程的调度，在Linux中称为SCHED_NORMAL。算法定义在文件kernel/sched_fair.c。 

四个组成部分：

  • 时间记账

         CFS使用调度器实体结构（struct_sched_entity）来追踪进程运行的时间记账，调度器实体结构是作为se成员变量嵌入在进程描述符struct task_struct内。 

  • 进程选择               

         CFS调度算法的核心：选择最小的vruntime的任务。 CFS使用红黑树来组织可运行的进程队列，并利用其迅速找到最小vruntime的进程。

  • 调度器入口

         进程调度的主要入口点是函数schedule()：选择哪个进程可以运行，何时将其投入运行。函数会调用pick_next_task()，以优先级为序依次检查每一个调度类，从最高优先级的调度类中选择最高优先级的进程。

  • 睡眠和唤醒

          睡眠：进程把自己标记为休眠状态，从可执行红黑树中移除，放入等待队列，然后调用schedule()选择和执行一个其他进程。
          唤醒：唤醒操作通过wake_up()函数进行，唤醒指定的队列的所有进程。

CFS的实现：

函数pick_next_task_fair：

static struct task_struct *pick_next_task_fair(struct rq *rq)
{
    struct task_struct *p;
    /*从CPU 的就绪队列找到公平调度队列*/
    struct cfs_rq *cfs_rq = &rq->cfs;
    struct sched_entity *se;
    /*如果公平调度类没有可运行的进程，直接返回*/
    if (!cfs_rq->nr_running)
        return NULL;
     /*如果调度的是一组进程，则需要进行循环设置，否则执行一次就退出了*/
    do {
        /*从公平调度类中找到一个可运行的实体*/
        se = pick_next_entity(cfs_rq);
        /*设置红黑树中下一个实体，并标记cfs_rq->curr为se*/
        set_next_entity(cfs_rq, se);
        cfs_rq = group_cfs_rq(se);
    } while (cfs_rq);
    /*获取到具体的task_struct*/
    p = task_of(se);
    if (hrtick_enabled(rq))
        hrtick_start_fair(rq, p);

    return p;
}

 

4.4 有关如何调度

一旦确定了要进行调度，那么schedule函数被调用。周期性调度器并不直接调度，至多设置进程的重调度位TIF_NEED_RESCHED，这样在返回用户空间的时候仍然由主调度器执行调度。跟踪schedule函数，具体实现由schedule函数完成。

  • schedule函数：
static void __sched __schedule(void)
{
    struct task_struct *prev, *next;
    unsigned long *switch_count;
    struct rq *rq;
    int cpu;

need_resched:
    /*禁止内核抢占*/
    preempt_disable();
    cpu = smp_processor_id();
    /*获取CPU 的调度队列*/
    rq = cpu_rq(cpu);
    rcu_note_context_switch(cpu);
    /*保存当前任务*/
    prev = rq->curr;

    schedule_debug(prev);

    if (sched_feat(HRTICK))
        hrtick_clear(rq);

    /*
     * Make sure that signal_pending_state()->signal_pending() below
     * can't be reordered with __set_current_state(TASK_INTERRUPTIBLE)
     * done by the caller to avoid the race with signal_wake_up().
     */
    smp_mb__before_spinlock();
    raw_spin_lock_irq(&rq->lock);

    switch_count = &prev->nivcsw;
     /*  如果内核态没有被抢占, 并且内核抢占有效
        即是否同时满足以下条件：
        1  该进程处于停止状态
        2  该进程没有在内核态被抢占 */
    if (prev->state && !(preempt_count() & PREEMPT_ACTIVE)) {
        if (unlikely(signal_pending_state(prev->state, prev))) {
            prev->state = TASK_RUNNING;
        } else {
            deactivate_task(rq, prev, DEQUEUE_SLEEP);
            prev->on_rq = 0;

            /*
             * If a worker went to sleep, notify and ask workqueue
             * whether it wants to wake up a task to maintain
             * concurrency.
             */
            if (prev->flags & PF_WQ_WORKER) {
                struct task_struct *to_wakeup;

                to_wakeup = wq_worker_sleeping(prev, cpu);
                if (to_wakeup)
                    try_to_wake_up_local(to_wakeup);
            }
        }
        switch_count = &prev->nvcsw;
    }

    pre_schedule(rq, prev);

    if (unlikely(!rq->nr_running))
        idle_balance(cpu, rq);
    /*告诉调度器prev进程即将被调度出去*/
    put_prev_task(rq, prev);
    /*挑选下一个可运行的进程*/
    next = pick_next_task(rq);
    /*清除pre的TIF_NEED_RESCHED标志*/
    clear_tsk_need_resched(prev);
    rq->skip_clock_update = 0;
   /*如果next和当前进程不一致，就可以调度*/
    if (likely(prev != next)) {
        rq->nr_switches++;
        /*设置当前调度进程为next*/
        rq->curr = next;
        ++*switch_count;
        /*切换进程上下文*/
        context_switch(rq, prev, next); /* unlocks the rq */
        /*
         * The context switch have flipped the stack from under us
         * and restored the local variables which were saved when
         * this task called schedule() in the past. prev == current
         * is still correct, but it can be moved to another cpu/rq.
         */
        cpu = smp_processor_id();
        rq = cpu_rq(cpu);
    } else
        raw_spin_unlock_irq(&rq->lock);

    post_schedule(rq);
  
    sched_preempt_enable_no_resched();
    if (need_resched())
        goto need_resched;
}
  • 核心函数实现：

pick_next_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.h_nr_running)) {
        p = fair_sched_class.pick_next_task(rq);
        if (likely(p))
            return p;
    }
    /*从优先级最高的调度器类开始遍历，顺序为stop_sched_class->rt_scheduled_class->fair_schedled_class->idle_sched_class*/
    /*
    #define for_each_class(class) \
   for (class = sched_class_highest; class; class = class->next)
    */
    for_each_class(class) {
        p = class->pick_next_task(rq);
        if (p)
            return p;
    }

    BUG(); /* the idle class will always have a runnable task */
}

五 对操作系统进程模型的看法

操作系统中最核心的概念是进程。Linux是目前最流行的几个操作系统之一。在Linux进程模型中，为了管理进程，内核必须对每个进程所做的事情进行清楚的描述，这也是进程描述符的功能。进程描述符都是task_struct类型结构，它是一个非常复杂的结构。在Linux里，只有进程的概念，变量并不共享，由程序员来显式地指定要共享的数据，使程序变得更清晰与安全。

 

六 参考资料

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

https://www.cnblogs.com/caidi/p/6698168.html

https://blog.csdn.net/sdkdlwk/article/details/65938204

https://www.cnblogs.com/ck1020/p/6089970.html

 

标签：

相关文章