1.进程与线程
1.0 进程：
-
进程是正在运行的程序的实例（an instance of a computer program that is being executed）。
-
进程是一个具有一定独立功能的程序关于某个数据集合的一次运行活动。它是操作系统动态执行的基本单元，在传统的操作系统中，进程既是基本的分配单元，也是基本的执行单元。
1.1 线程：
-
线程，有时被称为轻量级进程(Lightweight Process，LWP），是程序执行流的最小单元。
1.2 进程与线程的关系和区别：
-
进程是资源的分配和调度的一个独立单元，而线程是CPU调度的基本单元。
-
同一个进程中可以包括多个线程，并且线程共享整个进程的资源（寄存器、堆栈、上下文），一个进程至少包括一个线程。
-
进程在执行过程中拥有独立的内存单元，而多个线程共享内存，从而极大地提高了程序的运行效率。
-
线程是轻两级的进程，它的创建和销毁所需要的时间比进程小很多，所有操作系统中的执行功能都是创建线程去完成的。
-
每个独立的进程有一个程序运行的入口、顺序执行序列和程序的出口。但是线程不能够独立执行，必须依存在应用程序中，由应用程序提供多个线程执行控制。
-
线程有自己的私有属性TCB，线程id，寄存器、硬件上下文，而进程也有自己的私有属性进程控制块PCB，这些私有属性是不被共享的，用来标示一个进程或一个线程的标志。
2.Linux简介
2.0 定义：
-
Linux是一套免费使用和*传播的类Unix操作系统，是一个基于POSIX和UNIX的多用户、多任务、支持多线程和多CPU的操作系统。它能运行主要的UNIX工具软件、应用程序和网络协议。它支持32位和64位硬件。Linux继承了Unix以网络为核心的设计思想，是一个性能稳定的多用户网络操作系统。
2.1 特性：
-
多用户、多任务：Linux支持多用户，各个用户对于自己的文件设备有自己特殊的权利，保证了各用户之间互不影响。多任务则是现在电脑最主要的一个特点，Linux可以使多个程序同时并独立地运行。
-
良好的界面：Linux同时具有字符界面和图形界面。在字符界面用户可以通过键盘输入相应的指令来进行操作。它同时也提供了类似Windows图形界面的X-Window系统，用户可以使用鼠标对其进行操作。在X-Window环境中就和在Windows中相似，可以说是一个Linux版的Windows。
-
支持多种平台：Linux可以运行在多种硬件平台上，如具有x86、680x0、SPARC、Alpha等处理器的平台。此外Linux还是一种嵌入式操作系统，可以运行在掌上电脑、机顶盒或游戏机上。2001年1月份发布的Linux 2.4版内核已经能够完全支持Intel 64位芯片架构。同时Linux也支持多处理器技术。多个处理器同时工作，使系统性能大大提高。
-
文件系统：包含纯文本文件（ASCII）、二进制文件（binary）、数据格式的文件（data）。
3.Linux系统下进程的组织
3.0 标识符：
- 每个进程有进程标识符、用户标识符、组标识符。
| 域名 |
含义 |
| Pid |
进程标识符 |
| Uid、gid |
用户标识符、组标识符 |
| Euid、egid |
有效用户标识符、有效组标识符 |
| Suid、sgid |
备份用户标识符、备份组标识符 |
| Fsuid、fsgid |
文件系统用户标识符、文件系统组标识符 |
3.1 进程查看：
-
可以使用ps命令。它能显示当前运行中进程的相关信息，包括进程的PID。
-
ps -aux ##可以看到所有运行的程序与grep连用筛选
ps -a ##显示现行终端机下的所有程序（包括其他用户的程序）
ps -u ##以用户为主的排序显示（username）
ps -x ##显示所有程序（包括所有终端机下的）
3.2 进程创建：
-
fork（） ：fork创建一个进程时，子进程只是完全复制父进程的资源，复制出来的子进程有自己的task_struct结构和pid,但却复制父进程其它所有的资源。
#include <sys/types.h> #include <unistd.h> pid_t fork(void);
正确返回：在父进程中返回子进程的进程号，在子进程中返回0 ；错误返回：-1 。
-
vfolk（）：vfork系统调用不同于fork，用vfork创建的子进程与父进程共享地址空间，也就是说子进程完全运行在父进程的地址空间上，如果这时子进程修改了某个变量，这将影响到父进程。
#include <sys/types.h> #include <unistd.h> pid_t vfork(void);
正确返回：在父进程中返回子进程的进程号，在子进程中返回0 ；错误返回：-1 。
-
clone（）：fork()是全部复制，vfork()是共享内存，而clone() 是则可以将父进程资源有选择地复制给子进程，而没有复制的数据结构则通过指针的复制让子进程共享，具体要复制哪些资源给子进程，由参数列表中的 clone_flags来决定。另外，clone()返回的是子进程的pid。
#include <sched.h> int clone(int (*fn)(void *), void *child_stack, int flags, void *arg);
正确返回：返回所创建进程的PID，函数中的flags标志用于设置创建子进程时的相关选项 ； 错误返回：-１ 。
3.3 进程终止：
-
exit（）：
#include <stdio.h> #include <stdlib.h> int main() { printf("Using exit\n"); printf("This is the content in buffer"); exit(0); } //运行结果： Using exit This is the content in buffer
-
_exit（）：
#include <stdio.h> #include <stdlib.h> #include <unistd.h> int main() { printf("Using exit\n"); printf("This is the content in buffer"); _exit(0); } //运行结果： Using exit
exit和_exit函数都是用来终止进程的。当程序执行到exit和_exit时，进程会无条件的停止剩下的所有操作，清除包括PCB在内的各种数据结构，并终止本程序的运行。exit可输出缓冲区数据，_exit不可输出缓冲区数据。 -
abort（）：
#include <stdio.h> #include <stdlib.h> int main() { FILE *stream; if((stream = fopen("nofilehere", "r")) == NULL) { perror("Can not open"); abort(); } else { fclose(stream); } return 0; }
abort()是使异常程序终止，同时发送SIGABRT信号给调用进程。
3.4 进程管理命令
-
ps： 'ps'是Linux 中最基础的浏览系统中的进程的命令。能列出系统中运行的进程，包括进程号、命令、CPU使用量、内存使用量等。
-
pstree： linux中，每一个进程都是由其父进程创建的。此命令以可视化方式显示进程，通过显示进程的树状图来展示进程间关系。
-
top: ‘top’是一个更加有用的命令，可以监视系统中不同的进程所使用的资源。它提供实时的系统状态信息。显示进程的数据包括 PID、进程属主、优先级、%CPU、%memory等。可以使用这些显示指示出资源使用量。
-
htop: htop与top很类似，但是htop是交互式的文本模式的进程查看器。它通过文字图形化地显示每一个进程的CPU和内存使用量、swap使用量。使用上下光标键选择进程，F7和F8改变优先级，F9杀死进程。Htop不是系统默认安装的，所以需要额外安装。
-
nice: 通过nice命令的帮助，用户可以设置和改变进程的优先级。提高一个进程的优先级，内核会分配更多CPU时间片给这个进程。默认情况下，进程以0的优先级启动。进程优先级可以通过top命令显示的NI（nice value）列查看。
-
renice: renice命令类似nice命令。使用这个命令可以改变正在运行的进程优先值。注意，用户只能改变属于他们自己的进程的优先值。
-
kill: 这个命令用于发送信号来结束进程。如果一个进程没有响应杀死命令，这也许就需要强制杀死，使用-9参数来执行。
-
ulimit: 该命令用于控制系统资源在shell和进程上的分配量。对于系统管理员是最有用的，可以管理重度使用和存在性能问题的系统。限制资源大小可以确保重要进程持续运行，其他进程不会占用过多资源。
-
w: w 提供当前登录的用户及其正在执行的进程的信息。显示信息头包含信息，如当前时间、系统运行时长、登录用户总数、过去的1，5，15分钟内的负载均衡数。
-
pgrep: pgrep的意思是"进程号全局正则匹配输出"。该命令扫描当前运行进程，然后按照命令匹配条件列出匹配结果到标准输出。对于通过名字检索进程号是很有用。
-
fg , bg：有时，命令需要很长的时间才能执行完成。对于这种情况，我们使用‘bg’命令可以将任务放在后台执行，而用‘fg’可以调到前台来使用。
-
ipcs: ipcs命令报告进程间通信设施状态。（共享内存，信号量和消息队列）；用-p参数联合-m、-s或-q使用，可以获得相关的进程间通信的进程ID。
4.Linux下进程的状态
4.0 六种状态：
-
R (TASK_RUNNING)，可执行状态。
-
S (TASK_INTERRUPTIBLE)，可中断的睡眠状态。
-
D (TASK_UNINTERRUPTIBLE)，不可中断的睡眠状态。
-
T (TASK_STOPPED or TASK_TRACED)，暂停状态或跟踪状态。
-
Z (TASK_DEAD - EXIT_ZOMBIE)，退出状态，进程成为僵尸进程。
-
X (TASK_DEAD - EXIT_DEAD)，退出状态，进程即将被销毁。
4.1 状态转换图：
5.Linux下进程的调度
5.0 简介：
-
Linux进程调度采用的是抢占式多任务处理，所以进程之间的挂起和继续运行无需彼此之间的协作。
-
Linux在进行进程调度的时候把进程分为两种：1.普通进程；2.实时进程；实时进程的优先级永远比普通进程的优先级高。
-
SCHED_OTHER 分时调度策略。
-
SCHED_FIFO实时调度策略，先到先服务。
-
SCHED_RR实时调度策略，时间片轮转。
5.2 进程优先级：
-
使用nice值：越大的nice值意味着更低的优先级。 (-19 ~ 20之间)
-
实时优先级：可配置，越高意味着进程优先级越高。
-
时间片：Linux中并不是以固定的时间值(如10ms)来分配时间片的，而是将处理器的使用比作为“时间片”划分给进程。
5.3 O(1)调度算法：
-
算法介绍：在Linux2.6版中，O(1)调度被采用，它是对非实时进程进行调度的一种调度算法。
-
数据结构：在O(1)调度中，要问最重要的数据结构是运行队列。运行队列描绘了进程队列的结构，在内核源码中用runqueue结构体表示。
struct runqueue { unsigned long nr_running; task_t *curr; prio_array_t *active,*expired,arrays[2]; };
- 优先级数组:O(1)算法的另一个核心数据结构即为prio_array结构体。该结构体中有一个用来表示进程动态优先级的数组queue，它包含了每一种优先级进程所形成的链表。
-
#define MAX_USER_RT_PRIO 100 #define MAX_RT_PRIO MAX_USER_RT_PRIO #define MAX_PRIO (MAX_RT_PRIO + 40) typedef struct prio_array prio_array_t; struct prio_array { unsigned int nr_active; unsigned long bitmap[BITMAP_SIZE]; struct list_head queue[MAX_PRIO]; };
-
静态优先级和动态优先级：进程有两个优先级,一个是静态优先级,一个是动态优先级.静态优先级是用来计算进程运行的时间片长度的,动态优先级是在调度器进行调度时用到的,调度器每次都选取动态优先级最高的进程运行. 静态优先级的计算:
nice值和静态优先级之间的关系是：静态优先级=100+nice+20 而nice值的范围是-20～19，所以普通进程的静态优先级的范围是100～139
进程运行的时间片长度的计算:
静态优先级<120，基本时间片=max((140-静态优先级)*20, MIN_TIMESLICE) 静态优先级>=120，基本时间片=max((140-静态优先级)*5, MIN_TIMESLICE)
其中MIN_TIMESLICE为系统规定的最小时间片.从该计算公式可以看出,静态优先级越高（值越低),进程得到的时间片越长。 动态优先级的计算:
动态优先级=max(100 , min(静态优先级 – bonus + 5 , 139))
从上面看出,动态优先级的生成是以静态优先级为基础,再加上相应的惩罚或奖励(bonus).这个bonus并不是随机的产生,而是根据进程过去的平均睡眠时间做相应的惩罚或奖励.交互性强的进程会得到调度程序的奖励（bonus为正）,而那些一直霸占CPU的进程会得到相应的惩罚（bonus为负）。
-
调度算法：Linux2.4版本的内核调度算法理解起来简单：在每次进程切换时，内核依次扫描就绪队列上的每一个进程，计算每个进程的优先级，再选择出优先级最高的进程来运行；尽管这个算法理解简单，但是它花费在选择优先级最高进程上的时间却不容忽视。系统中可运行的进程越多，花费的时间就越大，时间复杂度为O(n)。伪代码如下：
for (系统中的每个进程) { 重新计算时间片; 重新计算优先级; }
而2.6内核所采用的O(1)算法则很好的解决了这个问题，该算法可以在恒定的时间内为每个进程重新分配好时间片，而且在恒定的时间内可以选取一个最高优先级的进程，重要的是这两个过程都与系统中可运行的进程数无关，这也正是该算法取名为O(1)的缘故。
-
时间片：O(1)算法采用过期进程数组和活跃进程数组解决以往调度算法所带来的O(n)复杂度问题。过期数组中的进程都已经用完了时间片，而活跃数组的进程还拥有时间片。当一个进程用完自己的时间片后，它就被移动到过期进程数组中，同时这个过期进程在被移动之前就已经计算好了新的时间片。可以看到O(1)调度算法是采用分散计算时间片的方法，并不像以往算法中集中为所有可运行进程重新计算时间片。当活跃进程数组中没有任何进程时，说明此时所有可运行的进程都用完了自己的时间片。那么此时只需要交换一下两个数组即可将过期进程切换为活跃进程，进而继续被调度程序所调度。两个数组之间的切换其实就是指针之间的交换，因此花费的时间是恒定的。下面的代码说明了两个数组之间的交换：
struct prop_array *array = rq->active; if (array->nr_active != 0) { rq->active = rq->expired; rq->expired = array; }
通过分散计算时间片、交换过期和活跃两个进程集合的方法可以使得O(1)算法在恒定的时间内为每个进程重新计算好时间片。
-
算法简介：从Linux2.6.23开始，考虑到O(1)调度的一些不足以及公平性方面的缺陷，所以改用完全公平调度（CFS）算法。
-
权重：普通进程的优先级为100～139，并且优先级是可以通过nice值修改的，nice值的范围为-20～19。而在CFS调度中，进程的权重与优先级有关，优先级越高，权重越大。并且优先级到权重的转换有一个经验公式，经验公式如下所示：
static const int prio_to_weight[40] = { /* -20 */ 88761, 71755, 56483, 46273, 36291, /* -15 */ 29154, 23254, 18705, 14949, 11916, /* -10 */ 9548, 7620, 6100, 4904, 3906, /* -5 */ 3121, 2501, 1991, 1586, 1277, /* 0 */ 1024, 820, 655, 526, 423, /* 5 */ 335, 272, 215, 172, 137, /* 10 */ 110, 87, 70, 56, 45, /* 15 */ 36, 29, 23, 18, 15, };548, 7620, 6100, 4904, 3906,
可以看到, nice值越小, 进程的权重越大。
CFS调度器的一个调度周期值是固定的, 由sysctl_sched_latency变量保存.
一个进程在一个调度周期中的运行时间为:
分配给进程的运行时间 = 调度周期 * 进程权重 / 所有进程权重之和
可以看到, 进程的权重越大, 分到的运行时间越多。
-
虚拟运行时间：为了实现公平，开发者将虚拟运行时间引入到CFS调度中来取代优先级对于选择进程运行的决定地位，在内核源码中用vruntime字段来表示虚拟运行时间。并且在CFS中主要有两个要素可以决定进程的虚拟运行时间，它们分别是进程的权重和进程实际运行的时间。调度器总是调度虚拟运行时间最小的进程，并且在每一次时钟中断到来时，内核都要重新计算当前进程的虚拟运行时间，计算公式如下：
vruntime = 进程在一个调度周期内的实际运行时间 * NICE_0_LOAD / 进程权重 = (调度周期 * 进程权重 / 所有进程总权重) * NICE_0_LOAD / 进程权重 = 调度周期 * NICE_0_LOAD / 所有进程总权重
NICE_0_LOAD = 1024, 表示nice值为0的进程权重。
由上述公式可以看出正在运行的进程的虚拟运行时间随着运行时间的增长而增长，当它的虚拟运行时间不是可运行态进程中的最小值时它就会被其它可运行态进程抢占，而且能够看出虚拟运行时间与当前进程运行的时间、当前进程的权重的关系是：虚拟运行时间与当前进程运行的时间成正比，与当前进程的权重成反比。
由此可见，当一个进程的优先级越高，运行的时间越少时，这个进程的虚拟运行时间就越小，此进程就越应该被调度执行。 -
红黑树 ：相比于O(1)调度，CFS调度没有用运行队列来维护可运行态进程，而是用红黑树来组织普通进程。红黑树本质上是一颗二叉查找树，它具有以下5个特点：
（1）每个叶结点都是空结点，并且它们是黑色的；
（2）根结点是黑色的；
（3）红色结点的子结点必定是黑色的；
（4）对于任意结点而言，其到叶节点的每条路径上的黑色结点的数目都相同；
（5）每个结点不是黑色就是红色。
这些特点决定了红黑树是自平衡的，虽然红黑树没有达到恒定O(1)的时间复杂度但是它最差的时间复杂度也为O(logn)，这就决定了它可以在插入和删除等操作上表现得非常高效。
CFS使用的红黑树是以时间为顺序的，它的结点由调度实体来描述，关于调度实体的概念将在下一节组调度中介绍，而进程的虚拟运行时间和权重也存放在这个结构中，下图描绘了CFS中红黑树的结构。
内核通过红黑树来对虚拟运行时间进行排序，红黑树的最左侧结点的虚拟运行时间最少，所以该结点所表示的进程将是下一个要被调度的进程。
- 组调度：Linux系统中不仅有进程而且也有进程组，所以在CFS中支持对进程组的调度，即CFS组调度。因为组中进程的task_struct不能完成对所属进程组的调度，所以为了解决这个问题，CFS引入了调度实体，也就是一个调度单位的概念，在内核源码中用sched_entity字段表示。进程和进程组的与调度相关的信息都被保存在调度实体中，比如虚拟运行时间和权重。当内核关闭组调度的使用时，调度实体就等同于进程。 CFS引入组调度是为了将以进程为单位的调度扩展到以用户为单位的调度，即将进程的归属按用户划分，每个用户拥有一个进程组，组中有一些进程。当进行组调度时，先选择用户，然后才选择用户所拥有进程组中的某一个进程。这样的话每个用户的进程组被调度的机率相同，用户享有相同比例的CPU时间，防止了当A用户的进程的权重远高于B用户的进程的权重时，B用户的进程只能等A用户的进程全部运行完了之后才能运行的情况，这样体现了用户间的公平性。
6.浅谈Linux进程模型
-
进程作为操作系统重要的核心之一，其发展形成经过了上万名高级程序员之手，千万级别的代码量，可见其工程的浩大。在不断地改革创新之后，进程模型渐臻完美，然而仍存在不足，例如：程序并发执行时付出了巨大的时空开销，每个进程在进行切换时身上带了过多的“累赘”导致系统效率降低，故而引入了线程。
-
进程模型建立在大量的数据结构基础上，不断地翻陈出新，如由早期的Linux 2.1版本的O(n)调度器到 Linux 2.6版本的O(1)调度器再到CFS调度器。
-
进程模型作为人类的高智慧集中产物，基于人类科学，在硬件的基础上实现软件层面的诸多功能，其深奥的原理仍有待我们进一步学习探究。
7.参考链接