OS调度思想

一、进程(作业)调度算法1.先来先服务调度算法（FCFS）:每次调度是从就绪队列中，选择一个最先进入就绪队列的进程，把处理器分配给该进程，使之得到执行。该进程一旦占有了处理器，它就一直运行下去，直到该进程完成或因发生事件而阻塞，才退出处理器。特点：利于长进程，而不利于短进程。2.短进程（作业）优先调度算法(SPF):它是从就绪队列中选择一个估计运行时间最短的进程，将处理器分配给该进程，使之占有处理器并执行，直到该进程完成或因发生事件而阻塞，然后退出处理器，再重新调度。3.时间片轮转调度算法:系统将所有的就绪进程按进入就绪队列的先后次序排列。每次调度时把CPU分配给队首进程，让其执行一个时间片，当时间片用完，由计时器发出时钟中断，调度程序则暂停该进程的执行，使其退出处理器，并将它送到就绪队列的末尾，等待下一轮调度执行。4.优先数调度算法:它是从就绪队列中选择一个优先权最高的进程，让其获得处理器并执行。5.响应比高者优先调度算法：它是从就绪队列中选择一个响应比最高的进程，让其获得处理器执行，直到该进程完成或因等待事件而退出处理器为止。特点：既照顾了短进程，又考虑了进程到达的先后次序，也不会使长进程长期得不到服务，因此是一个比较全面考虑的算法，但每次进行调度时，都需要对各个进程计算响应比。所以系统开销很大，比较复杂。6.多级队列调度算法基本概念：作业周转时间（Ti）＝完成时间(Tei)－提交时间(Tsi)作业平均周转时间(T)＝周转时间/作业个数作业带权周转时间（Wi）＝周转时间/运行时间响应比＝（等待时间＋运行时间）/运行时间二、存储器连续分配方式中分区分配算法1.首次适应分配算法（FF）：对空闲分区表记录的要求是按地址递增的顺序排列的，每次分配时，总是从第1条记录开始顺序查找空闲分区表，找到第一个能满足作业长度要求的空闲区，分割这个空闲区，一部分分配给作业，另一部分仍为空闲区。2.循环首次适应算法：每次分配均从上次分配的位置之后开始查找。3.最佳适应分配算法(BF)：是按作业要求从所有的空闲分区中挑选一个能满足作业要求的最小空闲区，这样可保证不去分割一个更大的区域，使装入大作业时比较容易得到满足。为实现这种算法，把空闲区按长度递增次序登记在空闲区表中，分配时，顺序查找。4.最坏适应算法(worstfitalgorithm)：要求空闲区按其大小递减的顺序组成空闲区可用表或自由链。当用户作业或进程申请一个空闲区时，先检查空闲区可用表或自由链的第一个空闲可用区的大小是否大于或等于所要求的内存长度，若可用表或自由链的第一个项所示空闲区长度小于所要求的，则分配失败，否则从空闲区可用表或自由链中分配相应的存储空间给用户，然后修改和调整空闲区可用表或自由链。三、页面置换算法1.最佳置换算法（OPT)：选择以后永不使用或在最长时间内不再被访问的内存页面予以淘汰。2.先进先出置换算法（FIFO）：选择最先进入内存的页面予以淘汰。3.最近最久未使用算法（LRU）：选择在最近一段时间内最久没有使用过的页，把它淘汰。4.最少使用算法（LFU）：选择到当前时间为止被访问次数最少的页转换。四、磁盘调度1.先来先服务（FCFS）：是按请求访问者的先后次序启动磁盘驱动器，而不考虑它们要访问的物理位置2.最短寻道时间优先（SSTF）：让离当前磁道最近的请求访问者启动磁盘驱动器，即是让查找时间最短的那个作业先执行，而不考虑请求访问者到来的先后次序，这样就克服了先来先服务调度算法中磁臂移动过大的问题3.扫描算法（SCAN）或电梯调度算法：总是从磁臂当前位置开始，沿磁臂的移动方向去选择离当前磁臂最近的那个柱面的访问者。如果沿磁臂的方向无请求访问时，就改变磁臂的移动方向。在这种调度方法下磁臂的移动类似于电梯的调度，所以它也称为电梯调度算法。4.循环扫描算法（CSCAN）：循环扫描调度算法是在扫描算法的基础上改进的。磁臂改为单项移动，由外向里。当前位置开始沿磁臂的移动方向去选择离当前磁臂最近的哪个柱面的访问者。如果沿磁臂的方向无请求访问时，再回到最外，访问柱面号最小的作业请求。在多进程、多线程并发的环境里，从概念上看，有多个进程或者多个线程在同时执行，具体到单个CPU级别，实际上任何时刻只能有一个进程或者线程处于执行状态；因此OS需要决定哪个进程执行，哪些进程等待，也就是进程的调度。一、调度的目标1、首先要区分程序使用CPU的三种模式：IO密集型、计算密集型和平衡型。对于IO密集型程序来说，响应时间非常重要；对于CPU密集型来说，CPU的周转时间就比较重要；对于平衡型程序来说，响应和周转之间的平衡是最重要的。2、CPU的调度就是要达到极小化平均响应时间、极大化系统吞吐率、保持系统各个功能部件均处于繁忙状态和提供某种公平的机制。3、对于实时系统来说，调度的目标就是要达到截止时间前完成所应该完成的任务和提供性能的可预测性。二、调度算法1、FCFS（Firstcomefirstserve)，或者称为FIFO算法，先来先处理。这个算法的优点是简单，实现容易，并且似乎公平；缺点在于短的任务有可能变的非常慢，因为其前面的任务占用很长时间，造成了平均响应时间非常慢。2、时间片轮询算法，这是对FIFO算法的改进，目的是改善短程序（运行时间短）的响应时间，其方法就是周期性地进行进程切换。这个算法的关键点在于时间片的选择，时间片过大，那么轮转就越接近FIFO，如果太小，进程切换的开销大于执行程序的开销，从而降低了系统效率。因此选择合适的时间片就非常重要。选择时间片的两个需要考虑的因素：一次进程切换所使用的系统消耗以及我们能接受的整个系统消耗、系统运行的进程数。时间片轮询看上起非常公平，并且响应时间非常好，然而时间片轮转并不能保证系统的响应时间总是比FIFO短，这很大程度上取决于时间片大小的选择，以及这个大小与进程运行时间的相互关系。3、STCF算法（Shorttimetocompletefirst)，顾名思义就是短任务优先算法。这种算法的核心就是所有的程序都有一个优先级，短任务的优先级比长任务的高，而OS总是安排优先级高的进程运行。STCF又分为两类：非抢占式和抢占式。非抢占式STCF就是让已经在CPU上运行的程序执行到结束或者阻塞，然后在所有的就绪进程中选择执行时间最短的来执行；而抢占式STCF就不是这样，在每进来一个新的进程时，就对所有进程（包括正在CPU上执行的进程）进行检查，谁的执行时间短，就运行谁。STCF总是能提供最优的响应时间，然而它也有缺点，第一可能造成长任务的程序无法得到CPU时间而饥饿，因为OS总是优先执行短任务；其次，关键问题在于我们怎么知道程序的运行时间，怎么预测某个进程需要的执行时间？通常有两个办法：使用启发式方法估算（例如根据程序大小估算），或者将程序执行一遍后记录其所用的CPU时间，在以后的执行过程中就可以根据这个测量数据来进行STCF调度。4、优先级调度，STCF遇到的问题是长任务的程序可能饥饿，那么优先级调度算法可以通过给长任务的进程更高的优先级来解决这个问题；优先级调度遇到的问题可能是短任务的进程饥饿，这个可以通过动态调整优先级来解决。实际上动态调整优先级（称为权值）+时间片轮询的策略正是linux的进程调度策略之一的SCHED_OTHER分时调度策略,它的调度过程如下：（1）创建任务指定采用分时调度策略，并指定优先级nice值(-20~19)。（2）将根据每个任务的nice值确定在cpu上的执行时间(counter)。（3）如果没有等待资源，则将该任务加入到就绪队列中。（4）调度程序遍历就绪队列中的任务，通过对每个任务动态优先级的计算(counter+20-nice)结果，选择计算结果最大的一个去运行，当这个时间片用完后(counter减至0)或者主动放弃cpu时，该任务将被放在就绪队列末尾(时间片用完)或等待队列(因等待资源而放弃cpu)中。（5）此时调度程序重复上面计算过程，转到第4步。（6）当调度程序发现所有就绪任务计算所得的权值都为不大于0时，重复第2步。linux还有两个实时进程的调度策略：FIFO和RR,实时进程会立即抢占非实时进程。5、显然，没有什么调度算法是毫无缺点的，因此现代OS通常都会采用混合调度算法。例如将不同的进程分为几个大类，每个大类有不同的优先级，不同大类的进程的调度取决于大类的优先级，同一个大类的进程采用时间片轮询来保证公平性。6、其他调度算法，保证调度算法保证每个进程享用的CPU时间完全一样；彩票调度算法是一种概率调度算法，通过给进程“发彩票”的多少，来赋予不同进程不同的调用时间，彩票调度算法的优点是非常灵活，如果你给短任务发更多“彩票”，那么就类似STCF调度，如果给每个进程一样多的“彩票”，那么就类似保证调度；用户公平调度算法，是按照每个用户，而不是按照每个进程来进行公平分配CPU时间，这是为了防止贪婪用户启用了过多进程导致系统效率降低甚至停顿。7、实时系统的调度算法，实时系统需要考虑每个具体任务的响应时间必须符合要求，在截止时间前完成。（1）EDF调度算法，就是最早截止任务优先（Earliestdeadlinefirst)算法，也就是让最早截止的任务先做。当新的任务过来时，如果它的截止时间更靠前，那么就让新任务抢占正在执行的任务。EDF算法其实是贪心算法的一种体现。如果一组任务可以被调度（也就是所有任务的截止时间在理论上都可以得到满足），那么EDF可以满足。如果一批任务不能全部满足（全部在各自的截止时间前完成），那EDF满足的任务数最多，这就是它最优的体现。EDF其实就是抢占式的STCF，只不过将程序的执行时间换成了截止时间。EDF的缺点在于需要对每个任务的截止时间做计算并动态调整优先级，并且抢占任务也需要消耗系统资源。因此它的实际效果比理论效果差一点。（2）RMS调度算法，EDF是动态调度算法，而RMS（ratemonotonicscheduling)算法是一种静态最优算法；该算法在进行调度前先计算出所有任务的优先级，然后按照计算出来的优先级进行调度，任务执行中间既不接收新任务，也不进行优先级调整或者CPU抢占。因此它的优点是系统消耗小，缺点就是不灵活了。对于RMS算法，关键点在于判断一个任务组是否能被调度，这里有一个定律，如果一个系统的所有任务的CPU利用率都低于ln2，那么这些任务的截止时间均可以得到满足，ln2约等于0.693147，也就是此时系统还剩下有30%的CPU时间。这个证明是Liu和Kayland在1973年给出的。三、优先级反转1、什么是优先级反转？优先级反转是指一个低优先级的任务持有一个被高优先级任务所需要的共享资源。高优先任务由于因资源缺乏而处于受阻状态，一直等到低优先级任务释放资源为止。而低优先级获得的CPU时间少，如果此时有优先级处于两者之间的任务，并且不需要那个共享资源，则该中优先级的任务反而超过这两个任务而获得CPU时间。如果高优先级等待资源时不是阻塞等待，而是忙循环，则可能永远无法获得资源，因为此时低优先级进程无法与高优先级进程争夺CPU时间，从而无法执行，进而无法释放资源，造成的后果就是高优先级任务无法获得资源而继续推进。2、解决方案：（1）设置优先级上限，给临界区一个高优先级，进入临界区的进程都将获得这个高优先级，如果其他试图进入临界区的进程的优先级都低于这个高优先级，那么优先级反转就不会发生。（2）优先级继承，当一个高优先级进程等待一个低优先级进程持有的资源时，低优先级进程将暂时获得高优先级进程的优先级别，在释放共享资源后，低优先级进程回到原来的优先级别。嵌入式系统VxWorks就是采用这种策略。这里还有一个八卦，1997年的美国的火星探测器（使用的就是vxworks)就遇到一个优先级反转问题引起的故障。简单说下，火星探测器有一个信息总线，有一个高优先级的总线任务负责总线数据的存取，访问总线都需要通过一个互斥锁（共享资源出现了）；还有一个低优先级的，运行不是很频繁的气象搜集任务，它需要对总线写数据，也就同样需要访问互斥锁；最后还有一个中优先级的通信任务，它的运