操作系统第三章

目录

一、处理机概念

什么是处理机？

处理机与CPU的区别？

二、处理机调度概念？

（一） 处理机调度的三个形式

1、高级调度：

2、低级调度

3、中级调度

 （二）作业和作业调度

作业的概念

作业控制块

作业调度工作原理

（三）进程调度

进程调度的三个任务

进程调度的方式

三、调度算法

（一）先来先服务（FCFS）

（二）短作业优先（SJF）

（三）优先级调度算法

特列算法：高响应比优先调度算法（HRRN）

（四）轮转调度算法（RR）

（五）多级队列调度算法

（六）多级反馈队列调度算法

（七）基于公平原则的调度算法

1、保证调度算法

2、公平分享调度算法

处理机包括中央处理器，主存储器，输入-输出接口，加接外围设备就构成完整的计算机系统。处理机是处理计算机系统存储程序和数据，并按照程序规定的步骤执行指令的部件。程序是描述处理机完成某项任务的指令序列。指令则是处理机能直接解释、执行的信息单位。

因为内存中肯定会有很多很多的进程，而处理机的数量是有限的，当进程数量远远大于处理机时，进程将无法有序高效率的执行。

此时就出现了处理机调度算法：按照算法动态地将处理机分配给处于就绪状态的进程。

调度说白了是一种资源的分配，为各种进程协调分好资源，不让这些进程争抢资源，有序高效的执行各种进程。

又称为：作业调度

调度对象：作业

功能：根据算法，决定将外存上处于后备队列的哪几个作业调入内存，为他们创建进程、分配必要的资源，并将它们放入就绪队列。

适用系统：适合多道批处理系统，不适合分时系统和实时系统。

运行频率：较低

又称为：进程调度 

调度对象：进程

功能：根据算法，决定就绪队列中的哪个进程应获得处理机，并由分派程序将处理机分配给被选中的进程。

适合系统：适合多道批处理系统，分时系统和实时系统。

运行频率：中

又称为：内存调度

调度对象：进程

功能：把那些内存中暂时不能运行的进程调至外存等待 ，此时进程的状态为就绪驻外存状态（挂起状态），相当于存储器管理中的对换功能，目的就是提高内存利用率和系统吞吐量。

运行频率：最高

作业比程序的概念更为大，作业=程序+数据+作业说明书

每一个作业设置一个作业控制块JCB，JCB中是系统对作业进行管理和调度所需的全部信息。

JCB内容：作业标志、用户名称、用户账号、作业类型、作业状态、调度信息、资源请求情况、资源使用情况。

根据JCB中的信息，检查系统中的资源能否满足作业的需求，若满足，此时根据某种调度算法从外存上的作业后备队列中选择一个作业调入内存。

调度算法有：先来先服务、短作业优先调度、基于作业优先级、响应比高者优先。 

保存CPU现场信息：执行进程调度时，要首先保存当前进程的CPU现场信息。

按某种算法选取进程：按照算法从进程就绪队列中选择一个，将其改为运行状态。

把CPU分配给进程：分配CPU，并准备把进程中的PCB内有关CPU的现场信息装入CPU相应的各个寄存器中。 

非抢占调度方式

抢占调度方式：不是任意的，有3个原则。

原则1：优先级原则，允许优先级高的并且是新到的进程可以抢占当前进程的处理机。

原则2：短进程原则

原则3：时间片原则

衡量算法好坏快慢的标准：平均周转时间、平均带权周转时间（考试要计算）

周转时间=进程完成时间-进程提交时间  

周转时间：相当于我去面试，从我开始签到开始一直到我面试结束为止这期间的总时间。包括了我等待前面面试者的时间。  

带权周转时间=进程周转时间 / 进程运行时间

算法原理：按照作业（进程）到达的先后次序来进行调度，谁先来，谁就先被调度。

缺点：忽略了作业的运行时间

使用表格法，直接把所有进程的其他时刻也推算出来，如进程开始执行的时间、进程完成的时间、紧接着就可以推出进程周转时间，继而推出带权周转时间。

算法原理：以作业的长短来计算优先级，作业越短优先级越高，作业长短以所要求的运行时间来衡量。

 缺点：必须预先知道作业的运行时间、对长作业不利，未考虑作业的紧迫程度。

我们首先是比较此刻时间已经提交的进程 ，如第一个进程完成时刻，就需要判断下一个谁作业短的进程，要从已经提交的进程中选择，那些还未提交还未到达的进程不能拿来选择。

如下面图中：作业1完成时间是9:00，要在9点之前提交的进程中选择一个最短作业的进程，这里容易忽略掉作业4是9:10到达且作业时间最短，不要把作业4拿来比较，因为9点时刻，作业4还未提交还未到达。

算法原理：FCFS、SJF两种算法都不能反映进程的紧迫程度。而优先级调度算法是外部赋予进程相应的优先级，来体现出进程的紧迫程度，紧迫性进程优先运行。

1、利用某一范围内的一个整数，优先数

2、响应比的大小，谁响应比大，谁优先级就大——高响应比优先调度算法

算法原理：谁的响应比大，谁先执行获取CPU和系统资源。

优点：即考虑了作业的等待时间，又考虑了作业的运行时间；即照顾了短作业，又不会致使长作业的等待时间过长。

优先级是动态改变的。优先级=响应比

响应时间=等待时间 + 要求运行时间  

或者 响应时间=前一个进程完成时间-该进程的提交时间

响应时间大白话说就是——该进程自从进入就绪队列后所等待所呆的的时间

响应比=响应时间 / 要求运行时间       

适合系统：分时系统

算法原理：基于时间片的轮转，非常公平，就绪队列中的每一个进程每次仅仅运行一个时间片，并且每个进程是轮流运行。

首先按照FCFS策略把就绪进程排成一个就绪队列，设置时间片，从第一个进程开始分配处理机，第一个进程的时间片执行完后，再从就绪队列中新的队首进程开始。若进程已经运行完，注意此时第一个进程就已经不在就绪队列的队首，而是从就绪队列中删除。若未执行完只是时间片完了，则是调度程序把它送往末尾去了。

时间片太小，意味着系统会频繁地执行进程调度和进程上下文切换，会增加系统的开销。

时间片太大，RR调度算法便会退化为FCFS调度算法。

以时间片q=1为例，首先处理机会调度进程A，把资源CPU分配给进程A，进程A执行完1个时间片后，处理机会收回资源CPU，而进程A还为执行完，把它放入就绪队列末尾。

紧接着处理机会调度进程B，以同样的工作原理执行。

直到某个进程所要求的服务时间已满足，把该进程从就绪队列中删除。

由于设置了多个就绪队列，对不同的队列就可以采用不同的调度算法了，系统就有针对性的提供多种调度策略。

这样就很方便地为每个处理机设置一个单独的就绪队列，每个处理机就可以实施不同的调度策略。

由于基于短作业优先、基于进程长度的抢占式优先调度算法有一个局限性——必须要指明进程的长度才可以。

多级反馈队列调度算法——就不需要事先知道各种进程所需的执行时间。目前公认较好的一种进程调度算法。

设置多个就绪队列，每个队列赋予不同的优先级，第一个队列优先级最高，并且首先调度最高优先级，也就是第一个队列里面的所有进程，仅当第一个队列空闲时，才开始调度第二个队列中的进程运行。优先级越高的队列，时间片越小。

当新进程进入内存后，首先将它放入第一个队列的末尾，按照FCFS策略等待调度。如果该进程能够在该就绪队列的时间片内完成就撤离系统，如果不能完成，就将其转入第二个队列的末尾等待调度。以此类推。

只是满足了进程优先运行，但是不能保证进程占用了处理机多长时间，未考虑调度的公平性。

不是优先运行保证，而是做到调度的公平性，保证每一个进程获得相同的处理机时间。

该算法需系统具有以下功能：

公平衡量：以用户能获得的处理机时间为公平原则，要求每个用户所获得的处理机时间相同，因为每个用户的进程数量是不一样的。

若某用户进程少，就要给该用户的该进程多一点处理机时间。