操作系统之调度算法

适合批处理系统的算法

先来先服务

• 思想非常简单：就是非常公平的概念，先到先进行运行
• 可以用于作业也可以用于进程
• 是非抢占的算法，因为核心思想就是先来先服务，如果可以抢占，那么就破坏了这个规则
• 缺点：它对短作业是不利的
• 是不会有饥饿问题

短作业优先

• 思想：就是将需要服务的最短时间的先运行
• 可以用于作业也可以用于进程
• 可以有非抢占式和抢占式的算法
• 优点是 最短的平均等待时间和平均周转时间
• 缺点是 它不公平的，对短作业有利，对长作业不利
• 会导致饥饿，因为可能会有一直短作业进入，导致长作业饿死

高响应比优先

• 先来新服务对短作业不友好，短作业优先对长作业不友好，还可能产生饥饿问题
• 高响应就是为了接近这两种问题

• 思想：要综合考虑作业/进程的等待时间和要求时间服务的时间 响应比=等待时间+要求服务时间/要求服务时间
• 这种是非抢占式的算法
• 对于长作业，如果等待的时间过长 那么响应比对应会增长
• 对于短作业，因为要求时间短，当等待时间一样的时候，短作业就会优先

总结

适合交互式系统的调度算法

时间片轮转

• 伴随着分时操作系统的出现而出现 ，其思想是公平的，轮流的为各个进程服务，让每个进程在一定的时间间隔内都可以得到响应
• 只能用于进程调度，只有作业被放入了内存建立了相应的进程后，才能被分配机分配
• 是抢占式的算法，因为如果进程未能在时间片内运行完，将被强行剥夺处理机，由时钟装载发出时钟中断来通知CPU时间片已经到了
• 优点：公平 响应快 适合分时操作系统 有交互能力
• 不会导致饥饿问题

关于时间片大小的设置

• 如果时间片太大了，使得每个进程都可以在一个时间片内完成，那么就会退化成了先来先服务的调度算法
• 但是如果时间片太小了，那么进程会调度的很频繁，切换是有时间代价的
• 一般来说，设计时间片是要让切换进程的开销占比不超过1%

优先级调度算法

• 因为分时的方式处理不了紧急事件，用优先级来区分进程/作业的运行的顺序
• 调度的时候选择优先级最高的作业
• 可用于作业或者进程
• 抢占式和非抢占式都有
• 优点就是可以区分紧急程度，适用于实时操作系统
• 可能会造成饥饿问题

关于优先级的设置

• 就绪队列未必只有一个，可以按照不同的优先级来组织，可以将优先级高的进程排在更靠近队头的位置
• 根据我们的优先级是否能动态的改变 将优先级变成静态优先级和动态优先级
  • 静态的意思 就是在创建进程的时候确定，之后一直不变
• 如何设置优先级
  • 系统进程优先级高于用户进程
  • 前台进程优先级高于后台进程
  • 操作系统更偏好I/O型进程（对应的是计算型进程）
    • I/O设备和CPU是可以并行的工作，优先让I/O繁忙运行，是为了尽可能让I/O设备尽量的投入工作调度算法

多级反馈队列调度算法

• 这个算法就是想集合上述算法的优点
  • 先来先服务是公平
  • 短作业的优点是尽快处理短作业 平均等待/周转时间等参数很优先
  • 时间轮转是为了让各个进程得到及时的响应
  • 优先级调度是为了灵活调整各种进程服务的几乎

• 思想就是对其他算法的折中
• 用于进程调度
• 原理
  • 设置多级就绪队列，各队列优先级从高到低 时间片从小到大
  • 新进程先进入第一级队列，先按照先来先服务的等待被分配时间片，若使用了完了线程时间片，进程还没有执行完毕，就会进入下一级队列的队尾，如果是最下级的队列，那么就重新放入队尾
  • 如果k层的执行完毕，才会去执行k+1层的队头的进程
• 抢占式的算法，如果一个进程在执行，如果上1到k-1队列进入了进程，那么此时新进程会抢占CPU,被抢占的重新回到K层的队尾