这里回顾第9章,本章介绍了调度:比例份额。

书籍介绍:

学习资料:

第9 章 调度:比例份额

内容回顾

关键概念

  • 比例份额(proportional-share)调度程序,也称公平份额(fair-share)调度程序
    • 因为调度程序的最终目标是确保每个工作获得一定比例的CPU 时间
  • 彩票调度(lottery scheduling)
    • 每个进程拥有一定的彩票数,不断定时地抽取彩票,彩票调度从概率上(但不是确定的)获得这种份额比例
    • 相关概念
      • 彩票货币(ticket currency)
        • 这种方式允许拥有一组彩票的用户以他们喜欢的某种货币,将彩票分给自己的不同工作。之后操作系统再自动将这种货币兑换为正确的全局彩票。
      • 彩票转让(ticket transfer)
        • 进程可以临时将自己的彩票交给另一个进程。
      • 彩票通胀(ticket inflation)
        • 进程可以临时提升或降低自己拥有的彩票数量。
      • 不公平指标U(unfairness metric)
        • U为两个工作完成时刻相除的值。
  • 步长调度(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

略过。