操作系统(一): 进程和线程，进程的多种状态以及进程的调度算法

---

前言

本文转载于cyc大佬的cs notes,在摘抄的过程中添加了部分自己的理解

一、进程和线程

1. 进程

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

2. 线程

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

比如QQ和浏览器是两个不同的进程，浏览器进程里面存在很多线程，比如http请求线程，事件响应线程，渲染线程等等，线程的并发执行使得在浏览器中点击一个新的连接从而发起http请求的时候，浏览器还可以响应用户的其他事件。

二、进程和线程的区别(面试常问)

1. 是否拥有资源
   进程是拥有资源的，其是资源分配的基本单位。但是线程是不拥有资源的，线程调用的是进程的基本资源。

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

3. 系统开销
   在创建或者撤销进程的时候，系统都要为其分配或者回收资源，比如内存空间，IO设备等等，付出的开销远远大于创建线程的开销。类似地，在进行进程切换的时候，涉及到当前执行进程CPU环境的保存和新调度的进程的CPU环境的设置，但是切换线程只需要保存和设置少量寄存器内容，开销很小。

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

三、进程调度算法

根据不同类型的操作系统，进程调度算法也不同，因此需要分操作系统的类型来展开讨论；

3.1. 批处理系统

该系统中不存在太多的用户操作，因此在该系统中调度算法的目标是保证吞吐量和周转时间

• 先来先服务(FCFS)
  非抢占式的调度算法，按照请求的顺序进行调度,有利于长作业，但不利于短作业。

• 短作业优先(SJF)
  非抢占式的调度算法，按估计运行时间最短的顺序进行调度。

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

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

3.2. 交互式系统

在该系统中，存在大量的用户交互操作，因此在该系统中调度算法的核心目标是快速进行响应。

3.2.1 时间片轮转

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

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

3.2.2 优先级调度

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

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

3.2.3 多级别反馈队列

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

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

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

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

3.3. 实时系统

实时系统的进程调度算法在面试中考察的较少，在这不讨论

四、进程的状态

可分为三态模型和五态模型。
三态模型:

五态模型:

请注意以下若干问题:

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

五、进程同步

5.1 什么是进程同步

多个并发进程在一些关键点上可能需要互相等待或互通消息，这种相互制约的等待或互通消息称为进程同步。

5.2 进程同步应该遵循的几点原则

• 空闲让进：其他进程均不处于临界区则允许进程进入；
• 忙则等待：已有进程处于其临界区则等待；
• 有限等待：等待进入临界区的进程不能"死等"；
• 让权等待：不能进入临界区的进程，应释放CPU（如转换到等待状态）
• 在这里补充一下临界区的概念：对临界资源进行访问的那段代码称为临界区。为了互斥访问临界资源，每个进程在进入临界区之前，需要先进行检查。

---