计算机操作系统进程管理总结

计算操作系统进程管理

一、进程与线程

1.1、进程

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

进程控制块PCB（Process Control Block）描述的是进程的基本信息以及进程的运行状态，我们说的创建及撤销进程都是对进程控制块PCB的操作。

进程之间可以并发执行。

一个程序中可以有多个进程。

1.2、线程

线程是独立调度的基本单位。

一个进程中可以有多个线程，他们之间共享进程资源。

1.3、进程和线程的区别

• 拥有资源：进程是资源分配的基本单位，但是线程不能进行资源分配，不能拥有资源，但是线程可以访问隶属于进程的资源。
• 调度：线程是独立调度的基本单位，但在同一进程中，线程的切换不会引起进程的切换，如果，从一个进程内的线程切换到另一个进程中的线程，就会引起进程的切换。
• 系统开销：因为创建和撤销进程时，系统都要为其分配或者回收资源，如内存空间，I/O设备等，所付出的系统开销远大于创建或撤销线程时所需的开销。类似地，在进行进程切换时，涉及到当前进程CPU环境的保存及新调度进程CPU环境的设置；而在线程切换时只需要保存和设置少量寄存器内容，系统开销很小。
• 通信方面：进程间通信（IPC）需要进程同步和互斥手段辅助，以保证数据的一致性。而线程之间的通信可以通过直接读/写同一进程中的数据段（例如：全局变量）来进行通信。

二、进程状态的切换

我们需要注意的是：

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

三、调度算法

这里我们根据不同的运行环境来讨论调度算法

3.1、批处理系统

那什么是批处理系统呢？

在批处理系统中用户所提交的作业先放到外存上。并且排成一个队列，称之为“后备队列”。然后作业调度的程序按照一定的算法，从后背队列中选择若干个作业调入内存，使他们共享CPU和系统中的各种资源。由于同时在内存中装有若干道程勋，这样便可以在运行A的时候，利用其I/O操作而暂定执行CPU的空闲时间，在调度另一个程序B运行，同样可以利用程序B在I/O操作时的CPU空闲时间，在调度程序C运行，使多道程序交替运行，这样就可以保持CPU处于忙碌状态。

多道批处理系统的优缺点是什么呢？

• 资源利用率高：多道程序交替运行，保持CPU的忙碌状态；内存中装入多道程序提高内存的利用率；此外还提高了I/O设备的利用率。
• 系统吞吐量大：CPU和其他资源都保持忙碌的状态，仅当作业运行完成或者运行不下去的时候才进行切换，系统开销小。
• 平均周转时间长：因为作业要排队一次进行处理，所以作业的周转时间比较长，通常为几个小时或者几天。
• 没有交互能力：作业交给系统后，直到作业完成，用户都不能与自己的作业进行交互，修改和调试程序很不方便。

一、先来先服务first-come first-serverd(FCFS)

调度的作业是最先进入就绪队列的作业。

这种调度算法有利于长作业，但是不利于短作业,因为短作业必须一直等待前面的长作业执行完毕后才能执行，但是长作业又需要执行很长的时间，造成了短作业等待的时间过长。

二、短作业优先shortest job first(SJF)

优先调度运行时间最短的作业

这种调度算法导致长作业有可能会出现饿死的现象，因为可能存在长作业一直等待短作业执行完毕的状态。如果一直有短作业到来，那么长作业永远也得不到调度。

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

调度程序总是悬着剩余运行时间最少的进程运行。它时短作业优先的抢占式版本。

程序的运行时间必须提前知道，当一个新作业到达时，整个运行时间和当前运行进程的剩余时间相比较，如果新作业的总时间小于当前运行程序的剩余运行时间少，则选择运行新程序。

3.2、交互式系统（分时系统）中的调度

什么是分时系统呢？

它是指一台主机上连接了多个配有显示器和键盘的终端由此所组成的系统，该系统运行多个用户同时通过自己的终端，以交互方式使用计算机，共享主机中的资源。

分时系统的特征有哪些呢？

• 多路性：允许多个用于共享一台计算机，提高了系统资源利用率。
• 独立性：每个用户在各自的终端上进行操作，彼此之间互不干扰。
• 及时性：对每个用户的请求能在很短的时间内获得响应。
• 交互性：用户可以通过终端与系统进行广泛的人机对话。

一、优先级调度

除了可以手动赋予优先权之外，还可以把响应比作为优先权，也叫做高响应比优先调度算法。

响应比 = （等待时间 + 要求服务时间）/要求服务时间 = 响应时间/要求服务时间

这种调度算法主要是为了解决短作业优先调度算法长作业可能会饿死的问题，随着等待时间的增长，响应比也会越来越高。

二、时间片轮转

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

时间片轮转算法的效率和时间片的大小有很大的关系，因为进程的切换都要保存进程的信息和载入新进程的信息，如果时间片太小，会导致进程切换的太频繁，在进程切换上会花费过多的时间。

三、多级反馈队列

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

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

3.3、实时系统的调度

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

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

一、最早截止时间优先EDF（Earliest Deadlin First）

该调度算法根据作业的截止时间确定任务的优先级，任务的截止时间越早，其优先级越高，具有最早截止时间的任务排在队列的队首。

二、最低松弛度优先LLF（Least Laxity First）算法

该算法在确定任务的优先级时，根据的是任务的紧急程度（或松弛度）。任务的紧急程度越高，赋予该任务的优先级就越高。

例如：一个任务在200ms时必须完成，而它本省所需的运行时间为100ms，因此调度程序必须在100ms之前调度执行，该任务的紧急程度（松弛程度）为100ms。又如另一个任务在400ms时必须完成，它本身需要运行150ms。则其松弛度为250ms。在实现该算法的时候要求系统中有一个按照松弛度排序的实时任务就绪队列。松弛对最低的任务排在最前面，调度程序优先选择队首的任务执行。

四、进程同步

4.1、临界区

对临界资源进行访问的那段代码称之为临界区。

为了互斥的访问临界资源，每个进程在进入临界区的之前，需要先进行检查。

4.2、互斥和同步

同步：多个进程按照一定的顺序执行。

互斥：多个进程同一时刻只能一个进程进入到临界区。

4.3、信号量

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

down：如果信号量大于0，执行-1操作；如果信号量等于0，进入睡眠，等待信号量大于0；

up：对信号量执行+1操作，唤醒睡眠的进程让其完成down操作。

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

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

typedef int semaphore;
semaphore mutex = 1;
void P1() {
    down(&mutex);
    // 临界区
    up(&mutex);
}

void P2() {
    down(&mutex);
    // 临界区
    up(&mutex);
}

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

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

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

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

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

#define N 100
typedef int semaphore;
semaphore mutex = 1;
semaphore empty = N;
semaphore full = 0;

void producer() {
    while(TRUE){
        int item = produce_item();
        down(&empty);
        down(&mutex);
        insert_item(item);
        up(&mutex);
        up(&full);
    }
}

void consumer() {
    while(TRUE){
        down(&full);
        down(&mutex);
        int item = remove_item();
        up(&mutex);
        up(&empty);
        consume_item(item);
    }
}

4.4、管程

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

c 语言不支持管程，下面的示例代码使用了类 Pascal 语言来描述管程。示例代码的管程提供了 insert() 和 remove() 方法，客户端代码通过调用这两个方法来解决生产者-消费者问题。

monitor ProducerConsumer
    integer i;
    condition c;

    procedure insert();
    begin
        // ...
    end;

    procedure remove();
    begin
        // ...
    end;
end monitor;

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

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

使用管程实现生成者-消费者问题

// 管程
monitor ProducerConsumer
    condition full, empty;
    integer count := 0;
    condition c;

    procedure insert(item: integer);
    begin
        if count = N then wait(full);
        insert_item(item);
        count := count + 1;
        if count = 1 then signal(empty);
    end;

    function remove: integer;
    begin
        if count = 0 then wait(empty);
        remove = remove_item;
        count := count - 1;
        if count = N -1 then signal(full);
    end;
end monitor;

// 生产者客户端
procedure producer
begin
    while true do
    begin
        item = produce_item;
        ProducerConsumer.insert(item);
    end
end;

// 消费者客户端
procedure consumer
begin
    while true do
    begin
        item = ProducerConsumer.remove;
        consume_item(item);
    end
end;

五、进程通信

进程同步与进程通信的区别在与：

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

5.1、信号量

在进程同步中介绍的信号量也是进程通信的一种方式，但是属于低级别的进程通信，因为他传输的信息量非常小。

5.2、消息传递

操作系统提供了用于通信的通道（Channel）,进程可以通过读写这个通道来进行通信。

一、管道

写进程在管道的尾端写入数据，读进程在管道的首端读取数据，管道提供了简单的流程控制机构，进程试图读空管道时，在有数据写入之前一直处于阻塞状态，同样地，管道已满的情况下，进程再试图写入数据，在其他进程从管道中移出数据之前，写进程将一直处于阻塞状态。

Linux中的管道通过空文件实现。

管道有三种：

• 普通管道：有两种限制，一是只能单向传输；二是只能在父子进程之间使用。
• 流管道：去除了普通管道的第一个限制，支持双向传输。
• 命名管道：去除了普通管道的第二个限制，可以在不想关进程之间进行通信。

二、消息队列

消息队列克服了信号量只能传递信息量少，管道只能承载无格式字节流以及缓冲区大小受限等缺点。

三、套接字

套接字也是进程间进行通信的一种方式，与其他通信机制不同的是，它可用于不同机器间进程之间的通信。

5.3、共享内存

操作系统建立了一块共享内存，并将其映射到每个进程的地址空间上，进程可以直接对这块共享内存进行读写。共享内存是最快的进程通信方式。

六、死锁

6.1、死锁的必要条件

• 互斥：进程对所分配的资源不允许其他进程进行访问，若其他进程进行访问只能等待，直至占有该资源的进程使用完成后释放该资源。
• 请求和保持：进程获取一定的资源后，又对其他资源发出请求，但是该资源可能被其他进程占有，此时请求阻塞，但是对自己获取的资源保持不放。
• 不可剥夺：进程已获得的资源，在未完成使用之前，不可被剥夺，只能使用完成后自己释放。
• 环路等待：有两个或者两个以上的进程组成一条环路，该环路中的每个进程都在等待下一个进程所占有的资源。

6.2、死锁的处理方法

一、鸵鸟策略

把头埋进沙子里面，当做根本没发生问题，因为解决死锁问题的代价很高，因此这种不采取任何方案会获得更高的性能。

当产生死锁时对用户不会造成多大影响或者产生死锁的概率很低，我们就可以采取鸵鸟策略。

二、死锁的检测与死锁的恢复

不试图阻止死锁而是当死锁发生的时候，采取措施进行恢复。

(一)、每种类型一个资源的死锁检测

对于上面的资源分配图，方框表示资源，圆圈表示进程。资源指向进程表示该资源已经分配给该进程，进程指向资源表示进程请求获取该资源。

图 (a) 可以抽取出环，如图 (b) 满足环路等待条件，因此就会发生死锁。

每种类型一个资源的死锁检测算法是通过检测有向图是否有环路存在来实现的。从一个节点出发进行深度优先搜索，对访问过的结点进行标记。如果访问了已经标记的结点，就表示有向图存在环路，也就是检测到了死锁的发生。

（二）、每种类型多个资源的死锁检测

上图中，有三个进程四个资源，每个数据代表的含义如下：

• E 向量：资源总量
• A 向量：资源剩余量
• C 矩阵：每个进程所拥有的资源数量，每一行都代表一个进程拥有资源的数量
• R 矩阵：每个进程请求的资源数量

进程 P1 和 P2 所请求的资源都得不到满足，只有进程 P3 可以，让 P3 执行，之后释放 P3 拥有的资源，此时 A = (2 2 2 0)。P2 可以执行，执行后释放 P2 拥有的资源，A = (4 2 2 1) 。P1 也可以执行。所有进程都可以顺利执行，没有死锁。

（三）、死锁恢复

• 利用抢占恢复
• 利用回滚恢复
• 通过杀死进程恢复

6.3、死锁预防

在进程运行之前预防发生死锁

一、破坏互斥条件

例如假脱机打印机技术允许若干个进程同时输出，唯一真正请求物理打印机的进程是打印机守护进程。

二、破坏请求和保持条件

一种实现方式是规定所有进程在开始执行前请求所需要的全部资源。

三、破坏不可剥夺条件

四、破坏环路等待

给资源统一编号，进程只能按编号顺序来请求资源。

6.4、死锁的避免

在程序运行时避免发生死锁

（一）、单个资源的银行家算法

一个小城镇的银行家，他向一群客户分别承诺了一定的贷款额度，算法要做的是判断对请求的满足是否会进入不安全状态，如果是，就拒绝请求；否则予以分配。

上图 c 为不安全状态，因此算法会拒绝之前的请求，从而避免进入图 c 中的状态。

（二）、多个资源的银行家算法

上图中有五个进程，四个资源。左边的图表示已经分配的资源，右边的图表示还需要分配的资源。最右边的 E、P 以及 A 分别表示：总资源、已分配资源以及可用资源，注意这三个为向量，而不是具体数值，例如 A=(1020)，表示 4 个资源分别还剩下 1/0/2/0。

检查一个状态是否安全的算法如下：

• 查找右边的矩阵是否存在一行小于等于向量 A。如果不存在这样的行，那么系统将会发生死锁，状态是不安全的。
• 假若找到这样一行，将该进程标记为终止，并将其已分配资源加到 A 中。
• 重复以上两步，直到所有进程都标记为终止，则状态时安全的。

如果一个状态不是安全的，需要拒绝进入这个状态。