处理机调度
- 处理机调度
- 三个层次
-
- 高级调度
- 中级调度
- 低级调度
- 三层调度联系, 对比
- 补充知识
-
- 进程的挂起态
- 七状态模型
基本概念
按照某种算法选择一个处理机分配给他
有一堆任务要处理的时候, 由于当前的资源有限, 没有办法同时处理, 需要确定某种规则来决定处理的顺序, 这就是调度研究的问题
高级调度(作业调度)
作业: 某一个具体的任务
用户向系统提交了一个作业=>用户让操作系统启动一个程序, 来处理一个任务
高级调度(作业调度): 操作系统按照一定的原则从外存中作业后备列表中选一个作业存入内存, 创建进程, 每个作业调入一次, 掉出一次, 分别创建撤销PCB, 是对请求任务的处理
低级调度(进程调度/处理机调度)
按照某一种策略从就绪队列选一个进程, 分配处理机给他, 是最基本的调度, 一般的操作系统都需要进程调度, 进程频率很高, 一般几十毫秒一次, 是对进程的管理
中级调度(内存调度)
内存不够的时候, 将空闲的进程调入外存, 空闲的时候再重新调回内存, 暂时调出去的进程称为挂起状态, 被挂起的PCB称为挂起队列
按照某种决策决定哪个处于挂起状态的进程重新调入内存
频率比高级调度要高
七状态模型
暂时挂起到内存的进程状态为挂起状态, 挂起状态又可以细分为就绪挂起, 阻塞挂起
两种的挂起状态可能被分为两种或多种队列
进程调度
- 进程调度
-
- 时机
-
- 什么时候需要
- 什么时候不能进行
- 切换与过程
-
- 狭义的”调度”与”切换”的区别
- 进程切换的过程需要什么
- 方式
-
- 非剥夺调度方式(非抢占式)
- 剥夺调度方式(抢占式)
时机
- 主动放弃处理
- 进程正常终止
- 进程过程中发生异常终止
- 进程主动请求阻塞(等待I/O)
- 被动放弃
- 分配的时间片用完
- 有更紧急的事件需要处理
- 有优先级更高的进程进入就绪队列
不能的情况
进程在操作系统内核程序临界区不能进行调度与切换
[×]处于临界区的时候不能进行处理机调度
临界资源: 一个时间段只允许一个进程使用资源, 各个进程需要互斥的访问临界资源
临界区: 访问临时资源的那段代码
内核程序临界: 访问某种内核数据结构
不可以进行进程调度
可以进行进程调度
调度方式
非剥夺调度方式: 有的系统只允许进程主动放弃处理机
实现简单开销小, 但是不能处理紧急任务, 使用于早期的批处理系统
剥夺调度方式: 有的系统进程可以主动的放弃处理机, 当有更紧急的任务需要处理的时候也会强制剥夺
实现优先处理紧急任务, 也可以实现进程按照时间片轮流执行的功能(时钟中断), 适合分时操作系统, 实时操作系统
进程切换与调度区别
进程切换完成
- 保存进程的各种数据
- 对新进程的数据进行恢复
进程切换是有代价的, 不能切换的过于频繁, 否则会导致操作系统效率低
调度器和处理程序
调度器
完成程序在就绪态和运行态之间进行转换
让谁运行=> 调度算法
运行多长时间=> 时间片大小
时机
创建新的进程
进程退出
运行阻塞
I/O中断发生(可能唤醒某些阻塞的程序)
- 非抢占式调度策略: 只有运行程序阻塞或者退出的时候才会触发调度程序
- 抢占式调度策略: 每个或者k个时钟中断会触发调度工作
不支持内核级线程的操作系统, 调度程序处理的对象是进程
支持内核级线程的操作系统, 调度的处理对象是内核级线程
闲逛进程
调度程序的备胎, 没有其它进程的时候闲逛进程运行(idle)
优先级最低, 0地址指令, 占一个完整的指令周期(指令周期末尾例行检查中断)
能耗低
调度算法的[请假指标
- CPU利用率: CPU忙碌时间占总时间的比例
某种设备的利用率
- 系统吞吐量
用尽可能少的事件完成尽可能多的作业
- 周转时间
作业提交到作业完成所需要的时间
周转时间 = 作业完成时间 - 作业提交时间
平均周转时间 = 各作业周转时间之和/作业数
- 带权周转时间(是一个比例)
带权周转时间 = 作业周转时间/作业实际的运行时间 = (作业完成时间-作业提交时间)作业实际运行时间
- 等待时间
进程/作业处于等待处理机状态的时间之和
对于进程来说等待I/O设备完成期间其实也是在被服务, 不计入等待时间
要加上在外存后备队列中等待的时间和建立进程之后的等待时间
- 响应时间
用户提交请求到首次产生响应的时间
调度算法
-
先来先服务
-
短作业优先
-
高响应比优先
-
时间片轮转调度算法
-
优先级调度算法
-
多级反馈队列调度算法
思路
- 算法思想
- 算法规则
- 调度算法使用的于作业调度还是进程调度
- 抢占式?非抢占式?
- 是否会导致饥饿(进程/作业长时间得不到服务)
先到先服务
FCFS, first come first serve
按照到来的顺序
短作业优先
SJF Shortest Job First
每次调度的时候选择当时已经到达且运行时间最短的作业/进程(非抢占式的)
抢占式的(SRTN), 最短剩余时间优先算法, 就绪队列改变的时候, 新到达的进程运行时间与当前进程的剩余时间进行比较, 一个进程完成时也会践行调度
题目中如果没有特殊说明, 默认是非抢占式的
高响应比优先
综合考虑作业进程的等待时间和要求服务的时间
根据响应比 = (等待时间 + 要求服务的时间)/要求服务的时间
进程主动放弃CPU的时候才会进行调度
总结
主要关心用户的公平性, 平均运转周期, 平均等待时间, 评价系统整体性能的指标, 但是不关心响应时间, 也不处理任务的紧急程度, 对用户来说交互性差, 一般适用于早期的批处理系统
FCFS经常结合其他算法
时间片轮转调度算法(RR)
公平轮流为各个进程服务, 在一定时间内所有进程都可以得到响应
按照到达的时间轮流运行时间片, 抢占式的算法
常用于分时操作系统, 更注重响应时间, 因此不计算周转时间
默认新到达的进程先进入就绪队列
- 如果时间片比较大会导致退化为先来先服务, 所以不能让太大
- 时间片太小会切换频繁, 导致系统花大量时间进行切换,, 一般占比小于百分之一
优先级调度算法
为每一个任务设置优先级, 根据优先级进行调度
有抢占式也有非抢占式的, 抢占式需要在就绪队列发生变化的时候判断
就绪队列可以有多个, 也可以动态进行排队
优先级是否可以动态改变:
- 静态优先级: 创建以后就不再改变
- 动态优先级: 创建的时候有一个初始值, 之后动态调整
如何设置
通常系统优先级高于用户进程
前台进程高于后台进程
操作系统偏好I/O型进程(I/O繁忙型进程)
I/O设备可以和CPU并行, 优先的话可以让I/O设备尽早的投入工作, 资源利用率提高
相对的是计算型进程(CPU繁忙型进程)
从公平角度来看, 某个进程等待时间长就提高优先级
多级反馈队列调度算法
设置多级就绪队列, 各个队列优先级从高到低, 时间片从大到小, 新到来的进程到大四进入以及队列, 按照FCFS进行调度, 用完时间片进程还未结束进入下一级队列末尾, 已经在最下级就重新放回最下级
第k级为空的时候才会进行k+1级的队列, 被抢占的进程放回原队列的队尾
总结2
更适合交互式操作系统
多级队列调度算法
队列之间可以采取固定优先级, 或时间片划分
也可以给各个优先级划分时间片长度不同
各个队列可以采用不同的调度策略, 系统采取优先级调度, 交互式队列采用RR, 批处理采用FCFS