跳到主要内容

进程管理

组成和状态​

进程由进程控制块PCB（唯一标识）、程序（描述进程要做什么）、数据（存放进程执行时所需数据）

进程基础的状态是下面图中的三态图，需要熟练掌握每个状态的功能和状态之间是如何切换的。

  • 运行态：表示当前这个进程正在运行，处于运行态的进程需要 CPU 时间片。
  • 就绪态：处于就绪队列中，等待被 CPU 调度（除了 CPU 之外，所有东西都有了）
  • 阻塞态：没有 CPU ，还缺其它条件。
提示

新建的进程处于就绪状态，运行态的进程还可以转到终止态。只有就绪和运行是可以相互转换的。

前驱图​

前驱图用来表示那些任务可以并行执行，那些任务之间有顺序关系，具体如下图：

A、B、C 可以 并行执行，但是必须 A、B、C 都执行完，才能执行 D，这就确定了两点：任务间的并行，任务间的先后顺序。

进程资源图（几乎不考）​

进程资源图用来表示进程之间的分配和请求关系，如下图所示：

P 代表进程、R 代表资源，R 方框中有几个圆球就表示有几个这种资源，在上图中，R1 指向 P1,表示 R1 已经有一个资源已经分配给了 P1，P1 指向 R2，表示 P1 还需要请求一个 R2 资源才能执行。

  • 阻塞节点：某进程 所请求资源已经全部分配完毕，无法获取所需资源，该进程被阻塞了无法继续。如上图 P2。

  • 非阻塞节点：某进程 所请求的资源还有剩余，可以继续分配给该进程继续运行，如上图中 P1、P3。

  • 当一个进程资源图中 所有进程都是阻塞节点时，即陷入死锁状态。

同步和互斥（重点）​

  • 临界资源：各进程间需要互斥方式对其进行访问的资源

  • 临界区：进程中对临界资源实施操作的那段程序。本质是一段程序代码。

  • 互斥：某资源（即临界资源）在 同一时间内只能由一个任务单独使用，使用时需要加锁，使用完后解锁才能被其它任务使用，如打印机。

  • 同步：多个任务可以并发执行，只不过有速度上的差异，在一定情况下停下来等待，不存在资源是否单独或共享的问题；如自行车和汽车。

  • 互斥信号量：对临界资源采用互斥访问，使用互斥信号量后其它进程无法访问，初始值为 1。

  • 同步信号量：对共享资源的访问控制，初始值一般是共享资源的数量。

PV 操作​

P 操作：申请资源，S=S-1，若 S>=>=0， 则执行 P 操作的进程继续执行；若 S << 0 ,则置该进程为阻塞状态（因为无可用资源），并将其插入阻塞队列。

V 操作：释放资源,S = S+1，若 S >> 0,则执行 V 操作的进程继续执行；若 S <=<= 0 ,则从阻塞状态唤醒一个进程，并将其插入就绪队列（此时因为缺少资源被 P 操作阻塞的进程可以继续执行），然后执行 V 操作的进程继续执行。

当 S 大于 0 的时候，S 表示的是资源的个数，当 S 小于 0 的时候，S 表示的是等待该资源的进程数。S <=<= 0 表示当前还有进程正在等待该资源，进程释放了资源可以去获取了。

生产者和消费者问题​

三个信号量：互斥信号量S0S_0（仓库独立使用权），同步信号量S1S_1(仓库空闲个数)，同步信号量S2S_2(仓库商品个数)。

提示

前驱图中的每一条线都是一个信号量。

进程调度​

进程调度方式是指当有更高优先级的进程到来时如何分配 CPU。分为可剥夺和不可剥夺两种，可剥夺指当有更高优先级进程到来时，强行将正在运行进程的 CPU 分配给高优先级进程；不可剥夺是指高优先级进程必须等待当前进程自动释放 CPU。

在某些操作系统中，一个作业从提交到完成需要经历高、中、低三级调度。

  1. 高级调度：高级调度又称为“长调度”、”作业调度“、或”接纳调度“，它决定 处于输入池中的那个后备作业可以调入主系统做好运行的准备，成为一个或一组就绪进程。在系统中一个作业只需要经过一次高级调度。

  2. 中级调度：中级调度又成为”中程调度“或”对换调度“，它决定 处于交换区中的那个就绪进程可以调入内存，以便直接参与对 CPU 的竞争。

  3. 低级调度：低级调度又称为“短程调度”或“进程调度”，它决定 处于内存中的那个就绪进程可以占用 CPU。低级调度时操作系统中最活跃、最重要的调度程序，对系统的影响很大。

调度算法​

  • 先来先服务：先到达的进程优先分配 CPU。用于宏观调度。
  • 时间片轮转：分配给每个进程 CPU 时间片，轮流使用 CPU，每个进程时间片大小相同，很公平，用于微观调度。
  • 优先级调度：每个进程都有一个优先级，优先级大的先分配 CPu。
  • 多级反馈调度：时间片轮转和优先级调度结合而成，设置多个就绪队列 1,2,3...n，每个队列分别赋予不同的优先级，分配不同的时间片长度；新进程先进入队列 1 的末尾，按 FCFS原则，执行队列 1 的时间片；若未能执行完进程，则转入队列 2 的末尾，如此重复。
提示

作业中可能会有一组进程

死锁（重点）​

当一个进程在等待永远不可能发生的事件时，就会产生死锁，若系统中有多个进程处于死锁状态，就会造成系统死锁。

死锁产生的四个必要条件：资源互斥、每个进程占有资源并等待其他资源、系统不可剥夺进程资源、循环等待（进程资源图是一个环路）。

死锁产生后，解决措施是打破四大条件，有下列方法：

  • 死锁预防：采用某种策略限制并发进程对于资源的请求，破坏死锁产生的四个条件之一，使系统任何时刻都不满足死锁的条件。
  • 死锁避免：一般采用银行家算法来避免，银行家算法，就是提前计算出一条不会死锁的资源分配方法，才分配资源，否则不分配资源，相当于借贷，考虑对方还得起才借钱，提前考虑好之后，就可以避免死锁。
  • 死锁检测：允许死锁产生，但系统定时运行一个检测死锁的程序，若检测到系统中发生的死锁，则设法加以解除。
  • 死锁资源计算：即死锁发生后的解除方法，每个进程都需要 R 个资源，那么其 发生死锁的最大资源数为 n*(R-1)。其不发生死锁的最小资源数为 n*(R-1)+1

线程​

传统的进程有两个属性：可拥有资源的独立单位；可独立调度和分配的基本单位。

引入线程的原因是进程在创建、撤销和切换中，系统必须为之付出较大的时空开销，故在系统中设置的 进程数目不宜过多，进程切换的频率不宜太高，这就限制了并发程度的提高。

引入线程后，将传统进程的两个基本属性分开，线程作为调度和分配的基本单位，进程作为独立分配资源的单位。用户可以通过创建线程来完成任务，以减少程序并执行时付出的时空开销。

线程是进程中的一个实体，是被系统独立分配和调度的基本单位。线程基本上不拥有资源，只拥有一点运行中必不可少的资源（如程序计数器、一组寄存器和栈），它 可与同属一个进程的其它线程共享进程所拥有的全部资源，，例如进程的公共数据、全局变量、代码、文件等资源，但 不能共享线程都有的资源，如线程的栈指针等标识数据。