05.进程调度
1.调度：是指在一个队列中，按照某种方法（算法），选择一个合适的个体的过程；调度的关键是需要某种方法或算法，好的调度算法有利于选择到合适的个体，如何判断、设计一个好的调度算法呢？
2.调度目标：a.公平性，防止某些进程长期不能获得调度而饥饿；b.处理机利用率，尽量提高处理机的利用率；c.提高系统吞吐量；d.尽量减少进程的响应时间。
3.调度原则：a.满足用户的要求：响应时间、周转时间、截止时间；b.满足系统的需求：系统吞吐量、处理机利用率、各类资源的平衡使用、公平性及优先级。
4.面向用户的原则：
4_1.响应时间，是指从用户通过键盘提交一个请求开始，直到系统首次产生响应为止的时间；响应时间=输入的请求传送到处理机的时间+处理机对请求信息进行处理的时间+将响应结果发送到输出终端的时间。调度算法应考虑尽可能使绝大多数用户的请求能在响应时间内完成，响应时间常用于评价分时系统的性能。
4_2.周转时间，指从作业提交给系统开始，到作业完成为止的这段时间间隔；周转时间=作业在外存排队等待调度的时间+进程在就绪队列中等待调度的时间+进程被处理机执行的时间+等待I/O操作完成的时间；周转时间常用于评价批处理系统的性能。
4_3.影响周转时间的调度：a. 作业从外存调度到内存（作业调度）；b.进入内存还需在就绪队列中排队，等待进程调度；c.甚至可能会挂起进程，在外存等待被激活（中程调度）。
4_4.截止时间，指实时系统中，某任务必须开始执行的最迟时间，或必须完成的最迟时间，这常用于评价实时系统的性能。
5.面向系统的原则：
系统吞吐量，指单位时间内系统所完成的作业数，常用于评价批处理系统的性能。
5_1.处理机利用率：a.大、中型多用户系统，由于处理机价格昂贵，处理机利用率是衡量系统性能的一个重要指标；b.单用户微机或某些实时系统，则并非很重要。
5_2.各类资源的平衡使用：a.多道程序系统的目标之一就是为了提高系统资源的利用率，因此，调度算法有责任使系统中的各种资源都尽牌忙碌状态；b.该原则同时适用于长程调度和中程调度，因为它们可以决定哪些作业（进程）可以进入内存，可以考虑系统资源的均衡使用。
5_3.公平性:调度算法应该对所有进程公平，不偏袒任何进程。
5_4.优先权原则：优先权高的进程应优先调度；可以根据进程的优先权不同，组织不同的就绪队列，进程调度时首先选择高优先权队列中的进程，直到该队列为空，再调度较低优先权队列中的进程。
5_5.几乎所有操作系统的调度算法都可考虑优先权原则，当然仅考虑优先权，可能会出现饥饿，对低优先权的进程不公平；可以将进程排队的等待时间等因素纳入优先权的计算，随着进程等待时间的增长，其优先权也不断提高，进程会在不久的将来得到调度。
6.进程调度方式：
根据执行进程的处理机是由进程自己释放，还是被强行剥夺，可以将进程调度方式分为非剥夺方式和剥夺方式两种。
6_1.非剥夺方式：执行进程只有在执行完毕，或因申请I/O阻塞自己时，才中断其执行，释放处理机，调度新的进程执行；这种方式不利于“即时性”要求较高的分时和实时系统，主要用于批处理系统。
6_2.剥夺方式：操作系统可以在新进程到来时，或某个具有较高优先权的被阻塞进程插入到就绪队列时，或在基于时间片调度的系统中，时间片用完而中断当前进程的执行，调度新的进程执行；这种方式会产生较多的中断，主要用于实时性要求较高的实时系统及性能要求较高的批处理系统和分时系统。
7.调度的类型：批处理、分时、实时和多处理机调度；重点：长程调度、中程调度、短程调度、I/O调度。
8.长程调度（Long-term scheduling）：
又称为高级调度或作业调度，它为被调度作业或用户程序创建进程，分配必要的系统资源，并将新创建的进程插入到就绪队列，等待短程调度；某些采用交换技术的系统将新创建的进程插入到就绪/挂起队列，等待中程调度；在批处理系统中，作业进入系统后，先驻留在磁盘上，组织成批处理队列，称为后备队列，长程调度从该队列中选择一个或多个作业，为之创建进程。
8_1.长程调度要考虑的问题：选择多少个作业进入内存，为之创建进程——这取决于多道程序的度，即允许同时在内存中运行的进程数；选择哪些作业——这取决于长程调度算法。
9.短程调度（Short-term scheduling）：也称为进程调度，或低级调度，决定就绪队列中的哪个进程获得处理机，短程调度运行频率最高，现代操作系统几乎都具有短程调度的功能。
10. 中程调度（Medium-term scheduling）：又称为中级调度，它是对换功能的一部分，当内存空间非常紧张时，或处理机找不到一个可执行的就绪进程时，需要选择一个进程（阻塞或就绪状态）换出到外存，释放出内存空间给别的进程使用；当内存空间充裕时，从外存选择一个挂起状态的进程调度到内存（换入）。中程调度的目的：提高内存的利用率和系统的吞吐量；只有支持进程挂起的操作系统才具有中程调度功能。
06.进程调度算法
1.先来先服务（FCFS）算法：
该方法按照进程到达的先后顺序排队，每次调度队首的进程；FCFS算法以属于非剥夺调度方式，实现简单，看似公平，但是对于那些后进入队列而运行时间较短的进程，或I/O型的进程而言，可能需要长时间等待。
1_1.FCFS的优劣：a.对短进程不公平，由于长进程可能排在队列前面，必将增加队列后部进程的等待时间，从而将增加平均周转时间；b.不得利于I/O型进程，未有效利用系统资源；c.一般的，FCFS与其它调度算法混合使用，如：系统可以按照不同的优先级维护多个就绪队列，每个队列内部按照FCFS算法调度；d.FCFS算法同时适合于长程、中程和短程调度三种调度类型。
2.短进程优先算法：
当需要调度进程（或作业）时，通过计算判断就绪进程队列中哪一个进程的预期执行时间最短，或后备作业执行时间最短，就调度谁。该算法属于非剥夺调度算法，当某进程获得处理机，直到其执行完成，或需要等待某事件而阻塞时，才自动释放处理机，系统又调度新的进程（或作业）。
2_1.与FCFS算法比较，短进程优先调度算清改善了系统的性能，降低了系统的平均等待时间，提高了系统的吞吐量，但是该算法出存在一些问题：很难准确预测进程的执行时间；可能导致长进程饥饿，这对长进程不公平；采用非剥夺调度方式，未考虑进程的紧迫程度，不适合于分时系统和事务处理系统。
3.时间片轮转调度法：
在一个分时联机系统中，同时有n个人通过各自的终端共享一台主机（服务器），终端完成输入/输出操作，主机负责处理从终端发来的请求，为之建立进程、协调各进程的运行、调度各个进程等，并尽量满足每个终端用户对响应时间的要求。
3_1.在分时联机系统中，n个进程循环地获得时间片而执行，从系统中来看它们是交替执行的，但就每个终端用户而言，都感觉到自己独占了一台主机，不受其他用户的影响，这是通过进程并发执行实现的；如果用户数太多，主机处理的进程将会急剧增加，进程排队等待的时间也会很长，进程的响应时间也可能增长；此外，时间片的大小也会影响进程的响应时间。
3_2.时间片的设置：a.进程切换将会增加系统的额外开销；b.时间片设定得太短，进程切换会非常频繁，从而降低处理机的效率；时间片设得太长，将无法满足交互式用户对响应时间的要求；c.因此，时间片大小的确定应综合考虑系统的最大用户数、响应时间、系统效率等多种因素。
3_3. 时间片轮转调度法常用于分时系统及事务处理系统，合理的时间片大小将带来满意的响应时间；通常，合理的时间片指，能让80%左右的进程在一个时间片内完成；对于短的、计算型的进程较有利；不适合于批处理系统的进程调度，也不利于I/O型的进程；改进的方法之一，可以将I/O阻塞事件完成的进程单独组织一个就绪队列，该队列进程的时间片可以设置小一点，且优先调度。
4.基于优先级的调度算法：基于时间片轮转调度法循环式地为每个被调度的进程分配一个时间片，对每个进程都是公平的；然而，实际应用中，进程的性质可能是不同的（如一个用户进行交互的前台进程急迫地需要对用户的输入作出响应，而一个后台打印进程的迫切性也许就不那么重要）；因此，可以为每个进程定义一个优先级，优先级越高的进程将优先获得处理机的调度。
5.如何设定进程的优先级：进程完成功能的重要性；进程完成功能的急迫性；为均衡系统资源的使用，指定进程（作业）优先级；进程对资源的占用程度，例如：可以为短进程（或作业）赋予较高的优先级。
6.静态与动态优先级：a.静态优先级：一旦确定，则进程运行期间优先级一直不改变；b.动态优先级：系统首先赋予进程一个初始优先级，该优先级将随着进程的运行而改变。
7.动态优先级：
a.典型的动态优先级变化方式为：优先级随着进程运行的剩余时间的减少而上长升，使使将要执行结束的进程尽快完成，或随着进程排队等待时间的增长而上升，使等待时间越长的进程优先得到调度，不至于长时间饥饿；b.具体实现方法：可以在每个时钟中断时，或需要进程切换时，重新计算就绪队列中各进程的优先级，并优先调度高优先级的进程；c.采用动态优先级的两种调度算法：剩余时间最短者优先和响应比高者优先。
7_1.剩余时间最短者优先：为了使将要结束的进程尽早结束，释放系统资源，让别的进程执行，可以在每个时钟中断时，根据就绪队列中各进程的剩余执行时间动态调整其优先级，剩余时间最短的进程优先级最高；显然，该算法是剥夺型的短进程的短进程优先调度算法，调度程序总是选择剩余执行时间最短的进程调度执行。
7_2..剩余时间最短者优先：与短进程优先调度算法一样，该调度算法很难准确估计进程的剩余执行时间；由于长进程在未执行时，或刚开始执行的一段时间内，其剩余执行时间都不会最短，所以该算法对长进程不公平；
7_2继：但是，它不象FCFS算法偏袒长进程，也不象轮转调度算法会产生很多中断而增加系统负担；由于短进程提前完成，故采用剩余时间最短者优先的调度算法获得的平均周转时间比采用短进程优先算法短。
7_3.响应比高者优先：将进程的等待时间和进程的预期执行时间纳入优先级的计算，进程（预期执行时间）越长优先级越低，而随着进程的等待时间增长优先级上升，即进程的优先级与等待时间正比，与进程执行时间成反比，令W表示等待时间，S表示预期执行时间，则响应比为：R=（W+S）/S=w/s+1。
7_3-1.调度方法：若当前执行进程执行完毕，或需要阻塞等待某事件而释放处理机，调度程序选择就绪队列中响应比最大的进程执行；若等待时间相同，短进程因为S较小，R较大而优先调度；若进程的预期执行时间相同，则等待时间长的进程优先调度，相当于FCFS；随着等待时间的增加，长进程的响应比不断增大，在某个时刻，也必然被调度。和短进程优先和剩余时间最短者优先调度算法一样，很难准确估计进程的预期执行时间；每次调度之前都需要计算响应比，增加了系统开销。
8. 反馈调度法：
前面介绍的几种调度算法都存在各自不同的问题，尤其是短进程优先、剩余时间最短者优先以及响应比高者优先调度算法都需要估计进程的预期执行时间，如果估计不准确，将影响调度结果和系统性能；如果根据进程执行历史，而非未来，进行调度，将解决这个问题；反馈调度法就是一种根据进程执行历史调整调度方式的调度方法，它结合了优先级和时间片轮转调度思想。
8_1.该方法有利于交互型短进程或短批处理作业，因为它们一般只需要一个或很少的几个时间片就可以完成，但可能使长进程的周转时间急剧增加；如果不断地有新进程到来，还可能出现长进程长期饥饿现象；为此，可以为各队列设置不同的时间片，优先级愈低时间片愈长。
9.进程调度算法小结：
如何选择进程调度算法与系统设计的目标有关；交互式多任务系统，主要考虑联机用户对响应时间的要求，一般采用基于时间片轮转调度算法，同时，根据进程的性质设置不同的优先级；批处理系统往往以作业的平均周转时间来衡量调度性能，常选用基于优先级的短进程（或作业）优先调度算法。
10.实时系统（Real-Time System）：
指能及时响应外部事件的请求，在规定的时间内完成对该事件的处理，并控制所有实时任务协调一致地运行的计算机系统；分为实时控制系统和实时信息处理系统。
10_1.实时控制系统：指要求进行实时控制的系统，主要用于生产过程的控制，实时采集现场数据，并对所采集的数据进行及时处理，进而自动地控制相应的执行机构，使某些（个）参数（如温度、压力、方位等）能按预定的规律变化，以保证产品的质量和提高产量，也可以用于武器的控制等。
10_2.实时信息处理系统：指能对信息进行实时处理的系统；该系统由一台或多台主机通过通信线路连接成百上千远程终端，计算机接收从远程终端发来的服务请求，根据用户提出的问题，对信息进行检索和处理，并在很短的时间内为用户做出正确的回答；典型的实时信息处理系统有：飞机订票系统、情报检索系统等。
11.实时任务（real-time task）：
指具有及时性要求的、常常被重复执行的特定进程，在实时系统中习惯称为任务；按任务执行时是否呈现周期性来分类：a.周期性实时任务，要求按指定的周期循环执行，以便周期性地控制某个外部事件；b.非周期性实时任务，任务的执行无明显的周期性，但都必须联系着一个截止时间（deadline）。
11_1.截止时间包括：开始截止时间（任务在某时间以前，必须开始执行）和完成截止时间（任务在某时间以前必须完成）；
11_2.根据对截止时间的要求将实时任务划分为：（1）硬实时任务，系统必须满足任务对截止时间的要求，否则可能出现难以预测的结果（影响较大）；（2）软实时任务，它也联系着一个截止时间，但并不严格，若错过了任务的截止时间，对系统产生的影响不会很大。
12.实时调度的目标：
主要考虑如何使硬实时任务在其规定的截止时间内完成，同时尽可能使软实时任务也能在规定的截止时间内完成；而公平性和最短平均响应时间等要求已不再重要；但是大多数现代实时操作系统无法直接处理任务的截止时间，它们只能尽量提高响应速度，以尽快地调度任务。
12_1.实时性要求不太高的实时系统可用的调度算法：基于时间片轮转调度算法；基于优先级的调度算法；最早截止时间优先调度算法，即优先调度截止时间最近的实时任务。
13.速度单调调度算法（Rate Monotonic Scheduling，RMS）：
根据任务的周期大小赋予优先级，最短周期的任务具有最高优先级；其中，任务周期（period）是指一个任务到达至下一任务到达之间的时间范围；任务速度（rate），是指周期（以秒计）的倒数，以赫兹为单位；任务周期的结束，表示任务的硬截止时间，任务的执行时间不应超过任务周期。