Microsoft PowerPoint - Chapter3_2_Scheduling.pptx

Size: px

Start display at page:

Download "Microsoft PowerPoint - Chapter3_2_Scheduling.pptx"

必坦邢
5 years ago
Views:

1 操作系统 2014 春第三章进程机制与并发程序设计 - 处理机调度授课人 : 孙海龙 2014 年 3 月 19 日调度的类型与模型常见的调度算法实时系统调度多处理机调度内容提要 1

2 要解决的问题 WHAT: 按什么原则分配 CPU 进程调度算法 WHEN: 何时分配 CPU 进程调度的时机 HOW: 如何分配 CPU CPU 切换过程 ( 进程的上下文切换 ) 处理机调度调度的类型与模型调度算法实时系统中的调度多处理机调度 2

3 问题处理机管理的工作是对 CPU 资源进行合理的分配使用, 以提高处理机利用率, 并使各用户公平地得到处理机资源这里的主要问题是处理机调度算法和调度算法特征分析高级调度中级调度低级调度调度的类型 3

4 高级调度高级调度 : 又称为宏观调度作业调度从用户工作流程的角度, 一次提交的若干个作业, 对每个作业进行调度时间上通常是分钟小时或天接纳多少个作业接纳哪些作业中级调度内外存交换 : 又称为中级调度指令和数据必须在内存里才能被 CPU 直接访问从存储器资源的角度, 将进程的部分或全部换出到外存上, 将当前所需部分换入到内存 4

5 低级调度低级调度 : 又称为微观调度进程或线程调度从 CPU 资源的角度, 执行的单位, 时间上通常是毫秒因为执行频繁, 要求在实现时达到高效率非抢占式抢占式时间片原则优先权原则短作业 ( 进程 ) 优先 New Admit Admit Suspend Ready Suspend Activate Suspend Ready Dispatch Timeout Running Release Exit Event Occurs Event Occurs Event Wait Activate Blocked Suspend Suspend Blocked 微观调度中级调度宏观调度 5

6 何时进行调度当一个新的进程被创建时, 是执行新进程还是继续执行父进程? 当一个进程运行完毕时 ; 当一个进程由于 I/O 信号量或其他的某个原因被阻塞时 ; 当一个 I/O 中断发生时, 表明某个 I/O 操作已经完成, 而等待该 I/O 操作的进程转入就绪状态 ; 在分时系统中, 当一个时钟中断发生时何时进行切换只要 OS 取得对 CPU 的控制, 进程切换就可能发生 : 用户调用 : 来自程序的显式请求 ( 如 : 打开文件 ), 该进程多半会被阻塞陷阱 : 最末一条指令导致出错, 会引起进程移至退出状态中断 : 外部因素影响当前指令的执行, 控制被转移至中断处理程序 6

7 在进程 ( 上下文 ) 中切换的步骤保存处理器的上下文, 包括程序计数器和其它寄存器用新状态和其它相关信息更新正在运行进程的 PCB 把进程移至合适的队列 - 就绪阻塞选择另一个要执行的进程更新被选中进程的 PCB 从被选中进程中重装入 CPU 上下文调度的性能准则从不同的角度来判断处理机调度算法的性能, 如用户的角度处理机的角度和算法实现的角度实际的处理机调度算法选择是一个综合的判断结果 7

8 面向用户的调度性能准则 1 周转时间 : 作业从提交到完成 ( 得到结果 ) 所经历的时间包括 : 在收容队列中等待,CPU 上执行, 就绪队列和阻塞队列中等待, 结果输出等待 -- 批处理系统外存等待时间就绪等待时间 CPU 执行时间 I/O 操作时间平均周转时间带权平均周转时间 (T/Ts): 总周转时间 / 总服务时间响应时间 : 用户输入一个请求 ( 如击键 ) 到系统给出首次响应 ( 如屏幕显示 ) 的时间 -- 分时系统面向用户的调度性能准则 2 截止时间 : 开始截止时间和完成截止时间 - - 实时系统, 与周转时间有些相似优先级 : 可以使关键任务达到更好的指标公平性 : 不因作业或进程本身的特性而使上述指标过分恶化, 如长作业等待很长时间 8

9 面向系统的调度性能准则吞吐量 : 单位时间内所完成的作业数, 跟作业本身特性和调度算法都有关系 - - 批处理系统平均周转时间不是吞吐量的倒数, 因为并发执行的作业在时间上可以重叠如 : 在 2 小时内完成 4 个作业, 而平均周转时间是 1 小时, 则吞吐量是 2 个作业 / 小时处理机利用率 :-- 大中型主机各种资源的均衡利用 : 如 CPU 繁忙的作业和 I/O 繁忙 ( 指次数多, 每次时间短 ) 的作业搭配 -- 大中型主机调度算法本身的调度性能准则易于实现执行开销比 9

10 调度的类型与模型常见的调度算法实时系统调度多处理机调度内容提要调度算法通常将作业或进程归入各种就绪或阻塞队列有的算法适用于作业调度, 有的算法适用于进程调度, 有的两者都适应 10

11 不可抢占式方式一旦处理器分配给一个进程, 它就一直占用处理器, 直到该进程自己因调用原语操作或等待 I/O 等原因而进入阻塞状态, 或时间片用完时才让出处理器, 重新进行抢占式方式就绪队列中一旦有优先级高于当前运行进程优先级的进程存在时, 便立即进行进程调度, 把处理器转给优先级高的进程先来先服务 (FCFS, First Come First Served) 这是最简单的调度算法, 按先后顺序调度按照作业提交或进程变为就绪状态的先后次序, 分派 CPU; 当前作业或进程占用 CPU, 直到执行完或阻塞, 才出让 CPU( 非抢占方式 ) 在作业或进程唤醒后 ( 如 I/O 完成 ), 并不立即恢复执行, 通常等到当前作业或进程出让 CPU 最简单的算法 FCFS 的特点比较有利于长作业, 而不利于短作业有利于 CPU 繁忙的作业, 不利于 I/O 繁忙的作业 11

12 短作业优先 (SJF, Shortest Job First) 又称为短进程优先 SPN(Shortest Process Next); 这是对 FCFS 算法的改进, 其目标是减少平均周转时间对预计执行时间短的作业 ( 进程 ) 优先分派处理机通常后来的短作业不抢先正在执行的作业 SJF 的特点优点 : 比 FCFS 改善平均周转时间和平均带权周转时间, 缩短作业的等待时间 ; 提高系统的吞吐量 ; 缺点 : 对长作业非常不利, 可能长时间得不到执行 ; 未能依据作业的紧迫程度来划分执行的优先级 ; 难以准确估计作业 ( 进程 ) 的执行时间, 从而影响调度性能 12

13 时间片轮转 (Round Robin) 算法前两种算法主要用于宏观调度, 本算法主要用于微观调度, 设计目标是提高资源利用率其基本思路是通过时间片轮转, 提高进程并发性和响应时间特性, 从而提高资源利用率 ; 时间片轮转算法将系统中所有的就绪进程按照 FCFS 原则, 排成一个队列每次调度时将 CPU 分派给队首进程, 让其执行一个时间片时间片的长度从几个 ms 到几百 ms 在一个时间片结束时, 发生时钟中断调度程序据此暂停当前进程的执行, 将其送到就绪队列的末尾, 并通过上下文切换执行当前的队首进程进程可以未使用完一个时间片, 就出让 CPU( 如阻塞 ) 13

14 时间片长度的确定时间片长度变化的影响过长 -> 退化为 FCFS 算法, 进程在一个时间片内都执行完, 响应时间长过短 -> 用户的一次请求需要多个时间片才能处理完, 上下文切换次数增加, 响应时间长系统的响应时间 :T( 响应时间 )=N( 进程数目 )*q( 时间片 ) 就绪进程的数目 : 数目越多, 时间片越小系统的处理能力 : 应当使用户输入通常在一个时间片内能处理完, 否则使响应时间, 平均周转时间和平均带权周转时间延长 A 0 4 B 1 3 C 2 5 D 3 2 E

15 作业到来顺序作业长短 A B C D E 先来先服务 A B C D E 平均周转时间 = 9 带权平均周转时间 =2.8 A B C D E 平均周转时间 = 8 带权平均周转时间 =2.1 最短作业优先作业到来顺序作业长短 A B C D E 时间片轮转法 A B C D E 时间片 =1 A B C D E 时间片 =4 15

16 优先级算法 (Priority Scheduling) 本算法是平衡各进程对响应时间的要求适用于作业调度和进程调度, 可分成抢先式和非抢先式 ; 静态优先级创建进程时就确定, 直到进程终止前都不改变通常是一个整数依据 : 进程类型 ( 系统进程优先级较高 ) 对资源的需求 ( 对 CPU 和内存需求较少的进程, 优先级较高 ) 用户要求 ( 紧迫程度和付费多少 ) 16

17 动态优先级在创建进程时赋予的优先级, 在进程运行过程中可以自动改变, 以便获得更好的调度性能如 : 在就绪队列中, 等待时间延长则优先级提高, 从而使优先级较低的进程在等待足够的时间后, 其优先级提高到可被调度执行 ; 进程每执行一个时间片, 就降低其优先级, 从而一个进程持续执行时, 其优先级降低到出让 CPU 高响应比优先调度算法响应比 =( 执行时间 + 等待时间 )/ 执行时间等待时间相同, 短作业优先执行时间相同, 优先权决定于等待时间,(FCFS) 长作业等待时间长, 优先权提高 17

18 多级队列算法 (Multiple-level Queue) 本算法引入多个就绪队列, 通过各队列的区别对待, 达到一个综合的调度目标 ; 根据作业或进程的性质或类型的不同, 将就绪队列再分为若干个子队列每个作业固定归入一个队列不同队列可有不同的优先级时间片长度调度策略等 ; 在运行过程中还可改变进程所在队列如 : 系统进程用户交互进程批处理进程等 18

19 多级反馈队列算法 (Round Robin with Multiple Feedback) 多级反馈队列算法 : 时间片轮转算法和优先级算法的综合和发展优点 : 为提高系统吞吐量和缩短平均周转时间而照顾短进程为获得较好的 I/O 设备利用率和缩短响应时间而照顾 I/O 型进程不必估计进程的执行时间, 动态调节多级反馈队列算法设置多个就绪队列, 分别赋予不同的优先级, 如逐级降低, 队列 1 的优先级最高每个队列执行时间片的长度也不同, 规定优先级越低则时间片越长, 如逐级加倍新进程进入内存后, 先投入队列 1 的末尾, 按 FCFS 算法调度 ; 若按队列 1 一个时间片未能执行完, 则降低投入到队列 2 的末尾, 同样按 FCFS 算法调度 ; 如此下去, 降低到最后的队列, 则按时间片轮转算法调度直到完成仅当较高优先级的队列为空, 才调度较低优先级的队列中的进程执行如果进程执行时有新进程进入较高优先级的队列, 则抢先执行新进程, 并把被抢先的进程投入原队列的末尾 19

20 几点说明 I/O 型进程 : 让其进入最高优先级队列, 以及时响应 I/O 交互通常执行一个小时间片, 要求可处理完一次 I/O 请求的数据, 然后转入到阻塞队列计算型进程 : 每次都执行完时间片, 进入更低级队列最终采用最大时间片来执行, 减少调度次数 I/O 次数不多, 而主要是 CPU 处理的进程在 I/O 完成后, 放回优先 I/O 请求时离开的队列, 以免每次都回到最高优先级队列后再逐次下降为适应一个进程在不同时间段的运行特点,I/O 完成时, 提高优先级 ; 时间片用完时, 降低优先级 ; 20

21 调度算法性能分析调度算法的性能通常是通过实验或计算得到的 FCFS, Round Robin, 响应比周转时间长作业时 :T(FCFS) < T( 响应比 ) < T(RR)( 运行时间是主要因素 ) 短作业时 :T(RR) < T( 响应比 ) < T(FCFS)( 等待时间是主要因素 ) 线程调度 21

22 调度的类型与模型常见的调度算法实时系统调度多处理机调度内容提要实时调度要求更详细的调度信息 : 如, 就绪时间开始或完成截止时间处理时间资源要求绝对或相对优先级 ( 硬实时或软实时 ) 采用抢先式调度快速中断响应, 在中断处理时 ( 硬件 ) 关中断的时间尽量短快速任务分派相应地采用较小的调度单位 ( 如线程 ) 22

23 实时调度算法时间片轮转单调速率调度 RMS:Rate Monotonic Scheduling m Ci 1 / m 可调度条件 m(2 1) i 1 Pi 最早截止时间优先算法 EDF m 可调度条件 Ci 1 P i 1 i C i 是任务 i 的执行时间, P i 是任务 i 的出现周期, m 是任务的个数 Rate-Monotonic Scheduling 任务的周期越小, 其优先级越高, 优先级最高的任务最先被调度如果两个任务的优先级一样, 当调度它们时,RM 算法将随机选择一个调度静态抢先式调度 23

任务 Ji 起始时间 Si 执行时间 Ci 周期 Pi 截止时间 Di J1 0 1

24 任务 Ji 起始时间 Si 执行时间 Ci 周期 Pi 截止时间 Di J J J Earliest Deadline First 任务的绝对截止时间越早, 其优先级越高, 优先级最高的任务最先被调度如果两个任务的优先级一样, 当调度它们时,EDF 算法将随机选择一个调度动态抢先式调度 24

25 任务 Ji 起始时间 Si 执行时间 Ci 周期 Pi 截止时间 Di J J EDF RMS 调度的类型与模型常见的调度算法实时系统调度多处理机调度内容提要 25

26 多处理机调度与单处理机调度的区别 : 注重整体运行效率 ( 而不是个别处理机的利用率 ) 更多样的调度算法多处理机访问 OS 数据结构时的互斥 ( 对于共享内存系统 ) 调度单位广泛采用线程对称式多处理系统 (SMP) 按控制方式,SMP 调度算法可分为集中控制和分散控制集中控制 : 静态和动态调度分散控制 : 自调度 26

27 非对称式多处理系统 (ASMP) 主 - 从处理机系统, 由主处理机管理一个公共就绪队列, 并分派进程给从处理机执行各个处理机有固定分工, 如执行 OS 的系统功能,I/O 处理, 应用程序 OS 的核心驻留在主处理机, 进程调度由主机执行静态分配 (static assignment): 每个 CPU 设立一个就绪队列, 进程从开始执行到完成, 都在同一个 CPU 上优点 : 调度算法开销小缺点 : 容易出现忙闲不均动态分配 (dynamic assignment): 各个 CPU 采用一个公共就绪队列, 队首进程每次分派到当前空闲的 CPU 上执行 27

28 自调度 (self-scheduling): 各个 CPU 采用一个公共就绪队列, 每个处理机都可以从队列中选择适当进程来执行需要对就绪队列的数据结构进行互斥访问控制是最常用的算法, 实现时易于移植采用单处理机的调度技术一种变形 :Mach OS 中局部和全局就绪队列相结合, 其中局部就绪队列中的线程优先调度瓶颈问题自调度的问题各处理机共享就绪队列低效问题被阻塞的进程重新运行时不一定仍在阻塞前的处理机上运行, 那么高速缓存中的内容需要重置线程切换问题由于合作中的几个线程没有同时运行而受阻, 进而被切换下来 28

29 成组调度 (gang scheduling) 将一个进程中的一组线程, 每次分派时同时到一组处理机上执行, 在剥夺处理机时也同时对这一组线程进行优点通常这样的一组线程在应用逻辑上相互合作, 成组调度提高了这些线程的执行并行度, 有利于减少阻塞和加快推进速度, 最终提高系统吞吐量每次调度可以完成多个线程的分派, 在系统内线程总数相同时能够减少调度次数, 从而减少调度算法的开销两种成组调度面向所有程序平分处理机时间面向所有线程平分处理机时间 29

30 专用处理机调度 (dedicated processor assignment) 为进程中的每个线程都固定分配一个 CPU, 直到该线程执行完成缺点 : 线程阻塞时, 造成 CPU 的闲置优点 : 线程执行时不需切换, 相应的开销可以大大减小, 推进速度更快适用场合 :CPU 数量众多的高度并行系统, 单个 CPU 利用率已不太重要传统 UNIX 的进程调度未设置作业调度, 进程调度采用基于时间片的多级反馈队列算法, 进程优先级分为核心优先级和用户优先级 30

31 调度时机调度由 0 号进程完成 ( 始终在核心态执行 ) 时机 : 进程由核心态转入用户态时 : 在每次执行核心代码之后返回用户态之前, 检查各就绪进程的优先级并进行调度如中断进程回到就绪队列进程主动放弃处理机时 : 进程申请系统资源而未得到满足 ( 如 read), 或进行进程间同步而暂停 ( 如 wait 或 pause), 或进程退出 ( 如 exit) 进程进入阻塞队列或 exit 状态调度标志 UNIX System V 中有三个与调度有关的标志 : runrun: 表示要求进行调度, 当发现有就绪进程优先级高于当前进程时, 设置该标识在 wakeup, setrun, setpri( 设置优先级 ) 过程和时钟中断处理例程进行设置 runin: 表示内存中没有适当的进程可以换出或内存无足够空间换入一个外存就绪进程 runout: 表示外存交换区中没有适当的进程可以换入 31

32 用户优先级进程在用户态和核心态的优先级是不同的, 这里说的是用户态进程的优先级它是基于执行时间的动态优先级, 进程优先级可为 0~127 之间的任一整数优先数越大, 优先级越低 0~49 之间的优先级为系统内核保留, 用户态下的进程优先级为 50~127 之间在 UNIX System V 中 : 进程优先数 :P_pri = P_CPU / 2 + PUSER + P_nice + NZERO 系统设置部分 :PUSER 和 NZERO 是基本用户优先数的阈值, 分别为 25 和 20 CPU 使用时间部分 :P_CPU 表示该进程最近一次 CPU 使用时间每次时钟中断则该值加 1( 最多可达 80) 如果时钟中断的周期为 16.6ms, 则每秒钟过后将该值为 60 新创建进程的 P_CPU 值为 0, 因而具有较高的优先级用户设置部分 :P_nice 是用户可以通过系统调用设置的一个优先级偏移值默认为 20 超级用户可以设置其在 0 到 39 之间, 而普通用户只能增大该值 ( 即降低优先级 ) 32

33 核心优先级内核把进程阻塞事件与一个睡眠优先级 (0~49) 联系起来 ; 当进程从阻塞中醒来时, 可及时进行处理核心优先级分为可中断和不可中断两类优先级当一个软中断信号到达时, 若进程正在可中断优先级上阻塞, 则进程立即被唤醒 ; 若正在不可中断优先级上, 则继续阻塞其中 : 不可中断优先级 : 对换, 等待磁盘 I/O, 等待缓冲区, 等待文件索引结点 -- 关键操作, 应该很快完成可中断优先级 : 等待 tty( 虚终端 )I/O, 等待子进程退出调度的实现分三个阶段检查是否作上下文切换 (runrun 标志 ) 和核心是否允许作上下文切换 ( 对核心的各种数据结构的操作都已经完成, 核心处于正确的状态 ) 如果允许作上下文切换, 则保存当前进程的上下文恢复 0 号进程的上下文, 然后执行 0 号进程, 寻找最高优先级的就绪进程, 如果没有这样的进程存在, 则执行 idle 过程如果有这样的进程存在, 则该进程作为当前进程分派处理机, 保存 0 号进程的上下文恢复当前进程的上下文, 执行该进程 33

34 Linux 的调度 Linux 中实现了三种进程调度策略 : SCHED_OTHER 一般分时进程 SCHED_FIFO 先进先出(First In First Out) 的实时进程 SCHED_RR 轮转(Round Robin) 方式执行的实时进程现代操作系统 P424 Linux 并不为这三种调度策略的进程分别设置一个运行队列, 而是通过权重的不同计算以及其他的一些队列操作, 在一个运行队列中实现这三种不同的调度发生进程调度时, 调度程序要在运行队列中选择一个最值得运行的进程来执行, 这个进程便是通过在运行队列中一一比较各个可运行进程的权重来选择的权重越大的进程越优, 而对于相同权重的进程, 在运行队列中的位置越靠前越优 34

35 调度策略为 SCHED_RR 的实时进程, 在分配的时间片到期后, 插入到运行队列的队尾调度策略为 SCHED_FIFO 的进程, 在时间片到期后, 调度程序并不改变该进程在运行队列中的位置 sys_sched_setschedule, sys_sched_setparam, sys_sched_getscheduler, sys_sched_getparam, sys_sched_get_priority_max, sys_sched_get_priority_min 35

36 优先级 priority 进程的优先级反映了进程相对于其他进程的可选择度, 其实就是系统每次允许进程运行的时间子进程继承了父进程的优先级 priority 也可以通过系统调用 sys_setpriority(sys_nice 已被 sys_setpriority 取代 ) 设置系统为每个进程预定的 priority 为 DEF_PRIORITY(include/linux/sched.h), 200ms 相对优先级 rt_priority 对于实时进程, 除了用 priority 来反映其优先级 ( 可执行时间 ) 外, 还有相对优先级用于同类进程之间的比较选择实时进程的 rt_priority 取值 1 ~ 99, 一般进程的 rt_priority 值只能取 0 进程的 rt_priority 可通过 setscheduler 函数而改变 36

37 计数器 counter counter 用以反映进程所剩余的可运行时间, 在进程运行期间, 每次发生时钟中断时, 其值减 1, 直至 0 由于时钟中断为快中断, 在其底半处理过程中, 才刷新当前进程的 counter 值因此, 也可能在发生了好几次时钟中断后才集中进行处理计数器 counter 是衡量一般进程权重的重要指标, 主要因为如下几种事件而改变 : task 0 的 counter 初值为 DEF_PRIORITY, 在执行 sys_idle() 时, 将 counter 值置为 -100 在创建子进程时, 父进程的 counter 变为原值的一半, 并将该值赋予子进程在进程运行期间, 每次发生时钟中断时,counter 值减 1, 直至为 0 若所有的可运行进程的 counter 值都为 0, 则需要为所有的进程都重新赋 counter 值 37

38 权重通过调用函数 goodness 来计算, 对于实时进程, 其权重为 1000+rt_priority; 否则, 权重为 counter 对于当前进程, 可以得到比其他进程稍高的权重, 为 counter+1 这样处理是为了在某个进程与当前进程权重相同时可选择当前进程继续执行, 以减少进程切换的开销小结调度的类型 ( 如调度单位的不同级别, 时间周期, 不同的 OS), 性能准则调度算法 :FCFS, SJF, RR, 多级队列, 优先级, 多级反馈队列调度算法的性能分析 : 周转时间和作业长短的关系实时调度 : 调度算法多处理机调度 : 自调度, 成组调度, 专用处理机调度 38

39 作业 3.1 有 5 个批处理作业 A B C D E, 几乎同时到达, 估计运行时间分别为 (min), 优先级分别为 , 其中 5 为最高优先级假设都是计算型作业, 不考虑其它系统开销若系统采用非剥夺方式使用 CPU, 对于以下调度算法, 计算平均周转时间和平均带权周转时间 : 优先级调度先来先服务 ( 到达顺序 A B C D E) 短作业优先问题? 39

4.process-part3.pptx

4.process-part3.pptx 操作系统 Operation System 四进程管理 : 调度孙海龙 2017 年 4 月 13 日内容提要基本概念设计调度算法要考虑的问题批处理系统的调度算法交互式系统的调度算法实时系统的调度算法多处理机调度 2 2 1 CPU 调度什么是 CPU 调度? CPU 调度的任务是控制协调多个进程对 CPU 的竞争也就是按照一定的策略 ( 调度算法 ), 从就绪队列中选择一个进程,