OSTEP：进程的调度策略

本文最后更新于：2022年4月23日 下午

第七章：进程调度/介绍

参数介绍：

Response：响应时间，即任务第一次运行的时间

Turnaround: 完成时刻（周转时间），即任务完成那一刻对应的时间

Wait: 等待中时间，即任务处于Ready状态，但当前CPU在执行其他任务的等待时间

  1. 执行结果如下

    FIFO:

    1
    2
    3
    4
    5
    6
    7
    8
    9
    10
    11
    12
    13
    14
    15
    16
    17
    18
    19
    20
    21
    ARG policy FIFO
    ARG jlist 200,200,200

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

    **Solutions**

    Execution trace:
    [ time   0 ] Run job 0 for 200.00 secs ( DONE at 200.00 )
    [ time 200 ] Run job 1 for 200.00 secs ( DONE at 400.00 )
    [ time 400 ] Run job 2 for 200.00 secs ( DONE at 600.00 )

    Final statistics:
    Job   0 -- Response: 0.00  Turnaround 200.00  Wait 0.00
    Job   1 -- Response: 200.00  Turnaround 400.00  Wait 200.00
    Job   2 -- Response: 400.00  Turnaround 600.00  Wait 400.00

    Average -- Response: 200.00  Turnaround 400.00  Wait 200.00

    同时，对于SJF(Short Job First)，由于每个任务的执行时间相同，所以策略上的处理结果和FIFO相同，不额外列出

  2. 在按照300,200和100的顺序一次执行任务的时候，对于FIFO策略依次执行，而依据SJF策略，则会先执行时间短的100，依次到最常的300。具体结果如下

    FIFO

    1
    2
    3
    4
    5
    6
    7
    8
    9
    10
    11
    12
    13
    14
    15
    16
    17
    18
    19
    20
    21
    ARG policy FIFO
    ARG jlist 300,200,100

    Here is the job list, with the run time of each job:
    Job 0 ( length = 300.0 )
    Job 1 ( length = 200.0 )
    Job 2 ( length = 100.0 )

    **Solutions**

    Execution trace:
    [ time   0 ] Run job 0 for 300.00 secs ( DONE at 300.00 )
    [ time 300 ] Run job 1 for 200.00 secs ( DONE at 500.00 )
    [ time 500 ] Run job 2 for 100.00 secs ( DONE at 600.00 )

    Final statistics:
    Job   0 -- Response: 0.00  Turnaround 300.00  Wait 0.00
    Job   1 -- Response: 300.00  Turnaround 500.00  Wait 300.00
    Job   2 -- Response: 500.00  Turnaround 600.00  Wait 500.00

    Average -- Response: 266.67  Turnaround 466.67  Wait 266.67

    SJF

    1
    2
    3
    4
    5
    6
    7
    8
    9
    10
    11
    12
    13
    14
    15
    16
    17
    18
    19
    20
    21
    ARG policy SJF
    ARG jlist 300,200,100

    Here is the job list, with the run time of each job:
    Job 0 ( length = 300.0 )
    Job 1 ( length = 200.0 )
    Job 2 ( length = 100.0 )

    **Solutions**

    Execution trace:
    [ time   0 ] Run job 2 for 100.00 secs ( DONE at 100.00 )
    [ time 100 ] Run job 1 for 200.00 secs ( DONE at 300.00 )
    [ time 300 ] Run job 0 for 300.00 secs ( DONE at 600.00 )

    Final statistics:
    Job   2 -- Response: 0.00  Turnaround 100.00  Wait 0.00
    Job   1 -- Response: 100.00  Turnaround 300.00  Wait 100.00
    Job   0 -- Response: 300.00  Turnaround 600.00  Wait 300.00

    Average -- Response: 133.33  Turnaround 333.33  Wait 133.33

    SJF的好处在于可以先执行时间短的程序，后执行时间长的程序，同时优化了程序的响应、完成和等待时间。缺点在于因为必须先完整的运行某个任务，后执行下一个任务。如果此时需要高频率执行某任务则无能为力（比如高频率的io输出）

  3. 采用RR策略，时间片设置为1，依次执行10、20和30有以下结果

    RR策略
    1
    2
    3
    4
    5
    6
    7
    8
    9
    10
    11
    12
    13
    14
    15
    16
    17
    18
    19
    20
    21
    22
    23
    24
    25
    26
    27
    28
    29
    30
    31
    32
    33
    34
    35
    36
    37
    38
    39
    40
    41
    42
    43
    44
    45
    46
    47
    48
    49
    50
    51
    52
    53
    54
    55
    56
    57
    58
    59
    60
    61
    62
    63
    64
    65
    66
    67
    68
    69
    70
    71
    72
    73
    74
    75
    76
    77
    78
    79
    ARG policy RR
    ARG jlist 10,20,30
       
    Here is the job list, with the run time of each job:
    Job 0 ( length = 10.0 )
    Job 1 ( length = 20.0 )
    Job 2 ( length = 30.0 )


    ** 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
    [ time  15 ] Run job   0 for 1.00 secs
    [ time  16 ] Run job   1 for 1.00 secs
    [ time  17 ] Run job   2 for 1.00 secs
    [ time  18 ] Run job   0 for 1.00 secs
    [ time  19 ] Run job   1 for 1.00 secs
    [ time  20 ] Run job   2 for 1.00 secs
    [ time  21 ] Run job   0 for 1.00 secs
    [ time  22 ] Run job   1 for 1.00 secs
    [ time  23 ] Run job   2 for 1.00 secs
    [ time  24 ] Run job   0 for 1.00 secs
    [ time  25 ] Run job   1 for 1.00 secs
    [ time  26 ] Run job   2 for 1.00 secs
    [ time  27 ] Run job   0 for 1.00 secs ( DONE at 28.00 )
    [ time  28 ] Run job   1 for 1.00 secs
    [ time  29 ] Run job   2 for 1.00 secs
    [ time  30 ] Run job   1 for 1.00 secs
    [ time  31 ] Run job   2 for 1.00 secs
    [ time  32 ] Run job   1 for 1.00 secs
    [ time  33 ] Run job   2 for 1.00 secs
    [ time  34 ] Run job   1 for 1.00 secs
    [ time  35 ] Run job   2 for 1.00 secs
    [ time  36 ] Run job   1 for 1.00 secs
    [ time  37 ] Run job   2 for 1.00 secs
    [ time  38 ] Run job   1 for 1.00 secs
    [ time  39 ] Run job   2 for 1.00 secs
    [ time  40 ] Run job   1 for 1.00 secs
    [ time  41 ] Run job   2 for 1.00 secs
    [ time  42 ] Run job   1 for 1.00 secs
    [ time  43 ] Run job   2 for 1.00 secs
    [ time  44 ] Run job   1 for 1.00 secs
    [ time  45 ] Run job   2 for 1.00 secs
    [ time  46 ] Run job   1 for 1.00 secs
    [ time  47 ] Run job   2 for 1.00 secs
    [ time  48 ] Run job   1 for 1.00 secs ( DONE at 49.00 )
    [ time  49 ] Run job   2 for 1.00 secs
    [ time  50 ] Run job   2 for 1.00 secs
    [ time  51 ] Run job   2 for 1.00 secs
    [ time  52 ] Run job   2 for 1.00 secs
    [ time  53 ] Run job   2 for 1.00 secs
    [ time  54 ] Run job   2 for 1.00 secs
    [ time  55 ] Run job   2 for 1.00 secs
    [ time  56 ] Run job   2 for 1.00 secs
    [ time  57 ] Run job   2 for 1.00 secs
    [ time  58 ] Run job   2 for 1.00 secs
    [ time  59 ] Run job   2 for 1.00 secs ( DONE at 60.00 )

    Final statistics:
    Job   0 -- Response: 0.00  Turnaround 28.00  Wait 18.00
    Job   1 -- Response: 1.00  Turnaround 49.00  Wait 29.00
    Job   2 -- Response: 2.00  Turnaround 60.00  Wait 30.00

    Average -- Response: 1.00  Turnaround 45.67  Wait 25.67

    采用RR策略的时候通过轮转运行三个程序，达到类似"同时"运行程序的效果，缩短了任务的反应时间。缺点是由于轮询过程会同时运行其他任务，因此总体的完成时刻和等待时间都会延长。

  4. 由于SJF是“短任务优先”的调度策略，因此当到达的任务顺序为先短时间的任务，后长时间任务的时候，SJF和FIFO的周转时间是相同的

  5. 当RR策略的量子时间大于等于SJF的单个任务最长工作时间时，SJF和RR可以提供相同的响应时间

  6. 当工作长度逐渐增加的时候，SJF的响应时间会逐渐增加，因为SJF必须要完成一个完整的任务才会运行下一个任务，因此后面的任务响应时间必须等待前一个任务的完成，模拟省略。

  7. 假定所有任务的长度都大于量子长度，且完成任务的时间都为量子长度的倍数，则可推得以下公式

∑i=1N−1iQN=Q∑i=1N−1iN=Q∗N(N−1)2N=Q(N−1)2\frac{\sum_{i=1}^{N-1} iQ}{N}=\frac{Q \sum_{i=1}^{N-1} i}{N}=\frac{Q * \frac{N(N-1)}{2}}{N}=\frac{Q(N-1)}{2}

知识记录
#OS
OSTEP：进程的调度策略
https://halc.top/p/28ea7a49
作者
HalcyonAzure
发布于
2022年3月28日
许可协议