操作系统——时间片轮换调度法
同义词：时间片轮换法一般指时间片轮换规划算法。 时间片轮换计划是最古老、最简单、最公平、使用最广泛的算法。 每个进程都分配了一个称为时间片的时间段。 这意味着允许进程运行的时间。
名称时间片轮转调度算法释义每个进程被分配了一个时间段，定义该进程可以运行的时间的合理时间片被设置为100毫秒
时间片循环调度算法语义时间片循环调度是最古老、最简单、最公平、使用最广泛的算法。 每个进程都分配了一个称为时间片的时间段。 这意味着进程可以运行的时间。 如果进程在时间片结束时仍在运行，则CPU将被抢占并分配给其他进程。 如果进程在时间片结束之前阻塞或终止，CPU将立即进行切换。 调度程序维护准备就绪的进程列表，并在进程用完时间片后将其移动到队列末尾。 时间片轮转调度中唯一有趣的是时间片的长度。 从一个过程切换到另一个过程需要时间。 保存和读取寄存器值和内存映像，更新各种表和队列等。 有时称为process switch上下文切换，需要5毫秒。 此外，假设时间片设置为20毫秒，则在完成20毫秒的有用工作后，CPU需要5毫秒来切换进程。 20%的CPU时间浪费在管理成本上。 为了提高CPU效率，可以将时间片设置为500毫秒。 此时浪费的时间只有1%。 但是，让我们考虑一下在时分系统中，如果10个交互式用户几乎同时按下回车键，会发生什么情况。 假设所有其他进程都充分使用了工时记录卡，最后一个不幸的进程必须等待5秒钟。 大多数用户无法忍受需要5秒才能响应的短命令。 同样的问题也发生在支持多个程序的一台电脑上。 结论是时间片过短会导致进程切换过多，降低CPU效率； 如果太长，对短交互请求的响应可能会变差。 将时间片设置为100毫秒通常是一个合理的折中。
时间片轮转调度算法的基本原理在初期的时间片轮转法中，系统将所有的准备过程按先后顺序排列在队列中，每次调度时将CPU分配到队列的前端过程中执行。 时间片的大小可以是几毫秒到几百毫秒。 执行的时间片消失的话，通过计时器发出时钟中断要求，调度程序相应地停止进程的执行，发送到准备队列之后，在就绪队列内的新的队列前端进程中分配处理器，同时也执行时间片时间片循环调度算法时间片大小的确定1。 对系统响应时间的要求2。 就绪队列中的进程数3。 系统处理能力时间片循环调度算法时间片循环调度算法多级反馈多级反馈队列调度算法(1)设置多个队列。 然后，给每个队列不同的优先级。 第一个队列的优先级最高，第二个队列次高，其馀每个队列的优先级逐一降低。 该算法对各队列内的进程给予执行时间片的大小也各不相同的：优先级越高的队列，各进程规定的执行时间片越小。 例如，在：的第二个队列的时间片比第一个队列的时间片长两倍，第i 1个队列的时间片比第I个队列的时间片长两倍。 )2)新进程进入内存后，首先放入最初队列的最后，根据FCFS原则进行排队等待调度。 一旦轮到该进程被执行，如果在该时间片内能够完成，则准备撤离系统； 如果时间片结束时尚未完成，调度程序将进程移动到第二个队列的末尾，并根据FCFS策略等待调度的运行。 在第2队列中执行了时间片还没有完成的情况下，将其放入第3队列后，…… 这样，调度程序按照从第1队列至第n队列的长任务(过程)的顺序下降后，在第n队列中按每个时间片执行旋转。 仅当第I(I-1 )个队列为空时，才会在第I个队列中调度进程的执行。 在第I个队列中服务进程时，如果新进程进入了高优先级队列(I(I-1 )中的任意一个队列)，则新进程将抢占运行该进程的处理器。 也就是说，调度程序将正在运行的进程放回第I个队列的末尾，以分配处理器的性能(1)终端作业用户(2)短批处理作业用户(3)长批处理作业用户： 满足大量用户需求的时间片轮换调度算法优先级调度算法1、优先级调度算法类型非抢占型优先级算法在这种方式下，系统是就绪队列中优先级最高的或者，如果过程因为一个事件发生而放弃所述处理器，那么系统可将所述处理器重新分配给具有最高优先级的另一过程。 该调度算法主要用于批处理系统； 也可以在对实时性要求不严格的实时系统中使用。 抢占优先级调度算法也同样将处理器分配给优先级最高的进程来执行。 但是，如果在运行过程中出现另一个具有较高优先级的进程，进程调度器将立即停止运行当前进程(最高优先级的进程)。 将处理器重新分配给新到的优先级最高的进程。 该抢占式优先级排序算法能更好地满足迫切的作业要求，常用于要求相对苛刻的实时系统，以及对性能要求较高的批量共享系统。 2、优先级类型(1)静态优先级静态优先级在进程创建时确定，在进程运行过程中保持不变。 一般来说，优先级是用某个范围内的整数来表示的
的某一整数, 又把该整数称为优先数.只是具体用法各异:有的系统用"0"表示最高优先权,当数值愈大时,其优先权愈低;而有的系统恰恰相反. 确定进程优先权的依据有如下三个方面: 1.进程类型.(系统进程/用户进程) 2.进程对资源的需求.(需求量的大小) 3.用户要求.(用户进程紧迫程度) (2) 动态优先权 动态优先权是指在创建进程时所赋予的优先权,可以随进程的推进或随其等待时间的增加而改变的,以便获得更好的调度性能. 例如,我们可以规定,在就绪队列中的进程,随其等待时间的增长,其优先权以速率a提高.若所有的进程都具有相同的优先权初值,则显然是最先进入就绪队列的进程,将因其动态优先权变得最高而优先获得处理机,此即FCFS算法. 优先权的变化规律可描述为: 由于等待时间与服务时间之和,就是系统对该作业的响应时间,故该优先权又相当于响应比RP.据此,又可表示为: 3,高响应比优先调度算法 由上面的式子可以得到以下结论: (1) 如果作业的等待时间相同,则要求服务的时间愈短,其优先权愈高,因而该算法有利于短作业. (2) 当要求服务的时间相同时,作业的优先权决定于其等待时间,等待时间愈长,其优先权愈高,因而它实现的是先来先服务. (3) 对于长作业,作业的优先级可以随等待时间的增加而提高,当其等待时间足够长时,其优先级便可升到很高, 从而也可获得处理机. 该算法照顾了短作业,且不会使长作业长期得不到服务 时间片轮转调度算法抢占式 1. 非抢占式调度算法 为每一个被控对象建立一个实时任务并将它们排列成一轮转队列,调度程序每次选择队列中的第一个任务投入运行.该任务完成后便把它挂在轮转队列的队尾等待下次调度运行. 2. 非抢占式优先调度算法. 实时任务到达时,把他们安排在就绪队列的队首,等待当前任务自我终止或运行完成后才能被调度执行. 3. 抢占式调度算法 1）基于时钟中断的抢占式优先权调度算法. 实时任务到达后,如果该任务的优先级别高于当前任务的优先级并不立即抢占当前任务的处理机,而是等到时钟中断到来时,调度程序才剥夺当前任务的执行,将处理机分配给新到的高优先权任务. 2）立即抢占的优先权调度算法. 在这种调度策略中,要求操作系统具有快速响应外部时间中断的能力.一旦出现 外部中断,只要当前任务未处于 临界区便立即剥夺当前任务的执行,把处理机分配给请求中断的紧迫任务，实时进程调度，实时进程抢占当前。 时间片轮转调度算法实时系统 1 实现实时调度的基本条件 1-1. 提供必要的信息-就绪时间. 1-2. 开始截止时间和完成截止时间. 1-3. 处理时间. 1-4. 资源要求. 1-5. 优先级. 2. 系统处理能力强 在实时系统中,通常都有着多个实时任务.若处理机的处理能力不够强,则有可能因处理机忙不过来而使某些实时任务不能得到及时处理, 从而导致发生难以预料的后果.假定系统中有m个周期性的硬实时任务,它们的处理时间可表示为Ci,周期时间表示为Pi,则在单处理机情况下,系统可调度必须满足下面的限制条件: 当系统不可调度时解决的方法是提高系统的处理能力,其途径有二: 其一仍是采用 单处理机系统,但须增强其处理能力, 以显著地减少对每一个任务的处理时间; 其二是采用 多处理机系统.假定系统中的处理机数为N,则应将上述的限制条件改为: 3. 采用抢占式调度机制 当一个优先权更高的任务到达时,允许将当前任务暂时挂起,而令高优先权任务立即投入运行.采用这种方式去满足那些开始截止时间即将到来的任务.? 4. 具有快速切换机制 应具有的能力: (1) 对外部中断的快速响应能力.为使在紧迫的外部事件请求中断时系统能及时响应,要求系统具有快速硬件中断机构,还应使禁止中断的时间间隔尽量短,以免耽误时机(其它紧迫任务).? (2) 快速的任务分派能力.在完成任务调度后,便应进行任务切换.为了提高分派程序进行任务切换时的速度, 应使系统中的每个运行功能单位适当的小,以减少任务切换的时间开销. 实时调度实例 一, 最早截止时间优先算法(EDF) EDF算法用于非抢占调度方式 优先级:根据任务的开始截止时间来确定任务的优先级. 二,最低松弛优先算法(LLF) 例如:系统中有两个周期性实时任务A和B,任务A要求每20ms执行一次,执行时间为10ms;任务B要求每50ms执行一次,执行时间为25ms.这样可知A和B每次必须完成的时间和开始截止时间如图所示 优先级:根据任务紧急程度来确定任务优先级 A和B任务每次必须完成的时间 A1 (10) A2 (30) A3(50) A4 (70) A5(90) A6 (110) A7(130) A8(150) 0 、10、 20、 30 、40、 50 、60、 70、 80 、90 、100 、110、 120、130、 140、 150 B1(25) B2(75) B3(125) A和B任务每次必须开始的时间 时间(ms) A截止时间 B截止时间 调度对象 0 A1(10) B1(25) A1 10 A2(20) B1(15) B1 30 A2(0) B1(15) A2 40 A3(10) B1(5) B1 45 A3(5) B2(30) A3 55 A4(15) B2(20) B2 70 A4(0) B2(20) A4 松弛度 松弛度 ( 20-10-0 ) ( 50-25-0 ) (40-10-10 ) ( 50-25-10 ) (40-10-30) (50-5-30) (60-10-40) (50-5-40) (60-10-45) (100-25-45) (80-10-55) (100-25-55) (80-10-70) (100-10-70 ) 3.4.1 多处理器系统 的类型 (1) 紧密耦合(Tightly Coupted)MPS. 这通常是通过高速总线或高速 交叉开关,来实现多个处理器之间的互连的.它们共享 主存储器系统和I/O设备,并要求将主存储器划分为若干个能独立访问的存储器模块,以便多个处理机能同时对主存进行访问.系统中的所有资源和进程,都由操作系统实施统一的控制和管理. 3.4 多处理机系统中的调度 从处理器之间耦合的紧密程度上划分: 松散耦合(Loosely Coupled)MPS. 在松散耦合MPS中,通常是通过通道或 通信线路,来实现多台计算机之间的互连.每台计算机都有自己的 存储器和I/O设备,并配置了OS来管理本地资源和在本地运行的进程.因此,每一台计算机都能独立地工作, 必要时可通过通信线路与其它计算机交换信息,以及协调它们之间的工作. 根据系统中所用处理器的相同与否划分: (1) 对称多处理器系统SMPS. 在系统中所包含的各处理器单元,在功能和结构上都是相同的,当前的绝大多数MPS都属于SMP系统.例如,IBM公司的SR/6000 Model F50, 便是利用4片Power PC处理器构成的.? (2) 非对称多处理器系统.在系统中有多种类型的处理单元,它们的功能和结构各不相同,其中只有一个主处理器,有多个从处理器： 1. 对称多处理器系统中的进程分配方式 在SMP系统中,所有的处理器都是相同的,因而可把所有的处理器作为一个处理器池(Processor pool),由调度程序或基于处理器的请求,将任何一个进程分配给池中的任何一个处理器去处理.在进行进程分配时,可采用以下两种方式之一. 1) 静态分配(Static Assigenment)方式 2) 动态分配(Dynamic Assgement)方式? 3.4.2 进程分配方式 静态分配(Static Assigenment)方式 一个进程从开始执行直到完成,都被固定分配到一个处理器上去执行. 2) 动态分配(Dynamic Assgement)方式 系统中设置有公共的就绪队列.分配进程时,可以将进程分配到任何一个处理器上. 动态分配方式的主要优点是消除了各处理器忙闲不均的现象 2. 非对称MPS中的进程分配方式? 对于非对称MPS,其OS大多采用主—从(Master-Slave)式OS,即OS的核心部分驻留在一台主机上(Master),而从机(Slave)上只是用户程序,进程调度只由主机执行.每当从机空闲时,便向主机发送一索求进程的信号,然后,便等待主机为它分配进程.在主机中保持有一个就绪队列,只要就绪队列不空,主机便从其队首摘下一进程分配给请求的从机.从机接收到分配的进程后便运行该进程,该进程结束后从机又向主机发出请求. 缺点:对主机要求高,出现故障导致整个系统瘫痪 1. 自调度(Self-Scheduling)方式 1) 自调度机制? 在系统中设置有一个公共的进程或线程就绪队列, 所有的处理器在空闲时,都可自己到该队列中取得一进程(或线程)来运行.在自调度方式中,可采用在单处理机环境下所用的调度算法,如先来先服务(FCFS)调度算法,最高优先权优先(FPF)调度算法和抢占式最高优先权优先调度算法等. 3.4.3 进程(线程)调度方式 2) 自调度方式的优点? 1,系统中的公共就绪队列可按照单处理机系统中所采用的各种方式加以组织;其调度算法也可沿用单处理机系统所用的算法,即很容易将单处理机环境下的调度机制移植到多处理机系统中 2,只要系统中有任务(公共就绪队列不空)就不会出现处理机空闲的情况,也不会发生处理器忙闲不均的现象,因而有利于提高处理器的利用率. 3)自调度方式的缺点 3.4.4进程调度过程 1、进程名：作为进程的标识。 指针：进程按顺序排成循环链表，用指针指出下一个进程的进程控制块首地址，最后一个进程中的指针指出第一个进程的进程控制块首地址。 2、要求运行时间：假设进程需要运行的单位时间数。 已运行时间：假设进程已经运行的单位时间数，初值为0。 状态：可假设有两种状态，就绪状态和结束状态。进程的初始状态都为就绪状态。 3、每次运行所设计的处理器调度程序调度进程之前，为每个进程任意确定它的要求运行时间。 4、此程序是模拟处理器调度，因此，被选中的进程并不实际启动运行，而是执行 已运行时间+1 来模拟进程的一次运行，表示进程已经运行过一个单位时间。 .5、在所设计的程序中应有显示或打印语句，能显示或打印每次被选中的进程名以及运行一次后进程队列的变化。 6、为进程任意确定要求运行时间，运行所设计的处理器调度程序，显示或打印逐次被选中进程的进程名以及进程控制块的动态变化过程。 7、设有一个就绪队列，就绪进程按优先数（优先数范围0－100）由小到大排列（优先数越小，级别越高）。当某一进程运行完一个时间片后，其优先级应下调（如优先数加2或3）。 8、例如一组进程如下表： 进程名 A B C D E F G H J K L M 到达时间 0 1 2 3 6 8 12 12 12 18 25 25 服务时间 6 4 10 5 1 2 5 10 4 3 15 8 时间片轮转调度算法瓶颈问题 1. 整个系统中只有一个就绪队列供多个处理器共享. (2)低效性. 线程在其生命周期内多次更换处理器使得高速缓存的使用率很低 (3)线程切换频繁. 2. 成组调度(Gang Scheduling)方式 3.专用处理器分配方式