OSTEP Chapter 9 回顾
这里回顾第9章,本章介绍了调度:比例份额。
书籍介绍:
学习资料:
- https://pages.cs.wisc.edu/~remzi/OSTEP/
- https://github.com/remzi-arpacidusseau/ostep-translations/tree/master/chinese
- https://github.com/joshuap233/Operating-Systems-Three-Easy-Pieces-NOTES
第9 章 调度:比例份额
内容回顾
关键概念
- 比例份额(proportional-share)调度程序,也称公平份额(fair-share)调度程序
- 因为调度程序的最终目标是确保每个工作获得一定比例的CPU 时间
- 彩票调度(lottery scheduling)
- 每个进程拥有一定的彩票数,不断定时地抽取彩票,彩票调度从概率上(但不是确定的)获得这种份额比例
- 相关概念
- 彩票货币(ticket currency)
- 这种方式允许拥有一组彩票的用户以他们喜欢的某种货币,将彩票分给自己的不同工作。之后操作系统再自动将这种货币兑换为正确的全局彩票。
- 彩票转让(ticket transfer)
- 进程可以临时将自己的彩票交给另一个进程。
- 彩票通胀(ticket inflation)
- 进程可以临时提升或降低自己拥有的彩票数量。
- 不公平指标U(unfairness metric)
- U为两个工作完成时刻相除的值。
- 彩票货币(ticket currency)
- 步长调度(stride scheduling)
- 用来解决彩票调度不确定性的问题
- 每个工作都有自己的步长,这个值与票数值成反比
- 进程有计数器[称为行程(pass)值],初始化为0
- 调度规则:当需要进行调度时,选择目前拥有最小行程值的进程,并且在运行之后将该进程的行程值增加步长
- 可以在调度周期内做到比例完全正确
- 缺点是需要记录全局状态
作业
1
只计算一个结果:
λ python ./lottery.py -j 3 -s 1
ARG jlist
ARG jobs 3
ARG maxlen 10
ARG maxticket 100
ARG quantum 1
ARG seed 1
Here is the job list, with the run time of each job:
Job 0 ( length = 1, tickets = 84 )
Job 1 ( length = 7, tickets = 25 )
Job 2 ( length = 4, tickets = 44 )
Here is the set of random numbers you will need (at most):
Random 651593
Random 788724
Random 93859
Random 28347
Random 835765
Random 432767
Random 762280
Random 2106
Random 445387
Random 721540
Random 228762
Random 945271
计算过程:
总彩票数: 153
Job 0: 0-83
Job 1: 84-108
Job 2: 109-152
Job 0完成后:
Job 1: 0-24
Job 2: 25-68
651593 % 153 = 119 => run Job 2
788724 % 153 = 9 => run Job 0 (Job 0完成, 后续不参与调度)
93859 % 69 = 19 => run Job 1
28347 % 69 = 57 => run Job 2
835765 % 69 = 37 => run Job 2
432767 % 69 = 68 => run Job 2 (Job 2完成, 后续不参与调度)
762280 % 25 = 5 => run Job 1
2106 % 25 = 6 => run Job 1
445387 % 25 = 12 => run Job 1
721540 % 25 = 15 => run Job 1
228762 % 25 = 12 => run Job 1
945271 % 25 = 21 => run Job 1
验证:
λ python ./lottery.py -j 3 -s 1 -c
ARG jlist
ARG jobs 3
ARG maxlen 10
ARG maxticket 100
ARG quantum 1
ARG seed 1
Here is the job list, with the run time of each job:
Job 0 ( length = 1, tickets = 84 )
Job 1 ( length = 7, tickets = 25 )
Job 2 ( length = 4, tickets = 44 )
** Solutions **
Random 651593 -> Winning ticket 119 (of 153) -> Run 2
Jobs:
( job:0 timeleft:1 tix:84 ) ( job:1 timeleft:7 tix:25 ) (* job:2 timeleft:4 tix:44 )
Random 788724 -> Winning ticket 9 (of 153) -> Run 0
Jobs:
(* job:0 timeleft:1 tix:84 ) ( job:1 timeleft:7 tix:25 ) ( job:2 timeleft:3 tix:44 )
--> JOB 0 DONE at time 2
Random 93859 -> Winning ticket 19 (of 69) -> Run 1
Jobs:
( job:0 timeleft:0 tix:--- ) (* job:1 timeleft:7 tix:25 ) ( job:2 timeleft:3 tix:44 )
Random 28347 -> Winning ticket 57 (of 69) -> Run 2
Jobs:
( job:0 timeleft:0 tix:--- ) ( job:1 timeleft:6 tix:25 ) (* job:2 timeleft:3 tix:44 )
Random 835765 -> Winning ticket 37 (of 69) -> Run 2
Jobs:
( job:0 timeleft:0 tix:--- ) ( job:1 timeleft:6 tix:25 ) (* job:2 timeleft:2 tix:44 )
Random 432767 -> Winning ticket 68 (of 69) -> Run 2
Jobs:
( job:0 timeleft:0 tix:--- ) ( job:1 timeleft:6 tix:25 ) (* job:2 timeleft:1 tix:44 )
--> JOB 2 DONE at time 6
Random 762280 -> Winning ticket 5 (of 25) -> Run 1
Jobs:
( job:0 timeleft:0 tix:--- ) (* job:1 timeleft:6 tix:25 ) ( job:2 timeleft:0 tix:--- )
Random 2106 -> Winning ticket 6 (of 25) -> Run 1
Jobs:
( job:0 timeleft:0 tix:--- ) (* job:1 timeleft:5 tix:25 ) ( job:2 timeleft:0 tix:--- )
Random 445387 -> Winning ticket 12 (of 25) -> Run 1
Jobs:
( job:0 timeleft:0 tix:--- ) (* job:1 timeleft:4 tix:25 ) ( job:2 timeleft:0 tix:--- )
Random 721540 -> Winning ticket 15 (of 25) -> Run 1
Jobs:
( job:0 timeleft:0 tix:--- ) (* job:1 timeleft:3 tix:25 ) ( job:2 timeleft:0 tix:--- )
Random 228762 -> Winning ticket 12 (of 25) -> Run 1
Jobs:
( job:0 timeleft:0 tix:--- ) (* job:1 timeleft:2 tix:25 ) ( job:2 timeleft:0 tix:--- )
Random 945271 -> Winning ticket 21 (of 25) -> Run 1
Jobs:
( job:0 timeleft:0 tix:--- ) (* job:1 timeleft:1 tix:25 ) ( job:2 timeleft:0 tix:--- )
--> JOB 1 DONE at time 12
2
运行:
λ python ./lottery.py -l 10:1,10:100 -s 1 -c
ARG jlist 10:1,10:100
ARG jobs 3
ARG maxlen 10
ARG maxticket 100
ARG quantum 1
ARG seed 1
Here is the job list, with the run time of each job:
Job 0 ( length = 10, tickets = 1 )
Job 1 ( length = 10, tickets = 100 )
** Solutions **
Random 134364 -> Winning ticket 34 (of 101) -> Run 1
Jobs:
( job:0 timeleft:10 tix:1 ) (* job:1 timeleft:10 tix:100 )
Random 847434 -> Winning ticket 44 (of 101) -> Run 1
Jobs:
( job:0 timeleft:10 tix:1 ) (* job:1 timeleft:9 tix:100 )
Random 763775 -> Winning ticket 13 (of 101) -> Run 1
Jobs:
( job:0 timeleft:10 tix:1 ) (* job:1 timeleft:8 tix:100 )
Random 255069 -> Winning ticket 44 (of 101) -> Run 1
Jobs:
( job:0 timeleft:10 tix:1 ) (* job:1 timeleft:7 tix:100 )
Random 495435 -> Winning ticket 30 (of 101) -> Run 1
Jobs:
( job:0 timeleft:10 tix:1 ) (* job:1 timeleft:6 tix:100 )
Random 449491 -> Winning ticket 41 (of 101) -> Run 1
Jobs:
( job:0 timeleft:10 tix:1 ) (* job:1 timeleft:5 tix:100 )
Random 651593 -> Winning ticket 42 (of 101) -> Run 1
Jobs:
( job:0 timeleft:10 tix:1 ) (* job:1 timeleft:4 tix:100 )
Random 788724 -> Winning ticket 15 (of 101) -> Run 1
Jobs:
( job:0 timeleft:10 tix:1 ) (* job:1 timeleft:3 tix:100 )
Random 93859 -> Winning ticket 30 (of 101) -> Run 1
Jobs:
( job:0 timeleft:10 tix:1 ) (* job:1 timeleft:2 tix:100 )
Random 28347 -> Winning ticket 67 (of 101) -> Run 1
Jobs:
( job:0 timeleft:10 tix:1 ) (* job:1 timeleft:1 tix:100 )
--> JOB 1 DONE at time 10
Random 835765 -> Winning ticket 0 (of 1) -> Run 0
Jobs:
(* job:0 timeleft:10 tix:1 ) ( job:1 timeleft:0 tix:--- )
Random 432767 -> Winning ticket 0 (of 1) -> Run 0
Jobs:
(* job:0 timeleft:9 tix:1 ) ( job:1 timeleft:0 tix:--- )
Random 762280 -> Winning ticket 0 (of 1) -> Run 0
Jobs:
(* job:0 timeleft:8 tix:1 ) ( job:1 timeleft:0 tix:--- )
Random 2106 -> Winning ticket 0 (of 1) -> Run 0
Jobs:
(* job:0 timeleft:7 tix:1 ) ( job:1 timeleft:0 tix:--- )
Random 445387 -> Winning ticket 0 (of 1) -> Run 0
Jobs:
(* job:0 timeleft:6 tix:1 ) ( job:1 timeleft:0 tix:--- )
Random 721540 -> Winning ticket 0 (of 1) -> Run 0
Jobs:
(* job:0 timeleft:5 tix:1 ) ( job:1 timeleft:0 tix:--- )
Random 228762 -> Winning ticket 0 (of 1) -> Run 0
Jobs:
(* job:0 timeleft:4 tix:1 ) ( job:1 timeleft:0 tix:--- )
Random 945271 -> Winning ticket 0 (of 1) -> Run 0
Jobs:
(* job:0 timeleft:3 tix:1 ) ( job:1 timeleft:0 tix:--- )
Random 901428 -> Winning ticket 0 (of 1) -> Run 0
Jobs:
(* job:0 timeleft:2 tix:1 ) ( job:1 timeleft:0 tix:--- )
Random 30590 -> Winning ticket 0 (of 1) -> Run 0
Jobs:
(* job:0 timeleft:1 tix:1 ) ( job:1 timeleft:0 tix:--- )
--> JOB 0 DONE at time 20
在工作1完成之前不会运行工作0,一般来说,会优先完成比例最大的工作。
3, 4
python ./lottery.py -l 1100:100,100:100 -c -s 1
和时间片有关,时间片越小,越公平。
5
略过。
本博客所有文章除特别声明外,均采用 CC BY-NC-SA 4.0 许可协议。转载请注明来自 Doraemonzzz!
评论
ValineLivere