1. 第三章 进程调度的几种方式
进程调度概念：操作系统必须为多个，吗进程可能有竞争的请求分配计算机资源。对处理器而言，可分配的资源是在处理器上的执行时间，分配途径是调度。调度功能必须设计成可以满足多个目标，包括公平、任何进程都不会饿死、有效地使用处理器时间和低开销。此外，调度功能可能需要为某些进程的启动或结束考虑不同的优先级和实时最后期限。
这些年以来，调度已经成为深入研究的焦点，并且已经实现了许多不同的算法。如今，调度研究的重点是开发多处理系统，特别是用于多线程的。
下面简介几种调度算法。
一、先来先服务和短作业(进程)优先调度算法
1．先来先服务调度算法
先来先服务(FCFS)调度算法是一种最简单的调度算法，该算法既可用于作业调度，也可用于进程调度。当在作业调度中采用该算法时，每次调度都是从后备作业队列中选择一个或多个最先进入该队列的作业，将它们调入内存，为它们分配资源、创建进程，然后放入就绪队列。在进程调度中采用FCFS算法时，则每次调度是从就绪队列中选择一个最先进入该队列的进程，为之分配处理机，使之投入运行。该进程一直运行到完成或发生某事件而阻塞后才放弃处理机。
2．短作业(进程)优先调度算法
短作业(进程)优先调度算法SJ(P)F，是指对短作业或短进程优先调度的算法。它们可以分别用于作业调度和进程调度。短作业优先(SJF)的调度算法是从后备队列中选择一个或若干个估计运行时间最短的作业，将它们调入内存运行。而短进程优先(SPF)调度算法则是从就绪队列中选出一个估计运行时间最短的进程，将处理机分配给它，使它立即执行并一直执行到完成，或发生某事件而被阻塞放弃处理机时再重新调度。
二、高优先权优先调度算法
1．优先权调度算法的类型
为了照顾紧迫型作业，使之在进入系统后便获得优先处理，引入了最高优先权优先(FPF)调度算法。此算法常被用于批处理系统中，作为作业调度算法，也作为多种操作系统中的进程调度算法，还可用于实时系统中。当把该算法用于作业调度时，系统将从后备队列中选择若干个优先权最高的作业装入内存。当用于进程调度时，该算法是把处理机分配给就绪队列中优先权最高的进程，这时，又可进一步把该算法分成如下两种。
1) 非抢占式优先权算法
在这种方式下，系统一旦把处理机分配给就绪队列中优先权最高的进程后，该进程便一直执行下去，直至完成；或因发生某事件使该进程放弃处理机时，系统方可再将处理机重新分配给另一优先权最高的进程。这种调度算法主要用于批处理系统中；也可用于某些对实时性要求不严的实时系统中。
2) 抢占式优先权调度算法
在这种方式下，系统同样是把处理机分配给优先权最高的进程，使之执行。但在其执行期间，只要又出现了另一个其优先权更高的进程，进程调度程序就立即停止当前进程(原优先权最高的进程)的执行，重新将处理机分配给新到的优先权最高的进程。因此，在采用这种调度算法时，是每当系统中出现一个新的就绪进程i 时，就将其优先权Pi与正在执行的进程j 的优先权Pj进行比较。如果Pi≤Pj，原进程Pj便继续执行；但如果是Pi>Pj，则立即停止Pj的执行，做进程切换，使i 进程投入执行。显然，这种抢占式的优先权调度算法能更好地满足紧迫作业的要求，故而常用于要求比较严格的实时系统中，以及对性能要求较高的批处理和分时系统中。
2．高响应比优先调度算法
在批处理系统中，短作业优先算法是一种比较好的算法，其主要的不足之处是长作业的运行得不到保证。如果我们能为每个作业引入前面所述的动态优先权，并使作业的优先级随着等待时间的增加而以速率a 提高，则长作业在等待一定的时间后，必然有机会分配到处理机。该优先权的变化规律可描述为：
由于等待时间与服务时间之和就是系统对该作业的响应时间，故该优先权又相当于响应比RP。据此，又可表示为：
由上式可以看出：
(1) 如果作业的等待时间相同，则要求服务的时间愈短，其优先权愈高，因而该算法有利于短作业。
(2) 当要求服务的时间相同时，作业的优先权决定于其等待时间，等待时间愈长，其优先权愈高，因而它实现的是先来先服务。
(3) 对于长作业，作业的优先级可以随等待时间的增加而提高，当其等待时间足够长时，其优先级便可升到很高，从而也可获得处理机。简言之，该算法既照顾了短作业，又考虑了作业到达的先后次序，不会使长作业长期得不到服务。因此，该算法实现了一种较好的折衷。当然，在利用该算法时，每要进行调度之前，都须先做响应比的计算，这会增加系统开销。
三、基于时间片的轮转调度算法
1．时间片轮转法
1) 基本原理
在早期的时间片轮转法中，系统将所有的就绪进程按先来先服务的原则排成一个队列，每次调度时，把CPU 分配给队首进程，并令其执行一个时间片。时间片的大小从几ms 到几百ms。当执行的时间片用完时，由一个计时器发出时钟中断请求，调度程序便据此信号来停止该进程的执行，并将它送往就绪队列的末尾；然后，再把处理机分配给就绪队列中新的队首进程，同时也让它执行一个时间片。这样就可以保证就绪队列中的所有进程在一给定的时间内均能获得一时间片的处理机执行时间。换言之，系统能在给定的时间内响应所有用户的请求。
2．多级反馈队列调度算法
前面介绍的各种用作进程调度的算法都有一定的局限性。如短进程优先的调度算法，仅照顾了短进程而忽略了长进程，而且如果并未指明进程的长度，则短进程优先和基于进程长度的抢占式调度算法都将无法使用。而多级反馈队列调度算法则不必事先知道各种进程所需的执行时间，而且还可以满足各种类型进程的需要，因而它是目前被公认的一种较好的进程调度算法。在采用多级反馈队列调度算法的系统中，调度算法的实施过程如下所述。
(1) 应设置多个就绪队列，并为各个队列赋予不同的优先级。第一个队列的优先级最高，第二个队列次之，其余各队列的优先权逐个降低。该算法赋予各个队列中进程执行时间片的大小也各不相同，在优先权愈高的队列中，为每个进程所规定的执行时间片就愈小。例如，第二个队列的时间片要比第一个队列的时间片长一倍，……，第i+1个队列的时间片要比第i个队列的时间片长一倍。
(2) 当一个新进程进入内存后，首先将它放入第一队列的末尾，按FCFS原则排队等待调度。当轮到该进程执行时，如它能在该时间片内完成，便可准备撤离系统；如果它在一个时间片结束时尚未完成，调度程序便将该进程转入第二队列的末尾，再同样地按FCFS原则等待调度执行；如果它在第二队列中运行一个时间片后仍未完成，再依次将它放入第三队列，……，如此下去，当一个长作业(进程)从第一队列依次降到第n队列后，在第n 队列便采取按时间片轮转的方式运行。
(3) 仅当第一队列空闲时，调度程序才调度第二队列中的进程运行；仅当第1～(i-1)队列均空时，才会调度第i队列中的进程运行。如果处理机正在第i队列中为某进程服务时，又有新进程进入优先权较高的队列(第1～(i-1)中的任何一个队列)，则此时新进程将抢占正在运行进程的处理机，即由调度程序把正在运行的进程放回到第i队列的末尾，把处理机分配给新到的高优先权进程。
2. 进程调度方案设计 实现一个基本动态优先级的调度算法
前两天做操作系统作业的时候学习了一下几种进程调度算法，在思考和讨论后，有了一些自己的想法，现在就写出来，跟大家讨论下。，或者说只有有限的CPU资源，当系统中有多个进程处于就绪状态，要竞争CPU资源时，操作系统就要负责完成如何分配资源的任务。在操作系统中，由调度程序来完成这一选择分配的工作，调度程序所使用的算法即是调度算法。调度算法需要考虑的指标主要有尽量保证CPU资源分配的公平性；按照一定策略强制执行算法调度；平衡整个计算机系统，尽量保持各个部分都处于忙碌状态。而根据系统各自不同的特点和要求，调度算法又有一些侧重点和目标不同，因此，算法按照系统差异主要分为三大类：批处理系统中的调度算法，代表调度算法有：先来先服务、最短作业优先、最短剩余时间优先。交互式系统中的调度算法，代表调度算法有：轮转调度、优先级调度、多级队列、最短进程优先、保证调度、彩票调度、公平分享调度。实时系统中的调度算法，代表调度算法有：速率单调调度、最早最终时限优先调度。下面就上述提到的调度算法中挑出几个进行重点分析：保证调度保证调度是指利用算法向用户做出明确的性能保证，然后尽力按照此保证实现CPU的资源分配。利用这种算法，就是定一个进程占用CPU的时间的标准，然后按照这个标准去比较实际占用CPU的时间，调度进程每次使离此标准最远的进程得到资源，不断满足离所保证的标准最远的进程，从而平衡资源分配满足这个标准的要求。保证调度算法的优点是：能很好的保证进程公平的CPU份额，当系统的特点是：进程的优先级没有太大悬殊，所制定的保证标准差异不大，各个进程对CPU的要求较为接近时，比如说系统要求n个进程中的每个进程都只占用1/n的CPU资源，利用保证调度可以很容易的实现稳定的CPU分配要求。但缺点是，这种情况太过理想，当系统的各个进程对CPU要求的紧急程度不同，所制定的保证较为复杂的时候，这个算法实现起来比较困难。彩票调度彩票调度这种算法的大意是指向进程提供各种系统资源如CPU资源的彩票，当系统需要做出调度决策时，随机抽出一张彩票，由此彩票的拥有者获得资源。在彩票调度系统中，如果有一个新的进程出现并得到一些彩票，那么在下一次的抽奖中，该进程会有同它持有彩票数量成正比例的机会赢得奖励。进程持有的彩票数量越多，则被抽中的可能性就越大。调度程序可以通过控制进程的彩票持有数量来进行调度。彩票调度有很多优点：首先，它很灵活，系统增加分给某个进程的彩票数量，就会大大增加它占用资源的可能性，可以说，彩票调度的反应是迅速的，而快速响应需求正是交互式系统的一个重要要求。其次，彩票调度算法中，进程可以交换彩票，这个特点可以更好的保证系统的平衡性，使其各个部分都尽可能的处于忙碌状态。而且利用彩票调度还可以解决许多别的算法很难解决的问题，例如可以根据特定的需要大致成比例的划分CPU的使用。速率单调调度速率单调调度算法是一种可适用于可抢占的周期性进程的经典静态实时调度算法。当实时系统中的进程满足：每个周期性进程必须在其周期内完成，且进程之间没有相互依赖的关系，每个进程在一次突发中需要相同的CPU时间量，非周期的进程都没有最终时限四个条件时，并且为了建模方便，我们假设进程抢占即刻发生没有系统开销，可以考虑利用速率单调算法。速率单调调度算法是将进程的速率（按照进程周期所算出的每秒响应的次数）赋为优先级，则保证了优先级与进程速率成线性关系，这即是我们所说的速率单调。调度程序每次运行优先级最高的，只要优先级较高的程序需要运行，则立即抢占优先级低的进程，而优先级较低的进程必须等所有优先级高于它的进程结束后才能运行。速率单调调度算法可以保证系统中最关键的任务总是得到调度，但是缺点是其作为一种静态算法，灵活性不够好，当进程数变多，系统调度变得复杂时，可能不能较好的保证进程在周期内运行。最早最终时限优先调度最早最终时限优先调度算法是一个动态算法，不要求进程是周期性的，只要一个进程需要CPU时间，它就宣布它的到来时间和最终时限。调度程序维持一个可运行的进程列表，按最终时限排序，每次调度一个最终时限最早的进程得到CPU 。当新进程就绪时，系统检查其最终时限是否在当前运行的进程结束之前，如果是，则抢占当前进程。由于是动态算法，最早最终优先调度的优点就是灵活，当进程数不超过负载时，资源分配更优，但也同样由于它的动态属性，进程的优先级都是在不断变化中的，所以也没有哪个进程是一定可以保证满足调度的，当进程数超过负载时，资源分配合理度会急速下降，所以不太稳定。
3. 挑战408——操作系统（8）——典型的调度算法
调度算法是操作系统中用于合理分配处理机资源的关键技术。在面对如何提高CPU利用率的问题时，不同的系统依据其设计目标选择不同的调度方式。常见的调度算法包括先来先服务（FCFS）、短作业优先（SJF或SPF）、高响应比优先（HRRN）、优先级调度（Priority）、时间片轮转（RR）以及多级反馈队列（MFQ）。
先来先服务（FCFS）
FCFS算法简单明了，其核心思想是按照程序到达的先后顺序进行调度，类似于队列的先进先出原则。它适合作业调度与进程调度，每次从就绪队列中选择最先进入队列的进程分配处理机。该算法虽然表面上看起来公平，但长作业的突然到来会导致短作业长期等待，不利于I/O繁忙作业的处理，常作为其他调度策略的辅助手段。
短作业优先（SJF或SPF）
SJF算法通过选择预计运行时间最短的进程进行调度，以减少作业或进程的平均周转时间。同样适用于作业调度和进程调度。然而，这种方法可能不利于长作业，容易导致饥饿现象，并未考虑作业的紧迫程度。
高响应比优先（HRRN）
HRRN算法综合了FCFS和SJF的特性，考虑每个作业的等待时间和估计运行时间。通过响应比（周转时间/运行时间）来衡量作业的优先级，实现对作业调度的动态平衡。
优先级调度（Priority）
优先级调度算法旨在满足紧急进程的及时处理，支持作业调度和进程调度。静态优先级在进程创建时确定，保持不变；动态优先级随进程执行情况动态调整，以优化系统性能。
时间片轮转（RR）
RR算法主要用于进程调度，常用于分时系统。通过将就绪进程按FCFS原则排序，每次分配固定时间片的处理机资源。时间片过长导致退化为FCFS，过短则增加用户响应时间，特别不利于I/O频繁的进程。
多级反馈队列（MFQ）
MFQ算法设置多个优先级不同的就绪队列，优先级越高，时间片越短。进程按FCFS原则加入最高优先级队列，若未完成，则依次移至较低优先级队列。此算法结合了前几种算法的优点，但需注意避免前队列长期阻塞导致后续队列饥饿。
调度算法比较
通过综合对比各类调度算法，可以清晰地看到它们在公平性、响应时间、资源利用率等方面的差异。选择合适的调度算法取决于系统的目标、资源状况和应用需求。
4. 进程调度
当计算机中有多个process处于ready状态，将CPU分配给哪个进程呢？操作系统中做出这个决策的组件就是调度器，决策的算法叫调度算法，决策过程就是进程调度的过程。
进程调度一般发生在一下几种情况下：
在非抢占式调度中，进程开始执行以后，除非它主动放弃CPU或被block, 否则就能一直执行。
抢占式调度中，如果在进程执行过程中来了一个优先级更高的进程，CPU使用权就会被抢走，尤其在时间片调度中即使时间片没用完也可以被抢占。但抢占也不是随时可以发生的，如果设计不好可能会发生优先级逆转或者死锁问题。
在不同的场景下，为了实现不同的目标，评价调度算法的标准不尽相同。这里我们介绍一些常用的标准：
Fairness : 给每个进程公平的CPU使用机会
Balance : 让系统的各个组件都能得到最大程度的利用率
Throughput 吞吐量 ：单位时间内完成的任务数量
Turnaround Time ：一般在批处理系统中，一个批任务从提交到结束的间隔时间
CPU Utilization ：CPU的利用率
Waiting Time ：进程在ready队列里等待的时间
Response Time ：一般在交互式系统中，从用户提交任务到第一次得到响应（任务不一定完成）的间隔时间
Meeting Deadline ：一般在实时系统中及时处理数据，避免丢失或失效
接下来我们看看在三种不同类型系统中常用的调度算法。
1. FCFS : First Come, First Served
这是一种非抢占式的先来先服务算法。ready process队列只有一个。如果进程执行中被block，进入block队列，ready之后作为新的进程排到ready队列的尾部。
优点：容易理解，容易实现
缺点：平均等待时间往往很长，不好平衡CPU密集和IO密集型进程
2. SJF: Shortest Job First
SJF也是非抢占式调度，每次都选择最短的任务来执行。
3. Shortest Remaining Time Next
是SJF的抢占式版本，只要有新任务到达就重新调度选择剩余时间最短的任务执行。
SJF和Shortest Remaining Time Next的问题在于一般情况下很难判断进程的剩余执行时间是多少。除非这是经常要执行的task，根据对历史的统计分析能确定一个执行时间的大致范围。
1. Round-Robin Scheling
轮询调度。 给每个进程相同的时间片，轮流执行。一般时间片选择在20-50msec比较合适，太短会导致进程切换浪费时间，太长会导致响应时间延长。
优点：比SJF响应快
缺点：turnaround时间长
2. Priority Scheling
优先级调度为每个进程分配优先级，高优先级先执行，这也是时间片调度算法。优先级可以静态分配也可以动态分配，为了避免高优先级的进程一直占用CPU不放，可以在依次执行结束后降低其优先级。相同优先级的进程之间可以使用其他的调度算法如round-robin，不同队列可以使用不同的调度算法。
优点：引入了优先级
3. Multiple Queues
为了避免执行时间长的进程频繁进程切换，可以在不同的优先级队列之间分配不等长度的时间片。进程执行一次之后被分配其他拥有更长执行时间的优先级。比如一个进程需要100个quanta, 第一次执行时分配1个，下一次执行分配2个，再下次分配4，8，16，32，64. 比每次都只分配1的纯轮询算法减少了进程调度的次数。
4. Guaranteed Scheling
前面提到的算法都不保证进程能够得到的CPU时间，但有些情况下我们需要确保进程使用CPU的机会和时间，比如n个用户同时登录，一般要保证每个用户都能获得1/n的CPU，或者我们购买VPN服务，根据不同的用户级别需要获得一定的带宽保证。这种算法就叫Guaranteed 调度。在实现中，需要追踪给每个进程分配的CPU，与承诺分配量比较，比值最小的进程会获得下一次使用权。
5. Lottery Scheling
彩票调度算法引入了随机性，为每个进程发一张彩票，调度时就像开奖，谁中奖谁获得资源。优先级更高的进程可以获得多张彩票以提高中奖机会。
彩票调度有趣的地方在于进程之间可以互赠彩票，比如process 1 pending在process 2上，它可以把自己的彩票都给process2提高它被调度的机会。process2结束以后再把彩票还给process1.
6. Fair-Share Scheling
下面考虑一种情况，所有进程并不属于一个用户，这在Linux 系统中非常常见。如果user1有99个process，user2只有1个process，按照前面的算法可能user1能得到99%的CPU，而user2只有1%。为了实现用户层面的公平性，调度时需要考虑进程属于哪个user.
实时系统分两种：
实时系统中，一般任务时间都比较短，调度器需要使所有进程都在deadline前完成。对于周期性发生的事件，如果事件发生的周期为 , 事件处理时间(需要占用CPU的时间)为 , 只有 时，才是可调度的。
调度算法只能由操作系统实现吗，关于使用哪种调度算法进程是否有话语权呢？答案是可以的。将机制与策略分离，由操作系统提供多种实现机制，并提供system call由process传参数给OS指定具体使用哪一种调度策略。
如果线程是在用户态实现的，那么需要两级调度，OS负责调度process，process负责调度thread。如果线程是在内核态实现的，OS直接调度thread，而不关心它属于哪个process。