操作系统基本功能 -- 进程管理

进程管理

插写一点并发与并行概念：
并发是指宏观上在一段时间内能同时运行多个程序，而并行则指同一时刻能运行多个指令。

进程控制

进程与线程

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

线程是独立调度的基本单位。
一个进程中可以有多个线程，它们共享进程资源。

区别：

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

进程状态切换

进程状态切换

• 就绪(Ready)状态
  当进程已分配到除CPU以外的所有必要的资源，只要获得处理机便可立即执行，这时的进程状态称为就绪状态。
• 执行（Running）状态
  当进程已获得处理机，其程序正在处理机上执行，此时的进程状态称为执行状态。
• 阻塞(Blocked)状态
  正在执行的进程，由于等待某个事件发生而无法执行时，便放弃处理机而处于阻塞状态。引起进程阻塞的事件可有多种，例如，等待I/O完成、申请缓冲区不能满足、等待信件(信号)等。

注意：只有就绪态和运行态可以相互转换，其它的都是单向转换。运行状态的进程，在分配给它的 CPU 时间片用完之后就会转为就绪状态，等待下一次调度。

进程调度

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

   先来先服务 first-come first-serverd（FCFS）
   按照请求的顺序进行调度。有利于长作业，但不利于短作业，因为短作业必须一直等待前面的长作业执行完毕才能执行，而长作业又需要执行很长时间，造成了短作业等待时间过长。

   短作业优先 shortest job first（SJF）
   按估计运行时间最短的顺序进行调度。长作业有可能会饿死，处于一直等待短作业执行完毕的状态。因为如果一直有短作业到来，那么长作业永远得不到调度。

   最短剩余时间优先 shortest remaining time next（SRTN）
   按估计剩余时间最短的顺序进行调度。当一个作业正在执行时，一个新作业进入就绪状态，如果新作业需要的 CPU 时间比当前正在执行的作业剩余下来还需的 CPU 时间短，SRTF 强行赶走当前正在执行的作业。
   /// 此算法不仅适用于作业调度，同样也适用于进程调度。///

   高响应比优先（HRRF）
   响应比定义：作业进入系统后的等待时间与处理时间之和称作该作业的响应时间，作业的响应时间除以作业处理时间称作响应比，即：

   • 响应比 = 1+已等待时间/作业处理时间

2. 交互式系统

   时间片轮转
   将所有就绪进程按 FCFS 的原则排成一个队列，每次调度时，把 CPU 时间分配给队首进程，该进程可以执行一个时间片。当时间片用完时，由计时器发出时钟中断，调度程序便停止该进程的执行，并将它送往就绪队列的末尾，同时继续把 CPU 时间分配给队首的进程。
   时间片轮转算法的效率和时间片的大小有很大关系。因为进程切换都要保存进程的信息并且载入新进程的信息，如果时间片太小，会导致进程切换得太频繁，在进程切换上就会花过多时间。

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

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

   每个队列优先权也不同，最上面的优先权最高。因此只有上一个队列没有进程在排队，才能调度当前队列上的进程。可以将这种调度算法看成是时间片轮转调度算法和优先级调度算法的结合。

   
   多级反馈队列
   

   不足：会存在饥饿问题。当新进程不断到来，进入较高优先级队列，CPU 忙于运行高优先级队列中的进程，低优先级队列中的进程将长时间得不到调度，产生饥饿现象。

3. 实时系统

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

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

进程同步

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

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

进入区
临界区
退出区
剩余区

同步与互斥：

• 同步：多个进程按一定顺序执行；
• 互斥：多个进程在同一时刻只有一个进程能进入临界区。

四条准则：空闲让进、忙则等待、有限等待、让权等待

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

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

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

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

进程通信

进程间通信方式一般认为有六种：

1. 管道（半双工，不能区分消息类型，无名管道需要血缘关系，有名管道有同步阻塞问题）
2. 信号（对一些特定事件的处理）
3. 消息队列（读写可同时存在，能区分消息类型，无同步阻塞问题）
4. 共享内存
5. 信号量（用于同步）
6. 套接字（网络通信，可以跨机器）

死锁

死锁的必要条件：

1. 互斥(Mutual exclusion)。进程对所分配到的资源进行排它性使用，在一段时间内某资源只由一个进程占用。
2. 持有并等待(Hold and wait)。指某个进程已经持有了一个或多个资源，但是还要请求其他资源，而它请求的资源不能立即获得，需要等待。
3. 不可抢占(No preemption)。即进程已经获取的资源在使用过程中不能被其他进程抢占，只能在使用完后，由该进程自己释放。
4. 环路等待(Circular wait)。即形成进程和请求资源之间的环路。

处理死锁的策略：

1. 预防死锁
   死锁的预防即不允许死锁的发生，可以从破除死锁发生的四个必要条件入手。因为如果不具备上述四个必要条件，那么死锁就一定不会发生。
   （1）互斥：不容易破除
   （2）占有并等待：两种破除方式，不持有并等待，即如果一个进程一次请求获取不了所有资源，那么它不可占用任何资源（释放掉它已经占有的资源）。持有不等待，资源充足，只要申请求资源，就给其资源，不让它等待。
   （3）不可抢占：如果一个进程所请求的资源被另一进程占有，使它可以抢占另一进程占有的资源。
   （4）环路等待：对资源进行排序，即每个进程访问资源的顺序是固定的（给资源统一编号，进程只能按编号顺序来请求资源）。

2. 避免死锁
   避免死锁同样是属于事先预防的策略，但是不是事先采取某种限制措施，而是在资源动态分配过程中，防止系统进入不安全状态，以避免发生死锁。这种方法所施加的限制条件较弱，可能获得较好的性能。
   银行家算法
   当新进程进入系统时，它必须说明其可能需要的各种类型资源实例的最大数量，这一数量不能超过当前系统资源的总和。当用户申请一组资源时，系统必须确定这些资源的分配是否仍会使系统出于安全状态，如果是，就分配资源；否则，进程必须等待直到某个其他进程释放足够资源为止。
   通俗的讲就是先寻找没有执行完并且所需资源小于可用资源的进程，若存在这样的进程，则将可用资源分配给这个进程，使这个进程执行完毕，进程执行完毕后会释放掉它占有的资源，于是可用资源增加，然后继续循环去找满足条件的进程，直到所有进程所需资源都被满足，这样可以确保系统一直处于安全状态。

3. 死锁监测与恢复
   不试图阻止死锁，而是当检测到死锁发生时，采取措施进行恢复。

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

   算法总结如下：
   每个进程最开始时都不被标记，执行过程有可能被标记。当算法结束时，任何没有被标记的进程都是死锁进程。

   1. 寻找一个没有标记的进程 Pi，它所请求的资源小于等于 A（资源剩余量）。
   2. 如果找到了这样一个进程，那么将 C（每个进程所拥有的资源数量）的第 i 行向量（拥有资源的数量）加到 A（资源剩余量）中，标记该进程，并转回第一步。
   3. 如果没有这样一个进程，算法终止。

   死锁解除算法： 认定系统中已发生了死锁，利用该算法将系统从死锁状态中解脱出来。

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

处理机调度

一、处理机调度的类型

处理机调度程序按照某种算法将处理机分配给某个进程，这就叫处理机调度。总体而言，按层次分，有三种类型：

作业调度（又称高级调度、长程调度）
作业调度的本质就是根据某种算法，把外存上的作业调入内存，并为之创建进程，分配处理机并执行。这里有两个概念：
1）作业（Job）
　　作业是一个比程序更广泛的概念，可以包含多个程序和数据，还包含一份作业说明书，处理机根据作业说明书来对作业中的程序进行控制。一般而言，批处理系统中才会有高级调度。
2）作业步（Job Step）
　　作业步的本质就是程序。作业运行过程中的每一个步骤可以称为一个作业步。典型的作业可分为三个作业步：编译作业步->连续装配作业步->运行作业步。相当于我们的程序代码的整个执行步骤。

进程调度（又称低级调度、短程调度）
进程调度的本质就是根据某种算法，把处理机分配给进程。进程调度首先会保存处理机现场。将程序计数器等指定寄存器中的内容保存到 PCB 中。然后将按照某种算法从就绪队列中选取进程，把处理机分配给进程。最后，把指定进程的 PCB 中的处理机现场信息恢复到处理机中，处理机分配给进程执行。这里需要额外的了解一下进程调度中的三个基本机制和两种调度方式：
1）进程调度中的三个基本机制

• 排队器。将所有的就绪进程按照一定方式 （如优先级）排成一个队列，以便调度程序找到。
• 分派器。把从就绪队列中取出的进程，处理机上下文切换后，把处理机分配给该进程执行。
• 上下文切换机制。
  （PS：这里有一个额外的知识：通常每一次上下文切换需要花费几毫秒的时间。有一种简单的方式，通过多组寄存器来减少上下文切换的时间。一组寄存器供处理机在系统态使用，一组供处理机在应用程序状态时使用。这样，上下文切换的时候只需要改变指针，指向当前的寄存器。）
  （PSS：CPU的系统态就是CPU在执行操作系统，用户态则是CPU在执行普通应用程序。）

2）进程调度的两种调度方式

• 非抢占式（Nonpreemptive Mode）。说白了就是一旦把进程分配给某个进程，除非它自愿退出，它将永远运行下去。
• 抢占式（Preemptive Mode）。说白了就是可以根据某种条件，使正在运行的进程暂停，将处理机分配给另一个进程。相当于信号量机制中的条件变量。

中级调度
中级调度的本质就是让暂时不能运行的进程挂起，释放内存资源，并把它们调到外存上去等待。什么是外存？外存就是硬盘、磁盘等存储设备。

二、调度算法

1. 先来先服务调度算法（FCFS）
   顾名思义。就是先来的先进入内存或占用处理机。对于作业调度，就是从后备作业队列中选择一个或多个最先进入队列的作业，将其调入内存。对于进程调度就是从就绪队列选择最新进入的进程，为之分配处理机。
2. 短作业（进程）优先调度算法（SJF）
   顾名思义。就是在选择作业或进程的时候，先估算每个作业、进程的服务时间，选择其中最短的优先获得处理机。
3. 高优先权优先调度算法
   这种算法给进程加了一个属性，那就是优先权。这个算法的本质就是，高优先权的优先调用。优先权有两种类型，一种是静态的，即每个进程、作业的优先权在它创建的时候就已经确定，此后都不能改变。另一种是动态的，即进程、作业的优先权是可以改变的。最常见的做法就是进程、作业在等待中，优先权以一定速率随时间增长，这样等待时间越长，被调用的可能性就越大。
4. 基于时间片的轮转调度法
   这就是分时系统中采用的调度算法。原理就是把所有的就绪队列进程按先来先服务的原则排成队列。每次都把 CPU 分配给队首，让其执行一个时间片，执行完毕，调度器中断进程，并把该进程移至就绪队列的队尾，然后再取一个队首进程，继续执行下一个时间片。时间片是什么，就是一段很短的 CPU 时间，几毫秒到几百毫秒不等。
5. 多级反馈队列调度算法
   这是当下公认的比较好的，使用最广泛的调度算法。其原理也不难。例如，某计算机采用多级反馈队列调度算法，设置了5个就绪队列。第一个就绪队列优先级最高，时间片为2ms。第二个就绪队列优先级第二，时间片为4ms，其余队列也一样，优先级依次递减，时间片依次增加。如果某个进程进入就绪队列，首先把它放在第一个就绪队列的末尾，轮到它执行就执行2ms，时间片结束，若该进程还没有执行完毕，就把该进程移入第二个就绪队列的末尾。只有当第一个队列的进程都执行完时间片，才会执行第二个队列。如此依次执行，若该进程服务时间很长，将被移到最后一个就绪队列。在最后一个就绪队列，进程将按照时间片轮转调度法执行。处理机执行过程中，只有当优先级高的队列中的线程都执行完毕，才会执行优先级低的队列。
   多级反馈队列调度算法