调度和死锁

处理机=处理器(cpu)+主存储器+输入输出设备接口

调度的实质是一种资源分配

1，处理机调度

​ 一个作业从提交到获得处理机执行，直至运行完毕，可能需要经历多级处理机调度，处理机调度有一些层次：

1. 高级调度，也称作业调度，他的调度对象是作业。主要根据一些算法，决定将外存上处于后备队列中的那几个作业调入内存，为其创建进程，分配必要的资源，并将她们放入就绪队列
2. 低级调度，也称进程调度，调度对象是进程。根据一些算法决定就绪队列中那个进程应获得处理机处理
3. 中级调度，也称内存调度。主要目的是提高内存利用率。暂时吧不能运行的进程调至外存，当他们具备运行条件时，将其重新调入内存，并修改状态为就绪状态。中级调度实际上就是存储器管理中的对换功能。

进程调度的运行频率最高，作业调度的周期较长，中级调度处于两者之间。

2，作业调度

​ 作业：是比程序更为广泛的概念，不仅包含了通常的程序和数据，还应配有一份作业说明书，根据说明书来对程序进行控制。在OS中，是以作业为基本单位从外存调入内存的

​ 作业步：每个作业必须经过若干个相对独立又相互关联的顺序加工步骤才能得到结果。比如，一个典型的作业步可分成：编译作业步，链接装配作业步，运行作业步

​ 作业控制块（Job Control Block）：每个作业都被设置了一个JCB，其中保存了系统对作业进程管理和调度的全部信息。

​ 作业的三种状态：

1. 后备状态。为作业建立JCB，并把它放入作业后备队列中。
2. 运行状态。一个作业从第一次进入就绪状态开始，直到它运行结束前，在此期间都处于运行状态。
3. 完成状态。当作业运行完成、或发生异常情况而提前结束时，作业便进入完成状态。

​ 作业调度主要任务：根据JCB中的信息，检查系统中的资源能否满足作业队资源的需求，以及按照一定的调度算法，从外存的后备队列中选择作业调入内存，并为他们创建进程，分配必要的资源

调度算法

1. 先来先服务算法（FCFS）

该算法既可用于作业调度，也可用于进程调度。系统会按照作业到达的先后次序来进行调度。

1. 短作业优先（SJF）

以作业的长短（运行时间）来计算优先级，作业越短，优先级越高。

缺点：

1. 优先级调度算法（PSA，priority scheduling algorithm）

对于FCFS来说，作业的等待时间就是作业的优先级，等待时间越短，优先级越高；对于SJF来说，作业的长短就是优先级。但是这两种优先级都不能反应作业的紧迫程度。

PSA则是基于作业的紧迫程度，由外部赋予作业相应的优先级，PSA根据该优先级进行调度，可以保证紧迫性作业优先运行。

1. 高响应比优先调度算法（HRRN）

FCFS算法只考虑了作业的等待时间，而忽略了作业运行时间；SJF算法正好相反，只考虑了作业运行时间，忽略了作业等待时间

HRRN算法则既考虑了作业的等待时间也考虑了作业的运行时间，既照顾了短作业，又不至于让场作业的等待时间过长

3，进程调度

进程调度的任务：

1. 保护处理机现场信息。比如保护程序计数器、多个通用寄存器中的内容
2. 按某种算法选取进程。
3. 吧处理器分配给进程。

进程调度算法：

1. 轮转调度

是一种非常公平的算法。让就绪队列上的每个进程每次仅运行一个时间片。如果队列上有n个进程，则每个进程每次大约都可以获得1/ n的处理机时间

1. 优先级调度

吧处理机分配给就绪队列中优先级最高的进程。分为两种算法：

1. 多队列调度

前面各种进程调度算法都是在系统中仅设置了一个进程就绪队列，无法满足不同用户对进程调度策略的不同要求。

多队列调度算法将进程就绪队列从一个拆分成若干个。将不同类型或性质的进程分配在不同的就绪队列，不同的就绪队列采用不同的调度算法，一个就绪队列中的进程可以设置不同的优先级，不同的就绪队列也可以设置不同的优先级

4，死锁

死锁概念

​ 死锁：一组进程中的每一个进程都在等待仅由改组进程中的其他进程才能引发的事件，那么该组进程是死锁的

​ 产生死锁的四个必要条件，打破一个死锁就不会发生：

1. 互斥。必须存在需要互斥使用的资源。
2. 占有等待。在出现死锁的系统中一定有已分配到了某些资源且在等待另外资源的进程。
3. 不可剥夺。在出现死锁的系统中一定有不可剥夺使用的资源。不可剥夺是指在进程未主动释放资源之前不可夺走其占有的资源
4. 循环等待。一定存在一个处于等待状态的进程集合

预防死锁

​ 通过破坏死锁存在的必要条件来防止死锁发生。

1. 破坏互斥条件

如果允许资源都能共享使用，则系统不会进入死锁。不过一些资源共享使用无法保证正确性。比如，对临界资源的访问就必须互斥进行

1. 破坏占有等待条件，有两种方法

   1. 使进程申请到了它所需要的所有资源才能开始运行
   2. 在进程提出申请资源前，必须释放已占有的所有资源

2. 破坏非剥夺条件，有两种方法

   1. 当进程Pi申请Ri类资源时，资源管理者检查Ri中有无可分配的资源。有，则分配给Pi，否则，将Pi战友的全部资源回收而让申请进程进入等待状态
   2. 当进程Pi申请Ri类资源时，资源管理者检查Ri中有无可分配的资源。有，则分配给Pi，否则，检查占有Ri类资源的进程Pj。若Pj处于等待资源状态，则剥夺Pj拥有的Ri类资源分配给Pi，若Pj不处于等待资源状态，则置Pi于等待资源状态
3. 破坏循环等待条件

避免死锁

​ 在进行资源分配时，判断如果满足这次分配资源后是否仍存在一条确保系统不会进入死锁状态的路径，如果没有这样的路径，即使现有资源满足申请，也拒绝分配。

​ 避免死锁主要采用银行家算法：银行家算法是从当前状态出发，按照系统各类资源剩余量逐个检查各进程需要申请的资源量，找到一个各类资源申请量均小于等于系统剩余资源量的进程P1。然后分配给该P1进程所请求的资源，假定P1完成工作后归还其占有的所有资源，更新系统剩余资源状态并且移除进程列表中的P1，进而检查下一个能完成工作的客户，......。如果所有客户都能完成工作，则找到一个安全序列，银行家才是安全的。若找不到这样的安全序列，则当前状态不安全。

​ 银行家算法中相关数据结构：描述系统中课利用的资源、所有进程对资源的最大需求、系统中的资源分配、以及所有进程还需要多少资源的情况。

1. 可利用资源向量Available。这是一个含有m个元素的数组，其中的而每一个元素代表一类可利用资源数目，其初始值是系统中所配置的该类全部可用资源的数目，其数值随该类资源的分配和回收而动态的改变。如果Available[j]=K,则表示系统中现有Rj类资源K个。
2. 最大需求矩阵Max。这是一个n*m的矩阵，它定义了系统中n个进程中的每一个进程对m类资源的最大需求。如果Max[i,j]=K；则表示进程i需要Rj类资源的最大数目为K。
3. 分配矩阵Allocation。这也是一个n*m的矩阵，它定义了系统中每一类资源当前已分配给每一进程的资源数。如果Allocation[i,j]=K，则表示进程i当前已分得Rj类资源的数目为K。
4. 需求矩阵Need。这也是一个n*m的矩阵，用以表示每一个进程尚需的各类资源数。如果Need[i,j]=K,则表示进程i还需要Rj类资源K个，方能完成任务。

检测死锁

​ 可以利用资源分配图来检测是否发生死锁

解除死锁

1. 抢占资源

从一个或多个进程中抢占足够数量的资源，分配给死锁进程，以解除死锁状态

1. 终止进程

终止系统中一个或多个死锁进程，直至打破循环环路，使系统从死锁状态解脱出来