第一次作业:深入源码分析进程模型(基于Linux kernel 2.6)

时间:2021-07-05 21:56:58

前言

本文为基于Linux kernel 2.6进行深入源码的进程模型分析,进程是操作系统的核心概念之一,进程是系统实现的重要途径,所以,在此进行进程的相关分析,以此加强对操作系统的学习。

附上Linux kernel 2.6 源码下载地址:https://mirrors.edge.kernel.org/pub/linux/kernel/v2.6/

一、进程的概念及其特性

首先是百度百科关于进程的解释:

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

接下来是*关于进程的解释:

接着我们看下*上对进程(Process)的解释

In computing, a process is an instance of a computer program that is being executed. It contains the program code and its current activity. Depending on the operating system (OS), a process may be made up of multiple threads of execution that execute instructions concurrently.

Google翻译, 内容如下:

在计算中,进程是正在执行的计算机程序的一个实例。它包含程序代码及其当前活动。根据操作系统(OS),一个进程可能由多个执行线程并发执行指令组成。

接下来是关于进程的特征的一些描述:

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

在对进程有了一些基础的了解之后, 我们便可以进行下一步的分析了

二、操作系统是如何组织进程运行

在Linux系统中, 进程在/linux/include/linux/sched.h 头文件中被定义为task_struct, 它是一个结构体, 一个它的实例化即为一个进程, task_struct由许多元素构成, 下面列举一些重要的元素进行分析。


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

三、进程之间的关系

/*  * pointers to (original) parent process, youngest child, younger sibling,  * older sibling, respectively. (p->father can be replaced with  * p->parent->pid)  */ struct task_struct *real_parent; /* real parent process (when being debugged) */ struct task_struct *parent; /* parent process */ /*  * children/sibling forms the list of my children plus the  * tasks I‘m ptracing.  */ struct list_head children; /* list of my children */ struct list_head sibling; /* linkage in my parent‘s children list */ struct task_struct *group_leader; /* threadgroup leader */

在Linux系统中,所有进程之间都有着直接或间接地联系,每个进程都有其父进程,也可能有零个或多个子进程。拥有同一父进程的所有进程具有兄弟关系。

real_parent指向其父进程,如果创建它的父进程不再存在,则指向PID为1的init进程。 parent指向其父进程,当它终止时,必须向它的父进程发送信号。它的值通常与 real_parent相同。 children表示链表的头部,链表中的所有元素都是它的子进程(进程的子进程链表)。 sibling用于把当前进程插入到兄弟链表中(进程的兄弟链表)。 group_leader指向其所在进程组的领头进程。

四、进程状态之间的转换

1、进程状态

在task_struct结构体中, 定义进程的状态语句为

volatile long state; /* -1 unrunnable, 0 runnable, >0 stopped */
valatile关键字的作用是确保本条指令不会因编译器的优化而省略, 且要求每次直接读值, 这样保证了对进程实时访问的稳定性。
进程在/linux/include/linux/sched.h 头文件中我们可以找到state的可能取值如下

/*

* Task state bitmask. NOTE! These bits are also

* encoded in fs/proc/array.c: get_task_state().

* We have two separate sets of flags: task->state

* is about runnability, while task->exit_state are

* the task exiting. Confusing, but this way

* modifying one set can‘t modify the other one by

* mistake.
*/
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

根据state后面的注释, 可以得到当state<0时,表示此进程是处于不可运行的状态, 当state=0时, 表示此进程正处于运行状态, 当state>0时, 表示此进程处于停止运行状态。
以下列举一些state的常用取值
| 状态 | 描述 |
| :---------------------- | :----------------------------------------------------------- |
| 0(TASK_RUNNING) | 进程处于正在运行或者准备运行的状态中 |
| 1(TASK_INTERRUPTIBLE) | 进程处于可中断睡眠状态, 可通过信号唤醒 |
| 2(TASK_UNINTERRUPTIBLE) | 进程处于不可中断睡眠状态, 不可通过信号进行唤醒 |
| 4( TASK_STOPPED) | 进程被停止执行 |
| 8( TASK_TRACED) | 进程被监视 |
| 16( EXIT_ZOMBIE) | 僵尸状态进程, 表示进程被终止, 但是其父程序还未获取其被终止的信息。 |
| 32(EXIT_DEAD) | 进程死亡, 此状态为进程的最终状态 |

2、进程的各种状态之间互相转换的关系图:

第一次作业:深入源码分析进程模型(基于Linux kernel 2.6)

(图片来源于网上)

五、进程的调度

1、与进程调度有关的数据结构

在了解进程是如何进行调度之前, 我们需要先了解一些与进程调度有关的数据结构。

①可运行队列(runqueue)

/kernel/sched.c文件下, 可运行队列被定义为struct rq, 每一个CPU都会拥有一个struct rq, 它主要被用来存储一些基本的用于调度的信息, 包括及时调度和CFS调度。在Linux kernel 2.6中, struct rq是一个非常重要的数据结构, 接下来我们介绍一下它的部分重要字段:

                            /* 选取出部分字段做注释 */ //runqueue的自旋锁,当对runqueue进行操作的时候,需要对其加锁。由于每个CPU都有一个runqueue,这样会大大减少竞争的机会 spinlock_t lock; // 此变量是用来记录active array中最早用完时间片的时间 unsigned long expired_timestamp; //记录该CPU上就绪进程总数,是active array和expired array进程总数和 unsigned long nr_running; // 记录该CPU运行以来发生的进程切换次数 unsigned long long nr_switches; // 记录该CPU不可中断状态进程的个数 unsigned long nr_uninterruptible; // 这部分是rq的最最最重要的部分, 我将在下面仔细分析它们 struct prio_array *active, *expired, arrays[2];

②优先级数组(prio_array)

Linux kernel 2.6版本中, 在rq中多加了两个按优先级排序的数组active arrayexpired array 。
这两个队列的结构是struct prio_array, 它被定义在/kernel/sched.c中, 其数据结构为:

struct prio_array { unsigned int nr_active; // DECLARE_BITMAP(bitmap, MAX_PRIO+1); /* include 1 bit for delimiter */ /*开辟MAX_PRIO + 1个bit的空间, 当某一个优先级的task正处于TASK_RUNNING状态时, 其优先级对应的二进制位将会被标记为1, 因此当你需要找此时需要运行的最高的优先级时, 只需要找到bitmap的哪一位被标记为1了即可*/ struct list_head queue[MAX_PRIO]; // 每一个优先级都有一个list头 };

Active array表示的是CPU选择执行的运行进程队列, 在这个队列里的进程都有时间片剩余, *active指针总是指向它。
Expired array则是用来存放在Active array中使用完时间片的进程, *expired指针总是指向它。
一旦在active array里面的某一个普通进程的时间片使用完了, 调度器将重新计算该进程的时间片与优先级, 并将它从active array中删除, 插入到expired array中的相应的优先级队列中 。
当active array内的所有task都用完了时间片, 这时只需要将*active*expired这两个指针交换下, 即可切换运行队列。

③调度器主函数(schedule())

schedule函数存在/kernel/sched.c中, 是Linux kernel很重要的一个函数, 它的作用是用来挑选出下一个应该执行的进程, 并且完成进程的切换工作, 是进程调度的主要执行者。

2、调度算法(O(1)算法)

①介绍O(1)算法

何为O(1)算法: 该算法总能够在有限的时间内选出优先级最高的进程然后执行, 而不管系统中有多少个可运行的进程, 因此命名为O(1)算法。

 ②O(1)算法的原理

在前面我们提到了两个按优先级排序的数组active arrayexpired array, 这两个数组是实现O(1)算法的关键所在。
O(1)调度算法每次都是选取在active array数组中且优先级最高的进程来运行。
那么该算法如何找到优先级最高的进程呢? 大家还记得前面prio_array内的DECLARE_BITMAP(bitmap, MAX_PRIO+1);字段吗?这里它就发挥出作用了(详情看代码注释), 这里只要找到bitmap内哪一个位被设置为了1, 即可得到当前系统所运行的task的优先级(idx, 通过sehed_find_first_bit()方法实现), 接下来找到idx所对应的进程链表(queue), queue内的所有进程都是目前可运行的并且拥有最高优先级的进程, 接着依次执行这些进程,。
该过程定义在schedule函数中, 主要代码如下:

struct task_struct *prev, *next; struct list_head *queue; struct prio_array *array; int idx; prev = current; array = rq->active; idx = sehed_find_first_bit(array->bitmap); //找到位图中第一个不为0的位的序号 queue = array->queue + idx; //得到对应的队列链表头 next = list_entry(queue->next, struct task_struct, run_list); //得到进程描述符 if (prev != next) //如果选出的进程和当前进程不是同一个,则交换上下文 context_switch();