操作系统-第五章-进程调度

操作系统-第五章-进程调度

⼀、CPU调度概述

1.长程调度⼜称作业调度或⾼级调度处于新建状态的进程⼀般⾸先被放到外存的进程池中，当内存进程的数量没有达到最多进程数时，操作系统的调度程序才从新建状态选择⼀个进⼊内存并转换为就绪状态“新建”状态转换到“就绪”状态由调度程序选择控制多道程序的“道/度”

2.短程调度

⼜称为CPU调度或低级调度在就绪队列中可能存在不⽌⼀个进程，当CPU空闲时，操作系统就需要从就绪队列中挑选⼀个进程让它运⾏

3.长程调度与短程调度的⽐较

4.中程调度⼜称为交换从本质上讲，中程调度不属于进程管理的内容，⽽应该属于内存管理⼀个进程在内存和外存间的换进换出，最⼤的⽬的是节省内存当⼀个进程在内存中长期不运⾏时，会造成内存浪费，为此，操作系统把这些进程从内存换道外存，从⽽腾出内存空间供运⾏进程使⽤当⼀个在外存的进程接下来需要运⾏时，操作系统则执⾏还如操作，把这个进程从外存换⼊内存

5.进程调度队列

为了⽅便进⾏CPU调度，操作系统需要对不同状态的进程进⾏组织和管理。为此操作系统为某些特定的状态设⽴了⼀个或多个进程队列，⽤于管理这些进程作业队列：在系统中的所有进程的集合就绪队列：在主存中的，就绪并等待执⾏的所有进程的集合,不必是先进先出队列，队列中的记录通常是进程控制块(PCB)设备队列：等待某⼀I/O设备的进程队列进程的执⾏过程实际上就是进程在各种队列之间的迁移

6.CPU调度过程调度程序根据某种策略选择内存中的⼀个就绪进程⼀个CPU同时只能运⾏⼀个进程做选择分派程序负责把CPU的控制权转交CPU调度程序切换上下⽂切换到⽤户态跳转到⽤户程序的适当位置并重新运⾏之分派延迟：分派程序终⽌⼀个进程的运⾏并启动另⼀个进程运⾏所花的时间

7.调度⽅式⾮抢占式调度⼀旦把CPU分配给某个进程后，系统不可以抢占已分配的CPU并分配给其他进程只有进程⾃愿释放CPU，才可以把CPU分配给其他进程优点：容易实现，调度开销⼩，适合批处理系统缺点：响应时间长，不合适交互系统抢占式调度调度程序可以根据某种原则暂停某个正在执⾏的进程，将已分配给它的CPU重新分配给另⼀个进程当多个进程共享数据时，抢占调度可能导致竞争情况抢占也影响操作系统的内核设计可防⽌单⼀进程长时间独占CPU系统开销⼤受中断影响的代码应加以保护，从⽽避免同时使⽤，为了这些代码段不被多个进程同时访问，在进⼊时禁⽌中断⽽退出时启⽤中断抢占式与⾮抢占式的区分运⾏进程是否是⾃愿放弃CPU

8.CPU调度时机

CPU调度可能发⽣在当⼀个进程从运⾏转到等待(⾮抢占式)从运⾏转到就绪(抢占式)从等待转到就绪(抢占式)终⽌运⾏(⾮抢占式)⼆、调度准则

CPU利⽤率：固定时间内CPU运⾏时间的⽐例吞吐量：单位时间内运⾏完的进程数周转时间：进程从提交到运⾏结束的全部时间等待时间：进程等待调度(不在运⾏)的时间⽚总和响应时间：从进程提出请求到⾸次被响应(⽽不是输出结果)的时间段(在分时系统环境下)，也就是第⼀段的等待时间周转时间=等待时间+运⾏时间带权周转时间:周转时间/运⾏时间

三、调度算法

1.先来先服务调度算法(FCFS)

调度策略：按照进程请求CPU的先后顺序来使⽤CPU调度依据：进⼊就绪队列的时间调度⽅法：先进⼊就绪队列的进程被优先选中运⾏使⽤FIFO队列实现特点：实现简单，可使⽤FIFO队列实现⾮抢占式调度公平，每个进程都有被调度的机会适⽤于长程调度，后台批处理系统的短程调度对长CPU脉冲的进程有利，对短CPU脉冲的进程不利护航效果：当⼀个长进程后⾯的多个短进程，让长进程先执⾏，会让后⾯的短进程等待较长时间，从⽽导致CPU和设备利⽤率降低例：

2.短作业优先调度算法(SJF)

调度策略：关联到每个进程下次运⾏的CPU脉冲长度，调度最短的进程调度依据：每个进程下次运⾏的CPU脉冲长度调度⽅法：调度最短的进程运⾏两种模式：⾮抢占式调度：⼀旦进程拥有CPU，它可在该CPU脉冲结束后让出CPU抢占式调度：有⽐当前进程剩余时间更短的进程到达时，新来的进程抢占当前运⾏进程的CPU，也称为最短剩余时间优先调度SJF最优：对⼀组的进程⽽⾔，它给出了最短的平均等待时间SJF算法困难：如何知道下⼀个CPU区间的长度SJF通常⽤于长程调度指数估算法：通过先前的CPU区间长度及其指数平均进⾏预测饥饿：长进程可能长时间等待，知道进程会运⾏但不知道什么时候运⾏死锁：进程长时间等待，不会运⾏例：

3.优先级调度算法⽬前主流的操作系统调度算法调度依据：优先级就绪队列中的排列⽅式：优先级⾼的在前，优先级低的在后调度⽅法：调度优先级最⾼进程运⾏优先数：表⽰优先级的整数可以参考不同的因素来设置(时间极限，内存要求，进程的重要性)优先数可⽤某⼀范围的整数来表⽰静态优先级：进程创建时确定，在运⾏期间不变简单易⾏，系统开销⼩不够精确，可能会出现饥饿问题动态优先级：进程创建时的优先级随进程推进或等待时间增加⽽改变调度模式：抢占式调度⾮抢占式调度特点：实现简单，考虑了进程的紧迫程度策略灵活，可模拟其他算法存在问题：饥饿(低优先级的进程可能永远得不到运⾏)解决问题：视进程等待时间的延长提⾼其优先级例：

4.时间⽚轮转(RR)为分时系统设计算法原理：把⼀段时间分割成若⼲个⼩碎⽚，每个需要运⾏的进程获得⼀个碎⽚运⾏，即在这段时间内，每个进程都得到运⾏时间⽚：较⼩单位的CPU时间，通常为10-100毫秒RR算法的性能很⼤程度上取决于时间⽚的⼤⼩时间⽚⼤->FCFS时间⽚⼩->系统开销⼤⼀般准则：时间⽚/10>进程上下⽂切换时间周转时间也依赖时间⽚的⼤⼩调度依据：进⼊就绪队列的时间调度⽅法：每个进程运⾏时间长度为⼀个时间⽚，时间⽚⽤完后，该进程被抢占并插⼊就绪队列末尾假定就绪队列中有n个进程、时间⽚q则每个进程每次得到不超过q单位的成块CPU时间没有⼀个进程的等待时间会超过(n-1)q在不超过nq时间内，n个进程都运⾏⼀次例：

5.多级队列调度(MLQ)以上算法存在局限性，不能适应各种不同类型的进程SJF算法有利于短进程，⽽不利于长进程RR算法系统开销⼤优先级算法存在饥饿问题等所有进程采⽤同⼀策略，不合理不同类型的进程需要不同策略交互进程需要较短的响应时间批处理进程需要较短的等待时间通常，交互进程较批处理进程的优先级⾼多级队列调度允许系统中存在多个就绪队列，每个就绪队列有⾃⼰的调度算法根据进程属性，如内存⼤⼩、进程优先级、进程类型等，⼀个进程永远分到⼀个队列，每个队列有⾃⼰的调度算法队列之间应有调度通常采⽤固定优先级抢占调度，可能产⽣饥饿另⼀种⽅法是在队列之间划分时间⽚，每个队列都有⼀定⽐例的CPU时间，可⽤于调度队列内的进程关键：需要确定就绪队列的数量需要确定新进程进⼊那个队列需要确定每⼀个队列的调度算法例：就绪队列：前台(交互式)后台(批处理)每个队列有⾃⼰的调度算法前台：RR后台：FCFS队列间的调度⽅法固定优先级调度，即前台运⾏完后再运⾏后台。有可能产⽣饥饿给定时间⽚调度，即每个队列得到⼀定的CPU时间，进程在给定时间内执⾏；如，80%的时间执⾏前台的RR调度，20%的时间 执⾏后台的FCFS调度

6.多级反馈队列调度(MLFQ)多级反馈队列调度算法的核⼼是进程在运⾏过程中，能在不同队列间移动进程能在不同的队列间移动：可实现⽼化⼀种⽤于避免资源调度系统中的饥饿的技术多级反馈队列调度程序由以下参数定义：队列数每⼀队列的调度算法决定需要服务的进程将进⼊哪个队列的⽅法决定进程升级的⽅法(低级队列到⾼级队列)决定进程降级的⽅法(⾼级队列到低级队列)优点：⽐MLQ算法具有更好的灵活性MLFQ很好地解决了CPU调度问题Unix，Solaris，Windows的调度算法⼀定程度上都是MLFQ的变种例：

四、线程调度

1.概念

在⽀持线程的操作系统上，内核级线程(⽽不是进程)才是操作系统所调度的⽤户级线程是由线程库来管理的，⽽内核并不知道它们⽤户级线程为了运⾏在CPU上，最终映射到相关的内核级线程，但是这种映射可能不是直接的，可能采⽤轻量级进程

2.竞争范围

进程竞争范围(PCS)：对于实现多对⼀和多对多模型的系统线程库会调度⽤户级线程，以便在可⽤轻量级进程(LWP)上运⾏，因为竞争CPU是发⽣在同⼀进程的线程之间PCS采⽤优先级调度，即调度程序选择运⾏具有最⾼优先级的、可运⾏的线程。⽤户级线程的优先级是由程序员设置的，并不是由线程库调整的允许⼀个更⾼优先级的线程来抢占当前运⾏的线程系统竞争范围(SCS)：决定哪个内核级线程调度到⼀个处理器上，采⽤SCS调度来竞争CPU，发⽣在系统内的所有线程之间五、多处理调度

适⽤多核处理器的CPU调度多个CPU可⽤时，CPU调度将更为复杂

1.多处理调度的⽅法

⾮对称多处理器(ASMP)：仅⼀个处理器能处理系统数据结构，减轻了对数据的共享需求。由这个主处理器负责调度，处理所有调度决定、I/O处理以及其他系统活动，其他处理器只执⾏⽤户代码对称多处理器(SMP)：每个处理器决定⾃⼰的调度⽅案，主流⽅案所有进程可能处于⼀个共同的就绪队列中，或每个处理器都有它⾃⼰的私有就绪队列不管如何，调度这样进⾏：每个处理器的调度程序都检查共同就绪队列，以便选择执⾏⼀个进程调度⽅法：和单处理器相似

2.处理器亲和性

由于缓存的⽆效或重新填充的代价⾼，⼤多数SMP系统试图避免将进程从⼀个处理器移到另⼀个处理器，⽽是试图让⼀个进程运⾏在同⼀个处理器上进程要在某个给定的CPU上尽量长时间地运⾏⽽不被迁移到其他处理器的倾向性⾼速缓存中的内容软亲和性：当⼀个操作系统试图保持进程运⾏在同⼀个处理器上时(但不会保证它会这么做)，进程通常不会在处理器之间频繁迁移硬亲和性：进程不会在处理器之间迁移，有的系统提供系统调⽤，从⽽允许某个进程运⾏在某个处理器⼦集上系统的内存架构可以影响处理器的亲和性

3.负载平衡

将任务平均分配给SMP系统的各个处理器针对私有就绪队列，⽽对公共队列系统，负载平衡通常没有必要，因为⼀旦处理器空闲，它⽴刻从公共队列中取⾛⼀个可执⾏进程和处理器亲和性⽭盾保持⼀个进程运⾏在同⼀个处理器上的好处是进程可以利⽤它在该处理器缓存内的数据。⽆论是从⼀个处理器向另⼀个处理器推或拉进程，都会失去这个好处⽅法：推迁移：对于推迁移，⼀个特定的任务周期性地检查每个处理器的负载，如果发现不平衡，那么通过将进程从超载处理器推到空闲或不太忙的处理器，从⽽平均分配负载拉迁移：当空闲处理器从⼀个忙的处理器上拉⼀个等待任务时，发⽣拉迁移推迁移和拉迁移不必相互排斥，事实上，在负载平衡系统中它们常被并⾏实现

4.单队列调度⽅法

系统有⼀个就绪队列。当任意⼀个CPU空闲时，就从就绪队列中选择⼀个进程到该CPU上运⾏优点：容易从单核调度算法推⼴到多核/多处理器实现简单，负载均衡缺点：不具有亲和性，⼀个进程可能在不同时候被调度到不同的CPU多核同时访问⼀个队列，会有加锁问题，从⽽严重影响调度的性能

5.多队列调度⽅法

系统有多个就绪队列，⼀般每个CPU⼀个队列。每个就绪队列有⾃⼰的调度算法，并且每个就绪队列的调度相对独⽴优点：亲和性好不需要加锁缺点：负载不均衡策略：‘偷’进程