操作系统学习笔记（三）进程的调度，同步/互斥与死锁
之前一篇博客讲过了进程存在的意义是什么，我们为什么要搞出进程这个概念。
但是随之而来的就是几个连续的问题，也是多道并发会遇到的几个问题：
- 多个进程并发的时候，如何进行调度，调度的原则是什么？
- 如果多个进程之间有相互依赖关系怎么办，比如同步和互斥关系？
- 如果因为依赖关系，产生了循环依赖，可能导致死锁，又该怎么办？
这篇博客我们就第一个问题进行解释，那就是处理机如何进行调度的。
调度的概念
在多道程序中，进程的数量往往多于处理机个数，所以进程争用处理机的情况在所难免。处理机调度是对处理机进行分配，即就绪队列中按照一定的算法选择一个进程将处理及分配给它运行，以实现进程并发执行。
调度的层次
一个作业从提交开始直到完成，往往要经历三级调度，如图所示：
高级调度（作业调度）
按照一定原则从外存上处于后备队列的作业中挑选一个或者多个，给它们分配内存，输入输出设备等必要的资源，并建立相应的进程，以使他们获得竞争处理机的权力。简言之，作业调度就是内存和辅存之间的调度。每个作业只调入一次，调出一次。
多道批处理系统中大多配有作业调度，其他系统通常不需要作业调度。
中级调度（内存调度）
引入中级调度的目的是提高内存利用率和系统吞吐量，为此将那些暂时不能运行的进程调至外存等待，此时进程的状态称为挂起态。当他们具备运行条件且内存又稍有空闲是，有中级调度来决定把外存上哪些已具备运行条件的就绪进程再重新调入内存，将其状态改为就绪态，挂在就绪队列上等待。
就绪态时间久了或者阻塞态时间久了都可能被挂起。中级调度实际上是存储管理中的对换。
低级调度（进程调度）
按照某种算法从就绪队列中选取一个进程，将处理机分配给它。进程调度是最基本的调度。
三级调度的联系
作业调度从外村的后备队列选择一批作业进入内存，为他们建立进程，这些进程被送入就绪队列，进程调度从就绪队列中选择一个，将其状态改为运行态，把CPU分配给它。中级调度则是为了提高内存利用率，将那些暂时不能运行的进程挂起来。
- 作业调度为进程活动做准备，进程调度使进程正常活动起来。
- 中级调度将暂时不能运行的进程挂起，处于作业调度和进程调度之间。
- 作业调度次数最少，进程调度次数最多。
- 进程调度是最基本的，不可或缺的。
进程调度的目标
不同调度算法有不同的特性，在选择算法的时候，我们需要考虑其性能，人们有很多评价标准，最主要的有：
CPU利用率
尽可能使CPU处于“忙”状态，使这一资源利用率最高。CPU利用率计算方法如下：
吞吐量
单位时间内CPU完成作业的数量
周转时间
指从作业提交到作业完成所经历的时间总和，是作业等待，在就绪队列中排队，在处理机上运行以及输入输出所花费时间的总和
等待时间
作业处于等待处理机的时间总和，等待时间越长，用户满意度越低。处理机调度算法实际上并不影响作业执行或输入输出时间。
响应时间
指从用户提交青岛到系统首次产生响应所用的时间。
调度的实现
调度程序（调度器）
在操作系统中，用于调度和分派CPU的组件称为调度程序，通常由三部分组成
- 排队器。将系统中所有就绪进程按照一定的策略排成一个或多个队列，以便于调度程序选择。每当有一个进程转变为就绪态时，排队器就将其插入到相应的就绪队列。
- 分派器。依据调度程序所选的进程，将其从就绪队列中取出，将CPU分配给新进程。
- 上下文切换器。在对处理机进行切换时，会发生两对上下文的切换操作。第一对，将当前进程的上下文保存到PCB中，再装入分派程序的上下文，以便分派程序运行；第二对，移出分派程序上下文，将新选进程的CPU现场信息装入处理机的各个相应的寄存器。
在上下文切换的时，需要大量的load和store指令，以保存寄存器的内容，因此会花费较多的时间。现在已有硬件方法来减少上下文切换时间。通常采用两组寄存器，其中一组供内核使用，一组供用户使用。这样，上下文切换时，只需要改变指针，让其指向当前寄存器组。
调度的时机，切换与过程
调度程序是系统内核程序，请求调度的事件发生后，才可能运行调度程序。调度了新的就绪进程后，才会进行进程切换。理论上这三件事应该顺序执行。但是实际上操作系统内核程序运行中，若某时刻发生了进程调度的因素，不一定马上进行调度与切换。
不能进行进程调度和切换的情况有：
- 在处理中断过程中。
- 进程在操作系统内核临界区。在进入临界区后，需要独占式地访问，理论上必须加锁，以防止其他并行进程进入，在解锁前不应该切换到其他进程，以加快临界区的释放。
- 其他需要完全屏蔽中断的原子操作过程。如加锁，解锁，中断保护现场，恢复等原子操作。在原子操作中，连中断都要屏蔽，更不应该进行进程的调度和切换。
应该进行进程调度的情况：
- 发生引起调度条件且当前进程无法继续运行下去，可以马上进行调度和切换。若操作系统只在这种情况下进行进程调度，则是非剥夺式调度。
- 中断处理结束或者自陷处理结束后，返回被中断进程的用户态程序执行现场前，若置上请求调度标志，即可马上进行进程的调度与切换。若操作系统支持这种情况下的运行调度程序，则实现了剥夺式调度。
进程的调度方式
所谓进程调度方式，是指某个进程正在处理机上运行时，若有某个更为重要或紧迫的进程需要处理，分为非抢占式调度（适用于大多数批处理系统，但是不适用于分时系统和大多数实时系统）和抢占式调度。
闲逛进程
在进程切换时，如果系统中没有就绪进程，就会调用闲逛进程，如果没有其他进程就绪，该进程就会一直运行。闲逛进程优先级最低，没有就绪进程时才会调用闲逛进程。
它不需要CPU以外的资源，所以不会被阻塞
两种线程的调度
用户级线程。由于内核不知道线程的存在，所以内核还是和以前一样，选择一个进程并给予时间控制。由进程中的调度程序决定哪个线程运行
内核级线程调度。内核选择一个特定的线程运行，通常不考虑该线程属于哪个进程。对被选择的线程赋予一个时间片，如果超过了时间片，就强制挂起。
典型的调度算法
先来先服务（FCFS）算法
最简单的调度算法，既可以用于作业调度，又可以用于进程调度。
在作业调度中，算法每次从后备作业队列中选择最先进入该队列的一个或几个作业，将它们调入内存，分配必要的资源，创建进程并放入就绪队列。
在进程调度中，FCFS调度算法每次从就绪队列中选择最先进入该队列的进程，将处理机分配给它，使之投入运行，知道运行完成或由于某种原因阻塞才释放处理机。
FCFS属于不可剥夺算法，从表面上看，对所有作业都公平，但是如果一个长作业先到达系统，就会使后面许多短作业等待很久，因此并不能作为分时系统和实时系统的主调度策略。
FCFS特点是简单，但效率低，对长作业有利。有利于CPU繁忙型，而不利于I/O繁忙型。
短作业优先（SJF）算法
作业调度时，从后备队列中选择一个估计运行时间最短的作业。进程调度时，从就绪队列中选择一个估计运行时间最短的进程
SJF的平均等待时间与平均周转时间都最少，但是也有缺点：
- 对长作业不利，可能会导致饥饿现象
- 完全未考虑作业的紧迫程度
- 作业长短根据用户提供的估计时间决定的，而用户可能会有意无意缩短其作业的估计运行时间，导致该算法不一定真的是短作业优先
优先级调度算法
优先级调度算法既可用于作业调度，又可用于进程调度。
根据更高优先级进程能否抢占当前正在执行的进程，可将调度算法分为两种：
- 非抢占式优先级调度算法。
- 抢占式优先级调度算法。
根据优先级是否可以改变，可以将优先级分为以下两种：
- 静态优先级。优先级在创建进程时确定，主要依据有进程类型，对资源的要求，用户要求等。
- 动态优先级。在运行过程中，可以动态调整优先级，主要依据有CPU时间长短，就绪进程等待CPU时间等。
高响应比优先算法
结合FCFS和SJF算法，同时考虑可每个作业的等待时间和估计运行时间。
根据公式可知：
- 作业等待时间相同，要求服务时间越短，响应比越高，有利于短作业，类似SJF
- 要求服务时间相同，等待时间越长，响应比越高，类似于FCFS
- 对于长作业，作业的响应比岁等待时间的增加而提高，等待时间足够长也可获取处理机，克服了饥饿现象
时间片轮转调度算法
适用于分时系统。在使用完一个时间片后，即使进程没有执行完成，也必须释放处理机给下一个就绪进程，被剥夺的进程返回就绪队列末尾。
时间片过大，会退化为FCFS，过小又会导致频繁切换。
多级队列调度算法
前面各种算法中，由于系统中仅设置一个进程的就绪队列，即调度算法是固定且单一的，无法满足系统中不同用户对进程调度策略的不同要求。在多处理机系统中，这种单一的调度策略实现机制更为突出，多级队列调度算法能在一定程度上弥补这一缺点。
为每个处理机单独设置一个就绪队列，每个队列实现不同的调度算法。
多级反馈队列调度算法（融合前面所有算法）
是时间片轮转调度算法和优先级调度算法的综合与发展，通过动态调整进程优先级大小和时间片大小，多级反馈队列可以兼顾多方面的系统目标。
实现思路如下：
- 设置多个就绪队列，并为每个队列设置不同的优先级，第一集队列优先级最高，依次递减
- 赋予各个队列进程运行的时间片大小不同，优先级越高，时间片越小
- 每个队里采取FCFS。新进程进入内存后，首先放入第一级队列的末尾，当轮到该进程执行时，如果能在时间片内完成，则撤离系统，如果不行，则转入第二级队列，如果仍未完成，继续往后推，直到降到第n级队列，在第n级队列中采用时间片轮转方式。
- 按队列优先级调度。只有第一级队列为空，才会调度第2级队列。若处理机正在执行第i级队列某个进程，又有新进程进入任一优先级较高队列，此时须立即把当前进程放到第i级队列末尾，把处理机重新分配给高优先级进程。
进程切换
进程切换时在内核支持下实现的，因此可以说，任何进程都是操作系统内核支持下运行的，是与内核紧密相关的
上下文切换
切换CPU到另一个进程需要保存当前进程状态并恢复另一个进程的状态，这个任务称为上下文切换。上下文是指某一时刻CPU寄存器和程序计数器的内容，进行上下文切换时，内存会将旧进程的状态保存在其PCB中。其流程如下：
- 挂起一个进程，保存了CPU上下文，包括程序计数器和其他寄存器
- 更新PCB信息
- 把新进程的PCB移入相应的队列，如就绪，在某事件阻塞等队列
- 选择另一个进程执行，并更新其PCB
- 跳转到新进程的PCB中程序计数器所指向的位置执行
- 回复处理机上下文
上下文切换的消耗
上下文切换是计算密集型，即它需要相当可观的CPU时间，所以上下文切换对系统来说意味着消耗大量的CPU时间。有些处理器提供多个寄存器组，这样上下文切换就只需要简单改变当前寄存器组的指针。
上下文切换和模式切换
模式切换时，CPU逻辑上可能还是在执行同一进程。用户进程最开始都在用户态，如果因为中断或异常进入核心态，执行完后又回到用户态刚被中止的进程运行。用户态和内核态之间切换叫做模式切换而不是上下文切换，没有改变当前进程。
上下文切换只能发生在内核态。