操作系统3：CPU调度¶
本页统计信息
-
本页约 1600 个字, 预计阅读时间 5 分钟。
-
本页总阅读量次
Chapter5：CPU Schedule¶
5.1 基本概念/标准¶
- 调度的基本概念
-
CPU调度=处理机调度=进程调度
-
进程运行消耗的时间主要分为CPU时间和I/O时间，根据程序运行主要消耗的时间，可以分为CPU型的程序和I/O型的程序
-
三种层级的调度
- 短程调度、中程调度和长程调度，其中CPU主要是短程调度
- 调度发生的时间点：
- 从运行切换到暂停的时候
- 从运行到就绪状态的时候
- 从等待到就绪状态的时候
- 进程终止的时候
-
调度的方式：
- 抢占式：进程一旦被调度了就一直运行，直到完成或者阻塞的时候才让处理机分配给另一个进程
- 非抢占式：程序运行的时候可以基于某种原则，剥夺进程的CPU使用权，分配给别的进程
-
调度程序 Dispatcher
- 需要进行上下文切换，并切换到用户态
-
调度的一系列标准：
-
面向用户的准则和评价方式
- 周转时间：进程从提交到完成所经历的时间，包含平均周转时间，加权周转时间，平均加权周转时间
- 响应时间：从进程提出到首次被响应所需要的时间
- 等待时间：进程在就绪队列中等待的时间总和
- 进程的调度需要满足公平性和一定的优先级
- 面向系统的调度性能准则
- 吞吐量 Throughput：单位时间内完成的进程数，跟进程本身的性质和调度算法都有一定的关系
- 批处理系统：用户交给操作系统一批任务之后就不再和操作系统交互，直到任务全部结束
- CPU利用率：要使得CPU尽可能忙碌
- 各种系统的均衡利用：比如CPU型程序和I/O型程序进行合理搭配，使整个系统的利用率比较高
要做软件开发的人多学一些怎么提高用户体验的内容，虽然这些我们学校都不教。
———— 季江民
- 我们希望的目标：最大的CPU利用率、最大的吞吐量，最短的周转时间、等待时间、响应时间
5.2 调度算法¶
- FCFS算法：First-Come First-Serve先来先服务
- 按照进程的提交顺序来安排CPU的调度，先来的直到结束或者阻塞，才让出CPU(非抢占式的)
- 在进程或者作业完成的时候，并不立即恢复执行，通常等到当前进程让出CPU才进行
- 是最简单的算法
- 优点是：有利于长进程，而不利于短进程，对CPU型进程友好
- SJF算法：Shortest-Job-First Scheduling
- 对预计执行时间最短的作业优先分配CPU使用权
- 事实上是很难实现的，因为难以估计进程运行需要的时间，所以真的操作系统中一般不用这些东西
- 两种变形的形式：
- 最短剩余时间优先 SRT
- 最高相应比优先 HRRN
- 相应比R=(等待时间+要求执行的时间)/要求执行的时间
- 这里JJM上课讲了好几道PPT里面的例题
- 优先级调度：Priority Scheduling
- 小的数字代表高的优先级，该算法就是把CPU分配给了就绪队列中优先级最高的进程
- 静态优先级和动态优先级，静态是一开始就确定优先级，动态优先级是基于某种原则，使得进程的优先级随情况而变
- 一般使用抢占式的调度，优先级高的进程来了直接将CPU使用权从当前进程中剥夺
- 饥饿 Starvation 在使用静态优先级的调度策略时，优先级低的进程可能永远得不到CPU的使用权
- 进程卷起来的后果
- 解决的方法：老化 Aging，随着时间的增加提高进程的优先级——动态优先级的策略
- 时间片轮转调度：
Round Robin(RR) - 算法描述
- 将系统中所有的进程按照FCFS原则排成队列，每次调度将CPU分配给队列顶端的进程，执行一个时间片slice
- 时间片结束的时候，发生时钟中断，然后将该进程移动到队列末尾
- 通过上下文切换，执行当前的队列顶端的进程
- 进程可以不运行完就出让CPU的使用权
- slice的确定：和进程数量有关，数目越多，时间片越短
- n个进程，
time quantum是q，响应时间就是nq
- n个进程，
- 多级队列调度
- 将就绪队列分为若干个子队列，每个进程按照一定方式归入一个队伍，不同的队伍可能有不同的优先级、时间片长度和调度策略：
- 固定优先级调度
- 给定时间片调度
- 多级反馈队列：时间片轮转算法和优先级算法的综合和发展，有点有
- 为提高系统吞吐量和缩短平均周转时间而照顾短进程
- 为获得较好的I/O设备利用率和缩短响应时间而照顾I/O型进程
- 不必估计进程的执行时间，动态调节
5.3这一部分不会考试，上课也就随便讲讲
5.3 Windows中的调度¶
- Windows2000/XP的处理机调度的调度对象是线程，调度算法是多种调度算法的综合体，针对实际系统的需要进行针对性的优化和改进
- 线程都是内核线程，没有用户线程
- 线程有七种状态：初始化、就绪、备用、运行、等待、转换、中止
- 采用动态优先级和抢占式的调度，总是运行优先级最高的线程，同一优先级的按照RR算法进行调度
-
32个用户优先级：其中一半是实时的优先级
-
哪些情况下会提高线程的当前优先级：
- I/O操作完成了
- 信号量或者时间等待结束
- 前台进程中的线程完成了一个等待的操作
- 由于窗口活动而唤醒图形用户接口线程
- 线程处于就绪状态超过一定的时间