| layout | title | category | tags | |||
|---|---|---|---|---|---|---|
post |
进程与线程 |
os |
|
进程(process) 是程序在系统中的一个运行实例。
有四种原因会导致进程的创建：
- 系统初始化
- 某进程通过 系统调用(system call) 创建子进程
- 用户创建新进程
- 一个批处理作业的初始化
实质上，新进程都是由已有进程通过 系统调用 而创建的。
进程的结束通常由以下四种原因引起：
- 完成工作，正常退出
- 遇到错误，自行退出
- 程序错误，被迫结束
- 被其他进程杀死
第二和第三种并不一样。 第二种是程序检测到错误（如输入参数错误等），自行退出。 而第三种是系统检测到错误（如除以0等），然后杀死进程。 但也有系统是把错误信号发给进程，让其处理，而不是直接杀死进程。
所有的新进程都是由旧进程创建，通常把它们分别称为 子进程 和 父进程 。
在类Unix系统中，所有进程都是构成以 init 为根的一棵树。
一般而言，进程都会有三种基本的状态：
- 运行(running) 正在CPU上运行
- 就绪(ready) 已经准备好可以运行
- 阻塞(blocked) 等待某件事情发生后才可以运行，也叫 等待(waiting)
进程在不同状态的转换如下图所示：
系统通过 进程调度器 根据不同的调度算法来转换进程的状态， 提高系统的系统的整体效率和不同进程的竞争公平性。
为了实现进程模型，系统维护着一张 进程表(process table) ， 每个进程都是表上的一项。每项都包含着如进程状态信息、程序计数器、 堆栈指针、内存信息等进程在 运行态 转换时必须保存的信息。 当进程从 运行态 转换到其他状态是，系统会把这些信息压入堆栈， 直到进程重新运行时再从堆栈中加载。
进程是 系统资源 和 执行过程 的集合。 通常把执行过程称作 线程(thread) ，。
在 面向线程设计 的操作系统中，进程只是线程的容器，一个进程可以运行多个线程。
同一进程中的线程共享该进程的资源，如地址空间、全局变量、打开文件、子进程、外设等。 但每个线程都有自己的堆栈、程序计数器、寄存器等，不过线程之间是没有保护的， 即每个线程都可以访问其它线程的堆栈并执行操作。
线程有两种实现方式: 内核线程(kernel thread) ， 用户线程(user thread) 。
用户线程是在用户空间中实现的，内核对线程一无所知。
线程所在的进程必须要有一张 线程表(thread table) ， 记录进程中每个线程的堆栈、程序计数器、寄存器、状态等，就像内核中的 进程表 一样作用。而且各线程的调度必须要由进程自行负责。
用户线程有很多优点：
- 切换时只需更改堆栈指针、程序计数器，比陷入内核的切换要快得多
- 可自定义线程调度算法
当然，也有缺点：
- 难以实现阻塞系统调用。当某个线程被阻塞后，整个进程都被阻塞，内核会切换到其它进程
- 不能使用轮转调度，调度算法很难设计
内核线程是由内核实现，类 Unix 通常用 轻量级线程(lightweight processes, LWP) 指代。
内核线程的线程表保存在内核空间，由内核管理，也由内核完成线程的调度， 所以在实现阻塞系统调用上没有问题，当一个线程阻塞时，内核会运行同一进程的其它线程。
但在内核中创建和撤销线程开销很大，所以线程切换比用户线程要慢得多。
对一些用户请求式服务，传统的做法是将进程阻塞在一个 receive 线程，当消息到达时，
系统把请求交给某个线程处理。
但也有一种方法，但消息到达时，系统创建一个系的处理线程，这种线程称为 弹出式线程 。 由于新线程没有寄存器、堆栈等历史，创建速度非常快，所以， 使用这种方式能够使消息到达与处理开始之间的时间非常短。
进程经常要与其它进程通信，以便协作完成某样工作。 对于 进程间通信(Inter Process Communication, IPC) 有几个基本的问题：
- 进程如何把信息转递给另一个进程
- 进程如何能有序完成协作
主要的 IPC 方式有共享内存、共享文件、管道、消息传递、同步等等。
当多个进程读写某些共享数据时，如果最后的结果取决于进程执行的精确时序， 这种情况称为竞争条件。
如这种情况：
读变量 p -> 令 p++ -> 写 *p
执行时序为：
进程A读 p -> 进程B读 p -> B使 p++ -> B写 *p -> A使 p++ -> A写 *p
显然，此时进程B所写下的数据被进程A给覆盖了，如果按照其它次序执行， 效果又会有所不同。
事实上，只要有多个进程能够同时读写共享数据，就会造成竞争条件。
如果把各进程中读写共享数据的部分称为 临界区域(critical region) 或 临界区(critical section) 则我们要考虑的就是如何使每个时刻只有一个进程处于临界区。
同时，加上其它考虑，一个好的解决方案应该包括以下部分：
- 每个时刻只有一个进程处于其临界区
- 不应对CPU的频率和数量作任何假设
- 临界区外的进程不得阻塞其它进程
- 不得使进程无限等待进入临界区
连续测试一个变量，直到某个值出现，这种方式称为 忙等待(busy waiting) 。 用于忙等待的锁称为 互斥锁(spin lock) 。
这种方案如下面的代码所示。
#define TRUE 1
#define A 0
#define B 1
int turn = A;
/* 进程A的代码 */
while(TRUE) {
while(turn != A); // 检测是否轮到自己
critical_region(); // 进入临界区
turn = B; // 把锁交给其它进程
noncritical_region(); // 进入非临界区
}
/* 进程B的代码 */
while(TRUE) {
while(turn != B);
critical_region();
turn = A;
noncritical_region();
}
每个进程都在进入临界区前都检查锁是否在自己手上，不在的话就不断循环， 直到另一进程把锁交给自己，然后进入临界区。离开临界区后又立即把锁交给其它进程。 之所以叫严格轮换法，是因为锁只能由别的进程给自己，不能主动去获得，使得每个进程只能 One-by-One 的进入临界区，不能出现 ...A-B-B-A... 这种情况。 在进程执行速度差异很大的情况下，很有可能出现一个进程被另一进程的非临界区代码阻塞的情况， 所以，这不是一种好的方案。
1981 年，G.L.Peterson 发现了一种简单的互斥算法，用于解决两个进程间的竞争冒险问题。
#define TRUE 1
#define FALSE 0
#define N 2
int turn;
int interested[N];
void enter_region(int process)
{
int other = 1 - process;
interested[process] = TRUE;
turn = process;
while (turn == process && interested[other] == TRUE);
}
void leave_region(int process)
{
interested[process] = FALSE;
}
当只有一个进程申请资源时，没有其它进程感兴趣，自然就能得到。
当两个进程竞争时，后来者把自己的进程号存入 turn ，并覆盖前者，
这时前者能顺利跳过 while 循环，而后者在前者离开临界区之前都必须忙等待。
Peterson 算法也可以扩展到多个进程间的竞争。
这是一种硬件解决方案。在许多计算机中，有这样一条指令
TSL RX, LOCK
称作 测试并加锁(TEST AND SET LOCK) ，它把内存中一个 字 LOCK 读到 RX 中， 并在 LOCK 对应的地址上写入一个非零数。这是一个原子操作，当该指令执行时， CPU 将锁住总线，其它的 CPU 不能在该指令完成前访问内存。
具体的方案如下所示：
enter_region:
TSL REGISTER, LOCK -- 复制锁到寄存器，并把锁置 1
CMP REGISTER, #0 -- 比较锁是否为 0
JNE enter_region -- 若不是 0，说明以上锁，循环检测
RET -- 返回，进入临界区
leave_region:
MOVE LOCK, #0 -- 已退出临界区，把锁置 0
RET -- 返回
各进程只须在进入临界区前执行 enter_region ，退出临界区后调用 leave_region ，
就可以避免竞争冒险出现。