基于Linux kernel 2.6.10的进程分析及调度算法分析
1.前言
非常高兴能和大家分享我对Linux kernel 2.6.10的进程的理解，以及对其调度算法的分析。首先，贴出Linux kernel 2.6.10的源代码:https://mirrors.edge.kernel.org/pub/linux/kernel/v2.6/linux-2.6.10.tar.gz
2.什么是进程
首先，我们先来了解一下进程的概念。在wikepedia中进程被解释为：
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.
进程是操作系统中最核心的概念：这是对正在运行程序的一个抽象。操作系统的其他所有内容都是围绕着进程的概念展开的。实际上，进程就是正在执行的程序代码的实时结果。
3.操作系统是如何组织进程的
3.1进程何时被创建？
* 系统初始化
* 正在运行的进程创建了子进程
* 用户请求创建一个新进程
* 批处理作业的初始化 3.2Linux采用何种方式创建进程
3.2.1进程标识符
每个Linux进程都有唯一的标识符，称为进程标识符（PID），它是一个范围从0到32767之间的证书。PID 0和PID 1对于系统有特点的意义，其他的进程标识符都被认为是普通进程。
3.2.2创建进程的方法
在系统运行以后传统的Linux实现方法，给出了两种创建新进程的方法：系统调用fork及_clone。当进程调用fork时，该进程从概念上被分成了两部分--祖先和子孙进程。
我们先使用ps -aux|less查看Linux系统上的当前正在运行的进程
- 接下来，我们使用
fork()exec()来创建进程
1.进程复制
使用fork函数得到的子进程从父进程的继承了整个进程的地址空间，包括：进程上下文、进程堆栈、内存信息、打开的文件描述符、信号控制设置、进程优先级、进程组号、当前工作目录、根目录、资源限制、控制终端等。
子进程与父进程的区别在于：
1、父进程设置的锁，子进程不继承（因为如果是排它锁，被继承的话，矛盾了）
2、各自的进程ID和父进程ID不同
3、子进程的未决告警被清除；
4、子进程的未决信号集设置为空集。 2.fork系统调用
包含头文件<sys/tyoes.h> 和 <unistd.h>
函数功能：创建一个子进程
返回值：
* 如果成功创建一个子进程，对于父进程来说返回子进程ID
* 如果成功创建一个子进程，对于子进程来说返回值为0
* 如果为-1表示创建失败 流程图：
3.exec系统调用
在fork后的子进程中使用exec函数族，可以装入和运行其它程序(子进程替换原有进程，和父进程做不同的事)。
fork创建一个新的进程就产生了一个新的PID，exec启动一个新程序，替换原有的进程，因此这个新的被 exec 执行的进程的PID不会改变(和调用exec的进程的PID一样)。
exec函数族：
#include <unistd.h> extern char **environ; int execl(const char *path, const char *arg, ...); int execlp(const char *file, const char *arg, ...); int execle(const char *path, const char *arg, ..., char * const envp[]); int execv(const char *path, char *const argv[]); int execvp(const char *file, char *const argv[]); int execve(const char *file, char *const argv[], char *const envp[]);
4.操作系统执行程序的过程
5.进程描述符及任务结构
1.内核把进程的列表存放在叫做任务队列(task list)的双向循环链表中。链表中每一项都是类型为task_struct，称为进程描述符(process descriptor)的结构，该结构定义在<include/linux/sched.h>文件中。进程描述符中包含了一个具体进程的所有信息。
2.所有运行在系统中的进程都以task_struct链表的形式存在内核中；
3.进程的信息可以通过 /proc 系统文件夹查看。要获取PID为400的进程信息，你需要查看 /proc/400 这个文件夹。大多数进程信息同样可以使用top和ps这些用户级工具来获取,例如：
如下为task_struct结构体代码分析
struct task_struct { //进程的运行时状态 volatile long state; /* -1 unrunnable, 0 runnable, >0 stopped */ void *stack; atomic_t usage; //进程当前的状态 /* 0x00000002表示进程正在被创建； 0x00000004表示进程正准备退出； 0x00000040 表示此进程被fork出，但是并没有执行exec； 0x00000400表示此进程由于其他进程发送相关信号而被杀死 。 */ unsigned int flags; /* per process flags, defined below */ unsigned int ptrace; int on_rq; //表示此进程的运行优先级，prio表示动态优先级，根据static_prio和交互性奖罚算出，static_prio是进程的静态优先级，在进程创建时确定，范围从-20到19，越小优先级越高。 int prio, static_prio, normal_prio; //进程的运行优先级 unsigned int rt_priority; //list_head结构体 struct list_head tasks; //mm_struct结构体，描述了进程内存的相关情况 struct mm_struct *mm, *active_mm; /* per-thread vma caching */ u32 vmacache_seqnum; struct vm_area_struct *vmacache[VMACACHE_SIZE]; /* task state */ //进程的状态参数 int exit_state; int exit_code, exit_signal; //父进程退出后信号被发送 int pdeath_signal; /* The signal sent when the parent dies */ /* scheduler bits, serialized by scheduler locks */ unsigned sched_reset_on_fork:1; unsigned sched_contributes_to_load:1; unsigned sched_migrated:1; unsigned sched_remote_wakeup:1; unsigned :0; /* force alignment to the next boundary */ /* unserialized, strictly 'current' */ unsigned in_execve:1; /* bit to tell LSMs we're in execve */ unsigned in_iowait:1; struct restart_block restart_block; //进程号 pid_t pid; //进程组号 pid_t tgid; //进程的亲身父亲 struct task_struct __rcu *real_parent; /* real parent process */ //进程的现在的父亲，可能为继父 struct task_struct __rcu *parent; /* recipient of SIGCHLD, wait4() reports */ //进程的孩子链表 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 */ /* PID/PID hash table linkage. */ struct pid_link pids[PIDTYPE_MAX]; //该进程的所有线程链表 struct list_head thread_group; struct list_head thread_node; //该进程使用cpu时间的信息，utime是在用户态下执行的时间，stime是在内核态下执行的时间。 cputime_t utime, stime; cputime_t gtime; struct prev_cputime prev_cputime; //启动时间，，只是时间基准不一样 u64 start_time; /* monotonic time in nsec */ u64 real_start_time; /* boot based time in nsec */ struct task_cputime cputime_expires; //list_head的CPU时间 struct list_head cpu_timers[3]; //保存进程名字的数组，一般数组大小为15位 char comm[TASK_COMM_LEN]; /* file system info */ //文件系统信息 struct nameidata *nameidata; /* 文件系统信息计数*/ int link_count, total_link_count; /* filesystem information */ //文件系统相关信息结构体 struct fs_struct *fs; /* open file information */ //打开文件信息的结构体 struct files_struct *files; /* namespaces */ struct nsproxy *nsproxy; /* signal handlers */ //信号相关信息的句柄 struct signal_struct *signal; struct sighand_struct *sighand; struct callback_head *task_works; struct audit_context *audit_context; struct seccomp seccomp; /* Thread group tracking */ u32 parent_exec_id; u32 self_exec_id; /* journalling filesystem info */ void *journal_info; /* VM state */ struct reclaim_state *reclaim_state; struct backing_dev_info *backing_dev_info; struct io_context *io_context; unsigned long ptrace_message; siginfo_t *last_siginfo; /* For ptrace use. */ /* * time slack values; these are used to round up poll() and * select() etc timeout values. These are in nanoseconds. */ //松弛时间值，用来记录select和poll的超时时间，单位为ns u64 timer_slack_ns; u64 default_timer_slack_ns; /* CPU-specific state of this task */ //该进程在特定CPU下的状态 struct thread_struct thread; };
具体代码分析：https://blog.csdn.net/xxpresent/article/details/71023637
3.3进程的终止
1.进程开始后，迟早会终止，通常是由下列条件引起的：
* 正常退出（自愿的）
* 出错退出（自愿的）
* 严重错误（非自愿的）
* 被其他进程杀死（非自愿的）2.正常退出的方式：exit()
从图里可以看出来，_exit()函数的作用是: 直接使进程停止运行，清除其使用的内存空间，并清除其在内核中的各种数据结构; 而exit()函数则在这些基础上做了一些包装，在执行退出之前加了若干道工序。
4.操作系统的进程状态如何转换？
进程是操作系统为了控制多个程序而创建的数据，操作系统是通过修改进程的状态来完成对相应程序的控制，用户程序的一些操作也可以修改一些进程的状态。那么进程的状态都有哪些呢？状态之间是如何转换的呢？
如下，我们先给出进程的三态图：
* 运行态
* 阻塞态
* 就绪态
(1) 就绪→执行
处于就绪状态的进程，当进程调度程序为之分配了处理机后，该进程便由就绪状态转变成执行状态。
(2) 执行→就绪
处于执行状态的进程在其执行过程中，因分配给它的一个时间片已用完而不得不让出处理机，于是进程从执行状态转变成就绪状态。
(3) 执行→阻塞
正在执行的进程因等待某种事件发生而无法继续执行时，便从执行状态变成阻塞状态。
(4) 阻塞→就绪
处于阻塞状态的进程，若其等待的事件已经发生，于是进程由阻塞状态转变为就绪状态。5.操作系统中的进程是如何调度的？
主要概念：调度程序负责决定将哪个进程投入运行，何时运行以及运行多长时间。
多任务系统可分为非抢占式多任务和抢占式多任务。Linux提供了抢占式的多任务模式。在此模式下，由调度程序来决定什么时候停止一个进程的运行，以便其他进程能够提到得到执行机会。
O(1)调度器
直到Linxu 2.6.23内核版本中，O(1)调度算法才真正替代为CFS调度算法。不过，O(1）调度算法依然在数以十计的多处理器的环境下尚能表现出近乎完美的性能和可扩展性，拥有着它独特优越性，但是时间证明该调度算法对于调度那些响应时间敏感的程序却有一些先天不足。 接下来，我将具体讲解Linux 2.6.10版本下的O(1)调度器
1.优先级数组
O(1)算法的一个核心数据结构即为prio_array结构体。该结构体中有一个用来表示进程动态优先级的数组queue，它包含了每一种优先级进程所形成的链表。
struct prio_array { int nr_active /* number of tasks in the queue */; unsigned long bitmap[BITMAP_SIZE]; /* priority bitmap */ struct list_head queue[MAX_PRIO]; /* priority queue */ }
这两个prio_array,一个挂着expired task（时间片已经用完的task），另一个挂着active task（时间片尚未用完的task）。当active task为空时，就交换这两个prio_array的指针值就OK了。
2.优先级计算
-
普通进程优先级计算
- 动态计算优先级，计算公式中包含了静态优先级。一般静态优先级越高，进程能分配到的时间片越长。
- 平均睡眠时间越长，计算得到的优先级越高
- 平均睡眠时间也被用来判断进程是否是一个交互式进程
- 动态计算优先级，计算公式中包含了静态优先级。一般静态优先级越高，进程能分配到的时间片越长。
-
实时进程优先级计算
- 实时进程的优先级不会动态修改，而且总是比普通进程的优先级高。
5.对操作系统进程模型的看法
进程作为整个操作系统最核心的理念，尽快并透彻地理解进程是非常重要的。并且，操作系统的版本在不断的更新，而这些核心的理念也在不断地随着社会的发展在不断地发展，掌握好最根本的模型，才能以不变应万变。