低级调度.ppt

二、低级调度算法 (5)
(3)动态优先数法及其确定原则
动态优先数法：在创建一个进程时，根据进程类型和资源使用 情况确定一个优先数，当进程耗尽时间片或重新被调度时，再 次计算并调整所有进程的优先数。
动态优先数的确定原则：
①根据进程占有CPU时间多少来决定,当进程占有CPU时间愈长, 那么，在它被阻塞之后再次获得调度的优先级就越低，反之,进 程获得调度的可能性越大;
处理器组成。 注意： 现代操作系统往往采用进程调度与线程调度相结合
的方式来完成多处理器调度。
四、多处理器调度 (2)
1.同步的粒度
同步的粒度，就是系统中多个进程之间同步的频率，它是刻画 多处理系统特征和描述进程并发度的一个重要指标。
根据进程或线程之间同步的周期（每隔多少条指令发生一次同 步事件），同步粒度划分为5个层次： •细粒度（fine-grained）：同步周期小于20条指令。属于超高 并行度的应用。 •中粒度（medium-grained）：同步周期为20~200条指令。适合 多线程技术实现，即一个进程包括多个线程，多个线程并发或 并行执行。 •粗粒度（coarse-grained）：同步周期为200~2000条指令。可 用多进程并发程序设计实现。
•收回处理器。将处理器有关寄存器内容送入该进程（内核级线 程）的进程控制块（线程控制块）内的相应单元，使该进程出 让处理器。
一、低级调度的功能 (3)
•低级调度的最初对象是传统操作系统中的进程，操作系统中引 入了线程以后，进程只作为中级调度的对象，内核级线程则替 代进程成为低级调度的对象。适用于进程调度的算法一般都适 用于内核级线程的调度。
2.7低级调度
主要内容：
低级调度的功能 低级调度算法 实时调度 多处理器调度
一、低级调度的功能 (1)
低级调度负责动态地把处理器分配给进程或内核级线程。操 作系统中实现低级调度的程序称为进程(线程)调度程序，或 分派程序(Dispatcher)。进程调度算法多数适用于线程调度。
1.引起低级调度的原因
三、实时调度 (3)
如果加入周期为1秒的第4个事件，则其处理时间不能超过a：
50/100+30/200+100/500+a/1000=1
a=150ms，否则该系统将不可调度。
尽管在理论上采取了下面将要讨论的实时调度算法后就可将通 用操作系统改造成实时操作系统，但实际上，
通用操作系统的进程切换开销太大，以至于只能满足那些限制 较松的实时应用。因此多数实时系统都使用专用的实时操作系 统，这些系统一般规模小、进程切换快、中断屏蔽和处理时间 短。
•用户级线程的调度是应用程序自己的事。在纯用户级多线程 策略中，低级调度的对象依然是进程；在混合策略中，低级调 度的对象是内核级线程。
二、低级调度算法 (1)
1.先来先服务算法
按照进程进入就绪队列的先后次序分配处理器。
先进入就绪队列的进程优先被挑选，运行进程一旦占有处理器 将一直运行直到结束或阻塞。这是一种非剥夺式调度。
(3)实时系统要响应的事件分类：分为周期性（每隔一段固定 的时间发生）和非周期性事件（在不可预测的时间发生）。
三、实时调度 (2)
(4)实时任务的可调度性
假如有m个周期性事件，事件i的周期为Pi，每个事件需要Ci秒 的CPU时间来处理，则只有满足以下条件：
C1/P1 + C2/P2 + … + Cm/Pm ≤ 1
三、实时调度 (1)
1.实时操作系统的特性
(1)特性
•实时系统是那些时间因素非常关键的系统。
•实时系统包括监控系统、自动驾驶系统、安全控制系统等，这 些系统中，迟到的响应即使正确，也和没有响应一样糟糕。
(2)实时系统分类
通常分为硬实时系统和软实时系统：实时系统通常分为硬实时 （hard real time）系统和软实时（soft real time）系统。 前者意味着存在必须满足的时间限制；后者意味着偶尔超过时 间限制时可以容忍的。
时间片大小的确定要从进程个数、切换开销、系统效率和响 应时间等方面考虑。
二、低级调度算法 (4)
3.优先数调度 (1)含义： 给每一个进程确定一个优先数，处理器调度每次选择就绪进程 中优先数最大者，让它占用处理器运行称优先数调度。 (2)优先数的确定依据（静态优先数法） •使用外围设备频繁者优先数大，这样有利于提高效率； •重要算题程序的进程优先数大，这样有利于用户更早得到结果； •进入计算机时间长的进程优先数大，这样有利于缩短作业周转 时间； •交互式用户的进程优先数大，这样有利于终端用户的响应时间 等等,
5 彩票调度算法：
•基本思想：为进程发放针对系统各种资源（包括CPU时间）的 彩票，当调度程序需要决策时，随机选择一张彩票，则持有该 彩票的进程将获得资源。 •进程获取资源（运行时间）的概率与彩票的数量成正比。 •彩票算法的特点：
彩票调度算法的反应非常迅速。 进程之间可以交换彩票。 彩票算法可以解决其它算法转法，它要求每个进程轮流运行一个 相同的时间片。改进的轮转法对于不同的进程给以不同的时间 片；时间片的长短可以动态地修改等等。
二、低级调度算法 (3)
(5)时间片取选
轮转法调度是一种剥夺式调度，系统耗费在进程切换上的开销 比较大，这个开销与时间片的大小很有关系。
二、低级调度算法 (7)
p-cpu按如下方法来改变：系统时钟中断处理程序每20ms工作一 次，每次工作就将当前进程的p-cpu加1。每到1秒时它就依次检 查系统中所有进程的p-cpu，若被检查进程的p-cpu<10，就表明 该进程在这1秒内所使用处理机的时间不超过200ms，于是将pcpu置为0；若被检查进程的p-cpu>10，就表明该进程在这1秒内 所使用处理机的时间超过200ms，于是将p-cpu置减10。
•记录进程（内核级线程）的状态。一般记录在一个进程（内核 级线程）的进程控制块（线程控制块）内。
•决定某个进程（内核级线程）什么时候获得处理器，以及占用 多长时间。
•把处理器分配给进程（内核级线程）。即进行进程（内核级线 程）上下文切换，把选中进程（内核级线程）的进程控制块 （线程控制块）内有关现场信息送入处理器相应的寄存器中， 让它占用处理器运行。
四、多处理器调度 (3)
时间片取值太小，多数进程不能在一个时间片内运行完毕，切 换就会频繁，开销显著增大，从系统效率来看，时间片取大一 点好。
时间片取值较大，随就绪队列里进程数目增加，轮转一次的总 时间增大，对进程的响应速度放慢了。如果时间片大到让每个 进程足以完成其所有任务，这一算法就退化成先来先服务算法。 为满足响应时间要求，要么限制就绪队列中进程数量，要么采 用动态时间片法，根据负载状况，及时调整时间片的大小。
三、实时调度 (4)
2.实时调度算法
(1)单比率调度算法
基本思想：为每个进程分配一个与事件发生频率成正比的优先 数。例如，周期为20ms的进程优先数为50，周期为100ms的进 程优先数为10，运行时调度程序总是调度优先数最高的就绪进 程，并采取抢占式分配策略。
(2)限期调度算法
基本思想：当一个事件发生时，对应的进程就按照截止期限被 加入就绪进程队列。对于一个周期性事件，其截止期限即为事 件下一次发生的时间。该调度算法首先运行队首进程，即截止 时间最近的那个进程。
二、低级调度算法 (11)
5 保证调度算法：
•基本思想：向用户作出明确的性能保证，然后实现它。 •方案：
如果有n个联机用户（进程），保证每个联机用户（进程）获 得CPU处理能力的1/n . •系统必须跟踪各个进程的CPU使用时间，然后计算各个进程应 该获得的CPU时间。
二、低级调度算法 (12)
UNIX这种动态优先数调度效果是：
(1)如果一个进程连续占用处理机较长时间，那么，它的p-cpu 值就增大，计算出的p-pri也增大，于是优先权下降。
(2)如果一个进程长时间未被调用到或者虽频繁调度到，但每次 占用的时间都小于200ms，那么，p-cpu就较小甚至为0，从而， 计算出的p-pri也较小，于是优先权上升。
时，才可能处理所有的负载。满足该条件的实时系统称作任务 可调度的（schedulable）。
例如，一个软实时系统处理三个事件流，其周期分别为100ms， 200ms和500ms，如果事件处理时间分别为50ms，30ms和100ms， 则这个系统是可调度的，因为
50/100+30/200+100/500=0.5 + 0.15 + 0.2=0.85 ≤ 1
算法容易实现，效率不高，不利于I/O频繁的进程。
2.时间片轮转调度算法
(1)算法思想
轮转法调度也称为时间片调度，时间片调度做法是：调度程序 每次把CPU分配给就绪队列首进程使用一个时间片，例如 100ms，就绪队列中的每个进程轮流地运行一个时间片。当这 个时间片结束时，强迫一个进程让出处理器，让它排列到就绪 队列的尾部，等候下一轮调度。
三、实时调度 (5)
(3)最少裕度法
基本思想：首先计算各个进程的富裕时间，即裕度（laxity）， 然后选择裕度最少的进程执行。 裕度=截止时间-(就绪时间+ 计算时间)
四、多处理器调度 (1)
流行的多处理器系统有： •松散耦合多处理器系统：包括一组相对独立的处理
器，每个处理器拥有自己的主存和I/O通道。 •紧密耦合多处理器系统：由共享主存和外设的一组
有四种情况都会发生CPU调度: •当一个进程从运行态切换成等待态时; •当一个进程从运行态切换成就绪态时; •当一个进程从等待态切换成就绪态时; •当一个进程中止时。 也就是说当一个进程由运行状态变为非运行状态,或者一个进 程变为就绪状态时,都会引起低级调度.
一、低级调度的功能 (2)
2.低级调度的主要功能
二、低级调度算法 (8)