2.7低级调度.ppt

《2.7低级调度.ppt》由会员分享，可在线阅读，更多相关《2.7低级调度.ppt（31页珍藏版）》请在得力文库 - 分享文档赚钱的网站上搜索。

1、主要内容：主要内容：n低级调度的功能低级调度的功能n低级调度算法低级调度算法n实时调度实时调度n多处理器调度多处理器调度2.7低级调度 1 1一、低级调度的功能一、低级调度的功能 (1)低级调度负责动态地把处理器分配给进程或内核级线程低级调度负责动态地把处理器分配给进程或内核级线程。操作系统中实现低级调度的程序称为进程(线程)调度程序，或分派程序(Dispatcher)。进程调度算法多数适用于线程调度。1.引起低级调度的原因 有四种情况都会发生CPU调度:当一个进程从运行态切换成等待态时;当一个进程从运行态切换成就绪态时;当一个进程从等待态切换成就绪态时;当一个进程中止时。也就是说当一个进程由

2、运行状态变为非运行状态,或者一个进程变为就绪状态时,都会引起低级调度.2 2一、低级调度的功能一、低级调度的功能(2)(2)2.2.低级调度的主要功能低级调度的主要功能 记录进程（内核级线程）的状态。一般记录在一个进程（内核级线程）的进程控制块（线程控制块）内。决定某个进程（内核级线程）什么时候获得处理器，以及占用多长时间。把处理器分配给进程（内核级线程）。即进行进程（内核级线程）上下文切换，把选中进程（内核级线程）的进程控制块（线程控制块）内有关现场信息送入处理器相应的寄存器中，让它占用处理器运行。收回处理器。将处理器有关寄存器内容送入该进程（内核级线程）的进程控制块（线程控制块）内的相应单

3、元，使该进程出让处理器。3 3一、低级调度的功能一、低级调度的功能(3)(3)低级调度的最初对象是传统操作系统中的进程，操作系统中引入了线程以后，进程只作为中级调度的对象，内核级线程则替代进程成为低级调度的对象。适用于进程调度的算法一般都适用于内核级线程的调度。用户级线程的调度是应用程序自己的事。在纯用户级多线程策略中，低级调度的对象依然是进程；在混合策略中，低级调度的对象是内核级线程。4 4二、低级调度算法二、低级调度算法(1)1.1.先来先服务算法先来先服务算法 按照进程进入就绪队列的先后次序分配处理器。先进入就绪队列的进程优先被挑选，运行进程一旦占有处理器将一直运行直到结束或阻塞。这是一

4、种非剥夺式调度。算法容易实现，效率不高，不利于I/O频繁的进程。2.时间片轮转调度算法时间片轮转调度算法(1)算法思想 轮转法调度也称为时间片调度，时间片调度做法是：调度程序每次把CPU分配给就绪队列首进程使用一个时间片，例如100ms，就绪队列中的每个进程轮流地运行一个时间片。当这个时间片结束时，强迫一个进程让出处理器，让它排列到就绪队列的尾部，等候下一轮调度。5 5二、低级调度算法(2)(2)实现原理 实现这种调度要使用一个间隔时钟。当一个进程开始运行时，就将时间片的值置入间隔时钟内，当发生间隔时钟中断时，中断处理程序就通知处理器调度进行处理器的切换工作。(3)效果：轮转策略可防止那些很少

5、使用外围设备的进程过长的占用处理器而使得要使用外围设备的那些进程没有机会去启动外围设备。(4)常用轮转法 最常用的轮转法是基本轮转法，它要求每个进程轮流运行一个相同的时间片。改进的轮转法对于不同的进程给以不同的时间片；时间片的长短可以动态地修改等等。6 6二、低级调度算法二、低级调度算法(3)(5)时间片取选 轮转法调度是一种剥夺式调度，系统耗费在进程切换上的开销比较大，这个开销与时间片的大小很有关系。时间片取值太小，多数进程不能在一个时间片内运行完毕，切换就会频繁，开销显著增大，从系统效率来看，时间片取大一点好。时间片取值较大，随就绪队列里进程数目增加，轮转一次的总时间增大，对进程的响应速度

6、放慢了。如果时间片大到让每个进程足以完成其所有任务，这一算法就退化成先来先服务算法。为满足响应时间要求，要么限制就绪队列中进程数量，要么采用动态时间片法，根据负载状况，及时调整时间片的大小。时间片大小的确定要从进程个数、切换开销、系统效率和响应时间等方面考虑。7 7二、低级调度算法二、低级调度算法(4)3.3.优先数调度优先数调度(1)含义：含义：给每一个进程确定一个优先数，处理器调度每次选择就绪进程中优先数最大者，让它占用处理器运行称优先数调度。(2)优先数的确定依据（静态优先数法）优先数的确定依据（静态优先数法）使用外围设备频繁者优先数大，这样有利于提高效率；重要算题程序的进程优先数大，这

7、样有利于用户更早得到结果；进入计算机时间长的进程优先数大，这样有利于缩短作业周转时间；交互式用户的进程优先数大，这样有利于终端用户的响应时间等等,8 8二、低级调度算法(5)(3)(3)动态优先数法及其确定原则动态优先数法及其确定原则 动态优先数法：在创建一个进程时，根据进程类型和资源使用情况确定一个优先数，当进程耗尽时间片或重新被调度时，再次计算并调整所有进程的优先数。动态优先数的确定原则：根据进程占有CPU时间多少来决定,当进程占有CPU时间愈长,那么，在它被阻塞之后再次获得调度的优先级就越低，反之,进程获得调度的可能性越大;根据进程等待CPU时间多少来决定,当进程在就绪队列中等待时间愈长

8、,那么，在它被阻塞之后再次获得调度的优先级就越高，反之,进程获得调度的可能性越小。9 9二、低级调度算法(6)(4)基于优先数的低级调度算法有两种调度方式：剥夺式和非剥夺式优先数调度算法。(5)UNIX(早期版本)动态优先数计算公式 p-pri=min 127,(p-cpu/16+PUSER+p-nice)p-pri为进程优先数，该值越小，则该进程优先权越高。p-nice用户调节参数，用户可按任务紧急程度设置。PUSER为常数 100p-cpu反映进程使用处理机的程度 1010二、低级调度算法(7)p-cpu按如下方法来改变：系统时钟中断处理程序每20ms工作一次，每次工作就将当前进程的p-c

9、pu加1。每到1秒时它就依次检查系统中所有进程的p-cpu，若被检查进程的p-cpu10，就表明该进程在这1秒内所使用处理机的时间超过200ms，于是将p-cpu置减10。UNIX这种动态优先数调度效果是：(1)如果一个进程连续占用处理机较长时间，那么，它的p-cpu值就增大，计算出的p-pri也增大，于是优先权下降。(2)如果一个进程长时间未被调用到或者虽频繁调度到，但每次占用的时间都小于200ms，那么，p-cpu就较小甚至为0，从而，计算出的p-pri也较小，于是优先权上升。1111二、低级调度算法(8)UNIX系统计算优先数的时机：一是对所有优先数大于100的进程，系统每秒钟重新计算一

10、次它的优先数；二是每次系统调用命令处理完毕之时，就重新对现进程的优先数进行计算。1212二、低级调度算法二、低级调度算法(9)4.4.多级反馈队列调度（反馈循环队列或多队列策略）多级反馈队列调度（反馈循环队列或多队列策略）(1)主要思想：是将就绪进程分为两级或多级，系统相应建立两个或多个就绪进程队列，较高优先级的队列一般分配给较短的时间片。处理器调度每次先从高级就绪进程队列中选取可占有处理器的进程，只有在选不到时，才从较低级的就绪进程队列中选取。同一队列中的进程按先来先服务原则排队。开始工作时，每当一个新进程进入内存后，首先进入高优先级队列等候调度，若能在该级队列的一个时间片内执行完成，则撤离

11、系统，否则进入低一级的队列等候调度，对列级别越低，时间片就越大，低优先级队列中的进程获得调度时运行的时间就长一些。(2)效果：性能较好，能满足各类用户的需要。1313二、低级调度算法(10)对分时交互式作业：通常可在最高优先级队列规定的一个时间片内完成，响应时间快。对于长批处理型作业：可以从高到低在各优先级队列中运行一个时间片直到在某个级别队列中执行完毕或者在最后一个队列中经过若干个时间片执行完毕，决不会发生长批处理型作业长期得不到调度的情况。1414二、低级调度算法(11)5 保证调度算法：保证调度算法：基本思想：向用户作出明确的性能保证，然后实现它。方案：如果有n个联机用户（进程），保证每

12、个联机用户（进程）获得CPU处理能力的1/n.系统必须跟踪各个进程的CPU使用时间，然后计算各个进程应该获得的CPU时间。1515二、低级调度算法(12)5 彩票调度算法：彩票调度算法：基本思想：为进程发放针对系统各种资源（包括CPU时间）的彩票，当调度程序需要决策时，随机选择一张彩票，则持有该彩票的进程将获得资源。进程获取资源（运行时间）的概率与彩票的数量成正比。进程获取资源（运行时间）的概率与彩票的数量成正比。彩票算法的特点：彩票算法的特点：彩票调度算法的反应非常迅速。进程之间可以交换彩票。彩票算法可以解决其它算法很难保证解决的问题。1616三、实时调度(1)1.实时操作系统的特性(1)特

13、性 实时系统是那些时间因素非常关键的系统。实时系统包括监控系统、自动驾驶系统、安全控制系统等，这些系统中，迟到的响应即使正确，也和没有响应一样糟糕。(2)实时系统分类 通常分为硬实时系统和软实时系统：实时系统通常分为硬实时（hard real time）系统和软实时（soft real time）系统。前者意味着存在必须满足的时间限制；后者意味着偶尔超过时前者意味着存在必须满足的时间限制；后者意味着偶尔超过时间限制时可以容忍的。间限制时可以容忍的。(3)实时系统要响应的事件分类：分为周期性（每隔一段固定的时间发生）和非周期性事件（在不可预测的时间发生）。1717三、实时调度(2)(4)实时任务

14、的可调度性 假如有m个周期性事件，事件i的周期为Pi，每个事件需要Ci秒的CPU时间来处理，则只有满足以下条件：C1/P1+C2/P2+Cm/Pm 1 时，才可能处理所有的负载。满足该条件的实时系统称作任务可调度的（schedulable）。例如，一个软实时系统处理三个事件流，其周期分别为100ms，200ms和500ms，如果事件处理时间分别为50ms，30ms和100ms，则这个系统是可调度的，因为 50/100+30/200+100/500=0.5+0.15+0.2=0.85 1 1818三、实时调度(3)如果加入周期为1秒的第4个事件，则其处理时间不能超过a：50/100+30/200

15、+100/500+a/1000=1 a=150ms，否则该系统将不可调度。尽管在理论上采取了下面将要讨论的实时调度算法后就可将通用操作系统改造成实时操作系统，但实际上，通用操作系统的进程切换开销太大，以至于只能满足那些限制通用操作系统的进程切换开销太大，以至于只能满足那些限制较松的实时应用。因此多数实时系统都使用专用的实时操作系较松的实时应用。因此多数实时系统都使用专用的实时操作系统，这些系统一般规模小、进程切换快、中断屏蔽和处理时间统，这些系统一般规模小、进程切换快、中断屏蔽和处理时间短。短。1919三、实时调度三、实时调度(4)2.2.实时调度算法实时调度算法 (1)(1)单比率调度算法单

16、比率调度算法 基本思想：为每个进程分配一个与事件发生频率成正比的优先为每个进程分配一个与事件发生频率成正比的优先数数。例如，周期为20ms的进程优先数为50，周期为100ms的进程优先数为10，运行时调度程序总是调度优先数最高的就绪进程，并采取抢占式分配策略。(2)限期调度算法 基本思想：当一个事件发生时，对应的进程就按照截止期限被当一个事件发生时，对应的进程就按照截止期限被加入就绪进程队列。加入就绪进程队列。对于一个周期性事件，其截止期限即为事件下一次发生的时间。该调度算法首先运行队首进程，即截止即截止时间最近的那个进程。时间最近的那个进程。2020三、实时调度(5)(3)(3)最少裕度法最

17、少裕度法 基本思想：首先计算各个进程的富裕时间，即裕度（laxity），然后选择裕度最少的进程执行。选择裕度最少的进程执行。裕度裕度=截止时间截止时间-(-(就绪时间就绪时间+计算时间计算时间)2121四、多处理器调度(1)流行的多处理器系统有：流行的多处理器系统有：松松散散耦耦合合多多处处理理器器系系统统：包包括括一一组组相相对对独独立立的的处处理理器，每个处理器拥有自己的主存和器，每个处理器拥有自己的主存和I/OI/O通道。通道。紧紧密密耦耦合合多多处处理理器器系系统统：由由共共享享主主存存和和外外设设的的一一组组处理器组成。处理器组成。注意：注意：现现代代操操作作系系统统往往往往采采用用

18、进进程程调调度度与与线线程程调调度度相相结结合合的方式来完成多处理器调度。的方式来完成多处理器调度。2222四、多处理器调度(2)1.1.同步的粒度同步的粒度 同步的粒度，就是系系统统中中多多个个进进程程之之间间同同步步的的频频率率，它是刻画多处理系统特征和描述进程并发度的一个重要指标。根据进程或线程之间同步的周期（每隔多少条指令发生一次同步事件），同步粒度划分为5个层次：细粒度（fine-grained）：同步周期小于20条指令。属于超高并行度的应用。中粒度（medium-grained）：同步周期为20200条指令。适合多线程技术实现，即一个进程包括多个线程，多个线程并发或并行执行。粗粒度

19、（coarse-grained）：同步周期为2002000条指令。可用多进程并发程序设计实现。2323四、多处理器调度(3)超粗粒度（very coarse-grained）：同步周期为2000条指令以上。可在分布式环境中通过网络实现并发执行。独立（independent）：进程或线程之间不存在同步。2.多处理器调度的设计要点（有三点）多处理器调度的设计要点（有三点）设计要点之一是如何把处理器分配给进程：假定在多处理器系统中所有的处理器都相同，则可采用两种策略分配处理器：静态分配策略：把一个进程永久地分配给一个处理器，分配在创建时执行，每个处理器对应一个低级调度队列。动态分配策略：所有处理器共

20、用一个就绪队列。当一个处理器空闲时，就选择一个就绪进程占有该处理器运行，一个进程可以在任意时间在任意处理器上运行。2424四、多处理器调度(4)操作系统在多处理机系统中是怎样分布呢？方法之一是采用主从式管理结构，操作系统的核心部分运行在一个特殊的处理器上，其他处理器运行用户程序。当用户程序需要请求操作系统服务时，请求将被传送到主处理器上的操作系统。这种实现方式的缺点是（1）整个系统的坚定性与主处理器上运行的操作系统关系过大；（2）主处理器极易成为系统的瓶颈。方法之二是采用分布式管理结构，操作系统可以在所有处理器上运行，每个处理器也可以自我调度。还可以把操作系统内核分成几部分，分别放在不同处理器

21、上运行。设计要点之二是是否否要要在在单单个个处处理理器器上上支支持持多多道道程程序序设设计计。对于独立、超粗粒度和粗粒度并行性进程来说，回答是肯定的。但对于中粒度并行性中粒度并行性的进程来说，答案不明朗。设计要点之三是如何指派进程如何指派进程。2525四、多处理器调度(5)3.3.多处理器的调度算法多处理器的调度算法 实验证明，随着处理器数目的增多，复杂低级调度算法的有效随着处理器数目的增多，复杂低级调度算法的有效性逐步下降。性逐步下降。多数采取动态分配策略的多处理器系统中，低级调度算法往往采用最简单的FCFS或优先数算法。就绪进程组成一个队列或多个按照优先数排列的队列。多处理器调度的主要研究

22、对象是线程调度算法。尽管线程也给单处理器系统带来很大益处，但在多处理器环境多处理器环境中线程的作用才真正得到充分发挥。中线程的作用才真正得到充分发挥。2626四、多处理器调度(6)多处理器环境中线程调度的几种算法：1 1）负载共享调度算法）负载共享调度算法基本思想：进程并不分配给一个特定处理器，系统维护一个全局性就绪线程队列，当一个处理器空闲时，就选择一个就绪线程占有处理器运行。负载共享调度算法优点：把负载均分到所有可用处理器上，保证了处理器效率的提高。不需要一个集中的调度程序，一旦一个处理器空闲，调度程序就可以运行在该处理器上以选择下一个运行的线程。运行线程的选择可以采用各种可行的策略。27

23、27四、多处理器调度(7)负载共享调度算法不足：就绪线程队列将成为性能的瓶颈。被抢占的线程很难在同一个处理器上恢复运行，会带来性能下降。线程都被放在公共线程池中，所有线程获得处理器的机会相同。如果一个程序的线程希望获得较高优先级，进程切换将导致性能的折衷。2828四、多处理器调度(8)群调度算法：把一组进程在同一时间一次性调度到一组处理器上运行。优点：优点：当紧密相关的进程同时运行时，同步造成的等待减少，进程切换也减少，系统性能提高。一次性同时调度一组进程，调度的代价也减少。结论：结论：群群调调度度算算法法对对于于多多线线程程并并行行执执行行的的单单个个应应用用来来说说具具有有较较好好的的效效

24、率，因此多用在细粒度和中粒度的多处理器。率，因此多用在细粒度和中粒度的多处理器。2929四、多处理器调度(9)处理器专派调度算法：给一个应用专门指派一组处理器，一一旦旦一一个个应应用用被被调调度度，它它的的每每一一个个线线程程被被分分配配一一个个处处理理器器并并一一直直占占有有这这个个处处理理器器运运行行直直到到整个应用运行结束整个应用运行结束。即使该线程阻塞，被分派的处理器也不会被调度给其他线程，而是空闲。特点：特点：主要追求并行性；在一个应用的整个周期内避免低级调度和切换；不考虑处理器的利用效率。适用于高度并行性的多处理器系统。适用于高度并行性的多处理器系统。提醒：提醒：在在多多处处理理器

25、器并并行行机机计计算算环环境境里里，任任何何一一种种算算法法的的加加速速比比的的提提高高都是有限度的。都是有限度的。3030四、多处理器调度(10)动态调度算法：动态调度算法：起源：某些应用提供了语言或者工具以动态地改变进程中的线程数，操作系统应该能够相应地动态调整算法。基本思想：由操作系统和应用进程共同完成调度：操操作作系系统统负负责责在在应应用用进进程程之之间间划划分分处处理理器器；应应用用进进程程在在分分配配给给它它的的处处理理器器上执行可运行线程的子集（自主决定子集中的线程的调度）。上执行可运行线程的子集（自主决定子集中的线程的调度）。步骤：当新的进程产生时如果有空闲处理器，则分配给新进程；否则，从已经获得一个以上处理器的进程手中收回一个，分配给新进程。如果无法分得处理器，则保留请求，等待出现可用的处理器或者请求自愿撤销。在申请处理器的进程队列中，按照先来先服务的原则分配空闲处理器。3131