处理机调度
调度的方式和层次
剥夺式：即就绪进程可以从运行进程手中抢占CPU。进程一直运行，直到结束、等待或被抢先。
非剥夺式：即就绪进程不可从运行进程手中抢占CPU。进程一直运行，直到结束或等待。
1、选择调度方式和调度算法的准则
面向用户的准则：周转时间短；响应时间快；等待时间短；截止时间的保证
面向系统的准则：系统吞吐量；处理机利用率好；各类资源的平衡利用
评价指标
2、调度的层次
高级调度（作业调度）：将外存上的作业调入内存，使之取得能分配到CPU并得以执行的资格。解决的问题（1）接纳多少个作业；（2）接纳哪些作业。
核心思想：选择尽可能多的作业进入内存，保证这些作业能够分配到运行所需的资源，尽力保证CPU和I/O设备的负载平衡，提高系统资源的利用率。
低级调度（进程调度）：根据进程调度算法选择就绪队列中的某个进程，并为其分配CPU。
低级调度的时机：进程终止时；进程阻塞时；被其他进程抢占；执行P操作时；执行V操作时。
中级调度：根据进程调度选择某个进程挂起，即将其调出到外存的交换区；或者，将挂起的进程唤醒，调回到内存中等待运行。
调度算法
1、先来先服务算法FCFS
算法描述：
按照作业提交或进程变为就绪状态的先后次序，分派CPU。
当前作业或进程占用CPU，直到执行完或阻塞，才出让CPU(非抢占方式)。
在作业或进程唤醒后(如I/O完成)，并不立即恢复执行，通常等到当前作业或进程让出CPU。是最简单的算法。
算法特点：
比较有利于长作业，而不利于短作业。这是因为若一个长作业先到达系统，就会使许多短作业等待很长的时间，从而引起许多短作业用户的不满。
有利于CPU繁忙的作业，而不利于I/O繁忙的作业。I/O繁忙的作业可以理解为短作业。
现代操作系统中，已很少用该算法作为主要调度策略，尤其是在分时系统和实时系统中。但它常被结合在其他调度策略中使用，即同等条件下按照FCFS调度。
2、短进程/作业优先算法SPF
算法描述：
短进程优先调度算法(Shortest Process First, SPF)，是指对短进程优先的算法。利用该算法，可以从就绪队列中选择一个估计运行时间最短的进程，并为之分配CPU，使其立即执行直到完成，或者在运行期间由于发生IO事件使该进程阻塞，并让出CPU，重新发生进程调度。
算法特点：
优点：比FCFS改善平均周转时间和平均带权周转时间，缩短作业的等待时间；假定所有任务同时到达，平均等待时间最短；提高系统吞吐量
缺点：对长作业非常不利，可能长时间得不到执行；长作业可能被饿死；未能依据作业的紧迫程度来划分执行的优先级；难以准确估计作业(进程)的执行时间，从而影响调度性能。
3、最高响应比优先算法HRN
算法描述：
最高响应比优先法(Highest Response_ratio Next，HRN)是对FCFS方式和SJF方式的一种综合平衡。
FCFS方式只考虑每个作业的等待时间而未考虑执行时间的长短，而SJF方式只考虑执行时间而未考虑等待时间的长短。
因此，这两种调度算法在某些极端情况下会带来某些不便。
HRN调度策略同时考虑每个作业的等待时间长短和估计需要的执行时间长短，从中选出响应比最高的作业投入执行。
其中T为该作业估计需要的执行时间，W为作业在后备状态队列中的等待时间。
每当要进行作业调度时，系统计算每个作业的响应比，选择其中R最大者投入执行。这样，即使是长作业，随着它等待时间的增加，W/T也就随着增加，也就有机会获得调度执行。
优点：同时到达任务，短者优先。等待时间相等时，服务时间越短，优先级越高，符合SJF思想；长作业随等待时间增加响应比增加。服务时间相等时，等待时间越长，优先级越高。对于长作业，只要其等待时间足够长，也能获得处理机。
缺点：吞吐量降低。这种算法是介于FCFS和SJF之间的一种折中算法。由于长作业也有机会投入运行，在同一时间内处理的作业数显然要少于SJF法，从而采用HRN方式时其吞吐量将小于采用SJF法时的吞吐量；系统开销增加。原因在于每次调度前要计算响应比。
4、最高优先数算法
算法描述：
在进程调度中，每次调度时，系统把处理机分配给就绪队列中优先数最高的进程。它又分为两种：非抢占式优先数算法和抢占式优先数算法。
在非抢占式优先数算法下，系统一旦把处理机分配给就绪队列中优先数最高的进程后，这个进程就会一直运行，直到完成或发生某事件使它放弃处理机，这时系统才能重新将处理机分配给就绪队列中的另一个优先数最高的进程。
在抢占式优先数算法下，系统先将处理机分配给就绪队列中优先数最高的进程让它运行，但在运行的过程中，如果出现另一个优先数比它高的进程，它就要立即停止，并将处理机分配给新的高优先数进程。
5、基于时间片的轮转调度算法
轮转(Round Robin，RR)调度算法是让每个进程在就绪队列中的等待时间与享受服务的时间成正比例。该算法适用于分时系统。
时间片长度的确定：
时间片过长，退化为FCFS算法，进程在一个时间片内都执行完，响应时间长。
时间片过短，用户的一次请求需要多个时间片才能处理完，上下文切换次数增加，响应时间长。
基本轮转：时间片(quantum,time slice)长度固定，不变；所有进程等速向前推进。
改进轮转：时间片长度不定，可变。
时间片长度为几十毫秒至几百毫秒(如50ms)。如果时间片过长则响应速度慢；反之，则系统开销(overhead)大。
对响应时间的要求：
T(响应时间)=N(进程数目)*q(时间片)
就绪进程的数目：数目越多，时间片越小
系统的处理能力：应当使用户输入通常在一个时间片内能处理完，否则使响应时间、平均周转时间和平均带权周转时间延长
算法描述：
1)将系统中所有的就绪进程按照FCFS原则，排成一个队列
2)每次调度时将CPU分派给队首进程，让其执行一个时间片。时间片的长度从几个ms到几百ms
3)在一个时间片结束时，发生时钟中断
4)调度程序据此暂停当前进程的执行，将其送到就绪队列的末尾，并通过上下文切换执行当前的队首进程
5)进程可以未使用完一个时间片，就出让CPU，如进程阻塞时
6、最短剩余时间优先算法
算法描述：
最短剩余时间优先(Shortest Remaining Time Next，SRTN)调度算法多用于剥夺式的调度中。
在进程调度中，每次调度时，系统把处理机分配给就绪队列中运行完所需时间最短的进程。
最短剩余时间优先算法也可用于不剥夺式调度方式中，此时退化为短作业优先算法。
7、多级反馈排队算法
算法描述：
1)设置多个就绪队列，分别赋予不同的优先级，如逐级降低，队列1的优先级最高。每个队列执行时间片的长度也不同，规定优先级越低则时间片越长，如逐级加倍
2)新进程进入内存后，先投入队列1的末尾，按FCFS算法调度；若按队列1一个时间片未能执行完，则降低投入到队列2的末尾，同样按FCFS算法调度；如此下去，降低到最后的队列，则按“时间片轮转”算法调度直到完成
3)仅当较高优先级的队列为空，才调度较低优先级的队列中的进程执行。如果进程执行时有新进程进入较高优先级的队列，则抢先执行新进程，并把被抢先的进程投入原队列的末尾
算法特点：
1）MFB算法为提高系统吞吐量和缩短平均周转时间而照顾短进程
2）MFB算法为获得较好的I/O设备利用率和缩短响应时间而照顾I/O型进程
3）不必估计进程的执行时间，动态调节。对于计算型进程，每次都执行完时间片，进入更低级队列，最终采用最大时间片来执行，减少调度次数
4）I/O次数不多，而主要是CPU处理的进程。在I/O完成后，放回优先I/O请求时离开的队列，以免每次都回到最高优先级队列后再逐次降低
优点：资源利用率高；响应速度快；系统开销小
实时调度
要实现实时调度，需要提供必要的信息，系统处理能力强，采用抢占式调度机制和具有快速切换机制
Linux操作系统中，实时调度时运行进程根据优先级放到对应的队列里面，对于相同的优先级的进程后面来的进程放到同一优先级队列的队尾
对于FIFO/RR调度，各自的进程需要设置相关的属性。进程运行时，要根据task中的这些属性判断和设置放弃CPU的时机(运行完或是时间片用完)
Linux内核中提供了两种实时调度策略：SCHED_FIFO和SCHED_RR，其中RR是带有时间片的FIFO。这两种调度算法实现的都是静态优先级。内核不为实时进程计算动态优先级。这能保证给定优先级别的实时进程总能抢占优先级比他低得进程
Linux的实时调度算法提供了一种软实时工作方式。实时优先级范围从0到MAX_RT_ PRIO减1
默认情况下，MAX_RT_PRIO为100，所以默认的实时优先级范围是从0到99。SCHED_NORMAL级进程的nice值共享了这个取值空间；它的取值范围是从MAX_RT_PRIO到MAX_RT_PRIO+40.也就是说，在默认情况下，nice值从-20到19直接对应的是从100到139的实时优先级范围