<>处理机调度
一、什么是处理机调度 ?
就是从就绪队列中 按照一定的算法选择一个进程 并 将处理机分配给它运行
二、调度的三个层次
1、高级调度 :从外存的后备队列中 挑选 n个作业,为它建立相应的进程 (建立PCB) (无 - > 创建态 - > 就绪态)
高级调度是外存与内存之间的调度,一个作业只能调入一次,调出一次,作业调入时会建立相应的PCB,调出时删除 相应的PCB
2、中级调度: 决定将哪个处于挂起状态的进程重新调入内存 (阻塞挂起 - > 阻塞态)
(为了解决内存不够,处于挂起的进程为被移到外存去)
3、低级调度 : 从就绪队列中,按照一定策略,将处理机分配给他 (就绪态 - > 运行态)
<>进程调度 (低级调度)
一、进程调度的时机
1、什么时候需要进程调度 ?
(1)当前运行的进程主动放弃处理机 ;
(2) 当前运行的进程被动放弃处理机
2、什么时候不能进行进程调度 ?
(1)在处理中断的过程中。 中断的操作过程比较复杂,需要硬件的支持,很难在中断过程钟进行进程的切换
(2)进程在 操作系统内核程序临界区 中 (这个时候切换,可能导致出错)
(3)原语执行过程中。
二、进程调度的方式
(1)非剥夺调度方式 : 只允许进程主动放弃处理机
(2)剥夺调度方式 : 当一个进程正在执行,如果有一个更紧急的进程任务,则立即暂停正在执行的进程,把处理机分配给紧急的进程
三、进程的切换与过程
1、什么是进程切换 ?
进程切换是指一个进程让出处理器,由另外一个进程占用处理机的过程
2、进程切换的过程
(1)对原来进程的各种运行书数据进行保存
(2)对新进程的各种数据恢复
<>调度算法的评价指标
一、CPU利用率计算
二、系统吞吐量的计算
三、周转时间的计算
四、等待时间
五、响应时间
<>调度算法
一、 先来先服务 (FCFS)
(1)算法思想 : 主要是从 “ 公平 ”的角度考虑
(2)算法规则 : 按照作业 / 进程 到达的先后顺序进行服务
(3)用于作业/进程调度:
用于作业调度时,考虑的是哪个作业先到达后备队列中那个 ; 用于进程调度,考虑的是哪个进程先到达 就绪队列
(4)不可以抢占
(5)优点 : 公平,算法实现简单
(6)缺点 : 对长作业有利,多短作业不利
(7)不会导致饥饿
二、短作业优先 SJF
(1)算法思想 : 追求最少的平均等待时间 ,最少的平均周转时间,最少的平均带权周转时间
(2)算法规则 : 最短的作业/进程 优先得到服务
(3)用于作业/进程调度
(4)SJF 和SPF 是非抢占式算法,而最短剩余时间优先算法 是 抢占式的
(5)优点 : 最短的平均等待时间 ,平均周转时间
(6)缺点: 不公平, 对长作业不利
(7)会导致饥饿
三 、高响应比优先 HRRN
(1)算法思想 : 综合考虑作业/进程 等待时间和要求服务时间
(2)算法规则 : 在每次调度的时候 计算各种作业/进程 的响应比,优先选择响应比高的,为它服务
(3)用于作业/进程调度
(4)非抢占式
(5)优点 : 不会导致饥饿,相对公平
四、时间片轮转
(1)算法思想 : 公平轮流的为各个进程服务,让每个进程在一定的时间内都能得到响应
(2)算法规则: 按照进程在就绪队列中的顺序,轮流的各执行一个时间片,如果到时间还没运行完,就剥夺处理机,将进程放回 达就绪队列对尾
(3)用于作业/进程 调度
(4)属于抢占式
(5)优点 : 公平,响应快 , 不会造成饥饿
(6)缺点: 由于高频繁的切换进程 ,会增加开销,而且不区分任务紧急程度
五、优先级调度算法
(1)算法思想 : 按照任务的紧急程度,来决定处理顺序
(2)算法规则 :调度时 选择优先级最高的作业/进程
(3)用于作业/进程 调度
(4)抢占、非抢占都有
(5)适用实时操作系统
(6)缺点: 会造成饥饿
六、多级反馈队列调度算法 (综合起来 最佳)
(1) 算法思想 : 对其他调度算法的折中权衡
(2)算法规则:
1、设置多级就绪队列,各级队列 优先级从高到低,时间片 从小到大
2、新进程到达时 ,先进入第1级队列,按照先来先到原则排队等待 被分配时间片 ;
如果用完时间片,进程还没结束,则进入下一个级别的队列中 ;
如果此时已经是 最下级的队列 ,则重新放回队尾。
3、只有当k 级队列为空 ,k+1 级队列 才能分配到时间片
(3)用于作业/进程调度
(4)属于抢占式 : 当 k 层队列中进程正在运行 ,如果 在 1~ k -1 层队列中进入了新进程, 则新进程会抢占处理机
(5)优点 : 对各类型的进程 相对公平
(6)缺点: 会导致饥饿