进程管理

一、进程

1.1 进程定义

进程是对正在运行中程序的一种抽象，操作系统所有的内容都是围绕进程展开。

在许多多道程序系统中，CPU会在进程间快速切换，使每个程序运行几十或者几百毫秒。然而，严格意义来说，在某一个瞬间，CPU只能运行一个进程，然而我们如果把时间定位为1秒内的话，它可能运行多个进程。这样就会让我们产生并行的错觉。有时候人们说的伪并行(pseudoparallelism)就是这种情况，以此来区分多处理器系统(该系统由两个或多个CPU来共享同一个物理内存)

进程实体=程序段+相关数据段+PCB(进程控制块)

进程是资源分配的基本单位。

进程控制块 (Process Control Block, PCB) 描述进程的基本信息和运行状态，所谓的创建进程和撤销进程，都是指对 PCB 的操作。

下图显示了 4 个程序创建了 4 个进程，这 4 个进程可以并发地执行。

在一个给定的时间只有一个线程在运行

1.2 进程的执行

1.2.1 顺序执行

顺序性。每个操作都必须在前一个操作结束后才能开始
封闭性。程序一旦开始运行，其运行结果不会受到外界因素的影响
可再现性。程序运行结果仅由初始结果和程序本身的操作决定

1.2.2 并发执行

在计算机引入通道和中断机制后，就使得CPU和外部设备之间，以及外部设备与外部设备之间可以并行操作，使得多道程序设计成为可能。

在同一时刻，有的程序占用CPU运行，有的程序通过外部设备传递数据。从宏观上看是多个设备同时运行，从微观上来看它们是在交替运行。

因此，程序并发执行环境下的计算机资源，已不再被某一个用户程序所独占，而是由多个并发执行的程序所共享。虽然提高了资源的利用率，但在另外一方面却引发了多个并发程序对资源的竞争导致了程序执行环境与运行速度的改变，从而可能产生程序运行结果不唯

间断性
无封闭性
不可再现性

1.3 进程特点

动态性。进程具有生命期，具有“创建-运行-消亡”这样一个过程
并发性。多个进程能够在一段时间内并发执行
独立性。每个进程都是一个独立运行的基本单位，也是系统进行资源分配和调度的基本单位
异步性。任何时刻只能有一个进程占用CPU，具有“执行-暂停-执行”这种间断性规律
结构性。由程序段、相关数据段、PCB三部分组成

1.4 进程和程序的区别

程序是静态的，进程是动态的

两这不是一一对应关系，一个程序对应多个进程，一个进程可以保护多个程序

1.5 进程状态

新建
当需要创建一个新进程时，系统为该进程分配一个进程控制块PCB，并为该进程分配内存空间，且装入该进程对应的程序和有关数据。
就绪
进程得到除了CPU之外的所需资源，一旦得到CPU资源既可以立即投入运行。
运行
进程获得了CUP和其他所需要的资源，目前正在CPU上运行
阻塞
进程运行过程中发生了某种等待事件（比如发生了I/O操作）而暂时不能运行的状态。即使把CPU资源分配给它也不能够运行。
结束
系统逐步释放为为其分配的资源，最后释放其PCB.

就绪状态（ready）：等待被调度
运行状态（running）
阻塞状态（waiting）：等待资源(如I/O资源)

注意

只有就绪态和运行态可以相互转换，其它的都是单向转换。就绪状态的进程通过调度算法从而获得 CPU 时间，转为运行状态；而运行状态的进程，在分配给它的 CPU 时间片用完之后就会转为就绪状态，等待下一次调度。
阻塞状态是缺少需要的资源从而由运行状态转换而来，但是该资源不包括 CPU 时间，缺少 CPU 时间会从运行态转换为就绪态。

二、线程

2.1线程的定义

在引入进程后，由于进程此时是资源分配的基本单位也是独立调度独立运行的基本单位。同时扮演连个角色，导致进程的并发执行产生了很大空间开销。因此引入了线程。将一个进程分解为多个线程。

线程属于轻型实体，基本不拥有系统资源
线程是独立调度和分配的基本单位，也是能够独立运行的基本单位
同一个进程的所有线程共享该进程的所拥有的全部资源
线程的并发执行程度高，不但同一进程的多个线程可以并发执行，甚至属于不同进程的多个线程也可以并发执行

与进程类似，线程也有生命周期，也存在执行、就绪和阻塞这三种基本状态，这是因为线程完全继承了进程的运行属性，因此线程的三种状态含义和转换关系与进程相同。由于线程不是资源的拥有单位，因此挂起状态对单个线程没有意义。

为了使并发的多个线程能够有条不紊地运行，操作系统必须提供用于线程间互斥和同步的机制：

互斥锁，每次只允许一个线程来执行特定的代码或访问特定的数据。
读写锁，对受保护的共享资源进行并发读取和独占写入。
条件变量，一直阻塞线程，直到特定的条件为真。
奇数信号量，用来协调对资源的访问，达到指定的计数时信号将阻塞。

2.2 与进程的区别

Ⅰ 拥有资源

进程是资源分配的基本单位，但是线程不拥有资源，线程可以访问隶属进程的资源。

Ⅱ 调度

线程是独立调度的基本单位，在同一进程中，线程的切换不会引起进程切换，从一个进程中的线程切换到另一个进程中的线程时，会引起进程切换。

Ⅲ 系统开销

由于创建或撤销进程时，系统都要为之分配或回收资源，如内存空间、I/O 设备等，所付出的开销远大于创建或撤销线程时的开销。类似地，在进行进程切换时，涉及当前执行进程 CPU 环境的保存及新调度进程 CPU 环境的设置，而线程切换时只需保存和设置少量寄存器内容，开销很小。

Ⅳ 通信方面

线程间可以通过直接读写同一进程中的数据进行通信，但是进程通信需要借助 IPC。

三、进程间通信

进程间通信ICP

3.1 临界资源与临界区

把同一时刻只允许一个进程使用的资源成为临界资源。

对临界资源的访问必须互斥进行，即各个进程对同一临界资源进行先从操作的程序段也应互斥进行，只有这样才能保证对临界资源的互斥访问。把进程中访问临界资源的代码称为临界区。

对于临界资源的访问必须互斥进行，所以进程在进入临界区时首先判断是否有其他进程在使用此临界资源，如果有，则该进程必须等待；如果没有，则该进程才能进入临界区执行临界区代码，同时还要关闭临界区以防止其他进程进入。当进程使用完临界资源时，要开放临界区以便其他进程进入。

临界资源是数据结构，临界区是访问该数据结构的代码片段

3.2 同步与互斥

同步：多个进程因为合作产生的直接制约关系，使得进程有一定的先后执行关系。
互斥：多个进程在同一时刻只有一个进程能进入临界区。

3.3 互斥访问临界资源的方法

3.3.1 从软件角度来看

单标志变量(有些同学不信邪)
勉强能用的两标志法
聪明人才能想出的三标志法(扩展性不行)

3.3.2 依靠系统支持

关中断大法(时间停止大法)

又称硬件锁，进程在进入临界区之前，先执行“关中断”指令来屏蔽掉所有中断，进程完成所有临界区的任务后，再执行“开中断”指令将中断打开。

缺点：开关中断时间过长会导致系统效率降低。

加锁法

锁不是一般的标志变量(否则锁本身就成了临界资源)
lock/unlock要做成原语
“关中断……关中断”做原语的方式是不行的，得固化成指令
缺点：忙等

3.4 信号量（重点）

信号量（Semaphore）是一个整型变量，可以对其执行 down 和 up 操作，也就是常见的 P 和 V 操作。

信号量的初值是一个非负整数，随着不断分配，value的值的情况：

value>0，代表该类资源当前的可用数量
value=0，表示该资源为空
value<0，其绝对值代表因等待该资源而阻塞的进程数量

down : 如果信号量大于 0 ，执行 -1 操作；如果信号量等于 0，进入阻塞队列中，等待信号量大于 0；
up ：对信号量执行 +1 操作，唤醒睡眠的进程让其完成 down 操作。

down 和 up 操作需要被设计成原语，不可分割，通常的做法是在执行这些操作的时候屏蔽中断。

如果信号量的取值只能为 0 或者 1，那么就成为了 互斥量（Mutex） ，0 表示临界区已经加锁，1 表示临界区解锁。

P、V信号量解决了进程主动进行循环测试消耗系统资源的问题。因为这种协调的本质是当出现资源竞争的冲突时，就将原来并发执行的多个进程在P、V操作的协调下变为依次顺序执行，当资源冲突结束后又恢复为并发执行。

使用信号量实现生产者-消费者问题

问题描述：使用一个缓冲区来保存物品，只有缓冲区没有满，生产者才可以放入物品；只有缓冲区不为空，消费者才可以拿走物品。

因为缓冲区属于临界资源，因此需要使用一个互斥量 mutex 来控制对缓冲区的互斥访问。

为了同步生产者和消费者的行为，需要记录缓冲区中物品的数量。数量可以使用信号量来进行统计，这里需要使用两个信号量：empty 记录空缓冲区的数量，full 记录满缓冲区的数量。其中，empty 信号量是在生产者进程中使用，当 empty 不为 0 时，生产者才可以放入物品；full 信号量是在消费者进程中使用，当 full 信号量不为 0 时，消费者才可以取走物品。

注意，不能先对缓冲区进行加锁，再测试信号量。也就是说，不能先执行 down(mutex) 再执行 down(empty)。如果这么做了，那么可能会出现这种情况：生产者对缓冲区加锁后，执行 down(empty) 操作，发现 empty = 0，此时生产者睡眠。消费者不能进入临界区，因为生产者对缓冲区加锁了，消费者就无法执行 up(empty) 操作，empty 永远都为 0，导致生产者永远等待下，不会释放锁，消费者因此也会永远等待下去。

3.5 互斥量

如果不需要信号量的计数能力时，可以使用信号量的一个简单版本，称为mutex(互斥量) 。互斥量的优势就在于在一-些共享资源和一段代码中保持互斥。由于互斥的实现既简单又有效，这使得互斥量在实现用户空间线程包时非常有用。
互斥量是一个处于两种状态之一的共享变量:解锁(unlocked)和加锁(locked) 。这样，只需要一个二进制位来表示它，不过一般情况下，通常会用一个整形(integer) 来表示。 0表示解锁，其他所有的值表示加锁，比1大的值表示加锁的次数。

3.6 管程

使用信号量机制实现的生产者消费者问题需要客户端代码做很多控制，而管程把控制的代码独立出来，不仅不容易出错，也使得客户端代码调用更容易。

管程有一个重要特性：在一个时刻只能有一个进程使用管程。进程在无法继续执行的时候不能一直占用管程，否则其它进程永远不能使用管程。

管程引入了 条件变量 以及相关的操作：wait() 和 signal() 来实现同步操作。对条件变量执行 wait() 操作会导致调用进程阻塞，把管程让出来给另一个进程持有。signal() 操作用于唤醒被阻塞的进程。

3.7 进程同步问题

哲学家进餐问题

五个哲学家围着一张圆桌，每个哲学家面前放着食物。哲学家的生活有两种交替活动：吃饭以及思考。当一个哲学家吃饭时，需要先拿起自己左右两边的两根筷子，并且一次只能拿起一根筷子。

为了防止死锁的发生，可以设置两个条件：

必须同时拿起左右两根筷子；
只有在两个邻居都没有进餐的情况下才允许进餐。

读者-写者问题

允许多个进程同时对数据进行读操作，但是不允许读和写以及写和写操作同时发生。

一个整型变量 count 记录在对数据进行读操作的进程数量，一个互斥量 count_mutex 用于对 count 加锁，一个互斥量 data_mutex 用于对读写的数据加锁。

3.8 进程通信

进程同步与进程通信很容易混淆，它们的区别在于：

进程同步：控制多个进程按一定顺序执行；
进程通信：进程间传输信息。

1. 管道

管道是通过调用 pipe 函数创建的，fd[0] 用于读，fd[1] 用于写。

它具有以下限制：

只支持半双工通信（单向交替传输）；
只能在父子进程或者兄弟进程中使用。

2. FIFO

也称为命名管道，去除了管道只能在父子进程中使用的限制。

FIFO 常用于客户-服务器应用程序中，FIFO 用作汇聚点，在客户进程和服务器进程之间传递数据。

3. 消息队列

相比于 FIFO，消息队列具有以下优点：

消息队列可以独立于读写进程存在，从而避免了 FIFO 中同步管道的打开和关闭时可能产生的困难；
避免了 FIFO 的同步阻塞问题，不需要进程自己提供同步方法；
读进程可以根据消息类型有选择地接收消息，而不像 FIFO 那样只能默认地接收。

4. 信号量

它是一个计数器，用于为多个进程提供对共享数据对象的访问。

5. 共享存储

允许多个进程共享一个给定的存储区。因为数据不需要在进程之间复制，所以这是最快的一种 IPC。

需要使用信号量用来同步对共享存储的访问。

多个进程可以将同一个文件映射到它们的地址空间从而实现共享内存。另外 XSI 共享内存不是使用文件，而是使用内存的匿名段。

6. 套接字

与其它通信机制不同的是，它可用于不同机器间的进程通信。

四、调度

4.1 批处理系统

批处理系统没有太多的用户操作，在该系统中，调度算法目标是保证吞吐量和周转时间（从提交到终止的时间）。

1.1 先来先服务 first-come first-serverd（FCFS）

非抢占式的调度算法，按照请求的顺序进行调度。

有利于长作业，但不利于短作业，因为短作业必须一直等待前面的长作业执行完毕才能执行，而长作业又需要执行很长时间，造成了短作业等待时间过长。

1.2 短作业优先 shortest job first（SJF）

非抢占式的调度算法，按估计运行时间最短的顺序进行调度。

长作业有可能会饿死，处于一直等待短作业执行完毕的状态。因为如果一直有短作业到来，那么长作业永远得不到调度。

1.3 最短剩余时间优先 shortest remaining time next（SRTN）

最短作业优先的抢占式版本，按剩余运行时间的顺序进行调度。当一个新的作业到达时，其整个运行时间与当前进程的剩余时间作比较。如果新的进程需要的时间更少，则挂起当前进程，运行新的进程。否则新的进程等待。

4.2 交互式系统

交互式系统有大量的用户交互操作，在该系统中调度算法的目标是快速地进行响应。

4.2.1 时间片轮转

将所有就绪进程按 FCFS 的原则排成一个队列，每次调度时，把 CPU 时间分配给队首进程，该进程可以执行一个时间片。当时间片用完时，由计时器发出时钟中断，调度程序便停止该进程的执行，并将它送往就绪队列的末尾，同时继续把 CPU 时间分配给队首的进程。

时间片轮转算法的效率和时间片的大小有很大关系：

因为进程切换都要保存进程的信息并且载入新进程的信息，如果时间片太小，会导致进程切换得太频繁，在进程切换上就会花过多时间。
而如果时间片过长，那么实时性就不能得到保证。

4.2.2 优先级调度

为每个进程分配一个优先级，按优先级进行调度。

为了防止低优先级的进程永远等不到调度，可以随着时间的推移增加等待进程的优先级。

4.2.3 多级反馈队列

一个进程需要执行 100 个时间片，如果采用时间片轮转调度算法，那么需要交换 100 次。

多级队列是为这种需要连续执行多个时间片的进程考虑，它设置了多个队列，每个队列时间片大小都不同，例如 1,2,4,8,..。进程在第一个队列没执行完，就会被移到下一个队列。这种方式下，之前的进程只需要交换 7 次。

每个队列优先权也不同，最上面的优先权最高。因此只有上一个队列没有进程在排队，才能调度当前队列上的进程。

可以将这种调度算法看成是时间片轮转调度算法和优先级调度算法的结合。

3. 实时系统

实时系统要求一个请求在一个确定时间内得到响应。

分为硬实时和软实时，前者必须满足绝对的截止时间，后者可以容忍一定的超时。

参考

线程与进程