Skip to content

Latest commit

 

History

History
423 lines (254 loc) · 16.3 KB

06-1-spoc-discussion.md

File metadata and controls

423 lines (254 loc) · 16.3 KB
Raw

lec15: 调度算法概念 spoc 思考题

  • 有"spoc"标记的题是要求拿清华学分的同学要在实体课上完成，并按时提交到学生对应的ucore_code和os_exercises的git repo上。

视频相关思考题

15.1 处理机调度概念

  1. 处理机调度的功能是什么？

选线程：从就绪队列中挑选下一个占用CPU运行的线程

选CPU：从多个可用CPU中挑选就绪线程可使用的CPU资源

  1. 在什么时候可以进行处理机调度？

调度时机的所有可能：

占用CPU运行的线程的主动放弃（退出、等待）

当前线程被抢先（时间片用完、高优先级线程就绪）

  1. 当操作系统的处理机调度导致线程切换时，暂停线程的当前指令指针可能在什么位置？用户态代码或内核代码？给出理由。

系统调用返回时可能出现线程切换

15.2 调度准则

  1. 处理机的使用模式有什么特征？

CPU与I/O交替使用；

每次占用CPU执行指令的时间长度分布多数在10ms以内；

  1. 处理机调度的目标是什么？

CPU利用率（CPU使用率、吞吐率、周转时间、等待时间）

用户感受（周转时间、等待时间、响应时间、响应时间的方差）

公平性（CPU时间分配公平性）

  1. 尝试在ucore上写一个外排序程序，然后分析它的执行时间分布统计（每次切换后开始执行时间和放弃CPU的时间、当前用户和内核栈信息）。

  2. 在Linux上有一个应用程序time，可以统计应用程序的执行时间信息。请分析它是如何统计进程执行时间信息的。如可能，请在ucore上实现相同功能的应用程序。下面是可能的参考。

  3. 尝试获取一个操作系统的调度算法的性能统计数据（CPU使用率、进程执行）。

15.3 先来先服务、短进程优先和最高响应比优先调度算法

  1. 尝试描述下列处理机调度算法的工作原理和算法优缺点。
    • 先来先服务算法（FCFC、FIFO）
    • 短进程优先算法（SPN、SJF）
    • 最高响应比优先算法（HRRN）

就绪队列的排队依据：到达时间、进程预期执行时间、按响应比R=(w+s)/s

算法特征：平均等待时间、等待时间方差、资源利用率

  1. 为什么短进程优先算法的平均周转时间最优？

可以证明知进程优先算法的调度顺序的平均周转时间是最短的。

  1. 如何调试你的调度算法？

监控调度算法的执行状态、调度结果、算法特征等信息。

15.4 时间片轮转、多级反馈队列、公平共享调度算法和ucore调度框架

  1. 尝试描述下列处理机调度算法的工作原理和算法优缺点。
    • 时间片轮转算法（RR）
    • 多级反馈队列算法（MLFQ）
    • 公平共享调度算法（FSS）

让出CPU的条件：进程执行时间

就绪队列排队依据：多队列、多种排队依据、依据进程特征调整所在队列

算法特征：响应时间、平均周转时间、不同类型进程的调度差异

  1. RR算法选择时间片长度的依据有哪些？

进程切换开销

进程当前操作占用的CPU时间

切换开销与响应时间的折中权衡

  1. 请描述在MLFQ中，如何提升或降低进程的优先级？

I/O操作后提升优先级

时间片用完后降低优先级

  1. 尝试跟踪ucore中进程切换和调度算法的就绪进程选择过程。

中断响应、进程的中断现场保存、中断处理、调度判断、进程切换、新进程的中断现场恢复、新进程的继续执行

  1. 为什么要引入调度框架？定义调度算法接口需要考虑哪些因素？

引入调度框架的目的：分离调度操作和调度策略，以支持多种调度算法；

定义调度算法接口的考虑因素：调度算法需要的调度操作类型、调度算法在各调度操作中的体现方式；

  1. 通过观察FIFO、SJF和RR调度算法的模拟程序运行结果及其描述文档，理解其工作原理和算法特征。

  2. 通过观察MLFQ调度算法的模拟程序运行结果及其描述文档，理解其工作原理和算法特征。

  3. 通过观察彩票调度算法(Lottery scheduling)的模拟程序运行结果及其描述文档，理解其工作原理和算法特征。

15.5 实时调度和多处理器调度

  1. 什么是实时操作系统？

实时操作系统是保证在一定时间限制内完成特定功能的操作系统。

参考： http://baike.baidu.com/item/%E5%AE%9E%E6%97%B6%E6%93%8D%E4%BD%9C%E7%B3%BB%E7%BB%9F

  1. 什么是可调度性？

可调度表示一个实时操作系统能够满足任务时限要求

  1. 尝试描述下列处理机调度算法的工作原理和算法优缺点。
    • 速率单调调度算法(RM, Rate Monotonic)
    • 最早截止时间优先算法 (EDF, Earliest Deadline First)

任务优先级定义：按周期大小排队、按截止时间先后排队

RM的可调度条件：CPU利用率小于ln2时，是可调度的。

EDF的可调度条件：CPU利用率小于100%。

  1. 有兴趣的同学，请阅读下面论文，然后说明实时调度面临的主要困难是什么？

  2. 多处理机调度中每个处理机一个就绪队列与整个系统一个就绪队列有什么不同？

区别：调度开销、负载均衡程度

15.6 优先级反置

  1. 什么是优先级反置现象？

操作系统中出现高优先级进程长时间等待低优先级进程所占用资源的现象

  1. 什么是优先级继承(Priority Inheritance)和优先级天花板协议(priority ceiling protocol)？它们的区别是什么？

优先级继承：占用资源的低优先级进程继承申请资源的高优先级进程的优先级

优先级天花板协议：占用资源进程的优先级和所有可能申请该资源的进程的最高优先级相同

区别：提升占用资源的低优先级进程的优先级的时机不同

  1. 在单CPU情况下，基于以前的OS知识，能否设计一个更简单的方法（也许执行效率会低一些）解决优先级反置现象？

  2. ppt中“优先级继承”页里的图示有误，你能指出来吗？

小组练习与思考题

参考往届同学的处理机调度算法实现练习，从下列8个算法中选择一个你感兴趣的调度算法，对其实现进行完善，并分析算法特征。

(1)(spoc) 理解并实现FIFO调度算法

可基于“python, ruby, C, C++，LISP、JavaScript”等语言模拟实现，并给出测试，在试验报告写出设计思路和测试结果分析。

请参考scheduler-homework.py代码或独自实现。 最后统计采用不同调度算法的每个任务的相关时间和总体的平均时间：

　- turnaround time　周转时间 　- response time 响应时间 　- wait time　等待时间

对模拟环境的抽象

  • 任务/进程，及其执行时间 Job 0 (length = 1) Job 1 (length = 4) Job 2 (length = 7)

  • 何时切换？

  • 如何统计？

执行结果

采用FIFO调度算法

 ./scheduler-homework.py  -p FIFO
ARG policy FIFO
ARG jobs 3
ARG maxlen 10
ARG seed 0

Here is the job list, with the run time of each job: 
  Job 0 ( length = 9 )
  Job 1 ( length = 8 )
  Job 2 ( length = 5 )


** Solutions **

Execution trace:
  [ time   0 ] Run job 0 for 9.00 secs ( DONE at 9.00 )
  [ time   9 ] Run job 1 for 8.00 secs ( DONE at 17.00 )
  [ time  17 ] Run job 2 for 5.00 secs ( DONE at 22.00 )

Final statistics:
  Job   0 -- Response: 0.00  Turnaround 9.00  Wait 0.00
  Job   1 -- Response: 9.00  Turnaround 17.00  Wait 9.00
  Job   2 -- Response: 17.00  Turnaround 22.00  Wait 17.00

  Average -- Response: 8.67  Turnaround 16.00  Wait 8.67

(2)(spoc) 理解并实现SJF调度算法

可基于“python, ruby, C, C++，LISP、JavaScript”等语言模拟实现，并给出测试，在试验报告写出设计思路和测试结果分析。

执行结果

采用SJF调度算法

 ./scheduler-homework.py  -p SJF
ARG policy SJF
ARG jobs 3
ARG maxlen 10
ARG seed 0

Here is the job list, with the run time of each job: 
  Job 0 ( length = 9 )
  Job 1 ( length = 8 )
  Job 2 ( length = 5 )


** Solutions **

Execution trace:
  [ time   0 ] Run job 2 for 5.00 secs ( DONE at 5.00 )
  [ time   5 ] Run job 1 for 8.00 secs ( DONE at 13.00 )
  [ time  13 ] Run job 0 for 9.00 secs ( DONE at 22.00 )

Final statistics:
  Job   2 -- Response: 0.00  Turnaround 5.00  Wait 0.00
  Job   1 -- Response: 5.00  Turnaround 13.00  Wait 5.00
  Job   0 -- Response: 13.00  Turnaround 22.00  Wait 13.00

  Average -- Response: 6.00  Turnaround 13.33  Wait 6.00

(3)(spoc) 理解并实现RR调度算法

可基于“python, ruby, C, C++，LISP、JavaScript”等语言模拟实现，并给出测试，在试验报告写出设计思路和测试结果分析。

执行结果

采用RR调度算法

 ./scheduler-homework.py  -p RR
ARG policy RR
ARG jobs 3
ARG maxlen 10
ARG seed 0

Here is the job list, with the run time of each job: 
  Job 0 ( length = 9 )
  Job 1 ( length = 8 )
  Job 2 ( length = 5 )


** Solutions **

Execution trace:
  [ time   0 ] Run job   0 for 1.00 secs
  [ time   1 ] Run job   1 for 1.00 secs
  [ time   2 ] Run job   2 for 1.00 secs
  [ time   3 ] Run job   0 for 1.00 secs
  [ time   4 ] Run job   1 for 1.00 secs
  [ time   5 ] Run job   2 for 1.00 secs
  [ time   6 ] Run job   0 for 1.00 secs
  [ time   7 ] Run job   1 for 1.00 secs
  [ time   8 ] Run job   2 for 1.00 secs
  [ time   9 ] Run job   0 for 1.00 secs
  [ time  10 ] Run job   1 for 1.00 secs
  [ time  11 ] Run job   2 for 1.00 secs
  [ time  12 ] Run job   0 for 1.00 secs
  [ time  13 ] Run job   1 for 1.00 secs
  [ time  14 ] Run job   2 for 1.00 secs ( DONE at 15.00 )
  [ time  15 ] Run job   0 for 1.00 secs
  [ time  16 ] Run job   1 for 1.00 secs
  [ time  17 ] Run job   0 for 1.00 secs
  [ time  18 ] Run job   1 for 1.00 secs
  [ time  19 ] Run job   0 for 1.00 secs
  [ time  20 ] Run job   1 for 1.00 secs ( DONE at 21.00 )
  [ time  21 ] Run job   0 for 1.00 secs ( DONE at 22.00 )

Final statistics:
  Job   0 -- Response: 0.00  Turnaround 22.00  Wait 13.00
  Job   1 -- Response: 1.00  Turnaround 21.00  Wait 13.00
  Job   2 -- Response: 2.00  Turnaround 15.00  Wait 10.00

  Average -- Response: 1.00  Turnaround 19.33  Wait 12.00

(4)理解并实现MLFQ调度算法

可基于“python, ruby, C, C++，LISP、JavaScript”等语言模拟实现，并给出测试，在试验报告写出设计思路和测试结果分析。

(5)理解并实现stride调度算法

可基于“python, ruby, C, C++，LISP、JavaScript”等语言模拟实现，并给出测试，在试验报告写出设计思路和测试结果分析。

(6)理解并实现EDF实时调度算法

可基于“python, ruby, C, C++，LISP、JavaScript”等语言模拟实现，并给出测试，在试验报告写出设计思路和测试结果分析。

(7)理解并实现RM实时调度算法

可基于“python, ruby, C, C++，LISP、JavaScript”等语言模拟实现，并给出测试，在试验报告写出设计思路和测试结果分析。

(8)理解并实现优先级反置方法

可基于“python, ruby, C, C++，LISP、JavaScript”等语言模拟实现，并给出测试，在试验报告写出设计思路和测试结果分析。

问答题

单处理机调度

Q1：[基础] 非抢占式的调度算法，以及抢占式的调度算法，他们的优点各是什么？

A:

Q2：[进阶] Linux 2.6 引入了 “内核抢占” 技术。简单的说，如果运行内核态代码时发生时钟中断，支持内核抢占的系统在处理完时钟中断后，允许发生进程切换。引入内核抢占有什么好处？又有什么挑战？（高阶）ucore / rcore 现在是可抢占的吗？

A:

Q3：[基础] 假设我们简单的将任务分为两种：前台交互（要求短时延）、后台计算（任务量大）。下列任务分别是前台还是后台？a) make 编译 linux; b) vim 光标移动; c) firefox 下载影片; d) 某游戏处理玩家点击鼠标开枪; e) 播放令人愉悦的歌曲; f) 转码十分有意思的视频。除此以外，想想你日常的任务，它们哪些是前台，哪些是后台的？

A:

Q4：[基础] RR 算法的时间片长短有什么影响？

A:

Q5：[进阶] MLFQ 算法并不公平，恶意的用户程序可以愚弄 MLFQ 算法，大幅挤占其他进程的时间。（MLFQ 的规则：“如果一个进程，时间片用完了它还在执行用户计算，那么 MLFQ 下调它的优先级”）你能举出一个例子，使得你的用户程序能够挤占其他进程的时间吗？

A:

Q6：[基础] 课上讲的 MLFQ 只提到了降低优先级，这会导致什么问题？如何解决？

A:

Q7：[进阶] Linux 内核代码中，持有资源（例如 spinlock，不过具体是什么资源不重要）的时候会关闭内核抢占。仅从本节课的内容来说，请问这是为了避免什么现象？

A:

Q8：[进阶] SMP 调度中，将进程动态指派到各个处理器上，效率方面的好处是使得各个处理器负载均衡。那么这样做，效率方面不好的地方是什么？

A:

多处理机调度

多核处理器

Q1：[基础] 对称多处理（SMP）和非一致内存访问（NUMA）最主要的区别是什么？它们分别适用于哪些场景？你面前的这台设备使用的是那种？

A:

Q2：[进阶] 考虑两台计算机，A 有一个 4 核 8 线程 CPU，B 有两个 4 核 4 线程的 CPU。假设每个核的性能大致相同。那么对于计算密集型和访存密集型的多线程程序，你觉得分别在哪台计算机上跑得更快一些？

A:

多核调度

Q3：[基础] 多核执行和调度引入了哪些新的问题和挑战？

A:

Q4：[基础] 工作窃取技术要解决什么问题？简述它的做法。

A:

O(1) 调度

Q5：[基础] 为什么它叫 O(1)调度器？我们知道常见的数据结构（如平衡树、Hash 表、数组、链表），都无法做到插入、删除、查找复杂度均为 O(1)。那么 O(1)调度器是如何做到这一点的？

A:

CFS 调度

Q6：[基础] CFS 的全称是什么？它为了解决 O(1)调度的哪些问题？算法如何体现其名字蕴含的特点？

A:

Q7：[基础] CFS 使用红黑树的原因是什么？为什么 O(logN)的算法会比 O(1)效果好？

A:

Q8：[进阶] vruntime 的意义是什么？对于休眠进程 vruntime 要如何处理？

A:

Q9：[进阶] 你是否认同 CFS 的做法达到了完全公平的目标？为什么？

A:

BFS 调度

Q10：[基础] BFS 的全称是什么？它为了解决 CFS 调度的哪些问题？算法如何体现其名字蕴含的特点？

A:

Q11： [扩展] BFS 蕴含了哪些哲学思想？体现了计算机系统领域的哪些特点？

A: