处理机调度与死锁

通过中断才能执行调度，否则，就会一直运行这一个程序直到完成。

处理机调度的层次和调度算法的目标

1. 处理机调度的层次

   1. 高级调度（长程调度/作业调度），频率较低，因此可以用花费时间长的算法

      调度对象：作业

      用处：将外存上的作业调度到内存上

      适用：多道批处理

      不适用：实时分时

   2. 中级调度（内存调度）

      调度对象：进程

      用处：将暂时不能运行的进程调度到外存上

   3. 低级调度（进程调度/短程调度），频率高，所以要简单快

      调度对象：进程

      用处：给就绪队列中的任务分配处理机

      适用：所有

2. 处理机调度算法的目标

   1. 共同目标：资源利用率，公平性，平衡性，策略强制执行（必须按指定的策略执行）
   2. 批处理系统：平均周转时间短（一般用带权周转时间来衡量$W=\frac{1}{n}\sum_{i=1}^{n}\frac{T_i(作业周转时长）}{T_s(系统提供服务时间)}$，系统吞吐量高，利用率高。
   3. 分时系统：响应速度快，均衡性
   4. 实时系统：截止时间的保证，可预测性

作业与作业调度

1. 批处理系统中的作业

   作业：包含程序，数据，和一个说明书，在批处理系统中是以作业为单位从外存调到内存。实际上就是一个宏观上的任务。

   作业步：实际上就是每一步

   作业控制块：为了调度作业，在作业进入系统的时候，给每一个作业设置一个控制块JCB。通过JCB来控制作业。

   三个阶段和三个状态：收容阶段（输入）→后备状态（放在后备序列中）→运行阶段(运行状态)→完成阶段(完成状态)

2. 作业调度的主要任务：接纳多少个作业(利用率和配置上的抉择)和接纳哪些作业（策略）

3. 先来先服务FCFS：选择队列中等的最久的调入内存。但现在已经很少使用FCFS，一般都是混合使用。

4. 短作业优先SJF：根据作业运行时长进行判断，越短优先级就越高。

   缺点：必须预估运行时间；对长作业不利；人机无法交互；未考虑作业紧迫程度

5. 优先级调度算法PSA：根据作业的紧迫程度，由外界赋予优先级，优先级高的先运行。

6. 高响应比优先调度算法HRRN：$优先权=\frac{等待时间+要求服务时间}{要求服务时间}$，即考虑了等待时间也考虑了作业长短，当等待时间相同，则跟短作业一致，要求服务时间相同，则更FCFS相同。

进程调度

进程调度的任务有三：保留现场信息，选取新进程，分配给该进程。

一般由3个部分组成：

1. 排队器：按一定策略排队，以便分配器快速拿到要使用的进程
2. 分派器：将进程从排队器中取出，然后交与上下文切换器。
3. 上下文切换器：首先保存当前进程，然后将新选的装入处理器的寄存器。

调度方式：

1. 非抢占模式：直到程序运行完，才切换；或者产生了阻塞。实现简单，适用于批处理系统，但不适合分时和实时。
2. 抢占模式：允许随时暂停一个正在运行的程序；能够实现人机交互，满足实时性任务，也能避免长任务长时间占用。但需要按照优先权，短进程优先和时间片原则。

各种调度算法：

1. 轮转调度算法：按照就绪队列的顺序，每次给队首一个时间片的时间执行，若时间片用完，则扔至末尾，或者任务已经完成，就切换下一个队首。能够保证在一个确定的时间内就能进行一次CPU执行。

   但是时间片很难确认：时间片太短，切换的太频繁。时间太长，就变成FCFS了。

2. 优先级调度算法：

   非抢占式：每次分配给最高优先级的完成，直到完成之后，才能选择下一个优先级最高的

   抢占式：每次进来一个新的，如果优先级比在运行的更高，就立即打断，开始执行新的

   优先级的确定：

   静态优先级：用一个某一范围内的一个整数来表示。一般用进程类型，进程对资源的需求和用户要求来确定这个整数的大小，但这种方法可能不够精确，可能会发生优先级低的进程永远不被调用。

   动态优先级：在一开始赋予一个数值后。随着时间的进行，可以逐渐升高，或者如果随着占用CPU时间越来越久，逐渐降低等。

3. 多队列调度算法

   设置多个队列，每个队列采用不同的策略，而每个队列使用一个处理机，就很完美。

4. 多级反馈队列调度算法

   无需知道各种进程所需执行时间，是一种当前较好的进程调度算法。

   设置多个就绪队列，按优先级设置为队列1-n。越小越高。

   第i个就绪队列的时间片为第i-1个的2被。

   所有队列采用FCFS算法，从高到低执行轮转法，但是当一个时间片结束但任务没完成的，就扔到次一级的就绪队列的队尾，而对于第i个队列，只有前面所有队列都没任务了，才运行本队列。

   但如果在为第i队中的某个进程服务，但是突然来了一个更高的，就直接扔回队尾，去执行更高的。

5. 基于公平原则的调度算法

   保证调度算法：保证每个进程从创建开始分配到的时间是平均的。

   实现方法：每次计算所有进程实际执行时间和应当执行时间的比例，选择比例最小的执行，直到他不是最小的。

   公平分享调度算法：如果每个用户所拥有的进程数不同，就会对用户不公平。这种调度算法就是要使每一个用户的获得的

实时调度

1. 为了实现实时调度，需要：（HRT，硬实时任务，SRT，软实时任务）

   就绪时间；开始和完成截止时间；处理事件；资源需求；优先级

   高性能：因为对于实时调度，对性能是有一个硬性指标的，只要低于某一个量就必然完成不了

   采用抢占式调度：满足HRT对截止时间的要求。但如果是对于小一点的系统，非抢占式也问题不大，但是要所有的实时任务都较小，并能及时释放处理器。

   能够快速切换：快速响应中断和快速任务分配（切换）

2. 非抢占式轮转调度算法：为每一个对象创建一个实时任务，建立一个轮转队列，当任务完成后，就挂到轮转队列的末尾等待，继续选择下一个执行，会产生数秒到数十秒的延迟。

3. 非抢占式优先调度算法：如果其中具有一些有一定要求的实时任务，可以为这些赋予比较高的优先级，将他们放在队首，在完成当前任务后，就可以执行这些优先级高的任务。响应时间减少到数秒至数百毫秒。

4. 基于时钟中断的抢占式优先级调度算法：当时钟中断的时候，才根据优先级进行抢断，可降至几十到几毫秒。

5. 立即抢占的优先级调度算法：立即剥夺抢占。

1. 最早截止时间优先EDF

   1. 非抢占式用于非周期实时任务：根据当前所有任务中截止时间最早的确定下一个任务
   2. 抢占式用于周期实时任务：实时根据截止时间最早的抢占，相较于固定优先度是更优的。

2. 最低松弛度优先LLF

   依据的标准是松弛度：松弛度就是距离最晚开始时间（截止时间-任务时长）的时长。

3. 优先级倒置

   按理来说，不管是抢占式还是是非抢占式，都应该是优先级高的优先，但是，如果优先级高的P1来晚了，而与其共享资源的P3是一个优先级低的进程，而在运行到与其共享资源占用资源后却被另一个进程抢占了，就会导致P1的延迟运行。

   

   方法1:进程在进入临界区后不允许被抢占。这在临界区不长的时候问题不大，但如果很长的话就也要等待很长时间。

   方法2:当一个更高优先级的使用相同临界资源的进入队列并因为临界资源发生阻塞，就将其优先级在临界区结束前都赋值给占用临界资源的进程，避免被抢占。这种方法可能在更加复杂的情况下更优？

死锁概述

1. 对于计算机中的资源可以从两方面分类。

   一方面是：可重用性上来说

   1. 可重用性资源：一般在运行时总数固定，在一个进程使用完后就会归还
   2. 可消耗性资源：在运行时由进程动态创建，因此一直是在变化的，如进程通信的消息

   另一方面是：从可抢占性上来说

   1. 可抢占性资源：指某进程获得该资源后会被其他进程或系统抢占，如CPU和内存
   2. 不可抢占性：当资源被分配后，不能强行回收，必须等待进程使用完后自动释放，如磁盘

2. 引起死锁的三种情况

   1. 竞争不可抢占性资源

      

      当出现类似这种情况的时候，就会发生死锁。如果用资源分配图描述：

      

      当形成一个环的时候就是死锁。

   2. 竞争可消耗性资源

      当三个进程按照一个圈的形状互相发送消息，如果先都进行receive的等待，就会产生死锁，如果用资源分配图也会新城一个环。

      

   3. 进程推进顺序不当

      当有两个进程和两个共享资源时，推进方式有多种可能，但如果进入了阴影区域，就是不安全区，就会产生死锁，但实际上我感觉就是上面的两个的总结。

      

3. 死锁：如果一组进程中的每一个进程都在等待仅由改组进程中的其他进程才能引发的时间，那么这组线程是死锁的。

4. 产生死锁的4个必要条件：互斥条件；请求和保持条件（在持有不可抢占资源的情况下去请求新资源）；不可抢占；循环等待条件。

5. 处理死锁的方法：预防死锁（通过各种限制条件来破坏四大条件），避免死锁（在资源分配的过程中，防止进入不安全去），检测死锁（检测到之后强制脱离），解出死锁。

预防死锁

一般破坏的都是后三个条件。

1. 破坏请求和保持

   有两种协议实现。

   1. 要求进程一开始就将所有资源都请求到，这样就不会再发生请求了，也就破坏了请求和保持。

      但是资源被严重浪费并且可能发生饥饿现象（所需的所有资源可能得过很久才能被其他进程释放掉）

   2. 允许一开始并不请求所有资源，但每次要请求新的资源的时候都要将持有的所有不可抢占资源全部释放。把第一种方式的两个弊端都避免了。

2. 破坏不可抢占

   相较于前一种，是在程序中进行逐步的合理的释放逻辑，而这个这是要强硬地破坏掉不可抢占。当要请求新的资源的时候，直接将不可抢占的释放掉，直到需要的时候再拿回来。

   但这种方法不仅实现复杂，并且要付出很大代价，不仅延长了进程的周转时间，加大了开销还降低了吞吐量。

3. 破坏循环等待条件

   将所有的不可抢占资源都进行排序并标号，要求所有的进程都必须按顺序从小到大请求资源。如果要请求一个比已经持有的更小的资源，就必须先释放更大的，然后，再从小重新请求。

   这时候序号的设定的合理性就很关乎性能了。这种方法的资源利用率和系统吞吐量都有改善。

   但是，限制了新设备的增加；当进程使用顺序不是顺序的时候就会造成对资源的浪费；限制了编程的自由度。

避免死锁

1. 安全状态：系统能按照某种进程推进顺序为每个进程分配其所需资源，直至其最大需求，是每个进程都可顺利完成。

   而只要一进入不安全状态，就可能导致死锁。

   因此需要在每一次请求的时候都判断这一次请求时候会导致自己进入不安全状态。

2. 银行家算法：对于每一次请求，都要记录当前可用资源数量Available，最大需求矩阵Max，分配矩阵Allocation，和需求矩阵Need(=Max-Allocation)。

   每一次在请求的时候，假设请求大小为Req。

   首先判断Req≤Need，不成立则说明请求非法。

   判断Req≤Available，不成立说明暂时资源不够，需要等待。

   进行实际分配，Allocation+=Req，Need-=Req，Available-=Req。

   进行安全性检验。

   在检验的每一轮中都要记录截止当前完成的进程为止有多少Avai的资源Work，和是否完成Finish.

   每一轮寻找一个未完成(Finish=false)并且资源需求量Need≤当前Avai的资源Work的进程（能按照某种进程推进顺序为每个进程分配其所需资源，直至其最大需求，是每个进程都可顺利完成），如果找不到，则不安全。

   如果找到，则分配，Work+=Allocation(假设这个进程被分配资源后并且运行完了)，Finish=true。

   当能够找到一个序列包含所有进程，则安全。

死锁的检测与解除

1. 死锁的检测

   需要一直记录所有资源的状态，可以使用资源分配图来记录。

   资源分配图中，由资源指向进程的一根线就代表分配一个资源给这个进程，由进程指向资源的一根线表示进程请求一个这个资源。

   死锁检测的方法：找到一个不阻塞也不独立且能够在当前资源分配图下满足其所有Req边的进程（所有的Req≤Work），消去他的所有边，不断重复，如果能消去所有边，则不死锁，否则死锁。

2. 死锁的解除

   一种是人工来解除

   另一种是用死锁解除算法

   1. 抢占资源。从其他进程里面抢一点资源给死锁进程。

   2. 停止进程。直接停止死锁进程，直到循环不成立，不再死锁。

      1. 终止所有死锁进程，但代价很高
      2. 按照代价最低的策略逐个释放死锁进程，但需要每一次释放都要计算一次当前时候仍然处在死锁的状态。但这个“代价最低”很难衡量。

   3. 付出代价最小的死锁 解除算法

      一种方式就是暴力所有解除的顺序，但代价很高。

      另一种方式就是对于每一次的所有能够选择进行解除的进程，找到其中代价最小的一个进行解除。直到不死锁。但这并不是最优的。