操作系统——进程管理（2）

线程

概念：“轻量级进程”，是一个基本的CPU执行单元，也是程序执行流的最小单元，由线程ID、程序计数器、寄存器集合和堆栈组成。
线程也有就绪、阻塞和运行三种基本状态。

线程与进程的比较

属性

每个线程有唯一的标识符和线程控制块；
不同的线程可以执行相同的程序（比如浏览器可以打开相同的网站，相同于开启多个线程）；
同一个进程中的各个线程共享该进程所拥有的资源；
线程是CPU的独立调度单位，在单CPU的计算机系统中，各线程可交替的占用CPU；在多CPU的计算机系统中，允许不同线程占用不同的CPU，若各个CPU同时为一个进程内的各线程服务则可以缩短进程的处理时间；
一个线程被创建后便开始了它的生命周期，直至终止，线程在生命周期内会经历阻塞态、就绪态和运行态等各种状态变化。

线程的实现方式

分为两类，用户级线程和内核态线程：

用户级线程：线程管理工作由应用程序完成，内核完全意识不到线程的存在（线程切换由application完成，少了管/目态切换的消耗，但不能很好地利用多核CPU）。应用程序可以通过使用线程库设计成多线程程序。
内核态线程：线程管理（如线程切换，切换线程前从目态切到管态，线程切换后从管态切到目态）由内核完成，内核为进程及其内部的每个线程维护上下文信息，调度也是在内核基于线程架构的基础上完成。
组合形式：应用程序负责线程的创建，线程的调度和同步也在应用程序中进行。这些用户级线程被映射到一些内核级线程上（数量少于用户级线程数）。

CPU调度

调度：存在进程争用CPU的情况，CPU调度就是对CPU进行分配，从就绪队列中，按照一定的算法（公平、高效）选择一个进程并将CPU分配给它运行，以实现进程并发的执行。

调度的层次

一个作业从提交直到完成，往往要经历三级调度，高级调度（作业调度）、中级调度（内存调度）、低级调度（进程调度）

高级调度。按一定的原则，从外存上处于后备状态的作业中挑选一个或多个作业，给它们分配内存、I/O设备等必要的资源，并建立相应的进程，以使它们获得竞争CPU的权利。对于每个作业只调入一次、调出一次。高级调度在三种调度中频率最低。
中级调度。为了提高内存利用率和系统吞吐量。使哪些暂时不能运行的进程，调至外存等待（即挂起）。当它们具备运行条件而且内存又稍有空闲时，由中级调度决定，将挂起的进程重新调入内存，挂在就绪队列等待运行。
低级调度。按照某种方法和策略从就绪队列中选取一个进程，并将CPU分配给它。进程调度的频率很高，一般几十毫秒一次。此调度室最基本的，不可或缺。
三级调度的关系：作业调度为进程活动做准备，进程调度使进程正常活动起来，中级调度将暂时不能运行的进程挂起，中级调度处于作业调度和进程调度之间。

调度的时机、切换和过程

OS中，不能进行进程调度的情况

处理中断的过程不能进行进程的调度。中断处理过程复杂，实现上很难做到进程切换；而且中断处理是系统工作的一部分，逻辑上不属于某一进程，不应被剥夺CPU资源；
当进程在os内核程序临界区中，理论上必须加锁，在解锁前不应切换到其他进程运行；
其他一些完全屏蔽中断的原子操作过程。比如加锁、解锁、中断现场保护、恢复等。

出现以上情况时，不能马上进行调度和切换，应置系统的请求调度标志，直到上述过程结束之后才进行相应的调度与切换。

剥夺调度和非剥夺调度

剥夺调度：当一个进程正在运行时，系统可以基于某种原则，剥夺已分配给它的处理机，将之分配给其它进程。原则主要有：优先权、短进程优先和时间片原则等。
非剥夺调度：分派程序一旦把处理机分配给某进程后便让它一直运行下去，直到进程完成或发生进程调度某事件而阻塞时，才把处理机分配给另一个进程。实现简单、系统开销小，适用于大多数的批处理系统，但不能用于分时系统和大多数的实时系统。

进程调度时的上下文处理

进程切换往往在调度完成后立刻发生，它要求保存原进程当前切换点的现场信息，恢复被调度进程的现场信息。
现场切换时，操作系统内核将原进程的现场信息推入到当前进程的内核堆栈来保存它们，并更新堆栈指针。
内核完成从新进程的内核栈中装入新进程的现场信息、更新当前运行进程空间指针、重设PC寄存器等相关工作后，开始运行新的进程。

调度基本原则（也是评价一个调度算法的指标）

基本原则主要有：CPU利用率（尽可能使CPU处于繁忙状态）、系统吞吐量（单位时间内CPU完成作业的数量，如果作业都是短作业，吞吐量就比较高）、周转时间（从作业提交到作业完成所经历的时间）、等待时间（进程处于等待CPU状态时间之和）、响应时间（用户提交请求到系统首次产生响应所用的时间）

重点关注：

周转时间。
- 周转时间=作业完成时间-作业提交时间。
- 平均周转时间是指多个作业周转时间的平均值。
- 带权周转时间是指作业周转时间与作业实际运行时间的比值。
- 平均带权周转时间=（sigma作业i的带权周转时间）/n。
等待时间。
- CPU调度算法实际上不影响作业执行或输入/输出操作的时间，只影响作业在就绪队列中等待所花的时间；
- 衡量一个算法的优劣，常常只需要简单的考察等待时间即可。

典型调度算法

有的调度算法适合于作业调度，有的适合于进程调度，有的算法两者都适用。
常用的调度算法有：先来先服务FCFS，短作业优先SJF、优先级调度算法、高响应比优先调度算法、时间片轮转调度算法、多级反馈队列调度算法

先来先服务FCFS

既可用于作业调度，又可用于进程调度；
应用在作业调度时，每次从后备作业队列中选择最先进入队列的作业，将它们调入内存，分配必要的资源，创建进程并放入就绪队列；
应用在进程调度时，每次从就绪队列中选择最先进入队列的进程，将CPU分配给它，直到完成或因某些原因而阻塞时才释放CPU；
FCFS属于不可剥夺算法。
特点：算法简单、效率低；对长作业比较有利，但对短作业不利（相对SJF和高响应比）；有利于CPU繁忙型作业，不利于I/O繁忙型作业。

短作业优先SJF

既可用于作业调度，又可用于进程调度；
应用在作业调度时，从后备队列中选择一个或多个估计运行时间最短的作业，调入内存中；
应用在进程调度时，从就绪队列中选择一个估计运行时间最短的进程；
缺点：对长作业不利，可能导致长作业长期不被调度出现饥饿现象；未考虑作业的紧迫程度，不能保证紧迫性作业会被及时处理；作业的长短由用户提供的估计执行时间而定，用户可能刻意缩短该估计时间；
特点：SJF调度算法的平均等待时间、平均周转时间最少。

优先级调度算法

既可用于作业调度，又可用于进程调度；
应用在作业调度时，从后备队列中挑选优先级最高的一个或多个作业调入内存；
应用在进程调度时，从就绪队列中选择优先级最高的进程；
新的最高优先级进程能够抢占当前执行的进程，要分两种情况：
- 非剥夺式。当前执行的进程让它出于自身原因主动让出CPU（任务完成或等待事件）给更高优先级的进程；
- 剥夺式。立即暂停当前执行的进程，将CPU移交给更高优先级的进程。
进程创建后其优先级能够改变，要分两种情况：
- 静态优先级。优先级在进程创建之初确认，之后保持不变。确定静态优先级的依据主要有：进程类型、进程对资源的要求、用户要求。
- 动态优先级。进程运行过程中，根据进程情况的变化动态调整优先级。确定动态优先级的依据主要有：进程占有CPU时间的长短、就绪进程等待CPU时间的长短。

高响应比优先调度算法

主要用于作业调度
同时考虑每个作业的等待时间和估计的运行时间。每次作业调度时，先计算后备作业队列中每个作业的响应比，从中选出响应比最高的作业投入运行。
响应比Rp=等待时间/ 要求服务时间 + 1 。要求服务时间即估计运行时间。有利于短作业，同时也有利于先来先服务。
优点：克服了饥饿状态，兼顾了长作业。

时间片轮转调度算法

用在进程调度，不用在作业调度（理解：作业的调入调出不可能随时间片频繁变动）
主要用在分时系统，总是选择就绪队列中第一个进程执行，等待一个时间片后，即使进程未完成运行，也必须释放出（或被剥夺）CPU给下一个进程，被剥夺的进程进入就绪队列的末尾重新排队。
时间片的大小需要选择合适，太大会使本算法退化成先来先服务算法；太小会使进程切换过于频繁，造成CPU开销太大。选取的标准视以下因素：系统的响应时间、就绪队列中的进程数量和系统的处理能力而定。
此算法利于多用户干预，人机交互得到提升。

多级反馈队列调度算法

用在进程调度，不用在作业调度（理由与时间片算法相同）
通过动态调整进程优先级和时间片大小，综合了时间片轮转调度算法和优先级调度算法
对短进程和I/O型进程照顾，不必事先估计进程的执行时间；
实现思想：
- 设置多个不同优先级的队列，比如第1队列优先级最高；
- 赋予各个队列的时间片大小也不相同，优先级越高的队列的时间片越小；
- 当新进程进入内存后，先放入第1队列的末尾，按照FCFS原则排队。等轮到该进程执行时，如果任务能够完成，便可撤离系统；如果任务完不成，调度程序会将该进程转入第2队列的末尾，再同样按照FCFS原则等待执行，以此类推；
- 仅当第1队列为空时，调度程序才会调度第2队列中的进程运行，以此类推。例如，如果CPU正在运行第3队列时，有新的进程加入第1进程末尾，此时新进程将抢占CPU；
优点：终端型作业用户：短作业优先；短批处理作业用户：周转时间较短；长批处理作业用户：经过前几个队列得到部分执行，不会长期得不到处理。