没有幻灯片标题

Size: px

Start display at page:

Download "没有幻灯片标题"

羸煤申
5 years ago
Views:

1 1

2 第六章处理机管理 2

3 6.1 处理机的二级调度 3 作业调度 ( 宏观 ): 决定那些程序调入计算机系统进程调度 ( 微观 ): 决定那个 ( 些 ) 进程占用 CPU

4 6.2 作业调度作业状态及转移 4 作业的四种状态 : 1. 提交状态用户将程序和数据提交机计算中心 ; 2. 后备状态将作业录入到后援存储设备 ; 3. 执行状态作业调入计算机系统内存 ; 4. 完成状态作业计算完成的善后处理

5 6.2 作业调度作业状态及转移 5

6 6.2.1 作业调度的功能 6 作业调度的主要任务是完成作业从后备状态到执行状态和从执行状态到完成状态的转变

7 6.2.1 作业调度的功能 7 作业调度功能 : 1. 记录已进入系统的各作业的情况 (JCB,Job Control Block); 2. 按一定的调度算法, 从后备作业中选择一个或几个作业进入内存 ; 3. 为被选中的作业创建进程, 并为其申请系统资源 ; 4. 作业结束后作善后处理

8 6.2.2 作业控制块 (JCB,Job Control Block) 8 每个作业进入系统时由系统为其建立一个作业控制块 JCB ( Job Control Block), 它是存放作业控制和管理信息的数据结构, 主要信息见右图

9 6.2.3 调度性能的衡量 9 作业调度算法规定了从后备作业中选择作业进入系统内存的原则, 这些原则的性能如何, 就是本节所讨论的问题一确定调度算法时应考虑的因素 1. 应与系统的整体设计目标一致 2. 考虑系统中各种资源的负载均匀 3. 保证作业的执行 4. 对一些专用资源的使用特性的考虑

10 6.2.3 调度性能的衡量 10 二调度性能的衡量通常采用平均周转时间和带权平均周转时间作业的周转时间 : t i = t ci -t si t i : 作业周转时间 t ci : 作业完成时间 t si : 作业提交时间

11 6.2.3 调度性能的衡量 11

12 6.2.4 先来先服务调度算法和短作业优先调度算法 12 先来先服务调度算法 : 先来先服务算法是按作业来到的先后次序进行调度的. 调度程序每次选择的作业是等待时间最久的, 而不管作业的运行时间的长短这种调度算法突出的优点是实现简单, 效率软低, 在一些实际的系统和一般应用程序中采用这种算法的较多

13 6.2.4 先来先服务调度算法和短作业优先调度算法 13 短作业优先调度算法 : 短作业优先调度算法考虑作业的运行时间, 每次总是选择一个运行时间最小的作业调入内存 ( 系统 ) 在一般情况下这种调度算法比先来先服务调度算法的效率要高一些实现相对先来先服务调度算法要困难些, 如果作业的到来顺序及运行时间不合适, 会出现饿死现象

14 6.2.4 先来先服务调度算法和短作业优先调度算法 14

15 6.2.5 其它几种调度算法 15 响应比高者优先调度算法 : 先来先服务和短作业优先算法都有其片面性 : 先来先服务调度算法只考虑作业的等待时间, 而忽视了作业的运行时间 ; 短作业优先算法则相反, 只考虑了作业的运行时间, 而忽视了作业黪等待时间 ; 响应比高者优先调度算法是介于这两种算法之间的一种拆衷的算法

16 6.2.5 其它几种调度算法 16

17 6.2.5 其它几种调度算法响应比高者优先调度算法 17 这样算法从理论上讲是比较完备的, 但作业调度程序要统计作业的等待时间, 使用用户的估计的运行时间, 并要作浮点运算 ( 这是系统程序最忌讳的 ) 浪费大量的计算时间, 这是系统程序所不允许的

18 6.2.5 其它几种调度算法 18 优先数调度算法优先数调度算法是终合考虑各方面的因素 ( 作业等待时间运行时间缓急程度, 系统资源使用等 ), 给每个作业设置一个优先数, 调度程序总是选择一个优先数最大 ( 或者最小 ) 的作业调入 ( 系统 ) 内存这种算法实现的困难在于如何终合考虑, 这些因素之间的关系怎样处理

19 6.2.5 其它几种调度算法 19 均衡调度算法均衡调度算法就是一种更为理想化的调度算法, 如何实现就更困难, 并且算法本身的开销有时会远选大于先来先服务和小作业优先调度算法的不足, 这也是这两种算法被众多系统采用的最根本的原因

20 6.3 进程调度调度 / 分派结构 20 调度 : 组织和维护就绪进程队列 ( 包括确定调度算法 ) 分派 : 当处理机空闲时, 从就绪进程中选择一个进程占用 CPU

21 6.3.2 进程调度的功能记录和保持系统中所有进程的有关情况和状态特征进程调度的信息记录在 PCB 中, 包括进程的状态调度优先级 ( 优先数 ) 就绪进程队列等

22 6.3.2 进程调度的功能决定分配 ( 处理机 ) 策略先来先服务优先数调度策略调度策略的不同, 组织就绪进程队列的方式

23 6.3.2 进程调度的功能实施处理机的分配调度算法的选择 ( 调度算法 ) 调度时机的选择 ( 调度时机 ) 实施进程调度 ( 调度程序 )

24 6.3.2 进程调度的功能 24 调度时机 (UNIX 系统中 ): 1. 进程自动放弃处理机当进程进入睡眠状态时 sleep( ) 在进程进入暂停状态时 stop( ) 进程进入僵死状态时 exit( )

25 6.3.2 进程调度的功能强迫调度保护现场形成调用中断处理程序的参数调具体中断处理程序防止优先级反转, 强迫调度用户态? Y runrun > 0 N N 中断返回 Y 处理机调度 swtch()

26 6.3.2 进程调度的功能 26 runrun 标志大于 0 是说明系统中处于就绪状态的进程的优先级高于现运行进程的优先级, 这时要进行强迫调度两种可能 : 睡眠进程唤醒后 ; 重新计算进程的优先数后 ( 包括当一个进程占用一段时间的 CPU 后, 它的优先级要降低 )

27 6.3.2 进程调度的功能 27 实施进程调度的程序称为进程调度程序, 或称调度程序, 在通常的操作系统原理中, 该程序属于系统进程的执行程序, 有的操作系统是把进程调度程序作一个特别的处理在 UNIX 系统中, 进程调度程序 swtch( ) 分属个不同的进程, 即调用 swtch( ) 的进程让出处理机的进程 ) 0 进程被调度到的进程

28 6.3.3 调度方式 28 定义 : 若一个进程正在处理机上运行, 若有一个更为紧迫的进程来到, 系统的处理方式 2 种调度方式 (1) 非剥夺方式 ( 不可抢先 ): 进程已执行, 若一个更为紧迫的进程来到, 必须该进程执行完或时间片到, 才让更紧迫的进程执行 (2) 可剥夺方式 ( 可抢先 ): 有更紧迫的进程到来,, 中止当前进程的执行, 立即让更紧迫的进程执行

29 6.3.3 调度方式 29 问 : 什么情况下可剥夺, 一般来讲总是就绪队列中优先级最高的进程占有 CPU? 在此进程运行期间, 有一个更高优先级的进程被唤醒进入就绪队列开销 : 进程的上下文切换, 处理机分派好处 : 高优先级进程尽快投入运行实时 OS 肯定支持可剥夺方式

30 6.3.4 调度用的进程状态变迁图 30 在这个图中新创建的进程进入低优就绪状态, 一个运行进程因时间片到 ( 实际上是计算量大的进程 ) 而转换成低优就绪 ; 进程因等待 I/O 完成而转换高优就绪.

31 6.3.4 调度用的进程状态变迁图 31 调度程序首先看高优就绪进程队列是否为空, 若不为空, 则从高优就绪进程中选择一个进程占用 CPU, 否则, 从低优就绪队列中选择这种调度效果是能充分地利用系统资源为什么? UNIX 系统的进程调度状态变迁图, 与前一种调度变迁图有着异曲同功的效果

32 6.3.5 进程优先数调度算法 32 优先数调度算法赋予每个进程一个优先数, 在处理机空闲时, 进程调度程序就从就绪进程中选择一个优先数最大 ( 或者最小 ) 的进程占用 CPU

33 6.3.5 进程优先数调度算法 33 如何确定进程的优先数优先数是固定的, 还是随着该进程运行的情况的变化而变化

34 6.3.5 进程优先数调度算法 34 静态优先数进程的优先数在进程创建时确定后就不再变化进程优先数的确定 : 系统确定 ( 运行时间使用资源, 进程的类型 ) 用户确定 ( 紧迫程度, 计费有关 ) 系统与用户结合 ( 用户可以为本用户的进程设置优先数, 但不是作调度用, 系统还要根据系统情况把用户设置的进程优先数作为确定进程优先数的一个参数 )

35 6.3.5 进程优先数调度算法 35 动态进程优先数系统在运行的过程中, 根据系统的设计目标, 不断地调整进程的优先数, 这种方法的优点是能比较客观地反映进程的实际情况和保证达到系统设计目标

36 6.3.6 循环轮转调度 36 循环轮转调度实际上是一种先来先服务算法的调度算法把系统的响应时间分成若干时间片进程被调度到后, 占用一个时间片多个进程循环轮转占用 CPU

37 6.3.6 循环轮转调度 37

38 6.3.6 循环轮转调度 38 评价 : 优点是实现简单系统开销小缺点是不灵活, 当系统中进程较少时, 系统开销变大

39 6.3.6 循环轮转调度 39 二可变时间片轮转调度为了克服前种调度算法的缺点, 人们设计出一种可变时间片的调度算法其思想是 : 时间片的大小是可变的, 系统可根据系统中当前的进程数来确定时间片的大小

40 6.3.6 循环轮转调度 40 与时间片大小有关的因素 : 系统响应时间就绪进程个数 CPU 能力时间片长度变化的影响过长 -> 退化为 FCFS 算法, 进程在一个时间片内都执行完, 响应时间长过短 -> 用户的一次请求需要多个时间片才能处理完, 上下文切换次数增加, 响应时间长

41 6.3.6 循环轮转调度 41 多队列反馈调度算法

42 6.4. UNIX 进程调度 UNIX 调度算法 42 一调度算法 UNIX 系统采用优先数调度算法进程有一个进程优先数 p_pri p_pri 取值范围是 -127~127, 其值越小, 进程的优先级越高

43 6.4.1 UNIX 调度算法 43 优先数的确定 1. 系统设置在 sleep() 中设置将要进入睡眠状态进程的优先数, 当该进程被唤醒后, 就以系统给它设置的优先数去参与处理机的竟争

44 6.4.1 UNIX 调度算法 44 进程进入睡眠状态 0# 进程 (-100 优先数 ); 资源请求得不到满足的进程, 磁盘 (-80), 打印机 (-20), ; 等待块设备 I/O 完成的进程 (-50); 等待字符设备 I/O 完成的进程 (0~20); 所有处于用户态运行进程同步 ( 一般情况下为大于 100)

45 6.4.1 UNIX 调度算法 45 目的使系统资源得到充分的利用, 换言之, 是为了提高系统资源的使用效率?!

46 6.4.1 UNIX 调度算法优先数的计算 (1) 计算公式 : p_pri = min{127, (p_cpu/16+p_nice+puser)} 其中 : p_cpu 进程占用 CPU 的程度 p_nice 用户通过系统调用 nice(priority) 设置的进程优先数 PUSER 常数, 其值为 100

47 6.4.1 UNIX 调度算法 47

48 6.4.1 UNIX 调度算法 48 UNIX 系统的设计者采用了一个巧妙的方法, 既避免了繁杂的统计工作, 也不需做浮点运行算 ( 这就是我们要学习的工程能力, 或称分析问题和解决问题的能力, 学会和记往一两个科学的定理和公式并不难, 难的是怎样将这些普遍的理论用于实际的工程之中,UNIX 系统中有很多值得我们学习的地方, 对 p_cpu 的处理就是其中之一, 这里并不要求把 UNIX 中的 p_cpu 的处理完全记住, 而是学会分析问题和解决问题的方法 )

49 6.4.1 UNIX 调度算法 49 UINX 系统中对 p_cpu 的处理 : 每个时钟中断当前占用处理机的进程的 p_cpu++; 每秒钟 ( 时钟中断 )( 对所有进程 ): if(p_cpu-schmag < 0 ) p_cpu = 0; 其中 :SCHMAG 调度魔数 10 在计算 p_pri 的公式中,PUSER 是个常数, 由于用户不可能频繁地设置进程的优先数, 所以 p_nice 实际上也是个常数, 那么决定 p_pri 的实际上就是 p_cpu 根据 UNIX 系统与调度算法可得出如下的一个负反馈的过程, 从这个过程中可看出什么?

50 6.4 UNIX 系统的进程调度 UNIX 调度算法 50 这种负反馈的效果使得系统中在用户态下运行的进程能均衡地得到处理机, 达到 UNIX 系统的设计目标 (UNIX 系统什么设计目标?)

51 6.4 UNIX 系统的进程调度 UNIX 调度算法 51 (3) 计算优先数的时机在 UNIX 系统中什么时候计算进程的优先数? 计算哪些进程的优先数? 会不会改变系统设置的进程的优先数?

52 6.4.2 UNIX 调度算法 52 计算进程优先数的时机 : A. 在时钟中断处理程序中, 每秒末计算满足下面条件进程的优先数 : p_pri > PUSER B. 现运行进程在自陷处理程序 trap( ) 末尾重新计算本进程的优先数. 目的 : 调用 nice() 设置的本进程的优先数 p_nice 的改变反映到 p_pri 中去 ;

53 6.4.2 UNIX 调度时机 53 C. 现运行进程在执行时钟中断处理程序时, 若发现中断前为用户态, 则每隔 1 秒钟重新计算本进程的优先数因为现运行进程已经占用了一些 CPU 的时间, 要反映到 p_pri 中去

54 6.4.1 UNIX 调度算法 54 调整进程优先数都没有修改系统设置的进程优先数, 从而保证了处于核心态的进能尽快地得到 CPU, 使得系统资源 ( 设备 ) 能得到充分地利用, 提高了系统资源的使用效率 ; 计算进程的优先数又使得系统中所有处于用户态的进程能较均衡地占用 CPU, 保证了各用户终端的响应时间, 实现了分时操作系统的特性

55 6.4.2 UNIX 调度时机 55 调度时机 (UNIX 系统中 ): 1) 进程自动放弃处理机在进程进入高低优先级睡眠状态时 ( 在 sleep() 程序中 ); 在进程进入暂停状态时 ( 在 stop() 程序中 ); 进程进入僵死状态时 ( 在 exit() 程序中 );

56 6.4.2 UNIX 调度时机 56 2) 强迫调度在中断自陷总控程序中, 当先前态是用户态, 且 runrun 标志大于 0, 则进行强迫调度, 强行剥夺现运行进程的处理机, 转进程调度程序

57 6.4.2 UNIX 调度时机 57 runrun 标志大于 0 是说明系统中处于就绪状态的进程的优先级高于现运行进程的优先级, 这时要进行强迫调度两种可能 : 睡眠进程唤醒后 ; 重新计算进程的优先数后 ( 包括当一个进程占用一段时间的 CPU 后, 它的优先级要降低 )

58 6.4.3 UNIX 系统调度程序 58 UNIX 系统中的进程调度程序是 swtch, 所以, 在绝大多数关于 UNIX 系统的文献中称为进程切换程序

59 6.4.3 UNIX 调度程序 59 UNIX 系统的进程调度程序有以下特点 : 1.swtch() 程序分属三个不同的进程 : 调用它的程序 ( 即将让出处理机的进程 ) 0 号进程被选中的进程 2. 调度程序中属于 0 号进程的那段程序是强制启动执行的 ( 可能是睡眠状态 ), 这一点非常特别, 在操作系统中, 仅此一例

Microsoft PowerPoint - Chapter3_2_Scheduling.pptx

Microsoft PowerPoint - Chapter3_2_Scheduling.pptx 操作系统 2014 春第三章进程机制与并发程序设计 - 处理机调度授课人 : 孙海龙 2014 年 3 月 19 日调度的类型与模型常见的调度算法实时系统调度多处理机调度内容提要 1 要解决的问题 WHAT: 按什么原则分配 CPU 进程调度算法 WHEN: 何时分配 CPU 进程调度的时机 HOW: 如何分配 CPU CPU 切换过程 ( 进程的上下文切换 ) 处理机调度调度的类型与模型