处理机调度和进程调度

  在多道程序系统中，进程的数量往往多于处理机的个数，这样不可能同时并行地处理各个进程。处理机的调度就是 从就绪队列中按照一定的算法选择一个进程并将处理机分配给它运行 ，以实现进程的并发执行。

  调度的方式： 高级调度、中级调度、低级调度。

  由于内存空间有限，有时无法将用户提交的作业全部放入内存中，因此需要确定某种规则来决定作业调入内存的顺序。

   高级调度（作业调度） ：按照一定的原则从外存上处于后备队列的作业中挑选一个或多个作业，给他们分配内存等必要资源，并建立相应的进程（ 建立PCB ），以使它（们） 获得竞争处理机的权利。

   高级调度是外存与内存之间的调度。 每个作业只调入一次，调出一次。作业调入时会建立相应的PCB，作业调出时才撤销PCB。高级调度主要是指调入的问题，因为只有调入的时机需要 *** 作系统来确定，但调出的时机必然是作业运行结束才调出。

  在引入虚拟存储技术之后，可以将暂时不能运行的进程调至外存等待，等它重新具备了运行条件且内存又稍有空间时，再重新调入内存。

  这样做是为了提高内存利用率和系统吞吐量。

  暂时调到外存等待的进程状态为 挂起状态 ，但是进程的PCB不会一起调到外存，而是会 常驻内存 。PCB中会记录进程数据在外存中的存放位置，进程状态等信息， *** 作系统通过内存的PCB来保持对各个进程的监控、管理。被挂起的进程PCB会被放到挂起队列中。

   中级调度（内存调度） ，就是按照某种规则，从挂起队列中选择合适的进程将其数据重新调回内存。

  一个进程可能会被多次调出、调入内存。因此中级调度发生的频率比高级调度更高

   低级调度（进程调度） ：其主要任务是按照某种方法和策略从就绪队列中选取一个进程，将处理机分配给它。

  进程调度是 *** 作系统中最基本的一种调度，在一般的 *** 作系统中都必须配置进程调度。

  进程调度的频率很高，一般几十毫秒一次。这样才能保证多进程在宏观是同时进行的。

  需要进行进程调度与切换的情况：

  不能进行进程调度与切换的情况：

   非剥夺调度方式，又称非抢占式。 即只允许进程主动放弃处理机，在运行过程中即使有更紧急的任务到达，当前进程依然会继续使用处理机，直到该进程终止或要求进入阻塞态。

  实现简单，系统开销小但是无法及时处理紧急任务，适合早期批处理 *** 作系统。

   剥夺调度方式，又称抢占式。 当一个进程正在处理机上执行时，如果有一个更重要更紧急进程要使用处理机，即立即暂停正在执行的进程，将处理机分配给更重要更紧急的那个进程。

  可以优先处理更紧急的进程。也可以实现各进程按时间片轮流执行的功能（通过时钟中断）。适合分时 *** 作系统、实时 *** 作系统。

  由此可见， 进程的切换是有代价的 ，因此如果进程切换调度过于频繁的话，必然会使整个系统的开销过大，效率降低。因为系统大部分时间都花在进程切换上，真正用于执行进程的时间少。

  评价指标： CPU利用率、系统吞吐量、周转时间、等待时间、响应时间。

  CPU利用率：指CPU忙碌的时间占总时间的比例。

   CPU利用率 = 忙碌时间 / 总时间。

  如某计算机只支持单道程序，某个作业刚开始需要在CPU上运行5s，再用打印机打印输出5s，之后再执行5s，在此过程中：

  CPU利用率=(5 + 5) / 15 = 66.67%.

  打印机利用率=5 / 15 = 33.33%.

  系统吞吐量：单位时间内完成作业的数量。

   系统吞吐量=总共完成了多少道作业/总共花了多少时间

  周转时间：指从作业被提交给 *** 作系统开始，到作业完成为止的这段时间间隔。

  包括四个部分：作业在外存设备队列上等待作业调度（高级调度）的时间、进程在就绪队列上等待进程调度（低级调度）的时间、进程在CPU上执行的时间、进程等待I/O *** 作完成的时间。

   作业周转时间= 作业完成时间 – 作业提交时间

   平均周转时间 = 各作业周转时间之和 / 作业数

   带权周转时间 = 作业周转时间 / 作业实际运行时间

   平均带权周转时间 = 各作业带权周转时间之和 / 作业数

   等待时间：指进程或作业处于等待处理机状态时间之和。

   平均等待时间：各个进程/作业等待时间的平均值。

  对进程来说，等待时间就是指进程建立后等待被服务的时间之和。

  对于作业来说，不仅要考虑建立进程后等待的时间（进程建立时作业已经进入了内存），还要加上作业在外部存后备队列中等待的时间。

  响应时间：指从用户提交请求到首次产生相应所用的时间。

   本文完

  如发现错误，请指正！！！

在多道程序系统中，调度的实质是一种资源分配，处理机调度是对处理机资源进行分配。处理机调度算法是指根据处理机分配策略所规定的处理机分配算法。

在多道程序系统中，进程的数量远远多于处理机的个数，因此进程争用处理机的情况在所难免。处理机调度是对处理机进行分配，即从就绪队列中按照一定的算法（公平、高效）选择一个进程并将处理机分配给它运行，以实现进程的并发执行。

高级调度又称 长程调度 或 作业调度 ，它调度的对象是 作业 。其主要功能是根据某种算法，决定将外存上处于后备队列中的哪几个作业调入内存，为它们创建进程、分配必要的资源，并将其放入就绪队列。

高级调度主要用于多道批处理系统中，在分时系统和实时系统中不设置高级调度。高级调度的执行频率较低，通常为几分钟一次。

低级调度又称为 进程调度 或 短程调度 ，其所调度的对象是 进程 或 内核级线程 。其主要功能是根据某种算法决定就绪队列中哪个进程应获得处理机，并由分派程序将处理机分配给被选中的进程。

进程调度是最基本的一种调度，在多道批处理、分时系统和实时系统三种类型的OS中都必须设置这种调度。进程调度的频率很高，一般几十毫秒一次。

中级调度又称 内存调度 。引入中级调度的目的主要是提高内存的吞吐率和系统吞吐量。为此应把那些暂时不能运行的进程调至外存等待，此时进程的状态称为 就绪驻外存状态（或挂起状态） 。当它们已具备运行条件且内存又稍有空闲时，由中级调度来决定把外存上那些已具备运行条件的就绪进程再重新调入内存，并修改其状态为就绪状态，挂在就绪队列上等待。中级调度实际上就是存储器管理中的对换功能。

为了管理和调度作业，在多道批处理系统中，为每个作业设置一个作业控制块JCB，它是作业在系统中存在的标志，其中保存了系统对作业进行管理和调度所需的全部信息，例如 作业标识 、 用户名称 、 用户账号 、 作业类型（CPU繁忙型、I/O繁忙型、批量型、终端型） 、 作业状态 、 调度信息（优先级、作业运行时间） 、 资源需求（预计运行时间、要求内存大小等） 、 资源使用情况 等。

每当一个作业进入系统时，由“作业注册”程序为该作业建立一个JCB，再根据作业类型放到相应的后备队列中等待调度。调度程序根据一定的调度算法来调度它们，被调度的作业将被装入内存。在作业运行期间，系统根据JCB中的信息和作业说明书对作业进行控制。当一个作业执行完毕后，系统负责回收分配给它的资源，并撤销该JCB。

作业调度的主要任务是 根据JCB中的信息，检查系统中的资源是否满足作业对资源的需求，以及按照一定的调度算法，从外存的后备队列中选取某些作业调入内存，并为它们创建进程、分配必要的资源，然后将新创建的进程排在就绪队列上等待调度 。因此也把作业调度称为“接纳调度”。在每次执行作业调度时，都需要决定 接纳多少个作业 和 接纳哪些作业 。

进程调度和切换的程序是 *** 作系统的内核程序。请求调度的事件发生后，才可能运行进程调度程序，调度了新的就绪进程后，才会进行进程间的切换。在实际设计中， *** 作系统的内核程序运行时，若发生了引起进程调度的因素，也不一定能够马上进行进程调度与切换。

不能进行进程调度与切换的原因有：

若上述过程中发生了引起调度的条件，不能马上进行进程的调度与切换，应置系统的请求调度标志，直到上述过程结束后再进行相应的调度与切换。

应该进行进程的调度与切换的情况如下：

进程切换往往在调度完成后立刻发生。

进程调度方式是指 某个进程正在处理机上执行时，若有某个更为重要或紧迫的进程需要处理，即有更高优先权的进程进入就绪队列，此时应该如何分配处理机。

进程调度通常有 非剥夺调度方式 和 剥夺调度方式 两种方式。

又称 非抢占方式 ，是指当一个进程正在处理机上执行时，即使有某个更为重要或紧迫的进程进入就绪队列，仍然让正在执行的进程继续执行，直到该进程完成或发生某种事件而进入阻塞状态时，才把处理机分配给更为重要或紧迫的进程。在非剥夺调度方式下，一旦把CPU分配给一个进程，该进程就会保持CPU直到终止或转换到等待态。

非剥夺调度方式适合大多数的批处理系统，但不能用于分时系统和大多数的实时系统。

又称 抢占方式 ，是指当一个进程在处理机上执行时，若有某个更为重要或紧迫的进程需要使用处理机，则立即暂停正在执行的进程，将处理机分配给这个更为重要或紧迫的进程。

采用剥夺调度方式，对提高系统吞吐率和响应效率都有明显的好处，但“剥夺”必须遵循一定的原则，主要有优先权、短进程优先、时间片原则等。

FCFS调度算法既可以用于作业调度，又可以用于进程调度。在作业调度中， 算法每次从后备队列中选择最先进入该队列的一个或几个作业，将它们调入内存，分配必要的资源，创建进程并放入就绪队列。

在进程调度中，FCFS调度算法每次从就绪队列中选择最先进入该队列的进程，将处理机分配给它，直到进程完成或因某种原因而阻塞才释放处理机。

FCFS调度算法属于不可剥夺算法。若一个长作业先到达系统，就会使后面许多短作业等待很长时间，因此它不能作为分时系统和实时系统的主要调度策略。但它常被结合在其它调度策略中使用，如在使用优先级作为调度策略的系统中，往往对多个具有相同优先级的进程按FCFS处理。

特点：

短作业优先调度算法是对短作业优先调度的算法。短作业优先算法从后备队列中选择一个或若干估计运行时间最短的进程，将它们调入内存执行；短进程优先算法从就绪队列中选择一个估计运行时间最短的进程，将处理机分配给它，直到完成或发生某事件而阻塞时，才释放处理机。

特点：

优先级调度算法又可称为优先权调度算法，既可以用于作业调度，又可以用于进程调度。该算法中的优先级用于描述作业的紧迫程度。在作业调度中，优先级调度算法每次从后备作业队列中选择优先级最高的一个或几个作业，将它们调入内存，分配必要的资源，创建进程并放入就绪队列。在进程调度中，优先级调度算法每次从就绪队列中选择优先级最高的进程，将处理机分配给它。

该算法按照更高优先级的进程是否抢占正在执行的进程可分为两种：

根据进程的优先级是否改变，可将进程的优先级分为以下两种：

一般来说，进程优先级的设置可以参照以下原则：

高响应比优先调度算法主要用于作业调度，是对FCFS调度算法和SJF调度算法的一种综合平衡，同时考虑了每个作业的等待事件和估计的运行时间。在每次进行作业调度时，先计算后备队列中每个作业的响应比，从中选出响应比最高的作业投入运行。

响应比的计算公式为： 响应比Rp = （等待时间 + 要求服务时间）/ 要求服务时间

特征：

时间片轮转调度算法主要用于分时系统。系统将所有就绪进程按到达时间的先后次序排成一个队列，进程调度程序总是选择就绪队列中的第一个进程执行，即先来先服务原则，但仅能运行一个时间片（如100ms）。在使用完一个时间片后，即使进程未完成其运行，它也必须释放处理机给下一个就绪的进程，而被剥夺处理机的进程返回就绪队列的末尾重新排队，等候再次运行。

时间片的大小对性能影响很大。若时间片足够大以至于所有进程都能在一个时间片内执行完毕，则该算法就退化为先来先服务调度算法；若时间片很小，则处理机将在进程间过于频繁地切换，使处理机的开销增大，而真正用于运行用户进程的时间将减少。

时间片的长短通常由以下因素确定：

多级反馈队列调度算法是时间片轮转调度算法和优先级调度算法的综合与发展。多级反馈队列调度算法可以兼顾多方面的系统目标，如为提高系统吞吐量和缩短平均周转时间而照顾短进程；为获得较好的I/O设备利用率和缩短响应时间而照顾I/O型进程；不必事先估计进程的执行时间。

该算法的实现思想如下：

优点：

死锁是指多个进程因竞争资源而造成的一种僵局（互相等待），若无外力作用，这些进程都将无法向前推进。

为使系统不发生死锁，必须破坏死锁的四个必要条件之一，或允许死锁产生，但当死锁发生时能检测出死锁，并有能力实现恢复。

设置某些限制条件，破坏产生死锁的四个必要条件中的一个或几个，以防止发生死锁。

在资源的动态分配过程中，用某种方法防止系统进入不安全状态，从而避免死锁。

无需采取任何限制性措施，允许进程在运行的过程中发生死锁，通过系统的检测机构及时地检测出死锁的发生，然后采取某种措施解除死锁。

死锁的预防和避免都属于事先预防策略，预防死锁的限制条件比较严格，实现起来较为简单，但往往导致系统的效率低，资源利用率低；避免死锁的限制条件比较宽松，资源分配后需要通过算法来判断是否进入不安全状态，实现起来比较复杂。

死锁的几种处理策略如下：

防止死锁的发生只需要破坏死锁产生的4个必要条件的其中之一即可。

特点：把只能互斥使用的资源改造成允许共享使用，则系统就不会进入死锁状态。如 *** 作系统使用SPOOLing技术把独占设备在逻辑上改造成共享设备。

缺点：并不是所有的资源都可以改造成可以共享使用的资源，并且为了系统安全，很多地方还必须保持这种互斥性。因此，很多时候都无法破坏这种互斥条件。

特点：

缺点：

特点：可采用静态分配方法，即进程运行之前一次申请完它所需要的全部资源，在它的资源尚未得到满足前，不把它投入运行。一旦投入运行，这些资源就一直归它所有，不再提出申请其他资源的请求。这种方法实现起来简单。

缺点：有些资源可能只需要使用很短的时间，因此如果进程的整个运行期间都一直保持着所有资源，就会造成严重的资源浪费，资源利用率极低。另外，该策略也有可能导致某些进程饥饿。

特点：采用顺序资源分配法，首先给系统中的资源编号，规定每个进程都必须按照编号递增的顺序请求资源，同类资源一次申请完。也就是说，只要进程提出申请分配资源Ri，则该进程在以后的资源申请中就只能申请编号大于Ri的资源（一个进程只有已占有我号的资源时，才有资格申请更大编号的资源）。按此规则，已持有更大编号资源的进程不可能逆向地申请我号的资源，从而就不会产生循环等待现象。

缺点：

所谓安全序列，就是指如果系统按照这种序列分配资源，则每个进程都能顺利完成。只要找出一个安全序列，系统就是安全状态。安全序列可能有多个。

如果分配了资源之后，系统找不到安全序列，则系统就进入了不安全状态。这就意味着之后可能所有进程都无法顺利执行下去。当然，如果有进程提前归还了一些资源，那系统也有可能提前回到安全状态。

如果系统处于安全状态，那么就一定不会发生死锁；如果系统进入不安全状态，就可能发生死锁（处于不安全状态未必就发生了死锁，但发生死锁时系统一定处于不安全状态）。因此可以在资源分配前预先判断这次分配是否会导致系统进入不安全状态，以此决定是否答应资源分配请求。

设Requesti是进程Pi的请求向量，Requesti[j] = K表示进程Pi需要j类资源K个。当Pi发出资源请求后，系统按照如下步骤进行检查：

安全性算法描述如下：

若系统在为进程分配资源时不采取任何措施，则应该提供死锁检测与解除的手段。

系统死锁可用资源分配图描述。如下图所示，圆圈代表一个进程，框代表一类资源，由于一种资源可能有多个，所以用框中的一个圆代表一类资源中的一个资源。从进程到资源的有向边称为请求边，表示该进程申请一个单位的该类资源；从资源到进程的边称为分配边，表示该类资源已经有一个资源分配给了该进程。

通过简化资源分配图可以检测系统状态S是否为死锁状态。简化方法如下：

分时。

计算机考试等级考试资料中，明确写道：为了支持多任务处理， *** 作系统的处理器调度程序使用分时技术把CPU分配给各个任务，使多个任务可以"同时"执行。

分时技术：把处理机的运行时间分为很短的时间片，按时间片轮流把处理机分给各联机作业使用。

---