操作系统导论-进程调度方法

本文最后更新于: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,200100的顺序一次执行任务的时候,对于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,依次执行102030有以下结果

    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=1N1iQN=Qi=1N1iN=QN(N1)2N=Q(N1)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}


操作系统导论-进程调度方法
https://halc.top/p/28ea7a49
作者
HalcyonAzure
发布于
2022年3月28日
许可协议